LeetCode 0001-0080 题解整合

L0001 Two Sum
First AC: 2019-07-25 Latest Modification: 2019-07-25
Note: 只要对每个数x判断左边是否有target-x,预处理遍历过的数,复杂度O(nlogn)

  1. #include<map>
  2. #include<vector>
  3. using namespace std;
  4. class Solution {
  5. public:
  6.     vector<int> twoSum(vector<int>& nums, int target) {
  7.         map<int,int>mp;
  8.         vector<int>::iterator itx;
  9.         map<int,int>::iterator ity;
  10.         int cnt = 0;
  11.         for(itx = nums.begin();itx != nums.end();++itx,++cnt){
  12.         	int rest = target - *itx;
  13.         	ity = mp.find(rest);
  14.         	if(ity != mp.end()){
  15.         		vector<int> ret;
  16.         		ret.push_back(ity->second);
  17.         		ret.push_back(cnt);
  18.         		return ret;
  19. 			}
  20. 			mp.insert(pair<int,int>(*itx,cnt));
  21. 		}
  22. 		return nums;
  23.     }
  24. };

L0002 Add Two Numbers
First AC: 2019-07-25 Latest Modification: 2019-07-25
Note: 模拟大数加法,复杂度O(n)

  1. class Solution {
  2. public:
  3.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  4.     	int temp = l1->val + l2->val;
  5.         ListNode *ret = new ListNode(temp % 10);
  6.         ListNode *node = ret;
  7.         int flag = temp / 10;
  8.         l1 = l1->next;
  9.         l2 = l2->next;
  10.         while(l1 && l2){
  11.         	temp = l1->val + l2->val + flag;
  12.         	flag = temp / 10;
  13.         	node->next = new ListNode(temp % 10);
  14.         	node = node->next;
  15.         	l1 = l1->next;
  16.         	l2 = l2->next;
  17. 		}
  18. 		while(l1){
  19. 			temp = l1->val + flag;
  20. 			flag = temp / 10;
  21. 			node->next = new ListNode(temp % 10);
  22. 			node = node->next;
  23. 			l1 = l1->next;
  24. 		}
  25. 		while(l2){
  26. 			temp = l2->val + flag;
  27. 			flag = temp / 10;
  28. 			node->next = new ListNode(temp % 10);
  29. 			node = node->next;
  30. 			l2 = l2->next;
  31. 		}
  32. 		if(flag){
  33. 			node->next = new ListNode(1);
  34. 		}
  35. 		return ret;
  36.     }
  37. };

L0003 Longest Substring Without Repeating Characters
First AC: 2019-07-25 Latest Modification: 2019-07-25
Note: 只要对每个右端点计算左端点,预处理最左左端点,复杂度O(n)

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     int lengthOfLongestSubstring(string s) {
  6.     	s = " " + s;
  7.         int len = s.length();
  8.         int temp[128] = {0};
  9.         int ret = 0;
  10.         int lst = 0;
  11.         for(int i = 1;i < len;++i){
  12.         	lst = max(lst,temp[s[i]]);
  13.         	ret = max(ret,i - lst);
  14. 			temp[s[i]] = i;
  15. 		}
  16. 		return ret;
  17.     }
  18. };

L0004 Median of Two Sorted Arrays
First AC: 2019-07-26 Latest Modification: 2019-07-26
Note: 比较两个中位数,两个数组都有一半区间不是最终答案,同时去掉相同长度,复杂度O(min(logn,logm)),再加上最后排序的一个常数

  1. #include<cmath>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5. class Solution {
  6. public:
  7.     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  8.         const double eps = 5e-3;
  9. 		int l1 = 0;
  10.         int r1 = nums1.size() - 1;
  11.         int l2 = 0;
  12.         int r2 = nums2.size() - 1;
  13.         int len1 = nums1.size();
  14.         int len2 = nums2.size();
  15.         while(len1 > 2 && len2 > 2){
  16.         	int mid1 = (l1 + r1) / 2;
  17.         	int mid2 = (l2 + r2) / 2;
  18.         	double temp1 = len1 & 1 ? nums1[mid1] : (nums1[mid1] + nums1[mid1 + 1]) / 2.0;
  19.         	double temp2 = len2 & 1 ? nums2[mid2] : (nums2[mid2] + nums2[mid2 + 1]) / 2.0;
  20.         	int half = min(len1 - 1,len2 - 1) / 2;
  21.         	if(fabs(temp1 - temp2) < eps){
  22.         		return temp1;
  23. 			}
  24.         	else if(temp1 < temp2){
  25.         		l1 += half;
  26.         		r2 -= half;
  27.         		len1 -= half;
  28.         		len2 -= half;
  29. 			}
  30. 			else{
  31. 				r1 -= half;
  32. 				l2 += half;
  33. 				len1 -= half;
  34. 				len2 -= half;
  35. 			}
  36. 		}
  37. 		if(len1 + len2 < 20){
  38. 			int a[20];
  39. 			int cnt = 0;
  40. 			for(int i = l1;i <= r1;++i){
  41. 				a[cnt++] = nums1[i];
  42. 			}
  43. 			for(int i = l2;i <= r2;++i){
  44. 				a[cnt++] = nums2[i];
  45. 			}
  46. 			sort(a,a+cnt);
  47. 			return cnt & 1? a[cnt / 2] : (a[cnt / 2 - 1] + a[cnt / 2]) / 2.0;
  48. 		}
  49. 		else if(len1 > len2){
  50. 			int a[20];
  51. 			int cnt = 0;
  52. 			int st = (l1 + r1) / 2 - 4;
  53. 			int ed,l,r;
  54. 			if(len1 & 1){
  55. 				ed = 9;
  56. 				l = 4;
  57. 				r = 4;
  58. 			}
  59. 			else{
  60. 				ed = 10;
  61. 				l = 4;
  62. 				r = 5;
  63. 			}
  64. 			for(int i = 0;i < ed;++i){
  65. 				a[cnt++] = nums1[st + i];
  66. 			}
  67. 			for(int i = l2;i <= r2;++i){
  68. 				if(nums2[i] < a[l]){
  69. 					a[l - 3] = nums2[i];
  70. 					sort(a + l - 3, a + l);
  71. 					--l;
  72. 				}
  73. 				else{
  74. 					a[r + 3] = nums2[i];
  75. 					sort(a + r + 1,a + r + 4);
  76. 					++r;
  77. 				}
  78. 			}
  79. 			sort(a + l,a + r + 1);
  80. 			int len = r - l + 1;
  81. 			int mid = (l + r) / 2;
  82. 			return len & 1 ? a[mid] : (a[mid] + a[mid + 1]) / 2.0;
  83. 		}
  84. 		else{
  85. 			int a[20];
  86. 			int cnt = 0;
  87. 			int st = (l2 + r2) / 2 - 4;
  88. 			int ed,l,r;
  89. 			if(len2 & 1){
  90. 				ed = 9;
  91. 				l = 4;
  92. 				r = 4;
  93. 			}
  94. 			else{
  95. 				ed = 10;
  96. 				l = 4;
  97. 				r = 5;
  98. 			}
  99. 			for(int i = 0;i < ed;++i){
  100. 				a[cnt++] = nums2[st + i];
  101. 			}
  102. 			for(int i = l1;i <= r1;++i){
  103. 				if(nums1[i] < a[l]){
  104. 					a[l - 3] = nums1[i];
  105. 					sort(a + l - 3, a + l);
  106. 					--l;
  107. 				}
  108. 				else{
  109. 					a[r + 3] = nums1[i];
  110. 					sort(a + r + 1,a + r + 4);
  111. 					++r;
  112. 				}
  113. 			}
  114. 			sort(a + l,a + r + 1);
  115. 			int len = r - l + 1;
  116. 			int mid = (l + r) / 2;
  117. 			return len & 1 ? a[mid] : (a[mid] + a[mid + 1]) / 2.0;
  118. 		}
  119.     }
  120. };

L0005 Longest Palindromic Substring
First AC: 2019-07-26 Latest Modification: 2019-07-26
Note: Manacher算法,复杂度O(n)

  1. #include<cmath>
  2. #include<iostream>
  3. using namespace std;
  4. class Solution {
  5. public:
  6.     string longestPalindrome(string s) {
  7.     	const int maxn = 2005;
  8.     	if(s == "")return s;
  9.         char str[maxn];
  10.         int cnt = 0;
  11.         int len = s.length();
  12.         str[cnt++] = '~';
  13.         for(int i = 0;i < len;++i){
  14.         	str[cnt++] = '.';
  15.         	str[cnt++] = s[i];
  16. 		}
  17. 		str[cnt++] = '.';
  18. 		str[cnt] = '\0';
  19. 		int p[maxn];
  20. 		int mx = 0;
  21. 		int id = 0;
  22. 		int temp = 0;
  23. 		int val = 0;
  24. 		for(int i = 0;i < cnt;++i){
  25. 			p[i] = mx > i ? min(mx - i,p[2 * id - i]) : 1;
  26. 			while(i > p[i] && str[i - p[i]] == str[i + p[i]])++p[i];
  27. 			if(i + p[i] > mx){
  28. 				mx = i + p[i];
  29. 				id = i;
  30. 			}
  31. 			if(p[i] > val){
  32. 				temp = i;
  33. 				val = p[i];
  34. 			}
  35. 		}
  36. 		len = temp + val;
  37. 		char ret[maxn];
  38. 		cnt = 0;
  39. 		for(int i = temp - val + 1;i < len;++i){
  40. 			if(str[i] != '.'){
  41. 				ret[cnt++] = str[i];
  42. 			}
  43. 		}
  44. 		ret[cnt] = '\0';
  45. 		return string(ret);
  46.     }
  47. };

L0006 Longest Palindromic Substring
First AC: 2019-07-26 Latest Modification: 2019-07-26
Note: 变步长遍历,复杂度O(n)

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     string convert(string s, int numRows) {
  6.     	int len = s.length();
  7.     	if(numRows == 1 || numRows >= len)return s;
  8.     	int sumx = --numRows * 2;
  9.     	char ret[len + 1];
  10.     	int cnt = 0;
  11.     	for(int i = 0;i < len;i += sumx){
  12.     		ret[cnt++] = s[i];
  13. 		}
  14.     	for(int i = 1;i < numRows;++i){
  15.     		int step1 = sumx - 2 * i;
  16.     		int step2 = 2 * i;
  17.     		ret[cnt++] = s[i];
  18.     		int j = i;
  19.     		while(1){
  20.     			if((j += step1) < len)ret[cnt++] = s[j];
  21.     			else break;
  22.     			if((j += step2) < len)ret[cnt++] = s[j];
  23.     			else break;
  24. 			}
  25. 		}
  26. 		for(int i = numRows;i < len;i += sumx){
  27. 			ret[cnt++] = s[i];
  28. 		}
  29. 		ret[cnt] = '\0';
  30. 		return string(ret);
  31.     }
  32. };

L0007 Reverse Integer
First AC: 2019-07-26 Latest Modification: 2019-07-26
Note: 在long范围内比较是否溢出,复杂度O(log(x))

  1. class Solution {
  2. public:
  3.     int reverse(int x) {
  4.     	if(x == INT_MIN || x == 0)return 0;
  5.         bool flag = 0;
  6.         if(x < 0){
  7.         	flag = 1;
  8.         	x = -x;
  9. 		}
  10. 		int ret = 0;
  11. 		while(x){
  12. 			long temp = ret * 10L + x % 10;
  13. 			if(temp > INT_MAX)return 0;
  14. 			ret = temp;
  15. 			x /= 10;
  16. 		}
  17. 		if(flag)return -ret;
  18. 		else return ret;
  19.     }
  20. };

L0008 String to Integer (atoi)
First AC: 2019-07-27 Latest Modification: 2019-07-27
Note: 在long long范围内比较是否溢出,复杂度O(len(str))

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     int myAtoi(string str) {
  6.     	str += "#";
  7.         int len = str.length();
  8.         int id = 0;
  9.         int flag = 0;
  10.         while(str[id] == ' ')++id;
  11.         if(str[id] == '+')++id;
  12.         else if(str[id] == '-')++id,flag = 1;
  13.         long long temp = 0;
  14.         int cnt = 0;
  15.         while(str[id] == '0')++id;
  16.         while(1){
  17.         	if(!isdigit(str[id]))break;
  18.         	temp = temp * 10 + str[id++] - '0';
  19.         	if(++cnt == 15)break;
  20. 		}
  21. 		if(cnt == 0)return 0;
  22. 		if(flag){
  23. 			return temp > INT_MAX ? INT_MIN : -temp;
  24. 		}
  25.         else{
  26.         	return temp >= INT_MAX ? INT_MAX : temp;
  27. 		}
  28.     }
  29. };

L0009 Palindrome Number
First AC: 2019-07-27 Latest Modification: 2019-07-27
Note: 先转化为数组,然后首尾逼近比较,复杂度O(log(x))

  1. class Solution {
  2. public:
  3.     bool isPalindrome(int x) {
  4.     	if(x < 0)return 0;
  5.         if(x == 0)return 1;
  6.         int a[32];
  7.         int cnt = 0;
  8.         while(x){
  9.         	a[cnt++] = x % 10;
  10.         	x /= 10;
  11. 		}
  12. 		for(int i = 0,j = cnt - 1;i < j;++i,--j){
  13. 			if(a[i] != a[j])return 0;
  14. 		}
  15. 		return 1;
  16.     }
  17. };

L0010 Regular Expression Matching
First AC: 2019-07-27 Latest Modification: 2019-07-27
Note: 动态规划,复杂度O(len(s)*len(p))

  1. #include<cstring>
  2. #include<iostream>
  3. using namespace std;
  4. class Solution {
  5. public:
  6.     bool isMatch(string s, string p) {
  7.     	s = ' ' + s;
  8.     	p = ' ' + p;
  9.         int lens = s.length();
  10.         int lenp = p.length();
  11.         bool ret[lens][lenp];
  12.         memset(ret,false,sizeof ret);
  13.         ret[0][0] = true;
  14.         for(int i = 2;i < lenp;++i){
  15.         	if(p[i] == '*')ret[0][i] = ret[0][i - 2];
  16. 		}
  17.         for(int i = 1;i < lens;++i){
  18.         	for(int j = 1;j < lenp;++j){
  19.         		if(s[i] == p[j] || p[j] == '.'){
  20.         			ret[i][j] = ret[i - 1][j - 1];
  21. 				}
  22.         		else if(p[j] == '*'){
  23.         			ret[i][j] = ret[i][j - 2];
  24.         			if(p[j - 1] == '.' || p[j - 1] == s[i]){
  25.         				ret[i][j] |= ret[i - 1][j];
  26. 					}
  27. 				}
  28. 			}
  29. 		}
  30. 		return ret[lens - 1][lenp - 1];
  31.     }
  32. };

L0011 Container With Most Water
First AC: 2019-07-27 Latest Modification: 2019-07-27
Note: 两端逼近,复杂度O(len(height))

  1. #include<cmath>
  2. class Solution {
  3. public:
  4.     int maxArea(vector<int>& height) {
  5.         int len = height.size();
  6.         int l = 0,r = len - 1;
  7.         int ret = 0;
  8.         while(l <= r){
  9.         	ret = max(ret,(r - l) * min(height[l],height[r]));
  10.         	height[l] < height[r] ? ++l : --r;
  11. 		}
  12. 		return ret;
  13.     }
  14. };

L0012 Integer to Roman
First AC: 2019-07-27 Latest Modification: 2019-07-27
Note: 每个数位分别判断,复杂度O(1)

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     string intToRoman(int num) {
  6.         string ret = "";
  7.         int temp = 0;
  8.         temp = num / 1000;
  9.         for(int i = 0;i < temp;++i)ret += "M";
  10.         num %= 1000;
  11.         temp = num / 100;
  12.         if(temp == 4)ret += "CD";
  13.         else if(temp == 9)ret += "CM";
  14.         else{
  15.         	if(temp > 4)ret += "D",temp -= 5;
  16.         	for(int i = 0;i < temp;++i)ret += "C";
  17. 		}
  18. 		num %= 100;
  19. 		temp = num / 10;
  20. 		if(temp == 4)ret += "XL";
  21.         else if(temp == 9)ret += "XC";
  22.         else{
  23.         	if(temp > 4)ret += "L",temp -= 5;
  24.         	for(int i = 0;i < temp;++i)ret += "X";
  25. 		}
  26. 		temp = num % 10;
  27. 		if(temp == 4)ret += "IV";
  28.         else if(temp == 9)ret += "IX";
  29.         else{
  30.         	if(temp > 4)ret += "V",temp -= 5;
  31.         	for(int i = 0;i < temp;++i)ret += "I";
  32. 		}
  33. 		return ret;
  34.     }
  35. };

L0013 Roman to Integer
First AC: 2019-07-28 Latest Modification: 2019-07-28
Note: 每一位与右边一位比较,小于则权重为负,否则权重为正,复杂度O(len(s))

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     int romanToInt(string s) {
  6.         int len = s.length();
  7.         s += 'I';
  8.         int a[len + 1];
  9. 		for(int i = 0;i <= len;++i){
  10. 			if(s[i] == 'I')a[i] = 1;
  11. 			else if(s[i] == 'V')a[i] = 5;
  12. 			else if(s[i] == 'X')a[i] = 10;
  13. 			else if(s[i] == 'L')a[i] = 50;
  14. 			else if(s[i] == 'C')a[i] = 100;
  15. 			else if(s[i] == 'D')a[i] = 500;
  16. 			else if(s[i] == 'M')a[i] = 1000;
  17. 		}
  18. 		int ret = 0;
  19. 		for(int i = 0;i < len;++i){
  20. 			if(a[i] < a[i + 1])ret -= a[i];
  21. 			else ret += a[i];
  22. 		}
  23. 		return ret;
  24.     }
  25. };

L0014 Longest Common Prefix
First AC: 2019-07-30 Latest Modification: 2019-07-30
Note: 依次比较,逐步缩小答案,复杂度O(sum(len(strs[i])))

  1. #include<cmath>
  2. #include<vector>
  3. #include<iostream>
  4. using namespace std;
  5. class Solution {
  6. public:
  7.     string longestCommonPrefix(vector<string>& strs) {
  8.         int len = strs.size();
  9.         if(!len)return "";
  10.         int ans = strs[0].length();
  11.         for(int i = 1;i < len;++i){
  12.         	int maxj = min(ans,(int)strs[i].length());
  13.         	for(int j = 0;j < maxj;++j){
  14.         		if(strs[0][j] != strs[i][j]){
  15.         			ans = j;
  16.         			break;
  17. 				}
  18. 			}
  19. 			ans = min(ans,maxj);
  20. 		}
  21. 		if(!ans)return "";
  22. 		else return strs[0].substr(0,ans);
  23.     }
  24. };

L0015 3 Sum
First AC: 2019-08-31 Latest Modification: 2019-08-31
Note: 两端逼近,重复跳过,复杂度O(n*n)

  1. #include<vector>
  2. #include<algorithm>
  3. using namespace std;
  4. class Solution {
  5. public:
  6.     vector< vector<int> > threeSum(vector<int>& nums) {
  7.         sort(nums.begin(),nums.end());
  8.         int len = nums.size();
  9.         vector< vector<int> > ret;
  10.         for(int i = 0;i < len;++i){
  11.         	if(nums[i] > 0)break;
  12.         	if(i > 0 && nums[i] == nums[i - 1])continue;
  13.         	int l = i + 1,r = len - 1;
  14.         	while(l < r){
  15.         		int temp = nums[i] + nums[l] + nums[r];
  16.         		if(temp == 0){
  17.         			int n[] = {nums[i],nums[l],nums[r]};
  18.         			vector<int> v(n,n + 3);
  19.         			ret.push_back(v);
  20.         			while(l < r && nums[l] == nums[l + 1])++l;
  21.         			while(l < r && nums[r] == nums[r - 1])--r;
  22.         			++l,--r;
  23. 				}
  24. 				else if(temp < 0)++l;
  25. 				else --r;
  26. 			}
  27. 		}
  28. 		return ret;
  29.     }
  30. };

L0016 3 Sum Closest
First AC: 2019-08-31 Latest Modification: 2019-08-31
Note: 两端逼近,重复跳过,复杂度O(n*n)

  1. #include<vector>
  2. #include<algorithm>
  3. using namespace std;
  4. class Solution {
  5. public:
  6.     int threeSumClosest(vector<int>& nums, int target) {
  7.         sort(nums.begin(),nums.end());
  8.         int len = nums.size();
  9.         int ret = 1 << 30;
  10.         for(int i = 0;i < len;++i){
  11.         	int l = i + 1,r = len - 1;
  12.         	while(l < r){
  13.         		int temp = nums[i] + nums[l] + nums[r];
  14.         		if(abs(temp - target) < abs(ret - target))ret = temp;
  15.         		if(temp == target)return target;
  16. 				else if(temp < target)++l;
  17. 				else --r;
  18. 			}
  19. 		}
  20. 		return ret;
  21.     }
  22. };

L0017 Letter Combinations of a Phone Number
First AC: 2019-08-31 Latest Modification: 2019-08-31
Note: dfs,注意输入为空串时返回空向量,复杂度O(4^len(digits))

  1. #include<vector>
  2. #include<iostream>
  3. using namespace std;
  4. class Solution {
  5. public:
  6. 	void dfs(vector<string> &ret,string s[],string &digits,string temp) {
  7. 		int len = temp.length();
  8. 		if(len == digits.length()){
  9. 			ret.push_back(temp);
  10. 			return;
  11. 		}
  12. 		int maxi = s[digits[len] - '1'].length();
  13. 		for(int i = 0;i < maxi;++i){
  14. 			temp = temp.substr(0,len) + s[digits[len] - '1'][i];
  15. 			dfs(ret,s,digits,temp);
  16. 		}
  17. 	}
  18.     vector<string> letterCombinations(string digits) {
  19.         string s[] = {"","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
  20.         vector<string> ret;
  21.         if(digits != "")dfs(ret,s,digits,"");
  22. 		return ret;
  23.     }
  24. };

L0018 4 Sum
First AC: 2019-09-01 Latest Modification: 2019-09-01
Note: 固定两数,两端逼近,复杂度O((len(nums))^3)

  1. #include<map>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5. typedef long long ll;
  6. class Solution {
  7. public:
  8. 	ll hash(ll a,ll b,ll c,ll d) {
  9. 		ll temp = a + 1e2 * b + 1e4 * c + 1e6 * d;
  10. 		return a * a + b * b + c * c + d * d + temp;
  11. 	}
  12.     vector< vector<int> > fourSum(vector<int>& nums, int target) {
  13.         sort(nums.begin(),nums.end());
  14.         int len = nums.size();
  15.         map<ll,bool>mp;
  16. 		vector< vector<int> > ret;
  17.         for(int i = 0;i < len;++i){
  18.         	for(int j = i + 1;j < len;++j){
  19.         		int temp = target - nums[i] - nums[j];
  20.         		int l = j + 1,r = len - 1;
  21.         		while(l < r){
  22.         			if(nums[l] + nums[r] == temp){
  23.         				ll t = hash(nums[i],nums[j],nums[l],nums[r]);
  24.         				if(mp.find(t) == mp.end()){
  25.         					int a[] = {nums[i],nums[j],nums[l],nums[r]};
  26.         					vector<int> v(a,a + 4);
  27.         					ret.push_back(v);
  28.         					mp.insert(pair<ll,bool>(t,1));
  29. 						}
  30. 						++l,--r;
  31. 					}
  32. 					else if(nums[l] + nums[r] < temp)++l;
  33. 					else --r;
  34. 				}
  35. 			}
  36. 		}
  37. 		return ret;
  38.     }
  39. };

L0019 Remove Nth Node From End of List
First AC: 2019-09-01 Latest Modification: 2019-09-01
Note: 先计算长度,再跳过指定节点,复杂度O(len(head))

  1. class Solution {
  2. public:
  3. 	int calculateLength(ListNode* head) {
  4. 		int ret = 0;
  5. 		ListNode* temp = head;
  6. 		while(temp != NULL)temp = temp->next,++ret;
  7. 		return ret;
  8. 	}
  9.     ListNode* removeNthFromEnd(ListNode* head, int n) {
  10.         int len = calculateLength(head) - n - 1;
  11.         if(len == -1)return head->next;
  12.         ListNode * temp = head;
  13.         while(len--)temp = temp->next;
  14.         temp->next = temp->next->next;
  15.         return head;
  16.     }
  17. };

L0020 Valid Parentheses
First AC: 2019-09-01 Latest Modification: 2019-09-01
Note: 栈匹配,复杂度O(len(s))

  1. #include<cmath>
  2. #include<stack>
  3. #include<iostream>
  4. using namespace std;
  5. class Solution {
  6. public:
  7.     bool isValid(string s) {
  8.         int len = s.length();
  9.         stack<char> stk;
  10.         for(int i = 0;i < len;++i){
  11.         	if(s[i] == '(')stk.push('(');
  12.         	else if(s[i] == '[')stk.push('[');
  13.         	else if(s[i] == '{')stk.push('{');
  14.         	else{
  15.         		if(stk.empty())return false;
  16.         		if(abs(s[i] - stk.top()) > 2)return false;
  17.         		stk.pop();
  18. 			}
  19. 		}
  20. 		return stk.empty();
  21.     }
  22. };

L0021 Merge Two Sorted Lists
First AC: 2019-09-01 Latest Modification: 2019-09-01
Note: 循环取较小,复杂度O(len(l1)+len(l2))

  1. class Solution {
  2. public:
  3.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  4.         ListNode* head = new ListNode(0);
  5.         ListNode* temp = head;
  6.         while(l1 != NULL && l2 != NULL){
  7.         	if(l1->val < l2->val){
  8.         		temp->next = l1;
  9.         		l1 = l1->next;
  10.         		temp = temp->next;
  11. 			}
  12. 			else{
  13. 				temp->next = l2;
  14. 				l2 = l2->next;
  15. 				temp = temp->next;
  16. 			}
  17. 		}
  18. 		if(l1 != NULL)temp->next = l1;
  19. 		else temp->next = l2;
  20. 		return head->next;
  21.     }
  22. };

L0022 Generate Parentheses
First AC: 2019-09-01 Latest Modification: 2019-09-01
Note: dfs,只遍历所有合法取法,复杂度O(n*C(2n,n))

  1. #include<vector>
  2. #include<iostream>
  3. using namespace std;
  4. class Solution {
  5. public:
  6. 	void dfs(vector<string> &v,int l,int r,int n,string s) {
  7. 		if(l + r == 2 * n){
  8. 			v.push_back(s);
  9. 			return;
  10. 		}
  11. 		if(l > r)dfs(v,l,r + 1,n,s + ')');
  12. 		if(l < n)dfs(v,l + 1,r,n,s + '(');
  13. 	}
  14.     vector<string> generateParenthesis(int n) {
  15.         vector<string>ret;
  16.         dfs(ret,0,0,n,"");
  17.         return ret;
  18.     }
  19. };

L0023 Merge k Sorted Lists
First AC: 2019-09-01 Latest Modification: 2019-09-01
Note: 循环取较小,复杂度O(k*sum(len(lists[i])))

  1. class Solution {
  2. public:
  3.     ListNode* mergeKLists(vector<ListNode*>& lists) {
  4.         ListNode* head = new ListNode(0);
  5.         ListNode* temp = head;
  6.         int len = lists.size();
  7.         int minv,index;
  8.         while(true){
  9.         	minv = 1e7;
  10.         	for(int i = 0;i < len;++i){
  11.         		if(lists[i] != NULL){
  12.         			if(lists[i]->val < minv){
  13.         				minv = lists[i]->val;
  14.         				index = i;
  15. 					}
  16. 				}
  17. 			}
  18. 			if(minv < 1e7){
  19. 				temp->next = lists[index];
  20. 				temp = temp->next;
  21. 				lists[index] = lists[index]->next;
  22. 			}
  23. 			else break;
  24. 		}
  25. 		return head->next;
  26.     }
  27. };

L0024 Swap Nodes in Pairs
First AC: 2019-09-01 Latest Modification: 2019-09-01
Note: 复杂度O(len(head))

  1. class Solution {
  2. public:
  3.     ListNode* swapPairs(ListNode* head) {
  4.         ListNode* ret = new ListNode(0);
  5.         ListNode* temp = ret;
  6.         ListNode* last = head;
  7.         while(true){
  8.         	ListNode* temp1 = last;
  9.         	if(temp1 == NULL){
  10.         		temp->next = NULL;
  11.         		break;
  12. 			}
  13.         	ListNode* temp2 = temp1->next;
  14.         	if(temp2 == NULL){
  15.         		temp->next = temp1;
  16.         		temp = temp->next;
  17.         		temp->next = NULL;
  18. 				break;
  19. 			}
  20. 			else{
  21. 				last = temp2->next;
  22. 				temp->next = temp2;
  23. 				temp = temp->next;
  24. 				temp->next = temp1;
  25. 				temp = temp->next;
  26. 			}
  27. 		}
  28. 		return ret->next;
  29.     }
  30. };

L0025 Reverse Nodes in k-Group
First AC: 2019-09-01 Latest Modification: 2019-09-01
Note: 复杂度O(len(head))

  1. class Solution {
  2. public:
  3.     ListNode* reverseKGroup(ListNode* head, int k) {
  4.         ListNode* ret = new ListNode(0);
  5.         ListNode* temp = ret;
  6.         ListNode* last = head;
  7.         while(true){
  8.         	if(last == NULL){
  9. 				temp->next = NULL;
  10. 				break;
  11. 			}
  12.         	ListNode* temps[k];
  13.         	bool flag = false;
  14.         	for(int i = 0;i < k;++i){
  15.         		temps[i] = last;
  16.         		if(temps[i] == NULL){
  17.         			flag = true;
  18.         			break;
  19. 				}
  20.         		last = last->next;
  21. 			}
  22. 			if(flag){
  23. 				temp->next = temps[0];
  24. 				for(int i = 1;i < k;++i){
  25. 					temps[i - 1]->next = temps[i];
  26. 					if(temps[i] == NULL)break;
  27. 				}
  28. 				break;
  29. 			}
  30. 			else{
  31. 				temp->next = temps[k - 1];
  32. 				for(int i = 1;i < k;++i){
  33. 					temps[i]->next = temps[i - 1];
  34. 				}
  35. 				temp = temps[0];
  36. 			}
  37. 		}
  38. 		return ret->next;
  39.     }
  40. };

L0026 Remove Duplicates from Sorted Array
First AC: 2019-09-01 Latest Modification: 2019-09-01
Note: 复杂度O(len(nums))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     int removeDuplicates(vector<int>& nums) {
  6.         int len = nums.size();
  7.         int ret = 1;
  8. 		for(int i = 1;i < len;++i){
  9. 			if(nums[i] != nums[i - 1]){
  10. 				nums[ret++] = nums[i];
  11. 			}
  12. 		}
  13. 		return min(ret,len);
  14.     }
  15. };

L0027 Remove Element
First AC: 2019-09-01 Latest Modification: 2019-09-01
Note: 复杂度O(len(nums))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     int removeElement(vector<int>& nums, int val) {
  6.         int len = nums.size();
  7.         if(len == 0)return 0;
  8.         int last = len - 1;
  9.         while(last >= 0 && nums[last] == val)--last;
  10.         int ret = 0;
  11.         for(int i = 0;i < len;++i){
  12.         	if(nums[i] != val)++ret;
  13.         	else if(i < last){
  14.         		nums[i] = nums[last--];
  15.         		while(last >= 0 && nums[last] == val)--last;
  16. 			}
  17. 		}
  18. 		return ret;
  19.     }
  20. };

L0028 Implement strStr()
First AC: 2019-09-01 Latest Modification: 2019-09-01
Note: 复杂度O(len(haystack)*len(needle))

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     int strStr(string haystack, string needle) {
  6.         int lenh = haystack.length();
  7.         int lenn = needle.length();
  8.         if(lenh < lenn)return -1;
  9. 		int maxi = lenh - lenn;
  10. 		for(int i = 0;i <= maxi;++i){
  11. 			bool flag = true;
  12. 			for(int j = 0;j < lenn;++j){
  13. 				if(haystack[i + j] != needle[j]){
  14. 					flag = false;
  15. 					break;
  16. 				}
  17. 			}
  18. 			if(flag)return i;
  19. 		}
  20. 		return -1;
  21.     }
  22. };

L0029 Divide Two Integers
First AC: 2019-09-02 Latest Modification: 2019-09-02
Note: 对商二进制表示,复杂度O(log(dividend/divisor))

  1. #include<cmath>
  2. typedef long long ll;
  3. class Solution {
  4. public:
  5. 	bool judge(int a,int b) {
  6. 		return (a < 0 && b > 0) || (a > 0 && b < 0);
  7. 	}
  8.     int divide(int dividend, int divisor) {
  9.     	if(dividend == -(1LL << 31) && divisor == -1)return (1LL << 31) - 1;
  10.     	if(divisor == 1)return dividend;
  11.     	if(divisor == -1)return -dividend;
  12. 		ll ans[64] = {1};
  13.         ll power[64] = {abs(ll(divisor))};
  14.         int index;
  15.         for(int i = 1;;++i){
  16.         	ans[i] = ans[i - 1] << 1;
  17.         	power[i] = power[i - 1] << 1;
  18.         	if(power[i] > abs(ll(dividend))){
  19.         		index = i - 1;
  20.         		break;
  21. 			}
  22. 		}
  23. 		ll ret = 0,temp = abs(ll(dividend));
  24. 		for(int i = index;i >= 0;--i){
  25. 			if(temp >= power[i]){
  26. 				temp -= power[i];
  27. 				ret += ans[i];
  28. 			}
  29. 		}
  30. 		return judge(dividend,divisor)? -abs(ret) : abs(ret);
  31.     }
  32. };

L0030 Substring with Concatenation of All Words
First AC: 2019-09-02 Latest Modification: 2019-09-02
Note: 计数去重哈希给定向量,预处理给定串的子串,复杂度O(len(s)*(len(s)+len(word))*log(len(word)))

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     vector<int> findSubstring(string s, vector<string>& words) {
  6.         int len = s.length();
  7.         int num = words.size();
  8.         vector<int> ret;
  9.         if(len * num == 0)return ret;
  10.         int cal[num] = {0};
  11.         map<string,int> hash;
  12.         map<string,int>::iterator it;
  13.         for(int i = 0;i < num;++i){
  14.         	it = hash.find(words[i]);
  15.         	if(it != hash.end())++cal[it->second];
  16.         	else cal[i] = 1,hash.insert(pair<string,int>(words[i],i));
  17. 		}
  18. 		int index[len];
  19. 		int temp = words[0].length();
  20. 		for(int i = 0;i < len;++i){
  21. 			it = hash.find(s.substr(i,temp));
  22. 			if(it == hash.end())index[i] = -1;
  23. 			else index[i] = it->second;
  24. 		}
  25. 		int cnt[num];
  26. 		int maxi = len - num * temp;
  27. 		for(int i = 0;i <= maxi;++i){
  28. 			int j = i;
  29. 			bool flag = true;
  30. 			memset(cnt,0,sizeof cnt);
  31. 			for(int k = 0;k < num;++k){
  32. 				if(index[j] == -1){
  33. 					flag = false;
  34. 					break;
  35. 				}
  36. 				++cnt[index[j]];
  37. 				j += temp;
  38. 			}
  39. 			if(flag){
  40. 				for(int k = 0;k < num;++k){
  41. 					if(cnt[k] != cal[k]){
  42. 						flag = false;
  43. 						break;
  44. 					}
  45. 				}
  46. 			}
  47. 			if(flag)ret.push_back(i);
  48. 		}
  49. 		return ret;
  50.     }
  51. };

L0031 Next Permutation
First AC: 2019-09-02 Latest Modification: 2019-09-02
Note: 最后用反转代替排序可以降低复杂度,但代码量更大,复杂度O((len(nums))^2*log(len(nums)))

  1. #include<vector>
  2. #include<algorithm>
  3. using namespace std;
  4. class Solution {
  5. public:
  6.     void nextPermutation(vector<int>& nums) {
  7.         int len = nums.size();
  8.         if(len < 2)return;
  9.         int index = -1;
  10.         for(int i = len - 2;i >= 0;--i){
  11.         	if(nums[i] < nums[i + 1]){
  12.         		index = i;
  13.         		break;
  14. 			}
  15. 		}
  16. 		if(index == -1){
  17. 			sort(nums.begin(),nums.end());
  18. 		}
  19. 		else{
  20. 			int pos;
  21. 			for(int i = len - 1;;--i){
  22. 				if(nums[i] > nums[index]){
  23. 					pos = i;
  24. 					break;
  25. 				}
  26. 			}
  27. 			int temp = nums[index];
  28. 			nums[index] = nums[pos];
  29. 			nums[pos] = temp;
  30. 			sort(nums.begin() + index + 1,nums.end());
  31. 		}
  32.     }
  33. };

L0032 Longest Valid Parentheses
First AC: 2019-09-02 Latest Modification: 2019-09-02
Note: 遍历起点,复杂度O((len(s))^2)

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     int longestValidParentheses(string s) {
  6.         int len = s.length();
  7.         int ret = 0;
  8.         for(int i = 0;i < len;++i){
  9.         	int temp = 0;
  10.         	for(int j = i;j < len;++j){
  11.         		if(s[j] == '(')++temp;
  12.         		else --temp;
  13.         		if(temp < 0)break;
  14.         		if(temp == 0)ret = max(ret,j - i + 1);
  15. 			}
  16. 		}
  17. 		return ret;
  18.     }
  19. };

L0033 Search in Rotated Sorted Array
First AC: 2019-09-02 Latest Modification: 2019-09-02
Note: 二分查找最小元位置,复杂度O(log(len(nums)))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5. 	int findMinValue(vector<int>& nums,int l,int r) {
  6. 		if(l + 1 == r)return r;
  7. 		int mid = (l + r) / 2;
  8. 		if(nums[mid] > nums[r])return findMinValue(nums,mid,r);
  9. 		else return findMinValue(nums,l,mid);
  10. 	}
  11. 	int findExactValue(vector<int>& nums,int l,int r,int target) {
  12. 		if(r - l < 5){
  13. 			for(int i = l;i <= r;++i)if(nums[i] == target)return i;
  14. 			return -1;
  15. 		}
  16. 		int mid = (l + r) / 2;
  17. 		if(nums[mid] == target)return mid;
  18. 		else if(nums[mid] < target)return findExactValue(nums,mid + 1,r,target);
  19. 		else return findExactValue(nums,l,mid - 1,target);
  20. 	}
  21.     int search(vector<int>& nums, int target) {
  22.     	int maxIndex = nums.size() - 1;
  23.         if(maxIndex > 0 && nums[0] > nums[maxIndex]){
  24.         	int pos = findMinValue(nums,0,maxIndex);
  25.         	if(nums[maxIndex] == target)return maxIndex;
  26.         	else if(nums[maxIndex] > target)return findExactValue(nums,pos,maxIndex,target);
  27.         	else return findExactValue(nums,0,pos - 1,target);
  28. 		}
  29. 		else return findExactValue(nums,0,nums.size() - 1,target);
  30.     }
  31. };

L0034 Find First and Last Position of Element in Sorted Array
First AC: 2019-09-02 Latest Modification: 2019-09-02
Note: 二分查找,复杂度O(log(len(nums)))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5. 	bool findExact(vector<int>& nums,int target,int l,int r) {
  6. 		if(r - l < 5){
  7. 			for(int i = l;i <= r;++i){
  8. 				if(nums[i] == target)return true;
  9. 			}
  10. 			return false;
  11. 		}
  12. 		int mid = (l + r) / 2;
  13. 		if(nums[mid] == target)return true;
  14. 		if(nums[mid] < target)return findExact(nums,target,mid + 1,r);
  15. 		else return findExact(nums,target,l,mid - 1);
  16. 	}
  17. 	int findLeft(vector<int>& nums,int target,int l,int r) {
  18. 		if(r - l < 5){
  19. 			for(int i = l;i <= r;++i){
  20. 				if(nums[i] == target)return i;
  21. 			}
  22. 		}
  23. 		int mid = (l + r) / 2;
  24. 		if(nums[mid] < target)return findLeft(nums,target,mid + 1,r);
  25. 		else return findLeft(nums,target,l,mid);
  26. 	}
  27. 	int findRight(vector<int>& nums,int target,int l,int r) {
  28. 		if(r - l < 5){
  29. 			for(int i = r;i >= l;--i){
  30. 				if(nums[i] == target)return i;
  31. 			}
  32. 		}
  33. 		int mid = (l + r) / 2;
  34. 		if(nums[mid] > target)return findRight(nums,target,l,mid - 1);
  35. 		else return findRight(nums,target,mid,r);
  36. 	}
  37.     vector<int> searchRange(vector<int>& nums, int target) {
  38.         int len = nums.size();
  39. 		int ans[2];
  40.         if(findExact(nums,target,0,len - 1)){
  41.         	ans[0] = findLeft(nums,target,0,len - 1);
  42.         	ans[1] = findRight(nums,target,0,len - 1);
  43. 		}
  44. 		else{
  45. 			ans[0] = ans[1] = -1;
  46. 		}
  47. 		vector<int> ret(ans,ans + 2);
  48. 		return ret;
  49.     }
  50. };

L0035 Search Insert Position
First AC: 2019-09-02 Latest Modification: 2019-09-02
Note: 二分查找,复杂度O(log(len(nums)))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5. 	int findExact(vector<int>& nums,int target,int l,int r) {
  6. 		if(r - l < 5){
  7. 			for(int i = l;i <= r;++i){
  8. 				if(nums[i] == target)return i;
  9. 			}
  10. 			return -1;
  11. 		}
  12. 		int mid = (l + r) / 2;
  13. 		if(nums[mid] == target)return mid;
  14. 		if(nums[mid] < target)return findExact(nums,target,mid + 1,r);
  15. 		else return findExact(nums,target,l,mid - 1);
  16. 	}
  17. 	int findLeft(vector<int>& nums,int target,int l,int r) {
  18. 		if(r - l < 5){
  19. 			for(int i = l;i <= r;++i){
  20. 				if(nums[i] > target)return i;
  21. 			}
  22. 		}
  23. 		int mid = (l + r) / 2;
  24. 		if(nums[mid] < target)return findLeft(nums,target,mid,r);
  25. 		else return findLeft(nums,target,l,mid);
  26. 	}
  27.     int searchInsert(vector<int>& nums, int target) {
  28.         int len = nums.size();
  29.         int pos = findExact(nums,target,0,len - 1);
  30.         if(pos != -1)return pos;
  31.         if(len == 0)return len;
  32.         if(nums[0] > target)return 0;
  33.         if(nums[len - 1] < target)return len;
  34.         return findLeft(nums,target,0,len - 1);
  35.     }
  36. };

L0036 Valid Sudoku
First AC: 2019-09-03 Latest Modification: 2019-09-03
Note: 复杂度O(1)

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     bool isValidSudoku(vector< vector<char> >& board) {
  6.         bool row[9][9] = {0};
  7.         bool column[9][9] = {0};
  8.         bool box[9][9] = {0};
  9.         for(int i = 0;i < 9;++i){
  10.         	for(int j = 0;j < 9;++j){
  11.         		char ch = board[i][j];
  12.         		if(ch == '.')continue;
  13.         		int temp = ch - '1';
  14.         		int r = i,c = j,b = i / 3 * 3 + j / 3;
  15.         		if(row[r][temp] || column[c][temp] || box[b][temp]){
  16.         			return false;
  17. 				}
  18. 				row[r][temp] = column[c][temp] = box[b][temp] = true;
  19. 			}
  20. 		}
  21. 		return true;
  22.     }
  23. };

L0037 Sudoku Solver
First AC: 2019-09-03 Latest Modification: 2019-09-03
Note: dfs,完全类似八皇后问题

  1. #include<vector>
  2. #include<iostream>
  3. using namespace std;
  4. class Solution {
  5. public:
  6. 	bool row[9][9];
  7.     bool column[9][9];
  8.     bool box[9][9];
  9. 	bool dfs(vector< vector<char> >& board,int n) {
  10. 		int r = n / 9,c = n % 9,b = r / 3 * 3 + c / 3;
  11. 		if(n == 81)return true;
  12. 		if(board[r][c] != '.'){
  13. 			int temp = board[r][c] - '1';
  14. 			return dfs(board,n + 1);
  15. 		}
  16. 		for(int i = 0;i < 9;++i){
  17. 			if(row[r][i] || column[c][i] || box[b][i])continue;
  18. 			board[r][c] = char('1' + i);
  19. 			row[r][i] = column[c][i] = box[b][i] = true;
  20. 			if(dfs(board,n + 1))return true;
  21. 			board[r][c] = '.';
  22. 			row[r][i] = column[c][i] = box[b][i] = false;
  23. 		}
  24. 		return false;
  25. 	}
  26.     void solveSudoku(vector< vector<char> >& board) {
  27.         for(int i = 0;i < 9;++i){
  28.         	for(int j = 0;j < 9;++j){
  29.         		char ch = board[i][j];
  30.         		if(ch == '.')continue;
  31.         		int temp = ch - '1';
  32.         		int r = i,c = j,b = i / 3 * 3 + j / 3;
  33. 				row[r][temp] = column[c][temp] = box[b][temp] = true;
  34. 			}
  35. 		}
  36. 		dfs(board,0);
  37.     }
  38. };

L0038 Count and Say
First AC: 2019-09-03 Latest Modification: 2019-09-03
Note: 复杂度O(n*max(len(s[i])))

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     string countAndSay(int n) {
  6.         string s[30] = {"1"};
  7.         for(int i = 1;i < n;++i){
  8.         	int len = s[i - 1].length();
  9.         	int count = 1;
  10.         	for(int j = 1;j < len;++j){
  11.         		if(s[i - 1][j] != s[i - 1][j - 1]){
  12.         			s[i] += char(count + '0');
  13. 					s[i] += s[i - 1][j - 1];
  14.         			count = 1;
  15. 				}
  16. 				else{
  17. 					++count;
  18. 				}
  19. 			}
  20. 			if(count){
  21. 				s[i] += char(count + '0');
  22. 				s[i] += s[i - 1][len - 1];
  23. 			}
  24. 		}
  25. 		return s[n - 1];
  26.     }
  27. };

L0039 Combination Sum
First AC: 2019-09-03 Latest Modification: 2019-09-03
Note: dfs

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5. 	void dfs(vector< vector<int> >& ret,vector<int>& candidates,vector<int>& ans,int now,int index) {
  6. 		if(index < 0)return;
  7. 		if(candidates[index] == now){
  8. 			ans.push_back(now);
  9. 			ret.push_back(ans);
  10. 			ans.erase(ans.end() - 1);
  11. 			dfs(ret,candidates,ans,now,index - 1);
  12. 		}
  13. 		else if(candidates[index] < now){
  14. 			ans.push_back(candidates[index]);
  15. 			dfs(ret,candidates,ans,now - candidates[index],index);
  16. 			ans.erase(ans.end() - 1);
  17. 			dfs(ret,candidates,ans,now,index - 1);
  18. 		}
  19. 		else{
  20. 			dfs(ret,candidates,ans,now,index - 1);
  21. 		}
  22. 	}
  23.     vector< vector<int> > combinationSum(vector<int>& candidates, int target) {
  24.         vector< vector<int> > ret;
  25.         vector<int> v;
  26.         dfs(ret,candidates,v,target,candidates.size() - 1);
  27.         return ret;
  28.     }
  29. };

L0040 Combination Sum II
First AC: 2019-09-03 Latest Modification: 2019-09-03
Note: dfs

  1. #include<vector>
  2. #include<algorithm>
  3. using namespace std;
  4. class Solution {
  5. public:
  6. 	void dfs(vector< vector<int> >& ret,vector<int>& candidates,vector<int>& ans,int now,int index) {
  7. 		if(index < 0)return;
  8. 		if(candidates[index] == now){
  9. 			ans.push_back(now);
  10. 			if(find(ret.begin(),ret.end(),ans) == ret.end())ret.push_back(ans);
  11. 			ans.erase(ans.end() - 1);
  12. 			dfs(ret,candidates,ans,now,index - 1);
  13. 		}
  14. 		else if(candidates[index] < now){
  15. 			ans.push_back(candidates[index]);
  16. 			dfs(ret,candidates,ans,now - candidates[index],index - 1);
  17. 			ans.erase(ans.end() - 1);
  18. 			dfs(ret,candidates,ans,now,index - 1);
  19. 		}
  20. 		else{
  21. 			dfs(ret,candidates,ans,now,index - 1);
  22. 		}
  23. 	}
  24.     vector< vector<int> > combinationSum2(vector<int>& candidates, int target) {
  25.     	sort(candidates.begin(),candidates.end());
  26.         vector< vector<int> > ret;
  27.         vector<int> v;
  28.         dfs(ret,candidates,v,target,candidates.size() - 1);
  29.         return ret;
  30.     }
  31. };

L0041 First Missing Positive
First AC: 2019-09-03 Latest Modification: 2019-09-03
Note: first[],last[]保存每个数所在连续正整数的左右端点,复杂度O(len(nums))

  1. #include<vector>
  2. #include<cstring>
  3. using namespace std;
  4. class Solution {
  5. public:
  6.     int firstMissingPositive(vector<int>& nums) {
  7.         int len = nums.size();
  8.         int first[len + 2];
  9.         int last[len + 2];
  10.         memset(first,-1,sizeof first);
  11.         memset(last,-1,sizeof last);
  12.         for(int i = 0;i < len;++i){
  13.         	int temp = nums[i];
  14.         	if(temp <= 0 || temp > len || first[temp] != -1)continue;
  15. 			if(first[temp - 1] == -1){
  16. 				last[temp - 1] = temp;
  17. 				first[temp] = temp - 1;
  18. 			}
  19. 			else{
  20. 				last[first[temp - 1]] = temp;
  21. 				first[temp] = first[temp - 1];
  22. 			}
  23. 		}
  24. 		int ret = 0;
  25. 		while(last[ret] != -1)ret =last[ret];
  26. 		return ret + 1;
  27.     }
  28. };

L0042 Trapping Rain Water
First AC: 2019-09-03 Latest Modification: 2019-09-03
Note: 找到最高的墙,然后两边靠近,复杂度O(len(height))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     int trap(vector<int>& height) {
  6.         int len = height.size();
  7.         int maxValue = 0,index = 0;
  8.         for(int i = 0;i < len;++i){
  9.         	if(height[i] > maxValue){
  10.         		index = i;
  11.         		maxValue = height[i];
  12. 			}
  13. 		}
  14. 		int ret = 0,maxLeft = 0,maxRight = 0;
  15. 		for(int i = 0;i < index;++i){
  16. 			if(height[i] > maxLeft)maxLeft = height[i];
  17. 			else ret += maxLeft - height[i];
  18. 		}
  19. 		for(int i = len - 1;i > index;--i){
  20. 			if(height[i] > maxRight)maxRight = height[i];
  21. 			else ret += maxRight - height[i];
  22. 		}
  23. 		return ret;
  24.     }
  25. };

L0043 Multiply Strings
First AC: 2019-09-04 Latest Modification: 2019-09-04
Note: 复杂度O(len(num1)*len(num2))

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     string multiply(string num1, string num2) {
  6.     	if(num1 == "0" || num2 == "0")return "0";
  7.         int len1 = num1.length(),len2 = num2.length();
  8.         int len3 = len1 + len2 - 2;
  9.         int ans[len3 + 5] = {0};
  10.         for(int i = 0;i < len1;++i){
  11.         	for(int j = 0;j < len2;++j){
  12.         		ans[len3 - i - j] += (num1[i] - '0') * (num2[j] - '0');
  13. 			}
  14. 		}
  15. 		int flag = 0,temp = 0;
  16. 		for(int i = 0;i < len3 + 5;++i){
  17. 			temp = ans[i] + flag;
  18. 			flag = temp / 10;
  19. 			ans[i] = temp % 10;
  20. 		}
  21. 		int index;
  22. 		for(int i = len3 + 4;;--i){
  23. 			if(ans[i] != 0){
  24. 				index = i;
  25. 				break;
  26. 			}
  27. 		}
  28. 		string ret = "";
  29. 		for(int i = index;i >= 0;--i){
  30. 			ret += char(ans[i] + '0');
  31. 		}
  32. 		return ret;
  33.     }
  34. };

L0044 Wildcard Matching
First AC: 2019-09-05 Latest Modification: 2019-09-05
Note: dp,复杂度O(len(s)*len(p))

  1. #include<cstring>
  2. #include<iostream>
  3. using namespace std;
  4. class Solution {
  5. public:
  6.     bool isMatch(string s, string p) {
  7.     	s = " " + s;
  8.     	p = " " + p;
  9.         int lens = s.length();
  10. 		int lenp = p.length();
  11. 		bool dp[lenp][lens];
  12. 		memset(dp,false,sizeof dp);
  13. 		dp[0][0] = true;
  14. 		int minTrue[lenp];
  15. 		memset(minTrue,0x3f,sizeof minTrue);
  16. 		minTrue[0] = 0;
  17. 		bool hasCharacter = false;
  18. 		if(lens == 1){
  19. 			for(int i = 1;i < lenp;++i){
  20. 				if(p[i] != '*'){
  21. 					hasCharacter = true;
  22. 					break;
  23. 				}
  24. 			}
  25. 			return !hasCharacter;
  26. 		}
  27. 		for(int i = 1;i < lenp;++i){
  28. 			bool flag = true;
  29. 			for(int j = 1;j < lens;++j){
  30. 				if(p[i] == '?'){
  31. 					hasCharacter = true;
  32. 					dp[i][j] = dp[i - 1][j - 1];
  33. 				}
  34. 				else if(p[i] == '*'){
  35. 					if(!hasCharacter){
  36. 						dp[i][0] = true;
  37. 					}
  38. 					if(minTrue[i - 1] <= j)dp[i][j] = true;
  39. 				}
  40. 				else{
  41. 					hasCharacter = true;
  42. 					if(p[i] != s[j])dp[i][j] = 0;
  43. 					else dp[i][j] = dp[i - 1][j - 1];
  44. 				}
  45. 				if(flag && dp[i][j] == true){
  46. 					flag = false;
  47. 					minTrue[i] = j;
  48. 				}
  49. 			}
  50. 		}
  51. 		return dp[lenp - 1][lens - 1];
  52.     }
  53. };

L0045 Jump Game II
First AC: 2019-09-07 Latest Modification: 2019-09-07
Note: 记录最远可达距离,复杂度O(len(nums))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     int jump(vector<int>& nums) {
  6.         int len = nums.size() - 1;
  7.         int now = 0,right = 0;
  8.         int ret = 0;
  9.         while(right < len){
  10.         	int temp = now;
  11.         	for(int i = now;i <= right;++i){
  12.         		temp = max(temp,i + nums[i]);
  13. 			}
  14. 			now = right;
  15. 			right = temp;
  16. 			++ret;
  17. 		}
  18. 		return ret;
  19.     }
  20. };

L0046 Permutations
First AC: 2019-09-07 Latest Modification: 2019-09-07
Note: 参考L0031,复杂度O(len(nums)!*(len(nums))^2*log(len(nums)))

  1. #include<vector>
  2. #include<algorithm>
  3. using namespace std;
  4. class Solution {
  5. public:
  6. 	bool nextPermutation(vector<int>& nums) {
  7.         int len = nums.size();
  8.         if(len < 2)return false;
  9.         int index = -1;
  10.         for(int i = len - 2;i >= 0;--i){
  11.         	if(nums[i] < nums[i + 1]){
  12.         		index = i;
  13.         		break;
  14. 			}
  15. 		}
  16. 		if(index == -1){
  17. 			return false;
  18. 		}
  19. 		else{
  20. 			int pos;
  21. 			for(int i = len - 1;;--i){
  22. 				if(nums[i] > nums[index]){
  23. 					pos = i;
  24. 					break;
  25. 				}
  26. 			}
  27. 			int temp = nums[index];
  28. 			nums[index] = nums[pos];
  29. 			nums[pos] = temp;
  30. 			sort(nums.begin() + index + 1,nums.end());
  31. 			return true;
  32. 		}
  33.     }
  34.     vector< vector<int> > permute(vector<int>& nums) {
  35.         sort(nums.begin(),nums.end());
  36.         vector< vector<int> > ret;
  37.         do{
  38.         	ret.push_back(nums);
  39. 		}while(nextPermutation(nums));
  40. 		return ret;
  41.     }
  42. };

L0047 Permutations II
First AC: 2019-09-07 Latest Modification: 2019-09-07
Note: 参考L0046,复杂度O(len(nums)!*(len(nums))^2*log(len(nums)))

  1. #include<vector>
  2. #include<algorithm>
  3. using namespace std;
  4. class Solution {
  5. public:
  6. 	bool nextPermutation(vector<int>& nums) {
  7.         int len = nums.size();
  8.         if(len < 2)return false;
  9.         int index = -1;
  10.         for(int i = len - 2;i >= 0;--i){
  11.         	if(nums[i] < nums[i + 1]){
  12.         		index = i;
  13.         		break;
  14. 			}
  15. 		}
  16. 		if(index == -1){
  17. 			return false;
  18. 		}
  19. 		else{
  20. 			int pos;
  21. 			for(int i = len - 1;;--i){
  22. 				if(nums[i] > nums[index]){
  23. 					pos = i;
  24. 					break;
  25. 				}
  26. 			}
  27. 			int temp = nums[index];
  28. 			nums[index] = nums[pos];
  29. 			nums[pos] = temp;
  30. 			sort(nums.begin() + index + 1,nums.end());
  31. 			return true;
  32. 		}
  33.     }
  34.     vector< vector<int> > permuteUnique(vector<int>& nums) {
  35.         sort(nums.begin(),nums.end());
  36.         vector< vector<int> > ret;
  37.         vector<int> temp;
  38.         do{
  39.         	if(nums != temp){
  40.         		ret.push_back(nums);
  41. 			}
  42. 		}while(nextPermutation(nums));
  43. 		return ret;
  44.     }
  45. };

L0048 Rotate Image
First AC: 2019-09-07 Latest Modification: 2019-09-07
Note: 复杂度O(len^2(nums))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     void rotate(vector< vector<int> >& matrix) {
  6.         int len = matrix.size();
  7.         vector< vector<int> > ret;
  8.         for(int i = 0;i < len;++i){
  9.         	vector<int> temp;
  10.         	for(int j = len - 1;j >= 0;--j){
  11.         		temp.push_back(matrix[j][i]);
  12. 			}
  13. 			ret.push_back(temp);
  14. 		}
  15. 		matrix = ret;
  16.     }
  17. };

L0049 Group Anagrams
First AC: 2019-09-07 Latest Modification: 2019-09-07
Note: 维护字符串到答案下标的映射,复杂度O(len(strs)*len(strs[i])*log(len(strs))

  1. #include<map>
  2. #include<vector>
  3. #include<iostream>
  4. using namespace std;
  5. class Solution {
  6. public:
  7. 	string change(string s) {
  8. 		int num[26] = {0};
  9. 		int len = s.length();
  10. 		for(int i = 0;i < len;++i)++num[s[i] - 'a'];
  11. 		string ret = "";
  12. 		for(int i = 0;i < 26;++i){
  13. 			while(num[i]--)ret += char(i + 'a');
  14. 		}
  15. 		return ret;
  16. 	}
  17.     vector< vector<string> > groupAnagrams(vector<string>& strs) {
  18.         vector< vector<string> > ret;
  19.         map<string,int> mp;
  20.         map<string,int>::iterator it;
  21.         int len = strs.size();
  22.         for(int i = 0;i < len;++i){
  23.         	string temp = change(strs[i]);
  24.         	it = mp.find(temp);
  25.         	if(it != mp.end()){
  26.         		ret[it->second].push_back(strs[i]);
  27. 			}
  28.         	else{
  29.         		vector<string> v;
  30.         		v.push_back(strs[i]);
  31.         		ret.push_back(v);
  32.         		mp.insert(pair<string,int>(temp,ret.size() - 1));
  33. 			}
  34. 		}
  35.         return ret;
  36.     }
  37. };

L0050 Pow(x, n)
First AC: 2019-09-07 Latest Modification: 2019-09-07
Note: 快速幂,复杂度O(log(n))

  1. class Solution {
  2. public:
  3. 	double qPow(double x,int n) {
  4. 		double ret = 1,temp = x;
  5. 		while(n){
  6. 			if(n % 2){
  7. 				ret *= temp;
  8. 			}
  9. 			temp *= temp;
  10. 			n /= 2;
  11. 		}
  12. 		return ret;
  13. 	}
  14.     double myPow(double x, int n) {
  15.         if(n > 0)return qPow(x,n);
  16.         else if(n == 0)return 1;
  17.         else return 1 / qPow(x,n);
  18.     }
  19. };

L0051 N-Queens
First AC: 2019-09-12 Latest Modification: 2019-09-12
Note: dfs

  1. #include<vector>
  2. #include<cstring>
  3. #include<iostream>
  4. using namespace std;
  5. class Solution {
  6. public:
  7. 	int std_n;
  8. 	int std_num;
  9. 	char mp[20][20];
  10. 	bool r[20],c[20],s[40],m[40];
  11. 	vector< vector<string> > ret;
  12. 	void insert() {
  13. 		vector<string> v;
  14. 		string s;
  15. 		for(int i = 0;i < std_n;++i){
  16. 			s = "";
  17. 			for(int j = 0;j < std_n;++j){
  18. 				s += mp[i][j];
  19. 			}
  20. 			v.push_back(s);
  21. 		}
  22. 		ret.push_back(v);
  23. 	}
  24. 	bool dfs(int n,int num) {
  25. 		if(num > std_num)return false;
  26. 		if(n == std_n){
  27. 			insert();
  28. 			return true;
  29. 		}
  30. 		int my_r = num / std_n;
  31. 		int my_c = num % std_n;
  32. 		int my_s = my_r + my_c;
  33. 		int my_m = my_r - my_c + std_n;
  34. 		dfs(n,num + 1);
  35. 		if(r[my_r] || c[my_c] || s[my_s] || m[my_m])return false;
  36. 		mp[my_r][my_c] = 'Q';
  37. 		r[my_r] = c[my_c] = s[my_s] = m[my_m] = true;
  38. 		dfs(n + 1,num + 1);
  39. 		mp[my_r][my_c] = '.';
  40. 		r[my_r] = c[my_c] = s[my_s] = m[my_m] = false;
  41. 		return true;
  42. 	}
  43.     vector< vector<string> > solveNQueens(int n) {
  44.     	std_n = n;
  45.     	std_num = n * n;
  46.     	memset(mp,'.',sizeof mp);
  47.     	memset(r,false,sizeof r);
  48.     	memset(c,false,sizeof c);
  49.     	memset(s,false,sizeof s);
  50.     	memset(m,false,sizeof m);
  51.     	dfs(0,0);
  52.         return ret;
  53.     }
  54. };

L0052 N-Queens II
First AC: 2019-09-12 Latest Modification: 2019-09-12
Note: dfs

  1. #include<cstring>
  2. class Solution {
  3. public:
  4. 	int std_n;
  5. 	int std_num;
  6. 	char mp[20][20];
  7. 	bool r[20],c[20],s[40],m[40];
  8. 	int ret;
  9. 	bool dfs(int n,int num) {
  10. 		if(num > std_num)return false;
  11. 		if(n == std_n){
  12. 			++ret;
  13. 			return true;
  14. 		}
  15. 		int my_r = num / std_n;
  16. 		int my_c = num % std_n;
  17. 		int my_s = my_r + my_c;
  18. 		int my_m = my_r - my_c + std_n;
  19. 		dfs(n,num + 1);
  20. 		if(r[my_r] || c[my_c] || s[my_s] || m[my_m])return false;
  21. 		mp[my_r][my_c] = 'Q';
  22. 		r[my_r] = c[my_c] = s[my_s] = m[my_m] = true;
  23. 		dfs(n + 1,num + 1);
  24. 		mp[my_r][my_c] = '.';
  25. 		r[my_r] = c[my_c] = s[my_s] = m[my_m] = false;
  26. 		return true;
  27. 	}
  28.     int totalNQueens(int n) {
  29.     	std_n = n;
  30.     	std_num = n * n;
  31.     	memset(mp,'.',sizeof mp);
  32.     	memset(r,false,sizeof r);
  33.     	memset(c,false,sizeof c);
  34.     	memset(s,false,sizeof s);
  35.     	memset(m,false,sizeof m);
  36.     	dfs(0,0);
  37.         return ret;
  38.     }
  39. };

L0053 Maximum Subarray
First AC: 2019-09-12 Latest Modification: 2019-09-12
Note: 维护最小和,复杂度O(n)

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     int maxSubArray(vector<int>& nums) {
  6.         int len = nums.size();
  7.         int minSum = 0;
  8.         int nowSum = 0;
  9.         int ret = -(1LL << 32 - 1);
  10.         for(int i = 0;i < len;++i){
  11.         	nowSum += nums[i];
  12.         	ret = max(ret,nowSum - min(minSum,0));
  13.         	minSum = min(minSum,nowSum);
  14. 		}
  15. 		return ret;
  16.     }
  17. };

L0054 Spiral Matrix
First AC: 2019-09-12 Latest Modification: 2019-09-12
Note: 直接遍历,复杂度O(len(matrix))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     vector<int> spiralOrder(vector< vector<int> >& matrix) {
  6.         vector<int> ret;
  7.         int row = matrix.size();
  8.         if(row == 0)return ret;
  9.         int column = matrix[0].size();
  10.         int num = row * column;
  11.         bool flag[row * column] = {true};
  12.         int now = 0;
  13.         ret.push_back(matrix[0][0]);
  14.         while(true){
  15.         	bool judge = true;
  16.         	while(now % column + 1 < column && !flag[now + 1]){
  17.         		++now;
  18.         		ret.push_back(matrix[now / column][now % column]);
  19.         		flag[now] = true;
  20.         		judge = false;
  21. 			}
  22. 			while(now / column + 1 < row && !flag[now + column]){
  23.         		now += column;
  24.         		ret.push_back(matrix[now / column][now % column]);
  25.         		flag[now] = true;
  26.         		judge = false;
  27. 			}
  28. 			while(now % column > 0 && !flag[now - 1]){
  29.         		--now;
  30.         		ret.push_back(matrix[now / column][now % column]);
  31.         		flag[now] = true;
  32.         		judge = false;
  33. 			}
  34. 			while(now / column > 0 && !flag[now - column]){
  35.         		now -= column;
  36.         		ret.push_back(matrix[now / column][now % column]);
  37.         		flag[now] = true;
  38.         		judge = false;
  39. 			}
  40. 			if(judge)break;
  41. 		}
  42. 		return ret;
  43.     }
  44. };

L0055 Jump Game
First AC: 2019-09-12 Latest Modification: 2019-09-12
Note: 复杂度O(len(nums))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     bool canJump(vector<int>& nums) {
  6.         int len = nums.size() - 1;
  7.         int maxLength = min(len,nums[0]);
  8.         int nowPosition = 0;
  9.         while(nowPosition <= maxLength){
  10.         	int temp = maxLength;
  11.         	maxLength = min(len,max(maxLength,nowPosition + nums[nowPosition]));
  12.         	if(maxLength == temp && nowPosition == maxLength)break;
  13.         	nowPosition = min(nowPosition + 1,maxLength);
  14. 		}
  15.         return nowPosition == len;
  16.     }
  17. };

L0056 Merge Intervals
First AC: 2019-09-12 Latest Modification: 2019-09-12
Note: 复杂度O(len(intervals)*log(len(intervals)))

  1. #include<vector>
  2. #include<algorithm>
  3. using namespace std;
  4. class Data {
  5. public:
  6. 	int left,right;
  7. 	friend bool operator < (const Data& x,const Data& y) {
  8. 		return x.left < y.left;
  9. 	}
  10. };
  11. class Solution {
  12. public:
  13.     vector< vector<int> > merge(vector< vector<int> >& intervals) {
  14.     	vector< vector<int> > ret;
  15.         int len = intervals.size();
  16. 		if(len == 0)return ret;
  17. 		Data d[len];
  18. 		for(int i = 0;i < len;++i){
  19. 			d[i].left = intervals[i][0];
  20. 			d[i].right = intervals[i][1];
  21. 		}
  22. 		sort(d,d + len);
  23. 		int a[2] = {d[0].left,d[0].right};
  24. 		for(int i = 1;i < len;++i){
  25. 			if(d[i].left <= a[1]){
  26. 				a[1] = max(a[1],d[i].right);
  27. 			}
  28. 			else{
  29. 				ret.push_back(vector<int>(a,a+2));
  30. 				a[0] = d[i].left;
  31. 				a[1] = d[i].right;
  32. 			}
  33. 		}
  34. 		ret.push_back(vector<int>(a,a+2));
  35. 		return ret;
  36.     }
  37. };

L0057 Insert Interval
First AC: 2019-09-13 Latest Modification: 2019-09-13
Note: 复杂度O(len(intervals))

  1. #include<vector>
  2. using namespace std;
  3. class Data {
  4. public:
  5. 	int left,right;
  6. };
  7. class Solution {
  8. public:
  9.     vector< vector<int> > insert(vector< vector<int> >& intervals, vector<int>& newInterval) {
  10.     	vector< vector<int> > ret;
  11.         int len = intervals.size();
  12.         if(len == 0){
  13.         	ret.push_back(newInterval);
  14.         	return ret;
  15. 		}
  16. 		Data d[len + 1];
  17. 		d[0].left = newInterval[0];
  18. 		d[0].right = newInterval[1];
  19. 		d[len].left = newInterval[0];
  20. 		d[len].right = newInterval[1];
  21. 		for(int i = 0;i < len;++i){
  22. 			if(intervals[i][0] > newInterval[0]){
  23. 				d[i].left = newInterval[0];
  24. 				d[i].right = newInterval[1];
  25. 				for(int j = i;j < len;++j){
  26. 					d[j + 1].left = intervals[j][0];
  27. 					d[j + 1].right = intervals[j][1];
  28. 				}
  29. 				break;
  30. 			}
  31. 			d[i].left = intervals[i][0];
  32. 			d[i].right = intervals[i][1];
  33. 		}
  34. 		int a[2] = {d[0].left,d[0].right};
  35. 		for(int i = 1;i <= len;++i){
  36. 			if(d[i].left <= a[1]){
  37. 				a[1] = max(a[1],d[i].right);
  38. 			}
  39. 			else{
  40. 				ret.push_back(vector<int>(a,a+2));
  41. 				a[0] = d[i].left;
  42. 				a[1] = d[i].right;
  43. 			}
  44. 		}
  45. 		ret.push_back(vector<int>(a,a+2));
  46. 		return ret;
  47.     }
  48. };

L0058 Length of Last Word
First AC: 2019-09-13 Latest Modification: 2019-09-13
Note: 复杂度O(len(s))

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     int lengthOfLastWord(string s) {
  6.         int len = s.length();
  7.         int left = -1,right = -1;
  8.         for(int i = len - 1;i >= 0;--i){
  9.         	if(s[i] != ' '){
  10.         		right = i;
  11.         		for(int j = i - 1;j >= 0;--j){
  12.         			if(s[j] == ' '){
  13.         				left = j;
  14.         				break;
  15. 					}
  16. 				}
  17. 				break;
  18. 			}
  19. 		}
  20. 		if(right == -1)return 0;
  21. 		return right - left;
  22.     }
  23. };

L0059 Spiral Matrix II
First AC: 2019-09-13 Latest Modification: 2019-09-13
Note: 复杂度O(n^2)

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     vector< vector<int> > generateMatrix(int n) {
  6.         vector< vector<int> > ret(n,vector<int>(n));
  7.         int cnt = 1,num = n * n;
  8.         int row = 0,column = 0;
  9.         int min_row = 1,max_row = n - 1;
  10.         int min_column = 0,max_column = n - 1;
  11.         ret[0][0] = 1;
  12.         while(cnt < num){
  13.         	while(column < max_column){
  14.         		ret[row][++column] = ++cnt;
  15. 			}
  16. 			--max_column;
  17. 			while(row < max_row){
  18. 				ret[++row][column] = ++cnt;
  19. 			}
  20. 			--max_row;
  21. 			while(column > min_column){
  22. 				ret[row][--column] = ++cnt;
  23. 			}
  24. 			++min_column;
  25. 			while(row > min_row){
  26. 				ret[--row][column] = ++cnt;
  27. 			}
  28. 			++min_row;
  29. 		}
  30. 		return ret;
  31.     }
  32. };

L0060 Permutation Sequence
First AC: 2019-09-13 Latest Modification: 2019-09-13
Note: 用L0031的做法能降低复杂度,复杂度O(n!*log(n!))

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. class Solution {
  5. public:
  6. 	int std_n;
  7. 	int a[500000];
  8. 	int cnt = 0;
  9. 	int num[10];
  10. 	bool used[10] = {false};
  11. 	int get() {
  12. 		int ret = 0;
  13. 		for(int i = 0;i < std_n;++i){
  14. 			ret = ret * 10 + num[i];
  15. 		}
  16. 		return ret;
  17. 	}
  18. 	void dfs(int pos) {
  19. 		if(pos == std_n){
  20. 			a[cnt++] = get();
  21. 			return;
  22. 		}
  23. 		for(int i = 1;i <= std_n;++i){
  24. 			if(!used[i]){
  25. 				num[pos] = i;
  26. 				used[i] = true;
  27. 				dfs(pos + 1);
  28. 				used[i] = false;
  29. 			}
  30. 		}
  31. 	}
  32. 	string intToString(int n) {
  33. 		char ch[10];
  34. 		int pos = 0;
  35. 		while(n){
  36. 			ch[pos++] = char(n % 10 + '0');
  37. 			n /= 10;
  38. 		}
  39. 		string ret = "";
  40. 		while(pos--)ret += ch[pos];
  41. 		return ret;
  42. 	}
  43.     string getPermutation(int n, int k) {
  44.     	std_n = n;
  45.     	dfs(0);
  46.     	sort(a,a+cnt);
  47.     	return intToString(a[--k]);
  48.     }
  49. };

L0061 Rotate List
First AC: 2019-09-13 Latest Modification: 2019-09-13
Note: 复杂度O(len(head))

  1. class Solution {
  2. public:
  3. 	int getLength(ListNode* head) {
  4. 		int ret = 0;
  5. 		ListNode* temp = head;
  6. 		while(temp != NULL){
  7. 			++ret;
  8. 			temp = temp->next;
  9. 		}
  10. 		return ret;
  11. 	}
  12.     ListNode* rotateRight(ListNode* head, int k) {
  13.         int len = getLength(head);
  14.         if(len < 2 || k % len == 0)return head;
  15. 		int cnt = len - k % len - 1;
  16. 		ListNode* temp1 = head;
  17. 		while(cnt--)temp1 = temp1->next;
  18. 		ListNode* temp2 = temp1->next;
  19. 		ListNode* temp3 = temp2;
  20. 		while(temp3->next != NULL)temp3 = temp3->next;
  21. 		temp1->next = NULL;
  22. 		temp3->next = head;
  23. 		return temp2;
  24.     }
  25. };

L0062 Unique Paths
First AC: 2019-09-13 Latest Modification: 2019-09-13
Note: 复杂度O(min(m,n))

  1. #include<iostream>
  2. using namespace std;
  3. typedef long long ll;
  4. class Solution {
  5. public:
  6. 	int C(int n,int m) {
  7. 		ll ret = 1;
  8. 		for(int i = 1;i <= m;++i){
  9. 			ret = ret * (n - i + 1) / i;
  10. 		}
  11. 		return ret;
  12. 	}
  13.     int uniquePaths(int m, int n) {
  14.         return C(m + n - 2,min(m - 1,n - 1));
  15.     }
  16. };

L0063 Unique Paths II
First AC: 2019-09-13 Latest Modification: 2019-09-13
Note: 复杂度O(len(obstacleGrid)*len(obstacleGrid[0]))

  1. #include<vector>
  2. #include<cstring>
  3. using namespace std;
  4. class Solution {
  5. public:
  6.     int uniquePathsWithObstacles(vector< vector<int> >& obstacleGrid) {
  7.         int row = obstacleGrid.size();
  8.         int column = obstacleGrid[0].size();
  9.         long long dp[row][column];
  10.         memset(dp,0,sizeof dp);
  11.         int my_row = 0,my_column = 0;
  12.         bool flag = true;
  13.         while(flag && my_column < column){
  14.         	if(obstacleGrid[0][my_column])flag = false;
  15.         	else dp[0][my_column++] = 1;
  16. 		}
  17. 		flag = true;
  18.         while(flag && my_row < row){
  19.         	if(obstacleGrid[my_row][0])flag = false;
  20.         	else dp[my_row++][0] = 1;
  21. 		}
  22.         for(int i = 1;i < row;++i){
  23.         	for(int j = 1;j < column;++j){
  24.         		if(!obstacleGrid[i][j]){
  25.         			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  26. 				}
  27. 			}
  28. 		}
  29. 		return dp[row - 1][column - 1];
  30.     }
  31. };

L0064 Minimum Path Sum
First AC: 2019-09-13 Latest Modification: 2019-09-13
Note: 复杂度O(len(grid)*len(grid[0]))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     int minPathSum(vector< vector<int> >& grid) {
  6.         int row = grid.size();
  7.         int column = grid[0].size();
  8.         for(int i = 1;i < row;++i)grid[i][0] += grid[i - 1][0];
  9.         for(int i = 1;i < column;++i)grid[0][i] += grid[0][i - 1];
  10.         for(int i = 1;i < row;++i){
  11.         	for(int j = 1;j < column;++j){
  12.         		grid[i][j] += min(grid[i - 1][j],grid[i][j - 1]);
  13. 			}
  14. 		}
  15. 		return grid[row - 1][column - 1];
  16.     }
  17. };

L0065 Valid Number
First AC: 2019-09-16 Latest Modification: 2019-09-16
Note: 题意不明确,没有给出规则,需要提交尝试,如”.3″,”1.”是”true”,而”e”是”false”,复杂度O(len(s))

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5. 	bool isAllNumber(string s,int l,int r) {
  6. 		if(l > r)return false;
  7. 		for(int i = l;i <= r;++i){
  8. 			if(s[i] < '0' || s[i] > '9')return false;
  9. 		}
  10. 		return true;
  11. 	}
  12. 	bool isNumber(string s,int l,int r) {
  13. 		if(s[l] == '+' || s[l] == '-')++l;
  14. 		if(s[l] == '.')return isAllNumber(s,l + 1,r);
  15. 		if(s[r] == '.')return isAllNumber(s,l,r - 1);
  16. 		for(int i = l;i <= r;++i){
  17. 			if(s[i] == '.'){
  18. 				return isAllNumber(s,l,i - 1) && isAllNumber(s,i + 1,r);
  19. 			}
  20. 		}
  21. 		return isAllNumber(s,l,r);
  22. 	}
  23.     bool isNumber(string s) {
  24.         int len = s.length();
  25.         int l = 0;
  26.         int r = len - 1;
  27.         while(l < r && s[l] == ' ')++l;
  28.         while(l < r && s[r] == ' ')--r;
  29.         if(l > r)return false;
  30.         if(l == r)return s[l] >= '0' && s[l] <= '9';
  31.         int pos = s.find('e');
  32.         if(pos == -1){
  33.         	return isNumber(s,l,r);
  34. 		}
  35. 		else if(pos < r && (s[pos + 1] == '+' || s[pos + 1] == '-')){
  36. 			return isNumber(s,l,pos - 1) && isAllNumber(s,pos + 2,r);
  37. 		}
  38. 		else{
  39. 			return isNumber(s,l,pos - 1) && isAllNumber(s,pos + 1,r);
  40. 		}
  41.     }
  42. };
  43. <pre>
  44.  
  45. L0066	Plus One
  46. First AC: 2019-09-16	Latest Modification: 2019-09-16
  47. Note: 复杂度O(len(digits))
  48. <pre lang="cpp" line="1" escaped="true">
  49. #include<vector>
  50. using namespace std;
  51. class Solution {
  52. public:
  53.     vector<int> plusOne(vector<int>& digits) {
  54.         int len = digits.size() - 1;
  55.         digits[len] += 1;
  56.         while(len && digits[len] > 9){
  57.         	digits[len] = 0;
  58.         	digits[--len] += 1;
  59. 		}
  60. 		if(digits[0] > 9){
  61. 			digits[0] = 0;
  62. 			digits.insert(digits.begin(),1);
  63. 		}
  64. 		return digits;
  65.     }
  66. };

L0067 Add Binary
First AC: 2019-09-18 Latest Modification: 2019-09-18
Note: 复杂度O(max(len(a),len(b)))

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     string addBinary(string a, string b) {
  6.     	if(a.length() < b.length()){
  7.     		string s = a;
  8.     		a = b;
  9.     		b = s;
  10. 		}
  11.         int lena = a.length();
  12.         int lenb = b.length();
  13.         int flag = 0;
  14.         for(int i = lenb - 1;i >= 0;--i){
  15.         	int temp = a[i + lena - lenb] + b[i] + flag - 2 * '0';
  16.         	a[i + lena - lenb] = char(temp % 2 + '0');
  17.         	flag = temp / 2;
  18. 		}
  19. 		for(int i = lena - lenb - 1;i >= 0;--i){
  20. 			if(!flag)break;
  21. 			a[i] += 1;
  22. 			flag = a[i] > '1' ? 1 : 0;
  23. 			if(flag)a[i] = '0';
  24. 		}
  25. 		if(!flag)return a;
  26. 		else return '1' + a;
  27.     }
  28. };

L0068 Text Justification
First AC: 2019-09-29 Latest Modification: 2019-09-29
Note: 复杂度O(sigma(len(words[i])))

  1. #include<vector>
  2. #include<iostream>
  3. using namespace std;
  4. class Solution {
  5. public:
  6. 	void push(vector<string>& ret,vector<string>& v,int maxWidth,int type) {
  7. 		if(type == 1){
  8. 			string s = v[0];
  9. 			int maxi = v.size();
  10. 			for(int i = 1;i < maxi;++i)s += " " + v[i];
  11. 			int extraSpace = maxWidth - s.length();
  12. 			while(extraSpace--)s += " ";
  13. 			ret.push_back(s);
  14. 		}
  15. 		else if(v.size() == 1){
  16. 			string s = "";
  17. 			for(int i = 0;i < maxWidth;++i)s += " ";
  18. 			int maxi = v[0].size();
  19. 			for(int i = 0;i < maxi;++i)s[i] = v[0][i];
  20. 			ret.push_back(s);
  21. 		}
  22. 		else{
  23. 			int numString = v.size();
  24. 			int cntString = 0;
  25. 			for(int i = 0;i < numString;++i)cntString += v[i].length();
  26. 			int numEmpty = numString - 1;
  27. 			int basicSpace = (maxWidth - cntString) / numEmpty;
  28. 			int extraSpace = (maxWidth - cntString) % numEmpty;
  29. 			string basicString = "";
  30. 			for(int i = 0;i < basicSpace;++i)basicString += " ";
  31. 			string s;
  32. 			for(int i = 0;i < numString;++i){
  33. 				s += v[i];
  34. 				if(i != numString - 1)s += basicString;
  35. 				if(i < extraSpace)s += " ";
  36. 			}
  37. 			ret.push_back(s);
  38. 		}
  39. 	}
  40.     vector<string> fullJustify(vector<string>& words, int maxWidth) {
  41.         int len = words.size();
  42.         vector<string> ret;
  43. 		vector<string> v;
  44.         int nowWidth = -1;
  45.         for(int i = 0;i < len;++i){
  46.         	if(nowWidth + words[i].length() + 1 <= maxWidth){
  47.         		v.push_back(words[i]);
  48.         		nowWidth += words[i].length() + 1;
  49. 			}
  50. 			else{
  51. 				--i;
  52. 				push(ret,v,maxWidth,0);
  53. 				v.clear();
  54. 				nowWidth = -1;
  55. 			}
  56. 		}
  57. 		if(!v.empty())push(ret,v,maxWidth,1);
  58. 		return ret;
  59.     }
  60. };

L0069 Sqrt(x)
First AC: 2019-09-29 Latest Modification: 2019-09-29
Note: 复杂度O(1)

  1. class Solution {
  2. public:
  3.     int mySqrt(int x) {
  4.     	long long t = x;
  5.     	while(t * t > x)t = (t + x / t) / 2;
  6.     	return t;
  7.     }
  8. };

L0070 Climbing Stairs
First AC: 2019-09-29 Latest Modification: 2019-09-29

  1. Note: 复杂度O(n)
  2. class Solution {
  3. public:
  4.     int climbStairs(int n) {
  5.     	if(n < 2)return n;
  6.         int ans[n + 1] = {0,1,2};
  7.         for(int i = 3;i <= n;++i)ans[i] = ans[i - 1] + ans[i - 2];
  8.         return ans[n];
  9.     }
  10. };

L0071 Simplify Path
First AC: 2019-09-29 Latest Modification: 2019-09-29
Note: path串按’/’分割,复杂度O(len(path))

  1. #include<deque>
  2. #include<iostream>
  3. using namespace std;
  4. class Solution {
  5. public:
  6.     string simplifyPath(string path) {
  7.         deque<string> dq;
  8.         string s = "";
  9.         path += '/';
  10.         int len = path.length();
  11.         for(int i = 0;i < len;++i){
  12.             if(path[i] != '/'){
  13.         	s += path[i];
  14. 	    }
  15. 	    else{
  16. 		if(s == ".."){
  17. 		    if(!dq.empty())dq.pop_back();
  18. 		}
  19. 		else if(s != "." && s != ""){
  20. 		    dq.push_back(s);
  21. 		}
  22. 		s = "";
  23. 	    }
  24. 	}
  25.         string ret = "";
  26. 	int maxi = dq.size();
  27. 	for(int i = 0;i < maxi;++i)ret += "/" + dq[i];
  28. 	if(ret == "")ret = "/";
  29. 	return ret;
  30.     }
  31. };

L0072 Edit Distance
First AC: 2019-10-17 Latest Modification: 2019-10-17
Note: 动态规划,复杂度O(len(word1)*len(word2))

  1. #include<cmath>
  2. #include<iostream>
  3. using namespace std;
  4. class Solution {
  5. public:
  6.     int Min(int a,int b,int c) {
  7. 	return min(min(a,b),c);
  8.     }
  9.     int minDistance(string word1, string word2) {
  10.         int len1 = word1.length();
  11.         int len2 = word2.length();
  12.         int maxLen = max(len1,len2);
  13.         int dp[maxLen + 3][maxLen + 3] = {0};
  14.         for(int i = 0;i <= maxLen;++i)dp[0][i] = dp[i][0] = i;
  15.         for(int i = 0;i < len1;++i){
  16.             for(int j = 0;j < len2;++j){
  17.         	if(word1[i] == word2[j]){
  18.         	    dp[i + 1][j + 1] = dp[i][j];
  19. 		}
  20. 		else{
  21. 		    dp[i + 1][j + 1] = Min(dp[i + 1][j],dp[i][j + 1],dp[i][j]) + 1;
  22. 		}
  23. 	    }
  24. 	}
  25. 	return dp[len1][len2];
  26.     }
  27. };

L0073 Set Matrix Zeroes
First AC: 2019-10-28 Latest Modification: 2019-10-28
Note: 第一行和第一列记录是否置零,复杂度O(len(matrix)*len(matrix[0]))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     void setZeroes(vector< vector<int> >& matrix) {
  6.         int n = matrix.size();
  7.         if(n == 0)return;
  8.         int m = matrix[0].size();
  9.         if(m == 0)return;
  10.         bool first_row = false;
  11.         bool first_column = false;
  12.         for(int i = 0;i < n;++i){
  13.         	if(matrix[i][0] == 0){
  14.         		first_column = true;
  15.         		break;
  16. 			}
  17. 		}
  18. 		for(int i = 0;i < m;++i){
  19. 			if(matrix[0][i] == 0){
  20. 				first_row = true;
  21. 				break;
  22. 			}
  23. 		}
  24. 		for(int i = 1;i < n;++i){
  25. 			for(int j = 1;j < m;++j){
  26. 				if(matrix[i][j] == 0){
  27. 					matrix[i][0] = 0;
  28. 					matrix[0][j] = 0;
  29. 				}
  30. 			}
  31. 		}
  32. 		for(int i = 1;i < n;++i){
  33. 			for(int j = 1;j < m;++j){
  34. 				if(matrix[i][0] == 0 || matrix[0][j] == 0){
  35. 					matrix[i][j] = 0;
  36. 				}
  37. 			}
  38. 		}
  39. 		if(first_column){
  40. 			for(int i = 0;i < n;++i)matrix[i][0] = 0;
  41. 		}
  42. 		if(first_row){
  43. 			for(int i = 0;i < m;++i)matrix[0][i] = 0;
  44. 		}
  45.     }
  46. };

L0074 Search a 2D Matrix
First AC: 2019-10-28 Latest Modification: 2019-10-28
Note: 二分查找,复杂度O(log(len(matrix)+len(matrix[0])))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5. 	int find_row(vector< vector<int> >& matrix,int l,int r,int target) {
  6. 		if(l + 3 > r){
  7. 			for(int i = r;i > l;--i){
  8. 				if(matrix[i][0] <= target)return i;
  9. 			}
  10. 			return l;
  11. 		}
  12. 		int m = (l + r) / 2;
  13. 		if(matrix[m][0] < target)return find_row(matrix,m,r,target);
  14. 		if(matrix[m][0] > target)return find_row(matrix,l,m - 1,target);
  15. 		return m;
  16. 	}
  17. 	bool find_column(vector< vector<int> >& matrix,int row,int l,int r,int target) {
  18. 		if(l + 3 > r){
  19. 			for(int i = l;i <= r;++i){
  20. 				if(matrix[row][i] == target)return true;
  21. 			}
  22. 			return false;
  23. 		}
  24. 		int m = (l + r) / 2;
  25. 		if(matrix[row][m] < target)return find_column(matrix,row,m + 1,r,target);
  26. 		if(matrix[row][m] > target)return find_column(matrix,row,l,m - 1,target);
  27. 		return true; 
  28. 	}
  29.     bool searchMatrix(vector< vector<int> >& matrix, int target) {
  30.         int m = matrix.size();
  31.         if(m == 0)return false;
  32.         int n = matrix[0].size();
  33.         if(n == 0)return false;
  34.         int row = find_row(matrix,0,m - 1,target);
  35.         return find_column(matrix,row,0,n - 1,target);
  36.     }
  37. };

L0075 Sort Colors
First AC: 2019-10-28 Latest Modification: 2019-10-28
Note: 记录最右的0和最左的2,复杂度O(len(nums))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     void sortColors(vector<int>& nums) {
  6.         int l = 0,r = nums.size() - 1,now = 0;
  7.         while(now <= r){
  8.         	if(nums[now] == 0){
  9.         		int temp = nums[now];
  10.         		nums[now++] = nums[l];
  11.         		nums[l++] = temp;
  12. 			}
  13. 			else if(nums[now] == 2){
  14. 				int temp = nums[now];
  15. 				nums[now] = nums[r];
  16. 				nums[r--] = temp;
  17. 			}
  18. 			else ++now;
  19. 		}
  20.     }
  21. };

L0076 Minimum Window Substring
First AC: 2019-11-01 Latest Modification: 2019-11-01
Note: 滑动答案,每个循环先右滑找到最左可行右端点,然后保存答案,再右滑左端点,复杂度O(len(s)+len(t))

  1. #include<iostream>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     string minWindow(string s, string t) {
  6.     	int lens = s.length(),lent = t.length();
  7.         int jdg[256] = {0};
  8.         int num = 0;
  9.         for(int i = 0;i < lent;++i){
  10.         	++num;
  11.         	++jdg[t[i]];
  12. 		}
  13. 		int cnt[256] = {0},now = 0;
  14. 		int l = 0,r = 0,ansl = 0,ansr = 0,anslen = lens;
  15. 		bool flag = false;
  16. 		while(true){
  17. 			while(now < num){
  18. 				if(r == lens)break;
  19. 				if(jdg[s[r]]){
  20. 					if(cnt[s[r]] < jdg[s[r]])++now;
  21. 					++cnt[s[r]];
  22. 				}
  23. 				++r;
  24. 			}
  25. 			if(now < num)break;
  26. 			flag = true;
  27. 			int tmplen = r - l;
  28. 			if(tmplen < anslen){
  29. 				ansl = l;
  30. 				ansr = r - 1;
  31. 				anslen = tmplen;
  32. 			}
  33. 			if(jdg[s[l]]){
  34. 				--cnt[s[l]];
  35. 				if(cnt[s[l]] < jdg[s[l]])--now;
  36. 			}
  37. 			++l;
  38. 		}
  39. 		if(!flag)return "";
  40. 		return s.substr(ansl,anslen);
  41.     }
  42. };

L0077 Combinations
First AC: 2019-11-01 Latest Modification: 2019-11-01
Note: dfs,复杂度O(n^k)

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5. 	void dfs(vector< vector<int> >& v,int n,int k,int pos,vector<int>& now) {
  6. 		if(pos == k){
  7. 			v.push_back(now);
  8. 			return;
  9. 		}
  10. 		for(int i = (pos? now[pos - 1] : 0) + 1;i <= n;++i){
  11. 			now[pos] = i;
  12. 			dfs(v,n,k,pos + 1,now);
  13. 		}
  14. 	}
  15.     vector< vector<int> > combine(int n, int k) {
  16.         vector< vector<int> > ret;
  17.         vector<int> v;
  18.         for(int i = 0;i < k;++i)v.push_back(0);
  19.         dfs(ret,n,k,0,v);
  20.         return ret;
  21.     }
  22. };

L0078 Subsets
First AC: 2019-11-01 Latest Modification: 2019-11-01
Note: 看作二进制编码,复杂度O(2^len(num))

  1. #include<vector>
  2. using namespace std;
  3. class Solution {
  4. public:
  5.     vector< vector<int> > subsets(vector<int>& nums) {
  6.         int len = nums.size();
  7.         int maxCode = 1;
  8.         while(len--)maxCode *= 2;
  9.         len = nums.size();
  10.         vector< vector<int> > ret;
  11.         for(int i = 0;i < maxCode;++i){
  12.         	int code = i;
  13.         	vector<int> temp;
  14.         	for(int j = 0;j < len;++j){
  15.         		if(code % 2)temp.push_back(nums[j]);
  16.         		code /= 2;
  17. 			}
  18. 			ret.push_back(temp);
  19. 		}
  20. 		return ret;
  21.     }
  22. };

L0079 Word Search
First AC: 2019-11-02 Latest Modification: 2019-11-02
Note: dfs

  1. #include<vector>
  2. #include<cstring>
  3. #include<iostream>
  4. using namespace std;
  5. typedef vector< vector<char> > mymap;
  6. class Solution {
  7. public:
  8. 	const int dr[4] = {-1, 1, 0, 0};
  9. 	const int dc[4] = { 0, 0,-1, 1};
  10. 	bool dfs(mymap& board,int r,int c,int mr,int mc,string w,int pos,mymap& jdg) {
  11. 		if(pos == w.length())return true;
  12. 		bool ret = false;
  13. 		for(int i = 0;i < 4;++i){
  14. 			if(ret)break;
  15. 			int tr = r + dr[i];
  16. 			int tc = c + dc[i];
  17. 			if(tr < 0 || tc < 0 || tr == mr || tc == mc)continue;
  18. 			if(jdg[tr][tc] == ' ' && board[tr][tc] == w[pos]){
  19. 				jdg[tr][tc] = '.';
  20. 				ret |= dfs(board,tr,tc,mr,mc,w,pos + 1,jdg);
  21. 				jdg[tr][tc] = ' ';
  22. 			}
  23. 		}
  24. 		return ret;
  25. 	}
  26.     bool exist(mymap& board, string word) {
  27.     	if(word == "")return true;
  28.         int r = board.size();
  29.         int c = board[0].size();
  30. 		vector<char> blankLine;
  31. 		for(int i = 0;i <c;++i)blankLine.push_back(' ');
  32.         for(int i = 0;i < r;++i){
  33.         	for(int j = 0;j < c;++j){
  34.         		if(board[i][j] == word[0]){
  35.         			vector< vector<char> > jdg;
  36.         			for(int k = 0;k < r;++k){
  37. 			        	jdg.push_back(blankLine);
  38. 					}
  39. 					jdg[i][j] = '.';
  40.         			if(dfs(board,i,j,r,c,word,1,jdg))return true;
  41. 				}
  42. 			}
  43. 		}
  44. 		return false;
  45.     }
  46. };

L0080 Remove Duplicates from Sorted Array II
First AC: 2019-11-02 Latest Modification: 2019-11-02
Note: 记录去重后保留的数目,复杂度O(len(nums))

  1. #include<vector>
  2. #include<iostream>
  3. using namespace std;
  4. class Solution {
  5. public:
  6.     int removeDuplicates(vector<int>& nums) {
  7.         int len = nums.size();
  8.         int now,cnt = 1,pos = 1;
  9.         for(int i = 1;i < len;++i){
  10.         	now = nums[i];
  11.         	if(nums[i] == nums[i - 1])++cnt;
  12.         	else cnt = 1;
  13.         	if(cnt < 3)nums[pos++] = nums[i];
  14. 		}
  15. 		return min(pos,len);
  16.     }
  17. };