搭木棍
在迷迷糊糊的大草原上，小红捡到了 n 根木棍，第i根木棍的长度为 i，小红现在很开心。想选出其中的三根木棍组成美丽的三角形。但是小明想捉弄小红，想去掉一些木棍，使得小红任意选三根木棍都不能组成
三角形。
请问小明最少去掉多少根木棍呢？
思路：
n 个数不能组成三角形，3 个数不能组成三角形的唯一原因：
，也就是说，任意两个数的和要大于等于第三个数。假设存在数组 arr 满足该条件，那么 arr 有序时必有 arr[i-2] + arr[i-1] <= arr[i]。本题中求的最少去掉的数量，也就是满足 arr[i-2] + arr[i-1] = arr[i] 时最小。
相当于 
，也就是最少需要去掉 
代码实现：
public class DeleteWood {public static int minDelete(int n) {if (n <= 2) return 0;int num = 0;int a = 1;int b = 2;for (int i = 3; i <= n; i++) {i = a + b;if (i <= n) {num += i - b - 1;} else {num += n - b;break;}a = b;b = i;}return num;}public static int minDelete1(int m) {if (m < 4) {return 0;}int k_2 = 2;int k_1 = 3;int num = 3;while (k_2 + k_1 <= m) {num++;k_1 += k_2;k_2 = k_1 - k_2;}return m - num;}public static void main(String[] args) {System.out.println(minDelete(6));for (int i = 0; i <= 10; i++) {System.out.println(i + "\t" + minDelete(i));System.out.println(i + "\t" + minDelete1(i));}}}
数组调整
给定一个数组 arr，如果通过调整可以做到 arr 中任意两个相邻的数字相乘是 4 的倍数，返回 true；如果不能返回 false
思路：
相邻两个数的积为 4 的倍数，有三种情况：
- 每隔一个数就有一个为 4 的倍数，如：[1, 0, 3, 4, 5, 8]
- 两个数都是偶数，如：[2, 6, 10, 14]
- 上面两种情况混合
即，如数组有 arr.length/2 以上的数是 4 的倍数 或者 (arr.length - 4 的倍数 * 2) 的数都是偶数
import com.example.test.base.sort.ArrayGenerator;
import java.util.Arrays;
public class NearMultiple4Times {
private static boolean nearMultiple4Times(int[] arr) {
int time4 = 0;
int time2 = 0;
for (int i : arr) {
if (i % 4 == 0) {
time4++;
} else if (i % 2 == 0) {
time2++;
}
}
return time4 >= arr.length / 2 || arr.length - time4 * 2 <= time2;
}
public static void main(String[] args) {
for (int i = 0; i < 100; i++) {
int[] arr = ArrayGenerator.getArr(6, 30);
System.out.println(Arrays.toString(arr) + "\t" + nearMultiple4Times(arr));
}
}
}
翻译数字
给定一个字符串，如果该字符串符合人们日常书写一个整数的形式，返回 int 类型的这个数；如果不符合或者越界返回 -1 或者报错
思路：
本题是一道业务题，旨在考察分析业务的能力。日常我们一般书写数字时，不会出现：07、1a2、-03、-、2*20、1-3、……规律为：
- 不能出现除
-之外的符号 - 如果有
-，那么一定是在最左边且不能单独出现，并且不能后面是 0 - 除了 0 以外的其他数都不能以 0 开头
- 保证数字在 int 范围中，不能越界
代码实现：
public class ConvertStringToInteger {
public static int convert(String str) {
if (str == null || str.equals("")) {
return -1; // can not convert
}
char[] chas = str.toCharArray();
if (!isValid(chas)) {
return -1; // can not convert
}
boolean posi = chas[0] == '-' ? false : true;
int minq = Integer.MIN_VALUE / 10;
int minr = Integer.MIN_VALUE % 10;
int res = 0;
int cur = 0;
for (int i = posi ? 0 : 1; i < chas.length; i++) {
// 这里用的 0 减去 其他的数，是想用负数来表示所有的数，因为负数的绝对值范围要比正数大一
cur = '0' - chas[i];
// 判断是否越界
if ((res < minq) || (res == minq && cur < minr)) {
return -1; // can not convert
}
res = res * 10 + cur;
}
if (posi && res == Integer.MIN_VALUE) {
return -1; // can not convert
}
return posi ? -res : res;
}
public static boolean isValid(char[] chas) {
if (chas[0] != '-' && (chas[0] < '0' || chas[0] > '9')) {
return false;
}
if (chas[0] == '-' && (chas.length == 1 || chas[1] == '0')) {
return false;
}
if (chas[0] == '0' && chas.length > 1) {
return false;
}
for (int i = 1; i < chas.length; i++) {
if (chas[i] < '0' || chas[i] > '9') {
return false;
}
}
return true;
}
public static void main(String[] args) {
String test1 = "2147483647"; // max in java
System.out.println(convert(test1));
String test2 = "-2147483648"; // min in java
System.out.println(convert(test2));
String test3 = "2147483648"; // overflow
System.out.println(convert(test3));
String test4 = "-2147483649"; // overflow
System.out.println(convert(test4));
String test5 = "-123";
System.out.println(convert(test5));
}
}
实现动态 Top K
设计并实现 TopKRecord 结构，可以不断地向其中加入字符串，并且可以根据字符串出现的情况随时打印加入次数最多的前k个字符串。具体为:
- k 在 TopKRecord 实例生成时指定，并且不再变化（k 是构造 TopKRecord 的参数）。
- 含有 add(String str) 方法，即向 TopKRecord 中加入字符串。
- 含有 printTopK() 方法，即打印加入次数最多的前 k 个字符串，打印有哪些字符串和对应的次数即可，不要求严格按排名顺序打印。
- 如果在出现次数最多的前 k 个字符串中，最后一名的字符串有多个，比如出现次数最多的前3个字符串具体排名为：
A 100次 B 90次 C 80次 D 80次 E 80次，其他任何字符串出现次数都不超过 80 次
那么只需要打印 3 个，打印 ABC、ABD、ABE 都可以。也就是说可以随意抛弃最后一名，只要求打印 k 个
要求：
1）在任何时候，add 方法的时间复杂度不超过 O(logk)
2）在任何时候，printTopK 方法的时间复杂度不超过O(k)。
这个之前有做过 各种练习 2 - 动态 Top
放零食
牛牛准备参加学校组织的春游，出发前牛牛准备往背包里装入一些零食，牛牛的背包容量为 w。牛牛家里一共有 n 袋零食，第 i 袋零食体积为 v[i]。
牛牛想知道在总体积不超过背包容量的情况下，他一共有多少种零食放法（总体积为 0 也算一种放法）。
思路一：
递归，每中零食都有放入背包和不放入背包两种选择
private static int ways(int[] v, int w) {
return process(v, w, 0);
}
private static int process(int[] v, int w, int i) {
if (i == v.length) return w >= 0 ? 1 : 0;
return process(v, w - v[i], i + 1) + process(v, w, i + 1);
}
思路二：
新建数组 [v.length][w + 1]，[i][j] 代表了容量 j 可以有多少存储 v[i] 的方法，如第一行：
- 容量 0、1、2、3 可以有 1 存储方法：不放
- 容量 4、5、6、7、8 可以有 2 存储方法：不放、放 4
第二行：
- 容量 0、1、2 可以有 1 存储方法：不放
- 容量 3 可以有 2 存储方法：不放、放 3
- 容量 4、5、6 可以有 3 存储方法：不放、放 3、放 4
- 容量 7、8 可以有 4 存储方法：不放、只放 3、只放 4、同时放 3 和 4
这里可以发现：对于 i > 0 任意的 [i][j] 来说，有以下的放入方法：
// 上一行存放的方式本行一定也能用
[i][j] = [i - 1][j];
if (j - v[i] >= 0) {
// 当前物品也能存入，存放的方式 = 上一行的方式 + 上一行减去当前重量的存放方式
[i][j] += [i - 1][j - v[i]];
}
填完后就是：
返回 [v.length - 1][w] 就是最后的结果。
public static int ways2(int[] v, int w) {
if (v == null || v.length == 0 || w < 0) {
return 0;
}
int[][] dp = new int[v.length][w + 1];
for (int i = 0; i < v.length; i++) {
dp[i][0] = 1;
}
for (int j = 1; j <= w; j++) {
dp[0][j] = j >= v[0] ? 2 : 1;
}
for (int i = 1; i < v.length; i++) {
for (int j = 1; j <= w; j++) {
dp[i][j] = dp[i - 1][j];
if (j - v[i] >= 0) {
dp[i][j] += dp[i - 1][j - v[i]];
}
}
}
return dp[v.length - 1][w];
}
找工作
为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
public class Job {
public int money;// 该工作的报酬
public int hard; // 该工作的难度
public Job(int money, int hard) {
this.money = money;
this.hard = hard;
}
}
给定一个 Job 类型的数组 jobarr，表示所有的工作。给定一个 int 类型的数组 arr，表示所有小伙伴的能力。 返回 int 类型的数组，表示每一个小伙伴按照牛牛的标准选工作后所能获得的报酬。
思路：
要得到在难度不超过自身能力值的情况下，选择报酬最高的工作，也就是性价比最高的工作。可以先将所有的工作进行排序，排序的规则为，难度从低到高，相同的难度报酬高的在前。
然后就会发现：其实在相同的难度时，报酬低的永远不会被选择，这样就可以只保留每种难度中报酬最高的工作。然后就有可能会出现：难度升高了，但是报酬却降低了，也要把这种情况排除掉，剩下的就是实际上会选择的工作。
import com.leetcodetest.algorithm.ArrayGenerator;
import java.util.Arrays;
import java.util.TreeMap;
public class ChooseWork {
public static int[] getMoneys(Job[] jobarr, int[] arr) {
Arrays.sort(jobarr, (o1, o2) -> o1.hard != o2.hard ? (o1.hard - o2.hard) : (o2.money - o1.money));
TreeMap<Integer, Integer> map = new TreeMap<>();
// 只保留每组的组长，并且报酬要递增。如报酬减少同样要删除
int curMoney = 0;
for (Job job : jobarr) {
if (!map.containsKey(job.hard) && job.money > curMoney) {
map.put(job.hard, job.money);
curMoney = job.money;
}
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
Integer key = map.floorKey(arr[i]);
if (key != null) res[i] = map.get(key);
}
return res;
}
public static void main(String[] args) {
Job[] jobarr = new Job[]{
new Job(5, 3),
new Job(7, 2),
new Job(100, 9),
new Job(4, 1),
new Job(6, 2),
new Job(3, 3),
new Job(1, 1),
new Job(8, 2),
};
int[] arr = ArrayGenerator.getArr(10, 15);
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(getMoneys(jobarr, arr)));
}
}
若有收获，就点个赞吧
0 人点赞
