力扣爆刷第169天之TOP200五连刷111-115（课程表、单词搜索、归并）

一、207. 课程表

题目链接：https://leetcode.cn/problems/course-schedule/description/
思路：本题是一个典型的有向图判定是否有环，如果有环就无法完成课程，因为循环依赖。
1、那么关键点就在于该如何判定有环，我们可以把有向图想象成一个多叉树，如果单条链路上有回路，就相当于有环。
2、另外如果遍历呢？有向图的话一般是采用数组和链表构建邻接表，通过遍历邻接表就可以完成图的遍历。
3、遍历过程中需要注意哪些问题呢？要防止重复遍历，如果防止重复遍历呢？只需要维护一个boolean数组，那个节点遍历过了就给标记一下既可以。
4、如果判定有环呢？因为只要单条链路形成环路即为有环，所以只需要模拟树的遍历，在前序的位置设置标识，在后序的位置移出标识，如果在遍历的过程中，标识被重复遇到了就说明有环路。
拓展：如果存在多条可以修习完课程的路径，如何找出一条，其实只需要在后序遍历的位置，记录节点，最后翻转搜集的节点即可。
基于以上的内容，可以写出下面的代码。

class Solution {boolean[] visited;boolean[] flag;boolean finish = true;public boolean canFinish(int numCourses, int[][] prerequisites) {visited = new boolean[numCourses];flag = new boolean[numCourses];List<Integer>[] list = builderGroup(numCourses, prerequisites);for(int i = 0; i < numCourses; i++) {traverse(i, list);}return finish;}void traverse(int from, List<Integer>[] list) {if(visited[from]) {finish = false;}if(flag[from] || !finish) {return;}flag[from] = true;visited[from] = true;for(int to : list[from]) {traverse(to, list);}visited[from] = false;}List<Integer>[] builderGroup(int numCourses, int[][] prerequisites) {List<Integer>[] list = new LinkedList[numCourses];for(int i = 0; i < numCourses; i++) {list[i] = new LinkedList();}for(int[] temp : prerequisites) {list[temp[1]].add(temp[0]);}return list;}
}

二、LCR 125. 图书整理 II

题目链接：https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/description/
思路：本题是用两个栈实现队列，思路不难。
1、实现队列只需要考虑如何先进先出就行，只需要先进栈，再出栈就可以。
2、如何防止乱序，只需要维护A,B两个栈，读取元素都从B中读，B空了就把A中元素都加入到B中，写入元素都写入到A中即可。

class CQueue {Deque<Integer> stack1 = new LinkedList<>();Deque<Integer> stack2 = new LinkedList<>();public CQueue() {}public void appendTail(int value) {stack1.push(value);}public int deleteHead() {if(!stack2.isEmpty()) return stack2.pop();while(!stack1.isEmpty()) {stack2.push(stack1.pop());}if(stack2.isEmpty()) return -1;return stack2.pop();}
}/*** Your CQueue object will be instantiated and called as such:* CQueue obj = new CQueue();* obj.appendTail(value);* int param_2 = obj.deleteHead();*/

三、402. 移掉 K 位数字

题目链接：https://leetcode.cn/problems/remove-k-digits/description/
思路：本题是要求从字符串中移除掉k个数字，之后使其表示的数最小。
1、如果让剩余的数足够小？其实数字是有高位和低位的，我们应该从高位往低位进行处理。
2、具体该如何处理呢？我们只需要丢弃掉较大的数，保留较小的数即可。
3、如何丢呢？我们应该丢掉高位较大的数，保留低位较小的数，就可以实现最终的数最小。
4、具体实现可以使用单调栈，如果当前元素小于栈顶元素，则说明，高位元素值大于低位元素值，该丢弃。如果当前元素值大于栈顶元素值，说明低位元素大于高位元素，需要保留下来高位元素，因为高位元素小。

class Solution {public String removeKdigits(String num, int k) {LinkedList<Character> stack = new LinkedList<>();for(int i = 0; i < num.length(); i++) {char c = num.charAt(i);while(!stack.isEmpty() && c < stack.peek() && k > 0) {stack.poll();k--;}stack.push(c);}while(k > 0 && !stack.isEmpty()) {stack.pop();k--;}StringBuilder sb = new StringBuilder();while(!stack.isEmpty()) sb.insert(0, stack.pop());String res = "";for(int i = 0; i < sb.length(); i++) {if(sb.charAt(i) != '0') {res = sb.toString().substring(i, sb.length());break;}}return res.equals("") ? "0" : res;}
}

四、79. 单词搜索

题目链接：https://leetcode.cn/problems/word-search/description/
思路：本题求单词搜索，问能不能按照单词自己的顺序，在二维数组中找到它。这其实涉及到了几个点。
1、首先明确，这是一个典型的无向图的遍历题，DFS和BFS都可以，一般我爱用DFS，因为好写不用写栈。
2、其次，要考虑怎么进行单词搜索，可以随着递归维护一个单词读取位置的指针，只要元素相同指针就可以+1，指针只要能够走到结尾部分，就算是搜索结束，搜索到了。
3、如何防止重复遍历，直接使用一个二维boolean数组是比较浪费空间的，可以对遍历过的节点设置为’0’，递归返回时再修改回原本的值，这样就可以完美解决掉重复遍历的问题。

class Solution {boolean flag = false;public boolean exist(char[][] board, String word) {for(int i = 0; i < board.length; i++) {for(int j = 0; j < board[0].length; j++) {if(flag) return true;dfs(board, word, i, j, 0);}}return flag;}void dfs(char[][] board, String word, int x, int y, int index) {if(index == word.length()) {flag = true;return;}if(x < 0 || x >= board.length || y < 0 || y >= board[0].length || flag) return;if(board[x][y] != word.charAt(index)) return;board[x][y] = '0';dfs(board, word, x-1, y, index+1);dfs(board, word, x, y-1, index+1);dfs(board, word, x+1, y, index+1);dfs(board, word, x, y+1, index+1);board[x][y] = word.charAt(index);}
}

五、912. 排序数组

题目链接：https://leetcode.cn/problems/sort-an-array/description/
思路：简单写一个排序算法就可以，不过本题的测试用例专门针对了一下快排，如果用快排的话需要自己处理，我这里用的堆排。
1、从最后一个非叶子节点开始，直到根节点，向下构造最大堆。
2、构造最大堆就是把堆顶的元素找到可以下沉到的具体位置，找到后，就把对应的元素交换位置即可。
3、构造完最大堆以后，堆顶元素就是最大值，只需要不断的把堆顶元素移动到数组尾部即可。

class Solution {public int[] sortArray(int[] nums) {heapSort(nums);return nums;}void heapSort(int[] nums) {int len = nums.length;for(int i = len/2-1; i >= 0; i--) {builderHeap(nums, i, len);}for(int i = len-1; i > 0; i--) {int max = nums[0];nums[0] = nums[i];nums[i] = max;builderHeap(nums, 0, i);}}void builderHeap(int[] nums, int start, int end) {int k = start, t = nums[start];for(int i = start*2+1; i < end; i = i*2+1) {if(i+1 < end && nums[i+1] > nums[i]) i = i+1;if(t < nums[i]) {nums[k] = nums[i];k = i;}else break;}nums[k] = t;}
}