Orange&1024-CSDN博客

原创 LeetCode437.路径总和3

给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。示例：root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \5 -3/ \ \3 2 11/ \ \3 -2 1返回

2020-09-28 09:44:05 123

原创 LeetCode112.路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。示例:给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4-&

2020-09-28 09:34:37 109

原创 LeetCode107.二叉树的层次遍历2

给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）例如：给定二叉树 [3,9,20,null,null,15,7],3/ \9 20 / \15 7返回其自底向上的层次遍历为：[[15,7],[9,20],[3]]程序输出为：15 7 9 20 3#include <iostream>#include <queue>#include<vector>#include

2020-09-28 09:29:18 192

原创 LeetCode101.对称二叉树

给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。1/ \2 2/ \ / \3 4 4 3二叉树[1,2,2,null,3,3,null,5,-2,-2,5]是对称的。 1 / \ 2 2 \ / 3

2020-09-28 09:27:48 123

原创 LeetCode207.课程表

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？示例 1:输入: 2, [[1,0]]输出: true解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。示例 2:输入: 2, [[1,0],[0,1]]输出: false解释:

2020-09-28 09:22:47 144 1

原创图的构造(邻接矩阵与邻接表)

两种方式构造下方的图#include<iostream>#include<vector>using namespace std;struct GraphNode { int label; vector<GraphNode*> neighbors; GraphNode(int x) : label(x) {};};//邻接矩阵一般用来表示稠密图 void construct_graph1() { const int MAX_N = 5; //5个顶

2020-09-27 21:11:09 212

原创 LeetCode199.侧面观察二叉树

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。示例:输入: [1,2,3,null,5,null,4]输出: [1, 3, 4]解释:思路：层序遍历。遍历时将每一层的最后一个节点加入结果中。如何判断节点是最后一个？层次遍历时，将节点与层数绑定为pair，压入队列时，将节点与层数同时压入队列，并记录每一层中出现的最后一个节点。在层次遍历中，每一层中的最后一个节点最后遍历到，随时更新对每层的最后一个节点即可。#include<iostream&gt

2020-09-27 20:53:28 86

原创 LeetCode114.二叉树转链表

给定一个二叉树，将该二叉树就地(in-place)转换为单链表。单链表中节点顺序为二叉树前序遍历顺序。#include<iostream>#include<vector>using namespace std;struct TreeNode{ int val; TreeNode *left; //左孩子指针 TreeNode *right;//右孩子指针 TreeNode(int x) : val(x),left(NULL),right(NULL) {}};

2020-09-27 11:12:15 177 1

原创 LeetCode236.最近的公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]示例 1:输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出: 3解释: 节点 5 和节点 1

2020-09-27 10:22:07 60

原创 LeetCode113.路径之和2

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。示例:给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回:[[5,4,11,2],[5,8,4,5]]思路:先序遍历。每遍历一个结点就将其值加入路径数组path

2020-09-27 09:54:31 45

原创二叉树构造以及前序，中序，后序，层序三种遍历方式的实现

树是n(n>=0)个节点的有限集，且这些节点满足如下关系:(1)有且仅有一个节点没有父结点，该节点称为树的根。(2)除根外，其余的每个节点都有且仅有一个父结点。(3)树中的每一个节点都构成一个以它为根的树。二叉树在满足树的条件时，满足如下条件:每个节点最多有两个孩子(子树)，这两个子树有左右之分，次序不可颠倒。二叉树构造#include<iostream>using namespace std;struct TreeNode{ int val; TreeNode *l

2020-09-27 09:35:10 115

原创 LeetCode131.分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。示例:输入: “aab”输出:[[“aa”,“b”],[“a”,“a”,“b”]]#include<iostream>#include<vector> #include<string>using namespace std;class Solution{public: vector<vector<string> > par

2020-09-26 15:09:52 54

原创 LeetCode93.复原ip地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。例如：“0.1.2.201” 和 “192.168.1.1” 是有效的 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “[email protected]” 是无效的 IP 地址。示例 1：输入：s = “25525511135”输出：[“255.255.11.135”,“25

2020-09-26 14:44:10 89

原创 LeetCode79.单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例:board =[[‘A’,‘B’,‘C’,‘E’],[‘S’,‘F’,‘C’,‘S’],[‘A’,‘D’,‘E’,‘E’]]给定 word = “ABCCED”, 返回 true给定 word = “SEE”, 返回 true给定 word = “ABCB”, 返回 false思路：

2020-09-26 14:10:36 103

原创 LeetCode90.组合总和2

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合，输出组合的数量。candidates 中的每个数字在每个组合中只能使用一次。说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。示例 1:输入: candidates = [10,1,2,7,6,1,5], target = 8,所求解集为:[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]]输出：4示例 2:

2020-09-25 15:54:30 52

原创 LeetCode39.组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。说明：所有数字（包括 target）都是正整数。解集不能包含重复的组合。示例 1：输入：candidates = [2,3,6,7], target = 7,所求解集为：[[7],[2,2,3]]示例 2：输入：candidates = [2,3,5], target = 8,所求

2020-09-25 15:33:06 49

原创 LeetCode698.划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。示例 1：输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4输出： True说明：有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。思路：1.计算出每个子集的和，为 sum = sum(nums) / k2.将nums升序排序，如果最大值大于每个子集的和，返回false3.定义大小为k的数组arr，相当于k个桶，每个桶的初始值为

2020-09-25 15:14:18 325

原创 LeetCode315.逆序数

预备知识：归并排序//合并两个有序数组void merge_sort_two_vec(vector<int> &sub_vec1,vector<int> &sub_vec2,vector<int> &vec) { int i = 0,j = 0; while(i < sub_vec1.size() && j < sub_vec2.size()) { if(sub_vec1[i] < sub_vec[j]

2020-09-25 14:35:51 188

原创 LeetCode51.N皇后问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。上图为 8 皇后问题的一种解法。给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。示例：输入：4输出：[[".Q…", // 解法 1“…Q”,“Q…”,“…Q.”],["…Q.", // 解法 2“Q…”,“…Q”,“.Q…”]]解释: 4 皇后问题存在两个不同

2020-09-25 14:14:26 115

原创 LeetCode22.生成括号

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。示例：输入：n = 3输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]在组成的所有可能中，哪些是合法的？1.左括号与右括号的数量不可超过n2.每放一个左括号，才可放一个右括号，即右括号不可先于左括号放置。故递归需要限制条件：1.左括号与右括号的数量，最多放置n个2.若左括号的数量<=右括号的数量，不可进行放置右括号的递归。cla

2020-09-25 13:36:27 62

原创 LeetCode40.组合总和2

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。示例 1:输入: candidates = [10,1,2,7,6,1,5], target = 8,所求解集为:[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]]示例 2:输入: candidate

2020-09-23 21:49:37 76

原创 LeetCode90.子集2

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例:输入: [1,2,2]输出:[[2],[1],[1,2,2],[2,2],[1,2],[]]思路：导致子集重复的原因有两种：1.不同位置的元素组成的集合是同一个子集，顺序相同例如[2,1,2,2]选择第1，2，3个元素组成的子集为[2,1,2]选择第1，2，4个元素组成的子集也为[2,1,2]2.不同位置的元素组成的集合是同一个子集，顺序不同例如[2,1

2020-09-23 21:32:45 79

原创 LeetCode78.子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例:输入: nums = [1,2,3]输出:[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]思路：利用回溯法生成子集，对于每个元素，都有加入与不加入两种选择。选择放入该元素后，递归地进行后续元素的选择，完成放入该元素后续所有元素的试探；之后将这个元素拿出，递归的进行后续元素的选择，完成不放入该元素后续所有元素的试探class S

2020-09-23 21:18:02 116

原创二叉树的三种遍历(使用栈迭代进行实现)

前序遍历非递归：struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNo

2020-09-23 18:40:01 205

原创翻转矩阵后的得分(LeetCode861)

问题描述 :有一个二维矩阵 A ，其中每个元素的值为 0 或 1 。翻转是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。在做出任意次数的翻转后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。返回尽可能高的分数。示例：输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]输出：39解释：转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]0b1111 + 0b1001 + 0b1111

2020-09-15 11:14:24 111

原创分割数组为连续子序列(LeetCode659)

问题描述 :给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。一个子序列是从原始数组挑选一部分（也可以全部）元素而不改变相对位置形成的新数组如果可以完成上述分割，则返回 true ；否则，返回 false 。示例 1：输入: [1,2,3,3,4,5]输出: True解释:你可以分割出这样两个连续子序列 :1, 2, 33, 4, 5示例 2：输入: [1,2,3,3,4,4,5,5]输出:

2020-09-15 10:58:20 320

原创无重叠区间(LeetCode435)

问题描述 :给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。注意:可以认为区间的终点总是大于它的起点。区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。示例 1:输入: [ [1,2], [2,3], [3,4], [1,3] ]输出: 1解释: 移除 [1,3] 后，剩下的区间没有重叠。示例 2:输入: [ [1,2], [1,2], [1,2] ]输出: 2解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。示例 3:输入: [

2020-09-15 10:30:53 115

原创去除重复字母(LeetCode361)

思路：贪心+栈用栈来存储最终返回的字符串，并维持字符串的最小字典序，每遇到一个字符，如果这个字符不在栈中，就需要将其入栈，但是入栈之前要将栈中之后还会出现，且字典序比当前元素大的出栈，然后当前元素才能入栈#include<iostream>#include<vector>#include<map>#include<set>#include<string>using namespace std;class Solution{pu

2020-09-15 10:06:04 150

原创救生艇(LeetCode881)

问题描述 :第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。返回载到每一个人所需的最小船数。(保证每个人都能被船载)。示例 1：输入：people = [1,2], limit = 3输出：1解释：1 艘船载 (1, 2)示例 2：输入：people = [3,2,2,1], limit = 3输出：3解释：3 艘船分别载 (1, 2), (2) 和 (3)示例 3：输入：peop

2020-09-15 09:47:48 70

原创买卖股票的最佳时机(LeetCode122)

问题描述 :给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1:输入: [7,1,5,3,6,4]输出: 7解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股

2020-09-15 09:39:48 48

原创 15.查找和最小的K对数字

问题描述 :给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。找到和最小的 k 对数字 (u1,v1), (u2,v2) … (uk,vk)，按从小到大的顺序输出它们的和。示例 1:输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3输出: 因为前三对是：[1,2],[1,4],[1,6]，所以输出3，5，7解释: 返回序列中的前 3 对数： [

2020-09-14 20:21:07 98

原创 14.前 K 个高频元素(LeetCode347)

问题描述 :给定一个非空的整数数组，返回其中出现频率前 k 高的元素。示例 1:输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2]示例 2:输入: nums = [1], k = 1输出: [1]说明：你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。输出时，首先输出频率最高的元素

2020-09-14 20:09:20 170

原创 13.任务调度器(LeetCode621)

问题描述 :给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。你需要计算完成所有任务所需要的最短时间。示例：输入：tasks = [“A”,“A”,“A”,“B”

2020-09-14 12:10:40 71

原创 12.和至少为 K 的最短子数组(LeetCode862)

问题描述 :返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。如果没有和至少为 K 的非空子数组，返回 -1 。示例 1：输入：A = [1], K = 1输出：1示例 2：输入：A = [1,2], K = 4输出：-1示例 3：输入：A = [2,-1,2], K = 3输出：3说明：1 <= A.length <= 50000-10 ^ 5 <= A[i] <= 10 ^ 51 <= K <= 10 ^ 9输入说明 :

2020-09-14 11:10:35 73

原创 11.接雨水(LeetCode42)

问题描述 :给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。示例:输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6可使用以下代码，完成其中的trap函数，其中形参height为上述的柱子高度数组，返回接到的雨水量。输入说明 :输入若干个非负整数，以空格分隔。输出说明 :输出一个整数

2020-09-14 10:47:24 78

原创 10.简化路径

问题描述 :以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点（…）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

2020-09-14 10:33:28 140

空空如也

空空如也