【Day11】每天三算法

【Day11】每天三算法

文章目录

题目

NC58 找到二叉搜索树中的两个交换节点(esay)

描述

一棵二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这棵二叉树不再是搜索二叉树,请按升序输出这两个错误节点的值。(每个节点的值各不相同)

搜索二叉树:满足每个节点的左子节点小于当前节点,右子节点大于当前节点。

【Day11】每天三算法

输入:{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 数组优化没有

【Day11】每天三算法

优化后的代码如下:

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));
    }
上一篇:Python文件操作与模块—Python Day11


下一篇:Day11面向对象2