跟着左神学算法(一)

跟着左神学算法(一)

仅作为个人学习笔记，大佬勿喷！

1.给定一个数组和一个基准值， 要求 小于基准值在数组左边，等于基准值在中间，大于基准值在右边

public static int[] hierarchy(int[] nums,int equivalent){
       
        if(nums==null){
            return null;
        }
        int l=-1;
        int r=nums.length;
        int i=l+1;
        while (iequivalent){
                change(nums,i,r-1);
                r--;
            }else {
                i++;
            }
            System.out.println("i="+i+" l="+l+" r="+r);
        }
        return nums;
    }

    public static  void  change(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }

解题思路：

左边小于区右下标l,右边大于区左下标为r=nums.length

（1当前值等于判断值,跳下一个;

（2）当前值小于判断值，当前值和小于区后一个值交换，小于区右移一个，跳下一个;

（3）当前值大于判断值，当前值和大于区前一个值交换，大于区左移一个。

2.荷兰国旗问题变种
力扣 https://leetcode-cn.com/problems/first-missing-positive/

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

public static int getMinPositiveInteger(int[] nums){
       int L=0;
       int R=nums.length;
        while (L!=R){
            if(nums[L]==L+1){
                L++;
            }else if(nums[L]<=L || nums[L]>R || nums[L]==nums[nums[L]-1] ){
                change(nums,L,--R);
            }else {
                change(nums,L,nums[L]-1);
            }
        }
        return L+1;
    }

    public static void change(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }

解题思路：
由荷兰国旗问题启发，有效区右下标L,垃圾区左下标R,

最好的情况数组里面是 1~nums.length=R,

如果大于R,则为垃圾数据

nums[L]小于L,同样属于垃圾数据

如果nums[nums[L]-1]的位置上已经放了符合条件的值，说明此时数值为重复，则归为垃圾数据

如果 num[L]==L+1,则直接下一个

其余情况，则交换对应位置数值即可

3.给定一个数组,里面只有"G"和"B"， 可以所有B放在左侧，所有G放在右侧， 或者所有G放在右侧，所有B放在右侧， 但是只能相领字符之间进行交换，请问至少需要交换几次

public static int minStep( String s){
        if(s == null || s.equals("")){
            return 0;
        }
        int stepB=0;
        int b=0;
        int stepG=0;
        int g=0;
        final char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if(chars[i]=='B'){
                stepB+=i-(b++);
            }else{
                stepG+=i-(g++);
            }
        }
        return Math.max(stepB,stepG);


    }

解题思路：
当一种字母归位，就意味着B和G都已经归位了，所以只需要取B字母在左侧需要步数和G字母在左侧需要步数中的小值即可。

一个变量记录当前符合条件是第几个字母(b++/g++),下一个符合 条件字母归位需要步数(i-(b++)/i-(g++))

4.现有多根线段,开始时间点和结束时间点都为整数，最多有多少线段重叠（重叠段大于1）？

public static int getMaxCoincideLine(int[][] lines){
        //按照开始时间点排正序
        Arrays.sort(lines, Comparator.comparingInt(a -> a[0]));
        final PriorityQueue queue = new PriorityQueue<>();
        int max=0;
        for (int[] line : lines) {
            final int start = line[0];
            final int end = line[1];
            while (!queue.isEmpty() && start>queue.peek()){
                queue.poll();
            }
            queue.add(end);
            int size=queue.size();
            max=Math.max(max,size);
        }
        return max;

    }

解题思路：
利用特殊的数据结构，小根堆(java中 PriorityQueue),堆顶为最小数，

线段按照开始时间点排正序，遍历放入小根堆，堆内比当前线段开始时间点小的d出(因为堆内都是放的结束时间点，比当前线段开始点小，意味着线段已结束，不在当前线段范围内)，再把当前线段的结束时间点放入小根堆，此时堆内数量就是重叠线段数。