超超超高频面试题，秋招持续发力！

ACM算法日常

发布于 2021-09-28 16:25:44

5710

发布于 2021-09-28 16:25:44

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

秋招即将过半，备战的小伙伴们可不能懈怠，我们继续发力！

前两期已经有题目命中面试题了，美团面试官直接拿第一期的「搜索螺旋数组」来问我，还好写出来了。

124. 二叉树中的最大路径和

用树形 dp 的思想，考虑以节点 root 为根最大的路径和，有三种状态可以向上转移

左子树带上 root
右子树带上 root
只有 root

维护答案的时候，还要计算左右子树带上 root 的情况，虽然这种状态无法向上转移

// go
func maxPathSum(root *TreeNode) int {
    ans := -1001
    var dfs func(root *TreeNode) int
    dfs = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        Left := dfs(root.Left)
        Right := dfs(root.Right)
        temp := max(root.Val, max(Left, Right) + root.Val)
        ans = max(ans, max(temp, root.Val + Left + Right))
        return temp
    }
    ans = max(ans, dfs(root))
    return ans
}

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

129. 求根节点到叶节点数字之和

dfs

// go
var ans int
func sumNumbers(root *TreeNode) int {
    pre := 0
    ans = 0
    dfs(root, pre)
    return ans
}

func dfs(root *TreeNode, val int) {
    if root == nil {
        return
    }
    val = val * 10 + root.Val
    if root.Left != nil {
        dfs(root.Left, val)
    }
    if root.Right != nil {
        dfs(root.Right, val)
    } 
    if root.Left == nil && root.Right == nil {
        ans += val
    }
    val = (val - root.Val) / 10
}

142. 环形链表 II

快指针步长为

，慢指针为

，设环之前的链长

，快慢指针相遇处距离环口

，剩下的环长

当快慢指针相遇时，设快指针走了

圈，慢指针走了

圈，考虑速度比，有

a + x(b + c) + b = 2\cdot [a + y(b + c) + b]

即

a + b\equiv 0\mod (b + c)

，从而

a\equiv c\mod (b + c)

因此再设置一个指针从头走，一定可以与慢指针在环口相遇

// go
func detectCycle(head *ListNode) *ListNode {
    a, b := head, head
    for b != nil {
        a = a.Next
        if b.Next == nil {
            return nil
        }
        b = b.Next.Next
        if a == b {
            c := head
            for a != c {
                a, c = a.Next, c.Next
            }
            return c
        }
    }
    return nil
}

143. 重排链表 ✨

用快慢指针找到链表中点
快指针步长为

，慢指针步长为

，这样可以确保快指针到达终点的时候慢指针到达了中点

反转后面一段链表
合并两个链表

// go
func reorderList(head *ListNode)  {
    mid := getMid(head)
    b := mid.Next
    mid.Next = nil
    a := revert(b)
    merge(head, a)
}

// 快慢指针获取链表中点
func getMid(head *ListNode) *ListNode {
    a, b := head, head
    for b != nil {
        if b.Next == nil {
            break
        }
        b = b.Next.Next
        a = a.Next
    }
    return a
}

// 反转链表
func revert(head *ListNode) *ListNode {
    var pre *ListNode
    for head != nil {
        temp := head.Next
        head.Next = pre
        pre = head
        head = temp
    }
    return pre
}

// 合并链表
func merge(a, b *ListNode) {
    for a != nil && b != nil {
        c := a.Next
        d := b.Next
        a.Next, b.Next = b, c
        a, b = c, d
    }
}

155. 最小栈

借用辅助栈，辅助栈栈顶维护主栈中的最小值
这样便可以

O(1)

调用主栈中的最小值

// cpp
class MinStack {
public:
    stack<int> sta1, sta2;
    MinStack() {
    }
    
    void push(int val) {
        sta1.push(val);
        sta2.push(min(getMin(), val));
    }
    
    void pop() {
        if (!sta1.empty()) {
            sta1.pop();
            sta2.pop();
        }
    }
    
    int top() {
        return sta1.top();
    }
    
    int getMin() {
        if (!sta2.empty()) return sta2.top();
        else return 2147483647;
    }
};

232. 用栈实现队列

维护两个栈

A,\ B

，其中

维护输入序列，

维护输出序列

每当需要 pop, peek 的时候，将

的元素全部 push 到

中去

每个元素只入栈出栈各

次，因此均摊复杂度为

O(1)

// cpp
class MyQueue {
public:
    stack<int> sta1, sta2;
    MyQueue() {

    }
    void mv() {
        if (sta2.empty()) {
            while (!sta1.empty()) {
                sta2.push(sta1.top());
                sta1.pop();
            }
        }
    }
    void push(int x) {
        sta1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        mv();
        int ans = sta2.top(); sta2.pop();
        return ans;
    }
    
    /** Get the front element. */
    int peek() {
        mv();
        return sta2.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return sta1.empty() && sta2.empty();
    }
};

剑指 Offer 22. 链表中倒数第k个节点

// go
func getKthFromEnd(head *ListNode, k int) *ListNode {
    n := 0
    temp := head
    for temp != nil {
        n++
        temp = temp.Next
    }
    temp = head
    x := n - k + 1
    n = 0
    var ans *ListNode
    for temp != nil {
        n++
        if n == x {
            ans = temp
            break
        }
        temp = temp.Next
    }
    return ans
}

51. N 皇后

回溯

// go
func solveNQueens(n int) [][]string {
    ans := [][]string{}
    col := make(map[int]int)
    mp1 := make(map[int]int)
    mp2 := make(map[int]int)
    var dfs func(step, n int, temp []string)
    dfs = func(step, n int, temp []string) {
        if step == n {
            ans = append(ans, append([]string{}, temp...))
            return
        }
        row := make([]byte, n)
        for i := 0; i < n; i++ {
            row[i] = '.'
        }
        for i := 0; i < n; i++ {
            if (col[i] == 0 && mp1[i + step] == 0 && mp2[i - step] == 0) {
                col[i], mp1[i + step], mp2[i - step] = 1, 1, 1
                row[i] = 'Q'
                temp = append(temp, string(row))
                dfs(step + 1, n, temp)
                col[i], mp1[i + step], mp2[i - step] = 0, 0, 0
                row[i] = '.'
                temp = temp[:len(temp) - 1]
            }
        }
    }
    dfs(0, n, []string{})
    return ans
}

62. 不同路径

dp

// go
func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }
    dp[0][0] = 1
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i - 1 >= 0 {
                dp[i][j] += dp[i - 1][j]
            }
            if j - 1 >= 0 {
                dp[i][j] += dp[i][j - 1]
            }
        }
    }
    return dp[m - 1][n - 1]
}

剑指 Offer 09. 用两个栈实现队列

参考上面一样的题目

// cpp
class CQueue {
public:
    stack<int> s1, s2;
    CQueue() {
    }
    
    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {
        if (s2.empty()) {
            while (!s1.empty()) s2.push(s1.top()), s1.pop();
        }
        if (s2.empty()) return -1;
        else {
            int x = s2.top(); s2.pop();
            return x;
        }
    }
};

64. 最小路径和

二维动态规划

// go
func minPathSum(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }
    dp[0][0] = grid[0][0]
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i - 1 >= 0 {
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + grid[i][j])
            }
            if j - 1 >= 0 {
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + grid[i][j])
            }
        }
    }
    return dp[m - 1][n - 1]
}

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

72. 编辑距离 ✨

字符串下标从

开始

定义

dp[i][j]

表示

w_1,\ w_2

前

i,\ j

个位置，即 w1[1:i], w2[1:i] 的距离，从而进行转移

#define inf 0x3f3f3f3f
class Solution {
public:
    int minDistance(string w1, string w2) {
        if (w1 == "" && w2 == "") return 0;
        else if (w1 == "") return w2.length();
        else if (w2 == "") return w1.length();
        int m = w1.length(), n = w2.length();
        int dp[m + 1][n + 1];
        memset(dp, inf, sizeof(dp));
        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int j = 0; j <= n; ++j) dp[0][j] = j;
        dp[1][1] = (w1[0] != w2[0]);
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = min(dp[i - 1][j - 1] + (w1[i - 1] != w2[j - 1]), min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
            }
        }
        return dp[m][n];
    }
};

78. 子集

二进制枚举

// cpp
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        int N = 1 << n;
        vector<vector<int>> ans;
        for (int i = 0; i < N; ++i) {
            vector<int> temp;
            for (int j = 0; j < n; ++j) {
                if (i & (1 << j)) temp.push_back(nums[j]);
            }
            ans.push_back(temp);
        }
        return ans;
    }
};

// go
func subsets(nums []int) [][]int {
    n := len(nums)
    N := 1 << n
    ans := [][]int{}
    for i := 0; i < N; i++ {
        temp := []int{}
        for j := 0; j < n; j++ {
            if ((i >> j) & 1) == 1 {
                temp = append(temp, nums[j])
            }
        }
        ans = append(ans, temp)
    }
    return ans
}

79. 单词搜索

dfs

// go
func exist(board [][]byte, word string) bool {
    DX := []int{1, 0, -1, 0}
    DY := []int{0, -1, 0, 1}
    m, n := len(board), len(board[0])
    vis := make([][]bool, m)
    for i := 0; i < m; i++ {
        vis[i] = make([]bool, n)
    }
    var dfs func(x, y, step int) bool
    dfs = func(x, y, step int) bool {
        if word[step] != board[x][y] {
            return false
        }
        if step == len(word) - 1 {
            return true
        }
        for i := 0; i < 4; i++ {
            tx, ty := x + DX[i], y + DY[i]
            if tx >= 0 && tx < m && ty >= 0 && ty < n && !vis[tx][ty] {
                vis[tx][ty] = true
                if dfs(tx, ty, step + 1) {
                    return true
                }
                vis[tx][ty] = false
            }
        }
        return false
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            vis[i][j] = true
            if dfs(i, j, 0) {
                return true
            }
            vis[i][j] = false
        }
    }
    return false
}

83. 删除排序链表中的重复元素

设置一个 dummy
维护两个指针，分别指向前一个元素和当前元素
若当前元素和前一个元素相同，则删掉当前元素

// go
func deleteDuplicates(head *ListNode) *ListNode {
    pre := &ListNode {
        Val: -101,
        Next: head,
    }
    prev := pre
    for head != nil {
        if head.Val == prev.Val {
            prev.Next = head.Next
        } else {
            prev = prev.Next
        }
        head = head.Next
    }
    return pre.Next
}

82. 删除排序链表中的重复元素 II

设置两个 dummy
维护三个指针

// go
func deleteDuplicates(head *ListNode) *ListNode {
    b := &ListNode {
        Val: -101,
        Next: head,
    }
    a := &ListNode {
        Val: -102,
        Next: b,
    }
    p1, p2 := a, b
    for head != nil {
        if head.Val == p2.Val {
            for head != nil && head.Val == p2.Val {
                p2.Next = head.Next
                head = head.Next
            }
            p1.Next = head
            p2 = head
            if head == nil {
                break
            }
            head = head.Next
        } else {
            p1 = p1.Next
            p2 = p2.Next
            head = head.Next
        }
    }
    return b.Next
}

104. 二叉树的最大深度

dfs

// go
func maxDepth(root *TreeNode) int {
    var dfs func(root *TreeNode) int
    dfs = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        return 1 + max(dfs(root.Left), dfs(root.Right))
    }
    return dfs(root)
}
func max(a, b int) int {
    if a < b {
        return b
    } else {
        return a
    }
}

110. 平衡二叉树

记录一下左右子树的高度差即可
如果要判断是不是 BBST，需要记录 dfs 序，然后判断是否有序

// go
func isBalanced(root *TreeNode) bool {
    var dfs func(root *TreeNode) (int, bool)
    dfs = func(root *TreeNode) (int, bool) {
        if root == nil {
            return 0, true
        }
        h1, f1 := dfs(root.Left)
        h2, f2 := dfs(root.Right)
        if f1 && f2 && abs(h1 - h2) <= 1 {
            return max(h1, h2) + 1, true
        }
        return max(h1, h2) + 1, false
    }
    _, f := dfs(root)
    return f
}

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

func abs(a int) int {
    if a < 0 {
        return -a
    } else {
        return a
    }
}

114. 二叉树展开为链表 ✨

考虑递归
将左子树展开成链表，挂在根的右节点上
再把右子树展开成链表，挂在左子树的末尾的右节点上

// go
func flatten(root *TreeNode)  {
    var dfs func(root *TreeNode)
    dfs = func(root *TreeNode) {
        if root == nil {
            return
        }
        dfs(root.Left)
        dfs(root.Right)
        temp := root.Right
        root.Left, root.Right = nil, root.Left
        cur := root
        for cur.Right != nil {
            cur = cur.Right
        }
        cur.Right = temp
    }
    dfs(root)
}

122. 买卖股票的最佳时机 II

线性 dp，每一天的状态只和前一天有关

// cpp
class Solution {
public:
    int maxProfit(vector<int>& p) {
        int n = p.size();
        int dp[n + 1][2];
        dp[0][0] = 0, dp[0][1] = -p[0];
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            dp[i][0] = max(dp[i - 1][1] + p[i], dp[i - 1][0]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - p[i]);
        }
        return dp[n - 1][0];
    }
};

139. 单词拆分

定义

dp[i]

表示前

个字符组成的字符串能否由字典拼凑而成

枚举

，判断

j..i

是否在字典里即可

// go
func wordBreak(s string, wordDict []string) bool {
    dp := make([]bool, len(s) + 1)
    mp := make(map[string]bool)
    for _, v := range(wordDict) {
        mp[v] = true
    }
    dp[0] = true
    for i := 1; i <= len(s); i++ {
        for j := 0; j < i; j++ {
            if dp[j] && mp[s[j:i]] {
                dp[i] = true
            }
        }
    }
    return dp[len(s)]
}

144. 二叉树的前序遍历

前序遍历

// go
func preorderTraversal(root *TreeNode) []int {
    ans := []int{}
    var dfs func(root *TreeNode)
    dfs = func(root *TreeNode) {
        if root == nil {
            return
        }
        ans = append(ans, root.Val)
        dfs(root.Left)
        dfs(root.Right)
    }
    dfs(root)
    return ans
}

148. 排序链表

用 multiset 维护

// go
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        multiset<int> st;
        while (head) st.insert(head->val), head = head->next;
        ListNode *pre = new ListNode(0);
        ListNode *cur = pre;
        for (auto &i: st) cur->next = new ListNode(i), cur = cur->next;
        return pre->next;
    }
};

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

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

二叉树

node.js

编程算法

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

二叉树

node.js

编程算法

登录后参与评论

0 条评论

热度