算法

初级算法 - LeetBook - 力扣（LeetCode）

数组

1. 删除排序数组中的重复项
   给你一个非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

双指针解题

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;
}
};
   

2. 买卖股票的最佳时机 II
   给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回你能获得的最大利润。

class Solution{
public:
  int maxProfit(vector<int>&prices){
    int n=prices.size();
    int tot=0;
    for(int i=1;i<n;i++){
      if(prices[i]>price[i-1]){
        tot+=price[i]-price[i-1];
      }
    }
    return tot;
  }
};

3. 旋转数组
   给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

使用一个新的数组

class Solution{
public:
  void rotate(vector<int>&nums,int k){
    int len=nums.size();
    k=k%len;
    vector<int>res(len);
    //将后k个元素移到前面
    for(int i=0;i<k;i++){
      res[i]=nums[len-k+i];
    }
    //将前len-k个元素移到后面
    for(int i=0;i<len-k;i++){
      res[k+i]=nums[i];
    }
    //将结果复制回nums
    nums=res;
  }
};

也可以这样

class Solution{
public:
  void rotate(vector<int>&nums,int k){
    int n=nums.size();
    vector<int>newArr(n);
    for(int i=0;i<n;i++){
      newArr[(i+k)%n]=nums[i];
    }
    nums.assign(newArr.begin(),newArr.end());
  }
};

4. 存在重复元素
   给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
   题解：考虑排序，排序后数组的重复元素一定出现在相邻位置中

   class Solution {
   public:
       bool containsDuplicate(vector<int>& nums) {
   	sort(nums.begin(),nums.end());
   	int n=nums.size();
   	for(int i=0;i<n-1;i++){
   	  if(nums[i]==nums[i+1]){
   	     return true;
   	  }
   	}
   	return false;
   };

5. 只出现一次的数字
   给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
   第一次的解法（没有考虑线性时间复杂度）这么写是因为收到前面思路的影响

   class Solution {
   public:
       int singleNumber(vector<int>& nums) {
           sort(nums.begin(), nums.end());
           int n = nums.size();
            // 如果数组只有一个元素，直接返回
           if (n == 1) {
               return nums[0];
           }
            // 检查第一个元素是否是唯一的
           if (nums[0] != nums[1]) {
               return nums[0];
           }
            // 检查最后一个元素是否是唯一的
           if (nums[n - 1] != nums[n - 2]) {
               return nums[n - 1];
           }
            // 从第二个元素到倒数第二个元素进行检查
           for (int i = 1; i < n - 1; i++) {
               if (nums[i] != nums[i - 1] && nums[i] != nums[i + 1]) {
                   return nums[i];
               }
           }
            return -1; 
       }
   };

   如果要考虑线性时间复杂度 O (n):

   class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int result = 0;
            for (int num : nums) {
                result ^= num;
            }
            return result;
        }
    };

   这个异或解法的时间复杂度是 O(n)，空间复杂度是 O(1)

6. 两个数组的交集Ⅱ
   给你两个整数数组 nums 1 和 nums 2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
   法一：哈希表
   遍历第一个数组，在哈希表中记录第一个数组中每个数字以及出现的次数，然后遍历第二个数组，如果哈希表中存在这个数字，将这个数字添加到答案，并减少哈希表中该数字出现的次数。

   class Solution{
   public:
     vector<int>intersect(vector<int>&nums1,vector<int>&nums2){
     if(nums1.size()>nums2.size()){
       return intersect(nums2,nums1);
     }
     unordered_map<int,int>m;
     for(int num:nums1){
       ++m[num];
     }
     vector<int>intersection;
     for(int num:nums2){
       if(m.count(num)){
         intersection.push_back(num);
         --m[num];
         if(m[num]==0){
           m.erase(num);
         }
       }
     }
     return intersection;
     }
   
   }