【Day11】每天三算法
文章目录
题目
NC58 找到二叉搜索树中的两个交换节点（esay）
描述
一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)
搜索二叉树：满足每个节点的左子节点小于当前节点，右子节点大于当前节点。
输入：{4,2,5,3,1}
返回值：[1,3]
思考
看到二叉搜索树，我们自然会想到其性质，即中序遍历后，节点的排列是有序的
那么对于题目中描述的情况，其中序遍历后的结果，就是一个两个元素被交换的有序数组（交换后其实不有序了）
那题目就变成了"找到有序数组中被交换位置的两个元素"
对于这个问题，其实是有固定解法的，大家可以自行悟一下：
建议在理解这段代码的时候，可以现在草稿纸上写几个有序数组被调换两个元素的示例
public static int[] getTwoSwap(int[]arr) {
int[] res = new int[2];
int first=-1;
int second=-1;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i]>arr[i+1]) {
if (first==-1) {
first=i;
second=i+1;
} else {
second=i+1;
}
}
}
res[0]=first;
res[1]=second;
return res;
}
剩下的，就是中序遍历了
题解
public class NC58_findError {
// 被调用的主函数
public int[] findError (TreeNode root) {
List<Integer> nums = new ArrayList<>();
dfs(nums,root);
return findErr(nums);
}
// 获取中序遍历的序列
public void dfs(List<Integer>nums,TreeNode root) {
if (root==null) return;
dfs(nums,root.left);
nums.add(root.val);
dfs(nums,root.right);
}
// 找到有序数组中被调换位置的两个元素
public int[] findErr(List<Integer>nums) {
int[] res = new int[2];
int first = -1;
int second = -1;
for (int i = 0; i < nums.size()-1; i++) {
if (nums.get(i)>nums.get(i+1)) {
if (first==-1) {
first=i;
second=i+1;
} else {
second=i+1;
}
}
}
res[0]=nums.get(second);
res[1]=nums.get(first);
return res;
}
}
NC142 最长重复子串（medium）
描述
定义重复字符串是由两个相同的字符串首尾拼接而成，例如 abcabcabcab**c 便是长度为6的一个重复字符串，而 abcbaabcba 则不存在重复字符串。
给定一个字符串，请返回其最长重复子串的长度。
若不存在任何重复字符子串，则返回 0 。
本题中子串的定义是字符串中一段连续的区间。
示例：
输入："ababc"
返回值：4
说明：abab为最长的重复字符子串，长度为4
输入："abcab"
返回值：0
说明：该字符串没有重复字符子串
思考
方法一：暴力算法
外层循环是定义串的长度（1-n），当然，我们的长度可以从大到小进行枚举，这样只要答案出现就可以返回了，减少了判断次数
内层是定义串的起始位置，记录从当前起始位置最多能有几个重复的串
题解
public class NC142_solve {
public static void main(String[] args) {
NC142_solve solu = new NC142_solve();
System.out.println(solu.solve("abcabcab"));
}
public int solve (String a) {
if (a.length()<=1) return 0;
// size不可能超过原串的一半
// 字符串长度从大到小枚举，这样只要出现答案，我们直接返回即可
for (int size = a.length()/2; size >=1 ; size--) {
// 第二层循环，枚举的是起始位置
for (int start = 0; start < a.length() - size; start++) {
String currSub = a.substring(start, start+size);
int l=start+size,r=l+size-1;
int count=1; // count 至少要为2，才说明至少出现了一次重复
while (r<a.length()) {
if (!currSub.equals(a.substring(l,r+1))) break;
count++;
l=r+1;
r=l+size-1;
}
//if (count>1) res=Math.max(res,count*size);
if (count>1) return count*size;
}
}
return 0;
}
}
NC144 不相邻最大子序列和（medium）
描述
给你一个数组，其长度为 n ，在其中选出一个子序列，子序列中任意两个数不能有相邻的下标（子序列可以为空）
本题中子序列指在数组中任意挑选若干个数组成的数组。
思考
对于这道题，咱么的第一反应，就是动规，其子状态为：要么当前位置不选，和前一个位置保持一致，要么当前位置选，则 dp[k]=dp[k-2]+arr[k]
其状态转移方程可以写成如下形式：
dp[k] = max(dp[k-1],dp[k-1]+arr[k]) <当前位置选或不选哪个更大>
题解
public long subsequence (int n, int[] array) {
if (array.length==1) return new Long(Math.max(0,array[0]));
if (array.length==2) return new Long(Math.max(0,Math.max(array[0],array[1])));
long[] dp = new long[n];
dp[0]=array[0];
dp[1]=array[1];
long res = Math.max(0,Math.max(dp[0], dp[1]));
for (int i = 2; i <n ; i++) {
dp[i]=Math.max(dp[i-1],dp[i-2]+array[i]);
res=Math.max(res,dp[i]);
}
return new Long(Math.max(0,res));
}
在上述代码中，我们能够发现，每次只是使用了 dp 的前一个和前前一个元素，所以我们可以把 dp 数组优化没有
优化后的代码如下：
public long subsequence (int n, int[] array) {
if (array.length==1) return new Long(Math.max(0,array[0]));
if (array.length==2) return new Long(Math.max(0,Math.max(array[0],array[1])));
long pre = array[0];
long curr = array[1];
long res = Math.max(0,Math.max(pre,curr));
for (int i = 2; i <n ; i++) {
long newPre = Math.max(curr, pre + array[i]);
res=Math.max(res,newPre);
pre=curr;
curr=newPre;
}
return new Long(Math.max(0,res));
}