leetcode每日一题46
134.加油站
贪心
1.油总量<耗油总量 无法跑完一圈
2.一旦在某个位置i的当前油量<耗油量 则从i+1作为起始点
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curGas=0;int totalGas=0;int start =0;for(int i=0;i<gas.size();i++){curGas += gas[i]-cost[i];totalGas += gas[i]-cost[i];if(curGas<0){start = i+1;curGas=0;}}if(totalGas<0) return -1;return start;}
};
137.只出现一次的数字ii
哈希表
class Solution {
public:int singleNumber(vector<int>& nums) {unordered_map<int,int> hash;for(int i=0;i<nums.size();i++){hash[nums[i]]++;}int ans=0;for(auto [i, j]: hash){if(j==1){ans=i;break;}}return ans;}
};
应该开始写符合cpp11新特性的for循环了，在处理数组、容器时更方便
看题解，还有另一种方法：二进制
为了方便叙述，我们称「只出现了一次的元素」为「答案」。
由于数组中的元素都在 int（即 32 位整数）范围内，因此我们可以依次计算答案的每一个二进制位是 0 还是 1。
具体地，考虑答案的第 i 个二进制位（i 从 0 开始编号），它可能为 0 或 1。对于数组中非答案的元素，每一个元素都出现了 3 次，对应着第 i 个二进制位的 3 个 0 或 3 个 1，无论是哪一种情况，它们的和都是 3 的倍数（即和为 0 或 3）。因此：
答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。
这样一来，对于数组中的每一个元素 x，我们使用位运算 (x >> i) & 1 得到 x 的第 i 个二进制位，并将它们相加再对 3 取余，得到的结果一定为 0 或 1，即为答案的第 i 个二进制位。
class Solution {
public:int singleNumber(vector<int>& nums) {int ans =0;for(int i=0;i<32;i++){int sum =0;for(int num:nums){sum += ((num>>i)&1);}if(sum%3)ans |= (1<<i);}return ans;}
};