leetcode刷题 650~

题目650

只有两个键的键盘

最初在一个记事本上只有一个字符 'A'。你每次可以对这个记事本进行两种操作：

Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
Paste (粘贴) : 你可以粘贴你上一次复制的字符。
给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 'A'。输出能够打印出 n 个 'A' 的最少操作次数。

思路

1.动态规划

2.素数分解

实现

1.
class Solution {
    public int minSteps(int n) {
        int[][] dp = new int [n+1][n+1];
        dp[1][1] = 1;
        int temp;
        for(int i=1; i < n+1; i++){
            temp = Integer.MAX_VALUE;
            for(int j=1; j < i; j++){
                if(dp[i-j][j] != 0){
                    dp[i][j] = dp[i-j][j] + 1;
                    temp = Math.min(temp, dp[i][j]);
                }
            }
            if(i != 1)
                dp[i][i] = temp+1;
        }
        return dp[n][n]-1;

    }
}
2.
class Solution {
    public int minSteps(int n) {
        int count = 0;
        while(n != 1){
            int i = findMaxDivisor(n);
            count += n/i;
            n = i;
        }
        return count;
    }

    private int findMaxDivisor(int n){
        int max = n / 2;
        for (int i = max ; i >= 2; i--) {
            if ( n % i == 0) return i;
        }
        return 1;
    }
}

题目652

寻找重复的子树

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

思路

假设每棵子树都有一个唯一标识符：只有当两个子树的 id 相同时，认为这两个子树是相同的。

一个节点 node 的左孩子 id 为 x，右孩子 id 为 y，那么该节点的 id 为 (node.val, x, y)。

实现

class Solution {
    int curID;
    Map<String, Integer> trees;
    Map<Integer, Integer> count;
    List<TreeNode> ans;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        curID = 1;
        trees = new HashMap<>();
        count = new HashMap<>();
        ans = new ArrayList();
        lookUP(root);
        return ans;
    }

    private int lookUP(TreeNode node){
        if (node == null) return 0;
        String serial = node.val + "," + lookUP(node.left) + "," + lookUP(node.right);
        int id = trees.computeIfAbsent(serial, key -> curID++);
        count.put(id, count.getOrDefault(id, 0) + 1);
        if (count.get(id) == 2)
            ans.add(node);
        return id;
    }
}

题目653

两数之和

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

思路

中序遍历出数组，双指针寻找元素

实现

class Solution {
    private ArrayList<Integer> nums = new ArrayList<>();
    public boolean findTarget(TreeNode root, int k) {
        inorder(root);
        int sum;
        int left = 0;
        int right = nums.size()-1;
        while(left < right){
            sum = nums.get(left) + nums.get(right);
            if(sum == k) return true;
            else if (sum < k) left++;
            else right--;
        }
        return false;
    }

    private void inorder(TreeNode node){
        if(node != null){
            inorder(node.left);
            nums.add(node.val);
            inorder(node.right);
        }
    }
}

题目654

最大二叉树

思路

递归

实现

class Solution {
    private int[] nums;
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        this.nums = nums;
        return construct(0, nums.length);
    }

    private TreeNode construct(int left, int right){
        if(left == right) return null;
        int maxIndex = getMaxIndex(left, right);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = construct(left, maxIndex);
        root.right = construct(maxIndex+1, right);
        return root;
    }

    private int getMaxIndex(int left, int right){
        int maxIndex=left;//假设第一个元素为最大值 那么下标设为0
        for(int i =left; i < right; i++){
            if(nums[maxIndex]<nums[i]){
                maxIndex=i;
            }
        }
        return maxIndex;
    }
}

题目655

输出二叉树

在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：

行数 m 应当等于给定二叉树的高度。
列数 n 应当总是奇数。
根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。
每个未使用的空间应包含一个空的字符串""。
使用相同的规则输出子树。

思路实现

class Solution {
    private String[][] res;
    public List<List<String>> printTree(TreeNode root) {
        int depth = getDepth(root);
        res = new String[depth][(1 << depth) - 1];
        for(String[] arr: res)
            Arrays.fill(arr,"");
        dfs(root, 0, 0, (1 << depth)-1);
        List<List<String>> ans = new ArrayList<>();
        for(String[] arr:res)
            ans.add(Arrays.asList(arr));
        return ans;
    }
    private void dfs(TreeNode node, int depth, int left, int right){
        if(node == null) return;
        int mid = (left+right)/2;
        res[depth][mid] = "" + node.val;
        dfs(node.left, depth+1, left, mid-1);
        dfs(node.right, depth+1, mid+1, right);
    }

    private int getDepth(TreeNode node){
        if(node == null) return 0;
        return Math.max(getDepth(node.left), getDepth(node.right))+1;
    }
}

题目657

机器人能否返回原点

在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。

移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。

注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

思路实现

class Solution {
    public boolean judgeCircle(String moves) {
        int x = 0, y = 0;
        int length = moves.length();
        for(int i=0;i<length;i++){
            char ch = moves.charAt(i);
            if(ch == 'R') x++;
            else if(ch == 'L') x--;
            else if(ch == 'U') y++;
            else y--;
        }
        return x == 0 && y == 0;
    }
}

题目658

找到k个最接近的元素

给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b

思路

利用二分法找到左区间

实现

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0, right = arr.length-k;
        while(left < right){
            int mid = left + (right-left)/2;
            if(x - arr[mid] > arr[mid + k] - x){
                left = mid +1;
            }else{
                right = mid;
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int i = left; i < left + k; i++) {
            res.add(arr[i]);
        }
        return res;

    }
}