Category: Medium

Posted 2022-05-11Updated 2022-05-12LeetCode / Medium / 复习2 minutes read (About 262 words)

Question

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Solution

动态规划，创建数组dp[]记录以每个字符开头能组成的字符串数量。
由于当长度为1时，每个字符串都能组成一次，因此初始化所有值为1。

n增长时，每一个层级都等于该字符后的所有值相加。
最后得出的结果在下一个层级的第一位。（因为第一位是所有上一个层级加和）

Code

class Solution {
    public int countVowelStrings(int n) {
        int[] dp = new int[]{1,1,1,1,1};
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 5; j++){
                for(int k = j+1; k < 5; k++){
                    dp[j] += dp[k];
                }
            }
        }
        return dp[0];
    }
}

Solution

递归，使用成员变量计算有效递归次数。

Code

class Solution {
    int count;
    public int countVowelStrings(int n) {
        count = 0;
        count(n, 0);
        return count;
    }
    
    private void count(int n, int start){
        if(n == 0){
            count++;
            return;
        }
        for(int i = start; i < 5; i++){
            count(n-1, i);
        }
    }
}

Posted 2022-05-10Updated 2022-05-10LeetCode / Medium2 minutes read (About 260 words)

216. Combination Sum III

Question

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used.

Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Solution

回溯，创建一个成员变量visited[]记录访问情况。

剪枝优化，遍历所有可选择的数字，将其加和，如果加和大于target则返回。
剪枝优化，每层级遍历的范围大于传入列表中的最后一个元素。
回溯，向下递归。

如果k等于0并且sum等于target则添加arr到列表ret中。

Code

class Solution {
    int[] visited;
    List<List<Integer>> ret;

    public List<List<Integer>> combinationSum3(int k, int n) {
        visited = new int[9];
        ret = new ArrayList<>();
        backTracking(k, n, new ArrayList<>(), 0);
        return ret;
    }
    
    private void backTracking(int k, int target, List<Integer> arr, int sum){
        if(k == 0 && sum == target) ret.add(new ArrayList<>(arr));
        int start = 1;
        if(arr.size() != 0) start =  arr.get(arr.size()-1)+1;
        for(int i = start ; i <= 9; i++){
            if(visited[i-1] == 1) continue;
            sum+=i;
            if(sum > target) return;
            visited[i-1] = 1;
            arr.add(i);
            
            backTracking(k-1, target, arr, sum);
            sum-=i;
            arr.remove(new Integer(i));
            visited[i-1] = 0;
        }
    }
}

Posted 2022-05-08Updated 2022-05-08LeetCode / Medium3 minutes read (About 391 words)

341. Flatten Nested List Iterator

Question

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.

int next() Returns the next integer in the nested list.

boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

Solution

将所有的NestedInteger展开后加入全局变量队列。

辅助方法buildQueue():
递归，如果当前元素是列表，则向下递归列表内的所有元素。
如果当前元素是单个整数，则将其加入队列。

next():
返回并挤出队列中的下一个元素，返回其整数。

hasNext():
返回队列是否为空。

Code

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    Queue<NestedInteger> q;
    public NestedIterator(List<NestedInteger> nestedList) {
        q = new LinkedList<>();
        for(NestedInteger item : nestedList){
            buildQueue(item);
        }
    }
    
    private void buildQueue(NestedInteger ni){
        if(!ni.isInteger()){
            for(NestedInteger item : ni.getList()){
                buildQueue(item);
            }
        }
        else{
            q.offer(ni);
        }
    }

    @Override
    public Integer next() {
        return q.poll().getInteger();
    }

    @Override
    public boolean hasNext() {
        return !q.isEmpty();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

Posted 2022-05-08Updated 2022-05-07LeetCode / Medium / 复习3 minutes read (About 404 words)

456. 132 Pattern

Question

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Solution

单调栈，专门用于找某一个元素的左边/右边第一个比自己大/小的位置。
递增单调栈会提出波峰，留下波谷。递减单调栈会剔除波谷，留下波峰。

我们需要找到同时满足j < k和nums[k] <[j]情况的位置。因此采用单调栈正合适。
我们枚举132模式中的“3”，由于我们要找到波谷，因此可以采用递增栈。

递增单调栈的实现：

当遍历的当前值小于栈顶元素时，不满足递增规律，因此挤出栈顶。
循环此操作直至当前栈顶于当前值满足递增规律或栈空。
此时的当前值是nums[j]，而最后一个被挤出的值就是nums[k]。
由于递增单调栈的性质，此时的nums[k] < nums[j]且nums[k]大于被挤出的所有元素。

对于nums[i]，我们可以通过遍历nums[]数组，计算出其在i位置的最小值，并存在放minOfLeft[]中。

Code

class Solution {
    public boolean find132pattern(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int[] minOfLeft = new int[nums.length];
        minOfLeft[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            minOfLeft[i] = Math.min(minOfLeft[i-1], nums[i]);
        }

        for(int j = nums.length-1; j >= 0; j--){
            int k = Integer.MIN_VALUE;
            while(!stack.isEmpty() && nums[j] > stack.peek()){
                k = stack.pop();
            }
            if(minOfLeft[j] < k){
                return true;
            }
            stack.push(nums[j]);
        }
        return false;
    }
}

Posted 2022-05-07Updated 2022-05-08LeetCode / Medium / 复习5 minutes read (About 715 words)

450. Delete Node in a BST

Problem

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.

If the node is found, delete the node.

Solution

二叉搜索树（BST）的递增排序的访问顺序是中序遍历。（Left -> Root -> Right）

因此二叉搜索树的前驱者（小于当前节点的最大值）和继任者（大于当前节点的最小值）对于修改二叉树至关重要。

辅助方法getPredecessor() 和getSuccessor() 可以获得前驱者和继任者的值。
分别为当前根节点的左子节点的最右子节点（二叉搜索树下的最大值）和当前根节点右子节点的最左子节点。（二叉搜索树下的最小值）

deleteNode() 方法搜索key。如果当前值大于搜索值则搜索并修改其左子节点，反之搜索并修改右子节点。（由于要修改，因此向下递归子节点时需要将返回的结果传入该子节点。）

当搜索值等于当前值时，存在三种情况：
1.该子节点存在右子节点。此时我们将当前值设置为继任者的值，然后递归搜索右子节点中继任者的值进行删除。
2.该子节点存在左子节点。此时我们将当前值设置为前驱者的值，然后递归搜索左子节点中前驱者的值进行删除。
3.该子节点是叶子节点。直接删除当前节点。

最后返回修改后的根节点即可。

Code

/**
 * 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 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;     
        if(root.val > key) root.left = deleteNode(root.left, key);  //如果当前值大于搜索值则搜索左子节点，否则搜索右子节点
        else if(root.val < key) root.right = deleteNode(root.right, key);
        else{   //如果当前值等于搜索值，根据子节点情况删除节点
            if(root.right != null){ //右子节点不为空则将当前root的值设置为继任者的值，然后向下递归删除继任者
                root.val = getSuccessor(root);
                root.right = deleteNode(root.right, root.val);
            }
            else if(root.left != null){ //左子节点不为空则将当前root的值设置为前驱者的值，然后向下递归删除继任者
                root.val = getPredecessor(root);
                root.left = deleteNode(root.left, root.val);
            }
            else{
                root = null;
            }
        }
        return root;
    }
    
    private int getSuccessor(TreeNode root){
        root = root.right;
        while(root.left != null){
            root = root.left;
        }
        return root.val;
    }
    private int getPredecessor(TreeNode root){
        root = root.left;
        while(root.right != null){
            root = root.right;
        }
        return root.val;
    }
}

Posted 2022-05-06Updated 2022-05-08LeetCode / Medium2 minutes read (About 365 words)

1209. Remove All Adjacent Duplicates in String II

Question

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

Solution

用一个栈保存当前的字符，同时建立一个cnt[]数组记录当前字符连续出现的次数。

遍历字符串。

如果当前的字符与栈顶的字符相同时，获取数组中记录的当前连续次数lastCount并加一。
如果lastCount等于k，则匹配到了足够的字符，去掉栈顶的k - 1个元素。
否则将字符串加入栈顶，记录当前位置的出现次数lastCount。

如果当前字符与栈顶字符不同，则将字符直接加入栈顶，记录当前位置的cnt[dq.size()]为1。

最后将栈内元素倒序组成字符串。由于需要这一步操作，因此之前的栈采用双端队列实现。

Code

class Solution {
    public String removeDuplicates(String s, int k) {
        Deque<Character> dq = new LinkedList<Character>();
        int[] cnt = new int[s.length()+1];

        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(i > 0 && !dq.isEmpty() && dq.peek() == c){
                int lastCount = cnt[dq.size()];
                lastCount++;
                if(lastCount == k){
                    while(lastCount != 1){
                        dq.removeFirst();
                        lastCount--;
                    }
                }
                else{
                    dq.offerFirst(c);
                    cnt[dq.size()] = lastCount;
                }
            }
            else{
                dq.offerFirst(c);
                cnt[dq.size()] = 1;
            }
        }
        
        StringBuffer sb = new StringBuffer();
        while(!dq.isEmpty()){
            sb.append(dq.removeLast());
        }
        return sb.toString();
    }
}

Posted 2022-05-06Updated 2022-05-05LeetCode / Medium / 复习4 minutes read (About 538 words)

673. Number of Longest Increasing Subsequence

Question

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Solution

本题还有贪心算法+前缀和+二分查找的算法。

本题是300. Longest Increasing Subsequence的拓展。
同样采用动态规划，数组dp[i]记录到i为止最长递增数列长度。
可以用一个新的数组cnt[i]记录到i为止可以组成的最长递增数列的数量。

对于每个新位置i，cnt[i]的最小值为i。
遍历i之前的所有位置j。如果nums[j] < nums[i]，则i可以比dp[j]组成更长的递增数列，其长度为dp[j]+1。
如果dp[i] < dp[j]+1。则可以更新dp[i]。同时，cnt[i]可以从cnt[j]继承其计数。
如果dp[i] == dp[j]+1。则之前已经更新过dp[i]。说明有新的组合同样可以组成更长的递增数列。此时将cnt[j]加入当前的cnt[i]。

遍历完成i以内的所有j后，如果dp[i]大于当前的最长递增数列长度，则更新max。
同时更新长度的总数count为cnt[i]。
如果dp[i]等于max，则将cnt[i]加入计数count。
最后返回count。

Code

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] cnt = new int[n];
        int max = 0;
        int count = 0;
        
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            cnt[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];    //如果后面的数字大于前面的，且可以组成更长的数列，则继承之前的计数。
                    }
                    else if(dp[j] + 1 == dp[i]){    //如果之前已经更新过dp[i]，则有新的组合长度一直，加和之前的计数。
                        cnt[i] += cnt[j];
                    }
                }
            }
            if(dp[i] > max){    //如果当前的长度大于之前的最大值，则更新。
                max = dp[i];
                count = cnt[i];  //同时将之前计算的计数记录。
            }
            else if(dp[i] == max){  //如果有同样达到最大值的情况，则加和计数。
                count += cnt[i];
            }
        }
        return count;
    }
}

Posted 2022-05-05Updated 2022-05-05LeetCode / Medium / 复习2 minutes read (About 260 words)

973. K Closest Points to Origin

Question

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Solution

此题可以采用快速排序的思想。可以在O(n)时间复杂度里完成排序。

Solution 2

优先级队列，根据每个点距离的平方排序。时间复杂度O(nlogk)。

Code

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int[] point : points){
            pq.add(point);
        }
        for(int i = 0; i < k; i++){
            ret[i] = pq.poll();
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}

Solution 3

直接排序。时间复杂度为O(nlogn)。

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        Arrays.sort(points, (a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int i = 0; i < k; i++){
            ret[i] = points[i];
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}

Posted 2022-05-05Updated 2022-05-04LeetCode / Mediuma minute read (About 203 words)

451. Sort Characters By Frequency

Question

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Solution

哈希表记录字符出现的频率。然后将其添加到优先队列中。
最后根据优先级队列的顺序，加入每个字符对应的哈希表中记录的字符数。
理论上也可以用数组记录频率，但是问题中字符较复杂故未采用。

Code

class Solution {
    public String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        PriorityQueue<Character> pq = new PriorityQueue<>((a,b) -> map.get(b) - map.get(a));
        StringBuffer sb = new StringBuffer();
        for(char c : s.toCharArray()){
            map.put(c, map.getOrDefault(c, 0)+1);
        }
        for(char c : map.keySet()){
            pq.add(c);
        }
        while(!pq.isEmpty()){
            char c = pq.poll();
            for(int i = 0; i < map.get(c); i++){
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

Posted 2022-05-05Updated 2022-06-21LeetCode / Mediuma minute read (About 149 words)

215. Kth Largest Element in an Array

Problem

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Solution

直接排序数组，返回倒数第k个值。

Code

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Solution 2

采用优先级队列，将所有元素加入队列，采用倒序比较器。
挤出前k-1个值，然后返回第k个值。

Code

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int num : nums){
            pq.add(num);
        }
        for(int i = 0; i < k-1; i++){
            pq.poll();
        }
        return pq.peek();
    }
}

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

130. Surrounded Regions

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

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

841. Keys and Rooms

Question

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Solution

BFS，创建一个数组记录房间是否被访问。（用DFS搜素亦可。）

如果钥匙对应的房间已经访问过则跳过。
如果未访问过则记录为已访问并加入队列。

最后遍历一次访问状态，如果有没访问过的房间则返回false。反之返回true。

Code

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int[] visited = new int[rooms.size()];
        visited[0] = 1;
        Queue<List<Integer>> q = new LinkedList<>();
        q.add(rooms.get(0));
        
        while(!q.isEmpty()){
            List<Integer> keys = q.poll();
            for(int key : keys){
                if(visited[key] == 1) continue;
                visited[key] = 1;
                q.add(rooms.get(key));
            }
        }
        
        for(int i=1; i<rooms.size(); i++){
            if(visited[i] == 0) return false;
        }
        return true;
    }
}

Question

Solution

Code

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Problem

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Solution 2

Code

Solution 3

Question

Solution

Code

Problem

Solution

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Recents

Archives

Links