【周赛复盘】力扣第 305 场单周赛

【周赛复盘】力扣第 305 场单周赛

目录

​​1.算术三元组的数目​​

​​1）题目描述​​​​2）原题链接​​​​3）思路解析​​​​4）模板代码​​​​5）算法与时间复杂度​​

​​2.受限条件下可到达节点的数目​​

​​1）题目描述​​​​2）原题链接​​​​3）思路解析​​​​4）模板代码​​​​5）算法与时间复杂度​​

​​3.检查数组是否存在有效划分​​

​​1）题目描述​​​​2）原题链接​​​​3）思路解析​​​​4）模板代码​​​​5）算法与时间复杂度​​

​​4.最长理想子序列​​

​​1）题目描述​​​​2）原题链接​​​​3）思路解析​​​​4）模板代码​​​​5）算法与时间复杂度​​

1.算术三元组的数目

1）题目描述

给你一个下标从 0 开始、严格递增 的整数数组 ​​nums​​​ 和一个正整数 ​​diff​​​ 。如果满足下述全部条件，则三元组 ​​(i, j, k)​​ 就是一个 算术三元组 ：

i < j < k ，​​nums[j] - nums[i] == diff​​ 且​​nums[k] - nums[j] == diff​​ 返回不同 算术三元组 的数目。

2）原题链接

3）思路解析

4）模板代码

public int arithmeticTriplets(int[] arr, int diff) { int ans=0; int n=arr.length; for (int i = 0; i <=n-3; i++) { for (int j = i+1; j <=n-2; j++) { for (int k = j+1; k <=n-1; k++) { if (arr[j]-arr[i]==diff&&arr[k]-arr[j]==diff) ans++; } } } return ans; }

5）算法与时间复杂度

2.受限条件下可到达节点的数目

1）题目描述

现有一棵由 ​​n​​​个节点组成的无向树，节点编号从​​0 ​​​到​​n - 1 ​​​，共有​​n - 1​​条边。

给你一个二维整数数组 ​​edges​​​ ，长度为​​ n - 1​​​ ，其中 ​​edges[i] = [ai, bi] ​​​表示树中节点 ​​ai ​​​和 ​​bi​​​ 之间存在一条边。另给你一个整数数组 ​​restricted​​ 表示 受限 节点。

在不访问受限节点的前提下，返回你可以从节点 ​​0​​ 到达的 最多 节点数目。

注意，节点 ​​0​​ 不会标记为受限节点。

2）原题链接

3）思路解析

4）模板代码

Map> map=new HashMap<>(); Set set=new HashSet<>(); int ans=0; public int reachableNodes(int n, int[][] edges, int[] restricted) { for (int v:restricted) set.add(v); for (int[] a:edges){ add(a[0],a[1]); add(a[1],a[0]); } dfs(0,-1); return ans; } void dfs(int u,int fa){ ans++; if (!map.containsKey(u)) return; for (int h:map.get(u)){ if (set.contains(h)||h==fa) continue; dfs(h,u); } } void add(int a,int b){ if (!map.containsKey(a)) map.put(a,new LinkedList<>()); map.get(a).add(b); }

5）算法与时间复杂度

3.检查数组是否存在有效划分

1）题目描述

给你一个下标从 0 开始的整数数组 ​​nums​​ ，你必须将数组划分为一个或多个 连续 子数组。

如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：

子数组恰由​​2​​​ 个相等元素组成，例如，子数组​​ [2,2]​​ 。子数组恰由​​3​​​ 个相等元素组成，例如，子数组​​[4,4,4]​​。子数组恰由​​3​​​ 个连续递增元素组成，并且相邻元素之间的差值为​​1 ​​​。例如，子数组​​ [3,4,5]​​​ ，但是子数组​​[1,3,5]​​不符合要求。

如果数组 至少 存在一种有效划分，返回 ​​true ​​​，否则，返回 ​​false ​​。

2）原题链接

3）思路解析

4）模板代码

public boolean validPartition(int[] arr) { int n=arr.length; boolean[] f=new boolean[n+1]; f[0]=true; for (int i = 2; i<=n; i++) { int x=i-1; if (arr[x]==arr[x-1]) f[i]|=f[i-2]; if (i>2){ if (arr[x]==arr[x-1]&&arr[x-1]==arr[x-2]) f[i]|=f[i-3]; if (arr[x]+arr[x-2]==arr[x-1]*2&&arr[x]-2==arr[x-2]) f[i]|=f[i-3]; } } return f[n]; }

5）算法与时间复杂度

4.最长理想子序列

1）题目描述

给你一个由小写字母组成的字符串 ​​s​​​ ，和一个整数 ​​k​​​ 。如果满足下述条件，则可以将字符串​​ t​​ 视作是 理想字符串 ：

​​t​​​是字符串​​s​​ 的一个子序列。​​t​​ 中每两个相邻字母在字母表中位次的绝对差值小于或等于​​ k​​​ 。返回最长理想字符串的长度。

字符串的子序列同样是一个字符串，并且子序列还满足：可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。

注意：字母表顺序不会循环。例如，​​'a' ​​​和​​'z'​​​在字母表中位次的绝对差值是 ​​25​​​ ，而不是 ​​1​​ 。

2）原题链接

3）思路解析

4）模板代码

class Solution { int[] f=new int[26]; public int longestIdealString(String s, int k) { char[] c=s.toCharArray(); int len=c.length; for (int i = 0; i

5）算法与时间复杂度

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。