知识文档站

Appearance

对数器打表找规律技巧

应用场景 ​

输入参数是简单类型，返回值也是简单类型 ​

打表过程 ​

（1）可以用最暴力的实现求入参不大情况下的答案，往往只需要最基本的递归能力 ​

（2）打印入参不大情况下的答案，然后观察规律 ​

（3）把规律变成代码，就是最优解了 ​

用袋子买苹果问题 ​

题目描述 ​

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

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

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

打表过程 ​

发现规律如下 ​

（1）n < 18，如果 n =6 || n = 8，则返回 1，n = 12 || n = 14 || n = 16，则返回 2 ​

（2）n >= 18，8 个数为一组，奇数返回 -1，偶数返回 3 ​

（3）到下一组，奇数返回 -1，偶数返回 4，以此类推 ​

java
public static int bags1(int apple) {
    int ans = f(apple);
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

// 当前还有rest个苹果，使用的每个袋子必须装满，返回至少几个袋子
public static int f(int rest) {
    if (rest < 0) {
        return Integer.MAX_VALUE;
    }
    // 苹果数量为 0，完成任务，不需要袋子了
    if (rest == 0) {
        return 0;
    }
    // 使用 8 规格的袋子，剩余的苹果还需要几个袋子，有可能返回无效解
    int p1 = f(rest - 8);
    // 使用 6 规格的袋子，剩余的苹果还需要几个袋子，有可能返回无效解
    int p2 = f(rest - 6);
    p1 += p1 != Integer.MAX_VALUE ? 1 : 0;
    p2 += p2 != Integer.MAX_VALUE ? 1 : 0;
    return Math.min(p1, p2);
}

代码实现 ​

java
public static int bags2(int apple) {
    // 奇数个苹果
    if ((apple & 1) != 0) {
        return -1;
    }
    if (apple < 18) {
        if (apple == 0) {
            return 0;
        }
        if (apple == 6 || apple == 8) {
            return 1;
        }
        if (apple == 12 || apple == 14 || apple == 16) {
            return 2;
        }
        return -1;
    }
    // 8 个为一组，奇数返回 -1，偶数从第一组开始返回 3
    // 第一组：（18 - 18）/ 8 = 0 + 3 = 3
    // 第二组：（26 - 18）/ 8 = 1 + 3 = 4
    // 以此类推......
    return (apple - 18) / 8 + 3;
}

测试代码 ​

java
package class042;

// 有装下8个苹果的袋子、装下6个苹果的袋子，一定要保证买苹果时所有使用的袋子都装满
// 对于无法装满所有袋子的方案不予考虑，给定n个苹果，返回至少要多少个袋子
// 如果不存在每个袋子都装满的方案返回-1
public class Code01_AppleMinBags {

	public static int bags1(int apple) {
		int ans = f(apple);
		return ans == Integer.MAX_VALUE ? -1 : ans;
	}

	// 当前还有rest个苹果，使用的每个袋子必须装满，返回至少几个袋子
	public static int f(int rest) {
		if (rest < 0) {
			return Integer.MAX_VALUE;
		}
		if (rest == 0) {
			return 0;
		}
		// 使用8规格的袋子，剩余的苹果还需要几个袋子，有可能返回无效解
		int p1 = f(rest - 8);
		// 使用6规格的袋子，剩余的苹果还需要几个袋子，有可能返回无效解
		int p2 = f(rest - 6);
		p1 += p1 != Integer.MAX_VALUE ? 1 : 0;
		p2 += p2 != Integer.MAX_VALUE ? 1 : 0;
		return Math.min(p1, p2);
	}

	public static int bags2(int apple) {
		if ((apple & 1) != 0) {
			return -1;
		}
		if (apple < 18) {
			if (apple == 0) {
				return 0;
			}
			if (apple == 6 || apple == 8) {
				return 1;
			}
			if (apple == 12 || apple == 14 || apple == 16) {
				return 2;
			}
			return -1;
		}
		return (apple - 18) / 8 + 3;
	}

	public static void main(String[] args) {
		for (int apple = 0; apple < 100; apple++) {
			System.out.println(apple + " : " + bags1(apple));
		}
	}

}

AB 轮流吃草输赢问题 ​

题目描述 ​

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

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

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

打表过程 ​

发现规律：每五个一组，都是 B A B A A ​

java
// "A"  "B"
public static String win1(int n) {
    return f(n, "A");
}

// rest : 还剩多少草
// cur  : 当前选手的名字
// 返回  : 还剩rest份草，当前选手是cur，按照题目说的，返回最终谁赢
public static String f(int rest, String cur) {
    // 找出敌方
    String enemy = cur.equals("A") ? "B" : "A";
    // base case，枚举得到的结果
    if (rest < 5) {
        return (rest == 0 || rest == 2) ? enemy : cur;
    }
    // rest >= 5
    // rest == 100
    // cur : 每一回合吃不同的数量的草，逐个尝试
    //       看在后面的回合中能否赢
    // 1) 1 ->99,enemy ....
    // 2) 4 ->96,enemy ....
    // 3) 16 -> 84,enemy ....
    // 4) 64 -> 36,enemy ...
    // 首先从第 1 回合开始，吃 1 个草
    int pick = 1;
    while (pick <= rest) {
        // 剩下的草给敌人去挑，如果返回结果是 cur，cur 赢
        if (f(rest - pick, enemy).equals(cur)) {
            return cur;
        }
        pick *= 4;
    }
    // 没有 cur 赢的分支，enemy 赢
    return enemy;
}

代码实现 ​

java
public static String win2(int n) {
    if (n % 5 == 0 || n % 5 == 2) {
        return "B";
    } else {
        return "A";
    }
}

测试代码 ​

java
package class042;

// 草一共有n的重量，两只牛轮流吃草，A牛先吃，B牛后吃
// 每只牛在自己的回合，吃草的重量必须是4的幂，1、4、16、64....
// 谁在自己的回合正好把草吃完谁赢，根据输入的n，返回谁赢
public class Code02_EatGrass {

	// "A"  "B"
	public static String win1(int n) {
		return f(n, "A");
	}

	// rest : 还剩多少草
	// cur  : 当前选手的名字
	// 返回  : 还剩rest份草，当前选手是cur，按照题目说的，返回最终谁赢
	public static String f(int rest, String cur) {
		String enemy = cur.equals("A") ? "B" : "A";
		if (rest < 5) {
			return (rest == 0 || rest == 2) ? enemy : cur;
		}
		// rest >= 5
		// rest == 100
		// cur :
		// 1) 1 ->99,enemy ....
		// 2) 4 ->96,enemy ....
		// 3) 16 -> 84,enemy ....
		// 4) 64 -> 36,enemy ...
		// 没有cur赢的分支，enemy赢
		int pick = 1;
		while (pick <= rest) {
			if (f(rest - pick, enemy).equals(cur)) {
				return cur;
			}
			pick *= 4;
		}
		return enemy;
	}

	public static String win2(int n) {
		if (n % 5 == 0 || n % 5 == 2) {
			return "B";
		} else {
			return "A";
		}
	}

	public static void main(String[] args) {
		for (int i = 0; i <= 50; i++) {
			System.out.println(i + " : " + win1(i));
		}
	}

}

是否为连续正整数的和 ​

题目描述 ​

判断一个数字是否是若干数量（数量 > 1）的连续正整数的和 ​

打表过程 ​

从 1 开始尝试，累加 2 3 4 5 ... ​

从 2 开始尝试，累加 2 3 4 5 ... ​

以此类推... ​

直到累加和等于 sum，返回 true，否则，返回 false ​

发现规律：1 2 4 8 16 32 64.... 都是 false，这些数都是 2 的幂 ​

判断某个数是否是 2 的幂即可，如果是，那这个数就是连续正整数的和 ​

java
public static boolean is1(int num) {
    for (int start = 1, sum; start <= num; start++) {
        // 每一次尝试，记录起始值
        sum = start;
        // 往后依次尝试，不满足继续累加，满足跳出，超过和了 break
        for (int j = start + 1; j <= num; j++) {
            if (sum + j > num) {
                break;
            }
            if (sum + j == num) {
                return true;
            }
            sum += j;
        }
    }
    return false;
}

代码实现 ​

java
public static boolean is2(int num) {
    return (num & (num - 1)) != 0;
}

测试代码 ​

java
package class042;

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

	public static boolean is1(int num) {
		for (int start = 1, sum; start <= num; start++) {
			sum = start;
			for (int j = start + 1; j <= num; j++) {
				if (sum + j > num) {
					break;
				}
				if (sum + j == num) {
					return true;
				}
				sum += j;
			}
		}
		return false;
	}

	public static boolean is2(int num) {
		return (num & (num - 1)) != 0;
	}

	public static void main(String[] args) {
		for (int num = 1; num < 200; num++) {
			System.out.println(num + " : " + (is1(num) ? "T" : "F"));
		}
	}
}

red 好串数量问题 ​

题目描述 ​

可以用 r、e、d 三种字符拼接字符串，如果拼出来的字符串中 ​

有且仅有 1 个长度 >=2 的回文子串，那么这个字符串定义为 " 好串 " ​

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

结果对 1000000007 取模， 1 <= n <= 10^9 ​

示例： ​

n = 1, 输出 0 ​

n = 2, 输出 3 ​

n = 3, 输出 18 ​

打表过程 ​

发现规律：n = 1，ans = 0；n = 2，ans = 3；n = 3，ans = 18 ​

n 从 4 开始，n 每累加 1 次，ans 就会累加 6 ​

java
// 暴力方法
// 为了观察规律
public static int num1(int n) {
    char[] path = new char[n];
    return f(path, 0);
}

public static int f(char[] path, int i) {
    if (i == path.length) {
        int cnt = 0;
        // 长度为 1 字符串肯定是回文串，没必要验证，这里跳过了
        // 枚举生成的每一个字符串的所有字串，判断是否符合要求
        for (int l = 0; l < path.length; l++) {
            // l 来到 i 位置，后面所有位置都去尝试
            // l 来到 i + 1 位置，后面所有位置都去尝试...
            for (int r = l + 1; r < path.length; r++) {
                if (is(path, l, r)) {
                    cnt++;
                }
                if (cnt > 1) {
                    return 0;
                }
            }
        }
        return cnt == 1 ? 1 : 0;
    } else {
        // i 正常位置
        // 由 r，e，d 三个字符生成长度为 n 的所有字符串
        int ans = 0;
        path[i] = 'r';
        ans += f(path, i + 1);
        path[i] = 'e';
        ans += f(path, i + 1);
        path[i] = 'd';
        ans += f(path, i + 1);
        return ans;
    }
}

public static boolean is(char[] s, int l, int r) {
    while (l < r) {
        if (s[l] != s[r]) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

代码实现 ​

相乘可能会溢出，注意转成 long 类型 ​

java
// 正式方法
// 观察规律之后变成代码
public static int num2(int n) {
    if (n == 1) {
        return 0;
    }
    if (n == 2) {
        return 3;
    }
    if (n == 3) {
        return 18;
    }
    return (int) (((long) 6 * (n + 1)) % 1000000007);
}

测试代码 ​

java
package class042;

// 可以用r、e、d三种字符拼接字符串，如果拼出来的字符串中
// 有且仅有1个长度>=2的回文子串，那么这个字符串定义为"好串"
// 返回长度为n的所有可能的字符串中，好串有多少个
// 结果对 1000000007 取模， 1 <= n <= 10^9
// 示例：
// n = 1, 输出0
// n = 2, 输出3
// n = 3, 输出18
public class Code04_RedPalindromeGoodStrings {

	// 暴力方法
	// 为了观察规律
	public static int num1(int n) {
		char[] path = new char[n];
		return f(path, 0);
	}

	public static int f(char[] path, int i) {
		if (i == path.length) {
			int cnt = 0;
			for (int l = 0; l < path.length; l++) {
				for (int r = l + 1; r < path.length; r++) {
					if (is(path, l, r)) {
						cnt++;
					}
					if (cnt > 1) {
						return 0;
					}
				}
			}
			return cnt == 1 ? 1 : 0;
		} else {
			// i正常位置
			int ans = 0;
			path[i] = 'r';
			ans += f(path, i + 1);
			path[i] = 'e';
			ans += f(path, i + 1);
			path[i] = 'd';
			ans += f(path, i + 1);
			return ans;
		}
	}

	public static boolean is(char[] s, int l, int r) {
		while (l < r) {
			if (s[l] != s[r]) {
				return false;
			}
			l++;
			r--;
		}
		return true;
	}

	// 正式方法
	// 观察规律之后变成代码
	public static int num2(int n) {
		if (n == 1) {
			return 0;
		}
		if (n == 2) {
			return 3;
		}
		if (n == 3) {
			return 18;
		}
		return (int) (((long) 6 * (n + 1)) % 1000000007);
	}

	public static void main(String[] args) {
		for (int i = 1; i <= 10; i++) {
			System.out.println("长度为" + i + ", 答案:" + num1(i));
		}
	}

}

Copyright © 2025 Jackson 凌 All Rights Reserved. | 粤ICP备2025441629号-1