[Swift]LeetCode969.煎饼排序|PancakeSorting

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10228389.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an array A, we can perform a pancake flip: We choose some positive integer k <= A.length, then reverse the order of the first k elements of A. We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

Return the k-values corresponding to a sequence of pancake flips that sort A. Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

Example 1:

Input: [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: A = [3, 2, 4, 1]
After 1st flip (k=4): A = [1, 4, 2, 3]
After 2nd flip (k=2): A = [4, 1, 2, 3]
After 3rd flip (k=4): A = [3, 2, 1, 4]
After 4th flip (k=3): A = [1, 2, 3, 4], which is sorted.

Example 2:

Input: [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

Note:

1 <= A.length <= 100
A[i] is a permutation of [1, 2, ..., A.length]

给定数组 A，我们可以对其进行煎饼翻转：我们选择一些正整数 k <= A.length，然后反转 A 的前 k 个元素的顺序。我们要执行零次或多次煎饼翻转（按顺序一次接一次地进行）以完成对数组 A 的排序。

返回能使 A 排序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * A.length 范围内的有效答案都将被判断为正确。

示例 1：

输入：[3,2,4,1]
输出：[4,2,4,3]
解释：
我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。
初始状态 A = [3, 2, 4, 1]
第一次翻转后 (k=4): A = [1, 4, 2, 3]
第二次翻转后 (k=2): A = [4, 1, 2, 3]
第三次翻转后 (k=4): A = [3, 2, 1, 4]
第四次翻转后 (k=3): A = [1, 2, 3, 4]，此时已完成排序。

示例 2：

输入：[1,2,3]
输出：[]
解释：
输入已经排序，因此不需要翻转任何内容。
请注意，其他可能的答案，如[3，3]，也将被接受。

提示：

1 <= A.length <= 100
A[i] 是 [1, 2, ..., A.length] 的排列

16ms

 1 class Solution {
 2     func pancakeSort(_ A: [Int]) -> [Int] {
 3         var aCopy = A
 4         var result = [Int]()
 5         var valueToBeSort = A.count
 6         
 7         while valueToBeSort != 1 {
 8             if valueToBeSort == aCopy[valueToBeSort - 1] {
 9                 valueToBeSort -= 1
10             } else {
11                 let index = aCopy.firstIndex(of: valueToBeSort)!
12                 if index != 0 {
13                     result.append(index + 1)
14                     for i in 0...index / 2 {
15                         aCopy.swapAt(i, index - i)
16                     }
17                 }
18                 result.append(valueToBeSort)
19                 for i in 0...(valueToBeSort - 1) / 2 {
20                     aCopy.swapAt(i, valueToBeSort - 1 - i)
21                 }
22             }
23         }
24 
25         return result
26     }
27 }

24ms

 1 class Solution {
 2     func pancakeSort(_ A: [Int]) -> [Int] {
 3         var A = A
 4         var ans = [Int]()
 5         var i = A.count
 6         while i>0 {
 7             var j=0
 8             for k in 0..<A.count {
 9                 if A[k] == i {
10                     j = k
11                     break
12                 }
13             }
14             flip(&A, &ans, j);
15             flip(&A, &ans, i-1);
16             i -= 1
17         }
18         return ans
19     }
20 
21     func flip(_ A: inout [Int], _ ans: inout [Int], _ pos: Int) -> Void {
22         var s = 0, e = pos
23         while s<e {
24             let temp=A[s]
25             A[s]=A[e]
26             A[e]=temp
27             s += 1
28             e -= 1
29         }
30         ans.append(pos+1)
31     }
32 }

32ms

 1 class Solution {
 2     func pancakeSort(_ A: [Int]) -> [Int] {
 3         var B = A
 4         var n = A.count
 5         var ret = [Int]()
 6         while n >= 1 {
 7             let i = B.firstIndex(of: n)!
 8             B[0...i].reverse()
 9             ret.append(i+1)
10             B[0..<n].reverse()
11             ret.append(n)
12             n -= 1
13         }
14         return ret
15     }
16 }

36ms

 1 class Solution {
 2     func pancakeSort(_ A: [Int]) -> [Int] {
 3         let sorted = A.sorted()
 4         guard A != sorted else { return [] }
 5         var ar = A
 6         var lastSorted = sorted.count - 1
 7         var res: [Int] = []
 8         while lastSorted >= 0 {
 9             let max = sorted[lastSorted]
10             let ind = ar.index(of: max)!
11             if ind == lastSorted {  
12             } else {
13                 res.append(ind + 1)
14                 res.append(lastSorted + 1)
15                 var ar1 = ar
16                 if ind != 0 {
17                   ar1 = Array(Array(ar[0...ind]).reversed()) + Array(ar[ind+1..<ar.count])
18                 }
19                 if lastSorted == ar1.count - 1 {
20                    ar = Array(ar1.reversed())
21                 } else {
22                     ar = Array(Array(ar1[0...lastSorted]).reversed()) + Array(ar1[lastSorted+1..<ar1.count])
23                 }
24             }
25             lastSorted -= 1
26         }
27         
28         return res        
29     }    
30 }

40ms

 1 class Solution {
 2     func pancakeSort(_ A: [Int]) -> [Int] {
 3         var A = A
 4         var n:Int = A.count
 5         var ans:[Int] = [Int]()
 6         for i in (0...(n - 1)).reversed()
 7         {
 8             var j:Int = 0
 9             while(A[j] != i+1)
10             {
11                 j += 1
12             }
13             ans.append(j + 1)
14             ans.append(i + 1)
15             var newA:[Int] = [Int](repeating:0,count:n)
16             for k in 0..<n
17             {
18                 newA[k] = A[k]
19             }
20             for k in 0...j
21             {
22                 newA[k] = A[j-k]
23             }
24             A = newA
25             newA = [Int](repeating:0,count:n)
26             for k in 0..<n
27             {
28                 newA[k] = A[k]
29             }
30             for k in 0...i
31             {
32                 newA[k] = A[i-k]
33             }
34             A = newA
35         }
36         return ans
37     }
38 }

80ms

 1 class Solution {
 2     func pancakeSort(_ A: [Int]) -> [Int] {
 3         
 4         var res: [Int] = []
 5         
 6         var sortArray: [Int] = A.sorted()
 7         var A = A
 8         
 9         for i in (0...A.count - 1).reversed() {
10             if A[i] == sortArray[i] {
11                 continue
12             } else {
13                 for j in (0...i).reversed() {
14                     if A[j] == sortArray[i] {
15                         A.replaceSubrange(Range.init(0...j), with: A[0...j].reversed())
16                         A.replaceSubrange(Range.init(0...i), with: A[0...i].reversed())
17                         
18                         res.append(j + 1)
19                         res.append(i + 1)
20                         
21                         break
22                     }
23                 }
24             }
25             
26         }
27         
28         return res
29     }
30 }

100ms

 1 class Solution {
 2     func pancakeSort(_ A: [Int]) -> [Int] {
 3         // find largest and send to back
 4         var sorted = true
 5         for i in 0..<A.count - 1 {
 6             if A[i] > A[i + 1] {
 7                 sorted = false
 8                 break;
 9             }
10         }
11         if sorted { return [] }
12         
13         var flippedArr = A
14         var accum: [Int] = []
15         for i in 0..<A.count {
16             var max = biggest(A.count - 1 - i, flippedArr)
17             accum.append(max + 1)
18             flippedArr = flip(max, flippedArr)
19             print(flippedArr)
20             accum.append(A.count - i)
21             flippedArr = flip(A.count - 1 - i, flippedArr)
22             // print(flippedArr)
23         }
24         return accum
25     }
26     
27     func flip(_ end: Int, _ arr: [Int]) -> [Int] {
28         var out = arr
29         for i in 0...end/2 {
30             let temp = out[i]
31             out[i] = out[end - i]
32             out[end - i] = temp
33         }
34         
35         return out
36     }
37     
38     func biggest(_ end: Int, _ arr: [Int]) -> Int {
39         var max = 0
40         for i in 0...end {
41             if arr[i] >= arr[max] {
42                 max = i
43             }
44         }
45         return max
46     }
47 }