1461. Check If a String Contains All Binary Codes
Posted Updated LeetCode / Medium3 minutes read (About 396 words)

1461. Check If a String Contains All Binary Codes

Question

Given a binary string s and an integer k, return true if every binary code of length k is a substring of s. Otherwise, return false.

Solution

位运算+哈希表，用整数num记录二进制编码并加入哈希表中。
首先将字符串内的前k位二进制码转换为整数。并将其数值添加到哈希表内。

滑动窗口遍历，维持num为k长度内二进制码所对应的整数，并在遍历时将num加入哈希集合。
如果哈希集合的size达到k长度对应的可组合数，则返回true，否则返回false。

位运算与掩码

为了维护整数num，首先将其二进制编码向左移动一位。
然后与mask进行按位与运算，屏蔽掉多余的位数。

mask的值为k长度对应的可组合数-1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean hasAllCodes(String s, int k) {
        if(s.length() < k) return false;    //字符串长度不足则返回false
        char[] bin = s.toCharArray();
        int n = s.length(), m = (int) Math.pow(2, k);
        HashSet<Integer> set = new HashSet<>(); //哈希表记录访问过的数字
        
        int num = Integer.parseInt(s.substring(0,k), 2);    //字符串以二进制转换为整数
        int mask = m-1; //掩码等于寻找长度-1
        set.add(num);
        
        for(int i = k; i < s.length(); i++){  //位运算，维护窗口内整数的值
            num <<= 1;  //位运算左移一位
            num &= mask;    //出界的位置被掩码遮盖
            if(bin[i] == '1') num++;
            set.add(num);
            if(set.size() == m) return true;    //如果哈希表长度等于2^k，则已经遍历了所有组合，返回true
        }
        return false;
    }
}
1379. Find a Node of a Binary Tree in a Clone Tree
Posted Updated LeetCode / Medium2 minutes read (About 234 words)

1379. Find a Node of a Binary Tree in a Clone Tree

Question

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Solution

DFS搜索，同步递归original和cloned的子节点。
当在original里找到target的时候返回当前的cloned节点。

注意可以先判断一个分支中的返回值是否为空，如果不为空则直接返回。反之则返回另一个分支。这样操作可以进行一部分剪枝。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if(original == null) return null;
        if(original.equals(target)) return cloned;
        
        TreeNode left = getTargetCopy(original.left, cloned.left, target);
        if(left != null) return left;
        else return getTargetCopy(original.right, cloned.right, target);
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 266 words)

2274. Maximum Floors Without Special Floors

Question

Alice manages a company and has rented some floors of a building as office space. Alice has decided some of these floors should be special floors, used for relaxation only.

You are given two integers bottom and top, which denote that Alice has rented all the floors from bottom to top (inclusive). You are also given the integer array special, where special[i] denotes a special floor that Alice has designated for relaxation.

Return the maximum number of consecutive floors without a special floor.

Solution

可以视为特殊的动态规划。

计算每个特殊房间与上一个特殊房间的层数。（可以将底层的上一个房间视为特殊房间，需要将第一个房间设置为bottom-1）。
当距离大于当前结果时则更新res。

最后需要计算最后一层到上一个特殊房间的距离。（可以将顶楼的上一层视为特殊房间，因此直接计算top - lastRoom的层数即可）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxConsecutive(int bottom, int top, int[] special) {
        int res = 0;
        int lastRoom = bottom-1;
        Arrays.sort(special);
        
        for(int room : special){
            int temp = room - lastRoom - 1;
            res = Math.max(res, temp);
            lastRoom = room;
            
        }
        int temp = top - lastRoom;
        res = Math.max(res, temp);
        
        return res;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 315 words)

34. Find First and Last Position in Sorted Array

问题
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

二分搜索，搜索中间项。
中间项等于左侧和右侧指针的中点，根据搜索左侧边界和右侧边界选择二分向下舍去或是二分向上补足。
当中间项小于目标，则更新左侧边界。
若中间项大于目标，则更新右侧边界。
当中间项等于目标时，根据搜索左侧边界还是右侧边界选择更新左侧或右侧。
由于有可能有重复元素存在，因此需要继续二分搜索下去，直到右侧边界大于左侧边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{searchLeft(nums,target),searchRight(nums,target)};
    } 

    private int searchRight(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        
        while(left <= right){
            mid = (right-left)/2+left;
            if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
            else{
                result = mid;
                left = mid+1;
            }
        }
        return result;
    }
    
    private int searchLeft(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        
        while(left <= right){
            mid = (right-left+1)/2+left;
            if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
            else{
                result = mid;
                right = mid-1;
            }
        }
        return result;
    }
}
Posted Updated LeetCode / Easya minute read (About 221 words)

235. Lowest Common Ancestor of a BST

问题
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

DFS搜索，如果当前节点为null，则返回null。
如果当前节点小于p和q的值，则递归其左子节点。
反之递归其右子节点。
如果当前节点在p与q之间，则返回当前节点。
该节点是p与q的Lowest Common Ancestor。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(p.val < root.val && q.val < root.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        if(p.val > root.val && q.val > root.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}
Follow

Recents

Archives

Links

×