leetcode_算法入门

Day1 二分查找

704. 二分查找

  • 递归方法

    class Solution {
    public:
      int recur(vector& nums,int start, int end, int target) {
          int mid = (start + end ) /2;
          if (mid < start || mid > end) return -1;
          if (nums[mid] > target) return recur(nums,start, mid-1, target);
          else if (nums[mid] < target) return recur(nums,mid+1,end , target);
          else return mid;
      }
      int search(vector& nums, int target) {
          int start = 0;
          int end = nums.size()-1;
          return recur(nums, start,end,target);
      }
    };
  • 非递归

    class Solution {
    public:
      int search(vector& 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){
                  // target 在右区间,所以[middle + 1, right]
                  left = mid+1;
              }
              else if (nums[mid] > target){
                  right = mid-1;
              }
              else {
                  return mid;
              }
          }
          return -1;
      }
    };

278. 第一个错误的版本

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { // 循环直至区间左右端点相同
            int mid = left + (right - left) / 2; // 防止计算时溢出
            if (isBadVersion(mid)) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right,区间缩为一个点,即为答案
        return left;
    }
};

35. 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size()-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;
            }
        }
        // l=r,且没找到target
        return left;
    }
};

Day2 双指针

977. 有序数组的平方

  • 计算后直接排序

    class Solution {
    public:
      vector sortedSquares(vector& nums) {
          vector res;
          for(int i: nums){
              res.push_back(i*i);
          }
          sort(res.begin(), res.end());
          return res;
      }
    };
  • 双指针1:找到正负之间的位置,左右两个指针负数从最大的开始,正数从最小的开始

    class Solution {
    public:
      vector sortedSquares(vector& nums) {
          int len = nums.size();
          // 初始化为最大 防止全负
          int positive = len;
          for (int i=0; i=0) {
                  positive = i;
                  break;
              }
          }
          vector res;
          // 双指针,left从index为0开始到positive-1,right从positive到最后
          int left=positive-1, right=positive;
          while(left>=0 || right=0) {
                  // right为len 左边还有
                  res.push_back(nums[left]*nums[left]);
                  --left;
              }
              else if ( -nums[left] < nums[right]) {
                  res.push_back(nums[left]*nums[left]);
                  --left;
              } else {
                  res.push_back(nums[right]*nums[right]);
                  ++right;
              }
    
          } 
    
          return res;
      }
    };
  • 双指针2:使用两个指针分别指向位置 00 和 n-1n−1,每次比较两个指针对应的数,选择较大的那个逆序放入答案并移动指针。

    class Solution {
    public:
      vector sortedSquares(vector& nums) {
          int n = nums.size();
          vector ans(n);
          //逆序放入
          for(int i=0,j=n-1,pos=n-1;i<=j;) {
              if(nums[j]*nums[j] > nums[i]*nums[i]) {
                  ans[pos] = nums[j]*nums[j];
                  j--;
              } else {
                  ans[pos] = nums[i]*nums[i];
                  i++;
              }
              pos--;
          }
          return ans;
      }
    };

189. 轮转数组

  • 创建新数组

    class Solution {
    public:
      void rotate(vector& nums, int k) {
          int n = nums.size();
          vector res(n);
          for(int i=0; i
  • 环状替换,求解最大公约数进行循环遍历

  • 原地修改,翻转。该方法为数组的翻转:我们可以先将所有元素翻转,这样尾部的 k mod n 个元素就被移至数组头部,然后我们再翻转[0,kmodn−1] 区间的元素和 [kmodn,n−1] 区间的元素即能得到最后的答案。

    class Solution {
    public:
      void reverse(vector& nums, int start, int end) {
          while(start < end) {
              swap(nums[start], nums[end]);
              start ++;
              end --;
          }
      }
      void rotate(vector& nums, int k) {
          k %= nums.size();
          // 全部旋转
          reverse(nums,0, nums.size()-1);
          // 分别旋转
          reverse(nums, 0, k-1);
          reverse(nums, k, nums.size()-1);
    
      }
    };

Day3 双指针

283. 移动零

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        // 双指针,都从最左边开始,将0换到最右边
        // left维护非零部分,right遇到0和left交换
        for(int left=0,right =0;right<nums.size();){
            if(nums[right]!=0) {
                swap(nums[left],nums[right]);
                left++;
            }
            right++;
        }

    }
};

167. 两数之和 II - 输入有序数组

双指针,分别从最左和最右开始,大了右边左移,小了左边右游

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res;
        int left =0, right = numbers.size()-1;
        while(left<=right){
            int res = numbers[left]+numbers[right];
            if(res>target) {
                right--;
            } else if(res<target) {
                left++;
            } else {
                return {left+1, right+1};
            }
        }
        return {-1,-1};
    }
};

Day4 双指针

344. 反转字符串

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        for(int i=0; i<n/2;i++){
            swap(s[i], s[n-i-1]);
        }
    }
};

557. 反转字符串中的单词 III

当找到一个单词的时候,我们交换字符串第一个字符与倒数第一个字符,随后交换第二个字符与倒数第二个字符

class Solution {
public:
    string reverseWords(string s) {
        int low =0, high=0;
        int length = s.length();
        while(high<length) {
            if(s[high]==' '){
                // 反转字符
                for(int i=0;i<(high-low)/2;i++) {
                    swap(s[i+low], s[high-i-1]);
                    }
            // 每次更新low为字符的最开始
            low = high+1;
            }
            high++;
        }
        // 最后再交换一次
        for(int i=0;i<(high-low)/2;i++) {
            swap(s[i+low], s[high-i-1]);
            }
        return s;
    }
};

Day5 双指针

876. 链表的中间结点

构建快指针和慢指针,快指针每次前进两个,慢指针前进一个

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast->next != nullptr && fast->next->next!=nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        if(fast->next == nullptr) {
            return slow;
        }
        return slow->next;
    }
};

19. 删除链表的倒数第 N 个结点

  • 计算链表长度

    class Solution {
    public:
      int getLength(ListNode* head) {
          int length = 0;
          while (head) {
              ++length;
              head = head->next;
          }
          return length;
      }
    
      ListNode* removeNthFromEnd(ListNode* head, int n) {
          ListNode* dummy = new ListNode(0, head);
          int length = getLength(head);
          ListNode* cur = dummy;
          for (int i = 1; i < length - n + 1; ++i) {
              cur = cur->next;
          }
          cur->next = cur->next->next;
          ListNode* ans = dummy->next;
          delete dummy;
          return ans;
      }
    };
  • 双指针,快慢指针

    class Solution {
    public:
      ListNode* removeNthFromEnd(ListNode* head, int n) {
          ListNode* dummy = new ListNode(0, head);
          ListNode* fast = head;
          ListNode* slow = dummy;
          for(int i=0;inext;
          }
          while(fast != nullptr) {
              fast = fast->next;
              slow = slow->next;
          }
          slow->next = slow->next->next;
          ListNode* ans = dummy->next;
          delete dummy;
          return ans;
    
      }
    };

Day6 滑动窗口

3. 无重复字符的最长子串

遍历滑动窗口

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int right=0, left=0;
        int ans = 0;
        unordered_set<char> occ;
        // 左指针不断增加 遍历
        for(;left<n;left++) {
            // 左指针为0的时候 不变化
            if(left!=0) {
                occ.erase(s[left-1]);
            }
            // 右指针不断增加
            while(right<n && !occ.count(s[right])) {
                occ.insert(s[right]);
                right++;
            }
            ans = max(ans, right-left);
        }
        return ans;
    }
};

567. 字符串的排列

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int m = s1.length(), n = s2.length();
        if(m>n) return false;
        vector<int> cnt1(26), cnt2(26);
        for(int i=0;i<m;i++) {
            ++cnt1[s1[i]-'a'];
            ++cnt2[s2[i]-'a'];
        }
        if(cnt1 == cnt2) return true;
        // 每滑动一次 多统计一个窗口右边的 少统计一个窗口左边的
        for(int i=m;i<n;i++) {
            ++cnt2[s2[i]-'a'];
            --cnt2[s2[i-m]-'a'];
            if(cnt1 == cnt2) {
                return true;
            }
        }
        return false;
    }
};

Day7 广度优先搜索 / 深度优先搜索

733. 图像渲染

  • DFS 递归

    class Solution
    {
    public:
      const int dx[4] = {1, 0, 0, -1};
      const int dy[4] = {0, 1, -1, 0};
    
      void dfs(vector> &image, int x, int y, int color, int newColor)
      {
          if (image[x][y] == color)
          {
              image[x][y] = newColor;
              for (int i = 0; i < 4; i++)
              {
                  int mx = x + dx[i];
                  int my = y + dy[i];
                  if (mx >= 0 && mx < image.size() && my >= 0 && my < image[0].size())
                  {
                      dfs(image, mx, my, color, newColor);
                  }
              }
          }
      }
    
      vector> floodFill(vector> &image, int sr, int sc, int newColor)
      {
          int curColor = image[sr][sc];
          if (curColor != newColor)
          {
              dfs(image, sr, sc, curColor, newColor);
          }
          return image;
      }
    };
  • BFS

    class Solution {
    public:
      const int dx[4] = {1, 0, 0, -1};
      const int dy[4] = {0, 1, -1, 0};
      vector> floodFill(vector>& image, int sr, int sc, int newColor) {
          int sameColor = image[sr][sc];
          // 颜色不同
          if(sameColor != newColor) {
              queue< pair > que;
              que.emplace(sr, sc);
              image[sr][sc] = newColor;
    
              while(!que.empty()) {
                  int x = que.front().first;
                  int y = que.front().second;
                  que.pop();
                  // 遍历四周
                  for(int i=0; i<4; i++){
                      int mx = x + dx[i], my = y + dy[i];
                      if (mx >= 0 && mx < image.size() && my >= 0 && my < image[0].size() && image[mx][my] == sameColor){
                          image[mx][my]  = newColor;
                          que.emplace(mx, my);
                      } 
                  }
              }
          }
    
          return image;
      }
    };

695. 岛屿的最大面积

  • DFS

    class Solution {
    public:
      // i j 的最大岛屿面积
      int dfsMaxArea(vector>& grid, int i, int j){
          // 超越范围了
          if(i>=grid.size() || j>=grid[0].size() || i<0 || j<0) return 0;
          if(grid[i][j] == 1) {
              // 访问过了 变为0
              grid[i][j] = 0;
              // 返回四周的最大岛屿面积
              return 1+dfsMaxArea(grid, i-1, j)+dfsMaxArea(grid, i, j-1)+dfsMaxArea(grid, i+1, j)+dfsMaxArea(grid, i, j+1);
          }
          return 0;
      }
    
      int maxAreaOfIsland(vector>& grid) {
          int maxArea = 0;
          int m = grid.size();
          int n = grid[0].size();
          for(int i=0;i
  • BFS

    class Solution {
    public:
      int maxAreaOfIsland(vector>& grid) {
          int ans = 0;
          for (int i = 0; i != grid.size(); ++i) {
              for (int j = 0; j != grid[0].size(); ++j) {
                  int cur = 0;
                  queue queuei;
                  queue queuej;
                  queuei.push(i);
                  queuej.push(j);
                  while (!queuei.empty()) {
                      int cur_i = queuei.front(), cur_j = queuej.front();
                      queuei.pop();
                      queuej.pop();
                      if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
                          continue;
                      }
                      ++cur;
                      grid[cur_i][cur_j] = 0;
                      int di[4] = {0, 0, 1, -1};
                      int dj[4] = {1, -1, 0, 0};
                      for (int index = 0; index != 4; ++index) {
                          int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                          queuei.push(next_i);
                          queuej.push(next_j);
                      }
                  }
                  ans = max(ans, cur);
              }
          }
          return ans;
      }
    };

Day8 广度优先搜索 / 深度优先搜索

617. 合并二叉树

  • DFS

    class Solution {
    public:
      TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
          if(!root1) return root2;
          if(!root2) return root1;
          TreeNode * newRoot = new TreeNode(root1->val+root2->val);
          newRoot->left = mergeTrees(root1->left, root2->left);
          newRoot->right = mergeTrees(root1->right, root2->right);
          return newRoot;
      }
    };

116. 填充每个节点的下一个右侧节点指针

Day9 广度优先搜索 / 深度优先搜索

542. 01 矩阵

994. 腐烂的橘子

Day10 递归/回溯

21. 合并两个有序链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1) return list2;
        if(!list2) return list1;

        if(list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list2->next, list1);
            return list2;
        }

    }
};

206. 反转链表

  • 用栈实现,注意最后一个node的next需要为nullptr,不然会报错

    class Solution {
    public:
      ListNode* reverseList(ListNode* head) {
          if(!head) return nullptr;
    
          stack stk;
    
          while(head) {
              stk.push(head);
              head = head->next;
          }
          head = stk.top();
          ListNode *cur = head;
          stk.pop();
    
          while(!stk.empty()) {
              cur->next = stk.top();
              cur = cur->next;
              stk.pop();
          }
          cur->next = nullptr;
    
          return head;
      }
    };
  • 递归

    if (head == nullptr || head->next == nullptr) return head;注意顺序,否则会报错

    class Solution {
    public:
      ListNode* reverseList(ListNode* head) {
          // 如果head为空 或者 只剩一下一个元素 就不需要反转了
          if (head == nullptr || head->next == nullptr) return head;
    
          // 递
          ListNode * p = reverseList(head->next);
          // 归
          // 反转
          head->next->next = head;
          head->next = nullptr;
    
          return p;
      }
    };

Day11 递归/回溯

77. 组合

46. 全排列

784. 字母大小写全排列

Day12 动态规划

70. 爬楼梯

198. 打家劫舍

120. 三角形最小路径和

Day13 位运算

231. 2 的幂

191. 位1的个数

暂无评论

发送评论 编辑评论


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