ACMerszl的博客

原创 搬家至博客园通知

博客搬家至博客园https://www.cnblogs.com/ACMerszl/

原创 图

原创 LeetCode 2039. 网络空闲的时刻

2039. 网络空闲的时刻Solution思路：一开始以为多源最短路径，但是n太大了，突然看到边权都是1，所以可以直接BFS，然后再根据每个点到源点的距离以及重发时间求最大即可。可以考虑三种情况：\(patience\ge2*distance\)：应为\(2*distance + 1\)\(patience<2*distance\)：至少为\(2*distance\)，然后...

原创 LeetCode 606. 根据二叉树创建字符串

606. 根据二叉树创建字符串Solution思路：最开始的思路就是简单的先序遍历，然后就可以得到带有空括号的字符串，再处理即可，代码都写了，然后发现有问题，还是在遍历的时候控制比较好，然后就开始无脑乱改，发现逻辑是通的，不过代码已经成狗屎了，删了重新写，梳理逻辑，1Y主要是叶节点和非叶节点的)，应该是叶节点不处理， 统一回退处理，然后存在孩子之一必有(，然后就是转右孩子的细节)(cla...

原创 LeetCode 397. 整数替换

397. 整数替换Solution思路：BFS或者DFS，但是最大范围是2^31-1，会超出int的最大范围。还可以进行记忆化搜索。题解中面对奇数的情况，可以等效为2步到达偶数，即\(2+Math.min(dfs(\frac{val +1}{2},dfs(\frac{val-1}{2}))\)，这里加一可能越界，所以可以对应变为\(\lfloor\frac{val}{2}\rfloor+1\...

原创 LeetCode 102. 二叉树的层序遍历

102. 二叉树的层序遍历Solution思路：搞一个深度，然后放到对应的层次里。这里开List嵌套的时候有点坑，不过根据list的容量大小和层次的高度关系，来进行创建。这里的NewNode不能共用。题解代码是 用for循环搞出来那一层的。普通的BFS是弹出一个。见下面代码二。///代码一class Solution { public List<List<Intege...

原创 LeetCode 20. 有效的括号

20. 有效的括号Solution思路：左边入栈，遇到右边判断即可，最后看堆栈是否为空。class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); char[] str = s.toCharArray()...

原创 LeetCode 3. 无重复字符的最长子串

3. 无重复字符的最长子串Solution思路：刚开始考虑是map记录下标，然后重复的话就看map的下标位置，得到极大子串的长度，但是没有考虑到这个过程中是可以维护出不重复的字串的，通过几个样例模拟，然后就以为map只是一开始用到了，后面都是靠的下标去得到子串长度，不删除的话还不好维护，没往删除上面考虑，然后感觉意义不大。看了题解，MD很接近了。从左开始枚举起点，整个过程中子串右端点不断递增...

原创 LeetCode 2. 两数相加

2. 两数相加Solution思路：模拟。自己的写法是两个一起循环，其中一个结束就停止循环，再处理另一个链表，不过也可以一直循环，但是可以直接连接过去，然后就是考虑进位。//class ListNode {// int val;// ListNode next;// ListNode() {}// ListNode(int val) { this.val = val; }...

原创 LeetCode 1. 两数之和

1. 两数之和Solution思路1：直接双重for循环，枚举每个数字，找到后返回结果class Solution { public int[] twoSum(int[] nums, int target) { int len = nums.length; for (int i = 0; i < len; i++) { ...

原创 LeetCode 540. 有序数组中的单一元素

540. 有序数组中的单一元素Solution思路：异或遍历一遍，相同数字异或为0，异或结果即为单个数字的值。时间复杂度O(n)class Solution { public int singleNonDuplicate(int[] nums) { int m = nums.length; int ans = 0; for (int ...

原创 LeetCode 1380. 矩阵中的幸运数

1380. 矩阵中的幸运数Solution思路：自己的思路就是遍历两遍数组，然后另开计数数组，如果同一个位置被计两次，则为幸运数。时间复杂度和空间复杂度都是O(mn)，看了题解是可以在遍历的时候直接判断的，时间复杂度为O(mn*(m+n)，空间复杂度为O(1)，因为不需要另开保存结果。还有一个方法是保存行的最大值和列的最小值，判断数组的值是否与两个都相等。时间复杂度为O(mn)，空间复杂度为...

原创 LeetCode 1765. 地图中的最高点

1765. 地图中的最高点Solution思路：开始的思路是直接把水域固定，然后扩散，但是扩散的方式不对，我是默认一圈的最小值直接加1，但是会出现问题，正确做法多源BFS，就是全部默认为-1，然后从水域开始做BFS，如果遇到不是-1的格子，说明一定是从之前的水域出发了，所以不能重复更新，不然就不满足要求了。class Solution { int[][] dir = {{0, 1}...

原创 LeetCode 1996. 游戏中弱角色的数量

1996. 游戏中弱角色的数量Solution思路：见过类似的，就知道是排序。需要满足都是小于，才算是一个弱角色。因此可以按照攻击降序排序，那么就保证了攻击是满足了，不过要实现防御也要小于，就需要攻击相同时，按照防御升序排列，如果出现当前防御比之前角色小的，那么一定是攻击值不一样且之前的更大的角色。class Solution { public int numberOfWeakCh...

原创 LeetCode 1725. 可以形成最大正方形的矩形数目

1725. 可以形成最大正方形的矩形数目Solution思路：就直接遍历一遍，哈希表记录每个矩形的最大边的次数，同时维护最大值即可。class Solution { Map<Integer, Integer> sides = new HashMap<Integer, Integer>(); public int countGoodRectangles...

原创 LeetCode 1748. 唯一元素的和

1748. 唯一元素的和Solution思路：看值域范围非常小，可以直接数组存值，就数组记录出现次数即可。class Solution { public int sumOfUnique(int[] nums) { int len = nums.length; int[] cnt = new int[100 + 1]; for (int...

原创 LeetCode 1219. 黄金矿工

1219. 黄金矿工Solution思路：第一个想法是有点类似数塔dp的感觉，但是这里的起点是随机，而且规模不大，所以可以逐个枚举起点，然后dfs搜索即可。长时间不写，判断新点是否可行时，传入了旧的点，人麻了。class Solution { int ans = 0; int[][] grids; int[][] dir = {{0, -1}, {0, 1}, {-...

原创 LeetCode 2013. 检测正方形

2013. 检测正方形Solution思路：和我的思路大概一致，我想的是枚举同一行，题解是枚举同一列，因为确定一个点，长度有了，其他的点也就确定。因此枚举查询点同一列的点，然后距离有了，就在这两个高度的行中找对应的点是否存在。class DetectSquares { Map<Integer, Map<Integer, Integer>> cnt; ...

原创 LeetCode 2047. 句子中的有效单词数

2047. 句子中的有效单词数Solution思路：简单模拟题，首先将单词划分开，然后根据条件一个一个否定即可。标记连接符和标点符号的位置，进行判断，这里注意特判是在数值为1的时候做的。class Solution { public int countValidWords(String sentence) { String[] words = sentence.sp...

原创 LeetCode 2045. 到达目的地的第二短时间

2045. 到达目的地的第二短时间Solution思路：求路径 然后再根据路径的长度算时间。这里使用BFS来维护最短路和次短路，然后根据次短路的长度来计算总时间。class Solution { public int secondMinimum(int n, int[][] edges, int time, int change) { List<Integer...

原创 LeetCode 2034. 股票价格波动

2034. 股票价格波动Solution思路一：有序集合+哈希表查询最新股票价格：维护最大的时间戳 哈希表直接查询。最高，最低价格查询：维护股票价格的有序集合。由于存在不同时间戳有相同的股票价格，因此股票价格需要记录出现次数，更新的时候维护即可。class StockPrice { int curTimestamp; HashMap<Integer, Integ...

原创 LeetCode 1345. 跳跃游戏 IV

1345. 跳跃游戏 IVSolution思路：看到题目后，发现转化为无向图就可以了。然后就以为没事了，发现大意了，因为重复的值可能有很多，导致图非常的稠密，最后会导致TLE，这里学习了可以去子图的方法，因为相等的值会在第一次进去子图时将其他的点都入队，不需要遍历其他点时再进入该子图，因此可以将该值去除，防止重复进入。class Solution { public int min...

原创 LeetCode 1332. 删除回文子序列

1332. 删除回文子序列Solution思路：回文子序列 所以最多两次，如果一开始就是回文串的话 就是一次。class Solution { public int removePalindromeSub(String s) { int i =0, j = s.length() - 1; while (i < j) { ...

原创 LeetCode 2029. 石子游戏

2029. 石子游戏 IXSolution自己思路：一开始也是分类讨论了，不过是从价值是3的倍数的数字的个数和总和是否是3的倍数来讨论的。正确思路：首先3的倍数的数字就是双方交替的。但是由于取完也会是Bob获胜，所以这里要讨论3的倍数cnt0的个数的奇偶性。同时要对非3的倍数细分，分为余数为1的cnt1的个数和余数为2cnt2的个数。cnt0为偶数时，等同于没有：Alice先...

原创 LeetCode 219. 存在重复元素 II

219. 存在重复元素 IISolution思路1：重复元素 然后就用HashMap不断更新最新出现的位置 与k值判断即可。class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer, Integer> mp = new HashMap...

原创 LeetCode 539. 最小时间差

539. 最小时间差Solution思路：将所有时间字符串排序后 最小时间只可能是 前后相邻时间 和 首位时间。1440可以剪枝处理，因为24*60。class Solution { public int findMinDifference(List<String> timePoints) { if (timePoints.size() > 14...

原创 二分总结

二分总结参考链接左闭右开求下界 上界用下界转化左右区间的变化重点是左右区间怎么扩张？求第一个大于等于3的位置(蓝色右边界取不到，紫色左边界取得到)\(a[mid]=3\)，右边必定都是\(\geq3\)的，所有要把紫色最大限度扩张\(last=mid\)，即更新后的\(last[last,last_0]\geq3\)\(a[mid]=0\)，左边必定是\(<3\)的...

原创 LeetCode 400. 第 N 位数字

传送门Solution首先找规律可以看出来每个位数\(digit\)的数字位数之和为\(sum_{digit}=digit*10^{digit-1}*9\)，所以可以处理出第\(n\)位所在的数字\(value\)，根据数字位数之和与\(n\)的关系，可以得出\(value\)的位数\(digit\)，所以可以计算出\(digit-1\)以及之前的数位之和，根据\(digit\)位数又能确定...

原创 LeetCode 438. 找到字符串中所有字母异位词

传送门Solution思路1：滑动窗口。维护窗口内字符的数量，判断与\(p\)字符串数量是否相等。复杂度\(O((sLen-pLen)*26)\)class Solution { public List<Integer> findAnagrams(String s, String p) { int sLen = s.length(), pLen = p...

原创 496. 下一个更大元素 I

Solution思路1：暴力class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { int[] ans = new int[nums1.length]; int cur = 0; for (int x: nums1) { ...

原创 240. 搜索二维矩阵 II

Solution思路1：暴力搜索class Solution { public boolean searchMatrix(int[][] matrix, int target) { for (int[] row: matrix) { for (int x : row) { if (x == target) ...

原创 java反射之ObjectAnalyzer

java反射之ObjectAnalyzer1 在运行时使用反射分析对象查看对象域的关键方法是Field类中的get方法，如果f是一个Field类型的对象，obj是某个包含f域的类的对象，f.get(obj)将放回一个对象，其值为obj域的当前值。Employee harry = new Employee("Harry Hacker", 35000, 10, 1, 1989);Class ...

原创 Codeforces Round #633 (Div. 2)

SolutionsA. Filling Diamonds通过猜测就欧克了。发现如果竖直放置就只有一种摆放方法了。#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define all(x) (x).begin(), (x).end()#de...

原创 Codeforces Round #634 (Div. 3)

SolutionsA. Candies and Two Sisters直接\(\frac{x-1}2\)#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define all(x) (x).begin(), (x).end()#define ...

原创 Codeforces Round #635 (Div. 2)

SolutionsA. Ichihime and Triangle直接让三边是\(a,c,c\)即可#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define all(x) (x).begin(), (x).end()#define fi...

原创 背包dp总结

背包dp总结背包每次写每次都不会，再次又学习了基础的背包，后面的遇到再补吧01背包首先对于每种物品可以取后者不取，所以我们可以写出记忆化的代码\(dp[pos][val]\)表示容量为\(val\)，选后\(pos\)个物品的最大价值每种物品取或不取，然后暴搜记忆化int V, n;int w[110];int c[110];int dp[1010][1010]; ...

原创 POJ3764 The xor-longest Path

题意：找出树上异或和最大的一条路径\(p\)\[_{xor}length(p)=\oplus_{e\in_p}w(e)\]01字典树。同样用到了简单的异或性质\(0\oplus a = a, a\oplus a = 0\)定义\(f(u,v)\)为\(u\)到\(v\)的路径异或和。那么\(f(u,v) = f(1,u)\oplus f(1,v)\)所以我们可以\(d...

原创 BZOJ4260 Codechef REBXOR

题意：给出一个含\(N\)个元素的数组\(A\)，下标从\(1\)开始，请找出下列式子的最大值：\[(A[l_1]\oplus A[l_1+1]\oplus\dots\oplus A[r_1])+(A[l_2]\oplus A[l_2+1]\oplus\dots A[r_2])\]其中\(1\leq l_1 \leq r_1 < l_2 \leq r_2\leq N\)...

原创 HDU5536 Chip Factory

题意：给出一个数组\(s\)，求\[max_{i,j,k}(s_i + s_j)\oplus s_k ,i\neq j\neq k\]思路：01字典树，首先还是正常插入。可以想到枚举\(i\)、\(j\)的和，再字典树跑\(k\)，这里涉及下标不能相同，所以可以把\(i\)、\(j\)，先删除了。在插入的时候计数\(cnt[u]++\)，删除就依次把到达的各点\(cnt[u]...

原创 HDU4825 Xor Sum

题意：询问\(m\)次，每次给出一个正整数\(k\)，求数组中和他异或的最大值。思路：01字典树裸题，……但是我不会，特意学习一下。顺便回忆一下字典树首先把数组中的每一个数，二进制存到字典树中，从高位开始，然后每次询问从上往下跑，尽量0走1，1走0。注意数组的大小，-_-!!!!#include<bits/stdc++.h>using namespace std...