- 博客(137)
- 收藏
- 关注
RSS订阅原创 LeetCode ---- 456、132模式
题目链接思路：132模式的数字，只要随意找出一组，即可返回以3为标准进行判断，这里的1用每个数字及它之前位置的最小值来代替，然后使用栈来判断是否出现了2首先，使用一个min数组来记录原始数组中每个位置及其之前位置的最小值，也就是找到了1使用栈，从后向前进行遍历数组，位置记为 i1）若 min[i] == nums[i]，则以这个数字结尾是不能出现132模式的，直接跳过2）若 min[i] < nums[i]，则当前数字可以作为132模式中的3，在此基础上寻找2（1）栈不
2020-09-20 21:09:46
106
原创 LeetCode ---- 402、移掉K位数字
题目链接思路：要使得移掉K位数字后，剩下的数字最小，需要从头开始移除掉最大的K个元素，这K个元素都满足：比后面一位元素大，即在原始数字中呈现的是逆序状态，需要将其删除使用单调栈来进行删除，栈内满足栈底到栈顶从小到大排列从头开始遍历所给数字1）若当前数字比栈顶数字大或等于，则压入栈中；2）若当前数字比栈顶数字小，则出现了逆序，需要将栈顶元素弹出，直至栈顶元素小于等于当前数字为止，弹出的过程，也就是删除元素的过程，一共需要删除K个元素，所以当一共弹出了K个元素后，就不需要再弹出任何元素了
2020-09-16 22:34:19
107
原创 LeetCode ---- 394、字符串解码
题目链接思路：使用栈来求解准备两个栈，分别存储“[” 前面的数字 和 “[”与“]”之间的字符串。从头开始遍历，遇到数字压入数字栈中，遇到字符串压入字符串栈中，遇到“]”时，弹出一个数字弹出一个字符串，进行拼接之后再次压入字符串栈中，最终全部出栈后拼接得到结果。这样做是为了求解所给字符串中最内部的“[”与“]”之间包含的字符串，从最内层一层一层向外进行瓦解整个字符串对于字符串"3[a2[bc]]"，从头开始遍历，首先将3入numStack，遇到“[”，将数字前面的字符串“a”压入st
2020-09-15 20:45:43
136
原创 LeetCode ---- 199、二叉树的右视图
题目链接思路：用层次遍历解决每一层的最后一个节点即为这棵二叉树的右视图 public List<Integer> rightSideView(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) { return res; } // 使用队列来存放遍历节点
2020-09-06 15:18:42
80
原创 LeetCode ---- 187、重复的DNA序列
题目链接思路：利用HashSet来判断是否出现了多次从头开始遍历字符串，每次截取字符串中连续的10个字符，若之前碰到过，则说明这个字符串出现了不止一次，将这个字符串加入到结果集中最终，遍历结束后将结果返回 public List<String> findRepeatedDnaSequences(String s) { if (s == null || s.length() <= 10) { return new Arra
2020-09-04 20:18:18
58
原创 LeetCode ---- 173、二叉搜索树迭代器
题目链接思路：题目要求的迭代器方法next()返回的是二叉搜索树中下一个最小的元素对于二叉搜索树来说，它的中序遍历结果是一个升序序列，那么先对二叉搜索树进行先序遍历后，得到的结果我们存在队列中，每次调用next()方法时，从队列的头部弹出一个元素返回，这个元素就是当前二叉搜索树中下一个最小的元素，调用hasNext()时，直接判断队列是否为空即可。 class BSTIterator { private TreeNode root; private D
2020-09-03 21:45:45
87
原创 LeetCode ---- 166、分数到小数
题目链接思路：为了计算方便，判断分子分母是否为一正一负，用来标记结果为正或负接下来，对原始的分子分母进行向上转型为long类型（避免取绝对值时发生溢出），并且取绝对值对得到的long类型的分子分母开始计算，计算时，需要根据前面判断的正负来添加运算结果的符号，并且还需要判断是否出现了循环小数出现循环小数时，说明之前已经出现了相同的小数，这里用一个map记录已经出现的小数和他们出现在整个小数部分的位置，便于在后面出现循环小数时，进行添加括号的操作。 public String f
2020-09-02 20:25:08
70
原创 LeetCode ---- 165、比较版本号
题目链接思路：使用String类的split方法，将版本号以分隔符“.”进行切分，得到版本号字符串数组接下来开始对两个版本号字符串数组进行遍历比较，在比较每一个字符串时，将其转为int类型会自动忽略掉前导0 public int compareVersion(String version1, String version2) { String[] v1 = version1.split("\\."); String[] v2 = version2.sp
2020-09-01 20:37:38
94
原创 LeetCode ---- 162、寻找峰值
题目链接思路：注意峰值定义：峰值元素是指其值大于左右相邻值的元素。即，只要出现一个数大于其左右相邻值的元素，即可返回。由于num[-1]=num[n]=负无穷，所以在遍历数组之前，可以对数组的开头和结尾进行判断，看是否满足峰值的定义之后，对数组进行二分查找，寻找符合峰值定义的元素在二分查找时，中间元素不满足峰值定义时，1）中间元素小于前一个元素，那么左边部分一定存在峰值元素，去左边查找2）中间元素大于前一个元素并且小于后一个元素时，那么右边部分一定存在峰值，去右边查找
2020-08-31 19:39:12
76
原创 LeetCode ---- 153、寻找旋转排序数组中的最小值
题目链接思路：题目所给的数组是通过对排序数组在某个位置进行旋转得到的，那么通过判断数组的0位置的元素和等于最后一个位置的元素的大小关系可以对问题进行分类1）若出现0位置元素小于最后一个位置的元素，则说明这个数组旋转过后仍然是升序数组，则0位置的元素就是最小元素2）若出现0位置元素大于等于最后一个位置的元素，则说明这个数组以某一个位置进行了旋转，数组由两部分有序的子数组组成。接下来，使用二分法来进行查找，①若中间的数字比右边的数字大，则说明数组中间往前的数组中肯定不存在整个数组的最小值，然
2020-08-28 20:33:45
57
原创 LeetCode ---- 151、翻转字符串里的单词
题目链接思路：先将字符串前后空格去除掉，然后再对整个字符串进行翻转，得到结果后，再以空格为分隔符，切分出每个单词，对每个单词分别进行翻转，再将翻转后的每个单词进行拼接，即可得到最终结果。例如：原字符串："a good example "1、去除掉前后空格："a good example"2、翻转整个字符串："elpmaxe doog a"3、切分出单个单词："elpmaxe"、"doog"、"a"4、对单个单词进行翻转之后拼接："example good a"代码
2020-08-28 19:49:47
94
原创 LeetCode ---- 150、逆波兰表达式求值
题目链接思路：这是非常经典的栈的应用题，讲数据结构的书上都会涉及到这道题目对于逆波兰表达式，简单说就是先写出要进行加减乘除的两个数字，再写出他们的运算符号如：1 + 2，逆波兰表达式为 1 2 +解这道题，需要使用一个栈来辅助计算从左到右遍历逆波兰表达式，遇到数字压入栈中，遇到符号就从栈中弹出两个数字，然后进行计算，计算完成之后再次压入栈中，当逆波兰表达式遍历结束，栈中剩余的唯一数字即为最终结果 public int evalRPN(String[] tokens) {
2020-08-27 20:38:10
63
原创 LeetCode ---- 148、排序链表
题目链接思路:使用归并排序。与数组的归并排序一致，都是将排序的部分分为两部分，然后对这两部分再进行归并排序，最后将有序的两个部分进行归并整合。将链表用快慢指针分为两部分，然后对这两部分分别进行归并排序，最后对这有序的两部分进行整合。形成一个递归过程 public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head;
2020-08-27 20:29:23
49
原创 LeetCode ---- 147、对链表进行插入排序
题目链接思路：数组的插入排序需要每次从排好序的尾部开始与当前元素进行比较，但单链表无法反向遍历，只能每次都从头开始逐个遍历节点。每次从链表上取下来一个节点，在当前已排好序的链表中进行查找比它大的节点，并记录这个节点的前一个节点，然后将此节点插入其中即可。 public ListNode insertionSortList(ListNode head) { if (head == null || head.next == null) { retu
2020-08-26 20:57:44
84
原创 LeetCode ---- 146、LRU缓存机制
题目链接思路：缓存问题，肯定需要使用Map又要求需要每次在缓存容量达到最大值后，删除最久未使用的，那么需要使用一个队列来维持秩序使用Map来存储key和value，使用Queue依据每个缓存使用频率来维护缓存之间的顺序每次get时，如果map中存在这个key，那么就返回它，但是这里还需要注意一下，get这个key时，说明这个key这是最新被使用的，需要更新它在Queue中的位置。每次put时，如果map中存在这个key，那么覆盖原始key对应的value，但是这里也需要注意一下，pu
2020-08-26 20:48:01
67
原创 LeetCode ---- 144、二叉树的前序遍历
题目链接解法一：递归解法。根据二叉树前序遍历的步骤（当第一次遇到该结点时，就访问该节点，之后访问该节点的左子树和右子树），可以直接写出二叉树前序遍历的递归解法 // 使用成员变量来进行结果的存储 List<Integer> res = new ArrayList<>(); public List<Integer> preorderTraversal(TreeNode root) { if (root == null)
2020-08-24 21:34:05
60
原创 LeetCode ---- 143、重排链表
题目链接思路：将链表一分为二，对半切开后，将后半部分的链表进行翻转，翻转过后，对这两个部分的链表从头开始遍历，并进行拼接，拼接时，第一部分的链表的每一个节点后面都需要拼接一个第二部分的链表例子：原始链表1->2->3->4->5对半切开后，得到1->2->34->5对后半部分进行翻转1->2->35->4最后，进行拼接合并1->2->3 -> 1->5->
2020-08-21 20:44:59
100
原创 LeetCode ---- 142、环形链表 II
题目链接思路：采用双指针准备一个快指针fast，一个慢指针slow，快指针一次走两步，慢指针一次走一步初始时，快指针fast位于头节点的下一个节点，慢指针slow位于头节点fast节点和slow节点同时开始向后走，若存在环，则一定会有一个时刻fast和slow指向同一个节点。若不存在，则最终fast走到null或者fast.next为null若存在环，此时，slow和fast都位于环上开始寻找第一个入环点：寻找入环点的思路是：环的长度 + 未形成环的长度 = 链表总长度，第一
2020-08-20 21:03:20
87
原创 LeetCode ---- 139、单词拆分
题目链接思路：动态规划dp[ i ]表示 s 的前 i 个字符组成的单词是否可以用空格拆分成若干单词后，这些单词都在wordDict中存在状态转移方程为 dp[ i ] = dp[ j ] && isExist(s[ j...i - 1])解释一下状态转移方程：对于前 i 个字符 s[0....i -1]，要检查它是否满足题意，则需要从头开始对s[0...i-1]进行拆分检查，检查时，用 j 来表示拆分的位置，对于s[ 0...j-1 ]，前面已经检查过了，用dp[ j.
2020-08-18 20:47:36
54
原创 LeetCode ---- 138、复制带随机指针的链表
题目链接思路：先将每个节点都复制一遍，复制好的节点插入到原节点的next位置如：原链表，此处先省略random指针1->2->3->4->null复制后，用1'代表1的复制节点1->1'->2->2'->3->3'->4->4'->null接下来，开始复制random指针对于每一个新复制的节点，它的random指向应为 对应的原始节点的random节点的next节点如： ——————————
2020-08-18 20:14:49
49
原创 LeetCode ---- 137、只出现一次的数字 II
题目链接思路：只有一个数字出现了一次，其余数字都出现了三次，那么对于每一个数的二进制表示，若这个数字出现了3次，则它二进制中的每一位也都出现了3次int类型是32位，那么通过遍历数组中数字的每一位出现次数是否是3的倍数即可判断出 只出现一次的数字在这一位上是否是1，若这一位出现1的次数为3的倍数，则说明这一位上 只出现一次的数字 为0，否则为1 public int singleNumber(int[] nums) { int result = 0;
2020-08-17 20:34:44
43
原创 LeetCode ---- 134、加油站
题目链接思路：遍历一遍数组，记录每到一个位置时油箱里剩余的油量，通过剩余油量就可以判断出能否环绕一周并且判断出起点位置剩余的油量 += 每个位置的储量量 - 走到下一个位置需要消耗的油量即：remain += (gas[i] - cost[i])为了记录起点位置，用start记录起点，初始值为0，还需要另一个参数run来进行判断，记录的仍然是剩余的油量，当这个变量从i走到 i+1之后小于0时，说明从位置 i 不能走到位置 i + 1，那么起点需要变为 i + 1，此时还需要将run进行清
2020-08-17 20:23:46
46
原创 LeetCode ---- 133、克隆图
题目链接思路：采用广度优先搜索来对图进行深拷贝。由于是无向图，那么为了避免从A遍历到B，再从B遍历到A的这种情况发生，需要对遍历过的节点进行标记，这里我们使用Map进行标记即可。使用一个队列来存放节点，使用一个Map来存放每一个节点（key），这个节点的拷贝（value），这个Map也可以用于判断节点是否已经访问过。对于队列中的每一个节点，弹出时，若之前没有访问过它的邻居，那么将这个节点的邻居作为key，重新拷贝一个这个节点作为value，放入到Map中。并且将这个节点的邻居加入到队列中
2020-08-12 21:43:04
63
原创 LeetCode ---- 130、被围绕的区域
题目链接思路：题目要求将被 x 包围住的 o 改为 x，且被填充的 o 不能位于边界处。若有o不在边界，但却与内部的 o 相连，则不能被填充那么，在填充之前，需要将边界上的o与其相连的o进行标记，以免被误填充标记时，需要对区域的四条边界都进行深度优先搜先，找到与边界的o相连的o进行标记这里，可以使用除了o和x之外的任何字符来对o进行标记除了标记的o之外，剩余未被标记的o即为需要被填充的o再次遍历，将未标记的o用x填充，将标记号用o填充 public void solv
2020-08-11 21:39:30
114
原创 LeetCode ---- 129、求根到叶子节点数字之和
题目链接思路：使用先序遍历求解。当遍历到节点cur时，1）cur节点为空，直接返回02）cur节点不为空，加上cur节点之后的和为 sum = sum * 10 + cur.val，sum为累加到cur的父节点时的总和3）当cur节点不为空，且cur节点为叶子节点时，将计算后的sum直接返回。4）遍历cur节点左子树，cur节点右子树，将它们的和返回，作为cur节点这棵子树的最终和先序遍历中，对每一个节点均进行上述操作，最终将得到答案。举例： 1 / .
2020-08-11 21:22:15
64
原创 LeetCode ---- 127、单词接龙
题目链接思路：使用广度优先搜索BFS。准备一个队列来存储可接龙的单词。为了避免形成环路，准备一个boolean数组来记录当前单词是否已经访问过对当前队列中的每一个元素都进行下列操作1、当队列中有元素时，弹出对头元素2、对弹出的元素，在所给字典中进行寻找它的可接龙的单词，并将其加入到队列中3、当在第二步寻找的过程中，找到了endWord，那么遍历结束 public int ladderLength(String beginWord, String endWord, Li
2020-08-09 22:36:32
53
原创 LeetCode ---- 120、三角形最小路径和
题目链接思路：可以发现，每次走一步都依赖于上一步的选择，最终要选择从顶点走到最后一行 和 最小的路径采用动态规划，构建一个数组来存储每次选择走到当前节点的最小路径和。代码以及注释已完善，如下： public int minimumTotal(List<List<Integer>> triangle) { if (triangle == null || triangle.get(0) == null || triangle.get(0).si
2020-08-06 21:47:37
66
原创 LeetCode ---- 117、填充每个节点的下一个右侧节点指针 II
题目链接思路：解法一：使用层次遍历来进行求解，当遍历到每一层时，这一层中的节点（除了最后一个节点）的next指针均指向同一层中的下一个节点，也就是next指向队列中的下一个元素。 public Node connect(Node root) { if (root == null) { return root; } Queue<Node> queue = new LinkedList<>()
2020-08-03 21:40:17
101
原创 LeetCode ---- 116、填充每个节点的下一个右侧节点指针
题目链接思路：对每一个节点来说，它的左孩子的next指针需要指向它的右孩子如果当前节点的next指向不为空，则需要将它的右孩子的next指向它的next指向节点的左孩子使用先序遍历处理整个流程举例： 1 / \ 2 5 / \ \3 4 6处理流程如下： 处理根节点 处理节点2 节点2next不为空 处理节点5 1 1
2020-07-31 21:02:28
102
原创 LeetCode ---- 114、二叉树展开为链表
题目链接思路：展开的过程即为 TreeNode last = null; public void flatten(TreeNode root) { if (root == null) return; flatten(root.right); flatten(root.left); root.right = last; root.left = null; las
2020-07-31 20:41:39
68
原创 LeetCode ---- 113、路径总和 II
题目链接思路：采用深度优先遍历来解。需要尝试每一种可能，如果在遍历尝试的过程中，遇到了一个节点是叶子节点且从根节点到这个节点的当前路径的和等于目标值，那么将其加入到最终结果中，对于每一个节点，都需要分别尝试它的左子树和右子树。例如： sum = 22上面这棵二叉树中，根节点为5，从根节点开始，向下进行尝试先尝试左子树（也可以先右子树）红色路径（5-4-11-7）上的总和为27，不符合条件，再看11的右子树红色路径（5-4-11-2）上的总和为22，符合条件...
2020-07-27 21:36:53
71
原创 LeetCode ---- 109、有序链表转换二叉搜索树
题目链接思路：先将单链表的所有节点值存入数组中，由于单链表本身保持升序，那么得到的数组也一定是升序状态，剩下的操作就变成了利用有序数组构造二叉平衡搜索树了接下来利用这个数组去构造二叉平衡搜索树，每次取数组可选范围内的中间位置为根节点，在其左边为左子树，右边为右子树递归进行查找添加即可。 public TreeNode sortedListToBST(ListNode head) { if (head == null) { return nu
2020-07-24 21:46:47
44
原创 LeetCode ---- 106、从中序与后序遍历序列构造二叉树
题目链接思路：与105题题解类似后序遍历为 左右根，中序遍历为 左根右在后序遍历中找到根节点，中序遍历中找到根节点的位置，中序遍历中根节点左边为左孩子，右边为右孩子，利用上面的性质，我们可以进行递归查找根节点，然后进行拼接即可后序：3 4 2 6 5 1中序：3 2 4 1 5 6后序中根节点为 1，中序中 3 2 4为 1 的左孩子，中序中 5 6 为 1 的右孩子后序中左孩子前序序列为 3 4 2，中序为 3 2 4，2为根节点，3为左孩子，4为右孩子后序..
2020-07-22 21:33:09
70
原创 LeetCode ---- 105、从前序与中序遍历序列构造二叉树
题目链接思路：前序遍历为 根左右，中序遍历为 左根右，那么前序遍历序列中的第一个节点即为整棵树的根节点，在中序遍历序列中找到根节点，在中序遍历中根节点的左侧全部都是根节点的左孩子，右侧全部都是根节点的右孩子利用上面的性质，我们可以进行递归查找根节点，然后进行拼接即可例如：前序：1 2 3 4 5 6中序：3 2 4 1 5 6前序中根节点为 1，中序中 3 2 4为 1 的左孩子，中序中 5 6 为 1 的右孩子前序中左孩子前序序列为 2 3 4，中序为 3 2 4，2为
2020-07-21 21:19:26
85
原创 LeetCode ---- 103、二叉树的锯齿形层次遍历
题目链接思路：利用102题二叉树的层次遍历的思路来解这道题在102题解的基础上，使用一个boolean类型的变量来控制每次应该从左向右输出还是从右向左输出初试时，从左向右输出，每遍历一层，方向变化一次 public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(
2020-07-20 23:00:07
55
原创 LeetCode ---- 102、二叉树的层序遍历
题目链接思路：在二叉树层次遍历的基础上进行修改，每次弹出这一整层的节点，得到每一层的所有节点先将根节点加入队列中，进入循环时，每一层的节点个数等于当前队列的大小，利用此性质来得到当前层的所有节点 public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>();
2020-07-19 20:35:54
180
原创 LeetCode ---- 98、验证二叉搜索树
题目链接思路：二叉搜索树有一个特性，当使用中序遍历来遍历二叉搜索树时，遍历结果一定是一个升序的结果利用这个特性，改造二叉树的中序遍历即可，在中序遍历打印当前节点值时，进行与之前最后一次打印的值进行比较即可 public boolean isValidBST(TreeNode root) { if (root == null) { return true; } Deque<TreeNode> stack
2020-07-16 21:13:51
49
原创 LeetCode ---- 96、不同的二叉搜索树
题目链接思路：不同的二叉搜索树的种类的计算方法：对于1~n中的一个数字 i，它作为根节点时，i-1全部为 i 的左子树，n - i 全部为 i 的右子树，那么以 i 为根节点时，不同的搜索二叉树的种类为 左子树的不同种类 * 右子树的不同种类即：f(i) = f(i - 1) * f(n - i)那么就可以写出下面的代码：但是会超时，时间复杂度过高 public int numTrees(int start, int end) { if (start >
2020-07-15 21:37:33
56
原创 LeetCode ---- 95、不同的二叉搜索树 II
题目链接思路：题目要求构建节点值从1~n的所有的二叉搜索树，那么就必须要确保任何一棵子树的左子树 < 根 < 右子树从1~n中，对于任意一个值，比如2来说，1只能作为它的左子树，从3开始到n都是2的右子树，但是右子树怎么排布就变成了和2挑选左子树右子树同样的问题，通过递归解决就好 public List<TreeNode> generateTrees(int n) { if (n == 0) { return new L
2020-07-14 21:09:28
51
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人