2.两个数字相加
题目：两个非空的链表，每个节点存着非负数字，数字排序是逆序，不会把0放在最前面。
image.png
想法1：
遍历链表，节点存着10的余数，进位是10的商。
代码1：
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int g = 0;
int s = 0;
int temp = l1->val+l2->val;
g = temp%10;
s = temp/10;
ListNode* head = new ListNode(g);
ListNode* p = head;
l1=l1->next;
l2=l2->next;
while(l1!=NULL&&l2!=NULL){
temp = l1->val+l2->val+s;
g = temp%10;
ListNode* r = new ListNode(g);
p->next = r;
p=p->next;
s = temp/10;
l1=l1->next;
l2=l2->next;
}
while(l1!=NULL){
temp = l1->val+s;
g = temp%10;
ListNode* r = new ListNode(g);
p->next = r;
p=p->next;
s = temp/10;
l1=l1->next;
}
while(l2!=NULL){
temp = l2->val+s;
g = temp%10;
ListNode* r = new ListNode(g);
p->next = r;
p=p->next;
s = temp/10;
l2=l2->next;
}
if(s!=0){
ListNode* r = new ListNode(s);
p->next = r;
p=p->next;
}
return head;
}
结果1：
参考答案更简洁，把我下面的情况结合在了第一个while里面：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
3.最长不重复子串
题目：找出最长不含有重复字符的子串长度。
image.png
想法1：
双重循环，暴力解决，使用set辅助碰到了重复没。
代码1：
int lengthOfLongestSubstring(string s) {
int m = 0;
if(s.size()<=1) return s.size();
for(int i = 0;i<s.size();i++){
set<char> t;
for(int j = i;j<s.size();j++){
if(!t.insert(s[j]).second) {
m = max(m,j-i);
t.clear();
break;
}else{
m = max(m,j-i+1);
}
}
}
return m;
}
结果1：
image.png
解法效率太差了。
想法2：
使用int[]保存每个字符的最近的位置，下标使用每个字符的ASCII。
256 位大小的整型数组，这样做的原因是 ASCII 表一共能表示 256 个字符，所以可以记录所有字符
int lengthOfLongestSubstring(string s) {
int m = 0;
int left=0;
int f[256]={0};
for(int i = 0;i<s.size();i++){
left = max(left, f[s[i]]);
m = max(m, i - left + 1);
f[s[i]]= i + 1;
}
return m;
}
image.png
使用set：
如果遇到重复的，则一直set删除和left一直移动到最新重复值的位置。
int lengthOfLongestSubstring(string s) {
int res = 0, left = 0, right = 0;
set<char> t;
while (right < s.length()) {
if (t.insert(s[right]).second) {
right++;
int le = t.size();
res = max(res, le);
} else {
t.erase(s[left]);
left++;
}
}
return res;
}
子串问题是不是都可以用滑动窗口？？？
对很多给定一个字符串，然后要求找到一个满足一定条件的子串的问题，一种比较通用的做法是借助一个MAP，或者是等价的int[128]数组，以及两个指针。由于可以将两个指针看作一个窗口，这种问题也可以叫做滑动窗口问题。
4.两个排好序的数组的中位数
题目：
时间复杂度应该在O(log (m+n))。
image.png
想法1：
使用上次数据流中大小根堆的算法。重新遍历连个数组，构建大小根堆。
代码1：
priority_queue<int, vector<int>, less<int> > a; //max
priority_queue<int, vector<int>, greater<int> > c; //min
int cou = 0;
void Insert(int num)
{
int temp;
if(cou%2==0){ //偶数
a.push(num);
temp = a.top();
c.push(temp);
a.pop();
}else{
c.push(num);
temp = c.top();
a.push(temp);
c.pop();
}
cou++;
}
double GetMedian()
{
int temp1;
int temp2;
if(cou%2==0){ //偶数
temp1 = a.top();
temp2 = c.top();
return (temp1+temp2)*1.0/2;
}else{
return c.top();
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int i = 0;
int j = 0;
while(i<nums1.size()||j<nums2.size()){
if(i<nums1.size()) Insert(nums1[i++]);
if(j<nums2.size()) Insert(nums2[j++]);
}
return GetMedian();
}
结果1：
image.png
想法2：
log级别的时间复杂度我们自然想到二分法，每次取中间值，自然得出的是log2(n)级别的。
不会。。。。。
5.Longest Palindromic Substring
题目：给定一个字符串s，找出s中最长的回文子串。可以假设s的最大长度为1000。
想法1：暴力解决，左右两个指针遍历
代码1：
bool todo(string s,int f ,int e ){
for(int i = f,j=e;i<=j;i++,j--){
if(s[i]!=s[j]) return false;
}
return true;
}
string longestPalindrome(string s) {
int m = 0;
int mi = 0;
if(s.size()==0) return "";
for(int i = 0;i<s.size();i++){
for(int j = s.size()-1;j>=i;j--){
if(todo(s, i, j)){
if(j-i+1>m){
m=j-i+1;
mi=i;
}
}
}
}
return s.substr(mi,m);
}
结果1：
内存超了，但是本地运行可以。算法没错。
image.png
想法2：
中心扩展：
每个字都可以是中心，或者和后者组成中心，因为这是根据总回文数目奇偶性划分的。
int m = 0;
int mi = 0;
void todo(string s,int f ,int e ){
int i = f,j=e;
while(i>=0&&j<s.size()){
if(s[i]!=s[j]) return ;
if(j-i+1>m){
m=j-i+1;
mi=i;
}
i--;
j++;
}
return ;
}
string longestPalindrome(string s) {
if(s.size()==0) return "";
for(int i = 0;i<s.size();i++){
todo(s,i,i);
todo(s,i,i+1);
}
return s.substr(mi,m);
}
image.png
最好的是Manacher's Algorithm，O（n）
6.ZigZag Conversion
题目：一个字符串，按给定行数之字形打印，按正常行顺序输出。
image.png
想法1：
使用二维数组保存之的列。
代码1：
string convert(string s, int numRows) {
vector<vector<char>> r;
int c = 0;
int c2 = 0;
vector<char> temp;
for(int i = 0;i<s.size();){
if(c%numRows==0||c%numRows==numRows-1){
temp.push_back(s[i++]);
c2++;
}else{
if(c2==(numRows-1-c%numRows)) temp.push_back(s[i++]);
else temp.push_back(' ');
c2++;
}
if(c2==numRows){
r.push_back(temp);
c2=0;
c++;
if(c==numRows-1) c=0;
temp.clear();
}
}
if(!temp.empty()){
while(c2<numRows){
temp.push_back(' ');
c2++;
}
r.push_back(temp);
temp.clear();
}
string result="";
for(int i = 0;i<numRows;i++){
for(int j = 0;j<r.size();j++){
if(r[j][i]!=' ') result+=r[j][i];
}
}
return result;
}
结果1：
image.png
这么辣鸡？看看别人的。
想法2：
按行存，使用方向标志改变方向，第一行向下，最后行向上。
string convert(string s, int numRows) {
if (numRows == 1) return s;
vector<string> rows(min(numRows, int(s.size())));
int curRow = 0;
bool goingDown = false;
for (char c : s) {
rows[curRow] += c;
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}
string ret;
for (string row : rows) ret += row;
return ret;
}
想法3：
按之字的规律，
image.png
-
Reverse Integer
题目：给一个整数，反转
image.png
想法1：一个个数位取出来，*10加回去
代码1：
int reverse(int x) {
int r= 0;
while(x!=0){
if(r>INT_MAX/10 || (r == INT_MAX / 10 && x%10 > 7)) return 0;
if(r<INT_MIN/10 || (r == INT_MIN / 10 && x%10 < -8)) return 0;
r=r*10+x%10;
x=x/10;
}
return r;
}
结果1：
注意比较最大最小的时候，不能使用r10>INT_MAX，因为这个r10可能就已经超出了，变成别的数字，不是r的十倍。试过r用long表示，那么可以直接跟INT_MAX比较，但是本地调试不通过，在线通过？？
image.png
8.String to Integer (atoi)
题目：字符串转数字
规则1：第一个非空字符如果不是+、-或者数字，则返回0，数字后面有文字则不略过后面字符。超出int范围则返回最大值。
image.png
想法1：
判断各种状态............会漏很多情况。
代码1：
int myAtoi(string str) {
long result=0;
bool flag = false;
bool first = false;
for(int i = 0 ;i<str.size();i++){
if(first&&(str[i]<'0'||str[i]>'9')){
break;
}
if(!first&&(str[i]!=' '&&str[i]!='+'&&str[i]!='-'&&(str[i]<'0'||str[i]>'9'))){
return 0;
}
if(str[i]=='-'||str[i]=='+'){
if(!first)first=!first;
if(str[i+1]>='0'&&str[i+1]<='9'){
if(str[i]=='-')flag=true;
}else return 0;
}
if(str[i]>='0'&&str[i]<='9'){
if(!first)first=!first;
if(flag){
if(-result<INT_MIN/10||(-result == INT_MIN / 10 && str[i]-'0' >= 8)) return INT_MIN;
}else if(result>INT_MAX/10|| (result == INT_MAX / 10 && str[i]-'0' >= 7)) return INT_MAX;
result=result*10+str[i]-'0';
}
}
if(flag) result=-result;
return result;
}
结果1：
image.png
尝试了9次 0.0
看看别人的。
想法2：
9. Palindrome Number
题目：判断一个数字是不是回文结构
想法1：取每个数位放入数组，对比
代码1：
bool isPalindrome(int x) {
if(x<0) return false;
if(x==0) return true;
vector<int> r;
int temp;
while(x!=0){
temp = x%10;
r.push_back(temp);
x=x/10;
}
int le =r.size();
for(int i =0 ;i <= (le-1)/2;i++){
if(r[i]!=r[le-1-i]) return false;
}
return true;
}
结果1：
image.png
想法2：
翻转后面一半的数字，和前面一半的对比，比如12321，后面21弄成12，和123/10对比，
bool isPalindrome(int x) {
if(x<0|| (x!=0 &&x%10==0)) return false;
int sum=0;
while(x>sum)
{
sum = sum*10+x%10;
x = x/10;
}
return (x==sum)||(x==sum/10);
}
10.Regular Expression Matching
题目：输入字符串s和匹配模式p，‘.’可以匹配所有单个字符，‘’匹配0或者多个前一个字符。跟牛客的一样。
想法1：
按下一个是不是，分析出各种状态。
代码1：
结果1:
11. Container With Most Water
题目：
求出左右边界，组成的面积最大。
image.png
想法1：
暴力的试下。
代码1：
int maxArea(vector<int>& height) {
int m = 0;
int temp = 0;
int c = 0;
int k = 0;
for(int i = 0;i<height.size()-1;i++){
for(int j = i+1;j<height.size();j++){
c = j-i;
k = min(height[i],height[j]);
m=max(m,c*k);
}
}
return m;
}
结果1:
超时：
image.png
想法2：
滑动窗口，动态规划？
left表示最高的左侧，一边移动right一边判断移动left。
两指针：left从0开始，right从最右边开始。
移动较短的一边
原理：面积受较短的限制，移动较长的一边对面积提升没什么效果，还是受较短的限制，所以移动较短的一边，可能会克服宽度减少的损失。
代码2：
int maxArea(vector<int>& height) {
int m = 0;
int temp = 0;
int left = 0;
int right = height.size()-1;
while(left<right){
temp = (right-left)*min(height[left],height[right]);
m = max(temp,m);
if(height[left]<=height[right]) left++;
else right--;
}
return m;
}
结果2：
image.png
12. Integer to Roman
题目：罗马数字
image.png
想法1：每个数位枚举出来，遍历的时候找到对应的字符，使用栈输出，先进后出。
代码1：
string c[4][10]={
{"","I","II","III","IV","V","VI","VII","VIII","IX"},
{"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"},
{"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"},
{"","M","MM","MMM"}
};
string intToRoman(int num) {
string r="";
stack<string> result;
int cou = 0;
while(num!=0){
result.push(c[cou][num%10]);
num=num/10;
cou++;
}
while(!result.empty()){
r+=result.top();
result.pop();
}
return r;
}
结果1：
image.png
13. Roman to Integer
题目：罗马转成数字
想法1:把能组合的东西放一起，碰到不能一起的就计算，但是VI,LX,DC，这样的算出来-1应该是能组合的，但是会导致MD计算错误，所以VI,LX,DC分开的算也没事。
代码1：
string c[4][10]={
{"","I","II","III","IV","V","VI","VII","VIII","IX"},
{"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"},
{"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"},
{"","M","MM","MMM"}
};
char c2[7]={'I','V','X','L','C','D','M'};
int c3[7]={1,5,10,50,100,500,1000};
int myfind(string tc){
for(int i =0 ;i<4;i++){
for(int j=0;j<10;j++){
if(c[i][j]==tc) {
double temp = j*pow(10,i);
return temp;
}
}
}
return 0;
}
int myfind2(char tc){
for(int i =0 ;i<7;i++){
if(c2[i]==tc) return i;
}
return 0;
}
int romanToInt(string s) {
int left = 0;
int sum = 0;
if(s.size()==0){
return 0;
}
if(s.size()==1){
return c3[myfind2(s[0])];
}
for(int i = 1 ;i<s.size();i++){
int temp = myfind2(s[i]);
int temp2 = myfind2(s[i-1]);
if(temp-temp2!=0&&temp-temp2!=1&&temp-temp2!=2)
{
sum+=myfind(s.substr(left,i-left));
left = i;
}
if(i==s.size()-1)
{
sum+=myfind(s.substr(left,i-left+1));
}
}
return sum;
}
结果1：
image.png
想法2：
直接遍历，如果遇到小的在大的前面，就减去小的，否则加上。
int romanToInt(string s) {
int result=0;
int map[256];
map['I']=1;map['V']=5;map['X']=10;map['L']=50;map['C']=100;map['D']=500;map['M']=1000;
for(int i=0;i<s.size();i++){
if(i+1<s.size()&&map[s[i]]<map[s[i+1]]) result-=map[s[i]];
else result+=map[s[i]];
}
return result;
}
14. Longest Common Prefix
题目：找出数组中最长的公共前缀
想法1：
横向遍历对比每个串的前缀，直到不一样为止，输出。
flag可以去掉，直接return 结果，但是消耗资源变多了，8 ms，9 MB
代码1：
string longestCommonPrefix(vector<string>& strs) {
string result="";
if(strs.size()==0) return result;
int le = INT_MAX;
for(int i =0;i<strs.size();i++){
int temp = strs[i].size();
le=min(le, temp);
}
if(le==0) return result;
bool flag =true;
for(int j =0; j < le;j++){
for(int f = 0 ;f<strs.size()-1;f++){
if(strs[f][j]!=strs[f+1][j]) {
flag = false;
break;
}
}
if(flag) result += strs[0][j];
else break;
}
return result;
}
结果1：
image.png
15. 3Sum
题目：从数组中找出，三个数字和为0的数对。
image.png
想法1：暴力遍历
代码1：
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
set<vector<int>> result2;
int le = nums.size();
if(le<3) return result;
for(int i =0;i<nums.size();i++){
for(int j =i+1;j<nums.size();j++){
for(int k =j+1;k<nums.size();k++){
if(nums[i]+nums[j]+nums[k]==0){
vector<int> temp;
temp.push_back(nums[i]);
temp.push_back(nums[j]);
temp.push_back(nums[k]);
sort(temp.begin(),temp.end());
result2.insert(temp);
break;
}
}
}
}
set<vector<int>>::iterator iter = result2.begin();
while (iter!=result2.end())
{
result.push_back(*iter);
iter++;
}
return result;
}
结果1：
超时。
想法2：
排序后，遍历固定一个指针i，左指针j，右指针k。小于0，j++，大于0，k--。
要跳过j，k重复值，还有i重复值。
代码2：
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
int le = nums.size();
if(le<3) return result;
sort(nums.begin(),nums.end());
for(int i =0;i<nums.size()-2;i++){
if(i>0&&nums[i]==nums[i-1]){continue;}
int j =i+1;
int k =nums.size()-1;
while(j<k){
if(nums[i]+nums[j]+nums[k]==0){
vector<int> temp;
temp.push_back(nums[i]);
temp.push_back(nums[j]);
temp.push_back(nums[k]);
result.push_back(temp);
while(j<k&&nums[j+1]==nums[j]) j++;
if(j<k)j++;
while(j<k&&nums[k-1]==nums[k]) k--;
if(j<k)k--;
}
if(nums[i]+nums[j]+nums[k]<0){
j++;
}
if(nums[i]+nums[j]+nums[k]>0){
k--;
}
}
}
return result;
}
结果2：
image.png
16.3Sum Closest
题目：给出一个数组n，找出3个数字的和最接近给定的sum。
image.png
想法1：
在上面的方法修改，大于目标值，右指针左移，小于目标值，左指针右移。
代码1：
int threeSumClosest(vector<int>& nums, int target) {
int result;
int le = nums.size();
if(le<3) return result;
sort(nums.begin(),nums.end());
int m =INT_MAX;
for(int i =0;i<nums.size()-2;i++){
if(i>0&&nums[i]==nums[i-1]){continue;}
int j =i+1;
int k =nums.size()-1;
while(j<k){
int mj = nums[j];
int mk = nums[k];
int temp = abs(nums[i]+mj+mk-target);
if(temp<m){
m =temp;
result = nums[i]+nums[j]+nums[k];
}
if(nums[i]+mj+mk<target) j++;
if(nums[i]+mj+mk>target) k--;
if(nums[i]+mj+mk==target) return result;
}
}
return result;
}
结果1：
image.png
数组的问题好像都可以想想左右指针。
17. Letter Combinations of a Phone Number
题目：九宫格，2-9的字母排列组合。
image.png
想法1：
跟之前的字母排列一样，固定前面的，加上后面的，DFS
代码1：
vector<vector<string>> l = {
{"a","b","c"},
{"d","e","f"},
{"g","h","i"},
{"j","k","l"},
{"m","n","o"},
{"p","q","r","s"},
{"t","u","v"},
{"w","x","y","z"}
};
vector<string> result;
void dfs(string temp, vector<int> nums, int f,int e){
int le = l[nums[f]-2].size();
if(f==e){
for(int i =0; i<le;i++){
result.push_back(temp+l[nums[f]-2][i]);
}
return ;
}else{
for(int i =0; i<le;i++){
dfs(temp+l[nums[f]-2][i],nums,f+1,e);
}
}
}
vector<string> letterCombinations(string digits) {
vector<int> nums;
if(digits=="") return result;
for(char s : digits){
if(s=='1') continue;
nums.push_back(s-'0');
}
string temp = "";
dfs(temp,nums,0,nums.size()-1);
return result;
}
结果1：
image.png
讨论说叫回溯法，不太懂。
18. 4Sum
题目：
数组中找出4个数字等于给定数字，结果去重
想法1：
试试3sum的修改。
代码1：
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
int le = nums.size();
if(le<4) return result;
sort(nums.begin(),nums.end());
for(int ii =0;ii<nums.size()-3;ii++){
if(ii>0&&nums[ii]==nums[ii-1]){continue;}
for(int i =ii+1;i<nums.size()-2;i++){
int j =i+1;
int k =nums.size()-1;
while(j<k){
if(ii>0&&nums[i]==nums[i-1]){
if(nums[i]+nums[j]+nums[k]==target-nums[ii]){
break;
}
if(nums[i]+nums[j]+nums[k]<target-nums[ii]){
j++;
}
if(nums[i]+nums[j]+nums[k]>target-nums[ii]){
k--;
}
continue;
}
if(nums[i]+nums[j]+nums[k]==target-nums[ii]){
vector<int> temp;
temp.push_back(nums[ii]);
temp.push_back(nums[i]);
temp.push_back(nums[j]);
temp.push_back(nums[k]);
result.push_back(temp);
while(j<k&&nums[j+1]==nums[j]) j++;
if(j<k)j++;
while(j<k&&nums[k-1]==nums[k]) k--;
if(j<k)k--;
}
if(nums[i]+nums[j]+nums[k]<target-nums[ii]){
j++;
}
if(nums[i]+nums[j]+nums[k]>target-nums[ii]){
k--;
}
}
}
}
return result;
}
结果1：
image.png
情况太多了。
想法2：
把第二位排重的放到for下面成功，下面的if还是配合else使用好。
代码2：
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
int le = nums.size();
if(le<4) return result;
sort(nums.begin(),nums.end());
for(int ii =0;ii<nums.size()-3;ii++){
if(ii>0&&nums[ii]==nums[ii-1]){continue;}
for(int i =ii+1;i<nums.size()-2;i++){
if(i>ii+1&&nums[i]==nums[i-1]) continue;
int j =i+1;
int k =nums.size()-1;
while(j<k){
if(nums[i]+nums[j]+nums[k]==target-nums[ii]){
vector<int> temp;
temp.push_back(nums[ii]);
temp.push_back(nums[i]);
temp.push_back(nums[j]);
temp.push_back(nums[k]);
result.push_back(temp);
while(j<k&&nums[j+1]==nums[j]) j++;
if(j<k)j++;
while(j<k&&nums[k-1]==nums[k]) k--;
if(j<k)k--;
}else if(nums[i]+nums[j]+nums[k]<target-nums[ii]){
j++;
}else if(nums[i]+nums[j]+nums[k]>target-nums[ii]){
k--;
}
}
}
}
return result;
}
结果2：
image.png
19. Remove Nth Node From End of List
题目：删除倒数第N个节点。
image.png
想法1：
一般是获取长度，然后重新走到倒数第N-1个删除下一个，但是提示要求一次弄完，那就两个指针，一个P走N，剩下路程L-N，另一个指针Q从头开始跟P一起走，直到P到了尾部，那么Q也到了倒数第N+1个节点，开始操作。但是别忘记删除第一个节点的情况。删除第一个节点的时候，P会走到尾部的NULL。
代码1：
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode*p = head;
ListNode*q = head;
while(n>0){
p = p->next;
n--;
}
if(p!=NULL){
while(p->next!=NULL){
q=q->next;
p=p->next;
}
q->next=q->next->next;
}else{
head = head->next;
}
return head;
}
结果1：
image.png
20. Valid Parentheses
题目：判断括号的合理性
image.png
想法1：
看了下答案的想法，使用栈，先匹配最近的左括号，相同则pop，否则push。最终是空表示匹配完全。
代码1：
bool isValid(string s) {
if(s=="") return true;
if(s.size()%2==1){
return false;
}
stack<char> temp;
temp.push(s[0]);
for(int i = 1;i<s.size();i++){
if(!temp.empty()&&s[i]-temp.top()<3&&s[i]-temp.top()>0){
temp.pop();
}else{
temp.push(s[i]);
}
}
if(temp.empty()) return true;
return false;
}
结果1：
image.png
想法2：
bool isValid(string s) {
stack<char> paren;
for (char& c : s) {
switch (c) {
case '(':
case '{':
case '[': paren.push(c); break;
case ')': if (paren.empty() || paren.top()!='(') return false; else paren.pop(); break;
case '}': if (paren.empty() || paren.top()!='{') return false; else paren.pop(); break;
case ']': if (paren.empty() || paren.top()!='[') return false; else paren.pop(); break;
default: ; // pass
}
}
return paren.empty() ;
}
21. Merge Two Sorted Lists
题目：合并两个排好序的列表
想法1：归并
代码1：
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* head;
ListNode* p;
if(l1==NULL&&l2==NULL) return NULL;
if(l1==NULL&&l2!=NULL) {return l2;}
if(l1!=NULL&&l2==NULL) {return l1;}
if(l1!=NULL&&l2!=NULL){
if(l1->val<=l2->val) {head = l1;l1=l1->next;}
else {head = l2;l2=l2->next;}
}
p = head;
while(l1!=NULL||l2!=NULL){
if(l1!=NULL&&l2!=NULL){
if(l1->val<=l2->val) {
p->next = l1;
l1=l1->next;
}
else {
p->next = l2;
l2=l2->next;
}
}else{
if(l1!=NULL) {
p->next = l1;
l1=l1->next;
}
if(l2!=NULL)
{
p->next = l2;
l2=l2->next;
}
}
p=p->next;
}
return head;
}
结果1：
image.png
22. Generate Parentheses
题目：给n对括号，排列出有效的组合。
image.png
想法1：
topic有个回溯法，是不是跟字母排列组合一样？
列出所有组合，判断合理的
借助之前的括号问题，使用计数器辅助判断该组合是不是合理。
代码1：
vector<string> result;
void todo(string s , int f, int e){
if(f==e){
s+=")";
int cou=0;
for(char ss: s){
if(ss=='(') cou++;
else if(ss==')') cou--;
if(cou<0) return;
}
if(cou==0) result.push_back(s);
return;
}
todo(s+")",f+1,e);
todo(s+"(",f+1,e);
}
vector<string> generateParenthesis(int n) {
int le = n*2-1;
if(le == 0) return result;
string s = "(";
todo(s,1,le);
return result;
}
结果1：
image.png
想法2：
不是每次都加入（），有效的加入（），限定左右括号数目
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
backtrack(ans, "", 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, String cur, int open, int close, int max){
if (cur.length() == max * 2) {
ans.add(cur);
return;
}
if (open < max)
backtrack(ans, cur+"(", open+1, close, max);
if (close < open)
backtrack(ans, cur+")", open, close+1, max);
}
23. Merge k Sorted Lists
题目：合并k个排序的列表
想法1：
比较每个头部为，知道每个人都到了NULL。
代码1：
ListNode* mergeKLists(vector<ListNode*>& lists) {
int le = lists.size();
if(le==0) return NULL;
int m = INT_MAX;
int f = 0;
ListNode thead(0);
ListNode* p = &thead;
int cou = 0;
bool flag = true;
while(true){
cou = 0;
m = INT_MAX;
for(int i = 0;i<le;i++){
if(lists[i]==NULL){
cou++;
if(cou == le) return thead.next;
continue;}
if(m>=lists[i]->val) {
m = lists[i]->val;
f = i;
}
}
p->next = lists[f];
lists[f] = lists[f]->next;
p=p->next;
}
return thead.next;
}
结果1：
image.png
效率好低
24. Swap Nodes in Pairs
题目:交换链表的相邻节点，不能修改值，只能修改节点本身
image.png
想法1：交换head和temp，用pre记录下一组交换前的一个位置。
代码1：
ListNode* swapPairs(ListNode* head) {
ListNode tHead(0);
ListNode* temp;
ListNode* pre;
if(head==NULL) return NULL;
if(head->next!=NULL){
temp = head->next;
head->next = temp->next;
temp->next = head;
tHead.next = temp;
}else return head;
while(head->next!=NULL&&head->next->next!=NULL){
pre = head;
temp = head->next->next;
head = head->next;
head->next = temp->next;
temp->next = head;
pre->next = temp;
}
return tHead.next;
}
结果1：
image.png
25. Reverse Nodes in k-Group
题目：上题的改版，自定义k个反转
想法1：
使用vector和reserve来局部反转，然后在从头穿起来。
代码1：
ListNode* reverseKGroup(ListNode* head, int k) {
if(head==NULL) return NULL;
if(head->next==NULL) return head;
ListNode tHead(0);
ListNode* temp = head;
tHead.next = head;
vector<ListNode*> nodes;
while(temp!=NULL){
nodes.push_back(temp);
temp=temp->next;
}
int le = nodes.size();
int n = le/k;
for(int i = 0;i<n;i++){
reverse(nodes.begin()+i*k,nodes.begin()+k+i*k);
//for(int first = i*k,en= k+i*k-1;first<en;first++,en--){
// swap(nodes[first], nodes[en]);
// }
// }
temp = nodes[0];
tHead.next = temp;
for(int i = 1;i<nodes.size();i++){
temp->next = nodes[i];
temp = temp->next;
}
nodes[nodes.size()-1]->next = NULL;
return tHead.next;
}
结果1：
image.png
想法2：
使用递归
ListNode* reverseKGroup(ListNode* head, int k) {
vector<ListNode*> p;
p.push_back(head);
if(p[0]==NULL) return head;
for(int i=1;i<k;i++){
p.push_back(p[i-1]->next);
if(p[i]==NULL) return head;
}
//reverse
p[0]->next=reverseKGroup(p[k-1]->next,k);
for(int i=k-1;i>0;i--){
p[i]->next=p[i-1];
}
return p[k-1];
}
26. Remove Duplicates from Sorted Array
题目：排好序的数组去重，不能使用额外的数组
想法1：左右指针，左指针是找出比前一个小于等于表示当前要换的，右指针找出比前一个大的用来换。
代码1：
void myswap(vector<int>& nums, int f, int e){
if(e>=nums.size())
return;
if(nums[f]<=nums[f-1]){
while(e<nums.size()){
if(nums[e]<=nums[f-1]) e++;
else {
int t1 = nums[f];
int t2 = nums[e];
swap(nums[f],nums[e]);
break;
}
}
}
myswap(nums,f+1,e+1);
}
int removeDuplicates(vector<int>& nums) {
if(nums.size()<2) return nums.size();
if(nums.size()==2){
if(nums[1]==nums[0]) return 1;
return 2;
}
int firest = 1 ;
int en = 2;
myswap(nums,firest,en);
int cou =1;
for(int i =1;i<nums.size();i++){
if(nums[i-1]<nums[i]){
cou++;
}else return cou;
}
return cou;
}
结果1：
image.png
想法2：
左右指针i，j，j比较快和i比，如果j比i大，那么他放入i的下一位，i进入下一位。
代码2：
int removeDuplicates(vector<int>& nums) {
if(nums.size()==0) return 0;
int i = 0 ;
for(int j =1;j<nums.size();j++){
if(nums[i]<nums[j]){
i++;
nums[i] = nums[j];
}
}
return i+1;
}
image.png
27. Remove Element
题目：删除元素
想法1：
双指针，遍历找出不一样的按顺序放入前面的
代码1：
int removeElement(vector<int>& nums, int val) {
int i = 0 ;
for(int j = 0;j<nums.size();j++){
if(nums[j]!=val)
{nums[i] = nums[j];
i++;}
}
return i;
}
结果1：
image.png
想法2：
两边往中间缩减
//我的：
int removeElement(vector<int>& nums, int val) {
if(nums.size()==0) return 0;
int i = 0 ;
int j = nums.size()-1;
while(i<=j){
if(i==j&&nums[i]!=val) return i+1;
else if(i==j&&nums[i]==val) return i;
while(nums[i]!=val&&i<=j){
i++;
if(i==nums.size()-1&&nums[i]!=val) return nums.size();
}
while(nums[j]==val&&i<=j){
j--;
if(j<0) return 0;
}
if(i<=j){
nums[i]=nums[j];
i++;
j--;
}
}
return i;
}
//参考的：
int i = 0;
int n = nums.length;
while (i < n) {
if (nums[i] == val) {
nums[i] = nums[n - 1];
// reduce array size by one
n--;
} else {
i++;
}
}
return n;
结果2:
我的判断情况很多，没理解根本原理。
28. Implement strStr()
题目：字符串中找出子串的索引，无就返回-1，空子串返回0
想法1：提示是2指针，不能跟前面一样想一个情况加入一个判断，永远处理不完所有情况，根据原理来。两个指针的一般都比较简单。
找出所有头，每个头判断是不是符合。
代码1：
int todo(int j ,string haystack, string needle){
int f = 0;
for(int i = j;i<haystack.size();i++){
if(haystack[i]==needle[f]){
f++;
}else{
return -1;
}
if(f==needle.size()) {
return j;
}
}
return -1;
}
int strStr(string haystack, string needle) {
int f = 0;
int r = -1;
if(needle == "") return 0;
if(haystack == "") return -1;
vector<int> start;
for(int i = 0;i<haystack.size();i++){
if(haystack[i]==needle[0]){
start.push_back(i);
}
}
for(int k = 0;k<start.size();k++){
int result = todo(start[k],haystack,needle);
if(result>-1){
return result;
}
}
return -1;
}
结果1：
image.png
想法2：
滑动窗口，长度是needle，从str头划到尾部，找到合适长度的进行匹配。
int strStr(string haystack, string needle) {
int f = 0;
if(needle == "") return 0;
if(haystack == "") return -1;
int i = 0;
int j = needle.size()-1;
while(j<haystack.size()){
if(haystack[i]!=needle[0]||haystack[j]!=needle[needle.size()-1]){
i++;
j++;
}
else {
int f = 0;
for(int k = i;k<j+1;k++){
if(haystack[k]==needle[f]){
f++;
}else{
i++;
j++;
break;
}
if(f==needle.size()) {
return i;
}
}
}
}
return -1;
}
image.png
想法3：
最普通的暴力，就是
1.如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
2.如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。
我没想到i的回溯方法：
int ViolentMatch(char* s, char* p)
{
int sLen = strlen(s);
int pLen = strlen(p);
int i = 0;
int j = 0;
while (i < sLen && j < pLen)
{
if (s[i] == p[j])
{
//①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++
i++;
j++;
}
else
{
//②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
i = i - j + 1;
j = 0;
}
}
//匹配成功，返回模式串p在文本串s中的位置，否则返回-1
if (j == pLen)
return i - j;
else
return -1;
}
还有种KMP的优化，上面的i不用回退到那么多，回退到最近的公共前缀。
https://blog.csdn.net/liu940204/article/details/51318281
29. Divide Two Integers
题目：不使用*%/算出两个数的除法。舍去小数。32位，不能除以0， [−2^31, 2^31 − 1]，溢出返回 2^31 − 1 。
想法1：
使用log和pow来解决乘除，但是pow的double 少一问题解决不了，
代码1：
int divide(int dividend, int divisor) {
bool f = false;
long d1 =dividend;
long d2 = divisor;
if(dividend<0&&divisor>0) {
f = true;
d1 = -d1;
}
if(dividend>0&&divisor<0) {
f = true;
d2 = -d2;
}
if(dividend<0&&divisor<0) {
d1 = -d1;
d2 = -d2;
}
double q = (double)(log10(d1)-log10(d2));
long i;
if(f){
i = -pow(10,q);
}else i = pow(10,q);
if(i>INT_MAX||i<INT_MIN) return INT_MAX;
return i ;
}
结果1：
image.png
想法2：
int divide(int dividend, int divisor) {
bool f = false;
long d1 =dividend;
long d2 = divisor;
if(dividend<0&&divisor>0) {
f = true;
d1 = -d1;
}
if(dividend>0&&divisor<0) {
f = true;
d2 = -d2;
}
if(dividend<0&&divisor<0) {
d1 = -d1;
d2 = -d2;
}
long long res=double(exp(log(d1)-log(d2)));
if(f){
res = -res;
}else res = res;
if(res>INT_MAX||res<INT_MIN) return INT_MAX;
return res ;
}
想法3：
上面的太偷巧了，
参考别人的使用位运算，不太会。
int divide(int dividend, int divisor) {
if(!divisor) return INT_MAX;
if(divisor == 1) return dividend;
if(divisor == -1){
if(dividend == INT_MIN) {return INT_MAX;}
else {return -dividend;}
}
bool s1 = dividend<0;
bool s2 = divisor<0;
unsigned int nom = s1?-dividend:dividend;
unsigned int den = s2?-divisor:divisor;
unsigned int rem = 0;
unsigned int quot = 0;
for(int i=31; i>=0;--i){
rem <<= 1;
rem |= (nom >> i) & 1;
if(rem >= den){
rem -= den;
quot |= (1<<i);
}
}
return s1^s2?-quot:quot;
}
30. Substring with Concatenation of All Words
题目：
想法1：
代码1：
结果1：
刷前50的中等，容易？
31. Next Permutation
题目：求出下一个排列，如果没有下一个排列，就按升序排。
image.png
想法1：讨论说的一个维基的方法：
image.png
代码1：
void nextPermutation(vector<int>& nums) {
int le = nums.size();
if(le<=1) return;
int left = le-1;
int right = 0;
int temp = 0;
while(left>0){
if(nums[left]>nums[left-1]){
right = le-1;
while(right>left){
if(nums[right] > nums[left-1] ){
break;
}
right--;
}
temp = nums[left-1];
nums[left-1] = nums[right];
nums[right] = temp;
right = le -1;
while(left<right){
temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
return;
}else{
left--;
}
}
left = 0;
right = le -1;
while(left<right){
temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
结果1：
image.png
33. Search in Rotated Sorted Array
题目：一个没有重复的升序数组，可能按某个轴转，然后找出目标值。要求 O(log n).
image.png
想法1：先找出翻转点，然后判断哪部分进行二分法查找。
代码1：
int bire(vector<int>& nums ,int f, int e,int tar){
if(f>e) return -1;
int mid = (f+e)/2;
if(nums[mid] == tar){
return mid;
}
if(f==e) return -1;
if(nums[mid] > tar){
return bire(nums,f,mid-1,tar);
}else{
return bire(nums,mid+1,e,tar);
}
}
int search(vector<int>& nums, int target) {
int flag =-1;
if(nums.size() == 0) return -1;
if(nums.size() == 1) return nums[0]==target?0:-1;
for(int i =0;i<nums.size()-1;i++){
if(nums[i]>nums[i+1]){
flag = i;
break;
}
}
if(flag>=0){
if(target<=nums[flag]&&target>=nums[0]){
return bire(nums,0,flag,target);
}else{
return bire(nums,flag+1,nums.size()-1,target);
}
}else{
return bire(nums,0,nums.size()-1,target);
}
}
结果1：
image.png
想法2：
查找flag的时候是n复杂度，好像不行，分清楚左右。
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size()-1;
while (l<=r) {
int mid = (r-l)/2+l;
if (nums[mid] == target)
return mid;
if (nums[mid] < nums[r]) {
if (nums[mid]<target && target<=nums[r])
l = mid+1;
else
r = mid-1;
} else {
if(nums[l]<=target && target<nums[mid])
r = mid-1;
else
l = mid+1;
}
}
return -1;
}
34. Find First and Last Position of Element in Sorted Array
题目：升序数组，找出目标数字的首尾位置，找不到就返回-1。 O(log n)。
想法1：
找出那个等于值，然后左找开头，右找结尾。
代码1：
vector<int> searchRange(vector<int>& nums, int target) {
int le = nums.size();
int f = -1, e = -1;;
vector<int> result ={f,e};
if(le==0) return result;
int l = 0, r = nums.size()-1;
while(l<=r){
int mid = (r-l)/2+l;
if(nums[mid]==target){
while(mid>0&&nums[mid-1]==nums[mid])
{
mid--;
}
if(mid==0) f = 0;
f = mid;
break;
}
if(nums[mid]<target){
l = mid+1;
}else{
r = mid-1;
}
}
l = 0, r = nums.size()-1;
while(l<=r){
int mid = (r-l)/2+l;
if(nums[mid]==target){
while(mid<nums.size()&&nums[mid+1]==nums[mid])
{
mid++;
}
if(mid==nums.size()) e = nums.size()-1;
e = mid;
break;
}
if(nums[mid]<target){
l = mid+1;
}else{
r = mid-1;
}
}
result[0] = f;
result[1] = e;
return result;
}
结果1：
本地可以，在线错误。
想法2：
左找右找好像也是n复杂度，不行····
简单：线性的话，从左找，从右找，O（n）
讨论优雅的解决方法，找出做范围
vector<int> searchRange(vector<int>& nums, int target) {
int idx1 = lower_bound(nums, target);
int idx2 = lower_bound(nums, target+1)-1;
if (idx1 < nums.size() && nums[idx1] == target)
return {idx1, idx2};
else
return {-1, -1};
}
int lower_bound(vector<int>& nums, int target) {
int l = 0, r = nums.size()-1;
while (l <= r) {
int mid = (r-l)/2+l;
if (nums[mid] < target)
l = mid+1;
else
r = mid-1;
}
return l;
}
方法2：
vector<int> searchRange(vector<int>& nums, int target) {
int start = 0, end = nums.size(), mid, left, right;
while (start < end) {
mid = (start + end) / 2;
if (nums[mid] >= target)
end = mid;
else
start = mid + 1;
}
left = start;
start = 0, end = nums.size();
while (start < end) {
mid = (start + end) / 2;
if (nums[mid] > target)
end = mid;
else
start = mid + 1;
}
right = start;
return left == right ? vector<int> {-1,-1} : vector<int> {left,right-1};
}
35. Search Insert Position
题目：没有重复的排序数组，找出插入项的位置，或者存在的位置。
想法1：直接遍历
代码1：
int searchInsert(vector<int>& nums, int target) {
for(int i = 0;i<nums.size();i++){
if(nums[i]==target){
return i;
}else{
if(nums[0]>target) return 0;
if(nums[nums.size()-1]<target) return nums.size();
if(nums[i]<target&&nums[i+1]>target){
return i+1;
}
}
}
return 0;
}
结果1：
image.png
想法2：
topic是二分查找法，
int searchInsert(vector<int>& nums, int target) {
int l =0,r=nums.size()-1;
while(l<=r){
int mid =(r-l)/2+l;
if(nums[mid] == target){
return mid;
}
if(nums[mid] < target){
l = mid + 1;
}else{
r = mid - 1;
}
}
return r+1; //return l；
}
参考的：
找下界。
int searchInsert(vector<int>& nums, int target) {
/// return index of first one that comp(item,target)==true, or nums.size() if not found
/// comp is greater or equal to for lower_bound
/// comp is greater for upper_bound
int first=0, last=nums.size(), mid;
while (first<last) {
mid=first+((last-first)>>1); // first<=mid, mid<last
/// if comp(item,target)==false, advance first
// if(nums[mid]<=target) // for upper_bound
if (nums[mid]<target) // for lower_bound
first=mid+1; // first always increases
else /// else recede last
last=mid; // last always decreases (even last-first==1)
}
return first;
}
36. Valid Sudoku
题目：验证数独板子是不是有效，行列和3X3都得是0-9.
image.png
想法1：
先判断行，再判断列，在一个圈圈判断。
代码1：
bool isValidSudoku(vector<vector<char>>& board) {
for(int i = 0;i<9;i++){
vector<int> flag(9,0);
for(int j = 0;j<9;j++){
if(board[i][j]!='.'){
if(flag[board[i][j]-'0'-1]==0){
flag[board[i][j]-'0'-1]++;
}else return false;
}
}
}
for(int i = 0;i<9;i++){
vector<int> flag(9,0);
for(int j = 0;j<9;j++){
if(board[j][i]!='.'){
if(flag[board[j][i]-'0'-1]==0){
flag[board[j][i]-'0'-1]++;
}else return false;
}
}
}
for(int i = 0;i<9;i++){
vector<int> flag(9,0);
for(int j = 0;j<3;j++){
if(board[j+i/3*3][i%3*3]!='.'){
if(flag[board[j+i/3*3][i%3*3]-'0'-1]==0){
flag[board[j+i/3*3][i%3*3]-'0'-1]++;
}else return false;
}
if(board[j+i/3*3][i%3*3+1]!='.'){
if(flag[board[j+i/3*3][i%3*3+1]-'0'-1]==0){
flag[board[j+i/3*3][i%3*3+1]-'0'-1]++;
}else return false;
}
if(board[j+i/3*3][i%3*3+2]!='.'){
if(flag[board[j+i/3*3][i%3*3+2]-'0'-1]==0){
flag[board[j+i/3*3][i%3*3+2]-'0'-1]++;
}else return false;
}
}
}
return true;
}
结果1：
image.png
找圈圈的规律有点久。
想法2：
38. Count and Say
题目：读出来数字个数
image.png
想法1：
递归的方法，一遍遍历一遍统计，
代码1：
string countAndSay(int n) {
if(n==1) return "1";
string toread = countAndSay(n-1);
string result="";
int cou = 0;
int left = 0;
for(int i = 0 ;i<toread.size();i++){
if(toread[i]==toread[left]) cou++;
else{
result+=('0'+cou);
result+=toread[left];
cou=1;
left = i;
}
}
result+=('0'+cou);
result+=toread[left];
return result;
}
结果1：
image.png
想法2：
解决了我的最后个数字怎么处理的疑惑
string countAndSay(int n)
{
string curr_str;
// The initial case, when n = 1
curr_str += '1';
// The iterative case, when n > 1
for (int i = 0; i < n - 1; i++)
{
string buffer;
// Handle the current string
int index = 0;
for (int index = 0; index < curr_str.size(); ++index)
{
// Count the occurance of each digit
int cnt = 1; // At least one occurance
while (index + 1 < curr_str.size() and curr_str[index + 1] == curr_str[index])
{
index++;
cnt++;
}
buffer.push_back(cnt + '0');
buffer.push_back(curr_str[index]);
}
// Update the current string
curr_str = buffer;
}
return curr_str;
}
39. Combination Sum
题目：给定set数组，在里面找出和是target的组合，一个数组可以重复选。
想法1：
动态规划，当前这个数值加还是不加
代码1：
void todo(vector<int>& candidates, int target,int f,vector<int> temp,int sum,vector<vector<int>>& result){
int le = candidates.size();
if(f==candidates.size()) return;
if(sum+candidates[f]==target){
temp.push_back(candidates[f]);
result.push_back(temp);
return;
}
if(sum+candidates[f]>target) return;
todo(candidates, target, f+1, temp, sum, result);
sum+=candidates[f];
temp.push_back(candidates[f]);
todo(candidates, target, f, temp, sum, result);
return;
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> temp;
vector<vector<int>> result;
sort(candidates.begin(), candidates.end());
int sum =0;
todo(candidates, target, 0, temp, sum, result);
return result;
}
结果1：
image.png
为什么我的效率低？
想法2：
别人的
void search(vector<int>& num, int next, vector<int>& pSol, int target, vector<vector<int> >& result)
{
if(target == 0)
{
result.push_back(pSol);
return;
}
if(next == num.size() || target - num[next] < 0)
return;
pSol.push_back(num[next]);
search(num, next, pSol, target - num[next], result);
pSol.pop_back();
search(num, next + 1, pSol, target, result);
}
vector<vector<int> > combinationSum(vector<int> &num, int target)
{
vector<vector<int> > result;
sort(num.begin(), num.end());
vector<int> pSol;
search(num, 0, pSol, target, result);
return result;
}
别人的2：
void elementSum(vector<int>&candidates,vector<vector<int>>&res,vector<int>&elements,int target,int start){
// if the sum of the elements is equal to the target, push this combination into the result
if(!target){
res.push_back(elements);return;
}
for(int i=start;i<candidates.size();i++){
// if current element is bigger than the assigned target, there is
// no need to keep searching, since all the numbers are positive and sorted
if(candidates[i]>target) break;
//push the valid candidate into the elements vector.
elements.push_back(candidates[i]);
// keep searching for new elements with start as i since here duplicates are allowed
elementSum(candidates,res,elements,target-candidates[i],i);
elements.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> elements;
sort(candidates.begin(),candidates.end());
elementSum(candidates,res,elements,target,0);
return res;
}
40. Combination Sum II
题目：和上面相同，但是每个数字只能使用一次。而且有重复数字。
想法1：选择加入的时候，只加入一次相同值。
代码1：
void todo(vector<int>& candidates, int target, int index, vector<int>& temp, vector<vector<int>>& result) {
if(target==0) {
result.push_back(temp);
return;
}
if(index == candidates.size()) return;
if(target<0) return;
for(int i = index;i<candidates.size();i++){
if (i>index && candidates[i] == candidates[i-1])
continue;
temp.push_back(candidates[i]);
todo(candidates, target-candidates[i], i+1, temp, result);
temp.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> temp;
vector<vector<int>> result;
sort(candidates.begin(), candidates.end());
int sum =0;
todo(candidates, target, 0, temp, result);
return result;
}
结果1：
去重不太明白。
image.png
43. Multiply Strings
题目：字符串乘法
想法1：转成数字乘法
代码1：
string multiply(string num1, string num2) {
long temp = 0;
double cou = 0;
for(int i = num1.size()-1 ;i>=0;i--){
temp = (num1[i]-'0')*pow(10,cou++) + temp;
}
int temp2 = 0;
cou = 0;
for(int i = num2.size()-1 ;i>=0;i--){
temp2 = (num2[i]-'0')*pow(10,cou++) + temp2;
}
long temp3 = temp*temp2;
if(temp3==0) return "0";
string res = "";
while(temp3!=0){
char t = temp3%10+'0';
res = t+res;
temp3=temp3/10;
}
return res;
}
结果1：
超出了int范围，因为数字可能很大。"498828660196"，
"840477629533"。不能用数字表示。
想法2：
在这里插入图片描述
思路：如上图，先将数字逐位相乘法，然后把每一位的结果和（也就是红色的数字）存到数组指定位置，然后再考虑进位，进位操作完成后就是结果，记得把对前面的‘0’进行处理即可！
注意：两数相乘，最大位数不会超过他两之和，并且若两数都不为0，结果那么最多只会前面多一个0；
string multiply(string num1, string num2) {
if(num1=="0"||num2=="0") return "0";
int l1=num1.size(),l2=num2.size();
vector<int> res1(l1+l2,0);
int i = num1.size()-1;
int j = num2.size()-1;
string res2 = "";
int f = 0;
int temp1 = 0;
int temp2 = 0;
int temp3 =0;
int cou = 0;
for (int i = l2-1; i >= 0; i --) {
for (int j = l1 - 1; j >= 0; j --) {
int pro = (num2[i] - '0') * (num1[j]- '0');
res1[ l2-1- i + l1 - 1-j] += pro;
}
}
for(int i =0;i<l2 + l1;i++){
//if(res1[i]==0&&f==0) return res2;
temp3 = f+res1[i];
if(i==(l2+l1-1)&&temp3==0) return res2;
res2 = char(temp3%10+'0')+res2;
f = temp3/10;
}
return res2;
}
从头加入，还是从尾巴算起，使用反向迭代器：
class Solution {
public:
string multiply(string num1, string num2) {
string zero = "0";
if(num1 == zero || num2 == zero)
return zero;
string mul = "";
int size1 = num1.size(), size2 = num2.size(), c = 0;
vector<int> count(size1 + size2 - 1, 0);
for(int i = 0; i < size1; i ++)
for(int j = 0; j < size2; j ++)
count[i + j] += (num1[i] - '0') * (num2[j] - '0');
for(auto i = count.rbegin(); i != count.rend(); i ++){
int tmp = *i + c;
mul.insert(mul.begin(), tmp % 10 + '0');
c = tmp / 10;
}
if(c)
mul.insert(mul.begin(), c + '0');
return mul;
}
};
46. Permutations
题目：给定不同数字的数组，全排列
想法1：之前学的一个个位置交换
代码1：
void dfs(vector<int> temp,int index, int le,vector<vector<int>>& result){
if(index == le ){
result.push_back(temp);
cout<<temp[0];
cout<<temp[1];
cout<<temp[2]<<endl;
return;
}
for(int i = index;i<le;i++){
swap(temp[index],temp[i]);
dfs(temp,index+1,le,result);
swap(temp[index],temp[i]); //换了得还回来不影响下面
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> temp=nums;
dfs(temp,0,nums.size(),result);
return result;
}
}
结果1：
image.png
47. Permutations II
题目：有重复的数字
想法1:加入去重，这个文章解释的很清楚，为什么重复了
https://www.cnblogs.com/grandyang/p/4359825.html
使用set去重，不太合格
代码1：
void dfs(vector<int>& nums,int index, int le,set<vector<int>>& result){
if(index == le ){
result.insert(nums);
return;
}
for(int i = index;i<le;i++){
if(i>index&&nums[i]==nums[index]) continue;
swap(nums[index],nums[i]);
dfs(nums,index+1,le,result);
swap(nums[index],nums[i]);
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
set<vector<int>> result;
sort(nums.begin(),nums.end());
dfs(nums,0,nums.size(),result);
return vector<vector<int>> (result.begin(), result.end());
}
结果1：
image.png
想法2：
回溯法的一个模板
image.png
全排列的问题，不考虑重复
但是(vector<int>& temp）这里要不要用&？？，讨论的答案里都用了，那就用吧，记住这个模板。。。。
image.png
image.png
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
permute(nums, 0, res);
return res;
}
void permute(vector<int>& nums, int start, vector<vector<int>>& res) {
if (start >= nums.size()) res.push_back(nums);
for (int i = start; i < nums.size(); ++i) {
int j = i - 1;
while (j >= start && nums[j] != nums[i]) --j;
if (j != start - 1) continue;
swap(nums[i], nums[start]);
permute(nums, start + 1, res);
swap(nums[i], nums[start]);
}
}
最简单版本：不恢复了，恢复可能和前面的重复，也不是引用传递了。
怎么才能当递归结束后，不还原成为交换之前的状态的呢？答案就是不进行还原，这样还是能保存为之前交换后的状态。我们只是将最后一句 swap(nums[i], nums[start]) 删掉是不行的，因为我们的递归函数的参数 nums 是加了&号，就表示引用了，那么之前调用递归函数之前的 nums 在递归函数中会被修改，可能还是无法得到我们想要的顺序，所以我们要把递归函数的nums参数的&号也同时去掉才行。
void recursion(vector<int> num, int i, int j, vector<vector<int> > &res) {
if (i == j-1) {
res.push_back(num);
return;
}
for (int k = i; k < j; k++) {
if (i != k && num[i] == num[k]) continue;
swap(num[i], num[k]);
recursion(num, i+1, j, res);
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
sort(num.begin(), num.end());
vector<vector<int> >res;
recursion(num, 0, num.size(), res);
return res;
}
想法3：用set
void helper(vector<int>& a, int pos, int n, vector<vector<int> >& result) {
if (pos == n-1) {
result.push_back(a);
return;
}
unordered_set<int> swapped;
for (int i = pos; i < n; ++i) {
if (swapped.find(a[i]) != swapped.end()) continue;
swapped.insert(a[i]);
swap(a[pos], a[i]);
helper(a, pos+1, n, result);
swap(a[pos], a[i]);
}
