class Solution { //求拓扑排序:B-A。我们将每一门课看成一个节点如果想要学习课程 A 之前必须完成课程 B那么我们从 B 到 A 连接一条有向边。这样以来在拓扑排序中B 一定出现在 A 的前面。我们可以将深度优先搜索的流程与拓扑排序的求解联系起来用一个栈来存储所有已经搜索完成的节点。这样以来我们对图进行一遍深度优先搜索。当每个节点进行回溯的时候我们把该节点放入栈中。最终从栈顶到栈底的序列就是一种拓扑排序。 //存储有向图 ListListInteger edgesnew ArrayListListInteger(); //标记每个节点的状态0未搜索1搜索中2已完成 int[] visited; //用数组模拟栈下标n-1为栈底0为栈顶 int[] result; //判断有向图中是否有环 boolean validtrue; //栈下标 int index; public int[] findOrder(int numCourses, int[][] prerequisites) { for(int i0;inumCourses;i){ edges.add(new ArrayListInteger()); } visitednew int[numCourses]; resultnew int[numCourses]; indexnumCourses-1; for(int[] info:prerequisites){ //List.get(数字) 拿的就是下标索引 //让前置课程指向后置课程巧妙。本质起始是list下标当做前置课程这个下标对应的list里面存这个课程所有的后置课程。edges.get(b).add(a); edges.get(info[1]).add(info[0]); } //每次挑选一个未搜索0的节点开始深度优先搜索 for(int i0;inumCoursesvalid;i){ if(visited[i]0){ dfs(i); } } if(!valid){ return new int[0];//空数组细节 } // 如果没有环那么就有拓扑排序 return result; } 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){ //如果「搜索中」说明找到了环 validfalse; return; } } // 将节点标记为「已完成」 visited[u]2; // 将节点入栈 result[index--] u; } }class Solution { public int subarraySum(int[] nums, int k) { /*暴力 1 以i开始的子数组中和为k的个数 int nnums.length; int cnt0,sum0; for(int i0;in;i){ sum0; for(int ji;jn;j){ sumnums[j]; if(sumk){ cnt; } } } return cnt;*/ //暴力 2 以i结尾的子数组中和为k的个数 /*int nnums.length; int cnt0,sum0; for(int i0;in;i){ sum0; for(int ji;j0;j--){ sumnums[j]; if(sumk){ cnt; } } } return cnt;*/ //前缀和优化针对暴力2 //欲求start~end之间的数组的值和是否为k即pre[end]-pre[start-1]k,即pre[start-1]pre[end]-k int nnums.length; int pre0,cnt0; MapInteger,Integer mpnew HashMap();//pre,cnt //预先放前缀和 0 出现 1 次 mp.put(0,1); for(int i0;in;i){ prenums[i]; if(mp.containsKey(pre-k)){ cntmp.get(pre-k); } mp.put(pre,mp.getOrDefault(pre,0)1); } return cnt; } }二分查找模版 1、 找第一个 target 的元素左边界 public int lowerBound(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; // 防溢出 if (nums[mid] target) { left mid 1; } else { right mid - 1; } } // 循环结束时 left right 1left 就是第一个 target 的位置 return left; } 2、找目标值存在性 public int search(int[] nums, int target) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; if (nums[mid] target) left mid 1; else right mid - 1; } return -1; }
