Eagle233-Blog

[Algorithm] 算法训练 202609

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

4.1k Words   |   15 Minutes

LeetCode 算法动画演示集

代码随想录 + Hot100

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

20260925

20260926

20260927

20260928

20260930

20261001

20261008

20261009

20261010

20261012

20261013

20261014

20261015
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