[LeetCode] 969. Pancake Sorting

本文主要是介绍[LeetCode] 969. Pancake Sorting，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/pancake-sorting

题目大意

对于数组A，可进行 k-reverse操作，即将 前k个元素翻转，求能使A为升序的 k-reverse 操作顺序。

解题思路

分析k操作，k-reverse操作只会影响 前面的数，不会影响 数组中后面的数，所以思路是逐步将最大元素 放置在合适的位置。

先拷贝 A 为 Abackup，然后 Arrays.sort(Abackup)，我们可以从Abackup从后往前来获得当前最大值。然后与A对比，发现当前最大值的位置。
然后做两次reverse。
一次将 当前最大值放到A的头部。
然后将 当前最大值放到A的最终位置。

class Solution {public void reverse(int[] A ,int l, int r){while(l<r){int tmp = A[l];A[l] = A[r];A[r] = tmp;l++;r--;}}public List<Integer> pancakeSort(int[] A) {List<Integer> res = new ArrayList();int[] Abackup = new int[A.length];for(int i = 0 ; i < Abackup.length;i++)Abackup[i] = A[i];Arrays.sort(Abackup);for(int i = Abackup.length-1 ; i>=0;i--){int j = Abackup.length-1;for( ; j >=0;j--)if(A[j] == Abackup[i])break;if(i == j)continue;if(j!=0){res.add(j+1);reverse(A,0,j);}res.add(i+1);reverse(A,0,i);}return res;}
}

这篇关于[LeetCode] 969. Pancake Sorting的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---