当前位置:网站首页>969. Pancake sorting
969. Pancake sorting
2022-07-06 16:08:00 【mrbone9】
Address :
Power button https://leetcode-cn.com/problems/pancake-sorting/
subject :
Give you an array of integers arr , Please use Pancake flip Finish sorting the array .
The execution process of a pancake flip is as follows :
Choose an integer k ,1 <= k <= arr.length
Anti rotor array arr[0...k-1]( Subscript from 0 Start )
for example ,arr = [3,2,1,4] , choice k = 3 Make a pancake flip , Anti rotor array [3,2,1] , obtain arr = [1,2,3,4] .
Returning as an array enables arr Corresponding to the orderly pancake flipping operation k Value sequence . Any array that is sorted and flipped a few times 10 * arr.length All valid answers within the range will be judged to be correct .
Example 1:
Input :[3,2,4,1] Output :[4,2,4,3] explain : We execute 4 Turn the pancake over again ,k Values, respectively 4,2,4, and 3. The initial state arr = [3, 2, 4, 1] After the first flip (k = 4):arr = [1, 4, 2, 3] After the second flip (k = 2):arr = [4, 1, 2, 3] After the third flip (k = 4):arr = [3, 2, 1, 4] After the fourth flip (k = 3):arr = [1, 2, 3, 4], Sorting is now complete . |
Example 2:
Input :[1,2,3] Output :[] explain : The input has been sorted , So there's no need to flip anything . Please note that , Other possible answers , Such as [3,3] , Will also be judged to be correct . |
Tips :
1 <= arr.length <= 100 1 <= arr[i] <= arr.length arr All integers in are different from each other ( namely ,arr It's from 1 To arr.length An arrangement of integers ) |
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/pancake-sorting
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas :
First of all, we need to find a “ The formula ”, You can deduce the final result on paper before you see how to write the code
You can know the title :
1. Array element values are not equal , It means that there is a maximum , minimum value
2. If the results are in ascending order
3. Flip yes 0~k-1, It means that if you put the minimum value first , Then the subsequent flipping is in vain
So we need to find Maximum , Make it to the end through operation , In this way, the whole string becomes a substring
Then repeat the action to converge to an element , Achieve ascending order
What if we put the maximum value at the end ?
Example : 3,2,4,1
1. Find the maximum
3,2,4,1 , Its coordinates idx = 2, The maximum coordinate of the current string maxIdx = 3
2. Flip k = idx+1 = 3
4,2,3,1 , The maximum value is [0]
3. Flip k = maxIdx + 1 = 4
1,3,2,4 , The maximum value is placed at the end , At this time, we need to reduce the range of strings maxIdx = 2
So circular , The resulting 1,2,3,4
The optimization part is , If the maximum coordinate found is just at the end , Then directly reduce the string range , No flipping is required
Method 1 、 Cycle the maximum value to the end
void dispArr(int *arr, int arrSize)
{
printf("arr = [");
for(int i=0; i<arrSize; i++)
printf("%d ", arr[i]);
printf("]\n\n");
}
int findMaxnumIdx(int *arr, int lastIdx)
{
int max = arr[0];
int maxIdx = 0;
for(int i=0; i<=lastIdx; i++)
{
if(max < arr[i])
{
maxIdx = i;
max = arr[i];
}
}
return maxIdx;
}
void reversArr(int *arr, int lastIdx)
{
int l = 0, r = lastIdx;
while(l < r)
{
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
l++;
r--;
}
}
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* pancakeSort(int* arr, int arrSize, int* returnSize){
int i = 0;
int k, cnt = 0;
int rlen = arrSize * 2;
int *ret = (int *)malloc(sizeof(int) * rlen);
int maxIdx = arrSize - 1;
while(maxIdx != 0)
{
int idx = findMaxnumIdx(arr, maxIdx);
//printf("idx=%d, maxIdx=%d\n", idx, maxIdx);
if(idx == maxIdx)
{
maxIdx--;
rlen--;
continue;
}
//dispArr(arr, arrSize);
reversArr(arr, idx);
//dispArr(arr, arrSize);
reversArr(arr, maxIdx);
//dispArr(arr, arrSize);
k = idx + 1;
//printf("k=%d\n\n", k);
ret[i++] = k;
k = maxIdx + 1;
//printf("k=%d\n\n", k);
ret[i++] = k;
cnt+=2;
maxIdx--;
}
if(rlen != cnt)
{
rlen = cnt;
ret = (int *)realloc(ret, sizeof(int) * rlen);
}
*returnSize = rlen;
return ret;
}
边栏推荐
- F - birthday cake (Shandong race)
- Web based photo digital printing website
- JS call camera
- 信息安全-安全编排自动化与响应 (SOAR) 技术解析
- New to redis
- 【练习-6】(PTA)分而治之
- JS调用摄像头
- C language is the watershed between low-level and high-level
- Nodejs+vue online fresh flower shop sales information system express+mysql
- [exercise-2] (UVA 712) s-trees
猜你喜欢
Vs2019 initial use
渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
Information security - threat detection - detailed design of NAT log access threat detection platform
Ball Dropping
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
C language learning notes
渗透测试 ( 4 ) --- Meterpreter 命令详解
7-1 understand everything (20 points)
[analysis of teacher Gao's software needs] collection of exercises and answers for level 20 cloud class
随机推荐
Penetration testing (5) -- a collection of practical skills of scanning King nmap and penetration testing tools
2078. Two houses with different colors and the farthest distance
Flink 使用之 CEP
渗透测试 ( 5 ) --- 扫描之王 nmap、渗透测试工具实战技巧合集
Truck History
Opencv learning log 14 - count the number of coins in the picture (regardless of overlap)
【练习-1】(Uva 673) Parentheses Balance/平衡的括号 (栈stack)
CS zero foundation introductory learning record
Record of brushing questions with force deduction -- complete knapsack problem (I)
[exercise-3] (UVA 442) matrix chain multiplication
China exterior wall cladding (EWC) market trend report, technical dynamic innovation and market forecast
What is the difficulty of programming?
Write web games in C language
Information security - security professional name | CVE | rce | POC | Vul | 0day
1010 things that college students majoring in it must do before graduation
【练习-5】(Uva 839)Not so Mobile(天平)
socket通讯
树莓派4B安装opencv3.4.0
Find 3-friendly Integers
Ball Dropping