代码随想录：额外题目

Hollis 收录于 Algorithm 和代码随想录

2024-05-15 2025-04-08 约 4400 字预计阅读 9 分钟 - 次阅读 - 条评论

数组

链表

两两交换链表中的节点

24. 两两交换链表中的节点

回文链表

234.回文链表

重排链表

143.重排链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


type ListNode struct {
    Val  int
    Next *ListNode
}
func main() {
    node5 := &ListNode{5, nil}
    node4 := &ListNode{4, node5}
    node3 := &ListNode{3, node4}
    node2 := &ListNode{2, node3}
    node1 := &ListNode{1, node2}
    reorderList(node1)
    for node1 != nil {
       fmt.Printf("%d ", node1.Val) // 1 5 2 4 3
       node1 = node1.Next
    }
}
func reorderList(head *ListNode) {
    // ......
}

分析

快慢指针，slow 和 fast，让 slow 指向链表最中间的位置，然后将链表的后半部分反转。 pre 为后面链表的头结点，两个指针，一个指向第 1 个链表，一个指向第 2 个链表，合并两个链表。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


func reorderList(head *ListNode) {
    slow, fast := head, head
    for fast != nil && fast.Next != nil && fast.Next.Next != nil {
       slow = slow.Next
       fast = fast.Next.Next
    }
    slowNext := slow.Next
    slow.Next = nil // 将slow的后一个位置置为空

    var pre *ListNode
    for slowNext != nil {
       temp := slowNext.Next
       slowNext.Next = pre
       pre = slowNext
       slowNext = temp
    }

    // 这里合并两个链表的逻辑上比较复杂的，需要理清
    headNext := head
    preNext := pre
    for preNext != nil {
       headNext = headNext.Next // 断开连接之前需要先记录下一个结点
       preNext = preNext.Next
       head.Next = pre
       head.Next.Next = headNext
       pre = preNext
       head = head.Next.Next
    }
}

环形链表

141. 环形链表

哈希表

同构字符串

205. 同构字符串

查找常用字符

1002. 查找常用字符

1
2
3
4
5
6
7
8
9


func main() {
    words := []string{"bella", "label", "roller"} // ["e","l","l"]
    //words := []string{"cool", "lock", "cook"} // [c o]
    r := commonChars(words)
    fmt.Println(r)
}
func commonChars(words []string) []string {
    // ......
}

分析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


func commonChars(words []string) []string {
    common := make(map[byte]int)
    tempComn := make(map[byte]int)
    for i := 0; i < len(words[0]); i++ {
       common[words[0][i]]++
    }
    for i := 1; i < len(words); i++ {
       tempComn = make(map[byte]int)
       for j := 0; j < len(words[i]); j++ {
          if oldCount, exist := common[words[i][j]]; exist {
             tempComn[words[i][j]]++
             if tempComn[words[i][j]] > oldCount { // 次数不能超过前面的次数
                tempComn[words[i][j]] = oldCount
             }
          }
       }
       common = tempComn
    }
    res := make([]string, 0)
    for str, count := range common {
       for count > 0 {
          res = append(res, string(str))
          count--
       }
    }
    return res
}

字符串

长按键入

925.长按键入

本题较为复杂，建议多加练习。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func main() {
    name := "alex"
    typed := "aaleexxx"
    //name := "alex"
    //typed := "aaleexa"
    //name := "saeed"
    //typed := "ssaaedd"
    r := isLongPressedName(name, typed)
    fmt.Println(r) // true
}
func isLongPressedName(name string, typed string) bool {
    // ......
}

分析

本题在自己做时，最先想到的就是：判断 name 是否是 typed 的子序列。

但这样写存在一个漏洞，如：name=“alex”，typed=“aaleexa”，出现非长按键入的字符无法判断。

这种写法的代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


func isLongPressedName(name string, typed string) bool {
	// 判断name和typed的最长公共子序列的长度maxLen是否和len(name)相等
	// dp[i][j]表示以name[i-1]和typed[j-1]结尾的两个字符串的最长公共子序列长度
	maxLen := 0
	dp := make([][]int, len(name)+1)
	for i := range dp {
		dp[i] = make([]int, len(typed)+1)
	}
	for i := 1; i <= len(name); i++ {
		for j := i; j <= len(typed); j++ {
			if name[i-1] == typed[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = dp[i][j-1]
			}
			if dp[i][j] > maxLen {
				maxLen = dp[i][j]
			}
		}
	}
	return maxLen == len(name)
}

为了不出现上面的问题，自己写了很久，怎么都不正确。

参考了答案，使用双指针来实现，这样双指针的处理还是比较巧妙的。

双指针：i 和 j。

如果 name[i] 和 typed[j] 相等，则同时将 i 和 j 加 1。
否则，如果 typed[j-1]==typed[j]，则说明 j 位置是前面字符的重复键入，只将 j 加 1。
如果上面两种情况都不满足，直接返回 false。

最后，如果 i 等于 len(name)，说明 name 字符串的每一个位置都参与了比较，返回 true。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func isLongPressedName(name string, typed string) bool {
    i, j := 0, 0
    for j < len(typed) { // 注意这里的遍历范围要遍历更大的typed，而不是name
       if i < len(name) && name[i] == typed[j] { // 两个位置相等，同时增加i和j的值
          i++
          j++
       } else if j > 0 && typed[j] == typed[j-1] { // 说明是重复键入的情况，只增加j的值
          j++
       } else { // 上面两种情况都不满足，说明键入了非长按字符，返回false
          return false
       }
    }
    return i == len(name)
}

比较含退格的字符串

844.比较含退格的字符串

二叉树

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

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

将二叉搜索树变平衡

1382.将二叉搜索树变平衡

相同的树

100. 相同的树

填充每个节点的下一个右侧节点指针

116. 填充每个节点的下一个右侧节点指针

N皇后II

52. N 皇后 II

贪心

Dota2参议院

649. Dota2 参议院

本题较难，建议多加理解和练习。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func main() {
	//senate := "DDRRR" // Dire
	//senate := "DDRRRR" // Radiant
	senate := "DRRD" // Dire
	//senate := "DRRDRDRDRDDRDRDR" // Radiant
	r := predictPartyVictory(senate)
	fmt.Println(r) // Dire
}
func predictPartyVictory(senate string) string {
    // ......
}

分析

自己写了很久都有问题，参考代码随想录，使用贪心算法。

贪心的策略是：尽量禁止自己后面的对手。

因为前面的对手已经使用过权利了，而后续的对手依然可以使用权利消灭自己的同伴。

使用 R 和 D 标记现存的数组中是否还有 R 和 D，如果不能同时满足 R&&D，则退出循环。

使用一个变量 flag 用于跟踪 R 和 D 之间的“优势”。如果 flag 为正，则 Radiant 在前；如果为负，则 Dire 在前。

遍历 senate，如果遇到的是 R，如果 flag<0，则消灭 R（置为 0），否则，R 标记为 true（数组中还有 R），最后将 flag++。

如果遇到的是 D，如果 flag>0，则消灭 D（置为 0），否则 D 标记为 true（数组中还有 D），最后将 flag–。

最后，R 和 D 变量只有一个为 true，返回对应的字符串即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


func predictPartyVictory(senate string) string {
    r, d := true, true
    flag := 0
    senateByte := []byte(senate)
    for r && d {
       r, d = false, false
       for i := 0; i < len(senateByte); i++ {
          if senateByte[i] == 'R' {
             if flag < 0 { // 删除该位置的R
                senateByte[i] = 0
             } else { // 保留该位置的R
                r = true
             }
             flag++
          } else if senateByte[i] == 'D' { // 由于我们删除元素不是真的删，而是置0，所以这里不能直接写else，而要判断是否等于D
             if flag > 0 {
                senateByte[i] = 0
             } else {
                d = true
             }
             flag--
          }
       }
    }
    //fmt.Println(senateByte)
    if r {
       return "Radiant"
    } else {
       return "Dire"
    }
}

分割平衡字符串

1221. 分割平衡字符串

动态规划

最长回文子串

5.最长回文子串

1
2
3
4
5
6
7
8
9


func main() {
    s := "aacabdkacaa"
    //s := "cbbd"
    r := longestPalindrome(s)
    fmt.Println(r) // aca
}
func longestPalindrome(s string) string {
    // ......
}

分析

dp[i][j]表示 i 到 j 位置是否是回文字符串，如果是，则dp[i][j]=true。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func longestPalindrome(s string) string {
	dp := make([][]bool, len(s))
	for i := range dp {
		dp[i] = make([]bool, len(s))
		dp[i][i] = true // 初始化dp数组
	}
	left, maxLen := 0, 1 // 回文串的左侧位置和长度
	for i := len(s) - 1; i >= 0; i-- {
		for j := i + 1; j < len(s); j++ {
			if s[i] == s[j] {
				// 如果 j==i+1 或 (i+1,j-1)之间的字符串是回文的，则i到j之间的字符串也是回文的
				if j == i+1 || dp[i+1][j-1] {
					dp[i][j] = true
					if j-i+1 > maxLen { // 更新左侧位置和最大长度
						left = i
						maxLen = j - i + 1
					}
				}
			}
		}
	}
	return s[left : left+maxLen]
}

分割回文串II

132. 分割回文串 II

1
2
3
4
5
6
7
8


func main() {
    s := "abbab"
    r := minCut(s)
    fmt.Println(r) // 1
}
func minCut(s string) int {
    // ......
}

分析

将 s 分割成全是回文的子串，需要的最少分割次数，我们使用动态规划来解决这个题。

dp[i] 表示 0 到 i 范围内，分割成回文子串，需要的最少次数为 dp[i]。

递推表达式，我们要对 [0, i] 范围内的字符串进行分割，分割位置为 j，如果 [j+1,i] 范围内的字符串为是回文的，则分割次数加 1。

我们要找到最少的分割次数，所以：dp[i] = min(dp[i], dp[j]+1)。

初始化 dp 数组：每个位置都应该是分割的最大值 i。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


func minCut(s string) int {
    dp := make([]int, len(s))
    for i := range dp {
       dp[i] = i
    }
    for i := 0; i < len(s); i++ {
       if isPalindrome(s[:i+1]) { // 如果0到i位置是回文的，则分割次数为0
          dp[i] = 0
          continue
       }
       for j := 0; j < i; j++ {
          if isPalindrome(s[j+1 : i+1]) {
             dp[i] = min(dp[i], dp[j]+1)
          }
       }
    }
    return dp[len(s)-1]
}
func isPalindrome(s string) bool {
    left, right := 0, len(s)-1
    for left < right {
       if s[left] != s[right] {
          return false
       }
       left++
       right--
    }
    return true
}

对上面的优化，在双重循环变量i和j时，都需要判断 [j+1: i] 位置是否是回文的，

为了减少计算的次数，我们可以把 [j+1: i] 位置是否是回文的存入到一个二维数组中。

这样，就用了两次 dp，一次计算 [i:j] 位置是否是回文的 isValid 数组，一次计算分割为回文字符串需要的最少次数。

如何判断 [i: j] 是否是回文的呢？

isValid[i][j]表示 [i: j]（包含 i 和 j ）位置的字符串是否是回文的，如果是，值为 true，否则值为 false。

递推表达式，如果 s[i]==s[j]，如果 isValid[i+1][j-1]==true，则 isValid[i][j] 值为 true。

初始化 isValid 数组，根据递推表达式，在遍历 i 时我们需要从大到小，遍历 j 时，我们需要从小到大。

应该初始化 i 和 j 相等时 isValid 数组的值，isValid[i][i]=true。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


func minCut(s string) int {
    isValid := make([][]bool, len(s))
    for i := range isValid {
       isValid[i] = make([]bool, len(s))
    }
    for i := range isValid {
       isValid[i][i] = true
    }
    for i := len(s) - 1; i >= 0; i-- {
       for j := i + 1; j < len(s); j++ {
          if s[i] == s[j] {
             if isValid[i+1][j-1] || j-i == 1 {
                isValid[i][j] = true
             }
          }
       }
    }
    dp := make([]int, len(s))
    for i := range dp {
       dp[i] = i
    }
    for i := 0; i < len(s); i++ {
       if isValid[0][i] { // 如果0到i位置是回文的，则分割次数为0
          dp[i] = 0
          continue
       }
       for j := 0; j < i; j++ {
          if isValid[j+1][i] {
             dp[i] = min(dp[i], dp[j]+1)
          }
       }
    }
    return dp[len(s)-1]
}

最长递增子序列的个数

673.最长递增子序列的个数

分析中的代码来自代码随想录，个人觉得本题过于复杂，先暂时跳过了。

1
2
3
4
5
6
7
8


func main() {
    nums := []int{1, 3, 5, 4, 7}
    r := findNumberOfLIS(nums)
    fmt.Println(r) // 2
}
func findNumberOfLIS(nums []int) int {
    // ......
}

分析

来自代码随想录的思路：

这道题可以说是 300.最长上升子序列的进阶版本。

1.确定 dp 数组（dp table）以及下标的含义

这道题目我们要一起维护两个数组。

dp[i]：i 之前（包括i）最长递增子序列的长度为 dp[i]

count[i]：以 nums[i] 为结尾的字符串，最长递增子序列的个数为count[i]

2.确定递推公式

在 300.最长上升子序列中，我们给出的状态转移是：

if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

即：位置 i 的最长递增子序列长度等于 j 从 0 到 i-1 各个位置的最长升序子序列 + 1的最大值。

本题就没那么简单了，我们要考虑两个维度，一个是dp[i]的更新，一个是count[i]的更新。

那么如何更新count[i]呢？

以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]。

那么在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 > dp[i]，说明找到了一个更长的递增子序列。

那么以j为结尾的子串的最长递增子序列的个数，就是最新的以i为结尾的子串的最长递增子序列的个数，即：count[i] = count[j]。

在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 == dp[i]，说明找到了两个相同长度的递增子序列。

那么以i为结尾的子串的最长递增子序列的个数就应该加上以j为结尾的子串的最长递增子序列的个数，即：count[i] += count[j]。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


func findNumberOfLIS(nums []int) int {
    size := len(nums)
    if size <= 1 {
       return size
    }
    dp := make([]int, size)
    for i, _ := range dp {
       dp[i] = 1
    }
    count := make([]int, size)
    for i, _ := range count {
       count[i] = 1
    }
    maxCount := 0
    for i := 1; i < size; i++ {
       for j := 0; j < i; j++ {
          if nums[i] > nums[j] {
             if dp[j]+1 > dp[i] {
                dp[i] = dp[j] + 1
                count[i] = count[j]
             } else if dp[j]+1 == dp[i] {
                count[i] += count[j]
             }
          }
          if dp[i] > maxCount {
             maxCount = dp[i]
          }
       }
    }
    result := 0
    for i := 0; i < size; i++ {
       if maxCount == dp[i] {
          result += count[i]
       }
    }
    return result
}

模拟

下一个排列

31.下一个排列

位运算

根据数字二进制下 1 的数目排序

1356. 根据数字二进制下 1 的数目排序

收录于合集・代码随想录 7

代码随想录：动态规划代码随想录：单调栈