Interview-Notes

class Solution { // 方法1：暴力，两重for循环，第一重for循环代表开头，第二重for循环代表结尾，遍历求和，时间复杂度O（n^2） // 方法2：前缀和+HashMap，类似于两数之和，用hashmap可以降时间复杂度 // public int subarraySum(int[] nums, int k) { int pre = 0; int count = 0; HashMap<Integer,Integer> hs = new HashMap<>(); // hashput存储的是前缀和 hs.put(0,1); //连续子数组，什么都没有默认为0 for (int i = 0; i < nums.length; i++) { pre += nums[i]; if (hs.containsKey(pre - k)) { count += hs.get(pre - k); } hs.put(pre, hs.getOrDefault(pre, 0) + 1); } return count; } }

class Solution { // 深度优先搜索：往一个方向遍历，走到头就回溯，再往另外一个方向遍历 // 广度优先搜索：从一个位置开始，向他的相邻位置搜索，逐层进行，用队列实现，需要用一个boolean数组进行标记,避免重复 // 岛屿数量这个题是深度优先搜索和广度优先搜索的基础题 // 深度优先代码相对简单，遍历字符数组，过程碰到'1'就进行深搜，深搜的过程只要判断是否越界，元素是否为'1'，对相邻'1'进行深度优先 int[][] pos = {{1,0}, {-1,0},{0,1},{0,-1}}; public int numIslands(char[][] grid) { int m = grid.length; int n = grid[0].length; int num = 0; boolean[][] visited = new boolean[m][n]; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if ( grid[i][j] == '1') { dfs(grid,i,j); num++; } } } return num; } public void dfs(char[][] grid, int row, int col) { if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == '0') { return; } grid[row][col] = '0'; dfs(grid, row + 1, col); dfs(grid, row - 1, col); dfs(grid, row, col + 1); dfs(grid, row, col - 1); } // public void dfs (char[][] grid, int row, int col) { // if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == '0') { // return; // } // grid[row][col] = '0'; // dfs(grid, row - 1, col); // dfs(grid, row + 1, col); // dfs(grid, row, col + 1); // dfs(grid, row, col - 1); // } public void bfs(char[][] grid, int row, int col, boolean[][] visited) { grid[row][col] = '0'; visited[row][col] = true; Queue<int[]> que = new LinkedList<>(); que.offer(new int[]{row,col}); while (!que.isEmpty()) { int[] cur = que.poll(); int x = cur[0]; int y = cur[1]; for (int[] tmp : pos) { int curX = tmp[0] + x; int curY = tmp[1] + y; if (curX < 0 || curX >= grid.length || curY < 0 || curY >= grid[0].length || grid[curX][curY] == '0' || visited[curX][curY]) { continue; } que.offer(new int[]{curX, curY}); visited[curX][curY] = true; } } } }

ref class Solution { //深度优先+回溯， int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}}; public boolean exist(char[][] board, String word) { int row = board.length; int col = board[0].length; boolean[][] visited = new boolean[row][col]; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (dfs(i,j,board,word,0,visited)) { return true; } } } return false; } public boolean dfs(int row, int col, char[][] board, String word, int index, boolean[][] visited) { if (index == word.length()) { return true; } if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || word.charAt(index) != board[row][col] || visited[row][col] == true) { return false; } visited[row][col] = true; // 对当前的路径进行标记，避免重复访问 for (int[] dir : directions) { int curRow = row + dir[0]; int curRol = col + dir[1]; if (dfs(curRow, curRol, board, word, index + 1, visited)) { return true; } } visited[row][col] = false; // 回溯，使得其他路径可以访问当前路径的元素 return false; } } 八皇后写法 class Solution { public boolean exist(char[][] board, String word) { int l = board.length; int w = board[0].length; boolean[][] visited = new boolean[l][w]; for(int i=0;i<l;i++){ for(int j=0;j<w;j++){ if(pd(board,visited,word,0,i,j)) return true; } } return false; } public boolean pd(char[][] board,boolean visited[][],String word,int index,int i,int j){ if(index == word.length()) return true; if(i<0||i>=board.length||j<0||j>=board[0].length||visited[i][j]||board[i][j] != word.charAt(index)) return false; visited[i][j] = true; boolean res = pd(board,visited,word,index+1,i+1,j)|pd(board,visited,word,index+1,i,j+1)|pd(board,visited,word,index+1,i-1,j)|pd(board,visited,word,index+1,i,j-1); visited[i][j] = false; return res; } }

class Solution { // 矮个子插队，高个子看不见；所以我们可以先安排高个子的位置，再通过插队的方式安排矮个子的位置 // 身高从大到小排（身高相同k小的站前面） //先按照身高h降序排序，这样处理时可以确保当前插入的元素之前的所有元素身高都不小于它，从而简化位置的确定。 //如果身高相同，则按照序号k升序排序，因为身高相同的情况下，序号小的人应该排在前面 public int[][] reconstructQueue(int[][] people) { Arrays.sort(people, (a,b) -> b[0] == a[0]? a[1] - b[1] : b[0] - a[0]); List<int[]> list = new ArrayList<>(); for (int i = 0; i < people.length; i++) { list.add(people[i][1], people[i]); } return list.toArray(new int[list.size()][2]); // list.toArray将list转成array } }

class Solution { // 贪心 // 先执行次数最多的任务，可以充分利用任务之间的间隔。时间最短 // 每次执行次数最多的任务，考虑优先队列，大根堆 public int leastInterval(char[] tasks, int n) { PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b-a); int[] count = new int[26]; int res = 0; for (int i = 0; i < tasks.length; i++) { //对任务计数 count[tasks[i] - 'A']++; } for (int tmp : count) { // 出现次数大于0的元素才意味着任务需要完成 if (tmp > 0) { pq.offer(tmp); } } while (!pq.isEmpty()) { List<Integer> list = new ArrayList<>(); // list记录一个间隔内完成的任务 for (int i = 0; i <= n; i++) { if (!pq.isEmpty()) { list.add(pq.poll()); } } for (int t : list) { if ( --t > 0) { pq.offer(t); } } res += pq.isEmpty() ? list.size() : n + 1; } return res; } // public int leastInterval(char[] tasks, int n) { // // 统计每种任务的出现次数 // int[] count = new int[26]; // for (char task : tasks) { // count[task - 'A']++; // } // // 创建一个优先队列,存储每种任务的下一次执行时间 // PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // for (int c : count) { // if (c > 0) { // pq.offer(c); // } // } // int time = 0; // while (!pq.isEmpty()) { // // 创建一个临时列表,存储当前时间可以执行的任务 // java.util.List<Integer> temp = new java.util.ArrayList<>(); // for (int i = 0; i <= n; i++) { // if (!pq.isEmpty()) { // temp.add(pq.poll()); // } // } // // 将当前时间可以执行的任务加回优先队列,并更新它们的下一次执行时间 // for (int t : temp) { // if (--t > 0) { // pq.offer(t); // } // } // // 如果优先队列为空,说明所有任务已经完成,返回当前时间 // time += pq.isEmpty() ? temp.size() : n + 1; // } // return time; // } }

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { // 用一个列表存储先序遍历的结果，再构建单链表，将列表中的节点的左指针赋值为空，右指针指向列表中的下一个位置 List<TreeNode> res = new ArrayList<>(); public void flatten(TreeNode root) { if (root == null) { return; } preOrder(root); for (int i = 0; i < res.size() - 1; i++) { // 这里是小于 res.size() - 1,确保不会数组越界 TreeNode node = res.get(i); node.left = null; node.right = res.get(i + 1); } } public void preOrder(TreeNode root) { if (root == null) { return; } res.add(root); preOrder(root.left); preOrder(root.right); } }

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ //环形链表，快慢指针 public class Solution { // Floyd判圈法 public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { return true; } } return false; } }

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { // floyd判圈法，快慢指针 // 设置快慢两个指针都指向头结点 // 让一个快指针一次走两步，慢指针一次走一步 // 两个指针相遇后，将快指针移到起点，一次走一步，相遇的位置就是链表中环的起始位置 public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { // fast需要走两步，所以需要判断fast != null && fast.next != null fast = fast.next.next; slow = slow.next; if (slow == fast) { fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return slow; } } return null; } }

// LRU缓存机制可以通过哈希表辅以双向链表实现 // 使用双向链表的理由：方便删除节点，O(1)时间 // 双向链表中存储key的理由：size > capcity 时可以O(1)的时间删除哈希表中的键值对 // O(1)的get和put，用hashmap实现 // 基础还是链表的增删改查，只是这里是双向链表作为hashmap的value // 链表的中节点的移动和删除修改通过双向链表可以在O(1)的时间内实现 // 每访问一个节点都要将其移动链表头。整个过程分为两步:1.双向链表中删除该节点，2.添加到头部 // 链表中的元素个数超过capcity后需要删除链表尾的节点 class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; DLinkedNode() {} DLinkedNode(int key, int value) { this.key = key; this.value = value; } } private int size; private int capacity; private DLinkedNode head = new DLinkedNode(); private DLinkedNode tail = new DLinkedNode(); private HashMap<Integer, DLinkedNode> hs = new HashMap<>(); LRUCache(int capacity) { size = 0; this.capacity = capacity; head.next = tail; tail.prev = head; } public int get (int key) { DLinkedNode node = hs.get(key); if (node == null) { return -1; } moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = hs.get(key); if (node == null) { node = new DLinkedNode(key, value); hs.put(key, node); addToHead(node); size++; if (size > capacity) { DLinkedNode tail = removeTail(); hs.remove(tail.key); --size; } } else { node.value = value; moveToHead(node); } } public void addToHead(DLinkedNode node) { // 添加到头结点,意味着新建了一个节点 node.next = head.next; node.prev = head; head.next.prev = node; head.next = node; } public void removeNode(DLinkedNode node) { // 删除节点 node.prev.next = node.next; node.next.prev = node.prev; } public void moveToHead(DLinkedNode node) { // 节点已经存在，改变他的值，需要将该节点移动到头的位置 removeNode(node); addToHead(node); } public DLinkedNode removeTail() { // size > capacity 需要删除末尾节点 DLinkedNode node = tail.prev; removeNode(node); return node; } } // java自带的LinkedHashMap已经实现了LRU缓存 // class LRUCache extends LinkedHashMap<Integer, Integer> { // private int capacity; // public LRUCache(int capacity) { // super(capacity, 0.75F, true); //调用父类的构造方法 // this.capacity = capacity; // } // public int get(int key) { // return super.getOrDefault(key, -1); // } // public void put(int key, int value) { // super.put(key, value); // } // @Override // protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest){ // return size() > capacity; // } // } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */