【代码随想录】二刷-数组

7

数组

  • 《代码随想录》

    二分查找

    704. 二分查找

    方法1

  • 注意:
    • 边界控制。
    • 前提是有序数组。
    • 循环控制
  • 解释: 这里使用我最好理解的一种方式。
    • 使用mid控制下标访问，nums[mid]大于target，+1更新左边界，反之，-1更新右边界。相等即找到目标数。
    • while循环条件left<=right,left=right仍有需要判断的数。即目标数的索引在数组的 边界。
    • 防止left+right过大会溢出，所以写成(right-left)/2，等同于(right+left)/2 
      
// 时间复杂度: O(log n)
// 空间复杂度: O(1)
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0;
int right = n-1;
    while(left <= right){
        int mid = left+((right-left)/2);
        if(nums[mid] > target){
            right = mid - 1;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else{
            return mid;
        }
    }
    return -1;
}

};

**方法2**
>- 与上一种方法的区别在于区间的控制不同，方法1为[left,right]，方法2为[left,right)。
```C++
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();

        while(left < right){// 等于时无意义
            int mid = left + (right-left)/2;
            if(nums[mid] > target){
                right = mid;
            }else if(nums[mid] < target){
                left = mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
};</code></pre>
<blockquote>
<ul>
<li>感悟:
<ul>
<li>算是比较基础的算法了，前两天给群友回答问题的时候，也重新复习了一下，这次顺利AC。</li>
<li>这两天可能也是没啥状态，被KMP困住了好久，希望数组可以给我找回点自信。</li>
<li>不过这题上来我写了个for循环，md，还是错了下。
<hr /></li>
</ul></li>
</ul>
</blockquote>
<h3><a href="https://leetcode.cn/problems/search-insert-position/">35. 搜索插入位置</a></h3>
<blockquote>
<ul>
<li>同上一题，不过需要多想一下插入的位置。
<ul>
<li>分析每种情况:
<ul>
<li>目标值在数组所有元素之前</li>
<li>目标等于数组中的某一个元素</li>
<li>目标值插入到数组中</li>
<li>目标值在所有元素之后
<pre><code class="language-C++">// 时间复杂度: O(log n)
// 空间复杂度: O(1)
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int left = 0;
int right = n-1;
while(left <= right){
int mid = left + ((right-left)/2);
if(nums[mid] > target){
right = mid-1;
}else if(nums[mid] < target){
left = mid + 1;
}else{
return mid;// 等于数组中某个存在元素
}
}
return right+1;// 其它三种情况
}
};</code></pre>
<hr />
<h3><a href="https://programmercarl.com/0034.%E5%9C%A8%E6%8E%92%E5%BA%8F%E6%95%B0%E7%BB%84%E4%B8%AD%E6%9F%A5%E6%89%BE%E5%85%83%E7%B4%A0%E7%9A%84%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%92%8C%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%E4%BD%8D%E7%BD%AE.html">34. 在排序数组中查找元素的第一个和最后一个位置</a></h3></li>
</ul></li>
</ul></li>
<li>分析每一种情况
<ul>
<li>target在数组的范围内，但是不存在于数组中。</li>
<li>target在数组范围内，存在于数组中。</li>
<li>target不在数组范围内。同样也不存在与数组中。</li>
</ul></li>
<li>在最基础的二分查找上减少了判断，不断收缩边界。结合示例带入进行运算下。
<pre><code class="language-C++">class Solution {
public:
/*
nums:    5 7 7 8 8 10
index:   0 1 2 3 4 5
*/
int getLeftBorder(vector<int>& nums,int target){
int left = 0;
int right = nums.size()-1;
int ret = -2;
while(left <= right){
int mid = left + (right-left)/2;
if(nums[mid] >= target){
right = mid - 1;
ret = right;
}else{
left = mid + 1;
}
}
return ret;
}
int getRightBorder(vector<int>& nums,int target){
int left = 0;
int right = nums.size()-1;
int ret = -2;
while(left <= right){
int mid = left + (right-left)/2;
if(nums[mid] > target){
right = mid - 1;
}else{
left = mid + 1;
ret = left;
}
}
return ret;       
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftBorder = getLeftBorder(nums,target);
int rightBorder = getRightBorder(nums,target);
if(leftBorder == -2 || rightBorder == -2){// 情况三
return {-1,-1};
}
if(rightBorder - leftBorder > 1){
return {leftBorder+1,rightBorder-1};// 情况二
}
return {-1,-1};// 情况一
}
};</code></pre>
<hr />
<h3><a href="https://leetcode.cn/problems/sqrtx/">69. x 的平方根 </a></h3>
<pre><code class="language-C++">// 时间复杂度 O(logn)
// 空间复杂度 o(1)
class Solution {
public:
int mySqrt(int x) {
int left = 0;
int right = x;
int ret = -1;
while(left <= right){
int mid = left + (right-left)/2;
if((long long)mid * mid <= x){
ret = mid;
left = mid + 1;
}else{
right = mid -1;
}
}
return ret;
}
};</code></pre>
<hr />
<h3><a href="https://leetcode.cn/problems/valid-perfect-square/">367. 有效的完全平方数</a></h3></li>
<li>二分法的使用，注意根据题意进行判断。</li>
<li>个人感觉比上面那两道题要好理解
<pre><code class="language-C++">// 时间复杂度 O(logn)
// 空间复杂度 O(1)
class Solution {
public:
bool isPerfectSquare(int num) {
int left = 0;
int right = num;
while(left <= right){
int mid = left + (right-left)/2;
if((long long)mid*mid < num){
left = mid + 1;
}else if((long long)mid* mid > num){
right = mid - 1;
}else{
return true;
}
}
return false;
}
};</code></pre>
<hr />
<h2>双指针</h2>
<h3><a href="https://leetcode.cn/problems/remove-element/">27. 移除元素</a></h3></li>
<li>暴力
<pre><code class="language-C++">// 时间复杂度O(n²)
// 空间复杂度O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
/*3 3 2 2 3 3
3 3 2 3 3
*/
int n = nums.size();
for(int i = 0 ; i < n ;i++){
if(nums[i] == val){
for(int j = i+1;j < n;j++){
nums[j-1] = nums[j];
}
i--;// 后面整体前移，i也前移
n--;
}      
}
return n;
}
};   </code></pre></li>
<li>双指针
<ul>
<li>快指针负责搜寻目标值，当找到目标，慢指针停住，将后面的非目标值换上来。    
<pre><code class="language-C++">
// 时间复杂度O(n)  
// 空间复杂度O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n =  nums.size();
int slowIndex = 0;
for(int fastIndex = 0;fastIndex < n;fastIndex++){
if(nums[fastIndex] != val){// 找到目标值了，慢指针就不动了
nums[slowIndex++] = nums[fastIndex];// 把后面不是目标值的替换上来
}
}
return slowIndex;</code></pre></li>
</ul></li>
</ul>
</blockquote>
<pre><code>}</code></pre>
<p>};</p>
<pre><code>***
### [26. 删除有序数组中的重复项](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/)
>- 双指针，快指针带路，将挑选出来的数，传递给慢指针。完成去重效果。
```C++
// 时间复杂度 O(n)
// 空间复杂度 O(1)
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 1;
        int fast = 1;
        int n = nums.size();
        if(n == 0){
            return 0;
        }
        while( fast < n){
            if(nums[fast] != nums[fast-1]){
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        // 从题目中可以看出，根据新的长度来遍历数组进行判断
        return slow;

    }
};

283.移动零

  • 双指针 
    // 时间复杂度O(N)
// 空间复杂度O(1)
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// 在不赋值数组的情况下原地对数组进行操作
int n = nums.size();
if(n == 0)return ;
int fast = 0;
int slow =0;
while(fast < n){
if(nums[fast] != 0){
swap(nums[slow++],nums[fast]);
}
fast++;
}
}
};

    844.比较含退格的字符串

  • 双指针: 遇到‘#’t将，#后面的数与#前面的交换，最后根据slow指针截取长度。 
    // 时间复杂度O(n)
// 空间复杂度O(m+n) 貌似
class Solution {
public:
string build(string s){
int n = s.size();
int slow = 0;
for(int fast = 0;fast < n;fast++){
if(s[fast] != '#'){
s[slow] = s[fast];
slow++;
}else if(slow > 0){
slow--;
}
}
return s.substr(0,slow);
}
bool backspaceCompare(string s, string t) {
return build(s) == build(t);
}
};
  • 用栈很简单,主要还是掌握双指针。 
    // 时间复杂度 O(m+n) 即O(n)
// 空间复杂度 O(m+n)
class Solution {
public:
string build(string s){
stack<char>st;
for(char c:s){
if(c != '#'){// 刚开始这里多了个条件，st.empty()然后把我坑了。
st.push(c);
}else if(c == '#' && !st.empty()){
st.pop();
}
}
string ret = "";
while(!st.empty()){
ret += st.top();
st.pop();
}
return ret;
}
bool backspaceCompare(string s, string t) {
return build(s) == build(t);
}
};

    977.有序数组的平方

  • 双指针: 默认是从升序，但是负数平方后不一定比右边大的整数平方小，i指针从前遍历，j指针从后遍历，取出较大的放入结果集，并移动指针。 
    // 时间复杂度 O(n)
// 空间复杂度 O(n)
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int i = 0;
int j = nums.size() - 1;
int k = nums.size() - 1;
vector<int>ret(nums.size());
while(i <= j){
if(nums[j]*nums[j] > nums[i]*nums[i]){
ret[k--] = nums[j]*nums[j];
j--;
}else{
ret[k--] = nums[i] * nums[i];
i++;
}
}
return ret;
}
};
  • 暴力 
    // 时间复杂度 O(n+nlogn)
// 空间复杂度 O(n)
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
for(int i = 0; i < n;i++){
nums[i] *= nums[i];
}
sort(nums.begin(),nums.end());
return nums;
}
};

    滑动窗口

  • 所谓滑动窗口，就是不断的调节子序列和起始位置和终止位置，从而得出我们想要的结果。
  • 滑动窗口三部曲
  • 本题中:
    • 窗口: 为满足和 >= s的长度最小的连续子数组
    • 窗口的起始位置如何移动: 如果当前窗口的值大于s了，窗口就要向前移动了(即，该缩小了)。
    • 窗口的结束位置如何移动: 窗口结束位置就是遍历数组的指针，也就是for循环里的索引。
  • 解题的关键在于窗口的其实位置如何移动。
  • j负责便利数组，即j为窗口右侧，i为窗口左侧，当窗口内的值sum大于targat了。
  • 就开始计算长度，保存结果，并使窗口的左侧右移。更新窗口内数字和。
  • 这是个循环的过程，因为可能去掉左侧的一个值，当前和扔大于target。 
    // 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int ret = INT_MAX;// 结果
int sum = 0;// 窗口内元素之和
int i = 0;// 窗口的左侧
int subLength = 0;// 窗口的长度
for(int j = 0; j < n ; j++){
sum += nums[j];
while(sum >= target){// 维护窗口
subLength = j - i + 1;
ret = ret > subLength?subLength:ret;
sum -= nums[i++];
}
}
return ret == INT_MAX ? 0 : ret;
}
};

    904. 水果成篮

  • 本题中的滑动窗口为一个只能装两种水果的水果篮。
  • 使用一个哈希表来记录窗口中的元素数量，当窗口中的种类>2(即==3了)，就开始判断上一次的窗口长度(即水果数量)。 
    // 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int,int>mp;
int n = fruits.size();
int ret = 0;// 保存结果，摘取的水果数量
for(int i = 0,j = 0;i < n; i++){
mp[fruits[i]]++;// 摘取水果
while(mp.size() > 2){// 维护滑动窗口
int cur = fruits[j++];
if(--mp[cur] == 0)mp.erase(cur);// 将水果篮中的一种水果拿光了，这时栏中又只剩两种水果了
}
ret = max(ret,i-j+1);// 求长度，即数量
}
return ret;
}
};

    76. 最小覆盖子串

  • 相关题解-最小覆盖子串 | 图解滑动窗口 | 最通俗易懂的讲解【c++/java版本】
  • 大致步骤:
    • 本题中维护的滑动窗口为使用哈希表保存遍历s每一个的字符，j为窗口左边界，i为窗口右边界，同时负责向后遍历。
    • 如果在我们当前遍历过的s中，其中的某一个字符出现的次数大于在t中出现的次数，此时我们可以尝试收缩边界，即j--。
    • 使用一个变量cnt来记录当前遍历过的s中，包含在t中的字符个数，当t==t.size()时，说明我们要找的字符都已经找到了，然后开始获取结果，
  • 详细流程详见代码中的注释。 
    // 时间复杂度O(n)
// 空间复杂度O(m+n) 貌似
class Solution {
public:
string minWindow(string s, string t) {
//ts为统计我们需要的字符与其对应的数量，ss为我们维护的滑动窗口
unordered_map<char,int>ts,ss;
// 先统计要查找字符串中各个字符的数量
for(char& c:t)ts[c]++;
int n = s.size();
string ret;
int cnt = 0;// 统计当前应该收集元素的个数
for(int i = 0,j=0;i<n;i++){
ss[s[i]]++;
// 统计收集的指定元素数量和，即找到t中的所有字符，在s中。
if(ss[s[i]] <= ts[s[i]])cnt++;
// 窗口收缩，如果当前的元素s[j](窗口左边界)收集的数量已经大于我们需要的，那就收缩左边界。或者去掉t中没有的元素。
while(ss[s[j]] >ts[s[j]])ss[s[j++]]--;
if(cnt == t.size()){// 每种元素都收集到了，开始计算长度
if(ret.empty() || i-j+1 < ret.size()){// 减少计算次数，如果没计算过或找到更小的连续子数组，才计算，收集结果。
ret = s.substr(j,i-j+1);
}
}
}
return ret;
}
};

    模拟行为

    59. 螺旋矩阵 II

  • 顺时针转，注意控制边界和起始位置。左闭右开。 
    class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>>ret(n,vector<int>(n,0));
int starX = 0;// 每圈开头
`       int starY = 0;
int loop = n / 2;// 转几圈
int mid = n / 2;// 矩阵中间的位置
int count = 1;// 每个元素值
int offset = 1;// 收缩个数
// 顺时针转
int i = 0,j =0;
while(loop--){
i = starX;
j = starY;
// 左闭右开
for(j = starY;j < n-offset;j++){
ret[starX][j] = count++;
}
for(i = starX;i < n-offset;i++){
ret[i][j] = count++;
}
for(;j > starY;j--){
ret[i][j] = count++;
}
for(;i > starX;i--){
ret[i][j] = count++;
}
offset++;
starX++;
starY++;
}
if(n % 2){// 给中间位置单独赋值
ret[mid][mid] = count;
}
return ret;
}
};

    54. 螺旋矩阵

  • 同上，不过这题是获取元素，注意本体的获取元素以及控制边界的方法，还是与上一题有所不同的。
  • 可以理解≈左开右闭。 
    class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int rc = matrix.size()-1;// 行数-下边界
int cc = matrix[0].size()-1;// 列数-右边界
int row = 0;// 标记当前行-上边界
int col = 0;// 标记当前列-左边界
vector<int>ret;
while(true){
for(int i = col;i <= cc;i++){
ret.push_back(matrix[row][i]);
}
if(++row > rc)break;// 收缩上边界
for(int i = row;i <= rc;i++){
ret.push_back(matrix[i][cc]);
}
if(--cc < col)break;// 收缩右边界
for(int i = cc;i >= col;i--){
ret.push_back(matrix[rc][i]);
}
if(--rc < row)break;// 收缩下边界
for(int i = rc;i>= row;i--){
ret.push_back(matrix[i][col]);
}
if(++col > cc)break;// 收缩左边界
}
return ret;
}
};

    剑指 Offer 29. 顺时针打印矩阵

  • 与上一题完全相同，但是要加入矩阵是否为空的判断，因为这题给的数据可以为空。 
    class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int>ret;
if(matrix.empty())return ret;
int rc = matrix.size()-1;// 下
int cc = matrix[0].size()-1;// 右
int row = 0;//上
int col = 0;// 左      
while(true){
for(int i = col;i <=cc;i++){
ret.push_back(matrix[row][i]);
}
if(++row > rc)break;
for(int i = row;i <= rc;i++){
ret.push_back(matrix[i][cc]);
}
if(--cc < col)break;
for(int i = cc; i >= col;i--){
ret.push_back(matrix[rc][i]);
}
if(--rc < row)break;
for(int i = rc; i >= row;i--){
ret.push_back(matrix[i][col]);
}
if(++col > cc)break;
}
return ret;
}
};