Interview-Notes

class Solution { List<List<Integer>> edges; //存储邻接矩阵 int[] visited; boolean valid = true; public boolean canFinish(int numCourses, int[][] prerequisites) { edges = new ArrayList<>(); //初始化邻接矩阵的列 for (int i = 0; i < numCourses; i++) { edges.add(new ArrayList<Integer>()); } //给每一列都添加他的后置课程 for (int[] info : prerequisites) { edges.get(info[1]).add(info[0]); } //遍历每一个课程，和vaild值一起进行dfs，判断每一个课程是否可以学习完成 visited = new int[numCourses]; 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; } //当出现有一个环的时候即为false }else if(visited[v] == 1) { valid = false; return; } } visited[u] = 2; //代表该门课程可以学习完成 } }

// 定义前缀树的节点，每个节点有一个子数组和标志位，标志位代表该节点是否为最终节点 // insert方法插入字符串，若当前节点的子数组中的对应索引位置为空，则新建前缀树的节点 // search 和 startWiths的区别在于search需要判断返回节点的isEnd属性 class TrieNode { TrieNode[] children; boolean isEnd; TrieNode() { children = new TrieNode[26]; isEnd = false; } } class Trie { TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { TrieNode node = root; for (int i = 0; i < word.length(); i++) { int index = word.charAt(i) - 'a'; if (node.children[index] == null){ node.children[index] = new TrieNode(); } node = node.children[index]; } node.isEnd = true; } public boolean search(String word) { TrieNode node = searchPrefix(word); return node != null && node.isEnd; } public boolean startsWith(String prefix) { TrieNode node = searchPrefix(prefix); return node != null; } public TrieNode searchPrefix(String word) { TrieNode node = root; for (int i = 0; i < word.length(); i++) { int index = word.charAt(i) - '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); */

class Solution { //使用构建图，使用HashMap存储节点和比率 //对每个查询使用DFS查询两个节点是否存在连接，并计算比率 // putIfAbsent方法 V putIfAbsent(K key, V value); // 如果之前 Map 中没有这个键，那么返回 null。 // 如果之前已经有这个键了，那么返回该键之前关联的值，并且不会替换已有的值。 HashMap<String, HashMap<String, Double>> hs = new HashMap<>(); public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { for (int i = 0; i < equations.size(); i++) { String u = equations.get(i).get(0); String v = equations.get(i).get(1); double k = values[i]; // 构建图 hs.putIfAbsent(u, new HashMap<>()); hs.putIfAbsent(v, new HashMap<>()); hs.get(u).put(v, k); hs.get(v).put(u, 1 / k); } double[] res = new double[queries.size()]; for (int i = 0; i < queries.size(); i++) { String u = queries.get(i).get(0); String v = queries.get(i).get(1); if (!hs.containsKey(u) || !hs.containsKey(v)) { res[i] = -1.0; } else { res[i] = dfs(u, v, new HashSet<String>()); } } return res; } public double dfs(String start, String end, HashSet<String> visited) { if (hs.get(start).containsKey(end)) { //直接包含 return hs.get(start).get(end); } visited.add(start); for (Map.Entry<String, Double> neighbor : hs.get(start).entrySet()) { if (!visited.contains(neighbor.getKey())) { double path = dfs(neighbor.getKey(), end, visited); if (path != -1.0) { return path*neighbor.getValue(); } } } return -1.0; } }

class Solution { // O（n）就不能是排序 // 用HashSet存储所有元素 // 对于一个最长序列hashSet中一定不包含当前的nums[i] - 1; // 判断是否存在nums[i] + 1; public int longestConsecutive(int[] nums) { if (nums.length == 0) { return 0; } HashSet<Integer> hs = new HashSet<>(); for (int i = 0; i < nums.length; i++) { hs.add(nums[i]); } int max = 1; for (int num : nums) { if (hs.contains(num - 1)) { continue; } int maxTmp = 1; while (hs.contains(num + 1)) { num += 1; maxTmp++; } max = Math.max(maxTmp, max); } return max; } }

class Solution { public int majorityElement(int[] nums) { //hashmap 使用HashMap,若其中存在，则value + 1,不存在则将相应的key添加进去 Map<Integer,Integer> map = new HashMap(); for(int num: nums){ map.put(num,map.getOrDefault(num,0)+1); if(map.get(num) > nums.length /2){ return num; } } return -1; } }

class Solution { public boolean isValid(String s) { // 字符串中出现左括号就将右括号压入栈中， // 出现右括号就与栈顶的元素匹配,判断栈顶的元素是不是对应的右括号 // 不匹配则返回false // 最终需要检查栈是否为空 // 不为空说明还有未匹配的左括号 Deque<Character> stack = new LinkedList<>(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') { stack.push(s.charAt(i)); } else { if (stack.isEmpty()) { return false; } char top = stack.pop(); if (s.charAt(i) == ']' && top != '[' || (s.charAt(i) == '}' && top != '{') || (s.charAt(i) == ')' && top != '(')) { return false; } } } return stack.isEmpty(); //不匹配说明有多余的左括号 } }

class Solution { // 时间复杂度O(n)，空间复杂度O(1) public int lengthOfLongestSubstring(String s) { if (s.length() == 0) { return 0; } // HashSet + 滑动窗口 or HashMap + 滑动窗口 HashMap<Character, Integer> hs = new HashMap<>(); int left = 0, right = 0, max = Integer.MIN_VALUE; while (right < s.length()) { char c = s.charAt(right); if (hs.containsKey(c) && hs.get(c) >= left) { //发现重复字符且重复字符的位置 > 左边界 left = hs.get(c) + 1; // left 的下一个位置是上一次出现重复的位置加1 } hs.put(c, right); max = Math.max(right - left + 1, max); right++; } return max; } }

class Solution { int ptr = 0; // 栈 // 对于数字、字符串和左括号将其压入栈中 // 遇到右括号时，将相邻的左括号和字符串数字都弹出 // 并将解码后的字符串在压入栈中 // 定义一个全局变量用来遍历字符串 // 使用了StringBuffer的insert方法 StringBuffer insert(int offset, String str) 在指定位置插入字符串 public String decodeString(String s) { Stack<String> stack = new Stack<>(); while (ptr < s.length()) { char c = s.charAt(ptr); if (Character.isDigit(c)) { //数字 String digits = getDigits(s); stack.push(digits); } else if (Character.isLetter(c) || c == '[') { stack.push(String.valueOf(c)); ptr++; } else { // 右括号 StringBuffer sb = new StringBuffer(); while (!stack.peek().equals("[")) { sb.insert(0, stack.pop()); } String str = sb.toString(); // stack.pop(); // 删除左括号 StringBuffer tmp = new StringBuffer(); int repeat = Integer.parseInt(stack.pop()); for (int j = 0; j < repeat; j++) { tmp.append(str); } stack.push(tmp.toString()); ptr++; } } StringBuffer sb = new StringBuffer(); while (!stack.isEmpty()) { sb.insert(0, stack.pop()); } return sb.toString(); } public String getDigits(String s) { // 获得数字 StringBuffer sb = new StringBuffer(); while (Character.isDigit(s.charAt(ptr)) && ptr < s.length()) { sb.append(s.charAt(ptr++)); } return sb.toString(); } }

class Solution { // 这一题和最小覆盖子串有点相似，但是这里需要找的子串不能包括其他元素,需要加一个长度限制的检查 // 异位词就是不同的排列方式 // 用哈希表存储字符串中每个字符出现的次数 // 维护一个p.length()长度的滑动窗口 // 如果滑动窗口内的元素出现频率等于p的频率，则为字母异位词 // 时间复杂度O(m + (n - m + 1)*26) // 改进的时间复杂度O(m + n) public List<Integer> findAnagrams(String s, String p) { // List<Integer> res = new ArrayList(); // int[] pCount = new int[26]; // for (int i = 0; i < p.length(); i++) { // pCount[p.charAt(i) - 'a']++; // } // int left = 0; int right = 0; // int[] sCount = new int[26] ; // while (right < s.length()) { // if(right - left + 1 > p.length()) { // sCount[s.charAt(left) - 'a']--; // left++; // } // sCount[s.charAt(right) - 'a']++; // if(right - left + 1 == p.length()) { // boolean isEqual = true; // for (int i = 0; i < 26; i++) { // if(pCount[i] != sCount[i]) { // isEqual = false; // break; // } // } // if (isEqual) { // res.add(left); // } // } // right++; // } // return res; List<Integer> res = new ArrayList<>(); int sLen = s.length(), pLen = p.length(); if (sLen < pLen) { return res; } HashMap<Character, Integer> hs = new HashMap<>(); for (int i = 0; i < pLen; i++) { char c = p.charAt(i); hs.put(c, hs.getOrDefault(c, 0) + 1); } int required = hs.size(), current = 0; HashMap<Character, Integer> window = new HashMap<>(); int left = 0, right = 0; while (right < sLen) { char word = s.charAt(right); if (hs.containsKey(word)) { window.put(word, window.getOrDefault(word, 0) + 1); if (window.get(word).equals(hs.get(word))) { current++; } } while (right - left + 1 >= pLen) { char tmp = s.charAt(left); if (current == required) { res.add(left); } if (hs.containsKey(tmp)) { if (window.get(tmp).equals(hs.get(tmp))) { current--; } window.put(tmp, window.get(tmp) - 1); } left++; } right++; } return res; } }