其实有时候觉得一天一道题真的是小菜一碟，但是又有时候觉得忙的时候力扣都忘记打开。总而言之空闲时间就刷刷题换换思路吧，而且我现在越来越发现刷的没有力扣涨的快。。。呕心沥血一年多，没刷的题比去年刚加入leetcode时的题目还多。。开始刷题吧。
网络延迟时间
题目：有 N 个网络节点，标记为 1 到 N。给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
注意:
N 的范围在 [1, 100] 之间。
K 的范围在 [1, N] 之间。
times 的长度在 [1, 6000] 之间。
所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。
题目截图
思路：这个题目前打算就是用map存储，因为是有向的，所以当前节点往外走的都记录。一层一层找。用set判重，连接过的就不算。最终有没连接过的直接-1.最终从k都能连上，则取最大的时间累积。我去试试代码
说真的，就我写的这个代码，能过我自己都觉得神奇。。先贴代码：
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
Map<Integer, Map<Integer, Integer>> map = new TreeMap<Integer, Map<Integer, Integer>>();
for(int[] i:times) {
Map<Integer, Integer> v = map.getOrDefault(i[0], new HashMap<Integer, Integer>());
v.put(i[1],i[2]);
map.put(i[0] , v);
}
Map<Integer,Integer> set = new HashMap<Integer,Integer>();
set.put(k, 0);
//如果有没连上的，直接-1
dfs(map, k, set);
if(set.size()<n) return -1;
int max = -1;
for(int i:set.values()) max = Math.max(max, i);
return max;
}
public void dfs(Map<Integer, Map<Integer, Integer>> map,int temp,Map<Integer,Integer> set) {
Map<Integer, Integer> cur = map.get(temp);
if(cur == null) return;
for(int i :cur.keySet()) {
//如果这个节点连上了判断能不能来个更短的路程
int time = set.get(temp)+cur.get(i);
if(set.containsKey(i)) {
if(set.get(i)>time) {
set.put(i, time);
dfs(map, i, set);
}
}else {
set.put(i, time);
dfs(map, i, set);
}
}
}
}
一开始我甚至都想到并查集了，但是因为路径不唯一，所以这个思路pass，不过现在反过来看看好像也不是不行。继续说上面的代码：第一步构图：构成一个有向图。第二部是从k点开始遍历这个图，然后这个题有一种现象：就是有的短路径时间多，长路径时间少，所以这里不能达到的点就pass，还得跟用时比较。就衍生成了上面的一大片代码。因为这个性能着实有点问题，所以尝试优化了下：
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
for(int[] i:times) {
map.computeIfAbsent(i[0],v->new HashMap<>()).put(i[1], i[2]);
}
int[] d = new int[n+1];
Arrays.fill(d,Integer.MAX_VALUE);
d[0] = 0;
d[k] = 0;
dfs(map, k, d);
int max = -1;
for(int i:d) {
if(i == Integer.MAX_VALUE) return -1;
max = Math.max(max, i);
}
return max;
}
public void dfs(Map<Integer, Map<Integer, Integer>> map,int temp,int[] d) {
Map<Integer, Integer> cur = map.get(temp);
if(cur == null) return;
for(int i :cur.keySet()) {
//如果这个节点连上了判断能不能来个更短的路程
if(d[i]>d[temp]+cur.get(i)){
d[i] = d[temp]+cur.get(i);
dfs(map, i, d);
}
}
}
}
重点是虽然性能快了一倍，但是还是垫底，所以我直接去看看性能第一的代码了：
看了性能第一的代码脑壳更疼了，毕竟看不懂。。我先贴出来：
class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
//建立有向图的临界表
int[][] arr = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
arr[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 0; i < times.length; i++) {
arr[times[i][0]][times[i][1]] = times[i][2];
}
//获取到初始节点的距离
int[] distances = new int[N + 1];
for (int i = 1; i <= N; i++) {
distances[i] = arr[K][i];
}
//标记节点是否已经访问
int[] visit = new int[N + 1];
visit[K] = 1;
int index = 0;//标记当前排查的节点
for (int i = 1; i <= N; i++) {
int min = Integer.MAX_VALUE;//最近距离
//贪心策略找出距离当前节点最近的下级节点
for (int j = 1; j <= N; j++) {
if (visit[j] == 0 && distances[j] < min) {
min = distances[j];
index = j;//指针移动到距离初始节点最近的节点
}
}
//标记新移动到的节点已访问
visit[index] = 1;
//更新新移动节点到后序节点的距离集合
for (int j = 1; j <= N; j++) {
if (visit[j] == 0 && arr[index][j] != Integer.MAX_VALUE) {
distances[j] = Math.min(distances[j], min + arr[index][j]);//初始节点到下级目标节点和当前节点到下级目标节点中选取较小的那个路径
}
}
//再继续循环直到所有的节点都被访问过
}
//找出距离中最远的距离即为网络延迟所需的最大时间
int res = Integer.MIN_VALUE;
for (int i = 1; i <= N; i++) {
if (i == K) continue;
res = Math.max(res, distances[i]);
}
return Integer.MAX_VALUE == res ? -1 : res;//如果最大值为MAX_VALUE说明存在节点没有被访问到
}
}
因为这个题的特殊性：从1到N的机子。所以可以用二维数组来构图。然后我刚刚去debug跑了两遍这个性能第一的代码。确实蛮神奇的。属于一层一层往下找。一直是取较小的路径，所以不怕多条方式先计算长路径的情况。
整体而言我觉得是精巧的，但是这个题现在的性能比较好是因为机子是1-N顺序一样一个而且N的范围100以内的。反正我觉得如果N的边界比较大并且数字不连续的话，还是我的方法好（强行挽尊一波）。哈哈，好了，这个题就这样了，下一题。
移除最多的同行或同列石头
题目：n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
示例 1：
输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
解释：一种移除 5 块石头的方法如下所示：
- 移除石头 [2,2] ，因为它和 [2,1] 同行。
- 移除石头 [2,1] ，因为它和 [0,1] 同列。
- 移除石头 [1,2] ，因为它和 [1,0] 同行。
- 移除石头 [1,0] ，因为它和 [0,0] 同列。
- 移除石头 [0,1] ，因为它和 [0,0] 同行。
石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。
示例 2：
输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：一种移除 3 块石头的方法如下所示：
- 移除石头 [2,2] ，因为它和 [2,0] 同行。
- 移除石头 [2,0] ，因为它和 [0,0] 同列。
- 移除石头 [0,2] ，因为它和 [0,0] 同行。
石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。
示例 3：
输入：stones = [[0,0]]
输出：0
解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。
提示：
1 <= stones.length <= 1000
0 <= xi, yi <= 104
不会有两块石头放在同一个坐标点上
思路：还好我事先知道这个月是图论+并查集月。所以审完题我看了下标签大概知道这个题的思路了。首先这个题是个并查集的题。而说到并查集，这个题列和行可以删除，其实这个又说到圈子了。我简单化个图来理解：
并查集，找圈子
下面是实现代码：
class Solution {
// 用一个列表来保存并查集
List<Integer> point;
public int removeStones(int[][] stones) {
point = new ArrayList<>();
int n = stones.length;
// 每一个点存下标
for(int i = 0; i < n; i++) {
point.add(i);
}
//最多要有n个石子，一个都不能删除
int res = n;
// 暴力双层循环，依次和后面所有的比较是不是一个圈子的。
for(int i = 0; i < n - 1; i ++) {
for(int j = i + 1; j < n; j ++) {
// 看两个石子的根是不是一样。
int a = find(i), b = find(j);
// 如果这两个石头是同行或同列，那么可以拿取一个圈子，合并
if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
// 如果之前不在一个圈子则合并，如果之前已经在一个圈子就算了
if(a != b){
// 这两个根合并
point.set(a, b);
// 圈子数少一
res --;
}
}
}
}
return n - res;
}
// 寻根方法，找到第一个点。这里下标代表点，值代表根
public int find(int x) {
if(point.get(x) != x) {
point.set(x, find(point.get(x)));
}
return point.get(x);
}
}
这个代码能过我就很庆幸了，性能就不能提了。讲真，这个代码其实应该不属于标准的并查集，毕竟都双层for循环了。但是让我说我又不知道怎么解决。毕竟之前的并查集是完全的两个点。而这个 其实本质上是两个线能不能并一起。头发薅掉一大把都没想出来怎么实现，甚至之间我都觉得这个题dfs可能都更容易做一点。但是因为知道这个月是并查集月，所以硬着头皮用并查集的方式实现的不伦不类的。我去换我喜欢的方式实现试试吧。
class Solution {
boolean[] flag;
public int removeStones(int[][] stones) {
flag = new boolean[stones.length];
int res = 0;
for(int i = 0;i<stones.length;i++) {
if(flag[i] == true) continue;
res++;
dfs(stones, i);
}
return stones.length - res;
}
public void dfs(int[][] stones,int temp) {
flag[temp] =true;
for(int i = 0;i<stones.length;i++) {
if(flag[i] == true) continue;
//这个人没圈子，则判断是不是一个圈子里的。是的话递归继续找
if(stones[i][0] == stones[temp][0] || stones[i][1] == stones[temp][1]) {
dfs(stones, i);
}
}
}
}
虽说性能也不咋地，但是比不伦不类的并查集好的多了。而且代码简单好撸。。。哎，这个题思路很容易想， 就是实现起来比较复杂。不行，我还是不服，我要去看看大佬们并查集怎么实现的：
class Solution {
public int removeStones(int[][] stones) {
int[] dsu = new int[20000];
for (int i = 0; i < dsu.length; i++) dsu[i] = i;
for (int[] stone : stones)
union(dsu, stone[0], stone[1] + 10000);
Set<Integer> set = new HashSet<>();
for (int[] stone : stones)
set.add(find(dsu, dsu[stone[0]]));
return stones.length - set.size();
}
private void union(int[] dsu, int x, int y) {
int fx = find(dsu, x);
int fy = find(dsu, y);
if (fx != fy)
dsu[fx] = fy;
}
private int find(int[] dsu, int x) {
while (dsu[x] != x) {
dsu[x] = dsu[dsu[x]];
x = dsu[x];
}
return x;
}
}
简单来说有一种什么感觉呢，看完了，我悟了。首先说到底这个题是横纵坐标的并查。出现了0,0石子，说明横坐标0和纵坐标0是一个圈子里的了。出现了0,2说明横坐标0 和纵坐标2到一个圈子里了。0,0 和0，2两个点说明横坐标0，纵坐标0，纵坐标2三个线是一个点。
这么看来的话，这里要做的是把所有的线放到一个圈子了。然后线对应的点自然也就只有一个领头人。由此，知道有几个领头人必须要留下，那么剩下的就自然可以删除。
反正代码我是看懂了。逻辑我也能捋明白。自己想就想不出来。更别说写了。
我现在烦躁的一批。自以为会了并查，确只在第一层，看山是山的程度。稍微变化一点就想不到了。还是练得少啊。这个题就这样了，以后随着做随着练吧。下一题。
可获得的最大点数
题目：几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。你的点数就是你拿到手中的所有卡牌的点数之和。给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
示例 1：
输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
示例 2：
输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
示例 3：
输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
示例 4：
输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。
示例 5：
输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出：202
提示：
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length
思路：这个题就是典型的dp。其实感觉也不用dp。简单来说这个题因为一定左右拿牌，所以最终结果的差别只不过是左边拿几张，右边拿几张的区别。而这个左右张数要选择最大值。我这边初步想法是先从左边全拿，然后一张一张退回，从右边拿。最终变成右边全拿。记录这中间的最大值就完事了。也是O（n）时间复杂度。。我去试试。
第一版代码：
class Solution {
public int maxScore(int[] cardPoints, int k) {
int len = cardPoints.length;
int sum = 0;
for(int i = 0;i<k;i++) sum += cardPoints[i];
if(k == len) return sum;
int ans = sum;
for(int i = k-1;i>=0;i--) {
int temp = sum-cardPoints[i]+cardPoints[len-(k-i)];
ans = Math.max(temp, ans);
sum = temp;
}
return ans;
}
}
性能也很好，并且这个dp是着实想不到了，我去看看题解吧。
额，题解看了也差不多就是我这个思路，我也是才知道这个叫做滑窗。。反正既然是一样的思路就算了，我也不贴代码了。这个题就这样了。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利，提现拜个早年吧~！
网友评论