Daily question brushing record (XXXI)

The first question is : 419. Warships on deck

LeetCode: 419. Warships on deck

describe :
Give you a size of m x n Matrix board Represents the deck , among , Each cell can be a warship ‘X’ Or an empty seat ‘.’ , Return on deck board Placed on Warship The number of .

Warship Can only be placed horizontally or vertically in board On . let me put it another way , Warships can only press 1 x k（1 That's ok ,k Column ） or k x 1（k That's ok ,1 Column ） Built in the shape of , among k It can be any size . There is at least one horizontal or vertical space between the two warships （ That is, there are no adjacent warships ）.

Their thinking :

1. Here, first judge the upper left corner , If it is in the upper left corner, count .
2. Determine whether it is the upper left corner , So above , Or the left cannot be X
3. This saves the method of judging the right and the bottom .

Code implementation :

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

The second question is : 443. Compress string

LeetCode: 443. Compress string

describe :
Give you an array of characters chars , Please use the following algorithm to compress ：

From an empty string s Start . about chars Each group in Consecutive repeating characters ：

• If the length of this group is 1 , Append characters to s in .
• otherwise , You need to s Append character , Followed by the length of this group .

Compressed string s Should not return directly to , Need to dump to character array chars in . It should be noted that , If the group length is 10 or 10 above , It's in chars The array will be split into multiple characters .

Please be there. After modifying the input array , Returns the new length of the array .

You must design and implement an algorithm that uses only constant extra space to solve this problem .

Their thinking :

1. Double pointer problem solving .
2. If at present right and left Same character , right++.
3. If at present right No left The right side of the , Then do not record the number of occurrences , If right , Just record the times . ( for example chars = [“a”] , There is no need to record the number of times )
4. In the form of string splicing , Record characters and times .

Code implementation :

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

Third question : 501. The mode in the binary search tree

LeetCode: 501. The mode in the binary search tree

describe :
Give you a binary search tree with duplicate values （BST） The root node root , Find out and return to BST All in The number of （ namely , The most frequent element ）.

If there is more than one mode in the tree , Can press In any order return .

Assume BST Meet the following definitions ：

• The value of the node contained in the left subtree of the node Less than or equal to The value of the current node
• The value of the node contained in the right subtree of the node Greater than or equal to The value of the current node
• Both the left and right subtrees are binary search trees
  

Their thinking :

1. Here we use the method of middle order traversal to record the same val Times of value .
2. Record the maximum number of times , If the current number of times is equal to the maximum number of times, add the result set .
3. If the current number is greater than the maximum number , Then empty the result set , To add .

Code implementation :

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

Fourth question : 503. Next bigger element II

LeetCode: 503. Next bigger element II

describe :
Given a circular array nums （ nums[nums.length - 1] The next element of this is nums[0] ）, return nums Of each element in Next bigger element .

Numbers x Of The next bigger element Is in the order of array traversal , The first larger number after this number , This means that you should cycle through it to the next larger number . If it doesn't exist , The output -1 .

Their thinking :

1. Here, a stack is used to record the current maximum element .
2. Here we use the method of twice traversal . Similar to loop traversal .
3. First, assign the result array to -1
4. If the current element is larger than the top of the stack , Out of the stack . At the same time, assign a value to the current outbound subscript .( If there is no stack , It will automatically -1)
5. First traversal . Stack subscript .

Code implementation :

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

Fifth question : 508. The most frequent sub tree elements and

LeetCode: 508. The most frequent sub tree elements and

describe :
Give you a root node of binary tree root , Please return the most frequent subtree elements and . If more than one element appears the same number of times , Returns all the most frequent subtree elements and （ Unlimited order ）.

Of a node 「 Subtree elements and 」 It is defined as the sum of the elements of all nodes in the binary tree with the node as the root （ Including the node itself ）

Their thinking :

1. Here, the value of each node is directly recorded , And the value of this node and the subtree node . Use a hash table to record . And record the number of times these values appear .
2. And record the maximum number of occurrences .
3. Traversal hash table , see value Is the maximum number of key, Add to List
4. And traverse the result array , Array elements and List equally .

Code implementation :

/** * 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;
    }
}

Sixth question : 537. Complex multiplication

LeetCode: 537. Complex multiplication

describe :

The plural Can be expressed as a string , follow " Real component + Imaginary part i" In the form of , And meet the following conditions ：

• Real component It's an integer , The value range is [-100, 100]
• Imaginary part It's also an integer , The value range is [-100, 100]
• i^2 == -1
  Give you a complex number represented by two strings num1 and num2 , Please follow the plural form , Returns a string representing their product .

Their thinking :

1. First of all, here is nums1 and nums2 Split the string
2. here nums1 The real part of is a1, nums1 The imaginary part of is a2
3. here nums2 The real part of is b1, nums2 The imaginary part of is b2
4. therefore The real part of the result is a1*b1-a2*b2, Imaginary part a2*b1+a1*b2
5. Return results a1*b1-a2*b2 + a2*b1+a1*b2 i

Code implementation :

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