面试资料

买卖股票的最佳时机 II给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。 返回 你能获得的 最大 利润 。 刚开始我考虑的是动态规划，想不出来。在草稿纸上画出了折线图就想到了可以用队列来做，也就是用单调队列找出所有的上升子序列。 维护一个单调队列使得从队尾到队头单调递减。 初始化最大利润ans=0 如果进队元素小于等于队尾，说明这一段上升序列结束，ans+=队尾-队头，并清空队列，将新元素入队。 否则，将新元素入队。 循环结束后再计算一遍ans+=队尾-队头，把最后一段上升子序列加进去。 123456789101112131415161718class Solution {public: int maxProfit(vector<int>& prices) { queue<int> q; q.p ...

买卖股票的最佳时机题目描述给定一个数组 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+ ...

轮转数组又是一道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, ...

多数元素给定一个大小为 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 ...

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 ...

删除有序数组中的重复项跟上个题很像。同样是双指针解法 设置快慢指针f，s 初始时s=0，f=1。 如果nums[s]不等于nums[f]说明不重复，f++，s++。 如果nums[s]等于nums[f]说明重复，f++。 替换操作nums[++s]=nums[f++]，可以合并到第1步。 12345678910111213class Solution {public: int removeDuplicates(vector<int>& nums) { int s=0; int n=nums.size(); for(int f=1;f<n;f++){ if(nums[f]-nums[s]){ nums[++s]=nums[f]; } } return s+1; }}; 做完下一道题后重新写这 ...

移除元素12345给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 方法1遍历数组，找到元素val。 val之后的元素全部左移 12345678910111213141516class Solution {public: int removeElement(vector<int>& nums, int val) { int n=nums.size(); int i=0; while(i<n){ if(nums[i]!=val) i++; else{ for(int j=i;j<n-1;j++) nums[j]=nums[j+1]; ...

合并两个有序数组123456给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。 时空复杂度均为O(n+m)123456789101112131415161718class Solution {public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int i=0,j=0; vector<int> nums; while(i<m&&j<n) { ...

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick StartCreate a new post1$ hexo new "My New Post" More info: Writing Run server1$ hexo server More info: Server Generate static files1$ hexo generate More info: Generating Deploy to remote sites1$ hexo deploy More info: Deployment