acwing-第k个数
第k个数给定一个长度为 n 的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k个数。
输入格式第一行包含两个整数 n 和 k。
第二行包含 n 个整数(所有整数均在 1∼1091∼109 范围内),表示整数数列。
输出格式输出一个整数,表示数列的第 k 小数。
最暴力的做法是把数组全部排序然后输出。
但其实可以不用全部排序,只排列一部分就能得到答案。
每趟排序后pivot左边的数全部小于等于pivot,右边的数全部大于等于pivot。所以每趟排序后判断j 和k的关系,决定排序哪一边。
1234567891011121314151617181920212223242526#include<iostream>#define N 100000using namespace std;int a[N];int quick_select(int l,int r,int k){ if(l==r) return a[l]; int x=a[l+r>>1]; int i=l-1,j=r+1; while(i<j) ...
acwing-快速排序
快速排序快速排序有三个地方容易写错,今天终于全弄明白了。
先来看代码
1234567891011121314151617181920212223242526#include<iostream>using namespace std;const int N = 1e5+10;int a[N];void quick_sort(int l,int r){ if(l==r) return; int i=l-1,j=r+1; int mid=a[l+r>>1];//易错点1 while(i<j){ while(a[--j]>mid); while(a[++i]<mid); if(i<j) //易错点2 swap(a[i],a[j]); } quick_sort(l,j); quick_sort(j+1,r);//易错点3}int main(){ int n; cin>>n ...
leetcode-274. H 指数
H指数给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义:h 代表“高引用次数” ,一名科研人员的 h 指数 是指他(她)至少发表了 h 篇论文,并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值,**h 指数** 是其中最大的那个。
这个H指数的定义非常绕。第一次做的时候有思路,代码就是写不出来。
翻译过来就是nums[i]大于等于[i,n-1]的长度,求满足这个条件的长度最大值。
要使长度为n-i最大,则i取最小值。
123456789101112class Solution {public: int hIndex(vector<int>& nums) { sort(nums.begin(),nums.end()); int n=nums.size(); for(int i=0;i<n;i++){ if( ...
leetcode-45. 跳跃游戏 II
跳跃游戏 II给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
这个有点难度,不会写。
要求最小跳跃次数,也就是每次尽可能多走。
元素nums[i]的覆盖范围是**[i,i+nums[i]]**,也就是从i位置能跳到的位置,每次跳跃到覆盖范围最大的位置就可以保证步数最小。
设置覆盖范围的右端点为end,i==end时,说明覆盖范围遍历完,跳跃次数+1.同时在遍历过程中,求出覆盖范围内的元素的最大覆盖范围,并更新end,也就是跳跃整个最大覆盖范围。
12345678910111213141516171819class Solution {public: int jump(vector<in ...
leetcode-55. 跳跃游戏
跳跃游戏给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。
f[i]表示从[0,i]的任意位置能到的最远下标值。难点是想出来这一步
状态转移方程就非常容易写了: f[i]=max(f[i-1],nums[i]+i)
初始化f[0]=nums[0]。当f[i-1]<i时,说明从[0,i-1]到不了i,连i都到不了自然是到不了最后,所以 return false
如果f[i]>=n-1,则 return true
123456789101112131415class Solution {public: bool canJump(vector<int>& nums) { int n=nums.size(); vector<int> f(n); if(n==1) return true; f[0]=nums ...
leetcode-122. 买卖股票的最佳时机 II
买卖股票的最佳时机 II给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。
在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。
返回 你能获得的 最大 利润 。
刚开始我考虑的是动态规划,想不出来。在草稿纸上画出了折线图就想到了可以用队列来做,也就是用单调队列找出所有的上升子序列。
维护一个单调队列使得从队尾到队头单调递减。
初始化最大利润ans=0
如果进队元素小于等于队尾,说明这一段上升序列结束,ans+=队尾-队头,并清空队列,将新元素入队。
否则,将新元素入队。
循环结束后再计算一遍ans+=队尾-队头,把最后一段上升子序列加进去。
123456789101112131415161718class Solution {public: int maxProfit(vector<int>& prices) { queue<int> q; q.p ...
leetcode-121. 买卖股票的最佳时机
买卖股票的最佳时机题目描述给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
看起来就很像动态规划的题目。
维护前i个元素的最小值min_price,f[i]表示前i天的最大利润。
f[i] = min(f[i-1],a[i]-min_price)
代码1234567891011121314class Solution {public: int maxProfit(vector<int>& prices) { int n = prices.size(); vector<int> f(n); f[0]=0; int min_price = prices[0]; for(int i=1;i<n;i+ ...
leetcode-189. 轮转数组
轮转数组又是一道408原题,非常简单。
题目描述给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。
代码12345678910111213141516class Solution {public: void reverse(int a,int b,vector<int>& nums){ while(a<b){ swap(nums[a],nums[b]); a++; b--; } } void rotate(vector<int>& nums, int k) { if(k>nums.size()) k%=nums.size(); reverse(0,nums.size()-1,nums); reverse(0,k-1,nums); reverse(k,nums.size()-1, ...
leetcode-169. 多数元素
多数元素给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
这个题目是某年的408原题,之前做的时候用的哈希表,答案好像是摩尔投票法不过当时没看懂😅
摩尔投票法规定众数的票数是1,非众数的票数是-1.由于众数的数量大于总元素个数的一半所以票数之和一定大于0.
若数组的前a个数票数之和为0,则后n-a个数的票数之和一定大于0,所以众数一定在后n-a个数中。
设置一个候选众数 maj = nums[0],初始化票数和votes = 0.
遍历数组,对于每一个元素x,若x==maj则votes++。否则votes–
遍历结束后maj即为整个数组的众数
123456789101112131415class Solution {public: int majorityElement(vector<int>& nums) { int maj=nums[0],vo ...
leetcode-80. 删除有序数组中的重复项 II
80. 删除有序数组中的重复项 II给你一个有序数组 nums ,请你** 原地** 删除重复出现的元素,使得出现次数超过两次的元素只出现两次 ,返回删除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
这个题和前面两道题[1](leetcode-27. 移除元素 | Grady’s coding notes (gr4dyzhou.github.io)),[2](leetcode-26. 删除有序数组中的重复项 | Grady’s coding notes (gr4dyzhou.github.io))都属于双指针,总结出了个模板
本题代码12345678910111213141516class Solution {public: int removeDuplicates(vector<int>& nums) { int n=nums.size(); if(n<3) return n; int s=2,f=2; w ...