376. 摆动序列
中等
860
相关企业
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
- 例如，
[1, 7, 4, 9, 2, 5]是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3)是正负交替出现的。- 相反，
[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组
nums，返回nums中作为 摆动序列 的 最长子序列的长度 。示例 1：
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1000
int up[numsSize]; memset(up,0,sizeof(int)*numsSize); up[0]=1; int down[numsSize]; memset(down,0,sizeof(int)*numsSize); down[0]=1; int max=0; for(int i=0;i<numsSize;i++){ for(int j=0;j<i;j++){ if(nums[i]>nums[j]){ down[i]=fmax(up[j]+1,down[i]); } if(nums[i]<nums[j]){ up[i]=fmax(down[j]+1,up[i]); } } if(up[i]>max){ max=up[i]; } if(down[i]>max){ max=down[i]; } } return max; }
402. 移掉 K 位数字
中等
923
相关企业
给你一个以字符串表示的非负整数
num和一个整数k，移除这个数中的k位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。示例 1 ：
输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
示例 2 ：
输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 ：
输入：num = "10", k = 2
输出："0"
解释：从原数字移除所有的数字，剩余为空就是 0 。
提示：
1 <= k <= num.length <= 105num仅由若干位数字（0 - 9）组成- 除了 0 本身之外，
num不含任何前导零
char * removeKdigits(char * num, int k){ int length=strlen(num),top=-1,i=0; char *stack=(char *)malloc(sizeof(char)*(length+1)); for(i;i<length;i++) { while(top!=-1&&stack[top]>num[i]&&k>0)//出栈 { top--; k--; } if(num[i]!='0'||top!=-1)//入栈，删除了0之前的所有有效数字就不入栈 stack[++top]=num[i]; } while(k>0&&top>-1) { top--; k--; } if(top==-1)//里面空空如也 stack[++top]='0'; stack[++top]='\0'; return stack; }
406. 根据身高重建队列
提示
中等
1.5K
相关企业
假设有打乱顺序的一群人站成一个队列，数组
people表示队列中一些人的属性（不一定按顺序）。每个people[i] = [hi, ki]表示第i个人的身高为hi，前面 正好 有ki个身高大于或等于hi的人。请你重新构造并返回输入数组
people所表示的队列。返回的队列应该格式化为数组queue，其中queue[j] = [hj, kj]是队列中第j个人的属性（queue[0]是排在队列前面的人）。示例 1：
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
示例 2：
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
提示：
1 <= people.length <= 20000 <= hi <= 1060 <= ki < people.length- 题目数据确保队列可以被重建
int cmp(const void* _a, const void* _b) { int *a = *(int**)_a, *b = *(int**)_b; return a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]; } int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes) { qsort(people, peopleSize, sizeof(int*), cmp); int** ans = malloc(sizeof(int*) * peopleSize); *returnSize = 0; *returnColumnSizes = malloc(sizeof(int) * peopleSize); for (int i = 0; i < peopleSize; i++) { (*returnColumnSizes)[i] = 2; } for (int i = 0; i < peopleSize; ++i) { int* person = people[i]; (*returnSize)++; for (int j = (*returnSize) - 1; j > person[1]; j--) { ans[j] = ans[j - 1]; } int* tmp = malloc(sizeof(int) * 2); tmp[0] = person[0], tmp[1] = person[1]; ans[person[1]] = tmp; } return ans; }
435. 无重叠区间
中等
902
相关企业
给定一个区间的集合
intervals，其中intervals[i] = [starti, endi]。返回 需要移除区间的最小数量，使剩余区间互不重叠 。示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
提示:
1 <= intervals.length <= 105intervals[i].length == 2-5 * 104 <= starti < endi <= 5 * 104
int cmp(const void* ptr1, const void* ptr2) { int* a = *(int**)ptr1; int* b = *(int**)ptr2; return a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]; } int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){ qsort(intervals, intervalsSize, sizeof(int*), cmp); //区间右端点排序 int del = 0; //需要删除的区间个数 int res = intervals[0][1]; //初始化起始位置 for (int i = 1; i < intervalsSize; i++) { if (res > intervals[i][0]) { //如果右端大于左端，则删掉下一个区间 del++; } else { //如果右端小于等于左端，则保留下一个区间 res = intervals[i][1]; //以下一个区间为当前区间进行新一轮比较 } } return del; //返回需要删除的区间个数 }
581. 最短无序连续子数组
中等
1K
相关企业
给你一个整数数组
nums，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的 最短 子数组，并输出它的长度。
示例 1：
输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
示例 2：
输入：nums = [1,2,3,4]
输出：0
示例 3：
输入：nums = [1]
输出：0
提示：
1 <= nums.length <= 104-105 <= nums[i] <= 105
int cmp(const void * a, const void * b)//升序子函数 { return *(int *)a - *(int *)b; } /* *int findUnsortedSubarray(int* nums, int numsSize) int findUnsortedSubarray：寻找不符合区间 int* nums：数组 int numsSize：数组长度 返回值：不符合区间长度 */ int findUnsortedSubarray(int* nums, int numsSize) { int * ans = malloc(sizeof(int) * numsSize); memcpy(ans, nums, sizeof(int) * numsSize); qsort(ans, numsSize, sizeof(int), cmp);//初始化变量 int i, j; int n = -1, m = -1; for(i = 0; i < numsSize; i++)//判断左边第一个不同点 { if(ans[i] != nums[i]) { n = i; break; } } for(j = numsSize-1; j >= 0; j--)//判断右边第一个不同点 { if(ans[j] != nums[j]) { m = j; break; } } return n == -1 ? 0 : m - n + 1; } 控制台
