Category: LeetCode

Posted 2022-05-18Updated 2022-05-18LeetCode / Hard / 复习4 minutes read (About 544 words)

Question

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

Solution

参考：# 60 分钟搞定图论中的 Tarjan 算法

根据connections建立图（采用数组记录图速度比用哈希表实现快）。
然后采用Tarjon算法寻找图中的桥。

时间戳

按访问顺序为数组dfn[]添加顺序。
(dfn = depth first (traversal) number)

搜索树

在无向图中，每一次从u节点出发进行DFS搜索，每个节点只访问一次，所有被访问过的节点与边构成一棵树，称之为“无向连通图的搜索树”

追溯值

数组low[]记录从当前节点u出发时，能够访问到的所有节点中，时间戳最小的值。

无向图的桥的判定法则

在一张无向图中，判断边 e （其对应的两个节点分别为 u 与 v）是否为桥，需要其满足如下条件即可：dfn[u] < low[v]

Code

class Solution {
    int num;
    int[] visited;
    int[] dfn;
    int[] low;
    List<List<Integer>> ret;
    List<Integer>[] graph;
    
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        num = 0;
        ret = new ArrayList<>();
        visited = new int[n];
        dfn = new int[n];
        low = new int[n];
        graph = new ArrayList[n];
        
        buildGraph(n, connections);
        tarjan(0, -1);
        
        return ret;

    }
    
    private void tarjan(int u, int parent){
        dfn[u] = low[u] = num++;    //记录节点遍历的顺序并初始化low值
        visited[u] = 1;
        for(Integer v : graph[u]){
            if(v == parent) continue;
            if(visited[v] == 0){    //搜索未搜索过的相邻节点
                tarjan(v, u);
                low[u] = Math.min(low[u], low[v]);  //搜索相邻节点后，更新访问的最小值
                if(dfn[u] < low[v]){    //满足桥的定义时添加结果
                    List<Integer> e = new ArrayList<>();
                    e.add(u);
                    e.add(v);
                    ret.add(e);
                }
            }
            else{
                low[u] = Math.min(low[u], dfn[v]);  //如果搜索过相邻节点，则判断这两个值得最小值并更新
            }
        }
    }
    
    private void buildGraph(int n, List<List<Integer>> connections){
        for(int i = 0; i < n; i++){
            graph[i]=new ArrayList<>();
        }
        
        for(List<Integer> e : connections){
            int v1 = e.get(0);
            int v2 = e.get(1);
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
    }
}

Posted 2022-05-18Updated 2022-05-17LeetCode / 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

/**
 * 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 2022-05-15Updated 2022-05-14LeetCode / Medium2 minutes read (About 242 words)

2275. Largest Combination With Bitwise AND

Problem

The bitwise AND of an array nums is the bitwise AND of all integers in nums.

For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.

Also, for nums = [7], the bitwise AND is 7.

You are given an array of positive integers candidates. Evaluate the bitwise AND of every combination of numbers of candidates. Each number in candidates may only be used once in each combination.

Return *the size of the largest combination of candidates with a bitwise AND greater than *0.

Solution

相当于将各个数字进行掩码操作，计算各个数组的同一个位上1的数量即可。

bin[]数组记录各个数字的各个位上的1的数量。
如果当前数字与1进行掩码操作后等于1，则将该位数量加一。
然后将当前数字向右移动一位，直至将所有的位都统计完。

最后返回各个位上的最大值即可。

Code

class Solution {
    public int largestCombination(int[] candidates) {
        int[] bin = new int[31];
        int res = 0;
        for(int candidate : candidates){
            int count = 0;
            while(count < 31){
                if((candidate & 1) == 1){
                    bin[count]++;
                }
                candidate = candidate >> 1; 
                count++;
            }
        }
        for(int time : bin){
            res = Math.max(res, time);
        }
        return res;
    }
}

Posted 2022-05-15Updated 2022-05-14LeetCode / 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

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 2022-05-15Updated 2022-05-14LeetCode / Easy2 minutes read (About 319 words)

2273. Find Resultant Array After Removing Anagrams

Problem

You are given a 0-indexed string array words, where words[i] consists of lowercase English letters.

In one operation, select any index i such that 0 < i < words.length and words[i - 1] and words[i] are anagrams, and delete words[i] from words. Keep performing this operation as long as you can select an index that satisfies the conditions.

Return words after performing all operations. It can be shown that selecting the indices for each operation in any arbitrary order will lead to the same result.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase using all the original letters exactly once. For example, "dacb" is an anagram of "abdc".

Solution

由于只用查看上一个元素。
记录一个prev[]数组记录上一个元素的字符情况。
遍历words，用数组bin[]统计每个字母出现的次数，同时减去prev数组的统计数字。
如果数组中的每个统计结果都为0，则是上一个字符串的Anagram。
否则是一个新的字符串，将其加入结果。
然后将上一个数组prev更新为当前的统计数组bin[]。

Code

class Solution {
    public List<String> removeAnagrams(String[] words) {
        int[] prev = new int[26];
        
        List<String> ans = new ArrayList<>();
        
        for(String word : words){
            int[] bin = new int[26];
            char[] chars = word.toCharArray();
            for(int i = 0; i < chars.length; i++){
                prev[chars[i]-'a']--;
                bin[chars[i]-'a']++;
            }
            if(!allZero(prev)){
                ans.add(word);
            }
            prev = bin;
        }
        return ans;
    }
    
    private boolean allZero(int[] bin){
        for(int num : bin){
            if(num != 0) return false;
        }
        return true;
    }
}

Posted 2022-05-15Updated 2022-05-14LeetCode / Mediuma minute read (About 153 words)

1302. Deepest Leaves Sum

Question

Given the root of a binary tree, return the sum of values of its deepest leaves.

Solution

BFS搜索，层序遍历，每次计算每个层级的总和。
最后返回最后一个层级总和。

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 int deepestLeavesSum(TreeNode root) {
        Deque<TreeNode> q = new LinkedList<>();
        int res = 0;
        
        q.offer(root);
        
        int level = q.size();
        
        while(!q.isEmpty()){
            int sum = 0;
            for(int i = 0; i < level; i++){
                TreeNode curr = q.poll();
                sum += curr.val;
                if(curr.left != null) q.offer(curr.left);
                if(curr.right != null) q.offer(curr.right);
            }
            res = sum;
            level = q.size();
        }
        return res;
    }
}

Posted 2022-05-15Updated 2022-05-14LeetCode / Medium / 复习5 minutes read (About 773 words)

743. Network Delay Time

Question

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Solution

Dijkstra算法

此题可以转化为求起始节点到最远距离的节点的距离。单源最短路径问题，可以采用Dijkstra算法。

采用一个visited[]数组记录初始节点的访问状况。
同时dist[]数组记录到达这一节点的最小距离，初始化为无限大。

进行BFS搜索，每次优先访问当前节点的子节点的最近子节点，并更新子节点与初始节点距离。
最后遍历dist[]数组，如果有元素仍为无限大，则BFS搜索未遍历到，返回-1。
否则返回数组内最大的距离即可。

建立映射

首先通过哈希表，将起始节点与有向边建立起映射关系。列表中储存子节点和对应边上的权值。
注意由于index是-1的，因此在组成列表时需要将当前数字减一。

优先级队列

采用优先级队列组成小根堆，每次将当前的最小距离作为权值加入队列。
初始化队列时需要将起始节点（k-1）放入，此时的总距离为0。

当当前的子节点的cost加上起始节点的距离小于子节点的最小距离时，更新子节点最小距离。
同时将子节点当前最小距离作为比较对象传入优先级队列。

Code

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        HashMap<Integer, List<int[]>> edges = new HashMap<>(); 
        
        for(int[] time : times){    //建立有向边
            int source = time[0] - 1, kid = time[1] - 1, cost = time[2];    //注意index需要-1
            List<int[]> list = edges.getOrDefault(source, new ArrayList<>());
            list.add(new int[]{kid, cost});    //建立起点——终点映射
            edges.put(source, list);
        }
        
        int[] visited = new int[n];
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);    //优先级队列，最小堆每次访问距离最近的节点
        
        int start = k-1;
        dist[start] = 0;
        pq.offer(new int[]{start, 0});  //start为初始节点，后面的距离为了实现优先级队列
        
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            int source = curr[0];

            if(visited[source] == 1) continue;
            visited[source] = 1;
            
            List<int[]> children = edges.getOrDefault(source, new ArrayList<>());   //获取当前起点的所有边
            for(int[] child : children){
                int kid = child[0], cost = child[1];
                
                if(cost + dist[source] < dist[kid]){    //如果新的距离小于之前的最小距离，则更新距离并将新的起点加入优先级队列
                    dist[kid] = cost + dist[source];
                    pq.offer(new int[]{kid, dist[kid]});    //更新的距离是从出发节点到当前节点的距离，每次优先访问最近的节点
                }
            }
        }
        
        int res = 0;
        
        for(int d : dist){  //最后遍历，距离的最大值就是结果
            res = Math.max(res, d);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

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

1641. Count Sorted Vowel Strings

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-07LeetCode / Hard / 复习3 minutes read (About 423 words)

149. Max Points on a Line

Question

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Solution

首先选取一个点，然后创建哈希表。记录这个点与其他点的斜率关系与出现次数。记录一个出现次数最多的max值，如果当前次数大于max则更新max。

注意计算斜率时对y == 0和 x == 0时要返回无穷大和0，否则会有精度问题。
最后返回max + 1。

可以优化的地方是，当max大于总点数的一半，或者max大于剩余的点时，因为已经找到了最大的max值，可以直接返回答案。

Code

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if(n == 1) return 1;
        else if(n == 2) return 2;
        int max = 0;
        
        for(int i = 0; i < points.length; i++){
            if(max > points.length / 2) break;
            if(max > points.length - i) break;
            HashMap<Double, Integer> map = new HashMap<>();
            
            for(int j = i+1; j < points.length; j++){
                double k = getSlope(points[i], points[j]);
                int count = map.getOrDefault(k, 0) + 1;
                max = Math.max(max, count);
                map.put(k, count);
            }
        }
        return max + 1 ;
        
    }
    
    private double getSlope(int[] p1, int[] p2){
        double x1 = p1[0], y1 = p1[1], x2 = p2[0], y2 = p2[1];
        if(y1-y2 == 0) return Double.MAX_VALUE;
        if(x1-x2 == 0) return 0;
        double k = (x1 - x2) / (y1 - y2);
        return k;
    }
}

叉乘计算可以判断两个向量是否重合。
由于叉乘乘积（$|a||b|sinθ$）的模等于两个向量组成的平行四边形的面积，因此当两者乘积为0时，则两个向量重合。

点乘乘积得到的是向量在另一个向量上的投影的乘积，$|a||b|cosθ$

Posted 2022-05-06Updated 2022-05-05LeetCode / Easy / 复习2 minutes read (About 353 words)

202. Happy Number

Question

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.

Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.

Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Solution

首先证明，快乐数的计算不会趋近于无穷大。
我们可以考虑每一个位数的最大数字（9999…999）。
其下一个数值等于(81*n)。
对于三位数以下，其最大的值得下一个结果不会大于243。
对于四位数以上，下一个结果会快速收缩到三位数。
因此计算结果不会趋近于无穷。

当我们计算快乐数的值时，形成了一个隐式链表。
因此我们可以用快慢指针的方式，查询链表上是否有环。
快指针比慢指针初始值快1个单位，且移动速度为慢指针的一倍。
如果链表中有环，则两者终能相遇。
如果fast指针先走到1，等于走到了链表的终点。

Code

class Solution {
    public boolean isHappy(int n) {
        int slow = n, fast = getNext(n);
        while(fast != 1 && fast != slow){
            fast = getNext(getNext(fast));
            slow = getNext(slow);
        }
        return fast == 1;
    }
    
    private int getNext(int n){
        int sum = 0;
        while(n != 0){
            int digit = n % 10;
            sum += (digit * digit);
            n = n / 10;
        }
        return sum;
    }
}

Question

Solution

时间戳

搜索树

追溯值

无向图的桥的判定法则

Code

Question

Solution

Code

Problem

Solution

Code

Question

Solution

Code

Problem

Solution

Code

Question

Solution

Code

Question

Solution

Dijkstra算法

建立映射

优先级队列

Code

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

Code

Recents

Archives

Links