超超超高频面试题，快来混个脸熟（一）

ACM算法日常

发布于 2021-09-07 14:55:33

3230

文章被收录于专栏：ACM算法日常ACM算法日常

秋招拉开了帷幕，今天开始更新互联网超高频面试题

此份试题来自民间面经、code top 网站以及部分官方渠道，命中率超高，可以混个脸熟

出现频率由高到低排序

3. 无重复字符的最长子串 ✨

双指针构成一个滑动窗口
哈希表记录每个元素的出现位置

// go
func max(a int, b int) int {
    if a < b {
        return b
    } else {
        return a
    }
}

func lengthOfLongestSubstring(s string) int {
    mp := make(map[byte]int)
    l, r, ans := 0, 0, 0
    for r < len(s) {
        val, ok := mp[s[r]]
        if !ok {
            mp[s[r]] = r
        } else {
            // mp[s[r]] 表示上一个 s[r] 出现的位置，如果 mp[s[r]] > l，要把 l 移到 mp[s[r]] 之后
            if val >= l {
                l = val + 1
            }
            mp[s[r]] = r
        }
        ans = max(ans, r-l+1)
        r++
    }
    return ans
}

25. K 个一组翻转链表✨

维护四个指针 pre, head, tail, next
找到待反转链表的头尾
做一次普通反转链表，返回新的头尾
串联

// cpp
#define PLL pair< ListNode *, ListNode * >
class Solution {
public:
    PLL getNewHeadTail(ListNode *head, ListNode *tail)
    {
        ListNode *pre = tail->next, *cur = head, *ed = tail->next;
        while (cur != ed) {
            ListNode *temp = cur->next;
            cur->next = pre;
            pre = cur, cur = temp;
        }
        return {tail, head};
    }
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        ListNode *dummy = new ListNode(0, head), *pre = dummy;
        while (head) {
            ListNode *tail = pre;
            for (int i = 0; i < k; ++i) {
                tail = tail->next;
                if (!tail) return dummy->next;
            }
            ListNode *nxt = tail->next;
            PLL temp = getNewHeadTail(head, tail);
            head = temp.first, tail = temp.second;
            pre->next = head, tail->next = nxt;
            pre = tail, head = nxt;
        }
        return dummy->next;
    }
};

20. 有效的括号

// cpp
class Solution {
public:
    bool isValid(string s) {
        stack<int> sta;
        for (auto &i: s) {
            if (i == '(' || i == '[' || i == '{') sta.push(i);
            else {
                if (sta.empty()) return 0;
                if (i == ')' && sta.top() != '(') return 0;
                if (i == ']' && sta.top() != '[') return 0;
                if (i == '}' && sta.top() != '{') return 0;
                sta.pop();
            }
        }
        return sta.empty();
    }
};

1. 两数之和

哈希
或者排序后双指针 meet in the middle

// go
func twoSum(nums []int, target int) []int {
    mp := make(map[int]int)
    for i, v := range nums {
        mp[v] = i
    }
    ans := []int{}
    for i, v := range nums {
        if pos, ok := mp[target-v]; ok && pos > i {
            ans = []int{i, pos}
            break
        }
    }
    return ans
}

15. 三数之和 ✨

排序
枚举第一个数字，接下来两个指针 meet in the middle
用一些去重剪枝技巧

// go
func threeSum(nums []int) [][]int {
    n := len(nums)
    sort.Ints(nums)
    ans := [][]int{}
    for i := 0; i < n; i++ {
        if nums[i] > 0 { // 剪枝
            break
        }
        if i > 0 && nums[i] == nums[i - 1] { // 去重,可能的解已经存在了
            continue;
        }
        k := n - 1
        for j := i + 1; j < n; j++ {
            if j > i + 1 && nums[j] == nums[j - 1] { // 去重,同上
                continue
            }
            for k > j && nums[i] + nums[j] + nums[k] > 0 {
                k--
            }
            if k == j {
                break
            }
            if nums[i] + nums[j] + nums[k] == 0 {
                ans = append(ans, []int{nums[i], nums[j], nums[k]})
            }
        }
    }
    return ans
}

54. 螺旋矩阵

dfs

// go
func spiralOrder(matrix [][]int) []int {
    m, n := len(matrix), len(matrix[0])
    ans := make([]int, m * n)
    vis := make([][]bool, m)
    for i := 0; i < len(matrix); i++ {
        vis[i] = make([]bool, n)
    }
    dfs(matrix, vis, ans, m, n, 0, 0, 0, 0)
    return ans
}
func check(m, n, x, y int, vis[][]bool) bool {
    return x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false
}
func dfs(matrix [][]int, vis [][]bool, ans []int, m, n, x, y, dir, cnt int) {
    if vis[x][y] {
        return
    }
    ans[cnt], cnt, vis[x][y] = matrix[x][y], cnt + 1, true
    DX := []int{0, 1, 0, -1}
    DY := []int{1, 0, -1, 0}
    var tx, ty int
    if check(m, n, x + DX[dir], y + DY[dir], vis) { // 继续顺着这个方向
        tx, ty = x + DX[dir], y + DY[dir]
    } else if check(m, n, x + DX[(dir + 1) % 4], y + DY[(dir + 1) % 4], vis) {  // 换下一个方向
        tx, ty, dir = x + DX[(dir + 1) % 4], y + DY[(dir + 1) % 4], (dir + 1) % 4
    }
    dfs(matrix, vis, ans, m, n, tx, ty, dir, cnt)
}

33. 搜索旋转排序数组

无聊的八股文，没兴趣写二分

// cpp
class Solution {
public:
    int search(vector<int>& nums, int t) {
        for (int i = 0; i < nums.size(); ++i)
            if (nums[i] == t) return i;
        return -1;
    }
};

21. 合并两个有序链表

归并排序的子步骤

// go
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode {
        Val: 0,
        Next: nil,
    }
    pre := head
    for l1 != nil || l2 != nil {
        if l1 == nil || l1 != nil && l2 != nil && l1.Val > l2.Val {
            head.Next = l2
            l2 = l2.Next
        } else {
            head.Next = l1
            l1 = l1.Next
        }
        head = head.Next
    }
    return pre.Next
}

31. 下一个排列 ✨

逆序遍历，找到第一个 nums[i] < nums[i + 1] 的位置 p1
在 [p1 + 1, n) 里面找到第一个比 nums[p1] 大的位置 p2
逆转 [p1 + 1, n)

// cpp
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(),  nums.end());
    }
};

// cpp
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int pos = -1;
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] < nums[i + 1]) {pos = i; break;}
        }
        if (pos != -1) {
            int p = n - 1;
            while (p > pos && nums[p] <= nums[pos]) p--;
            swap(nums[pos], nums[p]);
        }
        reverse(nums.begin() + pos + 1, nums.end());
    }
};

42. 接雨水 ✨

对于每个位置 i，找到他左边和右边最高的位置 p1, p2，则这个位置的贡献为 min(h[p1], h[p2]) - h[i]
累加贡献

// go
func trap(h []int) int {
    lmax := make([]int, len(h))
    rmax := make([]int, len(h))
    for i := 0; i < len(h); i++ {
        if i == 0 {
            lmax[i] = h[i];
        } else {
            lmax[i] = max(lmax[i - 1], h[i])
        }
    }
    for i := len(h) - 1; i >= 0; i-- {
        if i == len(h) - 1 {
            rmax[i] = h[i]
        } else {
            rmax[i] = max(rmax[i + 1], h[i])
        }
    }
    ans := 0
    for i := 1; i < len(h) - 1; i++ {
        ans += min(lmax[i], rmax[i]) - h[i]
    }
    return ans
}

func max(a, b int) int {
    if a < b {
        return b
    } else {
        return a
    }
}
func min(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

53. 最大子序和

动态规划的思想

// go
func maxSubArray(nums []int) int {
    sum, ans := 0, -100001
    for _, v := range(nums) {
        sum = max(sum + v, v)
        ans = max(ans, sum)
    }
    return ans
}

func max(a, b int) int {
    if a < b {
        return b
    } else {
        return a
    }
}

88. 合并两个有序数组

没兴趣写 in place

// go
func merge(nums1 []int, m int, nums2 []int, n int)  {
    temp := make([]int, m + n)
    i, j, k := 0, 0, 0
    for i < m || j < n {
        if (i == m || i < m && j < n && nums1[i] > nums2[j]) {
            temp[k] = nums2[j]
            k++
            j++
        } else {
            temp[k] = nums1[i]
            k++
            i++
        }
    }
    for i, v := range(temp) {
        nums1[i] = v
    }
}

102. 二叉树的层序遍历 ✨

把一层放入队列来 bfs

// cpp
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            int sz = q.size();
            vector<int> level;
            for (int i = 1; i <= sz; ++i) {
                TreeNode *temp = q.front(); q.pop();
                level.push_back(temp->val);
                if (temp->left) q.push(temp->left);
                if (temp->right) q.push(temp->right);
            }
            ans.push_back(level);
        }
        return ans;
    }
};

103. 二叉树的锯齿形层序遍历 ✨

用双端队列来维护节点
从右往左遍历先放右儿子，从左往右遍历先放左儿子

// cpp
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        deque<TreeNode *> q;
        q.push_back(root);
        int cnt = 0;
        while (!q.empty()) {
            int sz = q.size();
            vector<int> level;
            if (cnt == 0) {
                for (int i = 1; i <= sz; ++i) { // 从左往右遍历，先放左儿子
                    TreeNode *temp = q.front(); q.pop_front();
                    level.push_back(temp->val);
                    if (temp->left) q.push_back(temp->left);
                    if (temp->right) q.push_back(temp->right);
                }
            }
            else {
                for (int i = 1; i <= sz; ++i) { // 从右往左遍历，先放右儿子
                    TreeNode *temp = q.back(); q.pop_back();
                    level.push_back(temp->val);
                    if (temp->right) q.push_front(temp->right);
                    if (temp->left) q.push_front(temp->left);
                }
            }
            cnt = (cnt + 1) % 2;
            ans.push_back(level);
        }
        return ans;
    }
};

105. 从前序与中序遍历序列构造二叉树 ✨

前序结构为 [root] [left] [right]
中序结构为 [left] [root] [right]
在中序中找到根的位置 pos1，就可以快速定位前序中左子树的右边界 pos2
可以用哈希预处理中序里面根的位置

// cpp
class Solution {
public:
    unordered_map<int, int> mp;
    void preSolve(vector<int> &inorder) {
        for (int i = 0; i < inorder.size(); ++i) {
            mp[inorder[i]] = i;
        }
    }
    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir) {
        if (pl >= pr) return nullptr;
        TreeNode *root = new TreeNode(preorder[pl]);
        int pos1 = mp[root->val]; // 利用哈希表 O(1) 计算根在中序遍历中的位置 pos1
        int pos2 = pl + (pos1 - il); // 根据 pos1 计算出左子树的边界位置 pos2
        root->left = dfs(preorder, inorder, pl + 1, pos2 + 1, il, pos1);
        root->right = dfs(preorder, inorder, pos2 + 1, pr, pos1 + 1, ir);
        return root;
    }
    TreeNode* buildTree(vector<int>& p, vector<int>& i) {
        preSolve(i);
        return dfs(p, i, 0, p.size(), 0, i.size());
    }
};
/*
[root] [left] [right]
[left] [root] [right]
*/

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-08-25，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树