很常见算法记录

1. 判断链表中是否有环

这个问题利用快慢双指针比较高效，快指针fast每次走2步，slow每次走1步，慢指针走n步到尾时候快指针走了2n步，而环的大小一定小于等于n所以一定会相遇，如果相遇那么说明有环，如果不相遇fast先为null说明无环。O(1)解决

bool hasCycle(ListNode *head)
{
   ListNode *p1 =head;
   ListNode *p2 =head;
   while(p2 != NULL && p2 ->next !=NULL)
   {
	  p1= p1->next;
	  p2= p2->next->next;
      if(p1 == p2)
      {
      	  return true;
	  }
   }
   return false;
}

2. 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

思路：
1）首先要判断此链表是否有环，会得到首次相遇点
2）当一个节点从head出发，另一个节点从首次相遇点出发，每次均移动1，当再次相遇，每个点所走的距离就是入环点

class Solution {
public:
    ListNode *detectCycle(ListNode *head)
    {
        ListNode *fast = head;
        ListNode *slow = hasCycle(head);
        if(slow==NULL)
        {
        	return 	NULL;
		}
		else
		{
			while(fast!=slow)
        	{
        		slow= slow->next;
        		fast= fast->next;
			}
			return fast;
		}  
    }
    ListNode * hasCycle(ListNode *head)
    {
        ListNode *slow =head;
	    ListNode *fast =head;
        while(fast != NULL && fast ->next !=NULL)
        {
			slow= slow->next;
			fast= fast->next->next;
            if(slow == fast)
        	{
        		return slow;
			}
		}
		return NULL;
    }
}

3. 最小栈的实现

class MinStack {
public:
    MinStack() {

    }
    
    void push(int val)
    {
        minSt.push(val);
        if(s.empty() || val <= s.top())
        {
            s.push(val);
        }
    }
    
    void pop()
    {	
        if(minSt.top()==s.top())
        {
            s.pop();
        }
        minSt.pop();
    }
    
    int top() {
        return minSt.top();
    }
    
    int getMin() {
       return s.top(); 
    }
private:
    stack<int> minSt;
    stack<int> s;
};

4. 求最大公约数

#include<iostream>
using namespace std;

//辗转相除法: 当两个数都比较大时性能会比较差 
int getGreatestCommonDivisorV1(int a,int b)
{
	int big = a > b ? a : b;
	int small = a < b ? a : b;
	if(big % small == 0)
	{
		return small;
	}
	getGreatestCommonDivisorV1(big%small,small);
}

//更相减损术: 当两个数差别比较大时性能比较差 
int getGreatestCommonDivisorV2(int a,int b)
{
	int big = a > b ? a : b;
	int small = a < b ? a : b;
	if(big == small)
	{
		return small;
	}
	getGreatestCommonDivisorV2(big-small,small);
}

//最优: 会把两个数变成差距不大切数值不大的两个数 
int getGreatestCommonDivisorV3(int a,int b)
{
	if(a==b)
	{
		return a;
	}
	
	if(a&1==0 && b&1==0)
	{
		return getGreatestCommonDivisorV3(a>>1,b>>1)<<1;
	}
	else if(a&1!=0 && b&1==0)
	{
		return getGreatestCommonDivisorV3(a,b>>1);	
	}
	else if(a&1==0 && b&1!=0)
	{
		return getGreatestCommonDivisorV3(a>>1,b);
	}
	else
	{
		int big = a > b ? a : b;
		int small = a < b ? a : b;	
		getGreatestCommonDivisorV3(big-small,small);
	}
}

int main()
{
	cout<<getGreatestCommonDivisorV1(50, 10)<<endl;
	cout<<getGreatestCommonDivisorV2(50, 10)<<endl;
	cout<<getGreatestCommonDivisorV3(50, 10)<<endl;
	return 0;
 } 

5.判断是否为2的幂

class Solution {
public:
    bool isPowerOfTwo(int n)
    {
        if(n>0)
        {
            return (n&n-1)==0;	
        }
        else
            return false; 
    }
};

6. 无序数组排序后最大相邻差（不能直接排序）

• 计数排序适用于数组元素值相差不大
• 桶排序数组元素值相差很大也可以用

#include <iostream>
using namespace std;

void printArray(int* arr, int len)
{
	for(int i = 0; i < len; i++)
	{
		cout<<arr[i]<<" ";
	}
	cout<<endl;
}

int* createNewArr(int* arr, int k, int len, int minEle)
{
	
	//cout<<"newArr的长度："<< k <<endl; 
	int* newArr = new int[k]();
	for(int j = 0; j< len; j++)
	{
		newArr[arr[j] - minEle]++;
	}
	return newArr;
}

int getCountofContinueZeros(int* newArr, int k)
{
	int count = 0;
	int maxCount = 0; 
	for(int i = 0; i < k; i++)
	{
		if(newArr[i]==0)
		{
			count++;
		}
		else
		{
			if(count > maxCount)
			{
				maxCount = count;
			}
			count = 0;
		}
	} 
	return maxCount+1;
} 

//利用计数排序的思想 
int largestAdjacentDifferenceV1(int* arr, int len)
{
	//1.找到数组的最大值及最小值
	int minEle = arr[0];
	int maxEle = arr[0];
	for(int i=0; i<len; i++)
	{
		if(arr[i] > maxEle)
		{
			maxEle = arr[i];	
		}
		if(arr[i] < minEle)
		{
			minEle = arr[i];	
		}	
	}
	/* 
	cout<<"maxEle:"<<maxEle<<endl;
	cout<<"minEle:"<<minEle<<endl;
	*/ 
	
	//2.创建一个长度为k的新数组newArr
	int k = maxEle - minEle + 1;
	int* newArr = createNewArr(arr, k, len, minEle);
	/*	
	cout<<"打印newArr:"<<endl;
	printArray(newArr, k);
	*/ 
	
	//3. 找最大连续0出现的次数maxCount
	int maxCount = getCountofContinueZeros(newArr, k);
	return maxCount;
}

struct Bucket{
	int max;
	int min;
	bool initMinStatus;
	bool initMaxStatus;
};

Bucket* createBuckets(int len)
{
	Bucket* bucket = new Bucket[len]();
	return bucket;	
} 

void getBoundaryEle(Bucket* bucket, int* arr, int len, int maxEle, int minEle)
{
	for(int i = 0;i < len; i++)
	{
		int index = (arr[i] - minEle) * (len - 1) / (maxEle - minEle); //第i个元素在第index桶的位置 
		if(arr[i] < bucket[index].min || !bucket[index].initMinStatus)
		{
			bucket[index].min = arr[i];
			bucket[index].initMinStatus = true;
		} 
		if(arr[i] > bucket[index].max || !bucket[index].initMaxStatus)
		{
			bucket[index].max = arr[i];
			bucket[index].initMaxStatus = true;
		}
		
		#if 0
		cout<<"current bucket["<<index<<"]:"<<endl;
		cout<<"max:"<<bucket[index].max<<" min:"<<bucket[index].min<<endl;
		cout<<"-------------------------"<<endl;
		#endif
	} 
} 

int getMaxDistance(Bucket* bucket, int len)
{
	int leftMax = bucket[0].max;
	int maxDistance = 0;
	for(int i = 1; i < len; i++)
	{
		if(!bucket[i].initMinStatus && !bucket[i].initMaxStatus)
		{
			continue;	
		}
		if(bucket[i].min - leftMax > maxDistance)
		{
			maxDistance = bucket[i].min - leftMax;	
		}
		leftMax = bucket[i].max;	
	} 
	return maxDistance;
}

//利用桶排序的思想 
int largestAdjacentDifferenceV2(int* arr, int len)
{
	//1.找到数组的最大值及最小值
	int minEle = arr[0];
	int maxEle = arr[0];
	for(int i=0; i<len; i++)
	{
		if(arr[i] > maxEle)
		{
			maxEle = arr[i];	
		}
		if(arr[i] < minEle)
		{
			minEle = arr[i];	
		}	
	}
	/*
	cout<<"maxEle:"<<maxEle<<endl;
	cout<<"minEle:"<<minEle<<endl;
	*/
	
	//2.创建长度为len的桶，因为有len-1个区间，所以每个桶的区间长度为(maxEle-minEle)/(len-1) ,
	Bucket* bucket = createBuckets(len);
	
	//3. 找到arr中每个元素在bucket中的index,并同时记录每个bucket的max和min
	getBoundaryEle(bucket, arr, len, maxEle, minEle);
	
    // 4.遍历所有bucket, 找到最大差值maxDistance
    int maxDistance = getMaxDistance(bucket, len);
    
    return maxDistance;	
}


int main()
{
  
  int arr[] = {2, 6, 3, 4, 5, 10, 9};
  int len = sizeof(arr)/sizeof(int);
  printArray(arr, len);
  
  cout<<"求无序数组排序后的最大相邻差：" <<endl;  //不能采用排序 
  
  int maxCount1 = largestAdjacentDifferenceV1(arr, len);
  cout<<"利用计算排序的思想:"<<maxCount1<<endl; 
  
  int maxCount2 = largestAdjacentDifferenceV2(arr, len);
  cout<<"利用桶排序的思想 :"<<maxCount2<<endl; 
  
  
  return 0;	
} 

7. 用栈实现队列

class MyQueue {
public:
    MyQueue() {

    }
    
    void push(int x) {
        while(!s2.empty())
        {
            s1.push(s2.top());
            s2.pop();	
        }
        s1.push(x);
        while(!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();	
        }	
    }
    
    int pop() {
        int ret = s2.top();
        s2.pop();
        return ret;
    }
    
    int peek() {
        return s2.top();
    }
    
    bool empty() {
        return s2.empty();
    }
private:
    stack<int>s1;  // in
	stack<int>s2;  // out

};

8. 全排列的下一个数

#include<iostream>
#include<vector> 
#include<algorithm>
using namespace std;
 
void printVector(vector<int>& nums)
{
	vector<int>::iterator it;
	for(it = nums.begin(); it != nums.end(); it++)
	{
		cout<<*it<<" ";
	}
	cout<<endl;
} 
  
void exch(vector<int>& nums, int i, int j)
{
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
}

int findTransferPoint(vector<int>& nums)
{
	for(int i = nums.size() - 1; i >= 1; i--)
	{
		if(nums[i] > nums[i - 1])	 
		{
			return i;
		}
	} 	
} 
void nextPermutation(vector<int>& nums)
{
   
    int size = nums.size();
    
    //如果只有一个元素就是本身 
    if(size == 1)
        return;
      
    //1.从数组的最后往前找到第一个逆序的地方
	int index = findTransferPoint(nums);
	cout<<"index:"<<index<<endl;
	
	/*
     case 1
     [5,4,3,2,1]
                -> reverse the arary 1, 2, 3, ,4 ,5
	*/         
    if(index == 0)
	{
        sort(nums.begin(), nums.end());
        return;
    }
    /*
    case 2 
    1 2 3 4 5
	1 2 3 5 4 
	*/ 
    else if(index == size - 1)
	{
        exch(nums, index, index - 1);
        return;
    }
    else
    {
    	//case 3
	    /*              index 
	    	1   2   3   5      4 
			                   exchangeIndex
	    	1   2   4   5      3
			1   2   4   3      5 
	    */ 
    	for(int exchangeIndex = size - 1; exchangeIndex > index - 1; exchangeIndex--)
	    {
	    	if(nums[exchangeIndex] > nums[index - 1])
	    	{
	    		cout<<"exchangeIndex:"<<exchangeIndex<<endl; 
	    		exch(nums, index - 1, exchangeIndex);
	    		break;
			}
		}
      
    	sort(nums.begin() + index, nums.end());
    
    	return;
	}   
}
   
int main()
{
	vector<int>nums;

	nums.push_back(2);
	nums.push_back(3);
	nums.push_back(1);	
	printVector(nums);
	
	nextPermutation(nums);
	printVector(nums);
	
	return 0;	
	
} 

9. 删除k个数字之后的最小值

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

string removeKDigits(string s, int k)
{
	bool hasCut = false;
	do
	{
		for(int i=0; i < s.length(); i++)
		{
			if(s[i] > s[i+1])
			{
				k--;
				s.erase(i, 1);
				hasCut = true;
				break;
				//cout<<"k "<<k<<endl;
			}
		}	
	}while(k);
	
	if(!hasCut)
	{
		s.erase(s.length() - 1, 1);
	}
		
	return s;
}

int main()
{
	
	string s = "1593212";
	cout<<removeKDigits(s, 1)<<endl;  //153212
	cout<<removeKDigits(s, 2)<<endl;  //13212
	cout<<removeKDigits(s, 3)<<endl;  //1212
	
	string s1 = "123456";
	cout<<removeKDigits(s1, 1)<<endl;  //12345
	
	return 0;
} 

10. 实现大数算法

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

void printfArr(int *arr, int len)
{
	for(int i = 0; i < len; i++)
	{
		cout<<arr[i]<<" ";
	}
	cout<<endl;
}

string bigNbrSum(string &a, string &b)
{
	//1.把两个大数用数组逆序存储
	int maxLength = a.length() > b.length() ? a.length() + 1 : b.length() + 1;
	
	// for string a
	int *arr1 = new int[maxLength]();
	for(int i = 0; i< a.length(); i++)
	{
		arr1[i] = a[a.length() - i - 1] - '0';	
	} 
	printfArr(arr1, maxLength);
	
	//for string b
	int *arr2 = new int[maxLength]();
	for(int i = 0; i< b.length(); i++)
	{
		arr2[i] = b[b.length() - i - 1] - '0';	
	}
	printfArr(arr2, maxLength);
	
	//2.从左到右依次相加
	string res = "";
	int inc = 0; // 进位 
	for(int i = 0; i < maxLength; i++)
	{
		
		int temp = arr1[i] + arr2[i] + inc;
		inc = 0;
		if(temp >= 10)
		{
			temp -= 10;
			inc = 1; 
		}
		if(i == maxLength - 1 && inc == 0)
		{
			
		}
		else
		{
			res.append(1,temp + '0');	
		}
	} 
	
	//3.反转res
	reverse(res.begin(), res.end());
	return res;
} 

int main()
{
	string a = "18345";
	string b = "93458";
	cout<<bigNbrSum(a, b)<<endl;	
	
	return 0;	
} 

11. 求解金矿问题

递归实现：

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

/*
	w: 工人数量
	n: 金矿的数量
	p: 每个金矿对应的工人数量
	g: 每个金矿的储量 
*/
int getBestGoldMining(int w, int n, int *p, int *g)
{
	if(w == 0 || n == 0)
	{
		return 0; 
	} 
	if(w < p[n-1])
	{
		return  getBestGoldMining(w, n-1, p, g);
	}
	return max(getBestGoldMining(w, n-1, p, g), getBestGoldMining(w - p[n-1], n-1, p, g) + g[n-1]);
} 

int main()
{
	int w = 10;
	int n = 5;
	int p[] = {5, 5, 3, 4, 3};
	int g[] = {400, 500, 200, 300, 350};
	cout<<getBestGoldMining(w, n, p, g)<<endl;		
	return 0;
}

此方法时间复杂度为2^n, 也可采用自底向上的动态规划办法进行优化

12. 寻找缺失的数

1）在一个无序数组中有99个不重复的正整数，范围是1~100， 唯独缺少一个整数，如何找出这个整数：
直接算出1+2+3+…+99+100的和，然后依次减掉数组中的元素，最后得到的差值就是这个缺失的整数

2）一个无序数组里有若干个正整数，范围1~100，其中99个出现了偶数次，只有一个出现了奇数次，找到这个出现奇数次的数
用异或

3）一个无序数组里有若干个正整数，范围1~100，其中98个出现了偶数次，有两个出现了奇数次，找到这两个数:

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

vector<int>findLostNum(int arr[], int len)
{
	vector<int>res;
	
	//1.整体进行异或
	int xorResult = 0;
	for(int i = 0; i < len; i++)
	{
		xorResult ^= arr[i];	
	} 
	//cout<<"xorResult: "<<xorResult<<endl;
	
	//如果xorResut == 0, 则说明输入的数组不符合题目要求
	if(xorResult == 0)
	{
		return res;	
	}
	
	//2.确定2个整数的不同位, 依次来分组
	int separator = 1;
	while((xorResult & separator) == 0)
	{
		separator <<= 1;
		//cout<<"separator: "<<separator<<endl;	
	} 
	
	//3.分组，分别进行异或运算
	int a, b = 0;
	for(int i = 0; i < len; i++)
	{
		if((arr[i] & separator) == 0)
		{
			a ^= arr[i];
		}
		else
		{
			b ^= arr[i];
		}
	}
	res.push_back(a);
	res.push_back(b);
	return res;
}


int main()
{
	int arr[] = {4, 1, 2, 2, 5, 1, 4, 3};
	int len = 8;
	vector<int>res = findLostNum(arr, len);
	vector<int>::iterator it;
	for(it = res.begin(); it != res.end(); it++)	
	{
		cout<<*it<<" "; 
	}
	cout<<endl;
		
	return 0;	
}