Eagle233-Blog

[Algorithm] 算法训练 202609

2026-09-02 17:13:21   2026-09-02 17:13:21
Categories Algorithms
Tags

3.3k Words   |   12 Minutes

LeetCode 算法动画演示集

20260902

  • 59. 螺旋矩阵 II 左开右闭
  • 58. 区间和（第九期模拟笔试） 熟悉一下 Go 中标准输入输出的写法： 
    package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	
	var n int
	fmt.Fscan(in, &n)
	
	...
	
	// 连续读入
	for {
		var a, b int
		if _, err := fmt.Fscan(in, &a, &b); err != nil {
			break
		}
		
		...
		
		fmt.Fprintln(out, arr[b] - arr[a - 1])
	}
}

20260903

  • 44. 开发商购买土地（第五期模拟笔试） slices.Copy min() max() (Go 1.21) copy(dst, src) math.MaxInt 自己写abs函数
    • 对于 min() max()，无类型常量可以相互运算，结果可以近似理解为 x + y。但是例如 float64 int 之间不可以运算。string 之间可以运算（字典序），但是 slices, map 都不可以。
    • slices.Clone() min() max() 都是 Go 1.21 后才加入的，math.MaxInt 是 Go 1.17 才加入的 
      mmin = int(^uint(0) >> 1) // 无符号数逻辑右移
    • Go 中左移右移规则与 C 基本一致，但是
      1. 允许移位次数 >= 位宽（C 中 Undefined，编译器可以假设不会出现这种情况并且对这种情况进行优化）
      2. 不允许右操作数为负数
        • 常量为负：编译错误
        • 运行时计算出来的为负：runtime panic
      3. 负的有符号数右移作算数右移（C 中 Implementation-define，GCC/Clang/MSVC 都是算数右移）
      4. 左移发生溢出，有具体整数类型直接按照位宽截断（C 中 Undefined，编译器可以假设不会出现这种情况并且进行优化）
        • 无类型整数常量没有固定的位宽，在编译器可以使用任意精度：const x = 1 << 100
    • Go 中的 make([]T, n) 会创造 n 个元素，每个元素为 T 的零值
      1. 值
        • 所有整数：0
        • 所有浮点：0
        • complex64/128 （复数，实部和虚部都是 float32/64 ）：0+0i 
          var z complex128 = 3 + 4i
z := complex(3.0, 4.0)
fmt.Println(real(z)) // 3
fmt.Println(imag(z)) // 4
        • bool：false
        • string：""
      2. 引用/指针：nil
        • *T
        • []T
        • map
        • chan
        • func
        • interface
      3. 数组和 struct 内部成员递归取零值 
        var a [3]int // [0, 0, 0]
type Person struct {
	age  int    // 0
	name string // ""
	ok   bool   // false
}
      4. interface typed nil != nil (BUT why???)
  • 203. 移除链表元素 Go 中不需要手动 free()
  • 206. 反转链表 递归不会做了呀…双指针也忘记了
  • 142. 环形链表 II 主要想一下数学推导如何来的

20260904

对 Golang 的语法太不熟悉了。。。基本上都是语法上的问题

20260905

  • 541. 反转字符串 II slices.Reverse()；显式类型转换
  • 54. 替换数字（第八期模拟笔试）
    • slices.Clone() 里的参数必须是 slice，而 copy(dst, src) 中，dst 如果是 []byte / []rune， src 可以是 string
    • 对于标准输入，如果想要读入 string，可以用 []byte；但是如果想要用 []rune，需要： 
      var s string
fmt.Fscan(in, &s)
s1 := []rune(s)
    • 对于这题还是不用 rune unicode.IsDigit() 了…
    • byte == uint8 表示一个字节；rune == int32 表示一个 Unicode 码点
    • string 是不可变字节序列，s[i] 取出来的是 byte，但是遍历 s 取出来的是 rune 
      s := "a你好"
for i, r := range s {
	fmt.Fprintln(out, i, r)
}
      这里的 i 只有可能是 0 1 4 （表示的是 UTF-8 字节序列的起始下标，中文占 3 bytes）
  • 151. 反转字符串中的单词 库函数和手写两种方法
    • strings.Join([]string, " ") strings.Fields()
    • 几种修改 len or cap 的操作（通常 resize 用第一个）： 
      s = s[:n] // len == n
s = s[:n:n] // len == cap == n
s = slices.Clip(s) // 同上
s = slices.Clone(s) // 产生新的底层数组

20260908

20260909

20260910

20260913

20260914

20260915

20260916

20260917

回溯法：限制/不限制数量，重复/不重复 收集答案时的数组一定要拷贝

  • 77. 组合 剪枝
  • 39. 组合总和 如何剪枝
  • 40. 组合总和 II 去重，很像四数之和
  • 131. 分割回文串 dp回文
  • 93. 复原 IP 地址
    对于组合问题的去重，如果可以sort，那就直接用四数之和一样的做法（或者used数组）；如果不能sort就用set，并且set一定得在每一层初始化（树层去重，值作为key）。前者也可以用set，但是一定要sort再使用
  • 491. 非递减子序列 used数组（本质就是set） / set 不可以sort
  • 40. 组合总和 II 去重不能用set（除非sort）
    对于排列问题的去重，used数组一定要在层外初始化（树枝去重，下标作为key）
  • 46. 全排列 因为不重复，所以可以用值作为key
  • 47. 全排列 II 和上一题相比可以重复，所以不可以用值作为set的key，必须要是下标（否则会漏情况）；要排序，因为也要做树层去重
    所以树层去重如果要用used数组一定要排序，不排序只能用set
    AI总结一下：
1. 先问：为什么会重复？

2. 如果是“同一条路径不能重复使用同一个元素”
   → 树枝限制
   → used[index]

3. 如果是“同一层不能用相同的值开重复分支”
   → 树层去重

   能排序：
   → sort
   → 利用相邻相同元素去重

   不能排序：
   → 每层 set / used[value]

4. 如果是排列：
   → 每层都从 0 开始枚举
   → 往往需要 used[index] 判断当前路径哪些元素用过

5. 如果是组合：
   → 有 startIndex
   → 下一层从 i+1 开始
   → startIndex 本身就限制了元素不能回头使用

最后一点 startIndex 本身就限制了元素不能回头使用 我的理解如下：

  • 如果是组合问题，如果i == index ，即使 nums[i] == nums[i - 1] ，也并不说明是本层重复使用了，而肯定是上一层使用了，所以说不需要用 !used[i - 1]（used为true表示上一层用过；为false说明本层用过，因为i是从左往右遍历的，既然上一层没用过那当前数的前面肯定本层用过了） 来判断是否是树层使用过了。
  • 但是排列问题总是从 0 开始遍历，数组靠后的数都有可能是上一层，所以必须要用 !used[i - 1]
  • 51. N 皇后 模拟
  • 37. 解数独

20260918

20260920

20260921

关键看dp数组定义是以i-1结尾还是区间…

题目 s t 求什么
1143 LCS 可以不选 可以不选 最长长度
392 判断子序列 必须全部匹配 可以不选 能否匹配
115 不同子序列 可以不选 必须全部匹配 匹配方案数

20260924
Page views: Loading...  ·  Visitors: Loading...
Except where otherwise noted, original content on this site is dedicated to the public domain under CC0 1.0.
Powered by Hexo & Theme mdsuper
沪ICP备2026040813号
Search