力扣hot100—二刷
|
力扣Hot100
|

记录二刷力扣hot100，此次二刷主要是再次熟悉思路与常见的方法。用时二周。

常用容器函数对比

速记：只有queue系列能poll、offer、peek；Stack有push、peek；Map用put，其他用add。

双端队列能拿来当Stack用，方法和stack的一致

双端队列的offer等价于offerLast、poll等价于pollFirst、peek等价于peekFirst，从队尾进，从队头出。

容器类型添加元素删除元素获取/查看特点
List/ArrayListadd(e)remove(i), remove(e)get(i)顺序集合，可重复
LinkedListadd(e), addFirst(e), addLast(e)remove(), removeFirst(), removeLast()getFirst(), getLast()双向链表
Stackpush(e)pop()peek()后进先出（LIFO）
Queueoffer(e)poll()peek()先进先出（FIFO）
DequeofferFirst(e), offerLast(e)pollFirst(), pollLast()peekFirst(), peekLast()双端队列
PriorityQueueoffer(e)poll()peek()优先队列（堆）
Setadd(e)remove(e)contains(e)不重复集合
Mapput(k, v)remove(k)get(k)键值对

二分查找模板

二分查找左右边界的模板： 简单记忆：当分支逻辑是 l = mid时，mid的计算就必须 +1向上取整，以避免死循环

ep：1，2，2，2，3，5
//查大于等于target的第一个位置, target=2，目标位置是1
int l = 0, r = n - 1;
while (l < r) {
    int mid = l + r >> 1;
    // 找最早的那个值，nums[mid] >= x时，即使等于目标值，也要继续向左找，所以 r = mid
    if(a[mid] >= x) r=mid;
    else l = mid + 1;
}
​
//查小于等于target的最后一个位置，target等于2，目标位置是3
int l = 0, r = n - 1;
while (l < r)
 {
        int mid = l + r + 1 >> 1;
        if (a[mid] <= x) l = mid;
        else r = mid - 1;
 }

图论中BFS和DFS的使用

DFS套路：进去前设置现场，出来后还原现场

    public void dfs(int[] nums, int depth) {
        if (depth == n) {
            res.add(new ArrayList<>(path));
            return;  // 添加 return
        }
        for (int i = 0; i < n; i++) {  // 直接用 n
            if (!flag[i]) {
                path.add(nums[i]);
                flag[i] = true;
                dfs(nums, depth + 1);
                path.remove(path.size() - 1);
                flag[i] = false;
            }
        }
    }

BFS套路：队列遍历，一层一层，一般问题都是记录次数

import java.util.*;
​
public class BFS {
    public static void main(String[] args) {
        // 1. 构建图 (邻接表): 0->1,2; 1->3; 2->4
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < 5; i++) graph.add(new ArrayList<>());
        graph.get(0).addAll(Arrays.asList(1, 2));
        graph.get(1).add(3);
        graph.get(2).add(4);
        // 2. BFS 核心逻辑
        Queue<Integer> q = new LinkedList<>();
        q.offer(0); // 起点入队        
        while (!q.isEmpty()) {
            int cur = q.poll();
            System.out.print(cur + " "); // 访问节点
            for (int next : graph.get(cur)) q.offer(next); // 邻居入队
        }
    }
}
​

DP额外补充：背包问题

数论

前缀和差分

一维前缀和，一维差分

前缀和：用以快速求出元素组中某段区间的和

原数组: a[1], a[2], a[3], a[4], a[5], …, a[n] 前缀和Si为数组的前i项和：S[i] = a[1] + a[2] + a[3] + … + a[i] 因此，求 [l, r]中的和, 即可以转化为求：S[r] – S[l-1]

二维前缀和：S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j] 因此，求(x1,y1),(x2,y2)矩阵数和，转化为求：S[x2,y2]−S[x1−1,y2]−S[x2,y1−1]+S[x1−1,y1−1]

差分：目的是为了快速处理多次“区间修改”的操作

差分，即为前缀和的逆运算，求前缀和的时候，S[i] = a[1] + a[2] + ... + a[i]，求差分的时候，S[i]变为了a[i]， a[i]变成了b[i]， 即：b[1] = a[1] - a[0]、b[2] = a[2] - a[1]、b[n] = a[n] - a[n-1]

例子：给定区间[l ,r]，让我们把a数组中的[ l, r]区间中的每一个数都加上c,即a[l] + c , a[l+1] + c , a[l+2] + c, + ... + a[r] + c，假若做多次加减操作，最后输出操作后的序列，时间复杂度会过高。

一维差分结论：给a数组中的[ l, r]区间中的每一个数都加上c，只需对差分数组b： b[l]+=c, b[r+1]-= c，最后求时间复杂度为O(1), 大大提高了效率。 差分的最后是还原，通过a[i] = b[i] + a[i-1]，迭代一次还原回操作后的原数组。

    public static void main(String[] args) {
        int n = 5; // 数组长度
        int[] d = new int[n + 2]; // 差分数组
        // 核心操作：区间 [1, 3] 所有元素 +10
        // 逻辑：d[L] += val, d[R+1] -= val
        d[1] += 10;
        d[4] -= 10;
        // 还原：对差分数组求前缀和，直接在原数组上复用
        for (int i = 1; i <= n; i++) {
            d[i] += d[i - 1]; 
            System.out.print(d[i] + " ");
        }
    }

2.26

8题。

  • 两数之和，注意map的用法。
  • 字母异位词分组，排序+哈希，注意字符串的排序需要先转成char[]。           String str = strs[i];
              char[] sc = str.toCharArray();
              Arrays.sort(sc);
              str = new String(sc);
  • 最长连续序列，思路题，用set集合存数字，遍历set，对于每个数v，如果v-1存在就continue，不存在就开始遍历v+1、v+2、更新最长序列。
  • 移动0，第一步把所有非0的都填上，并记录位置，第二步把记录位置到末尾的都填0。
  • 盛水最多的容器，双指针最左最右开始迭代，每次移动一个更矮的。
  • 复杂！！，三数之和，排序，然后根据性质，移动左右两个指针，过程中需要去重。
  • 值得二刷！！，接雨水，类似前缀和，求出从左往右的最大高度和从右往左的最大高度，对于每个位置，其能承的雨水量就是：雨水量=min(左侧最高,右侧最高)−当前高度
  • 无重复字符的最长子串，Set+双指针遍历，从左往右，移动右指针，add到set中；遇到已在set中的，就移动左指针，并且弹出左指针指着的字符，直到不在set中了，再加入并移动右指针。

2.27

7题。

  • 值得二刷！！，找到字符串中所有字母异味词，注意数组比较可以用Arrays.equals(scount, pcount)，用数组来移动窗口，scount的长度是p_len，表示p_len大小的滑动窗口。
  • 和为K的子数组，暴力二重循环。
  • 值得二刷！！，滑动窗口最大值，
    • 暴力法：滑动窗口n次，每一次都遍历窗口k，找出最大的
    • 单调队列，维护一个单调递减的双端队列，队列里存元素下标，队头最大，队尾最小
  • 复杂！！，最小覆盖子串，问到就直接暴力枚举所有子串（同和为K的子数组），然后判断是否可以。
  • 最大子数组和，动态规划，dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
  • 值得二刷！！，合并区间，排序，注意排序的写法Arrays.sort(nums, (a,b)->a[0]-b[0])
  • 值得二刷！！，轮转数组，简单方法就是额外数组；思路方法就是三次反转，先整体反转，再反转前k个，再反转后n-k个。

2.28

6题

  • 值得二刷！！，除了自身以外数组的乘积，计算左侧的乘积和右侧的乘积。res[i] = res[i-1] * nums[i-1];
  • 跳过！！，难！！缺失的第一个正整数，跳过，空间复杂度方法O1的不考虑，不限制空间复杂度很简单。
  • 矩阵置零，把第一行第一列拿来当标记数组，这样就可以做到O(1)空间复杂度，注意一开始特判下第一行和第一列有没有有0的数，有0的数字就flag记录下。
  • 螺旋矩阵，模拟题，模拟四个方向遍历
  • 旋转图像，思路题，四个位置交换，m[i][j] <- m[n-1-j][i] <- m[n-1-i][n-1-j] <- m[j][n-1-i]
  • 搜索二维矩阵||，从左下到右上遍历，思路题。

3.1

14题

链表题，得会创建链表：

public class ListNode{
    int val;
    LstNode next;
    ListNode(int val){
        this.val = val;
        this.next = null
    }
}
  • 相交链表，求出两个链表长度，再让长的先走到和短的长度一样，之后一起走。
  • 值得二刷！！，反转链表，三指针，pre指向null、cur指向头，next记录cur的下一个。
  • 回文链表，控制空间复杂度为O1的话，只能反转后半段再对比，找链表的一半可以用快慢指针。
  • 环形链表，快慢指针，有环必会相遇，无环必会遇到null，能够终止循环。
  • 环形链表2，记住结论，相遇之后，一个从起点，一个从相遇点开始动，再次相遇的地方就是入口。
  • 合并两个有序链表，用一个dummy节点引出来做，就很容易了。
  • 两数相加，模拟题。
  • 值得二刷！！，删除链表的倒数第N个节点，就是遍历出长度，然后找到倒数第N个节点的前驱，后继。然后更改即可。一遍扫描的话，就要用双指针，右指针先走，当右指针到边界的时候，左指针的下一个就是要删除的点。
  • 值得二刷！！，两两交换链表的节点，思路类似反转链表，三指针做法。
  • K个一组反转链表，大模拟题，用dummy哑节点方便做，思路和反转链表差不多，多了一步剪裁出k大小的链表操作。
  • 随机链表的复制，主要是读懂题意，直接顺序创建的话，会不知道random该指向谁，找一个哈希表存旧节点—新节点的映射。 cur = head; while (cur != null) { Node newNode = map.get(cur); // 新节点的关系 藏在旧节点之间 newNode.next = map.get(cur.next); newNode.random = map.get(cur.random); cur = cur.next; }
  • 值得二刷！！，背下来！排序链表，归并排序。三部分：快慢指针找中点并切断链表，递归左右部分，merge合并已排序好的链表。
  • 合并K个升序链表，用优先队列，先把所有的链表的头节点放进去，然后遍历，弹出来的一定是最小的，然后把弹出来节点的next节点放到队列里面。// 用λ表达式定义比较器 简单 不用实现comparable PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val – b.val);
  • 值得二刷！！，LRU缓存，哈希表+双向链表。哈希表的作用是实现O1查找，双向链表的作用是实现O1的移动与删除（最常访问的提到最前头，最晚访问的删除掉）// 双向链表的节点 class LinkedNode{ int key; int value; LinkedNode prev; LinkedNode next; public LinkedNode(){} public LinkedNode(int k1, int v1){ key = k1; value = v1; } }

3.3

7题

层序遍历板子：

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<TreeNode> q = new LinkedList<>();
        if(root != null) q.offerLast(root);
        while(!q.isEmpty()){
            int levelSize =q.size();
            List<Integer> x =new ArrayList<>();
            for(int i = 0; i < levelSize; i++){
                // 注意双端队列当普通队列的用法 offerLast pollFirst
                TreeNode cur = q.pollFirst();
                x.add(cur.val);
                if(cur.left != null) q.offerLast(cur.left);
                if(cur.right != null) q.offerLast(cur.right);
            }
            res.add(x);
        }
        return res;
    }
  • 必会！！，二叉树的中序遍历，DFS，前序遍历、后续遍历、层序遍历！
  • 二叉树的最大深度，DFS
  • 值得二刷！！，翻转二叉树，DFS
  • 值得二刷！！，对称二叉树，DFS，需要一点思路，对比左右子树的值，然后对比左子树的左子树和右子树的右子树，以及左子树的右子树和右子树的左子树值。
  • 值得二刷！！，DFS，二叉树的直径，类似最大深度，得求出左子树的高和右子树的高，返回的是二者之间更高的值+1.
  • 层序遍历，必会。
  • 值得二刷！！，将有序数组转化为二叉搜索树，也是DFS，用递归的方法，二分开数组的左右两侧，每次递归都找出区间的中点作为root，然后继续递归左右两侧的值。 TreeNode cur = new TreeNode(nums[mid]); cur.left = dfs(nums, l, mid-1); cur.right = dfs(nums, mid+1, r);

3.4

4题

  • 值得二刷！！，验证二叉搜索树，递归DFS，传入dfs(root, Long.MIN_VALUE, Long.MAX_VALUE)，比较左右两边的值是否满足，不满足则返回false，满足则返回递归dfs(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
  • 二叉搜索树中第K小的树，中序遍历
  • 二叉树的右视图，层序遍历，每层的最后一个加入结果集合中。
  • 值得二刷！！，二叉树展开为链表，展开为先序遍历，需要画图理解， while(root != null){ if(root.left != null){ 具体的接入操作 } root = root.right; }

3.5

4题

  • 值得二刷！！，从前序与中序遍历序列构造二叉树，找出前序遍历在中序遍历的位置，递归处理， root.left = handler(preorder, inorder, l1+1, l1 + leftNum, l2, preLocation-1); root.right = handler(preorder, inorder, l1 + 1 + leftNum, r1, preLocation + 1, r2);
    • 额外：前序+后续构造二叉树，待做
  • 背！！，DFS，路径总和III
  • 值得二刷！！，二叉树的最近公共祖先，递归，分情况讨论：
    • p、q在root的子树中，且p、q分别属于root的不同侧子树，
    • p是root，q在p的子树中
    • q是root，p在q的子树中
    // 如果root是p或者q 直接返回就是结果 如果是空也返回 if(root == null || root == p || root == q) return root;
  • 值得二刷！！，二叉树的最大路径，四种选择：
    • 我自己就是一条路径
    • 只跟左子节点合并成一条路径
    • 只跟右子节点合并成一条路径
    • 以自己为桥梁，跟左、右子节点合并成一条路径
    // 当前节点的情况 有4种选择 判断出最大的那种 // 三种情况比最大的：仅本节点，本节点+左子节点，本节点+右子节点 int res = Math.max(node.val, node.val + Math.max(left, right)); // 一种特殊情况 即以本节点为桥 连接左右子节点（不考虑本节点的父节点） int bridge = node.val + left + right; // 维护出最大的 要么是pathSum本身 要么是特殊情况 要么是前三种情况中最大的 pathSum = Math.max(pathSum, Math.max(res, bridge)); return res;

3.6

图论跳过，

回溯，7题

回溯题的套路感觉都是：

  • 找到递归终止条件
  • 从上一个递归退出后需要恢复现场。
  • 值得二刷！！，全排列，DFS，注意遍历每一个位置，当没被选过的时候，添加到路径队里。 if(path.contains(nums[i])){ continue; } // 没被选过 添加 path.add(nums[i]); dfs(nums); // 还原现场 path.remove(path.size() – 1);
  • 值得二刷！！，子集，位运算，枚举子集，即每个数有两种情况，选出或者不选出，n个数有2^n种情况。
  • 电话号码的字母组合，同全排列，
  • 组合总数，递归，同样的找到终止条件，恢复现场。 res.add(new ArrayList<>(path)); res.add(path); 结果是不一样的， 后者的话 res里存的是同一个List对象的引用
  • 值得二刷！！，括号匹配， // 参数分别为：当前构造的字符串, 能使用的左括号数目, 能使用的右括号数 public void dfs(String str, int left, int right)
  • 单词搜索，图的DFS方法，较为简单
  • 值得二刷！！，难！分割回文串，关键是这个切割方式。

3.7

7题

N皇后+二分查找

  • N皇后，关键是建模3个判断数组，当前列，当前正斜线y = x + b 所以 b = y -x，当前反斜线y = -x + b 所以 b = y + x。

二分查找左右边界的模板： 简单记忆：当分支逻辑是 l = mid时，mid的计算就必须 +1向上取整，以避免死循环

  • 搜索插入位置，用第一个二分模板。
  • 搜索二维矩阵，找到最后一个不大于目标数的那一行，再对那一行进行二分查找。也可以用思维方式，从左下角出发，比target大就向上走，反之向右走。更简单。
  • 在排序数组中查找元素的第一个和最后一个位置，同二分模板。
  • 值得二刷！！，搜索旋转排序数组，即便是旋转后的数组，也是有序的，nums[0] <= nums[mid]表示左边有序， // 左边有序 if(nums[0] <= nums[mid]){ if(nums[0] <= target && target < nums[mid]){ r = mid – 1; }else{ l = mid + 1; } }
  • 值得二刷！！，寻找旋转排序数组中的最小值，同搜索旋转排序数组，也是区分左右两边的有序性判断性质。如果左边有序，最小值肯定是最左的，如果右边有序，最小值肯定是nums[mid].
  • 难！！，寻找两个正序数组的中位数，跳过。

3.8

8题

栈+堆

  • 有效的括号，栈匹配，注意双端队列的写法。
  • 最小栈，双栈法，一个正常栈和一个辅助栈，两者的size一致，辅助栈存着当前栈里的最小值。
  • 值得二刷！！，字符串解码，递归+模拟，递归构造一个StringBuilder，递归的终止条件是匹配到]，递归的中间处理数字和字符串，注意数字可能会是多位数，所以要额外处理。
  • 值得二刷！！，每日温度，单调栈，最直观的思路是二重循环查找，但是时间复杂度过高。引入单调栈存储已经遍历过元素的信息。 for(int i = 1; i < n; i++){ // 当前温度大于栈顶温度 就更新栈顶的对应数组结果 出栈，并将新温度放入栈顶 while(!dq.isEmpty() && temperatures[i] > temperatures[dq.peekLast()]){ res[dq.peekLast()] = i – dq.peekLast(); dq.pollLast(); } dq.offerLast(i); }
  • 值得二刷！！，柱状图中最大的矩形，单调栈，矩形的宽度由该柱子向左右延伸到第一个比它矮的柱子决定，问题转化为：对每个柱子，找到左右边界。维护一个单调递增栈，当遇到栈顶大于遍历的下标的时候，说明找到了右侧边界，左边界是出栈后的新栈顶，右边界是当前索引-1。
  • 值得二刷！！，数组中的第K个最大元素，维护优先队列，复杂度是O(nlogn)，使用基于快速排序的选择方法能优化成O(n)。 快速排序的核心是：迭代选中的某个数在其有序列中的下标位置，因此可以每次排序完毕后，查看下是不是符合第k个。可以改进快速排序算法来解决这个问题：在分解的过程当中，我们会对子数组进行划分，如果划分得到的 q 正好就是我们需要的下标，就直接返回 a[q]；否则，如果 q 比目标下标小，就递归右子区间，否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间，提高了时间效率。这就是「快速选择」算法。
  • 前 K 个高频元素，维护一个map和小顶堆。
  • 数据流的中位数，思路题，用一个小顶堆和一个大顶堆维护，小顶堆存最大的那一半数，大顶堆存最小的那一半数。

3.9

DP，7题。

  • 爬楼梯， dp[i] = dp[i-1] + dp[i-2];
  • 杨辉三角，把它左对齐就比较好做了。row.add(res.get(i-1).get(j-1) + res.get(i-1).get(j));
  • 打家劫舍，dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
  • 值得二刷！！，完全平方数，dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
  • 零钱兑换，同完全平方数的思路，填充最大值，然后枚举比较更新出最小的dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
  • 值得二刷！！，单词拆分，这题的难点一个是建模的思路，第二个就是集合和String类的函数使用，
    • 定义状态：dp[i]表示字符串 s的前 i个字符（即 s[0..i-1]）是否可以被拆分成字典中的单词。
    • dp[j] && wordSet.contains(s.substring(j, i))
    • 这题主要是两重循环枚举i、j，和传统的dp不太一样。
  • 值得二刷！！，最长递增子序列，定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，注意 nums[i] 必须被选取。 for (int i = 1; i < nums.length; i++) { // dp[i]表示以第i个数字为结尾的最递增子序列的长度 dp[i] = 1; for (int j = 0; j < i; j++) { // i 大于 j 可以更新最长的上升子序列 if (nums[i] > nums[j]) { // dp[i] = Max(dp[i], j的最长上升子序列+1) dp[i] = Math.max(dp[i], dp[j] + 1); } } maxans = Math.max(maxans, dp[i]); }总结：感觉这种字符串、序列的，遍历基本上就是双重循环，外层固定i，内层从0到i遍历找特征。

3.10

DP，8题。

  • 乘积最大子数组，注意维护两个DP数组（也可以用滚动变量），一个最大的值，一个最小的值。根据遍历的当前值大于0或者小于0来判断不同情况。
  • 值得二刷！！，分割等和子集，看作01背包问题。 dp[i][j]为：考虑前 i个物品（数组元素），能否恰好装满容量 j。 if (j >= num) { // j>=num 则dp[i][j]= 要么不拿第i个物品凑成j个数；要么拿第i个物品凑成j个数 dp[i][j] = dp[i-1][j] || dp[i – 1][j – num]; }else{ // j 小于num 只能等于不选第i个物品凑成j个数的 dp[i][j] = dp[i-1][j]; }
  • 值得二刷！！，模拟题，最长有效括号，这题用模拟更简单，维护一个栈，对于遇到的每个 (，将它的下标放入栈中
    • 对于遇到的每个 )，我们先弹出栈顶元素表示匹配了当前右括号：
    • 如果栈为空，说明当前的右括号为没有被匹配的右括号，把当前的)的下标，放入栈中更新
    • 如果栈不为空，当前右括号的下标减去栈顶元素下标，即为以该右括号为结尾的最长有效括号的长度
    • 栈预先存一个下标-1
  • 不同路径，二维动态规划，先预填充dp[i][0]和dp[0][i]
  • 最小路径和，同上一题，dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];简单题，
  • 值得二刷！！，最长回文子串，直接字符串处理更简单，中心回溯法。
    • 遍历每个索引i： 以 i为中心向左右扩展，得到奇数长度回文。 以 i和 i+1之间的空隙为中心向左右扩展，得到偶数长度回文。// 中心扩散 因为不知道回文串是奇数还是偶数，都枚举出来 int len1 = expandAroundCenter(s, i, i); // 奇数长度 int len2 = expandAroundCenter(s, i, i + 1); // 偶数长度 private int expandAroundCenter(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left–; right++; } return right – left – 1; // 回文长度 }
  • 值得二刷！！最长公共子序列，枚举子序列1和子序列2，dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列的长度。char c1 = text1.charAt(i-1); char c2 = text2.charAt(j-1); if(c1 == c2){ // 如果text1的第i个 == text2的第j个 那么dp[i][j] 等于前一序列+1 dp[i][j] = dp[i-1][j-1] + 1; }else{ // 不等的话 到目前的最长公共子序列 肯定只等于二者之一了 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); }
  • 值得二刷！！，编辑距离， 三种操作，表示三种dp状态转移，
    • dp[i][j]：将 word1的前 i个字符转换成 word2的前 j个字符所需的最少操作数。
    • 如果word1的i词和word2的j词相等 就不需要编辑：dp[i][j] = dp[i - 1][j - 1];
    • 替换 就相当于匹配 i-1和j-1的次数 再加上替换这一次的操作：replace = dp[i - 1][j - 1] + 1;
    • i词和j词不等 i删除一个词，相当于删除 word1的第 i个字符（即 word1[i-1]），然后让剩下的部分去匹配 word2。删除操作额外+1：delete = dp[i - 1][j] + 1;
    • i词和j词不等 要加一个词 相当于j删一个词：insert = dp[i][j - 1] + 1;
    • 最后：dp[i][j] = Math.min(replace, Math.min(delete, insert));

3.11

贪心，4题

  • 买卖股票的最佳时机，迭代每天的价格，更新当前遇到的最小价格和当前能得到的最大利润。
  • 跳跃游戏，思路题， for(int i = 0; i < nums.length; i++){ // 如果当前能到的最大值 都到不了i了 直接return false if(reach < i) return false; // 更新能到达的最大值 reach = Math.max(reach, i+nums[i]); }
  • 跳跃游戏 II， for (int i = 0; i < length – 1; i++) { // 更新当此跳跃能跳到的最远地方 maxPosition = Math.max(maxPosition, i + nums[i]); // 如果已经到达了上一次跳跃的最远点 说明还得跳 step++ 并且要更新现阶段能到的最远起跳点 if (i == end) { end = maxPosition; steps++; } }
  • 划分字母区间，思路：把每个字母的第一个出现下标和最后一个出现下标摘出来。迭代每一个片段。 for(int i = 0; i < s.length(); i++){ end = Math.max(Last[s.charAt(i) – ‘a’], end); // 如果下标i等于end了 说明i上的这个字符到头了 if(i == end){ res.add(end – start + 1); start = end + 1; } }

3.13

技巧，5题

  • 只出现一次的数字，异或^
  • 多数元素，记住技巧，摩尔投票法。当前的值和上一个值一样就+1 不一样就-1 为0就重新开始 最后结果肯定是众数
  • 颜色分类，冒泡排序，遍历两次，第一轮遍历把0全部放最前面，第二次遍历把1全部放最前面。
  • 值得二刷！！，下一个排列，建议用笔画例子，找规律题，例如12543，找到2和3，交换成为13542，然后反转5和2的区间，变成13245，即为答案。
    • 以上面例子为例，找出2，其实就是从后往前遍历，找出a[i]<a[i+1]的那个数字下标i
    • 以上面例子为例，找出3，其实就是找出从后往前遍历，a[j]>a[i]的那个数字下标j，
    • 最后交换i与j，并反转[i+1,n)之间的内容，即为答案。
  • 值得二刷！！，寻找重复数，用环形链表思想，以0开始，i->nums[i]，同时启用快慢指针，如果有重复数，肯定能成环，然后再用环形链表2的方法，拿到成环的入口节点。

3.16

图论4题

  • 岛屿数量，dfs，遍历每个位置，当遇到为1的时候，就DFS把整块岛屿染成0
  • 腐烂的橘子，实际上就是求腐烂橘子到所有新鲜橘子的最短路径。 用层序的BFS，每一层向外迭代，round++，即时间+1。
  • 值得二刷！！，课程表，拓扑排序，记录访问过的课程数目和总的课程数目，如果相等，说明是可以完成课程的。
    • 队列（用以遍历拓扑图的节点）、哈希表（每个节点的后续课程）、数组（记录每个节点的入度情况）队列中的元素为入度为0的课程，每次迭代取出一个入度为0的课（表示这门课修完了），并维护其后置课程（后置课程的入度-1）
  • 值得二刷！！，实现 Trie (前缀树)
    • 前缀树是一种特殊的多叉树，它的 TrieNode 中 chidren 是一个大小为 26 的一维数组，分别对应了26个英文字符 a~z，也就是说形成了一棵 26叉树。前缀树的结构里面存储了两个信息：
      • isWord 表示从根节点到当前节点为止，该路径是否形成了一个有效的字符串
      • children 是该节点的所有子节点。
    • 在构建前缀树的时候，按照下面的方法：
      • 根节点不保存任何信息；
      • 关键词放到「前缀树」时，需要把它拆成各个字符，每个字符按照其在 a ~ z 的序号，放在对应的 chidren 里面。下一个字符是当前字符的子节点。
      • 一个输入字符串构建「前缀树」结束的时候，需要把该节点的 isWord 标记为 true，说明从根节点到当前节点的路径，构成了一个关键词。
class Trie {
    public Trie[] children;
    public boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            int index = c - 'a';
            if(node.children[index] == null){
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = this;
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            int index = c - 'a';
            if(node.children[index] == null) return false;
            node = node.children[index];
        }
        if(node.isEnd == false) return false;
        else return true;
    }
    
    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.isEmpty()) return false;
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            int index = c - 'a';
            if (node.children[index] == null) return false;
            node = node.children[index];
        }
        return true;  // 只要前缀路径存在即可
    }
}

值得二刷
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

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

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇

                    

                    
			        推荐文章
		            

		            

							
剑指offer67题-No16.合并两个有序链表

							
							

							
剑指offer67题-No35.数组中的逆序对

							
							

							
剑指offer67题-No65.矩阵中的路径

							
							

							
剑指offer67题-No6.旋转数组中的最小数字

							
							

							
剑指offer67题-No63.数据流中的中位数

							
							

							
剑指offer67题-No25.复杂链表的复制

							
							

							
剑指offer67题-No26.二叉搜索树与双向链表

							
							

							
剑指offer67题-No24.二叉树中和为某一值的路径(二)

							
							

							
剑指offer67题-No64.滑动窗口的最大值

							
							

							
力扣hot100—双指针 4题