剑指 Offer 53 - II. 0～n-1中缺失的数字（easy） 方法一：二分 方法一：二分 思路：核心思想在于<mark>排序数组中的搜索问题，首先想到二分法解决</mark>，需要注意的是缺失的数字一定是右边子数组的第一个元素，如下图描述。图片源于 class Solution { public int missingNumber(int[] nums) { // 特例 if (nums == nul...

剑指 Offer 06. 从尾到头打印链表（easy） 方法一：暴力法 方法二：辅助栈 方法三：递归法 方法一：暴力法 思路：直接遍历一遍链表，并使用ArrayList记录链表元素。再新建返回数组arrs，反向遍历ArrayList并将值存入arrs返回即可。 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode...

字符与几种基本类型的转换 刷题中，我们经常要将从键盘读取的字符转换成基本数据类型，这个类用于对这些操作的集中处理！ package com.atguigu.exer; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * MyInput.java: Contain the methods for reading int, double, float, boolean, short, byte and * string values ...

数组实现栈 实现栈的方式有两种，一种是数组实现，一种是链表实现。相同之处在于入栈、出栈时间复杂度都为 O(1)。下面是一种数组的实现，支持入栈 push()、出栈 pop()、查看栈顶元素 peek()、判空 isEmpty()、查询栈长度 size()这些基本方法。 import java.util.Arrays; /** * @author roger * @create 2021-06-28 10:47 */ public class MyStack { private int[] storage; // 存放栈中元素的数组 ...

使用Java手动实现布隆过滤器 （1）定义：布隆过滤器是一种来检索元素是否在给定大集合中的数据结构，这种数据结构优点是高效性能好，缺点是一定的错误识别率和删除难度。理论情况下，添加到集合中的元素越多，误报的可能性就越大。 （2）原理：布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。 （3）使用场景：判断元素存在于一个非常庞大的数据集中、防止缓存穿透、垃圾邮箱过滤、黑名单、爬虫URL去重等。 以上描述源自 JavaGuide. 手动实现如下： import java.util.BitSet; import jav...

剑指 Offer 24. 反转链表（easy） 方法一：迭代法 方法二：递归法 方法一：迭代法 思路：迭代法需要三个指针，分别是pre、cur以及nxt，用于顺序遍历链表。初始化时，pre指向空节点(头结点的next指向)，cur指向头结点head，nxt指向head.next，同时由于head.next可能不存在，所以放在循环体中去初始化。迭代过程如下: (1) nxt指向cur.next (2) cur.next指向pre (3) pre移动到cur位置 (4) cur移动到n...

141. 环形链表（easy） 方法一：快慢指针（最优解） 方法一：快慢指针（最优解） 思路：定义fast、slow即快慢双指针，移动步数分别为2和1，如果链表存在环，那它们必然会相遇。当快指针fast到达尾部时，表示并不存在环路。 /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = nul...

剑指 Offer 12. 矩阵中的路径（medium） 方法一：递归 + 回溯 + 剪枝 方法一：递归 + 回溯 + 剪枝 思路：本题提供了一个矩阵，矩阵是一个二维数组，需要我们在二维数组中进行搜索，为了能够覆盖所有的情况，必然要使用两个嵌套for循环。 在搜索过程中，当遇到匹配成功的元素，搜索其下一元素的操作与当前的操作一致，即可以使用递归。 递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在word 中的索引 idx 。 终止条件： 返回 false： (1...

NC93. 设计缓存结构（medium） 方法一：HashMap + Queue（自己写的） 方法一：HashMap + Queue（自己写的） 思路：定义一个HashMap用于存放键值对，定义一个Queue记录存放时的顺序，也可用于更新顺序，定义一个ArrayList存放返回值（后面需要将其转换成数组）。直接遍历二维数组operators： （1）当操作为set，即operators[i][0] == 1时，作以下判断：<1> 当前Queue长度并没有超过k，那直接使用HashM...

NC76. 用两个栈实现队列（easy） 方法一：直接模拟法（自己写的） 方法一：直接模拟法（自己写的） 思路：stack1拿来存值，stack2拿来取值。push方法非常直接，稍微有点曲折的是pop方法，我们需要做判断：（1）stack2还有上一次stack1倒过来的值，而此时pop只需要将stack2中的栈顶元素pop出来就行。（2）当stack2为空，此时需要将stack1新增的值倒过来，再pop就行了。 import java.util.Stack; public class So...

NC105. 二分查找-II（medium） 方法一：递归二分（自己写的） 方法二：纯二分 方法一：递归二分（自己写的） 思路：题目已经给出解题思路：二分查找，但这里需要注意限制条件：首次出现的位置，不可避免地，我们需要递归去二分查找target。当找到时，需要考虑在当前mid的左边可能还有更小的，所有我们需要再递归调用左边。 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指...

NC15. 求二叉树的层序遍历（medium） 方法一：广度优先遍历（自己写的） 方法二：广度优先遍历（LeetCode最优解） 方法一：广度优先遍历（自己写的） 思路：使用一个队列nodes来存放当前层遍历的节点，将根节点放到该队列进行while循环。while中要做两件事：（1）首先是将当前层的值存放到新定义的cur中，用于返回。（2）遍历当前层的节点，并判断当前节点的左子树和右子树，将这层所有节点的子节点放到nxt_level列表中，用于下一层的遍历。将nxt_lev...

NC68. 跳台阶（easy） 方法一：动态规划 方法一：动态规划 思路：最经典的动态规划题，动态规划最重要的就是状态转移方程，具体到这题考虑如下：爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。这就是状态转移方程，再考虑边界条件，也就是初始条件，从第 0 级爬到第 0 级我们可以看作只有一种方案，即 f(0) = 1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1)=1。于是可以写出如下代码： public class Soluti...

NC41. 最长无重复子数组（medium） 方法一：HashSet+滑动窗口 方法二：HashSet+滑动窗口（优化） 方法一：HashSet+滑动窗口 思路：一道滑动窗口题（纯暴力是会超时的，注意看上图的备注信息。），其实很好理解：我们要找最长且无重复的子数组，无重复需要使用HashSet进行去重。要找到最长的，可以使用滑窗的思想去动态地改变长度。有以下情况（1）没有重复数组元素时，right指针一直往右移动，同时更新maxLen和window表。（2）当出现重复数组元...