LeetCode581+621+207

用了一个很巧妙的方法做出来的。

以nums = [2,6,4,8,10,9,15]为例，叙述思路。

思路

假如我们找到左边第一个开始下降的点和右边第一个开始上升的点，那么这两个点中点的所有点都需要排序。但是会有一种情况时[1,3,3,2]。所以我们需要找到的是左边第一个比右边最小的值大的点作为start，在右边找到第一个比左边最大值大的点是end，这样，这两个点中间的所有值就是要排序的点。其实本质还是找左边第一个开始下降的点和右边第一个开始上升的点。

左边最大值又没有说范围，所以不能直接求最大值，这里可以用一边遍历，一遍求的方式。我们可以用for循环来边遍历，边比较。max先设置为nums[0],然后从下标为1的位置开始遍历，每次遍历就先找两个数中最大的数，然后用当前i位置的数和max比较，如果当前i位置的数比max小，

end就是i。找start同理的。

总结就是end是正序遍历，start是倒序遍历。

代码

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int start = 0;
        int length = nums.length;
        int end = 0;
        int min = nums[length-1];
        int max = nums[0];
        for(int i= 1;i<length;i++){
            max = Math.max(nums[i],max);
            min = Math.min(nums[length-i-1],min);
            if(nums[i]<max){
                end = i;
            }
            if(nums[length-i-1]>min){
                start =length-i-1;
            }
        }
        if(end == start){
            return 0;
        }
        return end-start+1;
    }
}

621. 任务调度器

思路

这道题也是看的题解解决的。大家可以看这位大佬的题解，画的图很不错。用的是贪心算法。

力扣

代码

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] table = new int[26];
        for(char s:tasks){
            table[s-'A']++;
        }
        int maxCount = 0;
        for(int i = 0;i<table.length;i++){
            maxCount = Math.max(table[i],maxCount);
        }
        int res = (maxCount-1)*(n+1);
        int temp = 0;
        for(int i = 0;i<table.length;i++){
            if(table[i]!=0){
                temp++;
            }
        }
        return Math.max((res+temp),tasks.length);
    }
}

​​​​​​207. 课程表​​​​​​​s

思路

先构造图，然后用dfs遍历图，在遍历的时候判断图是否有圈，有圈就说明是不可能上完的。

代码

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] flages = new int[numCourses];//记录当前节点是否被访问过。正在访问是1，访问后是2.
        List<ArrayList<Integer>> graph = new ArrayList(numCourses);
        for(int i = 0;i<numCourses;i++){
            graph.add(new ArrayList<Integer>());
        }
        //以上是初始化图的存储结构.
        for(int i = 0;i<prerequisites.length;i++){
            int course = prerequisites[i][0];
            int pre = prerequisites[i][1];
            // 下标为course的数组里面的内容是course的所有前置课程
            graph.get(course).add(pre);
        }
        //以上是将图中赋值。
        //下面用dfs遍历图，并且判断图中是否有圈
        for (int i = 0; i < numCourses; i++) {
            if (dfs(i, flages, graph) == true) {
                return false;
            }
        }
        return true;
    }
    public boolean dfs(int cur, int[] flages, List<ArrayList<Integer>> graph){
        if(flages[cur] == 1){
            return true;
        }
        if(flages[cur] == 2){
            return false;
        }
        flages[cur] = 1;
        for(Integer preNode:graph.get(cur)){
            if(dfs(preNode,flages,graph) == true){
                return true;
            }
        }
        flages[cur] = 2;
        return false;
    }
}