LeetcodeShijuan

LeetCode试卷

括号匹配

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
import java.util.*;

public class Solution {
/**
*
* @param s string字符串
* @return bool布尔型
*/
public boolean IsValidExp (String s) {
// write code here
// 使用栈
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> map = new HashMap<Character, Character>();

char[] chars = s.toCharArray();
for(int i=0; i<chars.length; i++) {
if (chars[i] == '{') {
// 直接存相反的
stack.offerLast('}');
} else if (chars[i] == '[') {
// 直接存相反的
stack.offerLast(']');
} else if (chars[i] == '(') {
// 直接存相反的
stack.offerLast(')');
} else if (!stack.isEmpty() && stack.peekLast().equals(chars[i])) {
stack.pollLast();
} else {
return false;
}
}

return stack.isEmpty();
}
}

算24

Java 回溯, 经典面试题

给出4个1-10的数字,通过加减乘除,得到数字为24就算胜利。

1

福尔摩斯编码解码

5HWfpeACFyQ3KEh

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
// dp动态规划

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
char[] chars = str.toCharArray();
int n = chars.length;
if (n == 0) { System.out.println(0); return;}

long[] dp = new long[n];
// 边界
dp[0] = 1;

for (int i=1; i<n; i++) {
// 1位,不论01
dp[i] = dp[i-1];

// 2位
if (chars[i-1] == '1') {
if (i == 1) { dp[i] += 1; }
else {
dp[i] += dp[i-2];
}
}

// 3位
if (i >= 2 && chars[i-2] == '1') {
if (i == 2) { dp[i] += 1; }
else {
dp[i] += dp[i-3];
}
}
}

System.out.println(dp[n-1]);
}
}

电影院选座

项目经理

仓库配送

最短路径问题

1 Floyd

注意这一题k在最外面

使用邻接矩阵,Floyd
最短路径的子路径仍然是最短路径
dp[k][i][j] 为经过前k的节点,从i到j所能得到的最短路径
dp[k][i][j] = min(dp[k-1][i][k], dp[k-1][i][k], dp[k-1][k][j])
状态dp[k][i][j]由dp[k-1][i][j](不经过k),dp[k-1][i,k]+dp[k-1][k][j](经过k)转移过来,
很容易可以看出,dp[k]的状态完全由dp[k-1]转移过来,只要我们把k放倒最外层循环中,就能保证无后效性。

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
import java.util.*;

public class Flody {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt(), K = scanner.nextInt(), M = scanner.nextInt();


long [][] g = new long[N+1][N+1];

// 初始化
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
g[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 0; i < M; i++) {
int x = scanner.nextInt(), y = scanner.nextInt(), w = scanner.nextInt();
// 注意,题目描述的是有向的
g[x][y] = w;
}
for (int i = 0; i <= N; i++) {
g[i][i] = 0;
}

for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (g[i][k] != Integer.MAX_VALUE && g[k][j] != Integer.MAX_VALUE) {
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}

// 题目求的是,可以并行送货,所以只要看source到某一个的最远就好了
long ans = Integer.MIN_VALUE;
for (int i = 1; i <= N; i++) {
ans = Math.max(ans, g[K][i]);
}

System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
}
}

2 Dijikstra

最高效率的复习

【2022-08-20】美团秋招笔试五道编程题

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
import java.util.*;

public class HighestFuXi {
/**
* 思路,贪心,转换为损失的价值,然后优先补偿损失最多的
* @param args
*/
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();
scanner.nextLine();

int[][] scores = new int[2][n];
scores[0] = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
scores[1] = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

double ans = 0.0;
Queue<Double> queue = new PriorityQueue<>((a, b) -> {
if (a.equals(b)) { return 0;}
else if (b > a) { return 1;} // return正数代表
return -1;
});
for (int i = 0; i < n; i++) {
ans += scores[0][i] * 1.0 / 100 * scores[1][i];
queue.offer((1 - scores[0][i] * 1.0 / 100) * scores[1][i]);
}

for (int i = 0; i < m; i++) {
ans += queue.poll();
}

System.out.println(ans);
}
}

拟合,两个数列变相同

下面有一个 拼多多的 【字符变换】的,但是那个题目对应的做法更简单一点。

两个数列,可以去掉其中一个,步数abs(a[i]),也可以一个变成另外一个,步数abs(a[i] - b[i]),问最少步数两者相同。

思路

跟最长公共子序列差不多,dp[i][j],先考虑边界,在考虑递推式

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
// 未验证
import java.util.*;

public class NiHe {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();

scanner.nextLine();

int[] a = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
int[] b = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

// 二维,第一维是数组a,0表示数组a中没有元素,第二维是数组b
int[][] dp = new int[n+1][m+1];

// 边界
for (int i = 1; i < n + 1; i++) {
// b数组没有元素的时候,a数组需要吧元素全部去掉,注意下标
dp[i][0] = dp[i-1][0] + Math.abs(a[i-1]);
}
for (int i = 1; i < m + 1; i++) {
dp[0][i] = dp[0][i-1] + Math.abs(b[i-1]);
}

for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
// 地推关系,ij有三个的最小值组成,一个变成另外一个(这种情况步数一样),去掉其中一个
if (a[i-1] == b[i-1]) { dp[i][j] = dp[i-1][j-1]; }
else {
dp[i][j] = Math.min(dp[i-1][j-1] + Math.abs(a[i-1] - b[j-1]),
Math.min(dp[i-1][j] + Math.abs(a[i-1]), dp[i][j-1] + Math.abs(b[j-1])));
}

}
}

System.out.println(dp[n][m]);
}
}

回顾,最长公共子序列

剑指 Offer II 095. 最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
// 使用动态规划
int n = text1.length(), m = text2.length();
char[] a = text1.toCharArray();
char[] b = text2.toCharArray();
int[][] dp = new int[n+1][m+1];

// 边界,有0的,都是0

for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
if (a[i-1] == b[j-1]) { // 注意此处的字符串是i-1的,因为dp多了个长度为0的时候
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}

return dp[n][m];
}
}

修补

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
// 未验证
import java.util.*;

public class XiuBu {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();

scanner.nextLine();
int[] a = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
// 注意,去重复,distinct()
// 注意,此处升序其实不用这么麻烦,只是告诉你sorted里面也可以那样写,而且不能写在后面,因为maptoint返回IntStream,还是基本类型int,所以不能写
int[] b = Arrays.stream(scanner.nextLine().split(" ")).distinct().
sorted((x, y) -> Integer.parseInt(x) - Integer.parseInt(y)).mapToInt(Integer::valueOf).toArray();

long ans = 0;

// 对于每一个坏的地方ai,找出b中第一个大于等于的
for (int i = 0; i < n; i++) {
int left = 0, right = m;
while (left <= right) {
int mid = (left + (right - left >> 1));

if (b[mid] == a[i]) {
left = right = mid;
break;
} else if (b[mid] > a[i]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// 有相等,就是相等
// 没有相等,目前到了left > right,nums[left] > target,nums[right] < target
// 没有相等,然后由于left > right,所以left可能右边出界,right可能左边出界
// 这里估计肯定有,所以不考虑left出界的情况
ans += b[left];
}

System.out.println(ans);
}
}

美团2021_10

公司食堂

注意:

1 每次取最左边的餐桌,所以用了两个小根队。

2 卡输出,先用StringBuilder将所有输出缓存

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
import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = Integer.parseInt(scanner.nextLine());
// 一个个输出,太慢了,会超时的。
StringBuilder ans = new StringBuilder();

// 同时,使用了两个小根队,而不是在循环一遍去查找。

while (T-- != 0) {
int N = Integer.parseInt(scanner.nextLine());
String desk = scanner.nextLine();
char[] deskChars = desk.toCharArray();
int paidui = Integer.parseInt(scanner.nextLine());
String sexes = scanner.nextLine();

Queue<Integer> zeroQueue = new PriorityQueue<>();
Queue<Integer> oneQueue = new PriorityQueue<>();
for (int i=1; i<=N; i++) {
if (deskChars[i-1] == '1') {
oneQueue.offer(i);
} else if (deskChars[i-1] == '0') {
zeroQueue.offer(i);
}
}

for (Character c: sexes.toCharArray()) {
int deskNum = 0;
if (c == 'F') {
if (!zeroQueue.isEmpty()) {
deskNum = zeroQueue.poll();
oneQueue.offer(deskNum);
} else {
deskNum = oneQueue.poll();
}
} else {
if (!oneQueue.isEmpty()) {
deskNum = oneQueue.poll();
} else {
deskNum = zeroQueue.poll();
oneQueue.offer(deskNum);
}
}
ans.append(deskNum).append("\n");
}
}

System.out.println(ans);
}
}

最优二叉树

使用分治 + 记忆化搜索的方法

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
import java.util.*;

// 使用分治 + 记忆化搜索的方法
// 由于中序遍历的特点,节点在中间,然后左右分别是左右子树
// 所以来一个三维的dp[i][j][k],然后进行分治
// 其中ij代表i~j的树,k代表k为根节点
public class Main {
static int[][][] dp;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
int[] nums = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

dp = new int[n][n][n];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
for (int k=0; k<n; k++) {
dp[i][j][k] = -1;
}
}
}

// 初始条件,从0~n-1的节点,父节点不指定,所以-1
// 如果节点变成1~n,然后父写成0,这样下面的函数里面就不用确认了。
int ans = dfs(0, n-1, -1, nums);
System.out.println(ans);
}

public static int dfs(int left, int right, int root, int[] nums) {
if (left > right) { return 0; }
// 该方案已经计算过最优开销了
if (root >= 0 && dp[left][right][root] != -1) {
return dp[left][right][root];
}

// 然后让left~right中间的每一个轮流做根,构建二叉树
int cost = Integer.MAX_VALUE;
for (int index = left; index <= right; index++) {
// 左子树开销,left~index-1是左子树的,index是根
int leftCost = dfs(left, index-1, index, nums);
int rightCost = dfs(index+1, right, index, nums);
// root=-1时表示初始根节点还没有确定,不会有根节点连接左右子树的边
// 总最小=min(左子树+右子树+选出的根节点值*father节点值)
cost = Math.min(cost, leftCost + rightCost + nums[index] * (root == -1 ? 0 : nums[root]));
}

//备忘录记下已经取得的值
if (root > 0) { dp[left][right][root] = cost; }
return cost;
}
}

拼多多

多多的求和计算

![ScreenShot2022-08-26at11.00.41](https://gitee.com/JiaChengCC/u-pic-chart-bed/raw/master/uPic/Screen Shot 2022-08-26 at 11.00.41.png)

如果,二维朴素计算,稍微大了点。

所以用map存取模的前缀和,然后可以用来求区间个数。注意最后本来就是0的情况。

还有Map也要用Long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

// 前缀和
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt(), M = scanner.nextInt();
scanner.nextLine();
int[] nums = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

// map存储的是,当前前缀和,有多少个了,已经取模了M
Map<Long, Long> map = new HashMap<>();
// 注意sums[i]表示的是nums[0~i-1]的和。
long[] sums = new long[N + 1];
for (int i = 1; i <= N; i++) {
sums[i] = (sums[i - 1] + (nums[i - 1] % M)) % M;
map.put(sums[i], map.getOrDefault(sums[i], 0L) + 1);
}

// 看同一个取模M前缀和的相等的个数为n,那么该取模M前缀和下面有n(n-1)/2
// 注意,需要加上本身前缀和就是0的,就是从一开始,到该点前缀和取模
System.out.println(map.values().stream().map(n -> n * (n - 1) / 2).reduce(0L, Long::sum) + map.getOrDefault(0L, 0L));
}
}

数组组合

定义为:每个数字的十进制表示中(0~9),每个数位各不相同且各个数位之和等于N。
满足条件的数字可能很多,找到其中的最小值即可。

多多君还有很多研究课题,于是多多君找到了你–未来的计算机科学家寻求帮助。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// 答案很简单,从9开始往后,足够就放进去。

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
if (N > 45){
System.out.println(-1);
System.exit(0);
}
StringBuilder stringBuilder = new StringBuilder();
for (int i = 9; i > 0; i--) {
if (N>=i){
N-=i;
stringBuilder.insert(0,i);
}
}
System.out.println(stringBuilder.toString());
}
}

// 我自己用的,回溯 + 递归,遍历了所有的结果[Facepalm]
import java.util.*;

public class Main {
static List<Integer> ans;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int sum = scanner.nextInt();
if (sum > 50) {
System.out.println(-1);
return;
}

int[] nums = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

for (int step = 1; step <= 10; step += 1) {
dfsTrace(nums, 0, step, new ArrayList<>(), sum);
}

if (ans == null) {
System.out.println(-1);
return;
}

int ansVal = 0;
for (int num: ans) {
ansVal = (ansVal * 10) + num;
}
System.out.println(ansVal);
}

public static void dfsTrace(int[] nums, int curIndex, int step, List<Integer> curNums, int sum) {
if (step == curNums.size()) {
if (curNums.stream().mapToInt(Integer::valueOf).sum() == sum) {
ans = new ArrayList<>(curNums);
}
return;
}

if (ans != null || curIndex >= nums.length) {
return;
}

// 选择,选择先,因为更小
curNums.add(nums[curIndex]);
dfsTrace(nums, curIndex + 1, step, curNums, sum);
curNums.remove(curNums.size() - 1);

// 不选择
dfsTrace(nums, curIndex + 1, step, curNums, sum);
}
}

字符变换

注意和上面的美团的 【拟合,两个数列变相同】 这动态规划题目做比较。

多多君最近在研究字符串之间的变换,可以对字符串进行若干次变换操作:

  1. 交换任意两个相邻的字符,代价为0。
  2. 将任意一个字符a修改成字符b,代价为 |a - b|(绝对值)。

现在有两个长度相同的字符串X和Y,多多君想知道,如果要将X和Y变成两个一样的字符串,需要的最少的代价之和是多少。

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
/*
交换字符是不存在代价的,所以先将两个字符串的字符都修改为相同,然后再调整字符排列顺序就可以了,这个调整顺序的过程并不需要付出额外的代价。而字符串x中某个字符要修改为字符串y中的字符,代价最小的方式就是修改为排名相同的字符,即字符串x中字典序排名第k的字符修改为字符串y中字典序排名第k的字符,这样的修改才能使得整体代价最小,否则即使是这次修改为代价更小的字符,势必会造成另一个字符要付出更大的修改代价。
*/
import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());

String a = scanner.nextLine();
String b = scanner.nextLine();

char[] aChars = a.toCharArray();
char[] bChars = b.toCharArray();

Arrays.sort(aChars);
Arrays.sort(bChars);

int ans = 0;
for (int i = 0; i < aChars.length; i++) {
ans += Math.abs(aChars[i] - bChars[i]);
}

System.out.println(ans);
}
}

Author: Jcwang

Permalink: http://example.com/2022/08/19/AlgorithmLeetcodeShijuan/