在这里要嘚瑟一下，5/25号的力扣夜猫赛，4道题都过了，第一次ak，太兴奋了，感觉这一年多的付出有了收获。从当年的完全小白到现在哪怕是运气好但是能够ak，也付出了很多时间精力吧。当然了一次ak只不过是加深了我的荣誉感和幸福度。我知道代表不了什么，可能下次依然只能1,2,3题。我只是更加确信：付出终有回报，努力不会欺人。
好了，闲话少叙，继续今天的刷题。
形成两个异或相等数组的三元组数目
题目：给你一个整数数组 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, j , k) 的数目。
示例 1：
输入：arr = [2,3,1,6,7]
输出：4
解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)
示例 2：
输入：arr = [1,1,1,1,1]
输出：10
示例 3：
输入：arr = [2,3]
输出：0
示例 4：
输入：arr = [1,3,5,7,9]
输出：3
示例 5：
输入：arr = [7,11,12,9,5,2,7,17,22]
输出：8
提示：
1 <= arr.length <= 300
1 <= arr[i] <= 10^8
思路：这个题怎么说呢，首先a==b。也就是a ^ b 会等于0.然后这个三元组形成的大前提就是从i到k下标异或的结果是0。而且这个数据范围才300.我觉得暴力法就能破解。思路很清晰，我去代码实现。
讲真，这个题有毒吧？说好了的三元数组，结果两个数居然也可以。我简直了。。。然後用的双层循环。我要先附上第一版代码，虽然是错误的，但是原因是第一版代码一定要三个数才算解。其实正确答案去掉这个限制就行了:
class Solution {
public int countTriplets(int[] arr) {
int ans = 0;
for(int i = 0;i<arr.length-2;i++) {
int temp = arr[i]^arr[i+1];
for(int j = i+2;j<arr.length;j++) {
temp ^= arr[j];
if(temp == 0) {
//起始是i，结束是k，中间任何元素都可以当j。所以中间元素数就是可能数
ans += (j-i);
}
}
}
return ans;
}
}
去掉限制的正确代码：
class Solution {
public int countTriplets(int[] arr) {
int ans = 0;
for(int i = 0;i<arr.length-1;i++) {
int temp = arr[i];
for(int j = i+1;j<arr.length;j++) {
temp ^= arr[j];
if(temp == 0) {
//起始是i，结束是k，中间任何元素都可以当j。所以中间元素数就是可能数
ans += (j-i);
}
}
}
return ans;
}
}
这个题就这样了，比较简单，主要是知道如何计算可能数（x-y总结果是0，那么任何节点断开，两段异或都是0.所以可能数是x-y中间的元素数。所以是j-i）。这个理解了这个题就没啥难的，下一题。
找出第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：
输入：matrix = [[5,2],[1,6]], k = 1
输出：7
解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。
示例 2：
输入：matrix = [[5,2],[1,6]], k = 2
输出：5
解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。
示例 3：
输入：matrix = [[5,2],[1,6]], k = 3
输出：4
解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。
示例 4：
输入：matrix = [[5,2],[1,6]], k = 4
输出：0
解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
0 <= matrix[i][j] <= 106
1 <= k <= m * n
思路：这个题咋说呢，读了好几遍题目才懂了题意。我的想法是用一个二维数组压缩。第一次记录每一列/行的异或结果。然后第二遍遍历记录每一行的异或结果。这样就获取所有可能的a，b的结果了。有点类似dp。然后排序，获取第k个值。思路差不多是这样，我去实现下试试。
第一版代码：
class Solution {
public int kthLargestValue(int[][] matrix, int k) {
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m + 1][n + 1];
List<Integer> ans = new ArrayList<Integer>();
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1] ^ matrix[i - 1][j - 1];
ans.add(dp[i][j]);
}
}
ans.sort((i1,i2)->{return i2-i1;});
return ans.get(k - 1);
}
}
做的时候我还觉得我用到了dp，以为能不错。结果发现ac是ac了。但是性能低空略过，然后我觉得是m*n的时间复杂度是不可能再少了的。能优化的点也就是排序这块了。。然而我没啥思路。所以直接去看性能第一的代码吧：
class Solution {
public int kthLargestValue(int[][] matrix, int k) {
final int N = (matrix == null) ? 0 : matrix.length;
final int M = (N == 0) ? 0 : matrix[0].length;
int[][] xor = new int[N + 1][M + 1];
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
xor[i + 1][j + 1] = matrix[i][j] ^ xor[i][j + 1] ^ xor[i + 1][j] ^ xor[i][j];
}
}
int idx = 0;
int[] nums = new int[N * M];
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
nums[idx++] = xor[i][j];
}
}
return quickSelect(nums, 0, nums.length - 1, nums.length - k + 1);
}
private int quickSelect(int[] nums, int start, int end, int k) {
if (start == end) {
return nums[start];
}
int left = start;
int right = end;
int pivot = nums[start + (end - start) / 2];
while (left <= right) {
if (nums[left] < pivot) {
left++;
} else if (nums[right] > pivot) {
right--;
} else {
int temp = nums[left];
nums[left++] = nums[right];
nums[right--] = temp;
}
}
if (start + k - 1 <= right) {
return quickSelect(nums, start, right, k);
}
if (start + k - 1 >= left) {
return quickSelect(nums, left, end, start + k - left);
}
return nums[right + 1];
}
}
思路没啥问题，优化点也确实在排序上。我用的list。这里用了数组来存储。然后用了一个方法来获取第k个元素的值。重点应该是在这个排序上吧。反正这个题就这样了，下一题。
根据前序和后序遍历构造二叉树
题目：返回与给定的前序和后序遍历匹配的任何二叉树。pre 和 post 遍历中的值是不同的正整数。
示例：
输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]
提示：
1 <= pre.length == post.length <= 30
pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列
每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。
思路：这个题咋说呢，但凡带个中序就能确定一棵树了。问题是只有前序后序排列。所以其实应该是无法确定一棵树了。这里简单说下前序中序后序的顺序：前序：根，左，右。 中序：左，根，右。后序：左，右，根。然后现在给定是是前序和后序。所以知道了根左右和左右根。但是之所以说前后确定不了唯一的一棵树的原因也是这：左右子树的界限是不清楚的。继续说这个题目：因为左右节点的顺序是不会变的。不管是根左右还是左右根，起码都保证了左右节点的顺序不变。而且根的位置是从前到后了。所以我们可以判断当前pre中当前节点和post中节点的位置。如果说这个元素位置相对往后移动了。说明这个节点是一个根节点。然后如果是子节点上一层根节点，则只会往后移动两步。注意我说的不是相对位置。是指原本在他之后，结果在他之前的元素。比如上面demo中的本来是2,4,5.后序变成4.5，2.也就是两个元素提前面去了。同理1也是这样的。本来后面2-7.结果因为上述第二次，所以2乘3个元素到前面了。当然我这个思路是要都是完整的二叉树。我慢慢去代码试试吧。
第一版代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode constructFromPrePost(int[] pre, int[] post) {
return dfs(pre,post);
}
public TreeNode dfs(int[] pre, int[] post) {
int len = pre.length;
if(len == 0) return null;
// 根节点比较好确定。前序第一个和后序最后一个。
TreeNode ans = new TreeNode(pre[0]);
if (len == 1) return ans;
// 前序第二个元素是左子树根节点。后序倒数第二个元素是右子树根节点。如果不一样则递归分树
if (pre[1] != post[post.length-2]) {//Arrays.copyOfRange(data, 2 , 7 );
int v = pre[1];
int idx = -1;//记录左子树根节点在后序中的位置。
for(int i = 0;i<post.length;i++) if(post[i] == v) idx = i;
//左右子树都不包含当前根节点，也就是pre[0]和post[len-1]
int[] post1 = Arrays.copyOfRange(post, 0, idx+1);
int[] post2 = Arrays.copyOfRange(post, idx+1, len-1);
int[] pre1 = Arrays.copyOfRange(pre,1,1+post1.length);
int[] pre2 = Arrays.copyOfRange(pre,post1.length+1,len);
ans.left = dfs(pre1, post1);
ans.right = dfs(pre2, post2);
}else {//说明当前树只有一个根。左右无所谓了
ans.left = dfs(Arrays.copyOfRange(pre,1,len), Arrays.copyOfRange(post, 0, len-1));
}
return ans;
}
}
咳咳，和之前的思路不能说一模一样，只能说几乎不同。。。因为我在分解左右子树的时候就发现，其实这个题可以转化成递归问题。然后就和之前的思路完全不同了。。。反正最终变成了上述的代码。过是过了，毕竟节点30个以内。不过我觉得优化空间还是蛮大的。比如说复制数组可以换成传起始下标？不过这个太复杂了懒得自己去想了，我直接去看看性能第一的代码吧：
开过光的嘴预测到了答案：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode constructFromPrePost(int[] pre, int[] post) {
return helper(pre,post,0,pre.length-1,0,post.length-1);
}
public TreeNode helper(int[] pre,int[] post,int prestart,int preend,int poststart,int postend){
if(prestart>preend||poststart>postend)return null;
TreeNode root=new TreeNode(pre[prestart]);
if (prestart == preend)
return root;
int index=0;
while(post[index]!=pre[prestart+1]){
index++;
}
root.left=helper(pre,post,prestart+1,prestart+1+index-poststart,poststart,index);
root.right=helper(pre,post,prestart+2+index-poststart,preend,index+1,preend-1);
return root;
}
}
果然是不复制数组，而是直接用下标表示数值的方法，性能超过了百分百。其实不过是2ms进化到1ms而已。总而言之二叉树的题目，第一反应递归一般不会出错。这个题就这样了，下一题。
不相交的线
题目：在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足： nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
示例 2：
输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3
示例 3：
输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2
提示：
1 <= nums1.length <= 500
1 <= nums2.length <= 500
1 <= nums1[i], nums2[i] <= 2000
思路：不知道为啥审完题我第一反应又是dp，我这怕不是dp综合征吧。题目标签是数组。但是我还是觉得可以用dp来做。每一对元素可以分为连和不连。如果连则取下面的下标往下遍历。如果不连则从当前遍历。两个游标记录上下的线当前指向。思路还算清晰，不太好用言语表达出来，我去实现下试试。
真的要代码实现之前，我发现了个问题：其实这个问题可以转换思路，变成nums1和nums2的最长子序列。因为可以按照子序列的顺序连线。肯定不存在交叉。然后这个题就做过好几遍了，我觉得我思路没问题，我去写代码。
第一版代码：
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length+1][nums2.length+1];
for(int i = 0;i<nums1.length;i++) {
for(int j = 0;j<nums2.length;j++) {
if(nums1[i] == nums2[j]) {
dp[i+1][j+1] = dp[i][j]+1;
}else {
dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
}
}
}
return dp[nums1.length][nums2.length];
}
}
ac是ac了，性能没眼看了。。但是别的不说思路起码是对的。然后这个子数组的优化没啥好说的，毕竟我的技术最多也就能压缩下空间。时间复杂度少不了。。我直接去看看性能第一的代码吧：
！！！！！我踏马简直了，一样的思路压缩了下空间，性能就上来了。。一点脾气没有了，附上代码：
class Solution {
public int maxUncrossedLines(int[] A, int[] B) {
int lena = A.length, lenb = B.length;
int[] dp = new int[lenb+1];
for(int i = 1;i<=lena;i++) {
int[] temp = new int[lenb+1];
for(int j = 1;j<=lenb;j++) {
if(A[i-1]==B[j-1]) {
temp[j] = dp[j-1]+1;
}
else {
temp[j] = Math.max(dp[j], temp[j-1]);
}
}
dp = temp;
}
return dp[lenb];
}
}
因为当前数值只和上一层有关，所以压缩成两个数组很容易想到，我是没想到性能差别这么大，哎，这个题就这样吧，下一题。
查找和替换模式
题目：你有一个单词列表 words 和一个模式 pattern，你想知道 words 中的哪些单词与模式匹配。如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，我们就得到了所需的单词，那么单词与模式是匹配的。（回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）返回 words 中与给定模式匹配的单词列表。你可以按任何顺序返回答案。
示例：
输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
输出：["mee","aqq"]
解释：
"mee" 与模式匹配，因为存在排列 {a -> m, b -> e, ...}。
"ccc" 与模式不匹配，因为 {a -> c, b -> c, ...} 不是排列。
因为 a 和 b 映射到同一个字母。
提示：
1 <= words.length <= 50
1 <= pattern.length = words[i].length <= 20
思路：这个题一开始看题目没太明白，但是看了示例秒懂。有点类似中文的按照格式写成语，ABAB,AABB,ABBA之类的模板。只不过这个题的模板是pattern，然后我们照着这个模板去套单词就行了。感觉挺好实现的。因为单词数不超过50.而且长度不超过20。所以我觉得暴力应该可能可以。这个题咋说呢，在我看来是怎么都能解。但是怎么能解的好又没啥思路。
第一版本代码：
class Solution {
String[] c;
public List<String> findAndReplacePattern(String[] words, String pattern) {
c = new String[] {"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T"};
pattern = getStr(pattern);
List<String> ans = new ArrayList<String>();
for(String s:words) if(getStr(s).equals(pattern)) ans.add(s);
return ans;
}
public String getStr(String str) {
int temp = 0;
for(int i = 0;i<str.length();i++) {
char cur = str.charAt(i);
if(cur<97) continue;//这个元素已经替换过了，直接下一个
str = str.replaceAll(cur+"", c[temp++]);
}
return str;
}
}
仗着数据少就硬生生的暴力，我觉得20,50的数据范围绝对不会超时，果然ac了，但是性能只超过了百分之7。。emmmmm....其实别的实现方法也有好多，如说记录出现的下标，然后下标比对什么的。再来一种实现方式吧：
class Solution {
public List<String> findAndReplacePattern(String[] words, String pattern) {
int[] temp = getStr(pattern);
List<String> ans = new ArrayList<String>();
for(String s:words) {
int[] cur = getStr(s);
boolean flag = true;
for(int i = 0;i<cur.length;i++) {
if(cur[i] != temp[i]) {
flag = false;
break;
}
}
if(flag) ans.add(s);
}
return ans;
}
public int[] getStr(String str) {
int[] c = new int[str.length()];
char[] s = str.toCharArray();
int temp = 1;
for(int i = 0;i<s.length;i++) {
if(c[i] != 0) continue;
c[i] = temp++;
for(int j = i+1;j<s.length;j++) {
if(c[j] != 0) continue;
if(s[j] == s[i]) c[j] = c[i];
}
}
return c;
}
}
改了下思路，直接用染色的思路实现了，去掉了来回来去字符串操作，性能一下子就上来了。虽然实际上代码看着多了。但是这种实现比较好理解。思路很简单，一个元素代表一个数字。从前往后出现的依次递加。这样哪怕不是一样的字符但是格式一样数组也应该一样。
本篇笔记就记到这里了，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利，生活健健康康，周末愉快哟~！
