admin管理员组文章数量:1530060
对数器找规律
1）某个面试题，输入参数类型简单，并且只有一个实际参数
2）要求的返回值类型也简单，并且只有一个
3）用暴力方法，把输入参数对应的返回值，打印出来看看，进而优化code
题目一
小虎去买苹果，商店只提供两种类型的塑料袋，每种类型都有任意数量。
1）能装下6个苹果的袋子
2）能装下8个苹果的袋子
小虎可以自由使用两种袋子来装苹果，但是小虎有强迫症，他要求自己使用的袋子数量必须最少，且使用的每个袋子必须装满。
给定一个正整数N，返回至少使用多少袋子。如果N无法让使用的每个袋子必须装满，返回-1
使用暴力解，查看结果可以发现规律：
1）1-17没有规律
2）18后每8个一组，奇数返回-1，偶数返回（apple-18）/8+3
public static int minBags(int apple) {
if (apple < 0) {
return -1;
}
int bag8 = (apple >> 3);
int rest = apple - (bag8 << 3);
while(bag8 >= 0) {
// rest 个
if(rest % 6 ==0) {
return bag8 + (rest / 6);
} else {
bag8--;
rest += 8;
}
}
return -1;
}
public static int minBagAwesome(int apple) {
if ((apple & 1) != 0) { // 如果是奇数，返回-1
return -1;
}
if (apple < 18) {
return apple == 0 ? 0 : (apple == 6 || apple == 8) ? 1
: (apple == 12 || apple == 14 || apple == 16) ? 2 : -1;
}
return (apple - 18) / 8 + 3;
}题目二
给定一个正整数N，表示有N份青草统一堆放在仓库里
有一只牛和一只羊，牛先吃，羊后吃，它俩轮流吃草
不管是牛还是羊，每一轮能吃的草量必须是：
1，4，16，64…(4的某次方)
谁最先把草吃完，谁获胜
假设牛和羊都绝顶聪明，都想赢，都会做出理性的决定
根据唯一的参数N，返回谁会赢
解规律：每5个一组，顺序都为：后手 先手 后手 先手 先手
// 如果n份草，最终先手赢，返回"先手"
// 如果n份草，最终后手赢，返回"后手"
public static String whoWin(int n) {
if (n < 5) {
return n == 0 || n == 2 ? "后手" : "先手";
}
// 进到这个过程里来，当前的先手，先选
int want = 1;
while (want <= n) {
if (whoWin(n - want).equals("后手")) {
return "先手";
}
if (want <= (n / 4)) {
want *= 4;
} else {
break;
}
}
return "后手";
}
public static String winner1(int n) {
if (n < 5) {
return (n == 0 || n == 2) ? "后手" : "先手";
}
int base = 1;
while (base <= n) {
if (winner1(n - base).equals("后手")) {
return "先手";
}
if (base > n / 4) { // 防止base*4之后溢出
break;
}
base *= 4;
}
return "后手";
}
public static String winner2(int n) {
if (n % 5 == 0 || n % 5 == 2) {
return "后手";
} else {
return "先手";
}
}题目三
定义一种数：可以表示成若干（数量>1）连续正数和的数
比如:
5 = 2+3，5就是这样的数
12 = 3+4+5，12就是这样的数
1不是这样的数，因为要求数量大于1个、连续正数和
2 = 1 + 1，2也不是，因为等号右边不是连续正数
给定一个参数N，返回是不是可以表示成若干连续正数和的数
解规律：只有2的N次方的数不能表示成若干个连续的正数的和
public static boolean isMSum1(int num) {
for (int start = 1; start <= num; start++) {
int 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 isMSum2(int num) {
//
// return num == (num & (~num + 1));
//
// return num == (num & (-num));
//
//
return (num & (num - 1)) != 0;
}根据数据规模猜解法
1）C/C++，1秒处理的指令条数为10的8次方
2）Java等语言，1~4秒处理的指令条数为10的8次方
3）这里就有大量的空间了！
题目四
int[] d，d[i]：i号怪兽的能力
int[] p，p[i]：i号怪兽要求的钱
开始时你的能力是0，你的目标是从0号怪兽开始，通过所有的怪兽。
如果你当前的能力，小于i号怪兽的能力，你必须付出p[i]的钱，贿赂这个怪兽，然后怪兽就会加入你，他的能力直接累加到你的能力上；如果你当前的能力，大于等于i号怪兽的能力，你可以选择直接通过，你的能力并不会下降，你也可以选择贿赂这个怪兽，然后怪兽就会加入你，他的能力直接累加到你的能力上。
返回通过所有的怪兽，需要花的最小钱数。
第一种思路dp：dp[i][j] 表示能经过0~i的怪兽，能力>=j的情况下，花的钱最少是多少
问题：如果怪兽能力值过大，所求的dp二维表累加和sum会很大，这样就跑不完
第二种思虑dp：dp[i][j]表示能经过0～i的怪兽，且花钱为j（花钱的严格等于j）时的武力值最大是多少
问题：如果贿赂一个怪兽的钱非常大，所求dp二维表钱的累加和就很大，这样就跑不完
因此需要根据所给的数据情况，选择不同的解法
// int[] d d[i]：i号怪兽的武力
// int[] p p[i]：i号怪兽要求的钱
// ability 当前你所具有的能力
// index 来到了第index个怪兽的面前
// 目前，你的能力是ability，你来到了index号怪兽的面前，如果要通过后续所有的怪兽，
// 请返回需要花的最少钱数
public static long process1(int[] d, int[] p, int ability, int index) {
if (index == d.length) {
return 0;
}
if (ability < d[index]) {
return p[index] + process1(d, p, ability + d[index], index + 1);
} else { // ability >= d[index] 可以贿赂，也可以不贿赂
return Math.min(
p[index] + process1(d, p, ability + d[index], index + 1),
0 + process1(d, p, ability, index + 1));
}
}
public static long func1(int[] d, int[] p) {
return process1(d, p, 0, 0);
}
// 从0....index号怪兽，花的钱，必须严格==money
// 如果通过不了，返回-1
// 如果可以通过，返回能通过情况下的最大能力值
public static long process2(int[] d, int[] p, int index, int money) {
if (index == -1) { // 一个怪兽也没遇到呢
return money == 0 ? 0 : -1;
}
// index >= 0
// 1) 不贿赂当前index号怪兽
long preMaxAbility = process2(d, p, index - 1, money);
long p1 = -1;
if (preMaxAbility != -1 && preMaxAbility >= d[index]) {
p1 = preMaxAbility;
}
// 2) 贿赂当前的怪兽 当前的钱 p[index]
long preMaxAbility2 = process2(d, p, index - 1, money - p[index]);
long p2 = -1;
if (preMaxAbility2 != -1) {
p2 = d[index] + preMaxAbility2;
}
return Math.max(p1, p2);
}
public static int minMoney2(int[] d, int[] p) {
int allMoney = 0;
for (int i = 0; i < p.length; i++) {
allMoney += p[i];
}
int N = d.length;
for (int money = 0; money < allMoney; money++) {
if (process2(d, p, N - 1, money) != -1) {
return money;
}
}
return allMoney;
}
public static long func2(int[] d, int[] p) {
int sum = 0;
for (int num : d) {
sum += num;
}
long[][] dp = new long[d.length + 1][sum + 1];
for (int i = 0; i <= sum; i++) {
dp[0][i] = 0;
}
for (int cur = d.length - 1; cur >= 0; cur--) {
for (int hp = 0; hp <= sum; hp++) {
// 如果这种情况发生，那么这个hp必然是递归过程中不会出现的状态
// 既然动态规划是尝试过程的优化，尝试过程碰不到的状态，不必计算
if (hp + d[cur] > sum) {
continue;
}
if (hp < d[cur]) {
dp[cur][hp] = p[cur] + dp[cur + 1][hp + d[cur]];
} else {
dp[cur][hp] = Math.min(p[cur] + dp[cur + 1][hp + d[cur]], dp[cur + 1][hp]);
}
}
}
return dp[0][0];
}
public static long func3(int[] d, int[] p) {
int sum = 0;
for (int num : p) {
sum += num;
}
// dp[i][j]含义：
// 能经过0～i的怪兽，且花钱为j（花钱的严格等于j）时的武力值最大是多少？
// 如果dp[i][j]==-1，表示经过0～i的怪兽，花钱为j是无法通过的，或者之前的钱怎么组合也得不到正好为j的钱数
int[][] dp = new int[d.length][sum + 1];
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j <= sum; j++) {
dp[i][j] = -1;
}
}
// 经过0～i的怪兽，花钱数一定为p[0]，达到武力值d[0]的地步。其他第0行的状态一律是无效的
dp[0][p[0]] = d[0];
for (int i = 1; i < d.length; i++) {
for (int j = 0; j <= sum; j++) {
// 可能性一，为当前怪兽花钱
// 存在条件：
// j - p[i]要不越界，并且在钱数为j - p[i]时，要能通过0～i-1的怪兽，并且钱数组合是有效的。
if (j >= p[i] && dp[i - 1][j - p[i]] != -1) {
dp[i][j] = dp[i - 1][j - p[i]] + d[i];
}
// 可能性二，不为当前怪兽花钱
// 存在条件：
// 0~i-1怪兽在花钱为j的情况下，能保证通过当前i位置的怪兽
if (dp[i - 1][j] >= d[i]) {
// 两种可能性中，选武力值最大的
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
}
}
}
int ans = 0;
// dp表最后一行上，dp[N-1][j]代表：
// 能经过0～N-1的怪兽，且花钱为j（花钱的严格等于j）时的武力值最大是多少？
// 那么最后一行上，最左侧的不为-1的列数(j)，就是答案
for (int j = 0; j <= sum; j++) {
if (dp[d.length - 1][j] != -1) {
ans = j;
break;
}
}
return ans;
}分治使用的情况
分治的应用场景：
1，数据量整体做尝试可能性太多了，跑不完
2，数据分成多个块（常见是两块）之后，各自的可能性并不算多
3，合并多个块各自信息的整合过程不复杂
题目一
给定一个非负数组arr，和一个正数m。
返回arr的所有子序列中累加和%m之后的最大值。
//方法一：递归所有情况，放入set中
public static int max1(int[] arr, int m) {
HashSet<Integer> set = new HashSet<>();
process(arr, 0, 0, set);
int max = 0;
for (Integer sum : set) {
max = Math.max(max, sum % m);
}
return max;
}
public static void process(int[] arr, int index, int sum, HashSet<Integer> set) {
if (index == arr.length) {
set.add(sum);
} else {
process(arr, index + 1, sum, set);
process(arr, index + 1, sum + arr[index], set);
}
}//在所有数字累加和不大的情况下，使用dp[i][j]表示前i个零食，凑出j重量的dp二维表
public static int max2(int[] arr, int m) {
int sum = 0;
int N = arr.length;
for (int i = 0; i < N; i++) {
sum += arr[i];
}
boolean[][] dp = new boolean[N][sum + 1];
for (int i = 0; i < N; i++) {
dp[i][0] = true;
}
dp[0][arr[0]] = true;
for (int i = 1; i < N; i++) {
for (int j = 1; j <= sum; j++) {
dp[i][j] = dp[i - 1][j];
if (j - arr[i] >= 0) {
dp[i][j] |= dp[i - 1][j - arr[i]];
}
}
}
int ans = 0;
for (int j = 0; j <= sum; j++) {
if (dp[N - 1][j]) {
ans = Math.max(ans, j % m);
}
}
return ans;
}//dp[i][j]表示前i个数字自由选择，所搞出来的所有累加和再模m之后有没有余数j
public static int max3(int[] arr, int m) {
int N = arr.length;
// 0...m-1
boolean[][] dp = new boolean[N][m];
for (int i = 0; i < N; i++) {
dp[i][0] = true;
}
dp[0][arr[0] % m] = true;
for (int i = 1; i < N; i++) {
for (int j = 1; j < m; j++) {
// dp[i][j] T or F
dp[i][j] = dp[i - 1][j];
int cur = arr[i] % m;
if (cur <= j) {
dp[i][j] |= dp[i - 1][j - cur];
} else {
dp[i][j] |= dp[i - 1][m + j - cur];
}
}
}
int ans = 0;
for (int i = 0; i < m; i++) {
if (dp[N - 1][i]) {
ans = i;
}
}
return ans;
}
// 如果arr的累加和很大，m也很大
// 但是arr的长度相对不大，用分治
public static int max4(int[] arr, int m) {
if (arr.length == 1) {
return arr[0] % m;
}
int mid = (arr.length - 1) / 2;
TreeSet<Integer> sortSet1 = new TreeSet<>();
process4(arr, 0, 0, mid, m, sortSet1);
TreeSet<Integer> sortSet2 = new TreeSet<>();
process4(arr, mid + 1, 0, arr.length - 1, m, sortSet2);
int ans = 0;
for (Integer leftMod : sortSet1) {
ans = Math.max(ans, leftMod + sortSet2.floor(m - 1 - leftMod));
}
return ans;
}
// 从index出发，最后有边界是end+1，arr[index...end]
public static void process4(int[] arr, int index, int sum, int end, int m, TreeSet<Integer> sortSet) {
if (index == end + 1) {
sortSet.add(sum % m);
} else {
process4(arr, index + 1, sum, end, m, sortSet);
process4(arr, index + 1, sum + arr[index], end, m, sortSet);
}
}题目二
牛牛家里一共有n袋零食, 第i袋零食体积为v[i]，背包容量为w。
牛牛想知道在总体积不超过背包容量的情况下,
一共有多少种零食放法，体积为0也算一种放法
1 <= n <= 30, 1 <= w <= 2 * 10^9
v[i] (0 <= v[i] <= 10^9）
public static int ways1(int[] arr, int w) {
// arr[0...]
return process(arr, 0, w);
}
// 从左往右的经典模型
// 还剩的容量是rest，arr[index...]自由选择，
// 返回选择方案
// index ： 0～N
// rest : 0~w
public static int process(int[] arr, int index, int rest) {
if (rest < 0) { // 没有容量了
// -1 无方案的意思
return -1;
}
// rest>=0,
if (index == arr.length) { // 无零食可选
return 1;
}
// rest >=0
// 有零食index
// index号零食，要 or 不要
// index, rest
// (index+1, rest)
// (index+1, rest-arr[i])
int next1 = process(arr, index + 1, rest); // 不要
int next2 = process(arr, index + 1, rest - arr[index]); // 要
return next1 + (next2 == -1 ? 0 : next2);
}//分治算法，左边15个，右边15个
public static long ways(int[] arr, int bag) {
if (arr == null || arr.length == 0) {
return 0;
}
if (arr.length == 1) {
return arr[0] <= bag ? 2 : 1;
}
int mid = (arr.length - 1) >> 1;
TreeMap<Long, Long> lmap = new TreeMap<>();
long ways = process(arr, 0, 0, mid, bag, lmap);
TreeMap<Long, Long> rmap = new TreeMap<>();
ways += process(arr, mid + 1, 0, arr.length - 1, bag, rmap);
TreeMap<Long, Long> rpre = new TreeMap<>();
long pre = 0;
for (Entry<Long, Long> entry : rmap.entrySet()) {
pre += entry.getValue();
rpre.put(entry.getKey(), pre);
}
for (Entry<Long, Long> entry : lmap.entrySet()) {
long lweight = entry.getKey();
long lways = entry.getValue();
Long floor = rpre.floorKey(bag - lweight);
if (floor != null) {
long rways = rpre.get(floor);
ways += lways * rways;
}
}
return ways + 1;
}卡特兰数
卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中出现的数列。其前几项为：
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...
k(0) = 1, k(1) = 1时，如果接下来的项满足：
k(n) = k(0) * k(n - 1) + k(1) * k(n - 2) + ... + k(n - 2) * k(1) + k(n - 1) * k(0)
或者
k(n) = c(2n, n) - c(2n, n-1)
或者
k(n) = c(2n, n) / (n + 1)
就说这个表达式，满足卡特兰数，常用的是范式1和2，3几乎不会使用到
题目一
假设给你N个0，和N个1，你必须用全部数字拼序列
返回有多少个序列满足：任何前缀串，1的数量都不少于0的数量
//暴力解法
public static long ways1(int N) {
int zero = N;
int one = N;
LinkedList<Integer> path = new LinkedList<>();
LinkedList<LinkedList<Integer>> ans = new LinkedList<>();
process(zero, one, path, ans);
long count = 0;
for (LinkedList<Integer> cur : ans) {
int status = 0;
for (Integer num : cur) {
if (num == 0) {
status++;
} else {
status--;
}
if (status < 0) {
break;
}
}
if (status == 0) {
count++;
}
}
return count;
}
public static void process(int zero, int one, LinkedList<Integer> path, LinkedList<LinkedList<Integer>> ans) {
if (zero == 0 && one == 0) {
LinkedList<Integer> cur = new LinkedList<>();
for (Integer num : path) {
cur.add(num);
}
ans.add(cur);
} else {
if (zero == 0) {
path.addLast(1);
process(zero, one - 1, path, ans);
path.removeLast();
} else if (one == 0) {
path.addLast(0);
process(zero - 1, one, path, ans);
path.removeLast();
} else {
path.addLast(1);
process(zero, one - 1, path, ans);
path.removeLast();
path.addLast(0);
process(zero - 1, one, path, ans);
path.removeLast();
}
}
}//卡特兰数公式3解法
public static long ways2(int N) {
if (N < 0) {
return 0;
}
if (N < 2) {
return 1;
}
long a = 1;
long b = 1;
long limit = N << 1;
for (long i = 1; i <= limit; i++) {
if (i <= N) {
a *= i;
} else {
b *= i;
}
}
return (b / a) / (N + 1);
}题目二
有N个二叉树节点，每个节点彼此之间无任何差别
返回由N个二叉树节点，组成的不同结构数量是多少？
// k(0) = 1, k(1) = 1
//
// k(n) = k(0) * k(n - 1) + k(1) * k(n - 2) + ... + k(n - 2) * k(1) + k(n - 1) * k(0)
// 或者
// k(n) = c(2n, n) / (n + 1)
// 或者
// k(n) = c(2n, n) - c(2n, n-1)
public static long num1(int N) {
if (N < 0) {
return 0;
}
if (N < 2) {
return 1;
}
long[] dp = new long[N + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
for (int leftSize = 0; leftSize < i; leftSize++) {
dp[i] += dp[leftSize] * dp[i - 1 - leftSize];
}
}
return dp[N];
}
public static long num2(int N) {
if (N < 0) {
return 0;
}
if (N < 2) {
return 1;
}
long a = 1;
long b = 1;
for (int i = 1, j = N + 1; i <= N; i++, j++) {
a *= i;
b *= j;
long gcd = gcd(a, b);
a /= gcd;
b /= gcd;
}
return (b / a) / (N + 1);
}
public static long gcd(long m, long n) {
return n == 0 ? m : gcd(n, m % n);
}卡特兰数的算法原型在做题时怎么发现？
1）如果像题目一一样，这个太明显了，你一定能发现
2）看看题目是不是类题目二问题，比如：
人员站队问题
出栈入栈问题
需要敏感度！
补充题目
arr中的值可以为正、负、零，自由选择其中的数字，能不能累加得到sum
// arr中的值可能为正，可能为负，可能为0
// 自由选择arr中的数字，能不能累加得到sum
// 暴力递归方法
public static boolean isSum1(int[] arr, int sum) {
if (sum == 0) {
return true;
}
if (arr == null || arr.length == 0) {
return false;
}
return process1(arr, arr.length - 1, sum);
}
// 可以自由使用arr[0...i]上的数字，能不能累加得到sum
public static boolean process1(int[] arr, int i, int sum) {
if (sum == 0) {
return true;
}
if (i == -1) {
return false;
}
return process1(arr, i - 1, sum) || process1(arr, i - 1, sum - arr[i]);
}
// arr中的值可能为正，可能为负，可能为0
// 自由选择arr中的数字，能不能累加得到sum
// 记忆化搜索方法
// 从暴力递归方法来，加了记忆化缓存，就是动态规划了
public static boolean isSum2(int[] arr, int sum) {
if (sum == 0) {
return true;
}
if (arr == null || arr.length == 0) {
return false;
}
return process2(arr, arr.length - 1, sum, new HashMap<>());
}
public static boolean process2(int[] arr, int i, int sum, HashMap<Integer, HashMap<Integer, Boolean>> dp) {
if (dp.containsKey(i) && dp.get(i).containsKey(sum)) {
return dp.get(i).get(sum);
}
boolean ans = false;
if (sum == 0) {
ans = true;
} else if (i != -1) {
ans = process2(arr, i - 1, sum, dp) || process2(arr, i - 1, sum - arr[i], dp);
}
if (!dp.containsKey(i)) {
dp.put(i, new HashMap<>());
}
dp.get(i).put(sum, ans);
return ans;
}
// arr中的值可能为正，可能为负，可能为0
// 自由选择arr中的数字，能不能累加得到sum
// 经典动态规划
public static boolean isSum3(int[] arr, int sum) {
if (sum == 0) {
return true;
}
if (arr == null || arr.length == 0) {
return false;
}
int min = 0;
int max = 0;
for (int num : arr) {
min += num < 0 ? num : 0;
max += num > 0 ? num : 0;
}
if (sum < min || sum > max) {
return false;
}
int N = arr.length;
boolean[][] dp = new boolean[N][max - min + 1];
dp[0][-min] = true;
dp[0][arr[0] - min] = true;
for (int i = 1; i < N; i++) {
for (int j = min; j <= max; j++) {
dp[i][j - min] = dp[i - 1][j - min];
int next = j - min - arr[i];
dp[i][j - min] |= (next >= 0 && next <= max - min && dp[i - 1][next]);
}
}
return dp[N - 1][sum - min];
}
// arr中的值可能为正，可能为负，可能为0
// 自由选择arr中的数字，能不能累加得到sum
// 分治的方法
// 如果arr中的数值特别大，动态规划方法依然会很慢
// 此时如果arr的数字个数不算多(40以内)，哪怕其中的数值很大，分治的方法也将是最优解
public static boolean isSum4(int[] arr, int sum) {
if (sum == 0) {
return true;
}
if (arr == null || arr.length == 0) {
return false;
}
if (arr.length == 1) {
return arr[0] == sum;
}
int N = arr.length;
int mid = N >> 1;
HashSet<Integer> leftSum = new HashSet<>();
HashSet<Integer> rightSum = new HashSet<>();
process4(arr, 0, mid, 0, leftSum);
process4(arr, mid, N, 0, rightSum);
for (int l : leftSum) {
if (rightSum.contains(sum - l)) {
return true;
}
}
return false;
}
public static void process4(int[] arr, int i, int end, int pre, HashSet<Integer> ans) {
if (i == end) {
ans.add(pre);
} else {
process4(arr, i + 1, end, pre, ans);
process4(arr, i + 1, end, pre + arr[i], ans);
}
}
版权声明：本文标题：算法数据结构（三十四）----根据对数器找规律&根据数据量猜解法&分治 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1726763562a1083362.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论