字节跳动面试中的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实现。通过理解和练习这些题目,你可以更好地准备技术面试,同时也能够提高自己的编程技巧。希望这篇文章对你有所帮助,祝你在面试中取得优异成绩!
附录
-
推荐阅读:
-
工具列表:
- PyCharm(Python IDE)
- GoLand(Golang IDE)
- Visual Studio Code(多语言编辑器)
这篇文章涵盖了从基础到高级的不同难度级别的算法题目,并提供了详细的Python和Golang实现。无论是初学者还是有经验的开发者,都可以从中受益。如果你有任何疑问或需要进一步的帮助,请随时留言讨论!
网友评论