1.Two Sum
naive
4.Median of Two Sorted Arrays
找两个已排序数组的中位数
直接数可以过，但很蠢，O(m+n)时间
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int p1=-,p2=-;
double rst = ;
int len1 = nums1.size(),len2 = nums2.size();
if (len1==&&len2==) return 0.0;
if ((len1+len2)%==)
{
int count=(len1+len2+)/;
if (len1==) return 1.0*nums2[len2/];
if (len2==) return 1.0*nums1[len1/];
while (count)
{
if (p1==len1-) {rst=nums2[p2+];p2++;}
else if (p2==len2-) {rst=nums1[p1+];p1++;}
else if (nums1[p1+]>nums2[p2+]) {rst=nums2[p2+];p2++;}
else {rst=nums1[p1+];p1++;}
count--;
}
return rst;
}
else {
int count=(len1+len2)/;
if (len1==) return 0.5*nums2[len2/]+0.5*nums2[len2/-];
if (len2==) return 0.5*nums1[len1/]+0.5*nums1[len1/-];
int t1=,t2=;
while (count+)
{
t1=t2;
if (p1==len1-) {p2++;t2=nums2[p2];}
else if (p2==len2-) {p1++;t2=nums1[p1];}
else if (nums1[p1+]>nums2[p2+]) {p2++;t2=nums2[p2];}
else {p1++;t2=nums1[p1];}
count--;
}
return 0.5*t1+0.5*t2;
}
}
};
Stupid
直接思路是二分，O(log (m+n))
class Solution {
public:
double findMedianSortedArrays(vector<int>& num1, vector<int>& num2) {
int size = num1.size() + num2.size();
if (size % == ) return 1.0*search(num1, num2, , , size / + );
else return 0.5*search(num1, num2, , , size / ) + 0.5*search(num1, num2, , , size / + );
}
private:
int _min(int a, int b)
{
return a>b ? b : a;
}
int search(vector<int>& nums1, vector<int>& nums2, int s1, int s2, int pos)
{
//TODO:nums1[s1,s1+1,...,m],nums2[s2,s2+1,...,n],find the "pos"th smallest number
if ((nums1.size() - s1)>(nums2.size() - s2))
return search(nums2, nums1, s2, s1, pos); //use 1 extra call to ensure that nums1 is shorter
if (s1 == nums1.size())
return nums2[s2 + pos-];
if (pos == ) return _min(nums1[s1], nums2[s2]); //Point 1：边界特殊处理，否则RE
int k1 = _min(nums1.size() - s1, pos / );
int k2 = pos - k1;
if (nums1[s1 + k1 - ] == nums2[s2 + k2 - ]) //Point 2：等于的情况就不应该步进了
return nums1[s1 + k1 - ];
else if (nums1[s1 + k1 - ] > nums2[s2 + k2 - ])
return search(nums1, nums2, s1, s2 + k2, pos - k2);
else
return search(nums1, nums2, s1 + k1, s2, pos - k1);
}
};
Binary Search
11.Container With Most Water
找h[i],h[j]，使得min(h[i],h[j])*(j-i)最大
典型的双指针问题，从两端向中间逼近，注意移动条件
class Solution {
public:
int maxArea(vector<int>& height) {
int left = ,right = height.size()-;
int rst = ;
while (left<right)
{
rst = _max(rst,(right-left)*_min(height[left],height[right]));
if (height[left]>height[right]) right--; //当h[l]>h[r]时,显然挪动左侧获得的结果不可能比此刻更好，因而挪右侧
else left++; //同理
}
return rst;
}
private:
int _min(int a,int b)
{
return a>b?b:a;
}
int _max(int a,int b)
{
return a>b?a:b;
}
};
15.3Sum
思路：先排序，之后对每一个小于0的数进行查询：
设num[i]<0，则b=i+1,c=num.size()-1,根据和的正/负/0向中间逼近
注意：1.去重 2.数组越界 3.终止条件（当num[i]>0时，由于已排序，后面不必再扫）
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> rst;
if (nums.size()<) return rst;
sort(nums.begin(), nums.end());
int i = , a = nums[i];
while (i<=nums.size()-)
{
int b = i + , c = nums.size() - ;
while (b<c) {
int l = nums[b], r = nums[c];
if (nums[i] + nums[b] + nums[c] == )
{
vector<int> t({ nums[i],nums[b],nums[c] });
rst.push_back(t);
while ((b<nums.size())&&(nums[b] == l)) b++;
while ((c>=)&&(nums[c] == r)) c--;
}
else if (nums[i] + nums[b] + nums[c]<) { while ((b<nums.size()) && (nums[b] == l)) b++; }
else { while ((c>=) && (nums[c] == r)) c--; }
}
while ((i<=nums.size()-)&&(nums[i] == a)) i++;
a = nums[i];
}
return rst;
}
};
16.3Sum Closest
思路：不需要去重，直接双指针找即可，比15简单
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
if (nums.size()<) return -; //undefined
sort(nums.begin(), nums.end());
int rst = 0x3f3f3f3f;
int a = , b, c;
while (a <= nums.size() - ) {
b = a + , c = nums.size() - ;
int l = nums[b], r = nums[c], t = nums[a];
while (b<c)
{
int temp = nums[a] + l + r;
if (abs(temp - target)<abs(rst - target))
rst = temp;
if (temp>target) { c--; }
else { b++; }
l = nums[b];
r = nums[c];
}
if (rst == target) break;
a++;
}
return rst;
}
};
18.4Sum
思路：naive：对每个元素搞一次3Sum
优化思路：剪枝：当有两个点已确定时，在循环开始之前先判断最小的两个数加起来是否已经超过要求；最大的两个数加起来是否仍不足
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> rst;
if (nums.size()<) return rst;
sort(nums.begin(), nums.end());
int s = , start = nums[s];
while (s <= nums.size() - )
{
int tar = target - start;
int i = s + , a = nums[i];
while (i <= nums.size() - )
{
int b = i + , c = nums.size() - ;
while (b<c) {
int l = nums[b], r = nums[c];
if (nums[i] + nums[b] + nums[c] == tar)
{
vector<int> t({ nums[s],nums[i],nums[b],nums[c] });
rst.push_back(t);
while ((b<nums.size()) && (nums[b] == l)) b++;
while ((c >= ) && (nums[c] == r)) c--;
}
else if (nums[i] + nums[b] + nums[c]<tar) {
while ((b<nums.size()) && (nums[b] == l)) b++;
}
else { while ((c >= ) && (nums[c] == r)) c--; }
}
while ((i <= nums.size() - ) && (nums[i] == a)) i++;
a = nums[i];
}
while ((s <= nums.size() - ) && (nums[s] == start)) s++;
start = nums[s];
}
return rst;
}
};
Naive
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> rst;
if (nums.size()<) return rst;
sort(nums.begin(), nums.end());
for (int i = ; i < nums.size() - ; i++)
{
if ((i > ) && (nums[i] == nums[i - ])) continue;
int t1 = target - nums[i];
for (int j = i + ; j < nums.size() - ; j++)
{
if ((j > i + ) && (nums[j] == nums[j - ])) continue;
int t2 = t1 - nums[j];
int k = j + , r = nums.size() - ;
if (nums[k] + nums[k + ]>t2) break;
if (nums[r - ] + nums[r] < t2) continue;
while (k < r)
{
if (nums[k] + nums[r] == t2)
{
rst.push_back({ nums[i],nums[j],nums[k],nums[r] });
k++; r--;
while ((k<r) && (nums[k] == nums[k - ]))k++;
while ((k<r) && (nums[r] == nums[r + ]))r--;
}
else if (nums[k] + nums[r] < t2)
{
k++;
}
else
r--;
}
}
}
return rst;
}
};
加优化
26.Remove Duplicates from Sorted Array
去重，简单题，注意返回值是数组长度
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size()==) return ;
int p=;
for (int i=;i<nums.size();i++)
{
if (nums[i]!=nums[i-]) nums[++p]=nums[i];
}
return p+;
}
};
31.Next Permutation
基础题
算法：初始化：i=0,ii=0,j=0
1.从后向前扫，找到第一对相邻的nums[i]<nums[ii]，ii=i+1;
2.从后向前扫，找到第一个大于nums[i]的nums[j]
3.交换nums[i],num[j]，并将ii及之后的数组反转
从后向前扫，显然递减序列是最“大”的排列，因此找到非递减序列的开始
第一步后：nums[ii-end]为递减序列，此时将i与nums[ii-end]中的任意一个数交换，都可以保证其为此序列之后的序列（但不一定就是下一个）
为了保证是下一个，找到最小的大于i的数，交换
注意到交换后ii后面仍为有序序列，为了使得交换后该子序列最“小”，反转该序列即可
证明
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int i=,ii=,j=;
for (int k=nums.size()-;k>;k--)
{
if (nums[k-]<nums[k]) {
i=k-;ii=k;break;
}
}
for (int k=nums.size()-;k>;k--)
{
if (nums[k]>nums[i]) {j=k;break;}
}
swap(nums,i,j);
reverse(nums,ii,nums.size()-);
}
private:
void swap(vector<int>& nums,int a,int b)
{
int t=nums[a];
nums[a]=nums[b];
nums[b]=t;
}
void reverse(vector<int>& nums,int start,int end)
{
int p=start,q=end;
while (p<q)
{
swap(nums,p,q);
p++;q--;
}
}
};
扩展：
1.已知有序数组{a_1,a_2,...,a_n}，求第k个排列
第一位后面有(n-1)!种排列，因而第一位的数字应为a[k/(n-1)!]，剩余k%(n-1)!种情况
依次确认之后每一位的排列即可
举例说明：如7个数的集合为{1, 2, 3, 4, 5, 6, 7}，要求出第n=1654个排列。
(1654 / 6!)取整得2，确定第1位为3，剩下的6个数{1, 2, 4, 5, 6, 7}，求第1654 % 6!=214个序列；
(214 / 5!)取整得1，确定第2位为2，剩下5个数{1, 4, 5, 6, 7}，求第214 % 5!=94个序列；
(94 / 4!)取整得3，确定第3位为6，剩下4个数{1, 4, 5, 7}，求第94 % 4!=22个序列；
(22 / 3!)取整得3，确定第4位为7，剩下3个数{1, 4, 5}，求第22 % 3!=4个序列；
(4 / 2!)得2，确定第5为5，剩下2个数{1, 4}；由于4 % 2!=0，故第6位和第7位为增序<1 4>；
因此所有排列为：3267514。
(60.Permutation Sequence
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> vec;
for (int i=;i<n;i++)
vec.push_back(i);
string str;
int rank = k-;
for (int i=;i<n;i++)
{
int cas = fact(n-i-);
int temp = rank/cas;
rank = rank%cas;
str+=(''+vec[temp]);
vec.erase(vec.begin()+temp);
}
return str;
}
private:
int fact(int n)
{
int rst=;
while (n>) {rst*=n;n--;}
return rst;
}
};
注意：数组从0开始还是从1开始）
2.已知一个排列{a_1,a_2,...,a_n}，求这是第几个排列
反过来求即可：
第一位序数为k_1，则排列至少为第(k_1-1)*(n-1)!个
依此类推即可
例如3267514：
后6位的全排列为6!，3为{1, 2, 3 ,4 , 5, 6, 7}中第2个元素（从0开始计数），故2*720=1440；
后5位的全排列为5!，2为{1, 2, 4, 5, 6, 7}中第1个元素，故1*5!=120；
后4位的全排列为4!，6为{1, 4, 5, 6, 7}中第3个元素，故3*4!=72；
后3位的全排列为3!，7为{1, 4, 5, 7}中第3个元素，故3*3!=18；
后2位的全排列为2!，5为{1, 4, 5}中第2个元素，故2*2!=4；
最后2位为增序，因此计数0，求和得：1440+120+72+18+4=1654
参考：http://www.cnblogs.com/devymex/archive/2010/08/17/1801122.html
(46. Permutations
输出给定无重复数组的全排列
不要脸的做法：next_permutation，效率高于一般的递归，但仍较低（理论上(n*n!)）
一般的做法：递归：理论上为O(n!)，实际上优化的好坏与结果关系很大)
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> rst;
if (nums.size() == ) return rst;
allPermute(nums, , nums.size() - , rst);
return rst;
}
private:
vector<vector<int>> allPermute(vector<int>& nums, int k, int len, vector<vector<int>> &rst)
{
if (k == len) {
vector<int> vec;
for (int i = ; i < nums.size(); i++)
vec.push_back(nums[i]);
rst.push_back(vec);
}
else {
for (int i = k; i <= len; i++)
{
int temp = nums[k];
nums[k] = nums[i];
nums[i] = temp;
allPermute(nums, k + , len, rst);
int temp1 = nums[k];
nums[k] = nums[i];
nums[i] = temp1;
}
}
return rst;
}
};
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> rst;
allPermute(nums, , rst);
return rst;
}
private:
void allPermute(vector<int>& nums, int start, vector<vector<int>>& rst)
{
if (start >= nums.size()-) rst.push_back(nums);
else {
for (int i = start; i <= nums.size() - ; i++)
{
swap(nums[i], nums[start]);
allPermute(nums, start + , rst);
swap(nums[i], nums[start]);
}
}
}
};
72.27%
33. Search in Rotated Sorted Array
思路：首先找到转折点，之后在两边分别二分搜索，总的复杂度仍为O(logn)
class Solution {
public:
int search(vector<int>& nums, int target) {
int pivot = searchPivot(nums,,nums.size()-);
int rst = Search(nums,target,,pivot);
if (rst == -) rst = Search(nums,target,pivot+,nums.size()-);
return rst;
}
private:
int searchPivot(vector<int>& nums,int start,int end)
{
int p = start+(end-start)/;
if (p==start) return p;
if (nums[p]>nums[start]) return searchPivot(nums,p,end);
else return searchPivot(nums,start,p);
}
int Search(vector<int>& nums,int target,int start,int end)
{
if (target>nums[end]||target<nums[start]||start>end) return -;
else {
int pivot = start+(end-start)/;
if (nums[pivot]==target) return pivot;
else if (nums[pivot]>target) return Search(nums,target,start,pivot-);
else if (nums[pivot]<target) return Search(nums,target,pivot+,end);
}
}
};
34. Search for a Range
简单题，二分找到点后扩一下即可
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int i = Search(nums,target,,nums.size()-);
vector<int> rst;
if (i==-)
{
rst.push_back(-);
rst.push_back(-);
}
else {
int s=i,e=i;
while (s> && nums[s-]==nums[s]) s--;
while (e<nums.size()- && nums[e+]==nums[s]) e++;
rst.push_back(s);
rst.push_back(e);
}
return rst;
}
private:
int Search(vector<int>& nums,int target,int start,int end)
{
if (start>end) return -;
else {
int pivot = start+(end-start)/;
if (nums[pivot]==target) return pivot;
else if (nums[pivot]>target) return Search(nums,target,start,pivot-);
else if (nums[pivot]<target) return Search(nums,target,pivot+,end);
}
}
};
35. Search Insert Position
简单题，此处在找不到该值时，返回start而非-1即可，之后对start进行处理，找到需要的位置
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int rst = Search(nums,target,,nums.size()-);
if (nums[rst]>target)
{
while (rst> && nums[rst-]>target) rst--;
}
else if (nums[rst]<target)
{
while (rst<nums.size()- && nums[rst+]<target) rst++;
}
return rst;
}
private:
int Search(vector<int>& nums,int target,int start,int end)
{
if (start>end) return start;
else {
int pivot = start+(end-start)/;
if (nums[pivot]==target) return pivot;
else if (nums[pivot]>target) return Search(nums,target,start,pivot-);
else if (nums[pivot]<target) return Search(nums,target,pivot+,end);
}
}
};
39. Combination Sum
简单回溯题，注意去重时的操作
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> rst;
vector<int> cas;
Find(cas, candidates, target, rst);
return rst;
}
private:
void Find(vector<int>& sol, vector<int>& candidates, int target, vector<vector<int>>& rst)
{
if (target == ) { rst.push_back(sol); return; }
for (int i = ; i < candidates.size(); i++)
{
if (sol.size()> && (sol.back()) > candidates[i]) continue; //此处要谨慎，不能和下面的if合并，否则遇到一个不符合条件的就直接break
if (target >= candidates[i])
{
sol.push_back(candidates[i]);
Find(sol, candidates, target - candidates[i], rst);
sol.pop_back();
}
else break;
}
return;
}
};
40. Combination Sum II
在39的基础上，给定的数字有重复，但每个数字只能用一次
思路：在39的基础上加一个数组记录某个特定数字最多可用几次，额外开销为O(n)
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> rst;
if (candidates.size()==) return rst;
sort(candidates.begin(), candidates.end());
vector<int> flag,candi;
candi.push_back(candidates[]);
flag.push_back();
int p = ;
for (int i=;i<candidates.size();i++)
{
if (candidates[i-]<candidates[i]) //注意去重条件
{
candi.push_back(candidates[i]);
flag.push_back();
p++;
}
else {
flag[p]++;
}
}
vector<int> cas;
Find(cas, candi, target, rst,flag);
return rst;
}
private:
void Find(vector<int>& sol, vector<int>& candidates, int target, vector<vector<int>>& rst,vector<int>& flag)
{
if (target == ) { rst.push_back(sol); return; }
for (int i = ; i < candidates.size(); i++)
{
if (!flag[i]) continue;
if ((sol.size()>) && (sol.back() > candidates[i])) continue; //此处要谨慎，不能和下面的if合并，否则遇到一个不符合条件的就直接break
if (target >= candidates[i])
{
flag[i]--;
sol.push_back(candidates[i]);
Find(sol, candidates, target - candidates[i], rst,flag);
sol.pop_back();
flag[i]++;
}
else break;
}
return;
}
};
41. First Missing Positive
给定一个无序数组，找出第一个不存在的正数（[1,2,0]->3;[3,4,-1,1]->2）
思路1：利用数组本身大小这一信息，显然长为n的数组，结果不可能大于n+1
将每个大小为i（0<i<n）的数放在nums[i-1]处，之后再扫一遍找第一个不在应该在位置的数即可
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int i, n = nums.size();
for(i=; i<n; i++)
{
while(nums[i]>= && nums[i]<=n && nums[i]!=nums[nums[i]-]) //while loop,important
swap(nums[i], nums[nums[i]-]);
}
int j=;
for(j=; j<=n; j++)
if(nums[j-]!=j)
break;
return j;
}
};