【Day11】每天三算法

文章目录

• 【Day11】每天三算法
• • 题目
  • • NC58 找到二叉搜索树中的两个交换节点（esay）
    • • 描述
      • 思考
      • 题解
    • NC142 最长重复子串（medium）
    • • 描述
      • 思考
      • 题解
    • NC144 不相邻最大子序列和（medium）
    • • 描述
      • 思考
      • 题解

题目

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));
    }