算法面经

数组

88. 合并两个有序数组

经典 逆向双指针

1. void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {  
2.     for (int i = m - 1, j = n - 1, k = m + n - 1; ~j; k--) {  
3.         nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];  
4.     }  
5. }

复制代码

4. 寻找两个正序数组的中位数

困难，hot100，必会题，重点是求两个数组中第k大的数

1. double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {  
2.     int m = nums1.size(), n = nums2.size();  
3.     int a = getKth(0, 0, (m + n + 1) / 2, nums1, nums2);  
4.     int b = getKth(0, 0, (m + n + 2) / 2, nums1, nums2);  
5.     return (a + b) / 2.0;  
6. }  
7.   
8. int getKth(int i, int j, int k, vector<int> &nums1, vector<int> &nums2) {  
9.     int m = nums1.size(), n = nums2.size();  
10.     if (i >= m) {  
11.         return nums2[j + k - 1];  
12.     }  
13.     if (j >= n) {  
14.         return nums1[i + k - 1];  
15.     }  
16.     if (k == 1) {  
17.         return min(nums1[i], nums2[j]);  
18.     }  
19.     int p = k / 2;  
20.     int x = i + p - 1 < m ? nums1[i + p - 1] : INT_MAX;  
21.     int y = j + p - 1 < n ? nums2[j + p - 1] : INT_MAX;  
22.     return x < y ? getKth(i + p, j, k - p, nums1, nums2) : getKth(i, j + p, k - p, nums1, nums2);  
23. }

复制代码

15. 三数之和

两数之和升级版，方法完全不一样，还用hash的话，会有很多特殊情况需要考虑，推荐使用 排序+双指针 法。字节常考题，必会。

1. vector<vector<int>> threeSum(vector<int> &nums) {  
2.     sort(nums.begin(), nums.end());  
3.     vector<vector<int>> ans;  
4.     int n = nums.size();  
5.     for (int i = 0; i < n - 2 && nums[i] <= 0; i++) {  
6.         if (i && nums[i] == nums[i - 1]) continue;  
7.   
8.         int j = i + 1, k = n - 1;  
9.         while (j < k) {  
10.             int x = nums[i] + nums[j] + nums[k];  
11.             if (x < 0) {  
12.                 j++;  
13.             } else if (x > 0) {  
14.                 k--;  
15.             } else {  
16.                 ans.push_back({nums[i], nums[j++], nums[k--]});  
17.                 while (j < k && nums[j] == nums[j - 1]) {  
18.                     j++;  
19.                 }  
20.                 while (j < k && nums[k] == nums[k + 1]) {  
21.                     k--;  
22.                 }  
23.             }  
24.         }  
25.     }  
26.     return ans;  
27. }

复制代码

字符串

5. 最长回文子串

必须掌握，方法1:动态规划，方法2:中心扩展法

1. /* f[i][j] 即 s[i...j]是否为回文串  
2. * if s[i]=s[j],f[i][j]=f[i-1][j+1] */
3. string longestPalindrome(string s) {  
4.     int n = s.size();  
5.     vector<vector<bool>> f(n, vector<bool>(n, true));  
6.     int k = 0, mx = 1;  
7.     for (int i = n - 2; i >= 0; i++) {  
8.         for (int j = i + 1; j < n; j++) {  
9.             f[i][j] = false;  
10.             if (s[i] == s[j]) {  
11.                 f[i][j] = f[i + 1][j - 1];  
12.                 if (f[i][j] && mx < j - i + 1) {  
13.                     mx = j - i + 1;  
14.                     k = i;  
15.                 }  
16.             }  
17.         }  
18.     }  
19.     return s.substr(k, mx);  
20. }
22. // 中心扩展发
23. class Solution1 {  
24. public:  
25.     string palindrome(string s, int l, int r) {  
26.         int n = s.size();  
27.         while (l >= 0 && r < n && s[l] == s[r]) {  
28.             l--;  
29.             r++;  
30.         }  
31.         return s.substr(l + 1, r - l - 1);  
32.     }  
33.   
34.     string longestPalindrome(string s) {  
35.         string res = "";  
36.         for (int i = 0; i < s.length(); i++) {  
37.             string s1 = palindrome(s, i, i);  
38.             string s2 = palindrome(s, i, i + 1);  
39.             res = res.size() > s1.size() ? res : s1;  
40.             res = res.size() > s2.size() ? res : s2;  
41.         }  
42.         return res;  
43.     }  
44. };

复制代码

2的1000次方

字符串乘法，腾讯面试题
[code]#include   #include     using namespace std;    string multiplyByTow(const string &num) {      string res;      int carry = 0;      for (int i = num.size() - 1; i >= 0; i--) {          int digit = num - '0';          int product = digit * 2 + carry;          carry = product / 10;          res.insert(res.begin(), '0' + (product % 10));      }      while (carry > 0) {          res.insert(res.begin(), '0' + (carry % 10));          carry /= 10;      }      return res;  }    int main() {      string res = "1";      for (int i = 0; i < 1000; i++) {          res = multiplyByTow(res);      }      cout