以赛促练-力扣第84场双周赛反思以及第305场周赛补题_力扣双周赛为什么在晚上
赞
踩
这次参加了晚上的双周赛，但自感码力不足，做完T1就开始坐牢，接下来三题都没有思路遂放弃直接睡觉了。今天起来反思自己是否应该参加第305场周赛，想想在这短短的一晚，其实自己的码力也没有太大的提升，并且昨晚很多东西都还没有反思消化，于是还是退出了第305场周赛，准备在本文章后面补题。
第84场双周赛
T1直接拿数组模拟，没什么好说的。
T2.统计坏数对数目
枚举解法，参考TsReaper大神的思路，坏数对的数目，就是所有数对的数目，减去满足 i < j 且 j - i == nums[j] - nums[i]的数对数目，移项得 i < j 且 nums[i] - i == nums[j] - j。
如何统计在i<j的情况下nums[i] - i == nums[j] - j的数量，有一种方法是在遍历的过程中，用一个数组不断暂存所有的nums[i]-i相同结果的数量，然后想象相同结果的每个数字做排列，数量为n*(n-1)/2，这是一种动态更新的思想，能够在遍历的过程中不断更新「当前」满足i<j条件的数量。
还有一种方法是一次遍历，将做差的结果通过map.put(t,value)存起来，每次到一个新的下标j，就将其与前面做差结果相等的数量map.get(t)减掉，到最后就能把所有相等的结果减去。
class Solution {
public long countBadPairs(int[] nums) {
int len=nums.length;
long ans=1l*len*(len-1)/2;
HashMap<Integer,Integer> map=new HashMap<>();
for(int i=0;i<len;i++){
int t=nums[i]-i;
ans-=map.getOrDefault(t,0);
map.put(t,map.getOrDefault(t,0)+1);
}
return ans;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
T3.任务调度器II
由于是按顺序完成带冷却，读上来就感觉是纯纯模拟题，但是又不知道用什么数据结构怎么写。参考猿初大神的题解，模拟一遍，过程中直接就用HashMap<Integer,Long>存储同类型任务下一次应该开始的时间。
class Solution { public long taskSchedulerII(int[] tasks, int space) { long day=1; HashMap<Integer,Long> map=new HashMap<>(); for(int i:tasks){ long limit=map.getOrDefault(i,1l); if(day>=limit){ day++; //到那一天能做 map.put(i,day+space); }else{ day=map.get(i); //做完再++看下一天的 day++; map.put(i,day+space); } } //减去做完++的那一次 return day-1; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
T4.将数组拆分排序的最少替换次数
看到题目就是个不会，不知道怎么分，也不知道从何分起。
参考灵神的题解，运用贪心。其切入点就是发现最后一个数字不能够拆分，这会让前面的数字范围缩窄，那么就应该在最后一个不拆分的情况下，让前面的数字拆分都小于它，并且让这个拆分的最小值最大化。假设最后一个数字是前面数字所能达到的最大值min，那么直观地看，我们需要将倒数第二个不满足条件的数字n「最少」拆分成[n/min]上取整才可以，那么拆分次数就是这个数字「减一」，记为k。在拆分次数已知的情况下，怎么计算这次拆分的最小值，其实可以直观计算为当前数字/([n/min]上取整)，证明在灵神题解里。
class Solution {
public long minimumReplacement(int[] nums) {
long ans=0;
int len=nums.length;
int min=nums[len-1];
for(int i=len-2;i>=0;i--){
int k=(int)Math.ceil(1.0*nums[i]/min);
ans+=k-1;
min=nums[i]/k;
}
return ans;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
第305场周赛
T1数据量不大，暴力三层循环。
T2.受限条件下可以到达的节点数目
上周DFS、BFS在图中的应用没有来得及去做埋下的祸根，用邻接矩阵存储图直接变相提升难度，大无语。采用容器实现的邻接表存储可以很快找到相邻节点并且无须记录边代价。相关存图方式可以看我的算法学习-最短路算法与各种存图方式，链式前向星，配图加深理解，讲的很详细。
采用容器存图，BFS遍历一遍，这里都是只将未访问过的节点进队，所以直接无脑ans++。
class Solution { public int reachableNodes(int n, int[][] edges, int[] restricted) { HashSet<Integer>[] adj=new HashSet[n]; for(int i=0;i<n;i++){ adj[i]=new HashSet<>(); } for(int[]e:edges){ adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); } boolean[]vis=new boolean[n]; //受限点可以简单处理成已访问的点 for(int r:restricted){ vis[r]=true; } Deque<Integer> que=new ArrayDeque<>(); que.offer(0); int ans=0; while(!que.isEmpty()){ int node=que.poll(); ans++; vis[node]=true; for(int i:adj[node]){ if(!vis[i]) que.offer(i); } } return 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
同样采用容器存图，采用DFS递归遍历
class Solution { int ans=0; public int reachableNodes(int n, int[][] edges, int[] restricted) { HashSet<Integer>[] adj=new HashSet[n]; for(int i=0;i<n;i++){ adj[i]=new HashSet<>(); } for(int[]e:edges){ adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); } boolean[]vis=new boolean[n]; //受限点可以简单处理成已访问的点 for(int r:restricted){ vis[r]=true; } dfs(0,vis,adj); return ans; } public void dfs(int node,boolean[]vis, HashSet<Integer>[] adj){ vis[node]=true; ans++; for(int i:adj[node]){ if(!vis[i]){ dfs(i,vis,adj); } } } }
- 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
T3.检查数组是否存在有效划分
直观的，多种划分情况暴力递归，将接下来的情况交给子递归去做，base情况为划分点能够到达数组末尾。
下面做法是过不了 的，TLE但方法没错，原因是暴力递归想象成树，单节点分支为3，层数O(N)，复杂度O(3^N)，N为20就接近1*10^9。可以尝试在这个上面加记忆化。
class Solution { public boolean validPartition(int[] nums) { return dfs(nums,0); } //表示从index起(包括index)，能够划分nums public boolean dfs(int[]nums,int index){ if(index==nums.length) return true; int len=nums.length; boolean ans1=false; boolean ans2=false; boolean ans3=false; //index<=len-2，dfs(nums,index+2)极端情况，index+2划分到==nums.length刚好越界 if(index<=len-2&&nums[index]==nums[index+1]){ if(dfs(nums,index+2)) ans1=true; } if(index<=len-3&&nums[index]==nums[index+1]&&nums[index+1]==nums[index+2]){ if(dfs(nums,index+3)) ans2=true; } if(index<=len-3&&nums[index]+1==nums[index+1]&&nums[index+1]+1==nums[index+2]){ if(dfs(nums,index+3)) ans3=true; } return ans1||ans2||ans3; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
由于搜索状态就是「当前划分序号是否满足要求」，会出现很多子状态重复计算，可以进行记忆化DFS，通过数组m进行状态标记。
class Solution { int[]m; public boolean validPartition(int[] nums) { int len=nums.length; m=new int[len+1]; return dfs(nums,0); } //表示从index(包括index)，能够划分nums public boolean dfs(int[]nums,int index){ //如果状态已经被保存，直接返回 if(m[index]==1) return true; if(m[index]==-1) return false; if(index==nums.length) return true; int len=nums.length; boolean ans1=false; boolean ans2=false; boolean ans3=false; if(index<=len-2&&nums[index]==nums[index+1]){ if(dfs(nums,index+2)) ans1=true; } if(index<=len-3&&nums[index]==nums[index+1]&&nums[index+1]==nums[index+2]){ if(dfs(nums,index+3)) ans2=true; } if(index<=len-3&&nums[index]+1==nums[index+1]&&nums[index+1]+1==nums[index+2]){ if(dfs(nums,index+3)) ans3=true; } //记录状态 m[index]=ans1||ans2||ans3?1:-1; return ans1||ans2||ans3; } }
- 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
由于状态结果是唯一的，所以记忆化搜索其实可以改为「动态规划」解法。状态定义dp[index]表示是否能到达数组边界index，由后面的状态往前推导。
class Solution { public boolean validPartition(int[] nums) { int len=nums.length; //dp[index]代表数组边界到index开始，是否可以正确划分 boolean[]dp=new boolean[len+1]; dp[len]=true; for(int index=len-1;index>=0;index--){ if(index<=len-2&&nums[index]==nums[index+1]) dp[index]|=dp[index+2]; if(index<=len-3&&nums[index]==nums[index+1]&&nums[index+1]==nums[index+2]){ dp[index]|=dp[index+3]; } if(index<=len-3&&nums[index]+1==nums[index+1]&&nums[index+1]+1==nums[index+2]){ dp[index]|=dp[index+3]; } } return dp[0]; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
T4.最长理想子序列
子序列的题目，一眼尝试动态规划，直接TLE，过了74/84。不过的代码如下，可以看出整体复杂度O(N^2)，所以过不了。
class Solution { public int longestIdealString(String s, int k) { int len=s.length(); int[]dp=new int[len]; Arrays.fill(dp,1); for(int i=0;i<len;i++){ char b=s.charAt(i); for(int j=0;j<i;j++){ char a=s.charAt(j); if(Math.abs(b-a)<=k){ dp[i]=Math.max(dp[i],dp[j]+1); } } } int ans=1; for(int i:dp){ ans=Math.max(ans,i); } return ans; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
观察内层循环，其实不需要遍历i-1这样O(N)的复杂度，比如当 k = 3，如果当前字母为 g，那么它只能接在d e f g h i j为结尾的子序列后面，其实我们只要在遍历过程中，维护一个Map<Character, Integer> , 记录当前以某个字母结尾的最长子序列的长度，那么最大遍历次数为k.
class Solution { public int longestIdealString(String s, int k) { int len=s.length(); int[]dp=new int[len]; Arrays.fill(dp,1); //维护一个HashMap，记录当前以某个字母结尾的最长子序列的长度 HashMap<Character,Integer> map=new HashMap<>(); for(int i=0;i<len;i++){ char c=s.charAt(i); //查询前面以绝对值差<=k的那些字母结尾的最长子序列的长度 for(int j=0;j<=k;j++){ char left=(char)(c-j); char right=(char)(c+j); if(map.containsKey(left)){ dp[i]=Math.max(dp[i],map.get(left)+1); } if(map.containsKey(right)){ dp[i]=Math.max(dp[i],map.get(right)+1); } } //更新当前字母的最长长度 map.put(c,dp[i]); } int ans=1; for(int i:dp){ ans=Math.max(ans,i); } return 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
