ToB企服应用市场:ToB评测及商务社交产业平台

标题: 算法面经 [打印本页]
作者: 络腮胡菲菲    时间: 2024-5-7 18:38
标题: 算法面经
数组

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



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4