My-Notes

Search

SearchSearch

024.对数器打表找规律的技巧

Dec 26, 2023, 8 min read

前置知识：会基本递归即可，推荐 常见经典递归过程解析，以及 判断一个整数是不是 2 的幂

对数器打表找规律

使用场景：输入参数是简单类型，返回值也是简单类型

对数器打表找规律的过程：

  1. 可以用最暴力的实现求入参不大情况下的答案，往往只需要最基本的递归能力
  2. 打印入参不大情况下的答案，然后观察规律
  3. 把规律变成代码，就是最优解了

题目1.使用规格 8 和规格 6 的袋子买苹果问题

题目描述

有装下 8 个苹果的袋子和装下 6 个苹果的袋子，一定要保证买苹果时所有使用的袋子都装满

对于无法装满所有袋子的方案不予考虑，给定 n 个苹果，返回至少要多少个袋子

如果不存在每个袋子都装满的方案返回 -1

打表找规律

package main
 
import (
	"fmt"
	"math"
)
 
const (
	MAX_INT = math.MaxInt
)
 
func main() {
	for i := 0; i < 50; i++ {
		fmt.Printf("%d: %d\n", i, bags(i))
	}
}
 
func bags(n int) int {
	ans := f(n)
	if ans == MAX_INT {
		return -1
	}
	return ans
}
 
// 当前还有 rest 个苹果，使用的每个袋子必须装满，返回至少几个袋子
func f(rest int) int {
	if rest < 0 {
		return MAX_INT
	}
	if rest == 0 {
		return 0
	}
	p1 := f(rest - 8)
	p2 := f(rest - 6)
	if p1 != MAX_INT {
		p1 += 1
	}
	if p2 != MAX_INT {
		p2 += 1
	}
	return min(p1, p2)
}
0: 0
1: -1
2: -1
3: -1
4: -1
5: -1
6: 1
7: -1
8: 1
9: -1
10: -1
11: -1
12: 2
13: -1
14: 2
15: -1
16: 2
17: -1
18: 3
19: -1
20: 3
21: -1
22: 3
23: -1
24: 3
25: -1
26: 4
27: -1
28: 4
29: -1
30: 4
31: -1
32: 4
33: -1
34: 5
35: -1
36: 5
37: -1
38: 5
39: -1
40: 5
41: -1
42: 6
43: -1
44: 6
45: -1
46: 6
47: -1
48: 6
49: -1

看规律，写代码

func bags2(n int) int {
	if n&1 != 0 { // 奇数
		return -1
	}
	if n < 18 {
		if n == 0 {
			return 0
		}
		if n == 6 || n == 8 {
			return 1
		}
		if n == 12 || n == 14 || n == 16 {
			return 2
		}
		return -1
	}
	return (n-18)/8 + 3
}

，最优解！

题目2.A 和 B 轮流吃草最终谁会赢

题目描述

草一共有 n 的重量，两只牛轮流吃草，A 牛先吃，B 牛后吃

每只牛在自己的回合，吃草的重量必须是 4 的幂，1、4、16、64…

谁在自己的回合正好把草吃完谁赢，根据输入的 n，返回谁赢

博弈论：A、B 两牛都会选择最优解

打表找规律

package main
 
import "fmt"
 
func main() {
	for i := 0; i < 50; i++ {
		fmt.Printf("%d: %s\n", i, win(i))
	}
}
 
func win(n int) string {
	return f(n, "A")
}
 
// 还剩 rest 份草，当前选手是 cur，按照题目说的，返回最终谁赢
func f(rest int, cur string) string {
	other := "A"
	if cur == "A" {
		other = "B"
	}
	if rest < 5 {
		if rest == 0 || rest == 2 {
			return other
		} else {
			return cur
		}
	}
	// cur 吃几份草
	pick := 1
	for pick <= rest {
		if f(rest-pick, other) == cur {
			return cur
		}
		pick *= 4
	}
	return other
}
0: B
1: A
2: B
3: A
4: A
5: B
6: A
7: B
8: A
9: A
10: B
11: A
12: B
13: A
14: A
15: B
16: A
17: B
18: A
19: A
20: B
21: A
22: B
23: A
24: A
25: B
26: A
27: B
28: A
29: A
30: B
31: A
32: B
33: A
34: A
35: B
36: A
37: B
38: A
39: A
40: B
41: A
42: B
43: A
44: A
45: B
46: A
47: B
48: A
49: A

看规律，写代码

func win2(n int) string {
	if n%5 == 0 || n%5 == 2 {
		return "B"
	} else {
		return "A"
	}
}

题目3.是否是连续正整数的和

题目描述

判断一个数字是否是若干数量(数量>1)的连续正整数的和

如：12=3+4+5

打表找规律

package main
 
import "fmt"
 
func main() {
	for i := 1; i < 50; i++ {
		fmt.Printf("%d: %v\n", i, is(i))
	}
}
 
func is(n int) bool {
	for start := 1; start <= n; start++ {
		sum := start
		for i := start + 1; i <= n; i++ {
			sum += i
			if sum > n {
				break
			}
			if sum == n {
				return true
			}
		}
	}
	return false
}
1: false
2: false
3: true
4: false
5: true
6: true
7: true
8: false
9: true
10: true
11: true
12: true
13: true
14: true
15: true
16: false
17: true
18: true
19: true
20: true
21: true
22: true
23: true
24: true
25: true
26: true
27: true
28: true
29: true
30: true
31: true
32: false
33: true
34: true
35: true
36: true
37: true
38: true
39: true
40: true
41: true
42: true
43: true
44: true
45: true
46: true
47: true
48: true
49: true

看规律，写代码

func is2(n int) bool {
	return n&(n-1) != 0 // 不是 2 的某次方
}

题目4.好串数量

题目描述

可以用 r、e、d 三种字符拼接字符串，如果拼出来的字符串中有且仅有 1 个长度 的回文子串，那么这个字符串定义为”好串”

返回长度为 n 的所有可能的字符串中，好串有多少个

结果对 取模，

示例：

  • n = 1，输出 0
  • n = 2，输出 3
  • n = 3，输出 18

打表找规律

package main
 
import "fmt"
 
func main() {
	for i := 1; i <= 10; i++ {
		fmt.Printf("%d: %d\n", i, count(i))
	}
}
 
func count(n int) int {
	path := make([]byte, n)
	return f(0, n, path)
}
 
func f(idx, n int, path []byte) int {
	if idx == n {
		cnt := 0
		for l := 0; l < n; l++ {
			for r := l + 1; r < n; r++ {
				if is(path, l, r) {
					cnt++
				}
				if cnt > 1 {
					return 0
				}
			}
		}
		if cnt == 1 {
			return 1
		}
		return 0
	}
 
	ans := 0
	path[idx] = 'r'
	ans += f(idx+1, n, path)
	path[idx] = 'e'
	ans += f(idx+1, n, path)
	path[idx] = 'd'
	ans += f(idx+1, n, path)
	return ans
}
 
// 是否回文串
func is(path []byte, l, r int) bool {
	for l < r {
		if path[l] != path[r] {
			return false
		}
		l++
		r--
	}
	return true
}
1: 0
2: 3
3: 18
4: 30
5: 36
6: 42
7: 48
8: 54
9: 60
10: 66

看规律，写代码

const (
	MOD = 1e9 + 7
)
 
func count2(n int) int {
	if n == 1 {
		return 0
	}
	if n == 2 {
		return 3
	}
	if n == 3 {
		return 18
	}
	return 6 * (n + 1) % MOD
}

Graph View

Backlinks