- 博客(55)
- 收藏
- 关注
RSS订阅原创 【LeetCode】31.下一个排列
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。以下是一些例子，输入位于左侧列，其相应输出位于右侧列。1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1/*1.从末尾元素开始，找到第一个非升序的元素*//*...
2019-03-26 13:39:29
105
原创 【LeetCode】22. 括号生成
给出n代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。例如，给出n = 3，生成结果为：[ "((()))", "(()())", "(())()", "()(())", "()()()"]解题思路：用递归的方法，使用掉所有的左括号和右括号，为了保证符合规则，两个放置左右括号的子递归的条件分别是存在左括号和之前有多余的左括...
2019-03-21 14:44:23
124
原创 【LeetCode】17. 电话号码的字母组合
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。示例:输入："23"输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].解题思路：首先建立一个map实现数字与字母的对应关系，然后通过递归的方法，遍历所有可能的组合...
2019-03-21 10:20:08
204
原创 【LeetCode】15. 最接近的三数之和
给定一个包括n 个整数的数组nums和 一个目标值target。找出nums中的三个整数，使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).仍然是排序再寻找的策略，因为数组已经...
2019-03-20 15:37:37
101
原创 【LeetCode】15. 三数之和
给定一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。解题思路：不使用暴力解法，核心思想首先要把条件分解，三个数之和为0则至少有一个数为负数，按照选定一个数再寻找两个与之匹配的数的思路，先把数组排序，然后遍历所有的负数，遇到第一个正数就可以停止...
2019-03-20 11:59:22
86
原创 【LeetCode】437. 路径总和 III
给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。解题思路：两层递归，第一层递归当前节点起始，以下子树的sum，如果结果符合则路径数量+1。第二层递归遍历所有的元素。unsigned int pathcount = 0;int Solution::...
2019-01-30 10:42:28
110
原创 【LeetCode】404. 左叶子之和
计算给定二叉树的所有左叶子之和。解题思路：1.遍历所有子树->递归的方法 2.如何分辨这个子树是左子树->引入递归形参，递归左子树时置1，右子树置0. 3.如何判断叶子节点->root->left = NULL && root->right = NULLint S...
2019-01-29 14:24:25
121
原创 【LeetCode】113. 路径总和 II
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。解题思路：在上题找到是否有满足条件的路径的基础上，实际上是把符合条件的路径记录下来。需要注意以下几点1.如果涉及变量的修改，建议把变量构建为嵌套函数的形参。2.每次返回到上一层递归函数之前，需要弹出最近压入的元素，否则路径中会出现不期望的元素。vect...
2019-01-28 13:38:55
99
原创 【LeetCode】112. 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。解题思路：分别对一个节点的左右子树进行递归，不同的是传入的数值为sum减去节点保存的值，直到叶子节点，如果此时嵌套传入的sum的值等于当前节点保存的值，则表示存在这样一条路径。左右子树递归的结果是或的关系。bool Solution::h...
2019-01-25 15:34:19
118
原创 【LeetCode】110. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。解题思路：两层嵌套，第一层判断当前节点的左右子树的高度差，第二层遍历所有的节点。int maxdepth(TreeNode* root){ if(root == NULL) { return 0; }...
2019-01-25 10:38:07
91
原创 【LeetCode】107. 二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）解题思路：利用之前二叉树的层次遍历的方法，在temp压入result之前，先用栈保存temp，实际上是完成一个逆序的过程。vector<vector<int>> Solution::levelOrderBottom(TreeNode* root){ ...
2019-01-24 14:57:23
404
原创 【LeetCode】102. 二叉树的层次遍历
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。解题思路：建立一个队列用来存储节点，首先把根节点压入队列，第一层循环条件是队列不为空，第二层循环为根据队列中节点的个数，首先获取头节点存储的地址，保存头节点指向的数据，弹出头节点，并把不为空的左子树和右子树压入队列，以此循环。关于vector<vector<int>>的初始化，首先初始化...
2019-01-24 14:42:09
124
1
原创 【LeetCode】101. 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。利用之前相同二叉树的代码，递归的参数分别为root对应左右节点的大小。bool issametree(TreeNode* p, TreeNode* q){ if((p == NULL) && (q == NULL))/*p,q同时为空，意味着以前的遍历未出现不相同节点*/ { return true...
2019-01-23 13:57:51
88
原创 【LeetCode】100. 相同的树
给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。解题思路：利用递归的方法，比较各个左节点和右节点的大小。需要注意的是在递归的嵌套函数中，执行return的时候会结束当前嵌套。bool Solution::isSameTree(TreeNode* p, TreeNode* q){ if((p == NULL...
2019-01-23 13:24:03
97
原创 【慢一点走】二叉树的创建和遍历
利用递归完成了二叉树的创建和遍历，两个需要注意的点：1.递归中的变量如果涉及到累加或累减类似操作的时候，需要考虑清楚嵌套时的数值是否为期望的数值。2.创建二叉树时，由于要改变的是指针本身而不是指针指向的数据，所以需要二级指针，实际上传递的是指针本身的地址。typedef struct TreeNode { int val; struct TreeNode *left; ...
2019-01-23 13:10:11
82
原创 【LeetCode】150. 逆波兰表达式求值
根据逆波兰表示法，求表达式的值。有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。说明：整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。解题思路：首先搞清楚基本的数学原理，即遇到符号时，需要操作的是前两个元素，使用栈的保存方式，遇到数字入栈，遇到符号把栈头两个元素出栈进行运...
2019-01-09 10:54:27
128
原创 【LeetCode】844. 比较含退格的字符串
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。解题思路：用栈保存字符串中的字符，当遇到#时，pop元素出栈。bool Solution::backspaceCompare(string S, string T){ unsigned int index = 0; stack<int> st...
2019-01-09 09:08:16
112
原创 【LeetCode】682. 棒球比赛
你现在是棒球比赛记录员。给定一个字符串列表，每个字符串可以是以下四种类型之一：1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。2. "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。3. "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。4. "C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除...
2019-01-08 21:44:06
246
原创 【LeetCode】232. 用栈实现队列
使用栈实现队列的下列操作：push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。解题思路：基本与用队列实现栈类似，返回头部元素的操作稍微麻烦一点。class Solution {private: stack<int> Stack1, ...
2019-01-08 11:18:14
304
原创 【LeetCode】225. 用队列实现栈
使用队列实现栈的下列操作：push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空解题思路：首先用队列A保存元素，栈顶元素即为队列的rear元素，栈是否为空即为队列是否为空，执行pop操作时，先把除最后一个元素之外的元素弹出，保存在队列B中，然后弹出队列A中的最后一个元素，再把队列B的元素弹出的同时压入队...
2019-01-08 10:46:44
91
原创 【LeetCode】155. 最小栈
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。push(x) -- 将元素 x 推入栈中。 pop() -- 删除栈顶的元素。 top() -- 获取栈顶元素。 getMin() -- 检索栈中的最小元素。解题思路：利用两个栈完成操作，第一个栈保存所有的元素，第二个栈在每个元素进入第一个栈时，保存当前最小的元素，当查询最小元素时，返回第二个栈的栈顶即...
2019-01-08 10:00:28
987
原创 【LeetCode】622. 设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。你的实现应该支持如下操作：MyCircul...
2019-01-07 13:35:06
2973
原创 【LeetCode】933. 最近的请求次数
写一个 RecentCounter 类来计算最近的请求。它只有一个方法：ping(int t)，其中 t 代表以毫秒为单位的某个时间。返回从 3000 毫秒前到现在的 ping 数。任何处于 [t - 3000, t] 时间范围之内的 ping 都将会被计算在内，包括当前（指 t 时刻）的 ping。保证每次对 ping 的调用都使用比之前更大的 t 值。解题思路：利用队列先进...
2019-01-04 15:05:15
316
原创 【慢一点走】链表总结
1.思考清楚while循环结束的条件是head != NULL还是head->next != NULL2.通过快慢指针或类似的方法可以快速找到一些节点的位置3.处理链表相对于数组的区别是你需要记录当前节点之前的一个节点才能对当前节点进行操作，当然你也可以使用类似p->next来规避这样的问题4.复杂的问题先画图想清楚再开始写，重要的是思路清晰...
2019-01-04 13:32:42
95
原创 【LeetCode】445. 两数相加 II
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。解题思路：思路1：把两个链表代表的数字先算出来，然后相加，最后用一个新链表表示。写完之后运行发现，当数据过大时，会超出数据定义范围。思路2：把两个链表的每一位数据入栈，然后再每位出栈相加，最后得到一...
2019-01-04 10:07:18
544
原创 【LeetCode】328. 奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。解题思路：在原链表中操作，把奇数节点移动到上一个奇数节点尾部。ListNode* oddEvenList(ListNode* hea...
2019-01-03 15:04:15
109
原创 【LeetCode】237. 删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。现有一个链表 -- head = [4,5,1,9]，它可以表示为: 4 -> 5 -> 1 -> 9示例 1:输入: head = [4,5,1,9], node = 5输出: [4,1,9]解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之...
2019-01-03 13:45:51
118
原创 【LeetCode】234. 回文链表
请判断一个链表是否为回文链表。解题思路：根据 O(n) 时间复杂度和 O(1) 空间复杂度的要求，则不能使用堆栈。首先找到中间节点，然后反转中间节点之后的节点，最后比较头结点和中间节点之后元素的大小。bool Solution::isPalindrome(ListNode* head){ if((head == NULL) || (head->next == NULL))...
2019-01-03 12:05:00
240
原创 【LeetCode】206. 反转链表
反转一个单链表。解题思路：最简单的方法是反转每一个元素next指向的方向。ListNode* reverseList(ListNode* head) { ListNode *p1, *p2, *ptemp; ListNode *phead = new ListNode(0); if((head == NULL)||(head->next == NULL)...
2019-01-03 09:36:01
61
原创 【LeetCode】203. 移除链表元素
删除链表中等于给定值 val 的所有节点。解题思路：为了方便操作，新建一个前继节点，比较该节点next的val与给定值的大小需要注意的是当操作pdelete->next = pdelete->next->next后，pdelete不需要移动位置，因为它的后继变化了。ListNode* Solution::removeElements(ListNode* head, ...
2019-01-03 08:59:48
108
原创 【LeetCode】160. 相交链表
找到两个单链表相交的起始节点。注意：如果两个链表没有交点，返回 null. 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。 联系之前做过有环链表，把链表A的尾段指向链表B的头端，构成一个有环链表。利用之前推导的距离公式，找到相交的节点。ListNode* Solution::getI...
2019-01-02 12:55:45
90
原创 【LeetCode】148. 排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。根据时间复杂度选择归并排序，解题思路如下：1.使用归并排序前，找到中间节点pmiddle，因为是链表排序所以我们要找到的是中间节点的前继节点，使用快慢指针可以完成，需要注意的是分隔成两个链表时，前链表的最后一个节点指向空。2.对前后两部分再分别进行归并排序。3.合并两个有序链表，同样最后一个节点指向空。...
2018-12-28 12:24:54
134
原创 【LeetCode】142. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。说明：不允许修改给定的链表。解题思路：1.利用前一题环形链表判断是否有环的方法，判断当前链表是否有环 2.若有环，则下一步为找...
2018-12-27 15:33:16
123
原创 【LeetCode】141. 环形链表
给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。解题思路：利用快慢指针的方法，满指针每次走一步，快指针每次走两步，如果链表有环，快慢指针一定会相遇。需要想明白的是相遇时两个指针走的次数只与链表的原本长度有关，与链表的环连接到哪一个节点无关。bool S...
2018-12-27 14:31:49
158
原创 【LeetCode】83. 删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。两层while循环，时间复杂度n^2 ListNode *phead = head; if((head == NULL) || (head->next == NULL)) { return head; } /*大循环遍历所有元素*/ while(ph...
2018-12-27 10:42:19
79
原创 【LeetCode】92. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:1 ≤ m ≤ n ≤ 链表长度。遍历一遍链表完成反转，首先根据m的值确定反转的起始位置和其前继，保存以上两个位置。然后从此位置开始，循环次数为m+n-1，依次反转元素位置，结束时当前指针head指向的是第n个元素，newprehead指向的是第n-1个元素。然后把保存的起始位置的next指向当前指针head，完后后拼接，最后...
2018-12-27 09:49:27
64
原创 【LeetCode】86. 分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。题目理解起来比较拗口，并不是对链表进行完整的排序，可以简单的理解为把小于x的节点拿出来，把大于x的节点拿出来，拼接即可。通过新建两个头节点分别存储大于x和小于x的节点，空间换取时间的理念只需要遍历一遍链表即可完成，思路上比在原链表上进行移动的操作...
2018-12-26 09:31:58
139
原创 【LeetCode】82. 删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。基本思路是第一层循环，两个指针分别指向当前元素和它的前继，目的是如果有重复，需要删除当前元素，然后直到当前元素为空第二层循环，两个指针分别指向当前元素的下一个元素和它的前继，目的是如果有重复，需要删除当前元素之后的所有元素，然后直到当前比较元素为空ListNode* Solution::delete...
2018-12-25 11:28:43
107
原创 【LeetCode】61. 旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。基本思路是每次循环先找到倒数第二节点的位置，然后把头结点的next指向最后一个节点，倒数第二节点的next指向NULL需要注意的是，实际上K=1和K=链表长度+1时，返回的结果是一致的，需要对K作取余处理ListNode* Solution::rotateRight(ListNode* head, int...
2018-12-24 14:47:26
66
原创 【LeetCode】24. 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。示例:给定 1->2->3->4, 你应该返回 2->1->4->3创建一个新节点指向当前头节点，交换时新节点next指向当前节点的下一个节点，当前节点的下一个节点next指向当前节点，当前节点next指向当前节点的下一个节点，此时当前节点位置已调换，新节点=当前节点的地址，当前节点指向下一...
2018-12-24 13:35:43
85
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人