讨论/题目交流/🏆 第 173 场力扣周赛/
🏆 第 173 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 删除回文子序列
4 分 - 餐厅过滤器
5 分 - 阈值距离内邻居最少的城市
6 分 - 工作计划的最低难度

展开讨论

祝大家新春快乐,拿 offer 拿到手软

第一题:

第一题其实是思维题,只有三种情况:

  • 空字符串输出 0
  • 回文字符串输出 1
  • 其他情况,因为只有 a 和 b 两种字符,不管是什么样的字符串,只需要拆成只有 a 的字符串和只有 b 的字符串,这两个字符串肯定是回文串,输出 2
class Solution {
    public int removePalindromeSub(String s) {
        if ("".equals(s)) {
            return 0;
        }
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return 2;
            }
            left++;
            right--;
        }
        return 1;
    }
}

第二题:

第二题就按照题目要求的过滤条件过滤和排序即可。。这题其实可以出成 sql 题

这题可以看各种语言的写法,学习骚操作一堆堆

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

class Solution {
    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        return Stream
                .of(restaurants)
                .filter((x) -> x[3] <= maxPrice)
                .filter((x) -> veganFriendly == 0 || (veganFriendly == 1 && x[2] == 1))
                .filter((x) -> x[4] <= maxDistance)
                .sorted((x, y) -> {
                    if (x[1] == y[1]) {
                        return -Integer.compare(x[0], y[0]);
                    } else {
                        return -Integer.compare(x[1], y[1]);
                    }
                })
                .map((x) -> x[0])
                .collect(Collectors.toList());

    }
}

第三题:

题目要求寻找每个点,计算到其他点最短路径不超过 distanceThresholddistanceThreshold 的点的个数。

朴素最短路径算法有这几种:

单源算法:

  • BellmanFordBellman-Ford ,时间复杂度是 o(VE)o(VE) ,优点是可以处理负权图
  • DijkstraDijkstra ,时间复杂度是 o(V2)o(V^2) ,必须无负权边

多源算法:

  • floydfloyd ,时间复杂度是 o(V3)o(V^3)

这个题看数据范围,用 n 次 DijkstraDijkstrafloydfloyd 都可以,从编码的角度,floydfloyd 显然更容易编写

import java.util.Arrays;

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] mat = new int[n][n];
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < n;j++) {
                mat[i][j] = -1;
            }
        }
        for (int[] edge: edges) {
            if (mat[edge[0]][edge[1]] == -1 || mat[edge[0]][edge[1]] > edge[2]) {
                mat[edge[0]][edge[1]] = edge[2];
                mat[edge[1]][edge[0]] = edge[2];
            }
        }
        for (int k = 0;k < n;k++) {
            for (int i = 0;i < n;i++) {
                for (int j = 0;j < n;j++) {
                    if (i == j) {
                        continue;
                    }
                    if (mat[i][k] == -1 || mat[k][j] == -1) {
                        continue;
                    }
                    int t = mat[i][k] + mat[k][j];
                    if (mat[i][j] == -1 || mat[i][j] > t) {
                        mat[i][j] = t;
                    }
                }
            }
        }
        int maxNum = 0x3fffffff;
        int maxId = -1;
        for (int i = 0;i < n;i++) {
            int t = 0;
            for (int j = 0;j < n;j++) {
                if (mat[i][j] == -1) {
                    continue;
                }
                if (mat[i][j] <= distanceThreshold) {
                    t++;
                }
            }
            if (maxNum >= t) {
                maxNum = t;
                maxId = i;
            }
        }
        return maxId;
    }
}

第四题:

第四题是比较经典的动态规划题,

dp[i][j]dp[i][j] 表示前 j 份工作的 i 天计划表,显然 dp[d][jobDifficulty.length1]dp[d][jobDifficulty.length-1] 就是我们求的结果。

状态转移方程是:dp[i][j]=min{dp[i1][k]+max{jobDifficulty[k+1]..jobDifficulty[j]}}dp[i][j] = min \{ dp[i - 1][k] + max \{jobDifficulty[k + 1] .. jobDifficulty[j]\} \}

import java.util.Arrays;

class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int[][] dp = new int[d + 1][jobDifficulty.length];
        for (int i = 1;i <= d;i++) {
            Arrays.fill(dp[i], -1);
        }
        dp[1][0] = jobDifficulty[0];
        for (int j = 1;j < jobDifficulty.length;j++) {
            dp[1][j] = Math.max(dp[1][j - 1], jobDifficulty[j]);
        }
        for (int i = 2;i <= d;i++) {
            for (int j = i - 1;j < jobDifficulty.length;j++) {
                int s = 0;
                for (int k = j;k >= i - 1;k--) {
                    s = Math.max(s, jobDifficulty[k]);
                    int t = dp[i - 1][k - 1] + s;
                    if (dp[i][j] == -1 || dp[i][j] > t) {
                        dp[i][j] = t;
                    }
                }
            }
        }
        return dp[d][jobDifficulty.length - 1];
    }
}
9
展开全部 11 讨论