# 26.Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example, Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()==0)
return 0;
if(nums.size()<2)
return 1;
int i=0,new_len=1;
for(i=1;i<nums.size();i++){
if(nums[i]!=nums[i-1]){
nums[new_len]=nums[i];
new_len++;
}
}
return new_len;
}
};


# 18.4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1,  0, 0, 1],
[-2, -1, 1, 2],
[-2,  0, 0, 2]
]


solution1 用时92ms

• [ TODO To be faster]
/*solution 1*/
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>>res;
int left=0,mid1=0,mid2=0,right=0,tmp_mid2=0,tmp_right=0,tmp_mid1=0,tmp_left=0;
int size=nums.size();
sort(nums.begin(),nums.end());
if(size<4)
return res;
for(left=0;left<size-3;left++){
int tmp_left=target-nums[left];
/*去除left造成的重复*/
if(left > 0 && nums[left] == nums[left-1])
continue;
for(mid1=left+1;mid1<size-2;mid1++){
int tmp=tmp_left-nums[mid1];
mid2=mid1+1;
right=size-1;
/*去除mid1造成的重复*/
if(mid1 > left+1 && nums[mid1] == nums[mid1-1])
continue;
while(mid2<right){
if(nums[mid2]+nums[right]==tmp){
tmp_mid2=nums[mid2];
tmp_right=nums[right];
while(mid2 < right && nums[++mid2] == tmp_mid2);/*去除mid2造成的重复*/
while(mid2 < right && nums[--right] == tmp_right);
}
else if(nums[mid2]+nums[right]<tmp)
mid2++;
else
right--;
}
}
}
return res;
}
};


# 179. Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

1. 如果是两个个位数，则直接比较即可。
2. 如果其中有一个超过10的数字，比如23和9，则在这道题的逻辑中，应该是9>23
3. 如果某个数的前半部分和另一个数完全相同，则看该数剩下的那部分和另一个数的大小关系，如6532和65比较时，65是大于6532的，因为65大于32。
4. …………

bool compTwoString(string& s1,string& s2){
return s1+s2>s2+s1;
}


class Solution {
private:
static bool compTwoString(string& s1,string& s2){
return s1+s2>s2+s1;
}
public:
string largestNumber(vector<int>& nums) {
if(nums.empty())
return {};
vector<string> tmp;
string res;
for(int num:nums)
tmp.push_back(to_string(num));
sort(tmp.begin(),tmp.end(),compTwoString);
for(string s:tmp)
res+=s;
return res[0]=='0'?"0":res;
}
};


# 15.3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: (Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c))The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]


1. 以数组形式返回
2. 返回结果不能重复
3. 返回结果以升序排列

for(left=0;left<size&&nums[left]<=0;left++)


while(mid<right){
if(nums[mid]+nums[right]==tmp){
int tmp_left=nums[left],tmp_right=nums[right],tmp_mid=nums[mid];
vector<int>triplet(3,0);
triplet[0]=nums[left];
triplet[1]=nums[mid];
triplet[2]=nums[right];
res.push_back(triplet);
}
else if(nums[mid]+nums[right]<tmp)
mid++;
else
right--;
}


for(left=0;left<size&&nums[left]<=0;left++){
tmp=0-nums[left];
mid=left+1;
right=size-1;
while(mid<right){
if(nums[mid]+nums[right]==tmp){
int tmp_left=nums[left],tmp_right=nums[right],tmp_mid=nums[mid];
vector<int>triplet(3,0);
triplet[0]=nums[left];
triplet[1]=nums[mid];
triplet[2]=nums[right];
res.push_back(triplet);
while(mid<right&&nums[++mid]==tmp_mid);/*防止mid造成重复*/
while(mid<right&&nums[--right]==tmp_right);/*防止right造成重复*/
}
else if(nums[mid]+nums[right]<tmp)
mid++;
else
right--;
}
while(left+1<size&&nums[left]==nums[left+1])/*防止*/
left++;
}


# 389. Find the Difference

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.


/*solution1,use a vector to compute the frequency,4ms*/
class Solution {
public:
char findTheDifference(string s, string t) {
vector<int> word(26,0);
for(int i=0;i<s.size();i++)
word[s[i]-'a']++;
for(int i=0;i<t.size();i++){
int tmp=word[t[i]-'a']--;
if(tmp==0)
return t[i];
}
return 'a';
}
};



/*solution2,use bit manipulation，4ms*/
class Solution {
public:
char findTheDifference(string s, string t) {
char tmp=0;
for(char a:s)
tmp^=a;
for(char b:t)
tmp^=b;
return tmp;
}
};


Stefan大神提出了一行代码解决问题的方案，运用了accumulate方法，思路上和第二种方法相同,代码如下:

/*solution 3,one-line version of solution2*/
class Solution {
public:
char findTheDifference(string s, string t) {
return accumulate(begin(s), end(s += t), 0, bit_xor<int>());
}
};