【Leetcode-每日一题】煎饼排序

煎饼排序
难度:中等
【Leetcode-每日一题】煎饼排序
【Leetcode-每日一题】煎饼排序
通过翻转,我们可以将最大值放到最右边的位置。
具体实现:每次获取剩余数组中的最大值下标,判断当前下标是否在最右侧,若在最右侧则无需处理,若不在最右侧则分为两种情况

  1. 该最大值在第一位,则只需要一次翻转即可将该值置于最右侧
  2. 该最大值不在第一位,则将起始位置到该值所处位置的元素翻转,此时最大值将会成为第一位,再重复步骤1。

代码如下:

	public List<Integer> pancakeSort(int[] arr) {
        List<Integer> res = new ArrayList<>();
        int r = arr.length-1;
        while(r>0){
            int idx = max(arr, r);
            if (idx==r){
                r--;
                continue;
            }
            if (idx!=0){
                reverse(arr,idx);
                res.add(idx+1);
            }
            reverse(arr,r);
            res.add(r+1);
            r--;
        }
        return res;
    }

    //将arr数组的前r位翻转
    private void reverse(int[] arr, int r) {
        int pre = 0;
        int end = r;
        while(pre<end){
            arr[end] = arr[pre] ^ arr[end];
            arr[pre] = arr[pre] ^ arr[end];
            arr[end] = arr[pre] ^ arr[end];
            pre++;
            end--;
        }
    }

    //求arr数组前k位的最大值下标
    public int max(int[] arr,int k){
        int idx = 0;
        for (int i = 1; i <= k; i++) {
            if (arr[i]>arr[idx]) idx = i;
        }
        return idx;
    }

执行结果:成功
【Leetcode-每日一题】煎饼排序

上一篇:Leetcode:1405、最长快乐字符串


下一篇:Leetcode 744:寻找比目标字母大的最小字母