C++

相关知识点

数组是存放在连续内存空间上的相同的类型数据的集合

• 内存空间地址连续
• 下标从0开始
• 数组进行删除或者添加时，需要移动一系列元素
• 数组元素不能删除，只能覆盖

注意vector和array的区别
C++中，vector的底层实现是array,vector是容器,array是数组

常用方法

• 二分法(循环不变量原则)
• 双指针法
• 滑动窗口(根据当前子序列和大小情况，不断调节子序列的起始位置)
• 模拟行为

map和unordered_map的区别

1. 实现机制不同

map内部实现了一个红黑树，具有自动排序功能，所以map内元素是有序的。map中的元素是按照二叉搜索树来存储的，使用中序遍历可以将键值从小到大遍历出来。
unordered_map内部实现了一个哈希表，所以是无序的

2. 适用情况不同

map:有序、红黑树效率高;空间占用率高;适用于有顺序要求的问题
unordered_map:内部实现哈希表，查找速度很快;哈希表的建立耗费时间;适用于查找问题

二分查找

基础函数

#include <iostream>
#include <vector>
//#include <algorithm>,可以直接使用binary_search函数
using namespace std;

class Solution {
 public:
  int binary_search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;  // 定义区间[left,right]
    while (left <= right) {
      int mid = left + ((right - left) >> 1);  // 防止溢出
      if (nums[mid] > target) {
        right = mid - 1;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {  // nums[mid] == target
        return mid;  // 返回目标值下标
      }
    }
    // 未找到目标值
    return -1;
  }
};

int main() {
  // 测试用例
  vector<int> nums = {1,3,5,7,9,11,35,79};
  int target = 79;
  Solution solution;
  cout << solution.binary_search(nums, target) << endl;
  return 0;
}

移除元素

循环移除元素

#include <iostream>
#include <vector>
using namespace std;

class Solution {
 public:
  int ans = 0;
  int remove_element(vector<int>& nums, int val) {
    int size = nums.size();
    for (int i = 0; i < size; i++) {
      if (nums[i] == val) {
        ans = i;
        for (int j = i + 1; j < size; j++) {
          nums[j - 1] = nums[j];
        }
        --i;
        --size;
      }
    }
    // 输出移除元素后的数组大小
    return size;
    
  }
};

int main() {
  vector<int> nums = {1,2,3,4,5,6,7,8,9};
  int val = 3;
  Solution solution;
  
  cout << solution.remove_element(nums, val) << endl;
  // 输出移除元素的位置
  cout << solution.ans << endl;
  // 输出数组，能够看出其实数组中的数字其实不是被删除了，而是被覆盖了
  for (auto i : nums)
    cout << i;
  return 0;
}

双指针移除数组元素

#include <iostream>
#include <vector>
using namespace std;

class Solution {
 public:
  int remove_element(vector<int>& nums, int val) {
    int slowIndex = 0;
    for (int fastIndex = 0; fastIndex < nums.size(); ++fastIndex) {
      if (val != nums[fastIndex]) {
        nums[slowIndex++] = nums[fastIndex];
      }
    }
    // 移除后数组大小
    return slowIndex;
  }
};

int main() {
  vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8};
  int val = 5;
  Solution solution;
  cout << solution.remove_element(nums, val) << endl;
  for (int i = 0; i < nums.size(); ++i) {
    cout << nums[i];
  }
}

leetcode-844

// 判断两个字符串是否相等，有#删除一个字符
#include <iostream>
#include <string>
using namespace std;

// 双指针法, time_O(n), space_O(1)
class Solution {
 public:
  bool backspace_compare(string s, string t) {
    // 逆序遍历
    int i = s.length() - 1, j = t.length() - 1;
    // 需要退格的字符个数
    int skipS = 0, skipT = 0;
    while (i >= 0 || j >= 0) {
      while (i >= 0) {
        if (s[i] == '#') {
          ++skipS, --i;
        } else if (skipS > 0) {
          --skipS, --i;
        } else {
          break;
        }
      }
      while (j >= 0) {
        if (t[j] == '#') {
          ++skipT, --j;
        } else if (skipT > 0) {
          --skipT, --j;
        } else {
          break;
        }
      }
      if (i >= 0 && j >= 0) {
        if (s[i] != t[j]) {
          return false;
        }
      } else {
        if (i >= 0 || j >= 0) {
          return false;
        }
      }
      // 避免死循环超时
      --i, --j;
    }
    // 两个空字符串
    return true;
  }
};


// 栈, time/space O(n)
/*
bool backspace_compare(string S, string T) {
  return build(S) == build(T);
}
string build(string str) {
  string ret;
  for (char ch : str) {
    if (ch != '#') {
      ret.push_back(ch);
    } else if (!ret.empty()) {
      ret.pop_back();
    }
  }
  return ret;
}
*/

int main() {
  string s = "123###456";
  string t = "456##123";
  Solution solution;
  cout << endl;
  // 默认使用整数0/1来代表bool值
  // cout << solution.backspace_compare(s, t) << endl;
  // 使用std::boolalpha转化为true和false，对应有noboolalpha
  cout << std::boolalpha << solution.backspace_compare(s, t) << endl;
  return 0;
}

leetcode-977

// 有序数组的平方，按大小排列
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
 public:
  vector<int> sorted_squares(vector<int>& nums) {
    // 法1: 直接排序, time_O(nlogn), space_O(logn)
    // 不创建ans可以直接在nums数组上操作，nums[i] *= nums[i];
    /*
    vector<int> ans;
    for (int num : nums) {
      ans.push_back(num * num);
    }
    sort(ans.begin(), ans.end());
    return ans;
    */



    // 法2: 双指针, time_O(n), space_O(1), 忽略存储数组的O(n)
    /*
    int n = nums.size();
    // 负数与非负数的分界线
    int negative = -1;
    // 确定分界线，两边分别平方，通过分界线两侧数据进行排序插入
    for (int i = 0; i < n; ++i) {
      if (nums[i] < 0) {
        negative = i;
      } else {
        break;
      }
    }

    vector<int> ans;
    int i = negative, j = negative + 1;
    while (i >= 0 || j < n) {
      if (i < 0) {
        // 非负数组，赋值给i的是negative的初始值-1
        ans.push_back(nums[j] * nums[j]);
        ++j;
      } else if (j == n) {
        // 通过j == n 判断 i 是数组最右边的数，即非正数组
        ans.push_back(nums[i] * nums[i]);
        --i;
      } else if (nums[i] * nums[i] < nums[j] * nums[j]) {
        // 负数、非负数都有
        // 放入平方的最小值，注意--i和++j的区别
        ans.push_back(nums[i] * nums[i]);
        --i;
      } else {
        ans.push_back(nums[j] * nums[j]);
        ++j;
      }
    }
    return ans;
    */



    // 法3: 双指针,time_O(n), space_O(1)
    // 双指针表示0和n-1,比较两个对应的数，较大的逆序到答案数组
    int n = nums.size();
    vector<int> ans(n,0);
    // 双指针i,j表示最左边和最右边的值，pos表示新数组的最大值
    for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
      if (nums[i] * nums[i] > nums[j] * nums[j]) {
        ans[pos--] = nums[i] * nums[i];
        ++i;
      } else {
        ans[pos--] = nums[j] * nums[j];
        --j;
      }
    }
    return ans;
  }
};

int main() {
  vector<int> a = {-4, -1, 0, 3, 10};
  vector<int> ans;
  Solution solution;
  ans = solution.sorted_squares(a);
  cout << endl;
  for (int i = 0; i < ans.size(); ++i) {
    cout << ans[i] << " ";
  }
  return 0;
}

/*
vector可以像普通变量那样在函数体内声明后返回，返回的是临时对象，只能复制，不能返回它的应用和迭代器

如果vector存放的不是基本类型，是自定义类型的话，最好重写这个类的拷贝构造函数

vector的底层数据结构是数组，当用返回对象的方法返回vector时，vector会进行整个数组的拷贝，如果数组较大，则效率很低。
如果要返回的vector是在函数内部new的，那么可以返回该vector的指针，要注意vector的释放问题
由于vector的存储空间位置可能在插入、删除的时候变化，要小心迭代器的失效问题

vector的元素类型有要求，必须要能够支持赋值运算和对象必须可以复制
*/

滑动窗口

leetcode-76

// 最小覆盖字串
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
 public:
 // 两个map用来表示t中的字符与个数、滑动窗口的字符与个数
  unordered_map <char, int> original, count;
  
  // 判断original中的元素是否都包含在count里，即滑动窗口包含了t所有的字符
  bool check() {
    for (const auto &p : original) {
      // count中各个元素的个数 >= original中对应元素的个数
      if (count[p.first] < p.second) {
        return false;
      }
    }
    return true;
  }

  string min_window(string s, string t) {
    // 将t的所有元素存入map中
    for (const auto &c : t) {
      ++original[c];
    }
    int left = 0, right = -1;
    int len = INT32_MAX, ansL = -1;
    // 循环，右指针未超出字符串大小范围
    while (right < int(s.size())) {
      // 在字符串t的map中查找字符串s的指针对应的字符
      // find()函数返回一个迭代器指向键值为key的元素，如果没找到就返回指向map尾部的迭代器
      // 这边与尾部迭代器做是否相等判断，若不等，说明找到了该元素
      // 找到元素后存入计数的map里
      if (original.find(s[++right]) != original.end()) {
        ++count[s[right]];
      }
      // 检查count是否 >= original，且左指针<=右指针
      while (check() && left <= right) {
        // 获取最小长度
        if (right - left + 1 < len) {
          len = right - left + 1;
          // 确定最终满足条件的左指针
          ansL = left;
        }
        // 为了获取最小字符串，使用左指针尝试将一些字符删除
        // 能找到字符，在count中删除一个字符，并将左指针右移
        // 找不到字符，左指针直接右移
        // 一次运行结束后进行while循环，如果条件依旧满足，则可以继续，并重新计算len
        // 如果不满足while循环，即当前left的前一个字符是不可删除的，退出循环
        if (original.find(s[left]) != original.end()) {
          --count[s[left]];
        }
        ++left;
      }
    }
    // 返回最终确定的ansL,进行判断，是否==初始值
    // 若等于，则说明没有合适条件的left赋值给ansL，即没有满足while循环的条件
    // 说明字符串s中不包含字符串t的所有元素，返回" "
    // 若不相等，则返回从下标ansL开始，长度为len的字符串
    // substr(string, length)
    return ansL == -1 ? string() : s.substr(ansL, len);
  }
};

int main() {
  string s = "ADOBECODEBANC", t = "ABC";
  Solution solution;
  cout << endl;
  cout << solution.min_window(s, t) << endl;
}

leetcode-209

// 求长度最小 >= target的连续子数组
#include <iostream>
#include <vector>
using namespace std;

class Solution {
 public:
  int min_sub_array_len(int target, vector<int>& nums) {
    // 法1: 暴力解法，两个for循环, time_O(n^2)
    /*
    int result = INT32_MAX;  // 最终结果,初始值为最大值
    int sum = 0;  // 子数组的数值和
    int sub_length = 0;  // 子数组的长度
    for (int i = 0; i < nums.size(); ++i) {
      sum = 0;
      for (int j = i; j < nums.size(); ++j) {
        sum += nums[j];
        if (sum >= target) {
          sub_length = j - i + 1;  // 获取长度
          // 将长度最小的数组的长度赋值给result
          result = result < sub_length ? result : sub_length;
          break;
        }
      }
    }
    // 判断result是否被赋值
    return result == INT32_MAX ? 0 : result;
    */


    // 法2: 滑动窗口(可以理解为双指针的一种), time_O(n)
    int result = INT32_MAX;
    int sum = 0;
    int i = 0;  // 滑动窗口起始位置
    int sub_length = 0;
    for (int j = 0; j < nums.size(); ++j) {
      sum += nums[j];
      while (sum >= target) {
        sub_length = j - i + 1;
        result = result < sub_length ? result : sub_length;
        sum -= nums[i++];  // 精髓! 不断变更初始值i的位置
      }
    }
    return result == INT32_MAX ? 0 : result;
  }
};

int main() {
  vector<int> nums = {2, 3, 1, 2, 4, 3};
  int target = 7;
  Solution solution;
  cout << endl;
  cout << solution.min_sub_array_len(target, nums) << endl;
  return 0;
}

leetcode-904

// 求长度最小 >= target的连续子数组
#include <iostream>
#include <vector>
using namespace std;

class Solution {
 public:
  int min_sub_array_len(int target, vector<int>& nums) {
    // 法1: 暴力解法，两个for循环, time_O(n^2)
    /*
    int result = INT32_MAX;  // 最终结果,初始值为最大值
    int sum = 0;  // 子数组的数值和
    int sub_length = 0;  // 子数组的长度
    for (int i = 0; i < nums.size(); ++i) {
      sum = 0;
      for (int j = i; j < nums.size(); ++j) {
        sum += nums[j];
        if (sum >= target) {
          sub_length = j - i + 1;  // 获取长度
          // 将长度最小的数组的长度赋值给result
          result = result < sub_length ? result : sub_length;
          break;
        }
      }
    }
    // 判断result是否被赋值
    return result == INT32_MAX ? 0 : result;
    */


    // 法2: 滑动窗口(可以理解为双指针的一种), time_O(n)
    int result = INT32_MAX;
    int sum = 0;
    int i = 0;  // 滑动窗口起始位置
    int sub_length = 0;
    for (int j = 0; j < nums.size(); ++j) {
      sum += nums[j];
      while (sum >= target) {
        sub_length = j - i + 1;
        result = result < sub_length ? result : sub_length;
        sum -= nums[i++];  // 精髓! 不断变更初始值i的位置
      }
    }
    return result == INT32_MAX ? 0 : result;
  }
};

int main() {
  vector<int> nums = {2, 3, 1, 2, 4, 3};
  int target = 7;
  Solution solution;
  cout << endl;
  cout << solution.min_sub_array_len(target, nums) << endl;
  return 0;
}

螺旋矩阵

leetcode-54

#include <iostream>
#include <vector>
using namespace std;

class Solution {
 public:
  vector<int> spiral_order(vector<vector<int>>& matrix) {
    vector<int> ans;
    // matrix.empty()
    if (matrix.size() == 0)  return ans;
    int top = 0;
    int bottom = matrix.size() - 1;
    int left = 0;
    int right = matrix[0].size() - 1;
    while (true) {
      for (int i = left; i <= right; ++i)  ans.push_back(matrix[top][i]);
      if (++top > bottom)  break;
      for (int i = top; i <= bottom; ++i)  ans.push_back(matrix[i][right]);
      if (--right < left)  break;
      for (int i = right; i >= left; --i)  ans.push_back(matrix[bottom][i]);
      if (--bottom < top)  break;
      for (int i = bottom; i >= top; --i)  ans.push_back(matrix[i][left]);
      if (++left > right)  break;
    }
    return ans;
  }
};

int main() {
  Solution solution;
  vector<vector<int>> matrix = {{1,2,3},{4,5,6}};
  auto ans = solution.spiral_order(matrix);
  for (int i = 0; i < ans.size(); ++i) {
    cout << ans[i] << " ";
  }
}

leetcode-59

// 螺旋矩阵II,给正整数n，生成一个包含1到n^2所有元素，
// 顺时针螺旋排列的n x n正方形矩阵matrix
// 与二分法类似，保持循环不变量原则，即边界值是否能取到要固定
// eg:[left, right] 或者[elft, right)
#include <iostream>
#include <vector>
using namespace std;

// 解题思路：模拟过程，对于各种边界值需要分配好
class Solution {
 public:
  vector<vector<int>> generate_matrix(int n) {
    /*
    // 定义一个二维数组，存放1-n^2的元素
    vector<vector<int>> ans(n, vector<int>(n, 0));
    // 定义每循环一个圈的起始位置
    int startx = 0, starty = 0;
    // 每个圈循环的次数，如n=3，循环1次；n=4，循环2次
    int loop = n / 2;
    // 矩阵中间的位置
    int mid = n / 2;
    // 给矩阵的每一个空格赋值
    int count = 1;
    // 每一圈循环，每一行/列的长度，需要进行控制，使用该变量控制
    int offset = 1;
    int i, j;
    while (loop--) {
      i = startx;
      j = starty;
      // 模拟循环，转圈，每一行/列都是左闭右开
      // 从左到右
      for (j = starty; j < starty + n - offset; ++j) {
        ans[startx][j] = count++;
      }
      // 从右往下
      for (i = startx; i < startx + n - offset; ++i){
        ans[i][j] = count++;
      }
      // 从右往左
      for (; j > starty; --j) {
        ans[i][j] = count++;
      }
      // 从左往上
      for (; i > startx; --i) {
        ans[i][j] = count++;
      }
      // 第二圈开始时，起始位置的变化和offset的变化
      startx++;
      starty++;
      offset += 2;
    }

    // 如果n为奇数，则中心是一个单独的数，需要单独赋值；
    // 为偶数时，中心为2行2列的数据
    if (n % 2) {  // 直接判断，不需要 ==
    ans[mid][mid] = count;
    }
    return ans;
    */



    vector<vector<int>> ans(n, vector<int>(n, 0));
    // 定义上下左右
    int top = 0;
    int bottom = n - 1;
    int left = 0;
    int right = n - 1;
    int count = 1;
    int end = n * n;

    while (count <= end) {
      for (int i = left; i <= right; i++)
        ans[top][i] = count++;
      top++;
      for (int i = top; i <= bottom; i++)
        ans[i][right] = count++;
      right--;
      for (int i = right; i >= left; i--)
        ans[bottom][i] = count++;
      bottom--;
      for (int i = bottom; i >= top; i--)
        ans[i][left] = count++;
      left++;
    }
    return ans;
  }
};

int main() {
  // 定义类
  Solution solution;
  auto ans = solution.generate_matrix(5);
  // 二维数组，两层for循环
  for (int i = 0; i < ans.size(); ++i) {
    for (int j = 0; j < ans[0].size(); ++j) {
      cout << ans[i][j] << " ";
    }
    cout << endl;
  }
}

本文由 szr 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Sep 16, 2021 at 08:04 pm