驴の奇思妙想

时代和环境变化非常快速，因此我们必须持续将目光聚焦在未来。 题目描述：加油站 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。 解题代码：12345678910111213141516171819class Solution {public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int now = 0; int sum = 0; int start = 0; for(int i = 0; i < gas.size(); i++) ...

失败是抵达卓越的另一个踏脚石。 题目描述： 除自身以外数组的乘积 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法，且在 O(*n*) 时间复杂度内完成此题。 解题代码：1234567891011121314151617181920class Solution {public: vector<int> productExceptSelf(vector<int>& nums) { int len = nums.size(); if(len == 0) return {}; vector<int> ans(len,1); ans[0] = 1; for(int i = 1; i < nums.size(); i++)& ...

事情会改变，朋友会离去。 生命不会为了任何人而停歇。 题目描述：O(1) 时间插入、删除和获取随机元素 实现RandomizedSet 类： RandomizedSet() 初始化 RandomizedSet 对象 bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。 bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。 int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。 解题代码：12345678910111213141516171819202122232425262728293031323334353637383940class RandomizedSet {public: unordered_map<int, int> dat ...

原谅是人际关系的润滑油。 题目描述：H 指数 给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，**h 指数** 是其中最大的那个。 解题代码：12345678910111213141516class Solution {public: int hIndex(vector<int>& citations) { sort(citations.begin(), citations.end()); int len = citations.size(); for(int i = 0; i < len; i++){ if(citations[i] >= len - i){ ...

善用你的优势。 多做你擅长的事情而不是那些你不擅长的事。 题目描述：跳跃游戏 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]。 解题代码：12345678910111213141516171819class Solution {public:int jump(vector<int>& nums){ int step = 0; int end = 0; int maxPos = 0; for (int i = 0; i < nums.size() - 1; i++) { maxPos = max(nums[i] + i, max ...

不论今天过得很好还是过得很有趣。 明天都是新的开始。 题目描述：跳跃游戏 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。 解题代码：1234567891011class Solution {public: bool canJump(vector<int>& nums) { int most = 0; for (int i = 0; i < nums.size(); i++) { if (i > most) return false; k = max(most, i + nums[i]); } return true; }}; 解读与收获：遍历一遍数组，看看能到达的最远距离是否比数组要长，如果是就能到达。开始想麻烦了，把所有之后 ...

千秋为卷，山河作答。 题目描述：买卖股票的最佳时机 II 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。 返回 你能获得的 最大 利润 。 解题代码：12345678910111213class Solution {public: int maxProfit(vector<int>& prices) { int temp = 0; int profit = 0; for(int i = 1;i < prices.size();i++){ temp = prices[i] - prices[i-1]; if(temp > 0) profit += temp; } return profit; }} ...

题目描述：买卖股票的最佳时机 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 解题代码：1234567891011121314class Solution {public: int maxProfit(vector<int>& prices) { int min = prices[0]; int max_profit = 0; for(int day: prices){ max_profit = max_profit>(day-min)?max_profit:(day-min); min = min<(day)?min:day; } re ...

面对阳光你就不会看到阴影 题目描述：轮转数组 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 解题代码：123456789class Solution {public: void rotate(vector<int>& nums, int k) { k = k % nums.size(); reverse(nums.begin(), nums.end()); reverse(nums.begin(),nums.begin()+ k - 1); reverse(nums.begin() + k, nums.end()); }}; 解读与收获：本题还是比较简单的，轮转数组，如果要轮转k个元素，首先将k的数值范围减小成k % nums.size()，这才是有效移动的位数，然后将整个数组进行翻转，再然后以下标k为分界线，分界线左边和右边分别再进行一次翻转，最终得到翻转后的数组。

我从失败走向成功。 题目描述：多数元素 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 解题代码：123456789class Solution {public: int majorityElement(vector<int>& nums) { sort(nums.begin(), nums.end()); int len = ceil(nums.size() / 2.0); return nums[len - 1]; }}; 解读与收获：这个求解思路其实和求解众数（一组数据中出现次数最多的数）但题目是找出出现次数大于n/2的数（多数元素），只能说多数元素一定是众数，而众数不一定是多数元素，但题目说假设一定会有多数元素，所以用这种方法也可以求出题解。 将一个数组排序，中位数一定是众数。 在评论区看到了一个很有意思的解法，叫摩尔投票 ...

忧虑的度过一天，比起工作一周还令人劳累。 题目描述：删除有序数组中的重复项 II 给你一个有序数组 nums ，请你** 原地** 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 解题代码：123456789101112131415class Solution {public: int removeDuplicates(vector<int>& nums) { if(nums.size() <= 2) return nums.size(); int fast = 2,slow = 2; for(fast;fast < nums.size();fast++){ if(nums[fast] != nums[slow - 2]){ nums[slow] = nums[fast]; ...

海上生明月，天涯共此时。 题目描述：删除有序数组中的重复项 给你一个 非严格递增排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过： 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。 解题代码：1234567891011121314class Solution {public: int removeDuplicates(vector<int>& nums) { int first = 1; int second = 1; for(first;first < nums.size();first++){ if(nums[fir ...