- 一、基础篇
- 26.删除排序数组中的重复--2022/01/16
- 122. 买卖股票的最佳时机 II--2022/01/17
- 189. 轮转数组--2022/01/18
- 217. 存在重复元素--2022/01/19
- 136. 只出现一次的数字--2021/12/14
- 350. 两个数组的交集 II -- 2022/01/12
- 66. 加一 -- 2022/01/20
- 1.两数之和（2022/01/20）
总目录: LeetCode 解题笔记（一）总
一、基础篇 26.删除排序数组中的重复–2022/01/16
链接： 26.删除有序数组中的重复项
题目： 简单
标签： 数组、快慢指针
题解： 逆向思维！判断每一个不相等的数，并计数，答案就出来了！！！
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() <=0 )
return 0;
int c = 0;
nums[c++] = nums[0];
for(int i=1; i<nums.size(); i++) {
if(nums[i] != nums[i-1])
nums[c++] = nums[i];
}
return c;
}
};
官方
思路： 快慢指针
定义两个指针 fast 和 slow 分别为快指针和慢指针，快指针表示遍历数组到达的下标位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标 1。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int fast = 1, slow = 1;
while (fast < n) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
};
122. 买卖股票的最佳时机 II–2022/01/17
链接：122. 买卖股票的最佳时机 II
题目： 中等
**标签：**数组、动态规划、贪心
我的答案：
思路：暴力解法，考虑边界条件，然后试错得出，效果还行：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minp = prices[0], maxp= 0;
int sum = 0, n=prices.size();
for(int i=1; i<n; i++) {
if(prices[i] <= prices[i-1]) {
if(maxp) {
sum += maxp - minp; //存在了最大利润了，并且这次又是新的最小值买入时机
maxp = 0;
}
minp = prices[i]; //最小值买入时机
}
else {
maxp = prices[i]; //保存当前的最大利润
// minp = prices[i-1]; //不需要的，试错出来的
if(i == n-1) {
sum += maxp - minp; //最大值结束的话，得计算一遍
}
}
}
return sum;
}
};
时间复杂度：O(n)，其中 n 为数组的长度。我们只需要遍历一次数组即可。
空间复杂度：O(1)，只需要常数空间存放若干变量。
参考答案：
看动态规划比较累，看这个贪心太舒服了：
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-tong-su-yi-dong-de-ti-ji-avcz/
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
for(int i = 0; i < prices.size() - 1; i++)
if(prices[i + 1] > prices[i])
res += prices[i + 1] - prices[i];
return res;
}
};
189. 轮转数组–2022/01/18
链接：189. 轮转数组
题目： 中等
标签： 数组
我的答案： 最容易想到的：建立个临时的数组
class Solution {
public:
void rotate(vector<int>& nums, int k) {
if(nums.size() == 0) return;
int n= nums.size();
vector<int> tmp ; // vector tmp = {0}; 这样初始化就已经添加了一个值
for(const auto& num: nums){
tmp.push_back(num);
}
for(int i=0; i<n; i++) {
nums[(i+k)%n] = tmp[i];
}
}
};
官方：若干答案，后续补充…
217. 存在重复元素–2022/01/19
链接：217. 存在重复元素
标签： 数组、排序、哈希表
题目：
我的答案：
**思路：**应该是最快的一次呢，排序+遍历判断就好！
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
int n = nums.size();
if(n==0 || n==1) return false;
//快速排序
std::sort(nums.begin(), nums.end());
for(int i=1; i<n; i++) {
if(nums[i] == nums[i-1]) return true;
}
return false;
}
};
官方：
思路：哈希表，对于数组中每个元素，我们将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> s;
for (int x: nums) {
if (s.find(x) != s.end()) {
return true;
}
s.insert(x);
}
return false;
}
};
136. 只出现一次的数字–2021/12/14
标签：位运算、异或
题目：136. 只出现一次的数字
思路：
异或特性（异或是找不同！）：
① 任何数与0异或，都是它本身
② 任何数与自身异或，都是0
③ 满足交换律、结合律
所以两个一样的数都可以消掉，然后单独的数与0异或
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for(const auto& num: nums) {
ret ^= num;
}
return ret;
}
};
350. 两个数组的交集 II – 2022/01/12
题目：350. 两个数组的交集 II
标签： 数组、哈希表、双指针、二分查找、排序
方法一：我的思路： 先排序，后用双指针…
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
if(nums1.size()==0 || nums2.size()==0) return {};
//先排序
std::sort(nums1.begin(), nums1.end());
std::sort(nums2.begin(), nums2.end());
int i1=0,i2=0;
int n1 = nums1.size(), n2 = nums2.size();
vector<int> ret;
//双指针
while((i1!=n1) && (i2!=n2)) {
if(nums1[i1] < nums2[i2]) {
++i1;
}
else if(nums1[i1] > nums2[i2]) {
++i2;
}
else {
ret.push_back(nums1[i1]);
++i1;
++i2;
}
}
return ret;
}
};
方法二：参考官方的哈希表方法后写的：
1636 有点相似
首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
//调整为 num1 为短的数组， 高级技巧
if(nums1.size() > nums2.size()) {
intersect(nums2, nums1);
}
//添加 num1 到哈希表中, 键-值类型，且无序的，用 unordered_map
unordered_map<int,int> map;
for(const auto& num: nums1) {
++map[num]; //不用指定多大空间的？
}
unordered_map <int, int> m;
for (int num : nums1) {
++m[num];
}
//判断 num2 中
vector<int> ret;
for(const auto& num: nums2) {
if(map.count(num)) { //判断键有木有
--map[num];
if(map[num] == 0) { //减到了 0 了
map.erase(num); //删除之
}
ret.push_back(num); //添加一次
}
}
return ret;
};
};
66. 加一 – 2022/01/20
链接：66. 加一
题目： 简单
标签： 数组、数字
我的答案：
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int n = digits.size();
if(n==0) { return {}; }
bool carry = true; //最高位进位
for(int i=n-1; i>=0; i--) {
if(carry) {
if( digits[i] == 9) {
digits[i] = 0;
carry = true;
}
else {
digits[i]++;
carry = false;
}
}
}
if(carry) {
vector<int> ret(n + 1);
ret[0] = 1;
return ret;
}
return digits;
}
};
！官方的答案复杂了，不贴了
参考网友的，很简洁，就发现我的 array 很没必要！
public int[] plusOne(int[] digits) {
int n = digits.length;
for (int i = n - 1; i >= 0; i--) {
if (digits[i] == 9) {
digits[i] = 0;
} else {
digits[i] += 1;
return digits;
}
}
int[] ans = new int[n + 1];
ans[0] = 1;
return ans;
}
1.两数之和（2022/01/20）
链接： 1. 两数之和
题目：
标签： 哈希，数组
思路：
我的暴力解题：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
n = nums.size();
for(int i=0; i<n ; i++) {
for(int j=i+1; j<n ; j++) {
if(nums[i] + nums[j] == target) {
return {i,j};
}
}
}
return {};
}
};
我的双指针：（错误答案）
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//1.排序
std::sort(nums.begin(), nums.end());
//2.双指针
int left = 0, right = nums.size()-1;
vector<int> ret;
while(left < right) {
int t = nums[left] + nums[right];
if(t == target) {
ret.push_back(left);
ret.push_back(right);
break;
}
else if(t < target) {
left ++;
}
else {
right --;
}
}
return ret;
}
然而，是要返回数组的下表的，所以此方法不适应，考虑哈希才是最快的！ 用哈希的 count 方法
map.count(Key) 返回值为1或者0，1返回存在，0返回不存在
网友答案：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> _map; // unordered_map _map; 都行
vector<int> b(2,-1); //用来承载结果，初始化一个大小为2，值为-1的容器b
for(int i=0; i<nums.size() ; i++) {
//从第二个数开始寻找哈希表中是否有对应的 key
if(_map.count(target-nums[i])) {
b[0] = _map[target-nums[i]];
b[1] = i;
break;
}
//第一次的时候，反过来存入键值，为了count函数
_map[nums[i]] = i; //第一次存入了 （3,0） 第二次（2,1）
}
return b;
}
};
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）