数组

数组

参考代码随想录

704. 二分查找

左右闭合的查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 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; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

27. 移除元素

  • 个人思路,双指针,一个最前,一个最后

    class Solution
    {
    public:
      int removeElement(vector &nums, int val)
      {
          // 遇到targe 把最后面的交换
          int res = nums.size();
          int l = 0, r = nums.size() - 1;
    
          while (l <= r)
          {
              if (nums[l] == val)
              {
                  if (nums[r] != val)
                  {
                      nums[l] = nums[r];
                      r--;
                      l++;
                      res--;
                  }
                  else
                  {
                      r--;
                      res--;
                  }
              }
              else
              {
                  l++;
              }
          }
          return res;
      }
    };
  • 快慢指针

    class Solution {
    public:
      int removeElement(vector& nums, int val) {
          int slowIndex = 0;
          for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
             // 快指针和val相等,则快指针增加,其余不动
             // 快指针和val不等,慢指针和快指针的值相等,慢指针增加
              if (val != nums[fastIndex]) {
                  nums[slowIndex++] = nums[fastIndex];
              }
          }
          return slowIndex;
      }
    };

977. 有序数组的平方

  • 直接排序

    class Solution {
    public:
      vector sortedSquares(vector& A) {
          for (int i = 0; i < A.size(); i++) {
              A[i] *= A[i];
          }
          sort(A.begin(), A.end()); // 快速排序
          return A;
      }
    };
  • 双指针逆序放入

    
    class Solution {
    public:
      vector sortedSquares(vector& nums) {
          vector ans(nums.size(),0);
          int k = nums.size()-1;  // ans的逆序计数器
          for(int l=0, r=nums.size()-1; l<=r;) {
              // 右边大
              if(nums[l]*nums[l] < nums[r]*nums[r]){
                  ans[k] = nums[r]*nums[r];
                  r--;
              } else {
                  ans[k] = nums[l]*nums[l];
                  l++;
              }
              k--;
          }
          return ans;
      }
    };

209. 长度最小的子数组

  • 暴力解法

    class Solution {
    public:
      int minSubArrayLen(int s, vector& nums) {
          int result = INT32_MAX; // 最终的结果
          int sum = 0; // 子序列的数值之和
          int subLength = 0; // 子序列的长度
          for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
              sum = 0;
              for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                  sum += nums[j];
                  if (sum >= s) { // 一旦发现子序列和超过了s,更新result
                      subLength = j - i + 1; // 取子序列的长度
                      result = result < subLength ? result : subLength;
                      break; // 因为我们是找符合条件最短的子序列,所以一旦符合条件就break
                  }
              }
          }
          // 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列
          return result == INT32_MAX ? 0 : result;
      }
    };
  • 滑动窗口

    class Solution {
    public:
      int minSubArrayLen(int target, vector& nums) {
          int ans = INT_MAX;  // 初始为最大
          int sum = 0;
          for(int l=0,r=0; r= target) {
                  int length = r-l+1;
                  ans = ans

59. 螺旋矩阵 II

主要是模拟和确定边界

  • 方法一

    class Solution {
    public:
      vector> generateMatrix(int n) {
          vector> ans(n, vector(n,0));
          // 设置四个边界
          int t=0, l=0, b=n-1, r=n-1;
          int value = 1;  //填入的值
          while(value<=n*n) {
              // 从左到右
              for(int i=l;i<=r;i++) ans[t][i] = value++;
              t++;
              // 从上到下
              for(int i=t;i<=b;i++) ans[i][r] = value++;
              r--;
              // 从右到左
              for(int i=r;i>=l;i--) ans[b][i] = value++;
              b--;
              // 从下到上
              for(int i=b;i>=t;i--) ans[i][l] = value++;
              l++;
          }
          return ans;
      }
    };
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇