HHOT 100（61~80）
前言
2023-7-2 10:25:40
推荐
207. 课程表【中等】
课程表
提示
中等
1.6K
相关企业
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1： 输入：numCourses = 2, prerequisites = [[1,0]] 输出：true 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。 示例 2： 输入：numCourses = 2, prerequisites = [[1,0],[0,1]] 输出：false 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的
。
提示：
1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同
拓扑排序
BFS
class Solution { List<List<Integer>> edges;//有向图 int [] indeg;//入度 public boolean canFinish(int numCourses, int[][] prerequisites) { edges=new ArrayList<List<Integer>>(); for(int i=0;i<numCourses;i++){ edges.add(new ArrayList<Integer>()); } indeg=new int[numCourses]; for(int[] info:prerequisites){ edges.get(info[1]).add(info[0]); indeg[info[0]]++; } //拓扑排序 Queue<Integer> queue = new LinkedList<Integer>(); for(int i=0;i<numCourses;i++){ if(indeg[i]==0){ queue.offer(i); } } //广度优先搜索 int visited=0; while(!queue.isEmpty()){ visited++; int u=queue.poll(); for(int v:edges.get(u)){ indeg[v]--; if(indeg[v]==0){ queue.offer(v); } } } return visited==numCourses; } }
参考
dfs
class Solution { List<List<Integer>> edges;//有向图 int[] visited; boolean valid=true; public boolean canFinish(int numCourses, int[][] prerequisites) { edges=new ArrayList<List<Integer>>(); for(int i=0;i<numCourses;i++){ edges.add(new ArrayList<Integer>()); } visited=new int[numCourses]; for(int[] info:prerequisites){ edges.get(info[1]).add(info[0]); } for(int i=0;i<numCourses&&valid;i++){ if(visited[i]==0){ dfs(i); } } return valid; } public void dfs(int u){ visited[u]=1; for(int v:edges.get(u)){ if(visited[v]==0){ dfs(v); if(!valid){ return; } }else if(visited[v]==1){ valid=false; return; } } visited[u]=2; } }
208. 实现 Trie (前缀树)【中等】
208.实现 Trie (前缀树)
中等
1.5K
相关企业
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
示例： 输入 ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] 输出 [null, null, true, false, true, null, true] 解释 Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 True trie.search("app"); // 返回 False trie.startsWith("app"); // 返回 True trie.insert("app"); trie.search("app"); // 返回 True
提示：
1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次
官方
class Trie { private Trie[] children; private boolean isEnd; public Trie() { children = new Trie[26]; isEnd = false; } public void insert(String word) { Trie node = this; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); int index = ch - 'a'; if (node.children[index] == null) { node.children[index] = new Trie(); } node = node.children[index]; } node.isEnd = true; } public boolean search(String word) { Trie node = searchPrefix(word); return node != null && node.isEnd; } public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; } private Trie searchPrefix(String prefix) { Trie node = this; for (int i = 0; i < prefix.length(); i++) { char ch = prefix.charAt(i); int index = ch - 'a'; if (node.children[index] == null) { return null; } node = node.children[index]; } return node; } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */
215. 数组中的第K个最大元素【中等】
215.数组中的第K个最大元素
中等
2.2K
相关企业
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104
HashMap
class Solution { public int findKthLargest(int[] nums, int k) { Map<Integer, Integer> map = new TreeMap<Integer, Integer>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }); for (int i = 0; i < nums.length; i++) { int pre = map.getOrDefault(nums[i], 0); map.put(nums[i], ++pre); } Integer[] keys = new Integer[map.size()]; Integer[] values = new Integer[map.size()]; map.values().toArray(values); map.keySet().toArray(keys); int res = 0; // int c = 0; // for (int i = 0; i < values.length; i++) { // if (c >= k) { // break; // } // while (values[i] > 0) { // values[i]--; // c++; // res = keys[i]; // } // } int sum=0; int i=0; for (i=0;i<values.length;i++){ sum+=values[i]; //刚好超过的临界值 if(sum>=k&&sum-values[i]<=k){ break; } } res=keys[i]; return res; } }
221. 最大正方形【中等】
221.最大正方形
中等
1.5K
相关企业
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
示例 1： 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：4 示例 2： 输入：matrix = [["0","1"],["1","0"]] 输出：1 示例 3： 输入：matrix = [["0"]] 输出：0
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 ‘0’ 或 ‘1’
参考
class Solution { //暴力解法 public int maximalSquare(char[][] matrix) { int rows=matrix.length; int columns=matrix[0].length; if(rows==0||columns==0){ return 0; } int maxSide=0; for(int i=0;i<rows;i++){ for(int j=0;j<columns;j++){ //左上角=1 if(matrix[i][j]=='1'){ maxSide=Math.max(maxSide,1); //可能的最大正方形边长 int currentMaxSide=Math.min(rows-i,columns-j); for(int k=1;k<currentMaxSide;k++){ boolean flag=true; //右下角 if(matrix[i+k][j+k]=='0'){ break; } //外一环 for(int m=0;m<k;m++){ if(matrix[i+k][j+m]=='0'||matrix[i+m][j+k]=='0'){ flag=false; break; } } if(flag){ maxSide=Math.max(maxSide,k+1); }else{ break; } } } } } int maxSquare=maxSide*maxSide; return maxSquare; } }
参考
动态规划
class Solution { //动态规划 public int maximalSquare(char[][] matrix) { int rows=matrix.length; int columns=matrix[0].length; if(rows==0||columns==0){ return 0; } int maxSide=0; int[][] dp=new int[rows][columns]; for(int i=0;i<rows;i++){ for(int j=0;j<columns;j++){ if(matrix[i][j]=='1'){ if(i==0||j==0){ dp[i][j]=1; }else{ dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1; } maxSide=Math.max(maxSide,dp[i][j]); } } } int maxSquare=maxSide*maxSide; return maxSquare; } }
