2020-06-10

LeetCode排序

面试16.16 部分排序(排序后找不同的两边下标)

题目

分析

1. a.clone()复制一个数组然后排序
2. 最左边不同的值和最右边不同的值就是要求的两边

代码

public class BuFenPaiXu {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(Arrays.toString(subSort(a)));
    }

    public static int[] subSort(int[] a) {
        int[] b=a.clone();  //复制一个a数组
        int[] jie=new int[]{-1,-1}; //结果的值默认是-1 -1
        Arrays.sort(b);  //对于b数组进行排序
    //从左到右找最左边的不同的值
        for(int i=0;i<a.length;i++){
            if(a[i]!=b[i]){
                jie[0]=i;
                break;
            }
        }
	//如果找不到就输出 -1 -1
        if(jie[0]<0){
            return jie;
        }
    //从右到左找最右边的不同的值
        for(int i=a.length-1;i>=0;i--){
            if(a[i]!=b[i]){
                jie[1]=i;
                break;
            }
        }
        return jie;
    }

}

结果

面试16.21 交换和(set去重)

题目

分析

1. 两数组间差要是偶数(偶数才可以补之间差)
2. 计算出两者差cha=sum1—sum2
3. 计算出两者平均要补aver=cha/2
4. 使用set存储数组a，然后进行去重set.contains(b[i]+aver)是否存在就说明两者之间可以互换!!

代码

public class JiaoHuanHe {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();
        int m=input.nextInt();
        int[] a=new int[n];
        int[] b=new int[m];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        for(int i=0;i<m;i++){
            b[i]=input.nextInt();
        }
        System.out.println(Arrays.toString(findSwapValues(a,b)));
    }

    public static int[] findSwapValues(int[] a, int[] b) {
        int sum1 = 0; //a数组的和
        int sum2 = 0; //b数组的和
        Set<Integer> set = new HashSet<>();
    //遍历获得a数组的和
        for(int num:a){
            sum1 += num;
            set.add(num); //将a数组的内容加到set集合
        }
    //遍历获得b数组的和
        for(int num:b) {
            sum2 += num;
        }
        int diff = sum1 - sum2;  //获取之间的差
        if(diff % 2 != 0) {
            return new int[]{};  //如果差不是偶数的话肯定不能找到
        }
        int target = diff / 2;  //中间差/2就是两边需要补的数字
        for(int num:b){
            if(set.contains(num + target)){  //如果a数组里面有b数组加上中间补的数字 说明可以互换
                return new int[]{num + target, num}; //反着输出
            }
        }
        return new int[]{}; //返回空
    }

}

结果

面试17.08 马戏团人塔(map/最长子序列)

题目

分析

代码

class Solution {
    public int bestSeqAtIndex(int[] height, int[] weight) {
        if (height.length <= 1) {
            return height.length;
        }

        Integer[] indexs = new Integer[height.length];
        for (int i = 0; i < indexs.length; i++) {
            indexs[i] = i;
        }

        Arrays.sort(indexs, (o1, o2) -> {
            if (height[o1] == height[o2]) {
                return weight[o2] - weight[o1];
            }
            return height[o1] - height[o2];
        });
        
        int[] tail = new int[height.length + 1];
        int end = 0;
        tail[0] = weight[indexs[0]];
        for (int i = 1; i < height.length; i++) {
            if (weight[indexs[i]] > tail[end]) {
                ++end;
                tail[end] = weight[indexs[i]];
            } else {
                int left = 0;
                int right = end;
                int target = weight[indexs[i]];
                while (left < right) {
                    int mid = (left + right) >>> 1;
                    if (target > tail[mid]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                tail[left] = target;
            }
        }
        // 因为是从0 开始的 所以需要加1 
        end++;
        return end;
    }

结果

面试17.14 最小k个数(Arrays.sort())

题目

分析

1. 使用数组排序之后输出前k位即可

代码

public class MinK {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        int k=input.nextInt();
        System.out.println(Arrays.toString(smallestK(a,k)));
    }

    public static int[] smallestK(int[] arr, int k) {
        Arrays.sort(arr);  //原数组进行排序
        int[] b=new int[k];
        for(int i=0;i<k;i++){
            b[i]=arr[i];  //前k个数给b数组并且输出
        }
        return b;
    }

}

结果

面试45 数组排成最小的数(sort内置函数)

题目

分析

主要使用内置函数：Arrays.sort(strs,(x,y)->(x+y).compareTo(y+x))

代码

public class PaiZuiXiao {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(minNumber(a));
    }

    public static String minNumber(int[] nums) {
        StringBuilder sb=new StringBuilder();
        String[] strs=new String[nums.length];
        for(int i=0;i<strs.length;i++){
            strs[i]=String.valueOf(nums[i]);  ///所有数字转为字符串
        }
        Arrays.sort(strs,(x,y)->(x+y).compareTo(y+x)); //内置函数比较排序
        for(String s:strs){
            sb.append(s); //按序将所有内容添加到sb对象内
        }
        return sb.toString();
    }

}