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

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

image.png

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

共 11 个回复

第二题的中文翻译没有翻id降序,最后才加上去这个条件,机翻都比这强

9

祝大家新春快乐,拿 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

第一题我的心情是复杂的 mmp

作为一个菜鸡 第一反应是卧槽?这?longest palindrome? dp? 不对,难道是回溯?我靠 这都不是easy了吧
绝望的看着时间一分分过去,写的复杂到根本不信是easy
半小时过去了 痛定思痛 决定放弃 把第二题写了
回来重新看了遍题。shit 这tm不就是。。撤了a撤了b就完事儿了吗。。gg

class Solution {
    public int removePalindromeSub(String s) {
        if (s.length() == 0) return 0;
        if (isPalindrome(s)) return 1;
        else return 2;
    }
            
    boolean isPalindrome(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        for (int i = 0; i < n / 2; i++) {
            if (cs[i] != cs[n-1-i]) {
                // System.out.println(s + " is not a palindrome");
                return false;
                
            }
        }
        return true;
    }
}

哭了

5

我最讨厌回文,没卵用

3

输入:restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, maxDistance = 10
输出:[4,3,2,1,5]
2和3的rating 不是一样么?为什么[4,2,3,1,5]不行?

2

国服的翻译能认真点吗,好几次了!上次是数据错,这次连题目都没翻译完整!

2

求解我这题错在哪儿,第40个示例一直过不去,结果是33,可是我算出来的是27.。。。。

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        path = [[] for _ in range(n)]
        ans = [0 for _ in range(n)]
        for edge in edges:
            path[edge[0]].append((edge[1], edge[2]))
            path[edge[1]].append((edge[0], edge[2]))
        for i in range(n):
            vis, val = set(), set()
            vis.add(i)
            self.help(path, i, 0, distanceThreshold, vis, val)
            # print(val)
            ans[i] = len(val)
        mx, res = min(ans), 0
        for i in range(n):
            if ans[i] == mx:
                res = i
        return res
            
    def help(self, path, i, w, distanceThreshold, vis, val):
        for j in path[i]:
            if j[0] not in vis and w + j[1] <= distanceThreshold:
                val.add(j[0])
                vis.add(j[0])
                self.help(path, j[0], w + j[1], distanceThreshold, vis, val)
1

结束啦,第二题case有问题

请问大家,第一题这个case是怎么用两次操作处理完的?

输入:
"bbaabaaa"
输出:
3
预期:
2

xiangku