- 博客(265)
- 收藏
- 关注
RSS订阅原创 PAT.1143 Lowest Common Ancestor
给定一棵BST的前序遍历，根据若干查询给出两节点的最低公共祖先（Lowest Common Ancestor）。还是一贯的套路，根据前序中序建树，然后从根开始同时搜索两个节点，找到分叉点即可。
2022-09-16 16:58:58
464
1
原创 PAT.1139 First Contact
a如果喜欢b，需要找一个自己的同性朋友c去联系一个b的同性朋友d，同时要求cd为朋友，给定图和若干查询，求每个查询下所有可能的{c,d}。基于图的题目一开始想到的还是那老几样————各种搜索和最短路算法，显然这道题就是要求顶点ab之间的一条长度为3的路径，同时对cd两顶点的性别作出要求。
2022-09-15 20:04:48
290
原创 PAT.1135 Is It A Red-Black Tree
哈哈，红黑树。第一眼看过去被吓到了，还以为要把红黑树的几个基本操作都写出来。定睛一看发现还是一道建树的题，只不过建完树要根据红黑树的定义判断一下当前树是不是红黑树。这道题可以建树的基本前提是，红黑树是一种特殊的二叉搜索树，所以仍然保有中序有序的性质，因此给定前序遍历的同时可以通过排序得到中序遍历。递归建树的过程自然不必多说，这道题唯一的特点无非就是红黑树的判断。根节点必须为黑、所有节点非红即黑、所有Null节点为黑这三点的难度约等于没有。
2022-09-15 14:35:47
222
原创 PAT.1127 ZigZagging on a Tree
哈哈，又是树。最近老是遇到树，对于自底向上递归建树的策略已经熟稔了。题目给出树的中序遍历和后序遍历，要求你确定这棵树，然后给出这棵树的zigzag遍历（正如其名，就是从左到右、从右到左如此往复的层序遍历）。想想一般情况下的层序遍历用队列就可以很容易实现，那现在要两边整了————那就用deque吧。这样就可以看出来，zigzag层序遍历的实现仅仅在于pop的方向和push的先后以及push的方向，因此我们只要设置一个标志位，在两种状态间来回转换就可以了。
2022-09-08 12:21:18
139
原创 PAT.1067 Sort with Swap(0, i) - 基于连通性思考的贪心求解
PAT.1067 Sort with Swap(0, i) - 基于连通性思考的贪心求解题目链接 题目给定一组0的数N-1，要求每步只能交换0和一另外的数，问使得数组中每个值为i的数都在下标为i的位置最小需要几步。 首先从贪心的角度思考每一步如何交换能使得解法最优。 很容易想到，若0在下标为i的位置，那么就将0与值为i的数交换，经过这样一步交换，0会处在先前值为i的数所在的位置，然后0根据此前的策略不断地与值和自身所在下标相等的数交换位置。由此可见这个过程是传递性的，0可以不断的交换，且每步
2022-04-21 15:25:18
224
原创 PAT.1066 Root of AVL Tree - AVL树的构造
PAT.1066 Root of AVL Tree - AVL树的构造题目链接题目给出插入顺序，要求根据插入顺序构建AVL树，并给出AVL树最终的根。一下子想不到什么取巧的办法，老老实实构建AVL树吧。趁机复习一下AVL树的概念：AVL树是一种二叉排序树，且在插入的过程中通过旋转操作来实现平衡(即以任一节点为根，其左子树深度与右子树深度的差之绝对值不超过1)顺便再复习一下旋转的概念：旋转往往发生在形如(此处以RR失衡为例) root \ child1 \ child
2022-04-20 16:03:31
852
原创 PAT.1064 Complete Binary Search Tree - 二叉树的中序遍历与层序遍历
PAT.1064 Complete Binary Search Tree - 二叉树的中序遍历与层序遍历题目链接题干的意思是给你一个数组，根据数组建立一个完全的二叉搜索树，并打印其层序遍历。首先趁这个机会复习一下BST和CST的概念：通俗理解BST即是左子树中所有节点小于根节点，右子树中所有节点大于根节点的二叉树CST即是一棵完全二叉树，并在最底层从左填充若干节点的二叉树。根据题目给出的数列很容易想到预处理成升序，因为BST的中序遍历是升序的，得到中序遍历后我们要想办法将其向层序遍历转化。
2022-04-16 17:28:47
1110
原创 PAT.1057 Stack
PAT.1057 Stack题目链接看到题，是个提供能求中位数的栈，好哇直接模拟，然后超时。一开始想到的方法使用multiset来维护栈内数据，然后通过迭代器来获取中位数，但这样实质上效率很差。于是看了一些别人的解法，发现树状数组可以做，但是呢，我不会树状数组，付出了代价。后来看到了用multiset维护两段数据的写法，链接。于是按照这个思路写出了题解：用upper维护大于中位数的元素，用lower维护小于等于中位数的元素，两者都是multiset，begin()指向贴近中位数的数，每次栈中元素
2022-04-08 18:44:58
180
原创 PAT.1044 Shopping in Mars - 前缀和+二分查找
PAT.1044 Shopping in Mars - 前缀和+二分查找题目链接这道题让我们在给定的数列找找到和为某个值的子序列，并按左界升序输出，如果不存在这样的子序列，就按左界升序输出和大于且最接近给定值的子序列。首先想到可以用前缀和来预处理数据，然后枚举左右界检查和是否符合条件。然后呢?然后发现这样会超时，仔细一看题干，限时300ms。没办法，既然前缀和本身是递增的（给定数列所有数为正数），所以可以枚举左界然后对右界进行二分查找。题解#include<bits/stdc++.h&
2022-03-25 14:12:09
177
原创 PAT.1033 To Fill or Not to Fill
PAT.1033 To Fill or Not to Fill题目链接说实话一上来看到题目就觉得是动态规划，然后就写了，写完发现并过不了，在局部最优解上欠考虑。于是转向贪心，只要梳理清楚根本的思路这道题还是很简单的：寻找满油范围内可达的比当前油价低的站点，如果有就加刚好够用的油量前往，如果没有就尽可能寻找可达范围内价格较低的站，并在当前站把油加满。动态规划？那么dp行不行呢？我一开始将状态dp[i]设计为恰好到达第i个站点时花费的最少油钱，但这样写是不行的，因为在当前站点油价为续航范围内最低时要加
2022-03-15 14:53:41
521
原创 PAT.1030 Travel Plan - Dijikstra
PAT.1030 Travel Plan - Dijikstra题目链接思路和PAT.1018基本是一样的，先Dijikstra求所有可能的最短路，然后dfs求所有最短路里代价最小的一条。题解#include<bits/stdc++.h>using namespace std;typedef long long ll;struct city{ int num; int dis; bool operator < (const city &a)
2022-03-11 14:15:46
112
原创 PAT.1029 Median - 双指针
PAT.1029 Median - 双指针题目链接给两个不减序列，求两序列中位数，类似这种数据分散在两个结构里的问题可以用双指针来维护当前次序元素的位置，以此避免数据合并或排序的开销。题解#include<bits/stdc++.h>using namespace std;typedef long long ll;long nums1[200005],nums2[200005],num;int n,k,ptr1,ptr2,totalCnt,target;int main(
2022-03-10 13:34:45
78
原创 PAT.1022 Digital Library
PAT.1022 Digital Library题目链接一道很没意思的模拟题，基本没什么易错点，可以趁机熟悉一下各种输入的处理。getline获取整行输入，转stringstream通过空格划分，这里从字节流读出的时候末尾会有一个空字符，这里原理暂且不谈，注意忽略掉就可以。题解#include<bits/stdc++.h>using namespace std;typedef long long ll;//书名，作者，出版商，出版年，关键词map<string,vec
2022-03-05 16:21:34
149
原创 PAT.1021 Deepest Root - 并查集判断连通性，dfs搜索图
PAT.1021 Deepest Root - 并查集判断连通性，dfs搜索图题目链接看到题干，第一眼1e4的数据，如果用邻接矩阵1e8必爆，于是改用邻接表，然后就是在存路的时候顺便用并查集判断连通性，然后就是遍历每个点用dfs判断该点的最大深度。一开始测试点2怎么都不过，网上也查不到关于测试点2的问题，结果仔细检查之后发现是把if(getAnc(l) != getAnc(r))写成了if(getAnc[l] != getAnc[r])，乐了。似乎还可以加一个度判断的条件，只有度为1（只有一个点的情
2022-03-04 15:05:13
88
原创 PAT.1018 Public Bike Management - 不只是Dijikstra
PAT.1018 Public Bike Management - 不只是Dijikstra题目链接看到题目非常亢奋，我超，Dijikstra，然后越写越不对劲，似乎没法确保在求最短路的过程中保证出发带车量也是最少的，在不想大量修改代码的情况下在结构体里加入了站点原有车数，然后在优先队列里按距起点距离升序排列，等距按原有车数降序排列。显然这样试过不了的，测试点67直接寄（这个处理办法没法解决路线上多个车量大于一半的站点）。那没办法，只能抛弃在Dijikstra的过程中顺便求最少带车量的想法，用pre
2022-03-02 17:26:52
84
原创 PAT.1015 Reversible Primes
PAT.1015 Reversible Primes题目链接素数打表，然后判断正反数是否是素数即可，趁这个机会复习一下筛法求素数。题解#include<bits/stdc++.h>using namespace std;typedef long long ll;int n,d;bool isntPrime[100005];vector<int> primeList;deque<int> num;int main(){ isntPrime
2022-02-28 16:20:03
74
原创 PAT.1014 Waiting in Line - 模拟
PAT.1014 Waiting in Line - 模拟题目链接题干很长，但读下来很容易发现就是一道模拟题，思路就是每个队伍有一定容量，后来的人优先去人少的队伍排队，一样多就去下标小的队伍。由于队伍在发生变化的时候即为队列中有人被服务完的时候，所以用deque来维护队列的状况，方便检查队首人的结束时间，也方便计算进入队列的人的结束时间。另外，关于17:00前被服务到但服务在17:00后结束的人究竟算不算数，其实题干里明确写了"for those customers who cannot be se
2022-02-28 15:42:07
67
原创 PAT.1013 Battle Over Cities - 并查集
PAT.1013 Battle Over Cities - 并查集题目链接一开始的想法是判定所有节点是否在环上，如果查询节点不在环上答案就是相连路径数-1，如果在环上就是0，对应就用删除叶子节点的算法来标记。然后发现这样写比较麻烦，于是干脆对每次查询都用一次并查集来判断剩余连通分量的个数，答案就是删去目标节点后连通分量个数-1。题解把路径压缩放在getAnc函数里，同时将每个节点的初始最大祖先设为自己而非0，避免了以前用大量if的写法。#include<bits/stdc++.h>
2022-02-27 16:31:54
76
原创 PAT.1003 Emergency - Dijikstra
PAT.1003 Emergency - Dijikstra题目链接还就那个很久没写算法题，今天开始刷一下PAT甲级题库，权当复健。不想写Dijikstra这样写的问题在于由于起点是不定的，按照路的顺序遍历可能导致当前两个点都不可达，因此在遍历到起点相关的路之前的路会全部作废，（而且忽略了双向的问题）#include<bits/stdc++.h>using namespace std;typedef long long ll;int cityCnt,roadCnt,start
2022-02-22 18:41:05
150
原创 leetcode 剑指 Offer 22. 链表中倒数第k个节点
leetcode 剑指 Offer 22. 链表中倒数第k个节点题干输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。示例：给定一个链表: 1->2->3->4->5, 和 k = 2.返回链表 4->5.知识点&算法链表取倒很容易想到快慢指针的做法，这里因为
2021-09-02 22:16:31
59
原创 leetcode 165.比较版本号
leetcode 165.比较版本号题干给你两个版本号 version1 和 version2 ，请你比较它们。版本号由一个或多个修订号组成，各修订号由一个 ‘.’ 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值
2021-09-01 16:57:44
68
原创 leetcode 1109.航班预订统计
leetcode 1109.航班预订统计题干这里有 n 个航班，它们分别从 1 到 n 进行编号。有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。示例 1：输入：bookings
2021-08-31 12:45:46
81
原创 Java使用正则表达式时的二次转义问题
众所周知，反斜杠在Java里用作转义符。而在正则表达式中，当我们需要匹配诸如 [ ] 等特殊字符时，也需要用反斜杠进行转义。举个例子，假如我要匹配字符串"[哈哈哈]"两个方括号中间的内容时，按照一般的习惯，可以写出正则表达式(?<=[).+(?=])但这个表达式如果直接放到Java中进行matcher会出问题，因为[和]不是Java自身定义的转义字符，在读入时会忽略反斜杠，原本正常的正则表达式就变成了(?<=[).+(?=])。因此我们需要在正则表达式中使用转义符并在Java中使用时，反
2021-08-10 16:06:00
413
原创 leetcode 525.连续数组 - 前缀和 + 哈希表
leetcode 525.连续数组 - 前缀和 + 哈希表题干给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。示例 1:输入: nums = [0,1]输出: 2说明: [0, 1] 是具有相同数量0和1的最长连续子数组。示例 2:输入: nums = [0,1,0]输出: 2说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。提示：1 <= nums.length <= 105nu
2021-06-03 15:34:17
106
原创 leetcode 523.连续的子数组和 - 前缀和 + 哈希
leetcode 523.连续的子数组和 - 前缀和 + 哈希题干给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：子数组大小 至少为 2 ，且子数组元素总和为 k 的倍数。如果存在，返回 true ；否则，返回 false 。如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。示例 1：输入：nums = [23,2,4,6,7], k = 6输出：true解释：[2,4] 是
2021-06-02 20:25:46
82
原创 leetcode 1744.你能在你最喜欢的那天吃到你最喜欢的糖果吗？
leetcode 1744.你能在你最喜欢的那天吃到你最喜欢的糖果吗？题干给你一个下标从 0 开始的正整数数组 candiesCount ，其中 candiesCount[i] 表示你拥有的第 i 类糖果的数目。同时给你一个二维数组 queries ，其中 queries[i] = [favoriteTypei, favoriteDayi, dailyCapi] 。你按照如下规则进行一场游戏：你从第
2021-06-01 22:08:17
80
原创 leetcode 342.4的幂 - 位运算
leetcode 342.4的幂 - 位运算题干给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x示例 1：输入：n = 16输出：true示例 2：输入：n = 5输出：false示例 3：输入：n = 1输出：true提示：-231 <= n <= 231 - 1进阶：你能不使用循环或者递归来完成本题吗？知识点&算法遍历，掩码
2021-05-31 21:39:24
77
原创 Springboot + mybatis-plus 从入门到入土(210530更新)
Springboot + mybatis-plus 从入门到入土顺带一提的git从url克隆到本地git clone urlpush到远程仓库git init //初始化本地仓库git add . //将目录下所有文件添加到本地仓库git commit -m "注释" //将项目提交到本地git仓库git push 远程仓库名 分支名关于关联远程仓库git remote add 远程仓库名 url //url.git结尾Springboot注解@RequestBody用在
2021-05-30 22:55:32
63
原创 leetcode 1074.元素和为目标值的子矩阵数量 - 前缀和
leetcode 1074.元素和为目标值的子矩阵数量 - 前缀和题干给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。如果 (x1, y1, x2, y2) 和 (x
2021-05-29 22:03:08
103
原创 leetcode 461.汉明距离 - 位运算
leetcode 461.汉明距离 - 位运算题干两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y，计算它们之间的汉明距离。注意：0 ≤ x, y < 231.示例:输入: x = 1, y = 4输出: 2解释:1 (0 0 0 1)4 (0 1 0 0)↑ ↑上面的箭头指出了对应二进制位不同的位置。知识点&算法题解先统计两个数从低到高相异的位数，然后统计剩下的1。class Solution {pu
2021-05-27 19:34:13
57
原创 leetcode 1190.反转每队括号间的子串
leetcode 1190.反转每队括号间的子串题干给出一个字符串 s（仅含有小写英文字母和括号）。请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。注意，您的结果中 不应 包含任何括号。示例 1：输入：s = “(abcd)”输出：“dcba”示例 2：输入：s = “(u(love)i)”输出：“iloveu”示例 3：输入：s = “(ed(et(oc))el)”输出：“leetcode”示例 4：输入：s = “a(bcdefghi
2021-05-26 18:55:23
64
原创 codeforces A. MEX maximizing
codeforces A. MEX maximizing题干Recall that MEX of an array is a minimum non-negative integer that does not belong to the array. Examples:for the array [0,0,1,0,2] MEX equals to 3 because numbers 0,1 and 2 are presented in the array and 3 is the minimum n
2021-05-25 21:12:10
156
原创 leetcode 664.奇怪的打印机 - 动态规划
leetcode 664.奇怪的打印机 - 动态规划题干有台奇怪的打印机有以下两个特殊要求：打印机每次只能打印由 同一个字符 组成的序列。每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。示例 1：输入：s = “aaabbb”输出：2解释：首先打印 “aaa” 然后打印 “bbb”。示例 2：输入：s = “aba”输出：2解释：首先打印 “aaa” 然后在第二个位置打印 “b” 覆盖掉原来
2021-05-24 15:02:02
96
原创 leetcode 1707.与数组中元素的最大异或值 - 字典树 + 贪心
leetcode 1707.与数组中元素的最大异或值 - 字典树 + 贪心题干给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。返回一
2021-05-23 20:19:27
120
原创 leetcode 692.前K个高频单词
leetcode 692.前K个高频单词题干给一非空的单词列表，返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。示例 1：输入: [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2输出: [“i”, “love”]解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。注意，按字母顺序 “i” 在 “love” 之前。示例
2021-05-20 13:09:55
79
原创 leetcode 1738.找出第K大的异或坐标值 - 前缀和
leetcode 1738.找出第K大的异或坐标值 - 前缀和题干给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。示例 1：输入：
2021-05-19 18:39:13
100
原创 leetcode 1442.形成两个异或相等数组的三元组数目 - 前缀和
leetcode 1442.形成两个异或相等数组的三元组数目 - 前缀和题干给你一个整数数组 arr 。现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。a 和 b 定义如下：a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]注意：^ 表示 按位异或 操作。请返回能够令 a == b 成立的三元组 (i,
2021-05-18 15:53:23
91
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人