func longestPalindrome(s string) string {
var (
array = []rune(s)
maxStr = ""
)
for i := 0; i < len(array); i++ {
// 寻找奇数长度的回文子串
oddStr := expandAroundCenter(array, i, i)
if len(oddStr) > len(maxStr) {
maxStr = oddStr
}
// 寻找偶数长度的回文子串
evenStr := expandAroundCenter(array, i, i+1)
if len(evenStr) > len(maxStr) {
maxStr = evenStr
}
}
return maxStr
}
func expandAroundCenter(s []rune, left, right int) string {
for left >= 0 && right < len(s) && s[left] == s[right] {
left--
right++
}
return string(s[left+1 : right])
}- 业务介绍的并不太好，项目解决了啥问题
- 开源的框架，定制开发，需要换位思考，让面试官能懂一些；主动询问面试官明白了没有；
- 数据模型是怎么构建的 再说技术点，解决了什么问题
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int maxLen = 0;// 用于记录最大不重复子串的长度
int left = 0;// 滑动窗口左指针
for (int i = 0; i < s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
left = Math.max(left, map.get(s.charAt(i)) + 1);
}
// 不管是否更新left，都要更新 s.charAt(i) 的位置！
map.put(s.charAt(i), i);
maxLen = Math.max(maxLen, i - left + 1);
}
return maxLen;
}
}type ListNode struct {
Val int
Next *ListNode
}func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
prev := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return prev
}翻转指定区间链表
func reverseBetween(head *ListNode, left int, right int) *ListNode {
if head == nil || left == right {
return head
}
var successor *ListNode
if left == 1 {
successor = reverseN(head, right)
} else {
head.Next = reverseBetween(head.Next, left-1, right-1)
successor = head
}
return successor
}
var successor *ListNode
// 翻转前 N 个节点
func reverseN(head *ListNode, n int) *ListNode {
if n == 1 {
successor = head.Next
return head
}
last := reverseN(head.Next, n-1)
head.Next.Next = head
head.Next = successor
return last
}func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
prev := new(ListNode)
currentNode := prev
for list1 != nil && list2 != nil {
if list1.Val < list2.Val {
currentNode.Next = list1
list1 = list1.Next
} else {
currentNode.Next = list2
list2 = list2.Next
}
currentNode = currentNode.Next
}
// 将剩余的接上
if list1 != nil {
currentNode.Next = list1
}
if list2 != nil {
currentNode.Next = list2
}
return prev.Next
}func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
if len(lists) == 1 {
return lists[0]
}
for i := 0; i + 1 < len(lists); i++ {
lists[i+1] = mergeTwoLists(lists[i], lists[i+1])
}
return lists[len(lists) - 1]
}
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
prev := new(ListNode)
currentNode := prev
for list1 != nil && list2 != nil {
if list1.Val < list2.Val {
currentNode.Next = list1
list1 = list1.Next
} else {
currentNode.Next = list2
list2 = list2.Next
}
currentNode = currentNode.Next
}
// 将剩余的接上
if list1 != nil {
currentNode.Next = list1
}
if list2 != nil {
currentNode.Next = list2
}
return prev.Next
}二分法优化
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
return mergeHelper(lists, 0, len(lists)-1)
}
func mergeHelper(lists []*ListNode, start, end int) *ListNode {
if start == end {
return lists[start]
}
if start < end {
mid := (start + end) / 2
left := mergeHelper(lists, start, mid)
right := mergeHelper(lists, mid+1, end)
return mergeTwoLists(left, right)
}
return nil
}快慢指针，快指针先领先n个位置，然后一起往后，当快指针为nil时，慢指针指向的位置就是需要删除的节点
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{0, head}
slow, fast := dummy, dummy
// 移动 fast 指针 N 步
for i := 0; i <= n; i++ {
fast = fast.Next
}
// 同时移动 slow 和 fast 指针
for fast != nil {
slow = slow.Next
fast = fast.Next
}
// 删除倒数第 N 个节点
slow.Next = slow.Next.Next
return dummy.Next
}动态规划的核心是：状态定义和状态转移方程
递归的时间复杂度是指数级别的，下面的代码会超时
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
def dfs(i):
if i < 0:
return 0
return max(dfs(i-1), dfs(i-2)+nums[i])
return dfs(n -1)这题我们可以先看成简单的回溯题，但是回溯时间复杂度是指数级别，比较高，我们可以缓存一下搜索到的结果
优化后我们可以看到现在这颗BST只有n个节点了，所以时间复杂度是O(n)
python代码如下
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
@cache
def dfs(i):
if i < 0:
return 0
return max(dfs(i - 1), dfs(i - 2) + nums[i])
# 回溯时间复杂度是指数级别
return dfs(n - 1)当然我们可以不用cache的装饰器，我们可以自己记录之前搜索过的值
func rob(nums []int) int {
// 缓存子问题的值
var (
n = len(nums)
cache = func() []int {
memo := make([]int, n)
for i := range memo {
memo[i] = -1 // -1 表示没有计算过
}
return memo
}()
)
var dfs func(int) int
dfs = func(index int) (res int) {
if index < 0 {
return
}
// 如果已经有子问题的解了 就不往下找了
if cache[index] != -1 {
return cache[index]
}
// 把问题拆分为最后一个元素 选与不选两种清空
res = max(dfs(index-1), dfs(index-2)+nums[index])
// 缓存结果
cache[index] = res
return res
}
return dfs(len(nums) - 1)
}
func max(i, j int) int {
if i > j {
return i
}
return j
}还能不能再优化下呢，我们仔细观察就能发现
我们可以将dfs改为数组，然后将递归改为循环，注意上面可能产生负数下标，所以进行+2
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
f = [0] * (n + 2)
for i, x in enumerate(nums):
f[i + 2] = max(f[i + 1], f[i] + x)
return f[n + 1]此时空间复杂度为O(n)，那么如何降到O(1)呢
class Solution:
def rob(self, nums: List[int]) -> int:
f0 = f1 = 0
for i, x in enumerate(nums):
new_f = max(f1, f0 + x)
f0 = f1
f1 = new_f
# f0, f1 = f1, max(f1, f0 + x)
return f1func rob(nums []int) int {
var f0, f1 int
for _, value := range nums {
f0, f1 = f1, max(f1, f0 + value)
}
println(f0)
return f1
}
func max(i, j int) int {
if i > j {
return i
}
return j
}背包问题是选或不选思想的体现
常见的0-1背包标准代码如下
# capacity 背包的容量
# w[i]:第 i 个物品的体积
# v[i]: 第 i 个物品的价值
# 返回所选物品体积和不超过capacity的前提下所能得到的最大价值和
def zero_one_knapsack(capacity: int, w: List[int], v: List[int]) -> int:
n = len(w)
@cache
def dfs(i, c):
if i < 0:
return 0
if c < w[i]:
return dfs(i - 1, c)
return max(dfs(i - 1, c), dfs(i - 1, c - w[i]) + v[i])
return dfs(n - 1, capacity)这题是01背包的变形
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# p = 添加正数的数的和
# s - p = 添加负数的数（s为总数）
# p - (s - p) = t (target 结果) => 2p - s = t
# p = (t + s) / 2
target += sum(nums)
if target < 0 or target % 2:
return 0
target //= 2
n = len(nums)
@cache
def dfs(i, c):
if i < 0:
return 1 if c == 0 else 0
if c < nums[i]:
return dfs(i - 1, c)
return dfs(i - 1, c) + dfs(i - 1, c - nums[i])
return dfs(n - 1, target)
# capacity 背包的容量
# w[i]:第 i 个物品的体积
# v[i]: 第 i 个物品的价值
# 返回所选物品体积和不超过capacity的前提下所能得到的最大价值和
def zero_one_knapsack(capacity: int, w: List[int], v: List[int]) -> int:
n = len(w)
@cache
def dfs(i, c):
if i < 0:
return 0
if c < w[i]:
return dfs(i - 1, c)
return max(dfs(i - 1, c), dfs(i - 1, c - w[i]) + v[i])
return dfs(n - 1, capacity)上面的代码时间复杂度为
o(n * target)，空间复杂度也一样这里空间复杂度还可以再优化一下
改成递推式
按照一比一的翻译
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# p = 添加正数的数的和
# s - p = 添加负数的数（s为总数）
# p - (s - p) = t (target 结果) => 2p - s = t
# p = (t + s) / 2
target += sum(nums)
if target < 0 or target % 2:
return 0
target //= 2
n = len(nums)
f = [[0] * (target + 1) for _ in range(n + 1)]
f[0][0] = 1
for i, x in enumerate(nums):
for c in range(target + 1):
if c < x:
f[i + 1][c] = f[i][c]
else:
f[i + 1][c] = f[i][c] + f[i][c - x]
return f[n][target]是不是可以再优化一下呢 当然是可以的 我们可以用一个数组并且倒着算来得到正确的结果
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
target += sum(nums)
if target < 0 or target % 2:
return 0
target //= 2
n = len(nums)
f = [[0] * (target + 1) for _ in range(2)]
f[0][0] = 1
for i, x in enumerate(nums):
for c in range(target + 1):
if c < x:
f[(i + 1) % 2][c] = f[i % 2][c]
else:
f[(i + 1) % 2][c] = f[i % 2][c] + f[i % 2][c - x]
return f[n % 2][target]当然也可以用回溯来做，但是回溯的时间复杂度是O(n^2)
func findTargetSumWays(nums []int, target int) (result int) {
var (
n = len(nums)
dfs func(i int, currentSum int)
)
dfs = func(i int, currentSum int) {
if i == n {
if currentSum == target {
result++
}
return
}
dfs(i + 1, currentSum + nums[i])
dfs(i + 1, currentSum - nums[i])
}
dfs(0, 0)
return
}记忆化搜索
func lengthOfLongestSubsequence(nums []int, target int) (result int) {
var (
n = len(nums)
dfs func(i, c int) int
memo = make([][]int, n)
)
for index := range memo {
memo[index] = make([]int, target+1)
}
dfs = func(i, c int) int {
if i < 0 {
if c == 0 {
return 0
}
return -10000
}
if memo[i][c] != 0 {
return memo[i][c]
}
if nums[i] > c {
return dfs(i - 1, c)
}
memo[i][c] = max(dfs(i - 1, c), dfs(i - 1, c - nums[i]) + 1)
return memo[i][c]
}
r := dfs(n - 1, target)
if r < 0 {
return -1
}
return r
}递推
func lengthOfLongestSubsequence(nums []int, target int) (result int) {
var (
n = len(nums)
dp = make([][]int, n + 1)
)
for i := range dp {
dp[i] = make([]int, target+1)
for j := range dp[i] {
dp[i][j] = -1 << 31 // 设置为最小值
}
}
dp[0][0] = 0
for i, x := range nums {
for c := 0; c <= target; c++ {
dp[i + 1][c] = max(dp[i][c], dp[i + 1][c])
if c >= x {
dp[i + 1][c] = max(dp[i][c - x] + 1, dp[i + 1][c])
}
}
}
result = dp[n][target]
if result <= 0 {
return - 1
}
return result
}优化空间
完全背包和01背包主要区别就是可以重复选择某个元素，所以递归的i并不需要减少
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
n = len(coins)
@cache
def dfs(i, c):
if i < 0:
return 0 if c == 0 else inf
if c < coins[i]:
return dfs(i - 1, c)
return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)
ans = dfs(n - 1, amount)
return ans if ans < inf else -1func coinChange(coins []int, amount int) int {
var (
n = len(coins)
dfs func(i, c int) int
memo = make([][]int, n)
)
for i := range memo {
memo[i] = make([]int, amount+1)
for j := range memo[i] {
memo[i][j] = -1 // 初始化为-1
}
}
dfs = func(i, c int) int {
if i < 0 {
if c == 0 {
return 0
} else {
return 100000 // 这里如果用math.MaxInt 会溢出变成负数
}
}
if memo[i][c] != -1 {
return memo[i][c]
}
if c < coins[i] {
return dfs(i-1, c)
}
cnt := min(dfs(i-1, c), dfs(i, c-coins[i])+1)
memo[i][c] = cnt
return cnt
}
result := dfs(n-1, amount)
if result == 100000 {
return -1
}
return result
}改成递推
func coinChange(coins []int, amount int) int {
max := amount + 1
dp := make([]int, amount+1)
for i := range dp {
dp[i] = max
}
dp[0] = 0
for i := 1; i <= amount; i++ {
for j := 0; j < len(coins); j++ {
if coins[j] <= i {
dp[i] = min(dp[i], dp[i-coins[j]]+1)
}
}
}
if dp[amount] == max {
return -1
}
return dp[amount]
}那啥时候是正序，啥时候是倒序呢
动态规划解法
func change(amount int, coins []int) int {
dp := make([]int, amount+1)
dp[0] = 1
for _, coin := range coins {
for i := coin; i <= amount; i++ {
dp[i] += dp[i-coin]
}
}
return dp[amount]
}
改成递推
递归+记忆化搜索 golang的会超时
func longestCommonSubsequence(text1 string, text2 string) int {
var (
n, m = len(text1), len(text2)
dfs func(i, j int) int
memo = make([][]int, n)
)
for index := range memo {
memo[index] = make([]int, m)
}
dfs = func(i, j int) int {
if i < 0 || j < 0 {
return 0
}
if memo[i][j] != 0 {
return memo[i][j]
}
if text1[i] == text2[j] {
return dfs(i - 1, j - 1) + 1
}
memo[i][j] = max(dfs(i - 1, j), dfs(i, j - 1))
return memo[i][j]
}
return dfs(n - 1, m - 1)
}改成递推
func longestCommonSubsequence(text1 string, text2 string) int {
var (
n, m = len(text1), len(text2)
dp = make([][]int, n + 1)
)
for index := range dp {
dp[index] = make([]int, m + 1)
}
for i, x := range text1 {
for j, y := range text2 {
if x == y {
dp[i + 1][j + 1] = dp[i][j] + 1
} else {
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
}
}
}
return dp[n][m]
}改成滚动数组
func longestCommonSubsequence(s, t string) int {
n, m := len(s), len(t)
f := [2][]int{make([]int, m+1), make([]int, m+1)}
for i, x := range s {
for j, y := range t {
if x == y {
f[(i+1)%2][j+1] = f[i%2][j] + 1
} else {
f[(i+1)%2][j+1] = max(f[i%2][j+1], f[(i+1)%2][j])
}
}
}
return f[n%2][m]
}
func max(a, b int) int { if a < b { return b }; return a }用一个数组优化下
func longestCommonSubsequence(s, t string) int {
m := len(t)
f := make([]int, m+1)
for _, x := range s {
pre := 0 // f[0]
for j, y := range t {
if x == y {
f[j+1], pre = pre+1, f[j+1]
} else {
pre = f[j+1]
f[j+1] = max(f[j+1], f[j])
}
}
}
return f[m]
}
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n = len(word1)
m = len(word2)
@cache
def dfs(i, j):
if i < 0:
return j + 1
if j < 0:
return i + 1
if word1[i] == word2[j]:
return dfs(i - 1, j - 1)
return min(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1)) + 1
return dfs(n - 1, m - 1)改成递推
两种思路
- 选或不选：为了比大小，需要知道上一个选的数字
- 枚举选哪个：比较当前选的数字和下一个要选的数字
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
@cache
def dfs(i):
res = 0
for j in range(i):
if nums[j] < nums[i]:
res = max(res, dfs(j))
return res + 1
return max(dfs(i) for i in range(n))回溯的时间复杂度是指数级别的
func letterCombinations(digits string) (result []string) {
var n = len(digits)
if n == 0 {
return nil
}
var mapping = [...]string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
var (
dfs func(i int)
path = make([]byte, n)
)
dfs = func(i int) {
if i == n {
result = append(result, string(path))
return
}
for _, value := range mapping[digits[i]-'0'] {
path[i] = byte(value)
dfs(i + 1)
}
}
dfs(0)
return
}回溯分为：
- 子集型回溯
- 组合型
- 排列型
下面是第一种子集型，一般会涉及到选与不选的情况
选与不选我们可以看下面的题
func subsets(nums []int) (result [][]int) {
var n = len(nums)
if n == 0 {
return nil
}
var (
dfs func(i int)
path = make([]int, 0)
)
dfs = func(i int) {
if i == n {
back := make([]int, len(path))
copy(back, path)
result = append(result, back)
return
}
// 不选 直接递归
dfs(i + 1)
// 选
path = append(path, nums[i])
dfs(i + 1)
// 回溯 恢复现场
path = path[:len(path) - 1]
}
dfs(0)
return
}上述时间复杂度为O(2^n * n)
还有一种思路是必须选一个数
func subsets(nums []int) (result [][]int) {
var n = len(nums)
if n == 0 {
return nil
}
var (
dfs func(i int)
path = make([]int, 0)
)
dfs = func(i int) {
back := make([]int, len(path))
copy(back, path)
result = append(result, back)
// if i == n {
// return
// }
// // 不选 直接递归
// dfs(i + 1)
for j := i; j < n; j++ {
// 选
path = append(path, nums[j])
dfs(j + 1)
// 回溯 恢复现场
path = path[:len(path) - 1]
}
}
dfs(0)
return
}我们再来看一题
组合型回溯可以进行剪枝
func combine(n int, k int) (result [][]int) {
var (
dfs func(i int)
path = make([]int,0, k)
)
dfs = func(i int) {
if len(path) == k {
var temp = make([]int, k)
copy(temp, path)
result = append(result, temp)
return
}
for j := n; j >= 1; j-- {
path = append(path, j)
dfs(j - 1)
path = path[:len(path)-1]
}
}
dfs(n)
return
}和组合型回溯不一样的时，在排列型回溯中，可以再次选择之前路径的元素
例如下面选择了[1, 2]后还可以选择[2, 1]
我们可以用回溯三问来构造这个问题
func permute(nums []int) (result [][]int) {
var (
n = len(nums)
path = make([]int, n)
dfs func(i int, s []int)
)
dfs = func(i int, s []int) {
if i == n {
tmp := make([]int, n)
copy(tmp, path)
result = append(result, tmp)
return
}
for _, value := range s {
path[i] = value
dfs(i + 1, RemoveElement(s, value))
}
return
}
dfs(0, nums)
return
}
func RemoveElement(slice []int, num int) []int {
var result []int
for _, value := range slice {
if value != num {
result = append(result, value)
}
}
return result
}时间复杂度：全排列的时间复杂度是
e * n!向下取整（可以通过泰勒展开式求出），用大O记法为O(n!)，但是这里还多了一个copy，所以就是O(n! * n)空间复杂度：o(n)
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
col = [0] * n
# def valid(r, c):
# for R in range(r):
# C = col[R]
# # 45°和135°是不是连线了
# if r+c == R+C or r-c == R-C:
# return False
# return True
def dfs(r, s):
if r == n:
ans.append(['.'*c + 'Q' + '.'*(n-1-c) for c in col])
return
for c in s:
# if valid(r, c):
if all(r+c != R+col[R] and r-c != R-col[R] for R in range(r)):
col[r] = c
dfs(r+1, s-{c})
dfs(0, set(range(n)))
return ans时间复杂度：
o(n^2 * n!)空间复杂度：o(n)
还可以再优化一下
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
col = [0] * n
on_path = [False] * n
m = 2*n -1
diag1 = [False] * m
diag2 = [False] * m
def dfs(r):
if r == n:
ans.append(['.'*c + 'Q' + '.'*(n-1-c) for c in col])
return
for c in range(n):
# 在py中数组负数索引也可以访问，其他语言diag2[r-c]这里可能会出现负数
if not on_path[c] and not diag1[r+c] and not diag2[r-c]:
col[r] = c
on_path[c] = diag1[r+c] = diag2[r-c] = True
dfs(r+1)
on_path[c] = diag1[r+c] = diag2[r-c] = False
dfs(0)
return ans时间复杂度：
o(n * n!)空间复杂度：o(n)
class Solution:
def totalNQueens(self, n: int) -> int:
ans = 0
col = [0] * n
# def valid(r, c):
# for R in range(r):
# C = col[R]
# # 45°和135°是不是连线了
# if r+c == R+C or r-c == R-C:
# return False
# return True
def dfs(r, s):
if r == n:
nonlocal ans
ans += 1
return
for c in s:
# if valid(r, c):
if all(r+c != R+col[R] and r-c != R-col[R] for R in range(r)):
col[r] = c
dfs(r+1, s-{c})
dfs(0, set(range(n)))
return ansfunc candy(ratings []int) int {
var (
n = len(ratings)
candies = make([]int, n)
)
candies[0] = 1
// 从左到右贪心
for i := 1; i < n; i++ {
if ratings[i] > ratings[i-1] {
candies[i] = candies[i-1] + 1
} else {
candies[i] = 1
}
}
// 从右往左贪心
for i := n - 2; i >= 0; i-- {
if ratings[i] > ratings[i+1] && candies[i] <= candies[i+1] {
candies[i] = candies[i+1] + 1
}
}
var sum = 0
for _, value := range candies {
sum += value
}
return sum
}贪心算法（Greedy Algorithm）是一种基于贪心策略的算法思想。贪心策略的核心思想是，在每一步选择中都选择当前状态下的最优解，以期望最终获得全局最优解。
在解决问题时，贪心算法每次选择局部最优解，不考虑该选择对未来的影响，并且认为通过一系列局部最优解的选择，可以达到全局最优解。贪心算法通常适用于满足"最优子结构"和"贪心选择性质"的问题。
"最优子结构"指的是问题的最优解包含了子问题的最优解。也就是说，通过解决子问题的最优解，可以得到原问题的最优解。
"贪心选择性质"指的是贪心算法通过局部最优解的选择，期望最终得到全局最优解。这意味着在每一步的选择中，贪心算法选择当前最优的解决方案，而不考虑其他选择所带来的影响。
在解决问题时，贪心算法不保证能够得到全局最优解，因为它没有考虑所有可能的解决方案。但在一些问题中，贪心算法能够给出近似最优解或者满足问题要求的解。
在分发糖果的问题中，贪心算法的思路是先从左到右遍历一次评分数组，保证相邻两个孩子评分更高的孩子获得更多的糖果；然后再从右到左遍历一次评分数组，确保相邻两个孩子评分更高的孩子获得更多的糖果。通过贪心策略，每次都选择当前最优解，最终得到满足要求的最少糖果数目。
这个题还没做过 mark一下
func coinChange(coins []int, amount int) int {
// 初始化 dp 数组
dp := make([]int, amount+1)
for i := 1; i <= amount; i++ {
dp[i] = math.MaxInt32
}
// 动态规划计算最少硬币个数
for i := 1; i <= amount; i++ {
for _, coin := range coins {
if i-coin >= 0 && dp[i-coin] != math.MaxInt32 {
dp[i] = min(dp[i], dp[i-coin]+1)
}
}
}
if dp[amount] == math.MaxInt32 {
return -1
}
return dp[amount]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func buildTree(inorder, postorder []int) *TreeNode {
n := len(postorder)
if n == 0 { // 空节点
return nil
}
leftSize := slices.Index(inorder, postorder[n-1]) // 左子树的大小
left := buildTree(inorder[:leftSize], postorder[:leftSize])
right := buildTree(inorder[leftSize+1:], postorder[leftSize:n-1])
return &TreeNode{postorder[n-1], left, right}
}可以先分类讨论
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || root == p || root == q {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
// 如果左右都有 说明单前节点比他们都高
if left != nil && right != nil {
return root
}
if left != nil {
return left
}
return right
}func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// 由题意可得 当前节点肯定不会是空间点
x := root.Val
if p.Val < x && q.Val < x {
return lowestCommonAncestor(root.Left, p, q)
}
if p.Val > x && q.Val > x {
return lowestCommonAncestor(root.Right, p, q)
}
return root
}二分查找有很多种写法
- 闭区间
- 开区间
- 半闭半开
// lowerBound 返回最小的满足 nums[i] >= target 的 i
// 如果数组为空，或者所有数都 < target，则返回 len(nums)
// 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
// 闭区间写法
func lowerBound(nums []int, target int) int {
left, right := 0, len(nums)-1 // 闭区间 [left, right]
for left <= right { // 区间不为空
// 循环不变量：
// nums[left-1] < target
// nums[right+1] >= target
mid := left + (right-left)/2
if nums[mid] < target {
left = mid + 1 // 范围缩小到 [mid+1, right]
} else {
right = mid - 1 // 范围缩小到 [left, mid-1]
}
}
return left
}
// 左闭右开区间写法
func lowerBound2(nums []int, target int) int {
left, right := 0, len(nums) // 左闭右开区间 [left, right)
for left < right { // 区间不为空
// 循环不变量：
// nums[left-1] < target
// nums[right] >= target
mid := left + (right-left)/2
if nums[mid] < target {
left = mid + 1 // 范围缩小到 [mid+1, right)
} else {
right = mid // 范围缩小到 [left, mid)
}
}
return left // 返回 left 还是 right 都行，因为循环结束后 left == right
}
// 开区间写法 相当于返回插入位置（即第一个大于等于目标元素的位置）
// [35. 搜索插入位置](https://leetcode.cn/problems/search-insert-position/)
func lowerBound3(nums []int, target int) int {
left, right := -1, len(nums) // 开区间 (left, right)
for left+1 < right { // 区间不为空
// 循环不变量：
// nums[left] < target
// nums[right] >= target
mid := left + (right-left)/2
if nums[mid] < target {
left = mid // 范围缩小到 (mid, right)
} else {
right = mid // 范围缩小到 (left, mid)
}
}
return right
}java版本的比较简单，就是LinkedHashMap中使用hashMap维护节点快速插入寻找，使用双向链表维护顺序
简单介绍LinkedHashMap（跟题目有关的知识点） HashMap 大家都清楚，底层是 数组 + 红黑树 + 链表 （不清楚也没有关系），同时其是无序的，而 LinkedHashMap 刚好就比 HashMap 多这一个功能，就是其提供 有序，并且，LinkedHashMap的有序可以按两种顺序排列，一种是按照插入的顺序，一种是按照 读取 的顺序（这个题目的示例就是告诉我们要按照读取的顺序进行排序），而其内部是靠 建立一个双向链表 来维护这个顺序的，在每次插入、删除后，都会调用一个函数来进行 双向链表的维护 ，准确的来说，是有三个函数来做这件事，这三个函数都统称为 回调函数 ，这三个函数分别是：
void afterNodeAccess(Node<K,V> p) { } 其作用就是在访问元素之后，将该元素放到双向链表的尾巴处(所以这个函数只有在按照读取的顺序的时候才会执行)，之所以提这个，是建议大家去看看，如何优美的实现在双向链表中将指定元素放入链尾！ void afterNodeRemoval(Node<K,V> p) { } 其作用就是在删除元素之后，将元素从双向链表中删除，还是非常建议大家去看看这个函数的，很优美的方式在双向链表中删除节点！ void afterNodeInsertion(boolean evict) { } 这个才是我们题目中会用到的，在插入新元素之后，需要回调函数判断是否需要移除一直不用的某些元素！ 其次，我再介绍一下 LinkedHashMap 的构造函数！ 其主要是两个构造方法，一个是继承 HashMap ，一个是可以选择 accessOrder 的值(默认 false，代表按照插入顺序排序)来确定是按插入顺序还是读取顺序排序
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
// 这个可不写
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}golang
type LRUCache struct {
capacity int
cache map[int]*Node
head *Node
tail *Node
}
type Node struct {
key int
value int
prev *Node
next *Node
}
func Constructor(capacity int) LRUCache {
head := &Node{}
tail := &Node{}
head.next = tail
tail.prev = head
return LRUCache{
capacity: capacity,
cache: make(map[int]*Node),
head: head,
tail: tail,
}
}
func (this *LRUCache) Get(key int) int {
if node, ok := this.cache[key]; ok {
this.moveToHead(node)
return node.value
}
return -1
}
func (this *LRUCache) Put(key int, value int) {
if node, ok := this.cache[key]; ok {
node.value = value
this.moveToHead(node)
} else {
newNode := &Node{
key: key,
value: value,
}
this.cache[key] = newNode
this.addToHead(newNode)
if len(this.cache) > this.capacity {
removedNode := this.removeTail()
delete(this.cache, removedNode.key)
}
}
}
func (this *LRUCache) addToHead(node *Node) {
node.prev = this.head
node.next = this.head.next
this.head.next.prev = node
this.head.next = node
}
func (this *LRUCache) removeNode(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (this *LRUCache) moveToHead(node *Node) {
this.removeNode(node)
this.addToHead(node)
}
func (this *LRUCache) removeTail() *Node {
node := this.tail.prev
this.removeNode(node)
return node
}func zigzagLevelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
var (
q = NewQueue[*TreeNode]()
result [][]int
level int
)
q.offer(root)
for !q.isEmpty() {
level++
n := q.size()
subArr := make([]int, n)
for i := 0; i < n; i++ {
element := q.peek()
subArr[i] = element.Val
if element.Left != nil {
q.offer(element.Left)
}
if element.Right != nil {
q.offer(element.Right)
}
}
if level%2 == 0 {
// 偶数层，反转子数组
reverse(subArr)
}
result = append(result, subArr)
}
return result
}
// 反转切片
func reverse(arr []int) {
left, right := 0, len(arr)-1
for left < right {
arr[left], arr[right] = arr[right], arr[left]
left++
right--
}
}
type Queue[T any] struct {
array []T
len int
}
func NewQueue[T any]() *Queue[T] {
return &Queue[T]{array: make([]T, 0)}
}
func (q *Queue[T]) offer(element ...T) {
// 1. 添加元素
q.array = append(q.array, element...)
q.len += len(element)
}
// 从切片的第一个元素弹出
func (q *Queue[T]) peek() (element T) {
if q.len < 1 {
panic("cannot pop empty queue !")
}
element = q.array[0]
// 移除第一个元素
q.array = q.array[1:]
q.len--
return
}
func (q *Queue[T]) isEmpty() bool {
return q.len == 0
}
func (q *Queue[T]) size() int {
return q.len
}func reverse(x int) int {
y := 0
for x !=0{
if y < math.MinInt32/10 || y > math.MaxInt32/10 {
return 0
}
temp := x%10
y = y*10+temp
x /= 10
}
return y
}