只记录一些简单的高频面试题，方便自己随时复习。都是简单题，不要笑我😂因为有时候真的做不出来

1、 反转链表

两种方法都要掌握，面试官可能会指定用迭代或递归的方式完成。

//迭代法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) return head;
        ListNode *pre = head, *cur = head->next;

        while (cur)
        {
            ListNode *ne = cur->next;
            cur->next = pre;
            pre = cur, cur = ne;
        }

        head->next = nullptr;

        return pre;
    }
};

//递归法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;

        ListNode* p = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return p;
    }
};

2、两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;

        for (int i = 0; i < nums.size(); ++ i)
        {
            if (hash.count(target - nums[i]))
                return {hash[target - nums[i]], i};
            hash[nums[i]] = i;
        }
        return {};
    }
};

3、 三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;

        int n = nums.size();
        if (n < 3) return res;

        sort(nums.begin(), nums.end());

        for (int i = 0; i < n; i ++ )
        {
            if (nums[i] > 0) return res;            //若第一个数大于0，后面怎么加都不会等于0了
            if (i > 0 && nums[i] == nums[i - 1]) continue;  //跳过重复数字

            int l = i + 1, r = n - 1;
            while (l < r)
            {
                if (nums[i] + nums[l] + nums[r] == 0)
                {
                    res.push_back({nums[i], nums[l], nums[r]});         //加入一个正确方案
                    while (l < r && nums[l] == nums[l + 1]) l ++ ;      //跳过重复数字
                    while (l < r && nums[r] == nums[r - 1]) r -- ;
                    l ++ ;                                              //左指针前进
                    r -- ;                                              //右指针后退
                }
                else if (nums[i] + nums[l] + nums[r] > 0)
                {
                    r -- ;      //和大于0，要减少总和之值，即右指针后退
                }
                else
                {
                    l ++ ;      //和小于0，要增加总和之值，即左指针前进
                }
            }
        }
        return res;
    }
};

4、 无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) return 0;
        unordered_set<char> hash;

        int max_size = 0, st = 0;           //st表示无重复字符串的起始下标
        for (int i = 0; i < s.size(); ++ i)
        {
            while (hash.count(s[i]))
            {
                hash.erase(s[st]);          //注意这里删的是s[st]不是s[i]
                ++ st;                      //出现重复，则下标向前推进
            }
            max_size = max(max_size, i - st + 1);
            hash.insert(s[i]);
        }
        return max_size;
    }
};

5、 最大子序和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {    //经典的贪心题
        int res = INT_MIN, sum = 0;
        for (int &num : nums)
        {
            sum += num;
            res = max(res, sum);
            if (sum < 0) sum = 0;
        }
        return res;
    }
};

6、 相交链表

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) return nullptr;

        ListNode *pA = headA, *pB = headB;
        while (pA != pB)
        {
            if (pA) pA = pA->next;
            else pA = headB;
            if (pB) pB = pB->next;
            else pB = headA;
        }
        return pA;
    }
};

7、 环形链表

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr) return false;

        ListNode *p = head, *q = head;
        while (p && q)
        {
            p = p->next;
            q = q->next;
            if (q) q = q->next;
            else return false;

            if (p == q) return true;
        }
        return false;
    }
};

7.2 、环形链表 II

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr) return nullptr;

        ListNode* fast = head, *slow = head;
        while (fast && slow)
        {
            fast = fast->next, slow = slow->next;
            if (fast) fast = fast->next;
            else return nullptr;

            if (fast == slow)
            {
                slow = head;
                while (fast != slow)
                    fast = fast->next, slow = slow->next;
                return slow;
            }
        }

        return nullptr;
    }
};

8、 二叉搜索树的最近公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode *ans = root;

        while (true)
        {
            if (p->val < ans->val && q->val < ans->val)         //两个点根节点在左边
                ans = ans->left;
            else if (p->val > ans->val && q->val > ans->val)    //两个点根节点在右边
                ans = ans->right;
            else break;     //分别在根节点左右两边，根节点即是最近公共祖先
        }
        return ans;
    }
};

9、 二叉树的最近公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return nullptr;                     //递归到空，说明当前子树不包含p和q

        if (root == p || root == q) return root;    //递归找到p或q直接返回

        auto left = lowestCommonAncestor(root->left, p, q);
        auto right = lowestCommonAncestor(root->right, p, q);

        if (left && right) return root;             //p,q分别在左右子树，则返回当前节点
        if (left) return left;                      //p,q都在左子树，返回左节点
        else return right;
    }
};

10、 合并两个有序数组

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p = m + n - 1;
        int p1 = m - 1, p2 = n - 1;

        while (~p1 && ~p2)
        {
            if (nums1[p1] >= nums2[p2]) nums1[p -- ] = nums1[p1 -- ];
            else nums1[p -- ] = nums2[p2 -- ];
        }
        while (~p1) nums1[p -- ] = nums1[p1 -- ];
        while (~p2) nums1[p -- ] = nums2[p2 -- ];
    }
};

12、合并两个有序链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;

        ListNode *dummy = new ListNode(0), *p = dummy;
        while (l1 && l2)
        {
            if (l1->val <= l2->val)
                p = p->next = l1, l1 = l1->next;
            else
                p = p->next = l2, l2 = l2->next;
        }

        if (l1) p = p->next = l1;
        if (l2) p = p->next = l2;

        return dummy->next;
    }
};

12、 合并K个升序链表

class Solution {    //这题其实不难，就是在合并两个有序链表的基础上加了一个for循环
public:
    ListNode* merge(ListNode* l1, ListNode* l2)
    {
        ListNode *dummy = new ListNode(0), *p = dummy;

        while (l1 && l2)
        {
            if (l1->val < l2->val)
                p = p->next = l1, l1 = l1->next;
            else
                p = p->next = l2, l2 = l2->next;
        }
        if (l1) p = p->next = l1;
        if (l2) p = p->next = l2;
        return dummy->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;

        ListNode* res = lists[0];
        for (int i = 1; i < lists.size(); ++ i)
            res = merge(res, lists[i]);

        return res;
    }
};

15、 K 个一组翻转链表

class Solution {
public:
    ListNode* reverse(ListNode* head, ListNode* tail)
    {
        ListNode *pre = head, *cur = head->next;
        while (cur != tail)
        {
            ListNode* ne = cur->next;
            cur->next = pre;
            pre = cur, cur = ne;
        }
        head->next = nullptr;
        return pre;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == nullptr || head->next == nullptr) return head;

        ListNode* tail = head;
        for (int i = 0; i < k; ++ i)
        {
            if (tail == nullptr) return head;
            //注意，如果这里面试官要求最后不足k个也要翻转，就得改成下面一行
            //if (tail == nullptr) return reverse(head, tail);
            tail = tail->next;
        }

        ListNode* newhead = reverse(head, tail);
        head->next = reverseKGroup(tail, k);

        return newhead;
    }
};

14、 反转链表 II

class Solution {    //这题要找四个点才能解，一定要保持清醒
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (head == nullptr || head->next == nullptr) return head;

        ListNode *dummy = new ListNode(0, head);
        ListNode *before = dummy, *ed = dummy;

        for (int i = 0; i < left - 1; ++ i) 
        {
            if (before->next) before = before->next;
            else return head;
        }
        for (int i = 0; i < right; ++ i)
        {
            if (ed->next) ed = ed->next;
            else break;
        }
        ListNode *st = before->next, *after = ed->next;
        ListNode *pre = st, *cur = st->next;
        while (cur != after)
        {
            ListNode *ne = cur->next;
            cur->next = pre;
            pre = cur, cur = ne;
        }
        before->next = ed, st->next = after;
        return dummy->next;
    }
};

15、 买卖股票的最佳时机

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min_v = INT_MAX, max_v = 0;

        for (int& price : prices)
        {
            min_v = min(min_v, price);
            max_v = max(max_v, price - min_v);
        }
        return max_v;
    }
};

16、字符串转换整数 (atoi)

注意在做提前一定要主动询问面试官，如果遇到空字符串应该返回什么？字符串表示的数字范围是多大？这个题就是以这种方式来考察你的沟通能力的。

class Solution {
public:
    int myAtoi(string s) {
        if (s.empty()) return 0;
        int res = 0, flag = 1, i = 0;

        while (s[i] == ' ') ++ i;
        if (s[i] == '+') ++ i;
        else if (s[i] == '-') flag = -1, ++ i;

        while (i < s.size() && s[i] >= '0' && s[i] <= '9')
        {
            int t = s[i] - '0';
            if (res > INT_MAX / 10 || (res == INT_MAX / 10 && t > 7)) return flag == 1 ? INT_MAX : INT_MIN;
            res = res * 10 + t;
            ++ i;
        }
        return flag * res;
    }
};

17、 二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;

        int l = 0, r = nums.size() - 1;
        while (l <= r)
        {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return -1;
    }
};

18、字符串相加（高精度加法）

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = num1.size() - 1, j = num2.size() - 1, t = 0;
        string res = "";

        while (i >= 0 || j >= 0 || t != 0)
        {
            if (i >= 0) t += num1[i] - '0';
            if (j >= 0) t += num2[j] - '0';
            res.push_back(t % 10 + '0');
            t /= 10;
            -- i, -- j;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

19、 x 的平方根

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x;
        while (l < r)
        {
            int mid = ((long)l + r + 1) >> 1;
            if (mid <= x / mid) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

20、 最长回文子串

算是高频且有点难度的，字节考过，DP不会，直接上个中心展开简单版本。

class Solution {
public:
    pair<int, int> expand(string& s, int left, int right)
    {
        while (left >= 0 && right < s.size() && s[left] == s[right]) -- left, ++ right;
        return {left + 1, right - 1};
    }

    string longestPalindrome(string s) {
        int st = 0, ed = 0;
        for (int i = 0; i < s.size(); ++ i)
        {
            auto [left1, right1] = expand(s, i, i);
            auto [left2, right2] = expand(s, i, i + 1);
            if (right1 - left1 > ed - st) st = left1, ed = right1;
            if (right2 - left2 > ed - st) st = left2, ed = right2;
        }

        return s.substr(st, ed - st + 1);
    }
};

21、从前序与中序遍历序列构造二叉树

class Solution {
public:
    unordered_map<int, int> pos;

    TreeNode* dfs(vector<int>& pre, int pl, int pr, vector<int>& in, int il, int ir)
    {
        if (pl > pr) return nullptr;
        int k = pos[pre[pl]] - il;
        TreeNode* root = new TreeNode(pre[pl]);

        root->left = dfs(pre, pl + 1, pl + k, in, il, il + k - 1);
        root->right = dfs(pre, pl + k + 1, pr, in, il + k + 1, ir);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        if (n == 0) return nullptr;

        for (int i = 0; i < n; ++ i) pos[inorder[i]] = i;
        return dfs(preorder, 0, n - 1, inorder, 0, n - 1);
    }
};

22、从中序与后序遍历序列构造二叉树

class Solution {
public:
    unordered_map<int, int> pos;

    TreeNode* dfs(vector<int>& in, int il, int ir, vector<int>& post, int pl, int pr)
    {
        if (il > ir || pl > pr) return nullptr;
        int k = pos[post[pr]] - il;
        TreeNode* root = new TreeNode(post[pr]);

        root->left = dfs(in, il, il + k - 1, post, pl, pl + k - 1);
        root->right = dfs(in, il + k + 1, ir, post, pl + k, pr - 1);

        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        if (n == 0) return nullptr;

        for (int i = 0; i < n; ++ i) pos[inorder[i]] = i;
        return dfs(inorder, 0, n - 1, postorder, 0, n - 1);
    }
};

23、 螺旋矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if (matrix.empty()) return res;

        int left = 0, right = matrix[0].size() - 1, top = 0, down = matrix.size() - 1;//不-1的情况
        while (true)
        {
            for (int i = left; i <= right; ++ i) res.push_back(matrix[top][i]);
            if ( ++ top > down) break;
            for (int i = top; i <= down; ++ i) res.push_back(matrix[i][right]);
            if ( -- right < left) break;
            for (int i = right; i >= left; -- i) res.push_back(matrix[down][i]);
            if ( -- down < top) break;
            for (int i = down; i >= top; -- i) res.push_back(matrix[i][left]);
            if ( ++ left > right) break;
        }

        return res;
    }
};

更新ing…