LeetCode969. 煎饼排序
2024-08-30 12:48:39
问题:969. 煎饼排序
给定数组 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]
的排列
链接:https://leetcode-cn.com/contest/weekly-contest-118/problems/pancake-sorting/
分析:
翻转次数在10*A.length的都被判为正确,那么可以采用如下策略:
对于某个数组A0 A1...An,假设最大值为Ai
第一次翻转前i+1个,将Ai翻转到首位,然后翻转n+1个,将Ai翻转到最后,接下来处理A0 A1 ...Ai-1 Ai+1...An,这样的话每个数字经过两次翻转转到目标位置,满足小于10*要求。
则需要:
1.剩余待处理长度L。
2.剩余数字中最大值位置N。
3.翻转前N个。
4.翻转前L个。
AC Code:
class Solution {
public:
vector<int> pancakeSort(vector<int>& A) {
vector<int> ret;
int right = A.size();
while(IsSorted(A) != true)
{
//找到当期最大值位置
int max = FindMaxlocation(A, right);
if (max == right)
{
right--;
}
else
{
//先将最大值翻转到第一个,然后翻转到最后一个
ret.emplace_back(max);
A = Swap(A, max);
ret.emplace_back(right);
A = Swap(A, right);
right--;
}
}
return ret;
}
vector<int> Swap(vector<int> vec, int n)
{
n = n - ;
vector<int> ret;
for (int i = ; i < vec.size(); i++)
{
if (i <= n)
{
ret.emplace_back(vec[n-i]);
}
else
{
ret.emplace_back(vec[i]);
}
}
return ret;
}
int FindMaxlocation(vector<int> vec, int lim)
{
int ret = ;
for (int i = ; i < lim; i++)
{
if (vec[i] > vec[ret])
{
ret = i;
}
}
ret += ;
return ret;
}
};
其他:
第一code:
class Solution(object):
def pancakeSort(self, A):
"""
:type A: List[int]
:rtype: List[int]
"""
if len(A) == :
return []
mmax = len(A)
index = A.index(mmax)
A[:index+] = reversed(A[:index+])
A.reverse()
return [index+, len(A)] + self.pancakeSort(A[:-])
利用python的截取功能递归处理,基本思路一样。
最新文章
- ajax实例2
- 【leetcode❤python】 125. Valid Palindrome
- android开发-小技巧篇(集合)
- linux2.4.18内核定时器的使用
- Python学习遇到的问题
- xml基础学习笔记04
- UI2_IOS坐标系
- Appium项目搭建 For windows
- C# 编写通用的JSON数据进行序列化和反序列化
- linkin大话数据结构--泛型
- Ajax爬虫必用到的字典转换器
- 汇编 (NOT)按位取反指令
- int,char指针探究
- Machine Learning Books Suggested by Michael I. Jordan from Berkeley
- Windows10下搭建TensorFlow环境
- php 数值数组遍历
- error:Your local changes to the follwing files would be overwritten by merge
- ServletRequest面试题
- 2018.8.1 Java中的反射和同步详解
- 【POJ 3614】 Sunscreen
热门文章
- Mysql数据库常用操作整理
- c# 小数点格式化
- windows常用命令行总结
- C#开发usb通知之bulk传输
- 连接数据库报错:1130-Host &#39;xxx&#39; is not allowed to connect to this MySQL server解决
- 设计模式之装饰器模式io的小入门(十一)
- JSON FILE NOT FOUND?
- 即将要被淘汰的兼容之--CSS Hack
- Android SQLite数据库之事务的学习
- libmysqlclient.so.16未找到方法