2022-01-15：中心对称数 III。
中心对称数是指一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。
写一个函数来计算范围在 [low, high] 之间中心对称数的个数。
示例：
输入：low = "50",high = "100"，
输出:3。
解释：69,88和96是三个在该范围内的中心对称数。
注意：
由于范围可能很大，所以low和high都用字符串表示。
来自力扣248。
答案2022-01-15：
假设low=264，high=3422。
264到999的个数x，
1000到9999的个数y,3422到9999的个数z。
sum=x y-z。如果high本身是有效数，sum=x y-z 1。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
ret := strobogrammaticInRange("50", "100")
fmt.Println(ret)
}
func strobogrammaticInRange(l, h string) int {
low := []byte(l)
high := []byte(h)
if !equalMore(low, high) {
return 0
}
lowLen := len(low)
highLen := len(high)
if lowLen == highLen {
up1 := up(low, 0, false, 1)
up2 := up(high, 0, false, 1)
return up1 - up2 twoSelectOne(valid(high), 1, 0)
}
ans := 0
// lowLen = 3 hightLen = 7
// 4 5 6
for i := lowLen 1; i < highLen; i {
ans = all1(i)
}
ans = up(low, 0, false, 1)
ans = down(high, 0, false, 1)
return ans
}
func equalMore(low, cur []byte) bool {
if len(low) != len(cur) {
return len(low) < len(cur)
}
for i := 0; i < len(low); i {
if low[i] != cur[i] {
return low[i] < cur[i]
}
}
return true
}
func valid(str []byte) bool {
L := 0
R := len(str) - 1
for L <= R {
t := L != R
if convert2(str[L], t) != int(str[R]) {
return false
}
L
R--
}
return true
}
// left想得到cha字符，right配合应该做什么决定，
// 如果left怎么也得不到cha字符，返回-1；如果能得到，返回right配合应做什么决定
// 比如，left!=right，即不是同一个位置
// left想得到0，那么就right就需要是0
// left想得到1，那么就right就需要是1
// left想得到6，那么就right就需要是9
// left想得到8，那么就right就需要是8
// left想得到9，那么就right就需要是6
// 除此了这些之外，left不能得到别的了。
// 比如，left==right，即是同一个位置
// left想得到0，那么就right就需要是0
// left想得到1，那么就right就需要是1
// left想得到8，那么就right就需要是8
// 除此了这些之外，left不能得到别的了，比如：
// left想得到6，那么就right就需要是9，而left和right是一个位置啊，怎么可能即6又9，返回-1
// left想得到9，那么就right就需要是6，而left和right是一个位置啊，怎么可能即9又6，返回-1
func convert2(cha byte, diff bool) int {
switch cha {
case '0':
return '0'
case '1':
return '1'
case '6':
return twoSelectOne(diff, '9', -1)
case '8':
return '8'
case '9':
return twoSelectOne(diff, '6', -1)
default:
return -1
}
}
// low [左边已经做完决定了 left.....right 右边已经做完决定了]
// 左边已经做完决定的部分，如果大于low的原始，leftMore = true;
// 左边已经做完决定的部分，如果不大于low的原始，那一定是相等，不可能小于，leftMore = false;
// 右边已经做完决定的部分，如果小于low的原始，rightLessEqualMore = 0;
// 右边已经做完决定的部分，如果等于low的原始，rightLessEqualMore = 1;
// 右边已经做完决定的部分，如果大于low的原始，rightLessEqualMore = 2;
// rightLessEqualMore < = >
// 0 1 2
// 返回 ：没做决定的部分，随意变，几个有效的情况？返回！
func up(low []byte, left int, leftMore bool, rightLessEqualMore int) int {
N := len(low)
right := N - 1 - left
if left > right { // 都做完决定了！
// 如果左边做完决定的部分大于原始 或者 如果左边做完决定的部分等于原始&左边做完决定的部分不小于原始
// 有效！
// 否则，无效！
return twoSelectOne(leftMore || (!leftMore && rightLessEqualMore != 0), 1, 0)
}
// 如果上面没有return，说明决定没做完，就继续做
if leftMore { // 如果左边做完决定的部分大于原始
return num(N - (left << 1))
} else { // 如果左边做完决定的部分等于原始
ways := 0
// 当前left做的决定，大于原始的left
for cha := (low[left] 1); cha <= '9'; cha {
if convert2(cha, left != right) != -1 {
ways = up(low, left 1, true, rightLessEqualMore)
}
}
// 当前left做的决定，等于原始的left
convert := convert2(low[left], left != right)
if convert != -1 {
if convert < int(low[right]) {
ways = up(low, left 1, false, 0)
} else if convert == int(low[right]) {
ways = up(low, left 1, false, rightLessEqualMore)
} else {
ways = up(low, left 1, false, 2)
}
}
return ways
}
}
// ll < =
// rs < = >
func down(high []byte, left int, ll bool, rs int) int {
N := len(high)
right := N - 1 - left
if left > right {
return twoSelectOne(ll || (!ll && rs != 2), 1, 0)
}
if ll {
return num(N - (left << 1))
} else {
ways := 0
for cha := byte(twoSelectOne((N != 1 && left == 0), '1', '0')); cha < high[left]; cha {
if convert2(cha, left != right) != -1 {
ways = down(high, left 1, true, rs)
}
}
convert := convert2(high[left], left != right)
if convert != -1 {
if convert < int(high[right]) {
ways = down(high, left 1, false, 0)
} else if convert == int(high[right]) {
ways = down(high, left 1, false, rs)
} else {
ways = down(high, left 1, false, 2)
}
}
return ways
}
}
func num(bits int) int {
if bits == 1 {
return 3
}
if bits == 2 {
return 5
}
p2 := 3
p1 := 5
ans := 0
for i := 3; i <= bits; i {
ans = 5 * p2
p2 = p1
p1 = ans
}
return ans
}
// 如果是最开始 :
// Y X X X Y
// -> 1 X X X 1
// -> 8 X X X 8
// -> 9 X X X 6
// -> 6 X X X 9
// 如果不是最开始 :
// Y X X X Y
// -> 0 X X X 0
// -> 1 X X X 1
// -> 8 X X X 8
// -> 9 X X X 6
// -> 6 X X X 9
// 所有的len位数，有几个有效的？
func all1(len0 int) int {
ans := twoSelectOne((len0&1) == 0, 1, 3)
for i := twoSelectOne((len0&1) == 0, 2, 3); i < len0; i = 2 {
ans *= 5
}
return ans << 2
}
// 我们课上讲的
func all2(len0 int, init0 bool) int {
if len0 == 0 { // init == true，不可能调用all(0)
return 1
}
if len0 == 1 {
return 3
}
if init0 {
return all2(len0-2, false) << 2
} else {
return all2(len0-2, false) * 5
}
}
func twoSelectOne(c bool, a, b int) int {
if c {
return a
} else {
return b
}
}
执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class44/Problem_0248_StrobogrammaticNumberIII.java)
,
