力扣-数组专题

in 力扣 with 164 comments

C++

相关知识点

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

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

常用方法

map和unordered_map的区别

  1. 实现机制不同

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

  1. 适用情况不同

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

← → ↓ ↑
Responses
  1. https://cse.google.co.ke/url?q=https://www.hkflowersdelivery.com

    |Create your own special style. It is easy to dress like everyone else, but you should create a style all your own. You have to be comfortable with yourself in order to do this. Although once you decide to follow this path, you will notice the increase in compliments you receive.

    Reply
  2. https://www.google.ee/url?sa=t&url=https://www.hkflowersdelivery.com

    |Buy a lot of basics. Target items that are always in fashion, yet work with other styles as well. A basic black dress or blazer can be worn year after year.

    Reply
  3. https://images.google.cz/url?q=https://www.giftspresentsformen.com

    Although you might pretend that it's not important, you definitely want people to notice how good you're looking. Fashionable clothing can help increase your self-esteem as well as your social life. To improve your life, make a fashion investment. For easy tips you can use to look and dress better, keep reading this collection of helpful hints and advice.

    Reply
  4. https://register.scotland.gov.uk/subscribe/widgetsignup?url=https://www.giftspresentsformen.com

    When did you last shop for new clothes? Well, although you may be out of practice, that doesn't mean you can't shop for some stylish fashions just like the rest of us. Don't fret over this. The following article has ideas that can help.

    Reply
  1. 1
  2. ...
  3. 15
  4. 16
  5. 17