算法面经

数组

88. 合并两个有序数组

经典 逆向双指针

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

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

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

double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {  
    int m = nums1.size(), n = nums2.size();  
    int a = getKth(0, 0, (m + n + 1) / 2, nums1, nums2);  
    int b = getKth(0, 0, (m + n + 2) / 2, nums1, nums2);  
    return (a + b) / 2.0;  
}  
  
int getKth(int i, int j, int k, vector<int> &nums1, vector<int> &nums2) {  
    int m = nums1.size(), n = nums2.size();  
    if (i >= m) {  
        return nums2[j + k - 1];  
    }  
    if (j >= n) {  
        return nums1[i + k - 1];  
    }  
    if (k == 1) {  
        return min(nums1[i], nums2[j]);  
    }  
    int p = k / 2;  
    int x = i + p - 1 < m ? nums1[i + p - 1] : INT_MAX;  
    int y = j + p - 1 < n ? nums2[j + p - 1] : INT_MAX;  
    return x < y ? getKth(i + p, j, k - p, nums1, nums2) : getKth(i, j + p, k - p, nums1, nums2);  
}

15. 三数之和

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

vector<vector<int>> threeSum(vector<int> &nums) {  
    sort(nums.begin(), nums.end());  
    vector<vector<int>> ans;  
    int n = nums.size();  
    for (int i = 0; i < n - 2 && nums[i] <= 0; i++) {  
        if (i && nums[i] == nums[i - 1]) continue;  
  
        int j = i + 1, k = n - 1;  
        while (j < k) {  
            int x = nums[i] + nums[j] + nums[k];  
            if (x < 0) {  
                j++;  
            } else if (x > 0) {  
                k--;  
            } else {  
                ans.push_back({nums[i], nums[j++], nums[k--]});  
                while (j < k && nums[j] == nums[j - 1]) {  
                    j++;  
                }  
                while (j < k && nums[k] == nums[k + 1]) {  
                    k--;  
                }  
            }  
        }  
    }  
    return ans;  
}

字符串

5. 最长回文子串

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

/* f[i][j] 即 s[i...j]是否为回文串  
 * if s[i]=s[j],f[i][j]=f[i-1][j+1] */
string longestPalindrome(string s) {  
    int n = s.size();  
    vector<vector<bool>> f(n, vector<bool>(n, true));  
    int k = 0, mx = 1;  
    for (int i = n - 2; i >= 0; i++) {  
        for (int j = i + 1; j < n; j++) {  
            f[i][j] = false;  
            if (s[i] == s[j]) {  
                f[i][j] = f[i + 1][j - 1];  
                if (f[i][j] && mx < j - i + 1) {  
                    mx = j - i + 1;  
                    k = i;  
                }  
            }  
        }  
    }  
    return s.substr(k, mx);  
}

// 中心扩展发
class Solution1 {  
public:  
    string palindrome(string s, int l, int r) {  
        int n = s.size();  
        while (l >= 0 && r < n && s[l] == s[r]) {  
            l--;  
            r++;  
        }  
        return s.substr(l + 1, r - l - 1);  
    }  
  
    string longestPalindrome(string s) {  
        string res = "";  
        for (int i = 0; i < s.length(); i++) {  
            string s1 = palindrome(s, i, i);  
            string s2 = palindrome(s, i, i + 1);  
            res = res.size() > s1.size() ? res : s1;  
            res = res.size() > s2.size() ? res : s2;  
        }  
        return res;  
    }  
};

2的1000次方

字符串乘法，腾讯面试题

#include <iostream>  
#include <string>  
  
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[i] - '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 << "2^1000 = " << res << endl;  
}

14. 最长公共前缀

字符串最常考的题，面试不会直接回家种田

string longestCommonPrefix(vector<string> &strs) {  
    for (int i = 0; i < strs[0].size(); i++) {  
        for (int j = 1; j < strs.size(); j++) {  
            if (i >= strs[j].size() || strs[j][i] != strs[0][i]) {  
                return strs[0].substr(0,i);  
            }  
        }  
    }  
    return strs[0];  
}

哈希表

1. 两数之和 不必多言
3. 无重复字符的最长子串 双指针+哈希表

链表

翻转链表

标签：return,cur,nums,int,res,面经,算法,vector
From： https://www.cnblogs.com/cheng-sir/p/18032246