第一题: 419. 甲板上的战舰

LeetCode: 419. 甲板上的战舰

描述:
给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 ‘X’ 或者是一个空位 ‘.’ ，返回在甲板 board 上放置的 战舰 的数量。

战舰 只能水平或者垂直放置在 board 上。换句话说，战舰只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状建造，其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰）。

解题思路:

1. 这里首先去判断左上角, 如果是左上角就进行计数.
2. 判断是否是左上角, 那么上方, 或者左方就不能为X
3. 这样省去了判断右方和下方的方法.

代码实现:

class Solution {
    public int countBattleships(char[][] board) {
        int res = 0;
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if((board[i][j] == 'X') && (i == 0 || board[i-1][j]=='.') && (j == 0 || board[i][j-1]=='.')){
                    res++;
                }
            }
        }
        return res;
    }
}

第二题: 443. 压缩字符串

LeetCode: 443. 压缩字符串

描述:
给你一个字符数组 chars ，请使用下述算法压缩：

从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：

• 如果这一组长度为 1 ，则将字符追加到 s 中。
• 否则，需要向 s 追加字符，后跟这一组的长度。

压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。

请在 修改完输入数组后 ，返回该数组的新长度。

你必须设计并实现一个只使用常量额外空间的算法来解决此问题。

解题思路:

1. 双指针解题.
2. 如果当前right和left字符相同, right++.
3. 如果当前right不是left的右侧, 那么不记录出现次数, 如果是右侧, 就记录次数. (例如 chars = [“a”] , 不需要记录次数)
4. 以字符串拼接的形式, 记录字符以及次数.

代码实现:

class Solution {
    public int compress(char[] chars) {
        StringBuilder sb = new StringBuilder();
        int left = 0;
        int right = 0;
        while(right < chars.length) {
            right++;
            while(right < chars.length && chars[left] == chars[right]) {
                right++;
            }
            sb.append(chars[left]);
            if(right - left > 1) {
                sb.append(right - left);
            }
            left = right;
        }
        for(int i = 0; i < sb.length(); i++) {
            chars[i] = sb.charAt(i);
        }
        return sb.length();
    }
}

第三题: 501. 二叉搜索树中的众数

LeetCode: 501. 二叉搜索树中的众数

描述:
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

解题思路:

1. 这里使用中序遍历的方式去记录相同val值的次数.
2. 在记录最大次数, 如果当前次数和最大次数相等就添加结果集中.
3. 如果当前次数比最大次数大, 那么清空结果集, 重新添加.

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> list = new ArrayList<>();
    int maxCount = 0;
    int count = 0;
    TreeNode pre = null;
    public int[] findMode(TreeNode root) {
        inorder(root);
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    public void inorder(TreeNode root) {
        if(root == null) return;
        inorder(root.left);
        if(pre == null) {
            count = 1;
        }else if(pre.val == root.val) {
            count++;
        }else{
            count = 1;
        }
        pre = root;
        if(maxCount == count) {
            list.add(root.val);
        }
        if(maxCount < count) {
            maxCount = count;
            list.clear();
            list.add(root.val);            
        }
        inorder(root.right);
    }
}

第四题: 503. 下一个更大元素 II

LeetCode: 503. 下一个更大元素 II

描述:
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

解题思路:

1. 这里使用一个栈来记录当前最大元素.
2. 这里使用二次遍历的方法. 类似于循环遍历.
3. 首先将结果数组都赋值为 -1
4. 如果当前元素大于栈顶元素, 就出栈. 同时对当前出栈下标进行赋值.(如果没有出栈, 就会自动为-1)
5. 第一次遍历. 入栈下标.

代码实现:

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        Arrays.fill(res,-1);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length * 2; i++) {
            int val = nums[i % nums.length];
            while(!stack.isEmpty() && val > nums[stack.peek()]){
                res[stack.pop()] = val;
            }
            if(i < nums.length) stack.add(i);
        }
        return res;
    }
}

第五题: 508. 出现次数最多的子树元素和

LeetCode: 508. 出现次数最多的子树元素和

描述:
给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）

解题思路:

1. 这里直接记录每个节点的值, 以及该节点与子树节点的值. 使用哈希表记录. 并记录这些值出现的次数.
2. 并且要记录出现的最大次数.
3. 遍历哈希表, 查看value为最大次数的key, 添加到 List
4. 并且遍历结果数组, 数组元素和List一样.

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Map<Integer,Integer> map = new HashMap<>();
    int maxCount = 0;
    public int[] findFrequentTreeSum(TreeNode root) {
        if(root == null) return new int[0];
        inorder(root);
        List<Integer> list = new ArrayList<>();
        int i = 0;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if(maxCount == entry.getValue()) list.add(entry.getKey());
        }
        int[] res = new int[list.size()];
        for(int j = 0; j < list.size(); j++) {
            res[j] = list.get(j);
        }
        return res;
    }
    public int inorder(TreeNode root) {
        if(root == null) return 0;
        int left = inorder(root.left);
        int right = inorder(root.right);
        int sum = left + right + root.val;
        map.put(sum,map.getOrDefault(sum,0)+1);
        maxCount = Math.max(maxCount,map.get(sum));
        return sum;
    }
}

第六题: 537. 复数乘法

LeetCode: 537. 复数乘法

描述:

复数 可以用字符串表示，遵循 "实部+虚部i" 的形式，并满足下述条件：

• 实部 是一个整数，取值范围是 [-100, 100]
• 虚部 也是一个整数，取值范围是 [-100, 100]
• i^2 == -1
  给你两个字符串表示的复数 num1 和 num2 ，请你遵循复数表示形式，返回表示它们乘积的字符串。

解题思路:

1. 这里首先对 nums1 和 nums2 进行字符串拆分
2. 这里 nums1 的实部为 a1, nums1 的虚部为 a2
3. 这里 nums2 的实部为 b1, nums2 的虚部为 b2
4. 因此 结果的实部是 a1*b1-a2*b2, 虚部是 a2*b1+a1*b2
5. 返回结果 a1*b1-a2*b2 + a2*b1+a1*b2 i

代码实现:

class Solution {
    public String complexNumberMultiply(String num1, String num2) {
        String[] s1 = num1.split("\\+|i");
        int a1 = Integer.parseInt(s1[0]);
        int a2 = Integer.parseInt(s1[1]);
        String[] s2 = num2.split("\\+|i");
        int b1 = Integer.parseInt(s2[0]);
        int b2 = Integer.parseInt(s2[1]);
        int res1 = a1 * b1 - a2 * b2;
        int res2 = a2 * b1 + a1 * b2;
        return res1 + "+" + res2 + "i";
    }
}