字节跳动面试中的10个独特算法题目及Python/Golang实

字节跳动面试中的10个独特算法题目及Python/Golang实现

引言

字节的算法面试可以用变态形容，本文精选了十个不常出现在其他公司面试中的算法题目，并提供了Python和Golang的实现代码。这些题目涵盖了不同的数据结构和算法概念，能够帮助你更全面地准备面试。

---

1. 字符串解码 (Decode String)

题目描述：
给定一个经过编码的字符串 s，请你编写一个解码函数，返回其解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 总是正整数。

Python 实现：

def decodeString(s: str) -> str:
    stack = []
    current_num = 0
    current_string = ""
    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == '[':
            stack.append((current_string, current_num))
            current_string, current_num = "", 0
        elif char == ']':
            prev_string, num = stack.pop()
            current_string = prev_string + num * current_string
        else:
            current_string += char
    return current_string

Golang 实现：

func decodeString(s string) string {
    var stack [][2]interface{}
    currentNum := 0
    currentString := ""

    for _, char := range s {
        if char >= '0' && char <= '9' {
            currentNum = currentNum*10 + int(char-'0')
        } else if char == '[' {
            stack = append(stack, [2]interface{}{currentString, currentNum})
            currentString, currentNum = "", 0
        } else if char == ']' {
            last := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            prevString := last[0].(string)
            num := last[1].(int)
            currentString = prevString + strings.Repeat(currentString, num)
        } else {
            currentString += string(char)
        }
    }
    return currentString
}

---

2. 岛屿数量 (Number of Islands)

题目描述：
给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。岛屿总是被水包围，并且每个岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

Python 实现：

def numIslands(grid):
    def dfs(grid, i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '#'  # mark as visited
        dfs(grid, i+1, j)
        dfs(grid, i-1, j)
        dfs(grid, i, j+1)
        dfs(grid, i, j-1)

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(grid, i, j)
                count += 1
    return count

Golang 实现：

func numIslands(grid [][]byte) int {
    var dfs func(i, j int)
    dfs = func(i, j int) {
        if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] != '1' {
            return
        }
        grid[i][j] = '#'
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    }

    count := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' {
                dfs(i, j)
                count++
            }
        }
    }
    return count
}

---

3. 单词拆分 (Word Break)

题目描述：
给定一个非空字符串 s 和一个包含非空单词列表的 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

Python 实现：

def wordBreak(s, wordDict):
    wordSet = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True

    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break

    return dp[len(s)]

Golang 实现：

func wordBreak(s string, wordDict []string) bool {
    wordSet := make(map[string]bool)
    for _, word := range wordDict {
        wordSet[word] = true
    }

    dp := make([]bool, len(s)+1)
    dp[0] = true

    for i := 1; i <= len(s); i++ {
        for j := 0; j < i; j++ {
            if dp[j] && wordSet[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }

    return dp[len(s)]
}

---

4. 最长递增子序列 (Longest Increasing Subsequence)

题目描述：
给定一个未排序的整数数组 nums，找到最长递增子序列的长度。

Python 实现：

def lengthOfLIS(nums):
    if not nums:
        return 0

    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Golang 实现：

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    dp := make([]int, len(nums))
    for i := range dp {
        dp[i] = 1
    }

    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }

    maxLen := 0
    for _, v := range dp {
        if v > maxLen {
            maxLen = v
        }
    }
    return maxLen
}

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

---

5. 最小编辑距离 (Edit Distance)

题目描述：
给定两个单词 word1 和 word2，计算将 word1 转换为 word2 所使用的最少操作数。你可以对一个单词进行插入、删除或替换一个字符。

Python 实现：

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

    return dp[m][n]

Golang 实现：

func minDistance(word1, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 0; i <= m; i++ {
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            }
        }
    }

    return dp[m][n]
}

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

---

6. 二叉树的最大路径和 (Binary Tree Maximum Path Sum)

题目描述：
给定一个非空二叉树，返回其最大路径和。路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中不能出现两次。

Python 实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root):
    max_sum = float('-inf')

    def helper(node):
        nonlocal max_sum
        if not node:
            return 0

        left_gain = max(helper(node.left), 0)
        right_gain = max(helper(node.right), 0)

        price_newpath = node.val + left_gain + right_gain

        max_sum = max(max_sum, price_newpath)

        return node.val + max(left_gain, right_gain)

    helper(root)
    return max_sum

Golang 实现：

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

var maxSum int

func maxPathSum(root *TreeNode) int {
    maxSum = math.MinInt32
    helper(root)
    return maxSum
}

func helper(node *TreeNode) int {
    if node == nil {
        return 0
    }

    leftGain := max(0, helper(node.Left))
    rightGain := max(0, helper(node.Right))

    priceNewPath := node.Val + leftGain + rightGain

    maxSum = max(maxSum, priceNewPath)

    return node.Val + max(leftGain, rightGain)
}

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

---

7. 课程表 (Course Schedule)

题目描述：
现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]。给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习。

Python 实现：

from collections import defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    indegrees = [0] * numCourses

    for dest, src in prerequisites:
        graph[src].append(dest)
        indegrees[dest] += 1

    queue = [i for i in range(numCourses) if indegrees[i] == 0]
    visited = 0

    while queue:
        node = queue.pop(0)
        visited += 1
        for neighbor in graph[node]:
            indegrees[neighbor] -= 1
            if indegrees[neighbor] == 0:
                queue.append(neighbor)

    return visited == numCourses

Golang 实现：

func canFinish(numCourses int, prerequisites [][]int) bool {
    graph := make(map[int][]int)
    indegrees := make([]int, numCourses)

    for _, pre := range prerequisites {
        dest, src := pre[0], pre[1]
        graph[src] = append(graph[src], dest)
        indegrees[dest]++
    }

    queue := []int{}
    for i := 0; i < numCourses; i++ {
        if indegrees[i] == 0 {
            queue = append(queue, i)
        }
    }

    visited := 0
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        visited++

        for _, neighbor := range graph[node] {
            indegrees[neighbor]--
            if indegrees[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }

    return visited == numCourses
}

---

8. 接雨水 (Trapping Rain Water)

题目描述：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

Python 实现：

def trap(height):
    if not height:
        return 0

    left, right = 0, len(height) - 1
    maxLeft, maxRight = 0, 0
    waterTrapped = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= maxLeft:
                maxLeft = height[left]
            else:
                waterTrapped += maxLeft - height[left]
            left += 1
        else:
            if height[right] >= maxRight:
                maxRight = height[right]
            else:
                waterTrapped += maxRight - height[right]
            right -= 1

    return waterTrapped

Golang 实现：

func trap(height []int) int {
    if len(height) == 0 {
        return 0
    }

    left, right := 0, len(height)-1
    maxLeft, maxRight := 0, 0
    waterTrapped := 0

    for left < right {
        if height[left] < height[right] {
            if height[left] >= maxLeft {
                maxLeft = height[left]
            } else {
                waterTrapped += maxLeft - height[left]
            }
            left++
        } else {
            if height[right] >= maxRight {
                maxRight = height[right]
            } else {
                waterTrapped += maxRight - height[right]
            }
            right--
        }
    }

    return waterTrapped
}

---

9. 全排列 (Permutations)

题目描述：
给定一个没有重复数字的序列，返回其所有可能的全排列。

Python 实现：

def permute(nums):
    result = []

    def backtrack(path, remaining):
        if not remaining:
            result.append(path)
            return
        for i in range(len(remaining)):
            backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])

    backtrack([], nums)
    return result

Golang 实现：

func permute(nums []int) [][]int {
    var result [][]int

    var backtrack func(path, remaining []int)
    backtrack = func(path, remaining []int) {
        if len(remaining) == 0 {
            result = append(result, append([]int(nil), path...))
            return
        }
        for i := 0; i < len(remaining); i++ {
            newRemaining := append(append([]int(nil), remaining[:i]...), remaining[i+1:]...)
            backtrack(append(path, remaining[i]), newRemaining)
        }
    }

    backtrack([]int{}, nums)
    return result
}

---

10. 分割回文串 (Palindrome Partitioning)

题目描述：
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

Python 实现：

def partition(s):
    result = []

    def isPalindrome(sub):
        return sub == sub[::-1]

    def backtrack(start, path):
        if start == len(s):
            result.append(path)
            return
        for end in range(start + 1, len(s) + 1):
            if isPalindrome(s[start:end]):
                backtrack(end, path + [s[start:end]])

    backtrack(0, [])
    return result

Golang 实现：

func partition(s string) [][]string {
    var result [][]string

    isPalindrome := func(sub string) bool {
        for i := 0; i < len(sub)/2; i++ {
            if sub[i] != sub[len(sub)-1-i] {
                return false
            }
        }
        return true
    }

    var backtrack func(start int, path []string)
    backtrack = func(start int, path []string) {
        if start == len(s) {
            result = append(result, append([]string(nil), path...))
            return
        }
        for end := start + 1; end <= len(s); end++ {
            if isPalindrome(s[start:end]) {
                backtrack(end, append(path, s[start:end]))
            }
        }
    }

    backtrack(0, []string{})
    return result
}

---

结语

以上就是为字节跳动面试精心挑选的十个经典算法题目及其Python和Golang实现。通过理解和练习这些题目，你可以更好地准备技术面试，同时也能够提高自己的编程技巧。希望这篇文章对你有所帮助，祝你在面试中取得优异成绩！

---

附录

• 推荐阅读：

  • LeetCode
  • GeeksforGeeks
  • HackerRank

• 工具列表：

  • PyCharm（Python IDE）
  • GoLand（Golang IDE）
  • Visual Studio Code（多语言编辑器）

---

这篇文章涵盖了从基础到高级的不同难度级别的算法题目，并提供了详细的Python和Golang实现。无论是初学者还是有经验的开发者，都可以从中受益。如果你有任何疑问或需要进一步的帮助，请随时留言讨论！