欢迎
首页 标签 归档 友链 Page

AlgorithmLeetcodeShijuan

2022-06-13

牛客网试卷

括号匹配

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/06/13/AlgorithmLeetcodeShijuan/

updated at 2022-10-15

Previous Post
项目HouseRenting
Next Post
Algorithm多次写的