leetcode-287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, O(1) extra space.
  3. Your runtime complexity should be less than
    O(n<sup>2</sup>)

    .

  4. There is only one duplicate number in the array, but it could be repeated more than once.

题目描述:

给定长度为n+1的整形数组,该数组的每一个整数均在[1,n]之间。

假设只有一个重复的数字,请找出该重复数字。

注意:

1.不能修改数组(假设数组只读)

2.空间复杂度为O(1)

3.时间复杂度小于O(n^2)

4.数组中只有一个重复数字,但是它可能重复不止一次。

 

思路:

根据抽屉原理,如果数组中不超过n/2的元素的数目大于n/2,那么重复数字肯定出现在前半段。反之出现在后半段。导致这种结果的原因在于数组只有一个数字是重复的,也就是说n个数字不重复。超过一半的数字处于平均值之下,那么重复数字 只可能在前半部分。

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        right = len(nums)-1
        left = 1


        while left < right:
            mid = left + (right-left)/2
            counter = 0
            for num in nums:
                if num <= mid:
                    counter += 1
            if counter > mid:
                right = mid-1
            else:
                left = mid+1
        return left

leetcode-41.First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given

[1,2,0]

return

3

,
and

[3,4,-1,1]

return

2

.

Your algorithm should run in O(n) time and uses constant space.

题目描述:

给出无序的整数数组,找出第一个缺失的正数。

例如,

[1,2,0] 返回 3

[3,4,-1,1]返回2

算法的时间复杂度不超过O(n)并且使用常量空间。

思路:

题目要求是找到缺失的第一个正数,那么我们只把数组中是正数的元素交换到其在数组中其元素值的位置,比如a[5] = 3,那么将a[5]与a[2]交换。

这样正数都会被放置在其应该处于的位置,而负数以及元素值超过数组长度的数跳过。最后所有的有效正数都会被放置在其对应的位置。

等全部交换完成后从头开始查找第一个元素其元素值与位置不符,返回该元素位置。

Python代码示例:

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        while i < len(nums):
            if nums[i] != i+1 and nums[i] < len(nums) and nums[i] >= 1 and nums[i] != nums[nums[i]-1]:
                tmp = nums[i]
                nums[i] = nums[tmp-1]
                nums[tmp-1] = tmp
            else:
                i += 1
        print nums
        for i in xrange(len(nums)):
            if i+1 != nums[i]:
                return i+1
        return len(nums)+1

约瑟夫环

普通的解法:构建环然后循环去除元素

int JosephuseCircle(unsigned int n,unsigned int m){
if(n<1||m<1) return -1;
unsigned int i=0;
list<int> l;
for(i=0;i<n;++i)
l.push_back(i);
list<int>::iterator cur = l.begin();
while(l.size()>1){
for(int i=1;i<m;++i){
cur++;
if(cur == l.end())
cur = l.begin();
}
list<int>::iterator next = ++cur;
if(next == l.end())
next = l.begin();
–cur;
l.erase(cur);
cur = next;
}
return *(cur);
}

更高效的解决方法:构建递推公式

  1.  定义关于数据长度n和删除步进m的方程F(n,m),表示在n个数字0,1,…,n-1中每次删除第m个数字后最后剩下的一个数字。
  2. 在n的数字中,第一个被删除的是(m-1)%n,简记为k。那么剩下的n-1个数字是0,1,…,k-1,k+1,…,n-1.并且下一次删除从k+1开始。
  3. 在第二次删除时,数字序列是 k+1,k+2,…,n-1,0,1,…k-1。
  4. 此时的函数F(n,m)的数字序列发生了变化,为了适应该变化我们将此时的F(n,m)记为F'(n-1,m)
  5. 由于F与F’的结果都是最后一个数字,那么F(n,m)=F'(n-1,n)
  6. 然后对第二次的数字序列做映射:

k+1              ===>                       0

k+2              ===>                       1

n-1              ===>                       n-1-k-1=n-k-2

0                  ===>                       n-k-1

1                   ===>                      n-k

k-1                ===>                       n-2

7.从上面得出映射 p(x) = (x-k-1)%n,表示当前映射数字x实际上是F(n,m)中的第(x-k-1)%n个数字。逆映射p^-1(x) = (x+k+1)%n;

8.由于映射后的序列与最初的序列都具有同样的形式即都从0开始,那么仍然可以F(n-1,m)表示。可以得出

F'(n-1,m) = p^-1(F(n-1,m))=映射之前剩下的最后一个数字=[F(n-1,m)+k+1]%n

把k = (m-1)%n带入,那么F(n,m) = F'(n-1,m)=[F(n-1,m)+m]%n

9:上面的公式可以归纳为以下公式:

F(n,m)=0 if  n=1 else [F(n-1,m)+m]%n 

这是一个递归的求解过程,因为最后n=1时有具体的结果不会再继续递归下去。
int JosephuseCircle2(unsigned int n,unsigned int m){
if(n<1||m<1)
return -1;
int last = 0;
for(int i=2;i<=n;++i){
last = (last+m)%i;
}
return last;
}

Mysql 4种事务隔离级别

获取隔离级别:

select @@global.tx_isolation, @@tx_isolation;

隔离级别说明:

=============================================================================
隔离级别               脏读(Dirty Read)          不可重复读(NonRepeatable Read)     幻读(Phantom Read)
=============================================================================

未提交读(Read uncommitted)        可能                            可能                       可能

已提交读(Read committed)          不可能                          可能                        可能

可重复读(Repeatable read)          不可能                          不可能                     可能

可串行化(Serializable )                不可能                          不可能                     不可能

=============================================================================

·未提交读(Read Uncommitted):允许脏读,也就是可能读取到其他会话中未提交事务修改的数据

·提交读(Read Committed):只能读取到已经提交的数据。Oracle等多数数据库默认都是该级别 (不重复读)

·可重复读(Repeated Read):可重复读。在同一个事务内的查询都是事务开始时刻一致的,InnoDB默认级别。在SQL标准中,该隔离级别消除了不可重复读,但是还存在幻象读

·串行读(Serializable):完全串行化的读,每次读都需要获得表级共享锁,读写相互都会阻塞

Centos系统降级(7.2.1511->7.1.1503)

1.下载7.1.1503的release包(centos-release-7-1.1503.el7.centos.2.8.x86_64.rpm):

http://rpm.pbone.net/index.php3?stat=3&search=centos-release&srodzaj=3上有下载链接:

ftp://bo.mirror.garr.it/1/slc/centos/7.1.1503/os/x86_64/Packages/centos-release-7-1.1503.el7.centos.2.8.x86_64.rpm

2.强制安装旧的release包并删除新版本:

rpm -Uvh –oldpackage centos-release-7-1.1503.el7.centos.2.8.x86_64.rpm

leetCode-319. Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3. 
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 
So you should return 1, because there is only one bulb is on.

继续阅读“leetCode-319. Bulb Switcher”

Centos6挂载40T RAID磁盘

因为ext文件系统本身分区表的限制导致无法管理超过16T的文件系统,那么当超过16T时采用XFS文件系统就可以解决问题。

 

1.使用parted创建GPT分区

2.使用mkfs.xfs -f 命令格式化GPT为XFS文件系统

注意:Centos6如果没有mkfs.xfs命令,可以通过rpm安装。下面放下地址:

http://pkgs.org/centos-6/centos-x86_64/xfsprogs-3.1.1-4.el6.x86_64.rpm

http://pkgs.org/centos-6/centos-x86_64/xfsdump-3.0.4-4.el6_6.1.x86_64.rpm

下载上面的两个rpm并按顺序安装好就可以使用mkfs.xfs进行格式化了。

Composer安装时握手失败的解决

在win10中安装Composer出现如下错误:

 

Connection Error [ERR_CONNECTION]: Unable to connect to getcomposer.org Request tohttps://getcomposer.org/installer failed with errors: SSL: Handshake timed out. Failed to enable crypto. Failed to open stream: operation failed

 

解决方法:

在php.ini中修改


<span class="pln">curl</span><span class="pun">.</span><span class="pln">cainfo</span><span class="pun">=</span><span class="str">/path/</span><span class="pln">to</span><span class="pun">/</span><span class="pln">ssl</span><span class="pun">-</span><span class="pln">certs</span><span class="pun">/</span><span class="pln">ca</span><span class="pun">-</span><span class="pln">bundle</span><span class="pun">.</span><span class="pln">crt
openssl</span><span class="pun">.</span><span class="pln">cafile</span><span class="pun">=</span><span class="str">/path/</span><span class="pln">to</span><span class="pun">/</span><span class="pln">ssl</span><span class="pun">-</span><span class="pln">certs</span><span class="pun">/</span><span class="pln">ca</span><span class="pun">-</span><span class="pln">bundle</span><span class="pun">.</span><span class="pln">crt

</span>

<span class="pln">ca</span><span class="pun">-</span><span class="pln">bundle</span><span class="pun">.</span><span class="pln">crt的内容从下面链接获取:
https://curl.haxx.se/ca/cacert.pem
########################################################
将内容保存到</span>
<span class="pln">ca</span><span class="pun">-</span><span class="pln">bundle</span><span class="pun">.</span><span class="pln">crt</span>

堆排序的C++实现

堆排序的要点在于【向上调整堆】以及【向下调整堆】。

将这两个要点搞清楚堆排序就很简单了。

—————————————————————–

#include <iostream>
#include <vector>
using namespace std;

//辅助函数
void Swap(vector<int> &v,int i,int j){
v[i]^= v[j];
v[j]^= v[i];
v[i]^= v[j];
}
void Print(vector<int> v){
for(auto vi = v.begin();vi!=v.end();++vi) cout<<*vi<<” “;
cout<<endl;
}

/*堆操作函数*/
//向下调整堆
void AdjustDown(vector<int> &v,int i,int n){
for(int j=i*2;j<=n;j=j*2){
if(j<n&&v[j]<v[j+1]) ++j;
if(v[i]>v[j]) break;
else{
Swap(v,i,j);
i=j;
}
}
}
//向上调整堆
void AdjustUp(vector<int> &v,int i,int n){
for(int j=i/2;v[i]>v[j];j/=2){
Swap(v,j,i);
i=j;
}
}
//建堆
void BuildMaxHeap(vector<int> &v,int n){
for(int i=n/2;i>0;–i){
AdjustDown(v,i,n);
}
}
void MaxHeapInsert(vector<int> &v,int ins){
v.push_back(ins);
}
//大顶堆排序
void HeapSort(vector<int> &v,int n){
BuildMaxHeap(v,n);
for(int i=n;i>1;–i){
Swap(v,i,1);
AdjustDown(v,1,i-1);
}
}
int main()
{
vector<int> v = {0,53,17,78,9,45,65,87,32,1,43,22,67,83};
HeapSort(v,v.size()-1);
Print(v);
BuildMaxHeap(v,v.size()-1);
MaxHeapInsert(v,44);
HeapSort(v,v.size()-1);
Print(v);
return 0;
}

快速排序之中间基准值的实现[C++实现]

在很多时候写快排选择基准值时都是使用第一个元素作为基准,今天使用了中间元素作为基准值来实现快排。

Tips:比较重要的一点是要更新基准值的位置

—————————————————————

#include <iostream>
#include <vector>
using namespace std;
int Partition(vector<int> &v,int low,int high){

int pivot = low+(high-low)/2;
while(low<high){
while(low<high&&v[high]>v[pivot]) –high;
while(low<high&&v[low]<v[pivot]) ++low;
if(low<high){
//交换元素
v[low]^=v[high];
v[high]^=v[low];
v[low]^=v[high];
//基准追踪
if(low==pivot) pivot = high;
else if(high==pivot) pivot=low;
//循环退出
if(v[low]==v[pivot]&&v[high]==v[pivot]) ++low;
}
}
return pivot;

}
void quickSort(vector<int> &v,int low,int high){
if(low<high){
int pos = Partition(v,low,high);
quickSort(v,low,pos-1);
quickSort(v,pos+1,high);
}
}

int main(){
vector<int> v={1,3,2,4,5,7,2,1};
quickSort(v,0,v.size()-1);
for(auto vi = v.begin();vi!=v.end();++vi) cout<<*vi<<” “;
cout<<endl;
return 0;
}