一棵二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这棵二叉树不再是搜索二叉树,请按升序输出这两个错误节点的值。(每个节点的值各不相同)
搜索二叉树:满足每个节点的左子节点小于当前节点,右子节点大于当前节点。
输入:{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; } }
定义重复字符串是由两个相同的字符串首尾拼接而成,例如 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; } }
给你一个数组,其长度为 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)); }