1. 刷题——数组

数组刷题

主要参考《代码随想录》，次要参考leetcode上面各种好的题解思路

基础知识

1. 定义：数组是存放在连续内存空间上的相同类型的数据集合
2. 特点：
   • 数组下标从0开始的
   • 数组在内存的地址空间是连续的
   • 随机存取，但是增删元素需要移动其他元素，比较慢
3. 数组在内存空间的地址时连续的，需要注意的时是
   • 数组下标是从0开始的
   • 数组内存空间是连续的
4. vector是容器，底层是用array实现的
5. java在二维数组的内存空间是由row个具有column元素的连续空间组成的，而不是row*column组成的

一、二分查找

基本二分法

1. letcode网址https://leetcode.cn/problems/binary-search/submissions/

2. 算法特点

   • 有序无重复的数组，有重复元素返回的下标可能不唯一
   • 逻辑简单，但是确定边界比较繁琐

3. 区间定义方式

   • 左闭右闭 [left, right]
   • 左闭右开 [left, right)
   • 边界的处理就是根据区间的定义进行的

4. 左闭右闭代码

   class Solution {
   public:
       int search(vector& nums, int target) {
           int left = 0;
           int right = nums.size() - 1; // 定义target在左闭右闭的区间里
           
           while (left <= right) { // 前闭后闭用<=
           // 当left==right，区间[left, right]依然有效，所以用 <=
               int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
               if (nums[middle] > target) {// 结果在左区间
                   right = middle - 1; 
                   // target A在左区间，所以[left, middle - 1]
               } else if (nums[middle] < target) {// 结果在右区间
                   left = middle + 1; 
                   // target 在右区间，所以[middle + 1, right]
               } else { // 相等找到目标值
                   return middle; // 数组中找到目标值，直接返回下标
               }
           }
           return -1;// 未找到目标值
       }
   };
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22

搜索插入位置

1. letcode网址https://leetcode.cn/problems/search-insert-position/

2. 代码

   class Solution {
   public:
       int searchInsert(vector& nums, int target) {
           int n = nums.size();
           int left = 0;
           int right = n - 1; // 定义target在左闭右闭的区间里，[left, right]
           while (left <= right) { // 当left==right，区间[left, right]依然有效
               int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
               if (nums[middle] > target) {
                   right = middle - 1; // target 在左区间，所以[left, middle - 1]
               } else if (nums[middle] < target) {
                   left = middle + 1; // target 在右区间，所以[middle + 1, right]
               } else { // nums[middle] == target
                   return middle;
               }
           }
           // 分别处理如下四种情况
           // 目标值在数组所有元素之前  [0, -1]
           // 目标值等于数组中某一个元素  return middle;
           // 目标值插入数组中的位置 [left, right]，return  right + 1
           // 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1
           return right + 1;// 取整总是取的前一个
       }
   };
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24

在排序数组中查找元素的第一个和最后一个位置

1. letcode网址https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

2. 代码

   class Solution {
   public:
       vector searchRange(vector& nums, int target) {
           int rightBorder = getRightBorder(nums, target);
           int leftBorder = getLeftBorder(nums, target);
           if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
           if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
           return {-1, -1};
       }
   private:
       int getRightBorder(vector& nums, int target) {
           int left = 0;
           int right = nums.size() - 1;
           int mid;
           int rightBorder = -2;
   
           while (left <= right) {
               mid = (left + right) / 2;
               if (target < nums[mid]) {
                   right = mid - 1;
               }else{
                   left = mid + 1;
                   rightBorder = left;
               }
           }
           return rightBorder;
       }
       
       int getLeftBorder(vector& nums, int target) {
           int left = 0;
           int right = nums.size() - 1;
           int mid;
           int leftBorder = -2;
            
           while (left <= right) {
               mid = (left + right) / 2;
               if (target > nums[mid]){
                   left = mid + 1;
               }else{
                   right = mid - 1;
                   leftBorder = right;
               }
           }
           return leftBorder;
   
       }
   };
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39
   40
   41
   42
   43
   44
   45
   46
   47

x 的平方根

1. letcode网址https://leetcode.cn/problems/sqrtx/

2. 代码

   class Solution {
   public:
       int mySqrt(int x) {
           // x的平方根一定在[1, x/2+1]内
           int left = 1;
           int right = (x >> 1) + 1; // 除以2的倍数可以使用位运算
           // 区间使用方式：前闭后闭
           while (left <= right) {
               int mid = left + ((right - left) >> 1); // 防止溢出，使用位运算加快速度
               if (mid > x / mid) {  // 尽量使用除法和减法防止数值太大而内存溢出
                   right = mid - 1;
               } else if (mid < x / mid) {
                   left = mid + 1;
               } else {
                   return mid;
               }
           }
           return right; // 终止条件left > right,因为是向下取整，所以返回的是right     
       }
   };
   
   
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22

有效的完全平方数

1. letcode网址https://leetcode.cn/problems/valid-perfect-square/submissions/

2. 代码

   class Solution {
   public:
       bool isPerfectSquare(int num) {
           int left = 1;
           int right = (num >> 1) + 1;
           long mid;
   
           while (left <= right) {
               mid = left + ((right - left) >> 1);
               if (num < mid*mid) {// 不能使用num / mid 和mid进行比较，会向下取整导致错误
                   right = mid - 1;
               }else if (num > mid*mid){
                   left = mid + 1;
               }else
                   return true;
           }
           return false;
       }
   };
   
   
   // 完全平方数可以使用从1开始的连续奇数相加得到，不能得到的就是非完全平方数
   
   class Solution 
   {
   public:
       bool isPerfectSquare(int num) 
       {
           int num1 = 1;
           while(num > 0) 
           {
               num -= num1;
               num1 += 2;
           }
           return num == 0;
       }
   };
   
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38

二、移除元素

erase函数的实现

1. 数组 中的元素不能删除，只能覆盖，删除中间元素需要后面的元素都向前移动进行覆盖

2. 使用双指针：快指针寻找所需要的元素赋值给慢指针所指向的位置

3. 代码实现https://leetcode.cn/problems/remove-element/submissions/

   class Solution {
   public:
       int removeElement(vector& nums, int val) {
           int slow = 0;
           // 快指针寻找所需元素，慢指针获取赋值位置
           for(int fast = 1; fast < nums.size(); ++fast){
               if (nums[fast] != val){
                   nums[slow] = nums[fast];
                   slow++; 
               }
           }
           return slow;// 数组的新长度
       }
   };
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14

26.删除排序数组中的重复项

1. 代码

   int removeDuplicates(vector& nums) {
          int slow = 0;
          for (int fast = 1; fast  < nums.size() ; ++fast){
              if (nums[fast] == nums[slow]){
                  continue;
              }else{
              // 不相等就覆盖下一个slow的位置
              ++slow;
              nums[slow] = nums[fast];
              }
          }   
          return slow + 1;
      }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13

283.移动零

1. 代码

   void moveZeroes(vector& nums) {
           int slow = 0;
           for(int fast = 0; fast < nums.size(); ++fast){
               if (nums[fast] != 0) 
                   nums[slow++] = nums[fast];
           }
       // 慢指针最后停下的位置是判断条件符合的最后一个
           while (slow < nums.size()) 
               nums[slow++] = 0;
       }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10

844.比较含退格的字符串

1. 使用双指针，将字符串的处理封装成函数，时间100%，但是空间因为堆栈消耗可能大一些，只是超过60%

   class Solution {
   public:
       bool backspaceCompare(string s, string t) {
           int sLength = 0;
           int tLength = 0;
           int ptr = 0;
           // 对两个串都进行消减处理
           handleString(s, sLength);
           handleString(t, tLength);
           // 长度不等，直接否定
           if (sLength != tLength)
               return false;
           // 比较每个元素是否相同
           while(ptr < sLength) {
               if (s[ptr] != t[ptr])
                   return false;
               ptr++;
           }
           return true;
       }
   
   private:
       // 对每个字符串进行消减
       void handleString(string &str, int &length) {
           int slow = 0;
           int fast = 0;
           while (fast < str.size()) {
               if (str[fast] != '#') {
                   str[slow] = str[fast];
                   slow++;
                   fast++;
               } else {
                   fast++;
                   if (slow != 0) slow--;// 退格到0将无法继续退格
               }
           }
           length = slow;
       }
   };
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39

977.有序数组的平方

1. 寻找多种情况中，固定的哪一点。例如：有序（最值一定在端点处）

2. 代码

   class Solution {
   public:
       vector sortedSquares(vector& nums) {
           int p = nums.size() - 1;
           vector result(nums.size(), 0); // 初始化结果数组
           int left = 0;
           int right = nums.size() - 1;
           
           while (left <= right) {
               if ((nums[left] * nums[left]) > (nums[right] * nums[right])) {
                   result[p--] = nums[left] * nums[left];
                   left++;
               } else {
                   result[p--] =   nums[right] * nums[right];
                   right--;// 左边界++，右边界--
               }
           }
           return result;
       }
   };
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20

三、滑动窗口

长度最小的子数组

1. 滑动窗口的核心：根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

2. 代码

    int minSubArrayLen(int target, vector<int>& nums) {
           // 双指针定义
           int slow = 0;
           int fast = 0;
           // 过程变量记录
           int minLength = 0;
           int sum = 0;
           int result = INT32_MAX;// int的最大值
        
           for(;fast < nums.size(); ++fast) {
               sum += nums[fast];
               while (sum >= target) {// 核心就是if改为while
                   minLength = fast - slow + 1;// 取连续子序列的长度
                   result = result < minLength ? result : minLength;
                   // 比较记录最小长度
                   sum -= nums[slow++];// 慢指针滑动
               }
           }
        
           return result == INT32_MAX ? 0 : result;
       }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21

904.水果成篮

1. 题目地址https://leetcode.cn/problems/fruit-into-baskets/

2. 代码

    int totalFruit(vector& fruits) {
           // 设置窗口边界
           int slow = 0;
           int fast = 0;
           // 设置条件判定值
           unordered_map basket; //创建篮子
           int fruit_counter = 0; //篮子中的水果种类数
           int length = 0;
   
           while (fast < fruits.size()) {
               // 快指针前进的条件
               if (basket[fruits[fast]] == 0)// 水果种类fruits[fast]是键，basket[fruits[fast]]是值
                   fruit_counter++;
               basket[fruits[fast]]++; // 插入新水果 
               // 慢指针前进的条件
               while (fruit_counter > 2) {
                   basket[fruits[slow]]--;
                   if (basket[fruits[slow]] == 0) {
                       fruit_counter--;
                   }
                   slow++;
               }
               // 善后处理
               length = max(length, fast - slow + 1);
               fast++;
           }
           
           return length;
       }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29

   • 代码的开始先考虑边界值和正确性验证

3. 什么时候使用哈希法？ 查询集合中的一个元素是否存在

4. map是一种key value的存储结构，key保存要查询的键值，value保存对应其他信息

   1. std::map使用红黑树实现，key有序且不可重复，查询和增删效率均为O(log N)
   2. std::multimap使用红黑树实现，key有序且可重复，查询和增删效率均为O(log N)
   3. std::unordered_map使用哈希表，key无序且不可重复，查询和增删效率均为O(1)

5. map类型容器操作方法

   unordered_map mp;
   // 容器的插入
   // 1. 直接使用[] 符号
   mp[key] = "value";// mp[key]整体表示值
   // 2. 使用make_pair构造对象进行插入
   mp.insert(make_pair(key, "value"));
   // 3. 使用pair方法构造键值对插入
   mp.insert(pair(key, "d"));
   
   // 查找方法
   if (mp.find(key) != mp.end())
       function;// 找到返回迭代器，找不到返回mp.end()
       
   // 统计方法
   mp.count(key);// 统计key在map中出现的次数，没有返回0
   
   // 获取key的值
   // 1. 使用迭代器
   string val = mp.find(key)->second;
   
   // 2. at方法，不存在会报异常
   string val = mp.at(2);
   
   // 3. 使用[]操作符，不存在会插入
   string val = mp[key];
   
   // 删除元素
   // 1. 根据键删除
   mp.erase(key);
   // 2.根据值删除
   for(iter = mp.begin(); iter!=mp.end();) {
       if (iter->second=="value") {
           mymap.erase(iter++);
       } else {// 防止删除后迭代器失效
           iter++;
       }
   }
   
   // 遍历map
   map::iterator iter;
   for(iter = mp.begin(); iter != mp.end(); iter++) {
       cout<first<<": "<second<