Hexo

Posted 2022-05-05Updated 2022-05-04LeetCode / Medium / 复习a minute read (About 202 words)

Question

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Solution

首先对所有在边缘上的“O”进行BFS或DFS搜索，将和边缘连续的“O”改为“#”或任意其他字符。

然后遍历整个board，如果是“O”则改为“X”，如果是“#”则恢复为“O”。

Code

class Solution {
    public void solve(char[][] board) {
        for(int i = 0; i <board.length; i++){
            for(int j = 0; j <board[0].length; j++){
                boolean isEdge = (i == 0 || j == 0 || i == board.length-1 || j == board[0].length-1);
                if(isEdge && board[i][j] == 'O'){
                    bfs(board, i, j);
                }
            }
        }
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] == '#') board[i][j] = 'O';
                else if(board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }

    private void bfs(char[][] board, int x, int y){
        int m = board.length;
        int n = board[0].length;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        int size = 1;
        while(!q.isEmpty()){
            for(int k = 0; k < size; k++){
                int[] curr = q.poll();
                int i = curr[0], j = curr[1];
                if( i<0 || j<0 || i>m-1 || j>n-1 || board[i][j] == 'X' || board[i][j] == '#' ) continue;
                board[i][j] = '#';
                q.add(new int[]{i+1,j});
                q.add(new int[]{i-1,j});
                q.add(new int[]{i,j+1});
                q.add(new int[]{i,j-1});
            }
            size = q.size();
        }
    }
}

Posted 2022-05-05Updated 2022-05-04LeetCode / Medium3 minutes read (About 401 words)

384. Shuffle an Array

Question

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

Solution(int[] nums) Initializes the object with the integer array nums.

int[] reset() Resets the array to its original configuration and returns it.

int[] shuffle() Returns a random shuffling of the array.

Solution

Fisher-Yates洗牌算法。将数组分为两组部分，一组为已打乱的部分，一组为未打乱的部分。每次从未打乱部分中取一个元素，随机和一个未打乱部分的元素（包括自身）交换，则该位置变为已打乱的部分。

Code

class Solution {
    int[] data;
    int[] shuffle;
    Random r;
    public Solution(int[] nums) {
        data = nums;
        shuffle = new int[nums.length];
        r = new Random();
        for(int i = 0; i < data.length; i++){
            shuffle[i] = nums[i];
        }
    }
    
    public int[] reset() {
        return data;
    }
    
    public int[] shuffle() {
        for(int i = data.length-1 ; i >= 0; i--){
            swap(i, r.nextInt(i+1));
        }
        return shuffle;
    }
    
    private void swap(int i, int j){
        int temp = shuffle[i];
        shuffle[i] = shuffle[j];
        shuffle[j] = temp;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

Solution 2

将静态数组转换为动态数组，每次随机取动态数组里的一个index。
将其按顺序填入result数组，并删除动态数组这个位置。
最后返回result。

Code

class Solution {
    int[] data;
    Random r;
    public Solution(int[] nums) {
        data = nums;
        r = new Random();
    }
    
    public int[] reset() {
        return data;
    }
    
    public int[] shuffle() {
        ArrayList<Integer> bin = new ArrayList<>();
        for(int i = 0; i < data.length; i++){
            bin.add(data[i]);
        }
        
        int[] ret = new int[data.length];
        for(int i = 0 ; i < data.length; i++){
            int random = r.nextInt(bin.size());
            ret[i] = bin.get(random);
            bin.remove(random);
        }
        return ret;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

Posted 2022-05-05Updated 2022-05-04LeetCode / Hard4 minutes read (About 589 words)

297. Serialize and Deserialize Binary Tree

Question

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Solution

编码过程

编码时采用BFS搜索，将二叉树按层级组成字符串。
当当前节点不等于null时，添加当前节点的值和一个符号。
然后将其左右子节点加入队列。
当当前节点为null时，添加一个非数字字符和一个符号。

解码过程

解码时同样采用BFS搜索，按层级恢复二叉树。
首先将字符串根据符号进行分割，变为字符串数组。
如果第一个字符表示为null，返回null。

否则将第一个数字组成根节点并加入队列。创建一个指针i记录位置。
当队列不为空，且指针i未越界时，根据指针i上的字符串创建当前节点的左子节点。
将指针右移，如果没有越界则创建当前节点的右子节点，然后将指针右移。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder data = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            if(curr == null) data.append("n,");
            else {
                data.append(curr.val + ",");
                q.add(curr.left);
                q.add(curr.right);
            }
        }
        return data.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] values = data.split(",");
        if(values[0].equals("n")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;     
        while(!q.isEmpty() && i < values.length){
            TreeNode curr = q.poll();
            curr.left = values[i].equals("n") ? null : new TreeNode(Integer.parseInt(values[i]));
            if(i++ < values.length) curr.right = values[i].equals("n") ? null : new TreeNode(Integer.parseInt(values[i]));
            if(curr.left != null) q.add(curr.left);
            if(curr.right != null) q.add(curr.right);
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

Posted 2022-05-05Updated 2022-05-04LeetCode / Medium / 复习3 minutes read (About 384 words)

201. Bitwise AND of Numbers Range

Question

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Solution

进行按位和运算时，只要两个位不都是1就会为0。从left到right之间，如果left和right的前x位是一样的，那么两者之间必定有一个数字
在x位上为1，后面的位上为0。因此和这个数字进行按位和运算必定为0。
因此，我们只要保留前面两者相同的位的信息即可，后面均为0。

当left与right不相等时，将两者同时右移，并计算移动的总数。
当两者相等时，向左移动计算的总数的位数。就保留了其相同的前缀。

Code

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int count = 0;
        
        while(left != right){
            left >>= 1;
            right >>= 1;
            count++;
        }
        return left << count;
    }
}

Solution 2

利用一串只有一个1的32位数字作为掩码，获得两个数字单独的位信息。
32位整数的第一位是符号位。因此我们的掩码从第1位开始直到第31位。
当对left和right进行该位的掩码操作后，如果两者相同，则掩码右移一位。
并将答案和当前位进行位或运算。（相当于保存当前位的位信息。）

如果不同，或者掩码变为0，则返回结果。

Code

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int mask = 1 << 30;
        int ans = 0;
        
        while(mask > 0 && (mask & left) == (mask & right)){
            ans |= (mask & left);
            mask >>= 1;
        }
        return ans;
    }
}

Posted 2022-05-04Updated 2022-05-04LeetCode / Medium2 minutes read (About 358 words)

1679. Max Number of K-Sum Pairs

Question

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Solution

两种思路，第一种，哈希表统计总数，然后逐个排除。
每次从数组中取一个数，先查询寻找的target是否在哈希表内。
如果表内存在target，则将target的计数减一，对数加一。

如果target不在表内，则将当前的数字加入表内。
最后返回结果。时间复杂度为O(n)。

Code

class Solution {
    public int maxOperations(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for(int num : nums){
            int target = k - num;
            if(map.containsKey(target) && map.get(target) > 0){
                map.put(target, map.get(target)-1);
                count++;
            }
            else{
                map.put(num, map.getOrDefault(num, 0)+1);
            }
        }
        return count;
    }
}

Solution 2

第二种思路，先排序。
然后双指针放在首尾。
当两者的和等于目标值时增加计数器，并移动两个指针。
当两者的和大于目标值时，右侧指针左移。
当两者的和小于目标值时，左侧指针右移。
最后返回结果。由于有排序存在，因此时间复杂度为O(nlogn) + O(n)。

Code

class Solution {
    public int maxOperations(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0, right = nums.length-1, count = 0;

        while(left < right){
            if(nums[left] + nums[right] == k){
                count++;
                left++;
                right--;
            }
            else if(nums[left] + nums[right] > k){
                right--;
            }
            else{
                left++;
            }
        }
        return count;
    }
}

Question

Solution

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

编码过程

解码过程

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Solution 2

Code

Recents

Archives

Links