- 博客(103)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 最长上升子序列(动态规划/贪心+二分)
题目：给定一个无序的整数数组，找到其中最长上升子序列的长度。题解：动态规划经典题：class Solution {public: int lengthOfLIS(vector<int>& nums) { int n=nums.size(); if(n==0) return 0; vector<int> dp(n,1); int ans=1; for(int i=1;i<n;
2020-07-01 11:10:59
247
原创 寻找重复数(二分答案)
题目：给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。题解：题目确保只有一个重复的数，重复次数大于等于1，此处由于要在O(1)空间，且只读状态下进行查找，我们使用二分答案，答案区间[1,n]，因此要找到分割区间的条件，考虑任意一种分割，答案中点mid，那左区间和右区间中必有一个区间所包含的元素比区间点数多1，根据这个条件划分。class Solution {public:
2020-07-01 10:24:45
177
原创 颜色分类(三指针)
题目：给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。注意:不能使用代码库中的排序函数来解决这道题。题解：方法一：排序方法二：三指针，时间复杂度O(N)，左指针指向0，右指针指向2，p指针从最左边向右边移动，p指针指向的数为0，与左指针交换，并同时向右移动一位，指向2，与右指针交换，右指针向左移一位，p指针不动，指向为1，p右移一位。class
2020-06-30 23:08:46
225
原创 H 指数(二分+lower_bound二分)
题目：给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数 不超过 h 次。）例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。题解：显然这是一道二分答案的题目，找到h的答案区间，在区
2020-06-30 20:50:12
219
原创 二叉树的最近公共祖先(DFS+路径记录)
题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]题解：首先DFS找到到p，q节点的路径并记录下来，然后比较两条路径，得到LCA/** * Definition for a binary tree n
2020-06-26 00:05:08
275
1
原创 根据前序和后序遍历构造二叉树(递归法)
题目：返回与给定的前序和后序遍历匹配的任何二叉树。pre 和 post 遍历中的值是不同的正整数。题解：知道先序后序，二叉树不唯一，所以优先左子树，只要左子树符合条件，就进入递归，下面是比较复杂的寻找左子树的方法，较好的方法是根据后序倒数第二个数是右子树的根节点，对应先序遍历里的区间进行递归。/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;*
2020-06-25 22:42:59
631
原创 从前序与中序遍历序列构造二叉树(递归法)
题目：根据一棵树的前序遍历与中序遍历构造二叉树。注意:你可以假设树中没有重复的元素。题解：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solu
2020-06-25 19:48:00
187
原创 从中序与后序遍历序列构造二叉树(递归法+模拟)
题目：根据一棵树的中序遍历与后序遍历构造二叉树。注意:你可以假设树中没有重复的元素。题解：已知中序，后序，即可唯一确定一棵二叉树，关键点抓住后序的第一个元素是当前根节点，因而我们可以将序列进行切割，递归到只有一个元素时，构造节点。具体解释贴在代码里/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right;
2020-06-25 19:31:22
547
原创 113. 路径总和 II(DFS+回溯)
题目：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。题解：DFS，同时回溯法记录所有经过的节点，保存在path向量中，当遍历到叶子节点，检查sum是否符合要求，符合要求则将path加到ans里面。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNo
2020-06-25 15:17:32
109
原创 1038. 从二叉搜索树到更大和树(反向中序遍历和)
题目：给出二叉 搜索 树的根节点，该二叉树的节点值各不相同，修改二叉树，使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。提醒一下，二叉搜索树满足下列约束条件：节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。题解：二叉搜索树的中序遍历是从小到大的顺序，反向中序则是从大到小，每次遍历到时把和加到节点上即可，超级简洁的代码。/** * Definition for a binary tree nod
2020-06-24 15:13:19
131
原创 最接近的三数之和(双指针法)
题目：给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。题解：首先，暴力法O(N^3)，对于无序数组采取暴力法，我们对该解法进行优化，首先，有序的数组更加方便我们进行查找等操作，所以先对数组快速排序O(N*logN)，接下来有两条路可选。方法一： O(N^2)进行两重循环，将所有两个数的组合按序存储下来，然后对原来数组中的每一个元素进行二分查询O(NlogN *N)
2020-06-24 14:35:41
121
原创 二叉树的最大深度
简洁写法：/** * 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 {public: int dfs(TreeNode* root)
2020-06-20 11:33:45
92
原创 最佳观光组合(双指针法)
题目：给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。返回一对观光景点能取得的最高分。题解：暴力法O(N*N)双指针法O(N)：双指针在于固定某一个指针，移动另一个指针，在移动过程中发现数据之间的大小关系，或者重复的计算结构，从而实现直接利用已知结果，减少重复计算的目的。本题先划分两部分A[ i ]
2020-06-17 10:25:56
106
原创 长度最小的子数组(双指针法/二分法)
题目：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。题解：双指针法：左右指针中间的数是连续的，因而每次移动左右指针中的一个，时间复杂度为O(N)，当目前的和小于s时，右指针右移，当和大于或等于s时，左指针左移。class Solution {public: int minSubArrayLen(int s, vector<int>& nums) {
2020-06-16 17:05:19
137
原创 账户合并(并查集)
题目：给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该帐户的邮箱地址。现在，我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址，则两个帐户必定属于同一个人。请注意，即使两个帐户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户，但其所有帐户都具有相同的名称。合并帐户后，按以下格式返回帐户：每个帐户的第一个元素是名
2020-06-16 13:45:07
532
原创 丑数 II（优先队列/动态规划dp）
题目：编写一个程序，找出第 n 个丑数。丑数就是质因数只包含 2, 3, 5 的正整数。题解：方法一：符合条件的数需从小到大记录下来，优先队列具备这样的性质，因而对队列的top，将它取出，将2top，3top，5*top压入队列，当取出第n个top时，将他return。typedef long long ll;class Solution {public: int nthUglyNumber(int n) { priority_queue<ll,vector&l
2020-06-15 15:07:29
131
原创 前 K 个高频元素(最小堆+pair排序)
题目：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。题解：题目要求时间复杂度要小于O(NlogN)，所以先排除快排之类的排序算法。考虑到我们解决第k小元素时使用了堆这一数据结构，所以本题自然可以使用堆来解决，我们需要频率前k高的元素，堆的大小定为k，往大小为k的堆中插入一个元素O(logK)（堆为完全二叉树），那么n个数插入n次，时间复杂度O(NlongK) 小于 O(NlogN)，因而我们需要维护好频率与元素的对应关系，pair<int,int>将会是很方便的。tips：
2020-06-15 13:28:04
284
原创 寻找右区间
题目：给定一组区间，对于每一个区间 i，检查是否存在一个区间 j，它的起始点大于或等于区间 i 的终点，这可以称为 j 在 i 的“右侧”。对于任何区间，你需要存储的满足条件的区间 j 的最小索引，这意味着区间 j 有最小的起始点可以使其成为“右侧”区间。如果区间 j 不存在，则将区间 i 存储为 -1。最后，你需要输出一个值为存储的区间值的数组。注意:1.你可以假设区间的终点总是大于它的起始点。2.你可以假定这些区间都不具有相同的起始点。题解：法1：二分法按照区间左端点将区间排序（注意要预先
2020-06-10 19:42:25
88
原创 Pow(x, n)
题目：实现 pow(x, n) ，即计算 x 的 n 次幂函数。题解：快速幂：将指数n表示为二进制，如果当前位为1，则计算它的贡献乘到ans上，注意如果是负数要改成1.0 / ans，同时范围要开long longclass Solution {public: double quickPow(double x,long long N) { double ans=1.0; double base=x; while(N>0)
2020-06-10 09:55:20
90
原创 合并两个有序数组(双指针法+空间优化)
题目：给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。说明:初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。题解：双指针法：O(m+n)时间复杂度，O(m+n)空间复杂度如果两个指针从后往前，另外有一个p指针指向m+n的位置，则空间复杂度优化到O(1)class Solution {publi
2020-06-09 18:12:19
373
原创 下一个更大元素 I(单调栈)
题目：给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。题解：1.暴力搜索，对nums2中每一个元素依次向右找到第一个比它大的数2.单调栈，被压入栈中的元素应该具有单调性，例如1,3,4,2四个元素，按照单调递减栈的顺序入栈：初始状态下栈
2020-06-09 10:30:20
160
原创 两数之和 II - 输入有序数组
题目：给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。说明:返回的下标值（index1 和 index2）不是从零开始的。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。题解：二分查找：外层循环遍历n个数，对每一个数二分查找，O(nlogn)class Solution {public: vector<int> twoS
2020-06-08 13:53:45
74
原创 盛最多水的容器(数组+双指针法)
题目：给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器，且 n 的值至少为 2。题解：暴力法：遍历所有的左右边界，时间复杂度O(n*n)，空间复杂度O(1)双指针法：两个指针从最左和最右开始，由于面积的宽取决于两条高中的最小值，因此可以将较大的那条高固定住，向中间移动较小的高，移动过
2020-06-08 10:57:14
85
原创 两数之和(数组)
题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。题解：O(n*n)暴力法Hashmap法：取出每一个nums元素，如果target-nums[i]在之前出现过，那么它必为答案，题目要求输出位置，mp的value记录nums元素对应位置的信息，而且由于是对之前出现过的数进行搜索，其位置一定在i之前。class Solution {public:
2020-06-07 23:53:31
189
原创 PAT(甲级)1014
#include<bits/stdc++.h>#define lowbit(x) ((x)&(-(x)))#define ll long long#define INF 0x3f3f3f3f#define CLR(a) memset(a, 0, sizeof(a))using namespace std;struct node{ int poptime,endti...
2020-02-18 14:06:01
64
原创 PAT(甲级)1104
题意：求出所有的子段和。题解：双指针法。code in view#include<bits/stdc++.h>using namespace std;int n;int main(){ cin>>n; double temp,res=0; for(int i=1;i<=n;i++){ cin>>temp;...
2019-11-13 16:59:18
99
原创 PAT(甲级)1070
题意：给出N种货物，市场需求为D，如何安排使利润最大题解：求出单位重量货物的利润，sort排序。注意点：都要开浮点数code in view#include<bits/stdc++.h>using namespace std;const int maxn=1e5+10;int n;double d;struct node{ double amount,pric...
2019-11-13 16:37:49
130
原创 PAT(甲级)1074
题意：给出一条单链表，任意给定K，按照每K个节点就将它翻转，最后不足K个节点的不翻转，输出链表顺序。题解：链表表示法，开一个vector保存要翻转的元素，将它逆序存进ans结构体数组中，最后修改一下前后链的地址（注意到ans数组中的address是一致的，将next修改即可），输出。注意点：翻转后前后链地址需要作出相应的改变。code in view#include<bits/std...
2019-11-13 14:19:03
195
2
原创 PAT(甲级)1066
题意：将一组数插进AVL树中，输出这棵树的根节点的值。题解：AVL树四种旋转+AVL树的插入。注意点：数据结构基础题code in view#include<bits/stdc++.h>using namespace std;int n;struct node{ int val; node *left,*right;};node* RightRotat...
2019-11-12 16:21:33
100
原创 PAT(甲级)1116
题意：格式输出题注意点：如果已经访问过并且存在，再次访问时输出Checkedcode in view#include<bits/stdc++.h>using namespace std;unordered_map<int,int> mp;int vis[10005];int n;bool isprime(int x){ if(x==1) return...
2019-11-12 10:47:30
86
原创 PAT(甲级)1123
题意：给出一组数据，将他们插入到AVL树中，答案输出AVL树的层序遍历以及它是否是完全二叉树。题解：一道显然的数据结构题，AVL树的四种旋转操作，树的插入，层序遍历，难点是如何判断完全二叉树，由于是层序遍历，如果遍历到一个空节点，那么它以后的节点应该全部为空，如果发现一个节点不为空，那么它就不是完全二叉树。注意点：数据结构写正确，四种旋转操作和插入要写正确，代码量较大。code in vie...
2019-11-12 10:28:56
107
原创 PAT(甲级)1038
题意：给出一些数字，前后拼接使得其值最小。题解：重写sort的cmp函数，快速排序的神奇应用。注意点：去掉前导零之后如果字符串为空则书输出0code in view#include<bits/stdc++.h>using namespace std;const int maxn=1e4+10;int n;string s[maxn];bool cmp(string a...
2019-11-11 23:14:38
64
原创 PAT(甲级)1146
题意：给一张图，给出一些遍历顺序，输出其中不满足拓扑排序的index。题解：一道拓扑排序的简单题，关键抓住出度与入度，当前点可以加入结果的条件是入度为0，跑一边图，判断点的入度是否为0，不为0则非法。注意点：基础25分题，注意细节即可。code in view// topological order#include<bits/stdc++.h>using namespace...
2019-11-11 20:17:16
110
原创 PAT(甲级)1145
题意：哈希–平方探测法，求数能否插入和数的平均查找次数。注意点：平均查找次数中平方项范围[0,size]，遇到空白的直接退出。code in view#include<bits/stdc++.h>using namespace std;const int maxn=1e4+10;int sz,n,m;int vis[maxn];bool isprime(int x){...
2019-11-11 20:10:57
166
原创 PAT(甲级)1144
题意：给一串数，找到最小的未出现的正整数。题解：注意数据范围只有100000个数，先给它从小到大排个序，找出最小的大于等于0的数a，从a前面的一个数开始，每次增加1，至多100000，肯定会出现没有出现过的正整数，由于数据int范围，可以map去保存。注意点：数组从1开始取，方便往前取1个时，a[0]正好是0.code in view#include<bits/stdc++.h>...
2019-11-11 20:06:47
102
原创 PAT(甲级)1122
题意：给出一张图，再给出M条路线，判断其是否是哈密顿圈(经过所有顶点不重复)。题解：三个判断：1.首尾两点要一样，2.长度为n+1，且除了出发点，其他所有的点必须只能出现1次，3.必须连成圈注意点：范围开大一点(205被卡了)code in view#include<bits/stdc++.h>using namespace std;const int maxn=2005;...
2019-11-11 19:59:35
61
原创 PAT(甲级)1121
题意：给出N对夫妇，再给出M个参加party的人，求出其中单身狗的个数。题解：map(unordered_map)容器的应用，将M个人中单身人数（除掉夫妇）+夫妇中只有一人出席的人数。注意点：注意序号从0开始，所以将序号+1，以防出现映射到0的情况，造成出错。code in view#include<bits/stdc++.h>using namespace std;con...
2019-11-11 19:54:00
140
原创 PAT(甲级)1147
题意：给出完全二叉树的层序排列，判断它是大根堆还是小根堆或者不是堆，再将原序列转为后序排列输出。题解：首先判断是不是堆，可以dfs看子节点与父节点的大小关系，或者直接for循环判断，层序转后序直接dfs一下即可。注意点：判断堆时逻辑关系要清楚，总体来说事一道简单的30分题。code in view// 层序转后序#include<bits/stdc++.h>using na...
2019-11-11 19:46:49
122
编译原理实验.zip
2020-01-13
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人