题目一 达标字符串
字符串只由’0’和’1’两种字符构成，
当字符串长度为1时，所有可能的字符串为”0”、”1”;
当字符串长度为2时，所有可能的字符串为”00”、”01”、”10”、”11”;
当字符串长度为3时，所有可能的字符串为”000”、”001”、 “010”、 “011”、 “100”、”101”、”110”、 “111”
如果某一个字符串中，只要是出现’0’的位置，左边就靠着’1’，这样的字符串叫作达标字符串。
给定一一个正数N，返回所有长度为N的字符串中，达标字符串的数量。
比如，N=3， 返回3，因为只有”101”、”110”、 “111”达标。
解
n=i在长度为i有多少合法的字符串，就规定了在0位置上必须为1，求f(n-1)。
对于n=8，就是0位置为1,求剩下7位置的可能性，f(7),此时就有2中可能性
- 第一位为1，求f(6)的数量
- 第一位为0，那么下一位就必须填1，f(5)的数量
f(i) = f(i-1)+f(i-2),此时把问题转化为了斐波那契数列问题。采用递归或动态规划的方式求解,下面是采用的线性代数中将斐波那契数列转换为矩阵相乘的求解方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| public static int fi(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
int[][] base = {{1, 1}, {1, 0}};
int[][] res = matrixPower(base, n - 2);
return res[0][0] + res[1][0];
}
private static int[][] matrixPower(int[][] m, int p) {
int[][] res = new int[m.length][m[0].length];
for (int i = 0; i < res.length; i++) {
res[i][i] = i;
}
int[][] tmp = m;
for (; p != 0; p >>= 1) {
if ((p & 1) !=0){
res = muliMatrix(res, tmp);
}
tmp = muliMatrix(tmp, tmp);
}
return res;
}
private static int[][] muliMatrix(int[][] m1, int[][] m2) {
int[][] res = new int[m1.length][m2[0].length];
for (int i =0; i<m1.length;i++){
for (int j = 0;j<=m2.length;j++){
for (int k = 0;k<m2.length;k++){
res[i][j] += m1[i][k] * m2[k][j];
}
}
}
return res;
}
|
题目二 不能组成三角形
在迷迷糊糊的大草原上，小红捡到了n根木棍，第i根木棍的长度为i，小红现在很开心。想选出其中的三根木棍组成美丽的三角形。
但是小明想捉弄小红，想去掉一些木棍，使得小红任意选三根木棍都不能组成三角形。
请问小明最少去掉多少根木棍呢?给定N，返回至少去掉多少根?
解
不能组成三角形，将题目转化为求n以内的斐波那契数列数列的个数，就是最多个保留木棍的个数。两边之和大于第三边
代码如上一题。
题目三 相邻是4的倍数
给定一个数组arr,如果通过调整可以做到arr中任意两个相邻的数字相乘是4的倍数,返回true;如果不能返回false
解
将数组中数分为2类奇数a个,偶数中只有一个2因子的b个，包含4因子的数c个，有以下几种情况
b==0 “奇 四 奇 四 奇” … 这样摆节省空间
a==1, c>=1a!=1,c>=a-1
b!=0 “2222224奇4奇4”
a==1, c>=1a!=1 , c>=a
c>=a
b=1 c=0 a=0 不成立
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| public static boolean nearMultiple4(int[] arr) {
int even2 = 0;
int even4 = 0;
int odd = 0;
for (int num : arr) {
if (num % 2 == 0) {
if (num % 4 == 0) {
even4++;
} else {
even2++;
}
} else {
odd++;
}
}
if (even2 == 1 && even4 == 0 && odd == 0) {
return false;
}
boolean res;
if (even2 == 0) {
if (odd == 1) {
res = even4 >= 1;
} else {
res = even4 >= odd - 1;
}
} else {
res = even4 >= odd;
}
return res;
}
|
题目四 整数字符串
给定一个字符串，如果该字符串符合人们日常书写一个整数的形式，返回int类型的这个数;如果不符合或者越界返回-1或者报错。
解
有以下几个条件
- 数字之外只允许有”-“,
- 有”-“只允许出现在开头, 并且跟着数字字符
- 如果开头是0后序没有数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| public static int convert(String s) {
if (s == null || s.equals("")) {
return 0;
}
char[] str = s.toCharArray();
if (!isValid(str)) {
throw new RuntimeException("can not convert");
}
boolean neg = str[0] == '-' ? true : false;
int minq = Integer.MIN_VALUE /10;
int minr = Integer.MIN_VALUE %10;
int res = 0;int cur = 0;
for (int i = neg ? 1 : 0; i < str.length; i++) {
cur = '0' - str[i];
if ( ( res < minq) || (res == minq && cur < minr)) {
throw new RuntimeException( "can not convert" );
}
res = res * 10 + cur;
}
if (!neg && res == Integer.MIN_VALUE){
throw new RuntimeException( "can not convert" );
}
return neg ? res : -res;
}
public static boolean isValid(char[] str) {
if (str[0] != '-' && (str[0] < '0' || str[0] > '9')) {
return false;
}
if (str[0] == '-' && (str.length == 1 || str[1] == '0')) {
return false;
}
if (str[0] == '0' && str.length > 1) {
return false;
}
for (int i = 1; i < str.length; i++) {
if (str[i] < '0' || str[i] > '9') {
return false;
}
}
return true;
}
|
题目五 最高的k个记录
设计并实现TopKRecord结构，可以不断地向其中加入字符串，并且可以根据字符串出现的情况随时打印加入次数最多的前k个字符串。具体为:
- k在TopKRecord实例生成时指定，并且不再变化(k是构造TopKRecord的参数)
- 含有add (String str)方法，即向TopKRecord中加入字符串。
- 含有printTopK()方法，即打印加入次数最多的前k个字符串，打印有哪些字符串和对应的次数即可，不要求严格按排名顺序打印。
- 如果在出现次数最征…..o字符串中，最后一名的字符串有多个，比如出现次数最多的前3个字符串具体排名为:
A 100次B 90次C 80次D 80次E80次，其他任何字符串出现次数都不超过80次
那么只需要打印3个，打印ABC、ABD、ABE都可以。也就是说可以随意抛弃最后一名，只要求打印k个
要求:
- 在任何时候，add 方法的时间复杂度不超过0(logk)2）在任何时候，printTopK方法的时间复杂度不超过0(k)。
题目在 中级提升班3 字符串数组出现最大的前k个中已经写过，此处省略
题目六 零食的装法
牛牛准备参加学校组织的春游，出发前牛牛准备往背包里装入一些零食，牛牛的背包容量为w。
牛牛家里一共有n袋零食，第i袋零食体积为v[i]。
牛牛想知道在总体积不超过背包容量的情况下，他一共有多少种零食放法(总体积为0也算一种放法)。
解
背包问题的变种，完全背包问题是容量为n正好可以装满的方法，该方法就是从容量为0到容量为n的方法都相加即使最终的答案。
类似于leetcode 零钱兑换2问题 只不过是所有的可能性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public int snackPlacement(int n, int[] arr){
if (arr == null || arr.length == 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][n + 1];
dp[N][0] = 1;
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= n; rest++) {
int ways = 0;
for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {
ways += dp[ index + 1][ rest - arr[index] * zhang];
}
dp[index][rest] = ways;
}
}
int res = 1;
for (int i = 0; i <= n; i++ ){
res += dp[0][i];
}
return res;
}
|
题目七 找工作
为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
1
2
3
4
5
6
7
8
| 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类型的数组，表示每一个小伙伴按照牛牛的标准选工作后所能获得的报酬。
leetcode 502 IPO
解
首先对Job进行排序，先安装Job的难度由小到大排，如果难度一样按照报酬排。难度一样保留报酬最高的；去掉难度升高报酬减少的工作；保持难度递增，报酬一定递增的单调性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public static class JobComparator implements Comparator<Job> {
@Override
public int compare(Job o1, Job o2) {
return o1.hard != o2.hard ? o1.hard - o2.hard : o2.money - o1.money;
}
}
public static int[] getMoneys(Job[] jobs, int[] ability) {
Arrays.sort(jobs, new JobComparator());
TreeMap<Integer, Integer> map = new TreeMap<>();
map.put(jobs[0].hard, jobs[0].money);
Job pre = jobs[0];
for (int i = 1; i < jobs.length; i++) {
if (jobs[i].hard != pre.hard && jobs[i].money > pre.money) {
pre = jobs[i];
map.put(pre.hard, pre.money);
}
}
int[] ans = new int[ability.length];
for (int i = 0; i < ability.length; i++) {
Integer key = map.floorKey(ability[i]);
ans[i] = key != null ? map.get(key) : 0;
}
return ans;
}
|
