- 博客(120)
- 收藏
- 关注
RSS订阅原创 剑指 Offer 57. 和为s的两个数字 剑指 Offer 57 - II. 和为s的连续正数序列
题目：剑指 Offer 57. 和为s的两个数字题目描述：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。代码：class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { vector<int>res; int sum,i=0,j=nums.size(
2020-09-29 23:36:28
142
原创 leetcode155. 最小栈 1441. 用栈操作构建数组 剑指 Offer 09. 用两个栈实现队列
题目：leetcode155. 最小栈题目描述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。代码：class MinStack {public: /** initialize your data structure here. */ stack<int>s1; stack<int>s2; void push(int x) { s1.push(x); if(s2.
2020-09-27 23:52:31
756
原创 剑指offer 简单 C++
题目：剑指 Offer 22. 链表中倒数第k个节点题目描述：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。代码：/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next;
2020-09-22 23:12:17
166
原创 剑指 Offer 68 - II. 二叉树的最近公共祖先C++
题目描述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。解题思路：（1）在root的左子树和右子树同时找p和q，若p和q分别分布在root的左右子树，则root为所求。（2）若左子树返回NULL，则说明p和q都在右子树，则进入右子树做1。（3） 若右子树返回NULL，则说明p和q都在左子树，则进入左子树左1。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * Tree
2020-09-02 23:11:45
130
原创 589. N叉树的前序遍历
题目描述：给定一个 N 叉树，返回其节点值的前序遍历。代码：/*// Definition for a Node.class Node {public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val
2020-09-01 23:15:32
78
原创 94. 二叉树的中序遍历C++
题目描述：给定一个二叉树，返回它的中序 遍历。解题思路：（1）根的左孩子依次入栈（2）左孩子全部入栈后，栈顶元素出栈。(3)若栈顶元素有右孩子重复（1）的操作。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL),
2020-08-31 23:19:14
96
原创 965. 单值二叉树C++
题目描述：如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL
2020-08-29 21:21:54
106
原创 24. 两两交换链表中的节点C++
题目描述：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。代码：/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* swapPairs(ListNode*
2020-08-28 23:07:24
78
原创 19. 删除链表的倒数第N个节点C++
题目描述：给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。代码：/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* removeNthFromEn
2020-08-27 22:43:38
78
原创 226. 翻转二叉树C++
题目描述：翻转一棵二叉树。解题思路：根节点入栈，然后依次交换根节点的左右子树。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution
2020-08-26 21:34:27
175
原创 671. 二叉树中第二小的节点C++
题目描述：给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode
2020-08-25 22:50:35
133
原创 101. 对称二叉树C++
题目描述：给定一个二叉树，检查它是否是镜像对称的。解题思路：二叉树要想对称，根结点的左孩子的右子树要等于根结点的右孩子的左子树；左孩子的左子树要等于右孩子的右子树。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL
2020-08-24 21:16:32
129
原创 617. 合并二叉树C++
题目描述：给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right;
2020-08-23 20:27:45
290
原创 257. 二叉树的所有路径C++
题目描述：给定一个二叉树，返回所有从根节点到叶子节点的路径。解题思路：分别递归左子树和右子树。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class S
2020-08-22 17:06:53
130
原创 538. 把二叉搜索树转换为累加树C++
题目描述：给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。解题思路：中序遍历右—中—左。右子树都是大于根节点本身的，所以右子树的累加和就是根节点需要累加的数值。 而左子树有些特殊。根的左根，要累加根节点的数值。左根要累加它自身的右子树的数值。 左根右子树，因为小于根节点，所以计算左根右子树的时候还要把根节点的数值算上去，因为根节点大于它。左根的左子树要累加左跟的数值。代码：/**
2020-08-21 17:49:51
86
原创 108. 将有序数组转换为二叉搜索树C++
题目描述：将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。解题思路：二叉搜索树的左子树值小于根的值，右子树的值大于根的值。将数组的中间元素设为根的值，数组的前半部分元素构建左子树，数组的后半部分构建右子树。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode
2020-08-20 18:34:03
161
原创 110. 平衡二叉树C++
题目描述：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。解题思路：判断一棵树是否为二叉树关键看树中结点的左右孩子是否存在同时左右孩子的高度差是否超过一。代码:/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *rig
2020-08-19 20:46:38
87
原创 637. 二叉树的层平均值C++
题目描述：给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。解题思路：要借助一个队列得知每层有多少个结点。队列的头结点出队，头节点若有左右孩子则入队。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL),
2020-08-18 19:11:45
197
原创 剑指 Offer 65. 不用加减乘除做加法C++
题目描述：写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。解题思路：代码：class Solution {public: int add(int a, int b) { //无进位和，进位值 int sum,carry; while(b!=0){ //异或操作得无进位和 sum=a^b; //与操作后移位得进位值
2020-08-17 21:41:37
65
原创 剑指 Offer 60. n个骰子的点数C++
题目描述：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。解题思路：n 枚骰子掷出的点数的范围是 [n, 6n]，也就是最后数组的长度为 5n + 1，因为每个骰子掷出每个数字的概率都是 1/6，所以对于 n 枚骰子，每次掷出的数字组合的概率都为 (1/6)^n。也就是说如果和为 s 的组合有 k 种，那么和为 s 的概率为 k(1/6)^n我们这里
2020-08-16 19:23:16
169
原创 剑指 Offer 55 - I. 二叉树的深度C++
题目描述：输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL)
2020-08-15 22:39:50
43
原创 剑指 Offer 24. 反转链表C++
题目描述：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。解题思路：定义两个指针：（1） pre 和 cur；preprepre 在前 curcurcur 在后。（2）每次让 pre 的 next 指向 cur ，实现一次局部反转。（3）局部反转完成之后， pre 和 cur 同时往前移动一个位置循环上述过程，直至 pre 到达链表尾部。代码：/** * Definition for singly-linked list. * struct ListNode { *
2020-08-14 21:38:44
101
原创 剑指 Offer 30. 包含min函数的栈C++
题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。解题思路：一个栈存数据，一个栈存最小值。代码：class MinStack {public: /** initialize your data structure here. */ MinStack() {} stack<int>s; stack<int>Min; voi
2020-08-13 19:27:48
264
原创 剑指 Offer 09. 用两个栈实现队列C++
题目描述：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )。解题思路：只使用一个栈 stack1 当作队列，另一个栈 stack2 用来辅助操作。队列是先进后出，栈是先进先出。要想将新加入的元素出现栈底，需要先将 stack1 的元素转移到 stack2，将元素入栈 stack1，最后将 stack2 的元素全部回到 stack1。
2020-08-12 20:21:49
211
原创 剑指 Offer 06. 从尾到头打印链表C++
题目描述：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。解题思路：利用栈先进后出的特点。代码：/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: vector&
2020-08-11 22:01:36
123
原创 剑指 Offer 32 - II. 从上到下打印二叉树 IIC++
题目描述：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。解题思路：这道题其实就是层序遍历二叉树并依次输出每层二叉树的元素。先建立一个队列，根结点入队，取队列大小为l。在for(i=0;i<l;i++)中队首元素依次压入容器vector,然后出队。若根结点有左右孩子则将左右孩子入队。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * Tree
2020-08-10 20:25:52
132
原创 剑指 Offer 27. 二叉树的镜像C++
题目描述：请完成一个函数，输入一个二叉树，该函数输出它的镜像。解题思路：每次遍历左右子树前，先交换左右子树。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
2020-08-09 19:05:12
135
原创 剑指 Offer 06. 从尾到头打印链表C++
题目描述：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。代码：/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: vector<int> revers
2020-08-08 21:19:26
92
原创 剑指 Offer 03. 数组中重复的数字C++
题目描述：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 : val(x), next(NULL) {} * }; */class Solution {public: ListNode* d
2020-08-06 21:54:46
106
原创 剑指 Offer 25. 合并两个排序的链表C++
题目描述：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。代码：/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* mergeTwoLis
2020-08-05 21:59:28
162
原创 剑指 Offer 10- I. 斐波那契数列C++
题目描述：写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：代码：class Solution {public: int fib(int n) { if(n==0) return 0; vector<int>dp(n+1); dp[0]=0; dp[1]=1; for(int i=2;i<=n;i++) dp[i]=(dp[i-1
2020-08-04 22:38:14
77
原创 剑指 Offer 28. 对称的二叉树C++
题目描述：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。解题思路：一棵二叉树的左右孩子同样是两棵二叉树。二叉树要想对称，左右孩子的值要相等，左孩子的右子树要等于右孩子的左子树；右孩子的右子树要等于左孩子的左子树。代码 * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right
2020-08-03 22:30:18
164
原创 剑指 Offer 55 - II. 平衡二叉树C++
题目描述：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。解题思路：1.若为空返回true。2.计算左子树和右子树的高度差 高度计算方式就是求二叉树的最大深度。3.所有节点都满足高度差小于等于1 返回true。4.否则有一个高度差大于1 则返回false。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; *
2020-08-02 21:02:57
151
原创 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
题目描述：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。解题思路：利用二叉搜索树左子树的值小于根的值，右子树的值大于根的值的特点。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(
2020-08-01 20:27:39
45
原创 剑指 Offer 55 - I. 二叉树的深度C++
题目描述：输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。解题思路：指针指向队头元素然后队头元素出队；队头元素如果有左右孩子依次入队。迭代代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode
2020-07-31 21:18:45
179
1
原创 leetcode第1304. 和为零的N个唯一整数C++
题目描述：给你一个整数 n，请你返回 任意 一个由 n 个 各不相同 的整数组成的数组，并且这 n 个数相加和为 0 。解题思路：n为偶数数组关于正负号对称；n为奇数数组以0为中心对称。代码：class Solution {public: vector<int> sumZero(int n) { vector<int>A(n); for(int i=0;i<n;++i) A[i]=i*2-n+1;
2020-07-30 18:13:13
105
原创 leetcode第1346. 检查整数及其两倍数是否存在C++
题目描述：给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。解题思路：注意0这个特殊值。代码：class Solution {public: bool checkIfExist(vector<int>& arr) { unordered_map<int,int>s; for(int x:arr) s[x]++; for(int
2020-07-29 21:17:42
92
原创 leetcode第605. 种花问题C++
题目描述：假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。解题思路：在 flowerbed 数组两端各增加一个 0， 这样处理的好处在于不用考虑边界条件，任意位置处只要连续出现三个 0 就可以栽上一棵花。代码：class Solution {publ
2020-07-28 18:01:22
428
原创 leetcode第1502. 判断能否形成等差数列C++
题目描述：给你一个数字数组 arr 。如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。先排好序。代码：class Solution {public: bool canMakeArithmeticProgression(vector<int>& arr) { sort(arr.begin(),arr.end()); int dif
2020-07-27 17:44:46
470
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人