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

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