文章目录
41. 复原 IP 地址
题目链接：93. 复原 IP 地址
题目描述
代码与解题思路
func restoreIpAddresses(s string) []string {
path, ans := make([]string, 0), make([]string, 0)
var dfs func(int)
dfs = func(start int) {
// start 作为的是起始字符位置
if len(path) == 4 {
// 分成四段了, 可以 return 了
if start == len(s) {
// 这里证明整个 s 已经走完了
str := strings.Join(path, ".")
ans = append(ans, str)
}
return
}
for i := start; i < len(s); i++ {
if i != start && s[start] == '0' {
// 含有前导 0，无效
break
}
str := s[start:i+1]
num, _ := strconv.Atoi(str) // 字符串转数字
if num >= 0 && num <= 255 {
// 符合 IP 的要求
path = append(path, str)
dfs(i+1)
path = path[:len(path)-1]
} else {
// 如果不满足条件，再往后也不可能满足条件，直接退出
break
}
}
}
dfs(0)
return ans
}
经典的 dfs 题目，题目的代码细节非常的多，必须非常细致的分析
- 如果已经将 ip 分成四段了，这种情况就已经走完了，就可以返回了
- 如果 start == len(s)，证明这次递归刚好用完所有字符，证明是一个正确情况，就追加到 ans 数组中
- 遍历 s 字符串，搜索每一种情况
- IP 地址不含前导零
- 将字符串转数字，判断是否符合 IP 地址 num >= 0 && num <= 255 的要求
- 如果符合条件，将该字符串追加到 path 数组，等到追加到四段就能判断是否符合条件了
- 继续 dfs 搜索，给 start 传 i+1，继续搜索 s 字符串之后的字符
42. 排序链表
题目链接：148. 排序链表
题目描述
代码与解题思路
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
mid := getMid(head) // 从中间分
next := mid.Next
mid.Next = nil
list1 := sortList(head) // 将链表分割
list2 := sortList(next)
return mergeSortList(list1, list2) // 归并排序
}
func getMid(head *ListNode) *ListNode {
slow, fast := head, head.Next
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
func mergeSortList(head1, head2 *ListNode) *ListNode {
phead := &ListNode{
}
prev := phead
for head1 != nil && head2 != nil {
if head1.Val < head2.Val {
prev.Next = head1
head1 = head1.Next
} else {
prev.Next = head2
head2 = head2.Next
}
prev = prev.Next
}
if head1 != nil {
prev.Next = head1
}
if head2 != nil {
prev.Next = head2
}
return phead.Next
}
这道题说实话并不难，思路太清晰了，先取中分割链表，然后进行归并排序，归并排序有两种实现方式，可以用迭代来实现，也可以用递归来实现，我推荐是用迭代的方法，实现起来最清晰，这里我都抽象出来：
迭代法，通过 prev 节点将两个有序链表合并成一个有序链表
func mergeSortList(head1, head2 *ListNode) *ListNode {
phead := &ListNode{
}
prev := phead
for head1 != nil && head2 != nil {
if head1.Val < head2.Val {
prev.Next = head1
head1 = head1.Next
} else {
prev.Next = head2
head2 = head2.Next
}
prev = prev.Next
}
if head1 != nil {
prev.Next = head1
}
if head2 != nil {
prev.Next = head2
}
return phead.Next
}
递归法，自行领悟：
func mergeSortList(head1, head2 *ListNode) *ListNode {
// 如果走到 next 了, 就让 next 直接接上另一个链表
if head1 == nil {
return head2
}
if head2 == nil {
return head1
}
// 哪个小就让哪个走 next
if head1.Val < head2.Val {
head1.Next = mergeSortList(head2, head1.Next)
return head1
} else {
head2.Next = mergeSortList(head1, head2.Next)
return head2
}
}
43. 下一个排列
题目链接：31. 下一个排列
题目描述
代码与解题思路
func nextPermutation(nums []int) {
i, j := len(nums)-2, len(nums)-1
for i >= 0 && nums[i] >= nums[i+1] {
i--
}
if i >= 0 {
for j >= 0 && nums[i] >= nums[j] {
j--
}
nums[i], nums[j] = nums[j], nums[i]
}
// reverse
l, r := i+1, len(nums)-1
for l < r {
nums[l], nums[r] = nums[r], nums[l]
l++
r--
}
}
难爆了，这思路谁想的出来：
先找一个 nums[i] < nums[i+1] 的数，然后找一个 nums[j] > nums[i] 的数，交换，然后让后面的区间反转
就是这个思路，我也不知道为什么可行，总之背下来准没错，算法苦手再次落泪了
44. x 的平方根
题目链接：69. x 的平方根
题目描述
代码与解题思路
func mySqrt(x int) (ans int) {
left, right := 0, x
for left <= right {
mid := left+(right-left)/2
if x < mid*mid {
right = mid-1
} else {
ans = mid
left = mid+1
}
}
return ans
}
这道题可以用二分的思路来做，记住要更新 ans，和二分的模板就行。
45. 爬楼梯
题目链接：70. 爬楼梯
题目描述
代码与解题思路
func climbStairs(n int) int {
dp := make([]int, n+1)
dp[0], dp[1] = 1, 1
for i := 2; i < n+1; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
最基础的 dp 算法，创建 dp 数组，初始化，根据状态转移方程填表。
46. 字符串转换整数 (atoi)
题目链接：8. 字符串转换整数 (atoi)
题目描述
代码与解题思路
func myAtoi(s string) (ans int) {
length := len(s)
// 去除前导空格
index := 0
for index < length {
if s[index] != ' ' {
break
}
index++
}
// 如果全是空格, 那就可以直接返回了
if index == length {
return 0
}
// 判断正负
sign := 1
if s[index] == '+' {
index++
} else if s[index] == '-' {
sign = -1
index++
}
// 将后续出现的数字字符进行转换
maxInt := math.MaxInt32
minInt := math.MinInt32
for index < length {
// 判断不合法的情况
if s[index] < '0' || s[index] > '9' {
break
}
// 字符转整形
num, _ := strconv.Atoi(string(s[index]))
// 题目要求只能存储 32 位大小的有符号整数
// ans 接下来会乘 10, 如果 ans*10 == maxInt, 那就比较 num 和 maxInt%10
if ans > maxInt/10 || (ans == maxInt/10 && num > maxInt%10) {
return maxInt
}
if ans < minInt/10 || (ans == minInt/10 && num > -(minInt%10)) {
return minInt
}
ans = ans*10 + num*sign
index++
}
return ans
}
这道题最重要的就是分析题目要求，把题目要求分析完善了，然后再对照着需求写代码就行了：
- 读入字符串并丢弃无用的前导空格
- 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果正。
- 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串其余部分将被忽略。
- 将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” ->32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 始）。
- 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 大于 231 − 1 的整数应该被固定为 231 − 1 。
- 返回整数作为最终结果。
按照这六个要求，逐个实现，代码中有清晰的注释信息引导了。
47. 括号生成
题目链接：22. 括号生成
题目描述
代码与解题思路
func generateParenthesis(n int) (ans []string) {
var dfs func(string, int, int)
dfs = func(s string, left, right int) {
if left < 0 || left > right {
return
}
if left == 0 && right == 0 {
ans = append(ans, s)
return
}
dfs(s+"(", left-1, right)
dfs(s+")", left, right-1)
}
dfs("", n, n)
return ans
}
这是一道经典的搜索题目，而这个解法是评论区的一个大佬想出来的，非常的巧妙，dfs 用的非常的传神，好好学习一下别人清晰的思路
48. 两数相加
题目链接：2. 两数相加
题目描述
代码与解题思路
如果说，LeetCode 第一题劝退了 90% 从第一题开始刷的铁头娃，那 LeetCode 的第二题，劝退了剩下的 99%。这就是我对这道题的评价。
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
nxtVal := 0
phead := &ListNode{
}
cur := phead;
for l1 != nil && l2 != nil {
sum := l1.Val + l2.Val + nxtVal
newnode := &ListNode{
Val: sum%10}
cur.Next = newnode
cur = cur.Next
nxtVal = sum/10
l1 = l1.Next
l2 = l2.Next
}
if l1 == nil {
for l2 != nil {
sum := l2.Val + nxtVal
newnode := &ListNode{
Val: sum%10}
cur.Next = newnode
cur = cur.Next
nxtVal = sum/10
l2 = l2.Next
}
}
if l2 == nil {
for l1 != nil {
sum := l1.Val + nxtVal
newnode := &ListNode{
Val: sum%10}
cur.Next = newnode
cur = cur.Next
nxtVal = sum/10
l1 = l1.Next
}
}
if nxtVal > 0 {
cur.Next = &ListNode{
Val: nxtVal, Next: nil}
}
return phead.Next
}
我这里就是非常经典的模拟操作，两个链表同时操作，然后再单独操作比较长的链表，最后特判一下进位的情况，代码比较屎山，但是我能够独立写出来
还有一种放法是题解的方法，代码简短且巧妙，但我想不出来这种解法，看看就好：
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
auto dummy = new ListNode(); // 哨兵节点
auto cur = dummy;
int carry = 0; // 进位
while (l1 || l2 || carry) {
// 有一个不是空节点，或者还有进位，就继续迭代
carry += (l1 ? l1->val : 0) + (l2 ? l2->val : 0); // 节点值和进位加在一起
cur = cur->next = new ListNode(carry % 10); // 每个节点保存一个数位
carry /= 10; // 新的进位
if (l1) l1 = l1->next; // 下一个节点
if (l2) l2 = l2->next; // 下一个节点
}
return dummy->next; // 哨兵节点的下一个节点就是头节点
}
};
49. 滑动窗口最大值
题目链接：239. 滑动窗口最大值
题目描述
代码与解题思路
func maxSlidingWindow(nums []int, k int) (ans []int) {
q := make([]int, len(nums))
for i, v := range nums {
// 维护单调队列, 把比 v 小的队尾全部踢出队列
for len(q) > 0 && nums[q[len(q)-1]] <= v {
q = q[:len(q)-1]
}
q = append(q, i)
// 如果滑动窗口大小超过 k, 就去出队头, 缩小滑动窗口
if i - q[0] >= k {
q = q[1:]
}
// 滑动窗口 >= k 之后, 就需要开始更新答案了
if i >= k-1 {
ans = append(ans, nums[q[0]])
}
}
return ans
}
看着不难，但是做起来不简单的题目，我一开始的思路是用优先级队列来做，理论上是可行的，但，go 手写堆我写不出来
用单调队列来做也行，不过得熟悉单调队列该怎么组织起来，最重要的就是每次入队前都要维护队列的单调性，用多几次估计就熟悉了。
50. 比较版本号
题目链接：165. 比较版本号
题目描述
代码与解题思路
func compareVersion(version1 string, version2 string) int {
arr1, arr2 := strings.Split(version1, "."), strings.Split(version2, ".")
for i := 0; i < max(len(arr1), len(arr2)); i++ {
val1, val2 := getVal(arr1, i), getVal(arr2, i)
if val1 > val2 {
return 1
} else if val1 < val2 {
return -1
}
}
return 0
}
func getVal(arr []string, i int) int {
if i < len(arr) {
ans, _ := strconv.Atoi(arr[i])
return ans
}
return 0
}
非常巧妙的调用 go 的库，必须学会：
- 先是用 strings.Split 将 string 根据分隔符切割成数组
- 然后用 strconv.Atoi 将 字符串转整数，最重要的是直接把前导零解决了
好好学习一下大佬的库使用
