leetcode 刷题记录

1. 3. Longest Substring Without Repeating Characters 这道题忘了两点：

1. 无论如何都要刷新m[rightIndex]

2. 需要从map中删除从老的left到新的left之间的全部的元素

2. 5. Longest Palindromic Substring 错误

1. 使用dfs的时候，应该是i>j都直接返回true。开始写成了j<0才返回true。这是根本的逻辑错误

dfs = func(i, j int) bool { if cache[i][j] != 0 { return cache[i][j] == 1 } if i > j { cache[i][j] = 1 return true }

2. cache采用map。超时，修改为数组的cache才通过

3. 修改为数组的cache就有负的index的问题。因此增加了修改，杜绝负index入cache的情况

if i == j || i == j-1 { cache[i][j] = 1 return true }

增加了剪枝，效果有一点，不够好

for i := 0; i < len(s); i++ {if maxLength >= len(s)-i { break }for j := 0; j < len(s); j++ { if dfs(i, j) { if maxLength < j-i+1 { maxLength = j - i + 1 maxString = s[i : j+1] } } } }

3. 133. Clone Graph 错误原因：

1. 将visited := map[int]*Node{}写成了visited := map[int]bool。然后

dfs = func(node *Node) *Node { if node == nil { return nil } if visited[node.Val] { return node }

这样导致node返回的是原始的节点不是真实的copy后的节点。因此这里需要记录的是copy后的节点的内容

2. 差点忘了记录当前copy后的节点到visited中

3. 没有考虑nil指针的情况。

if node == nil { return nil }