Tag: 每日一题

Posted 2022-07-29Updated 2022-08-03LeetCode / Medium2 minutes read (About 323 words)

Question

Given a list of strings words and a string pattern, return a list of words[i] that match pattern. You may return the answer in any order.

A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.

Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.

Solution

遍历words，对pattern和words中的字符建立映射。
used[]数组记录访问状况。

如未建立映射关系，且word中的字符已建立映射，则不在结果中添加当前字符串。
如未建立映射，则建立新的word与pattern的映射关系。
如果当前已经建立映射，但是当前字符违反了映射关系，则不在结果中添加当前字符串。

Code

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> ret = new ArrayList<>();
        for(String word : words){
            HashMap<Character, Character> map = new HashMap<>();    //map characters from pattern and words
            boolean isSamePattern = true;
            int[] used = new int[26];
            
            for(int i = 0; i < word.length(); i++){
                char pc = pattern.charAt(i), wc = word.charAt(i);
                if( !map.containsKey(pc) ){
                    if(used[wc-'a'] == 0){  //add new map if there is no map between characters and the character in word is not used
                        map.put( pc, wc );
                        used[wc-'a']++;
                    }
                    else{
                        isSamePattern = false;
                        break;
                    }
                }
                else if( map.get(pc) != wc ){   //drop the word if not follow the pattern
                    isSamePattern = false;
                    break;
                }
            }
            if(isSamePattern) ret.add(word);
        }
        return ret;
    }
}

Posted 2022-07-27Updated 2022-07-27LeetCode / Medium / 复习2 minutes read (About 343 words)

114. Flatten Binary Tree to Linked List

Question

Given the root of a binary tree, flatten the tree into a “linked list”:

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

The “linked list” should be in the same order as a pre-order** traversal** of the binary tree.

Solution

全局变量prev，初始化为null，用来记录上一个访问的节点。

由于最后要达到先序遍历（根节点-左子节点-右子节点）的数据结构顺序，因此在进行访问时需要与先序遍历的操作相反，首先递归右子节点，然后递归左子节点，最后修改当前节点。

先遍历当前节点的右侧节点，再遍历当前节点的左侧节点。
最后处理当前节点，将左子节点设置为null，右子节点设置为prev。
最后将当前节点保存在prev上。

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 {
    TreeNode prev = null;
    public void flatten(TreeNode root) {
        if(root == null) return;
        flatten(root.right);    //traverse right nodes first
        flatten(root.left); //traverse left nodes
        root.left = null;   //set current node's left child node to null
        root.right = prev;  //set current node's right child node to previous node
        prev = root;    //update previous node
    }
}

Posted 2022-07-24Updated 2022-07-24LeetCode / Mediuma minute read (About 155 words)

34. Find the Element in Sorted Array

Question

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.

Solution

二分搜索，首先搜索target。如果搜索到结果为负数，则返回[-1, -1]。
如果搜索到target，则记录index。
然后从index向两边搜索，直到找到界限并返回。

Code

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        int index = 0;
        index = Arrays.binarySearch(nums, target);
        if(index < 0){
            ret[0] = -1;
            ret[1] = -1;
            return ret;
        }
        int less = index, more = index;
        while(less >= 0 && nums[less] == target) less--;
        while(more < nums.length && nums[more] == target) more++;
        
        ret[0] = less + 1;
        ret[1] = more - 1;
        return ret;
    }
}

Posted 2022-07-22Updated 2022-07-22LeetCode / Medium3 minutes read (About 442 words)

86. Partition List

Question

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Solution 1

生成前后两个部分的dummy链表头。
遍历原链表，当当前值小于x时则将当前节点添加到第一个链表头后。
当当前值大于x时则将当前节点添加到第二个链表头后。

遍历完成后将第二个链表头的下一个节点添加到第一个链表的下一个节点上。然后将第二个链表的尾部指向null。

返回第一个dummy链表节点的下一个节点即可。

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(), dummy2 = new ListNode();
        ListNode hd1 = dummy1, hd2 = dummy2;
        while(head != null){
            if(head.val < x){
                dummy1.next = head;
                dummy1 = dummy1.next;
            }
            else{
                dummy2.next = head;
                dummy2 = dummy2.next;
            }
            head = head.next;
        }
        dummy1.next = hd2.next;
        dummy2.next = null;
        
        return hd1.next;
    }
}

Solution 2

遍历整个链表，根据各个节点的值将其保存在两个队列中。

设置一个dummy节点头，将两个队列中的节点按顺序挤出并生成新链表。
返回dummy节点头的下一个节点即可。

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        Queue<ListNode> q1 = new LinkedList<>();
        Queue<ListNode> q2 = new LinkedList<>();
        while(head != null){
            if(head.val < x) q1.add(head);
            else q2.add(head);
            head = head.next;
        }
        
        ListNode dummy = new ListNode();
        ListNode res = dummy;
        
        while(!q1.isEmpty()){
            res.next = q1.poll();
            res = res.next;
        }
        
        while(!q2.isEmpty()){
            res.next = q2.poll();
            res = res.next;
        }
        res.next = null;
        return dummy.next;
    }
}

Posted 2022-07-16Updated 2022-07-16LeetCode / Medium / 复习3 minutes read (About 449 words)

576. Out of Boundary Paths

Question

There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.

Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 109 + 7.

Solution

DFS，记忆化搜索哦剪枝。

记忆化搜索

三维数组memo[][][]用来记录起点为startRow, startColumn，剩余距离为maxMove时的总路径数。
注意需要将memo[][][]所有数值初始化为-1。否则在进行BFS搜索时，无法对maxMove等于0的情况进行剪枝。

DFS

当当前位置越界，则为一个有效路径，返回1。
当剩余步数为0时，无法继续移动，返回0。

如果当前位置与剩余步数的状态已经被搜索并记录过，则直接返回memo[startRow][startColumn][maxMove]。
如果未搜索，则将maxMove减一，并向四周移动一格，对当前位置的四个方向进行递归。
记忆当前位置的四个方向的总路径数之和，模除后返回。

Code

class Solution {
    final int MOD = (int) Math.pow(10, 9) + 7;
    long[][][] memo;
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        memo = new long[m][n][maxMove];
       for(int i = 0; i < m; i++){
           for(int j = 0; j < n; j++){
               for(int k = 0; k < maxMove; k++){
                   memo[i][j][k] = -1;
               }
           }
       }
        return (int) dfs(m, n, maxMove, startRow, startColumn);
    }
    
    private long dfs(int m, int n, int maxMove, int startRow, int startColumn){
        if(startRow < 0 || startRow >= m || startColumn < 0 || startColumn >= n) return 1;
        if(maxMove == 0) return 0;
        
        maxMove--;
        if(memo[startRow][startColumn][maxMove] != -1) return memo[startRow][startColumn][maxMove];
        
        long left = dfs(m, n, maxMove, startRow-1, startColumn);
        long right = dfs(m, n, maxMove, startRow+1, startColumn);
        long up = dfs(m, n, maxMove, startRow, startColumn+1);
        long down = dfs(m, n, maxMove, startRow, startColumn-1);

        memo[startRow][startColumn][maxMove] = (left + right + up + down) % MOD;
        return memo[startRow][startColumn][maxMove];
    }
}

Posted 2022-07-13Updated 2022-07-16LeetCode / Medium / 复习2 minutes read (About 279 words)

473. Matchsticks to Square

Question

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

Solution

回溯，用int[] edges记录边长。

先计算所有火柴棍的长度之和是否能被4整除，如果不能则返回false。
将所有火柴排序，以减少回溯时的计算量。

Backtracking 回溯

当遍历越界时（传入index为-1），则返回true。

每次将当前火柴matchsticks[index]添加到一个edges[i]中。
当edges[i] <= sum / 4，且向前回溯前一个位置index-1返回结果为真，则返回true。
然后将当前火柴从edges[i]中取出。

Code

class Solution {
    int[] edges;
    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for(int i = 0; i < matchsticks.length; i++) sum += matchsticks[i];
        if(sum % 4 != 0) return false;
        
        edges = new int[4];
        Arrays.sort(matchsticks);
        return backtracking(matchsticks, matchsticks.length-1, sum/4);
    }
    
    public boolean backtracking(int[] matchsticks, int index, int len){
        if(index == -1) return true;

        for(int i = 0; i < 4; i++){
            edges[i] += matchsticks[index];
            if(edges[i] <= len && backtracking(matchsticks, index - 1, len)) return true;
            edges[i] -= matchsticks[index];
        }
        return false;
    }
}

Posted 2022-07-10Updated 2022-07-11LeetCode / Easy / 复习a minute read (About 134 words)

746. Min Cost Climbing Stairs

Question

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Solution

动态规划，每一个新位置的等于前一个位置加上其cost和前两个位置加上cost的较小值。

Code

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length+1];
        for(int i = 2; i <= cost.length; i++){
            dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[cost.length];
    }
}

Posted 2022-07-07Updated 2022-07-06a minute read (About 163 words)

509. Fibonacci Number

Question

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).

Solution 1

记忆化搜索，在递归时递归过的n放入数组memo中记录。

Code

class Solution {
    int[] memo;
    public int fib(int n) {
        if(n == 0 || n == 1) return n;
        memo = new int[n+1];
        return fibo(n);
    }
    
    private int fibo(int n){
        if(n == 0 || n == 1) return n;
        if(memo[n] == 0) memo[n] = fibo(n-1) + fibo(n-2);
        return memo[n];
    }
}

Solution 2

递归，当n等于0或者1时返回固定值。
否则返回fib(n-1)+fib(n-2)。

Code

class Solution {
    public int fib(int n) {
        if(n == 0 || n == 1) return n;
        return fib(n-1) + fib(n-2);
    }
}

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

128. Longest Consecutive Sequence

Question

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Solution 1

哈希表，先将所有元素加入哈希表。
然后遍历哈希表，如果表内没有当前数字-1时（没有更小的连续数字），则将temp初始化为1。
当表内有下一个连续数字时，将temp和curNum增加1。

当没有下一个连续数字时，更新结果到res上。

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        
        for(int num : nums){
            set.add(num);
        }
        
        int res = 0;
        
        for(int num : set){
            if(!set.contains(num - 1)){
                int temp = 1;
                int curNum = num;
                while(set.contains(curNum + 1)){
                    temp++;
                    curNum++;
                }
                res = Math.max(res, temp);
            }
        }
        return res;
    }
}

Solution 2

先排序，再遍历。
维护一个最大长度res。
用一个temp参数记录连续长度。
如果当前值是上一个值+1，则temp+1。
如果当前值等于上一个值，则continue。
其他情况则更新最大长度res，并将temp恢复为1。

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        Arrays.sort(nums);
        int res = 0, temp = 1;
        
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == nums[i-1] + 1){
                temp++;
            }
            else if(nums[i] == nums[i-1]){
                continue;
            }
            else{
                res = Math.max(res, temp);
                temp = 1;
            }
        }
        res = Math.max(res, temp);
        
        return res;
    }
}

Posted 2022-07-04Updated 2022-07-04LeetCode / Hard / 复习2 minutes read (About 227 words)

135. Candy

Question

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Solution

双向遍历。
先从左至右遍历数组，如果上一个数值小于当前数值，则当前糖果等于上一个糖果数+1。
然后从右至左遍历数组，同理计算right的数值。
然后保存right与left[]里较大的数值，作为需要分配的糖果数加入到res。

Code

class Solution {
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        for(int i = 0; i < ratings.length; i++){
            if(i > 0 && ratings[i] > ratings[i-1]){
                left[i] = left[i-1] + 1;
            }
            else{
                left[i] = 1;
            }
        }
        
        int right = 0, res = 0;
        for(int i = ratings.length-1; i >= 0; i--){
            if(i < ratings.length-1 && ratings[i] > ratings[i+1]){
                right++;
            }
            else{
                right = 1;
            }
            res += Math.max(left[i], right);
        }
        return res;
    }
}

Posted 2022-07-02Updated 2022-07-01LeetCode / Medium2 minutes read (About 264 words)

1465. Max Area After Horizontal and Vertical Cuts

Question

You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where:

horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, and

verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 109 + 7.

Solution

先排序，记录两次切割之间的距离的最大值。
最后同样需要比较蛋糕的总尺寸和最后一次切割的距离。

返回宽度和长度的最大值的乘积即可。

注意：两个int整数相乘会溢出，max需要记录为long类型。

Code

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        int MOD = (int) Math.pow(10,9)+7;
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        long maxH = 0, maxV = 0;
        int lastH = 0, lastV = 0;
        
        for(int i = 0; i < horizontalCuts.length; i++){
            maxH = Math.max(maxH, horizontalCuts[i] - lastH);
            lastH = horizontalCuts[i];
        }
        
        maxH = Math.max(maxH, h - lastH);
        
        for(int i = 0; i < verticalCuts.length; i++){
            maxV = Math.max(maxV, verticalCuts[i] - lastV);
            lastV = verticalCuts[i];
        }
        
        maxV = Math.max(maxV, w - lastV);
        return (int) (maxV * maxH % MOD) ;
    }
}

Posted 2022-07-01Updated 2022-07-01LeetCode / Easya minute read (About 221 words)

1710. Maximum Units on a Truck

Question

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

numberOfBoxesi is the number of boxes of type i.

numberOfUnitsPerBoxi is the number of units in each box of the type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

Solution

根据每个箱子可以装最多单元从大到小排序。
遍历数组，如果truckSize还有剩余，则将res增加容量乘以箱子数量。
然后将truckSize减少箱子数量个。

最后返回res即可。

Code

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        int res = 0;
        Arrays.sort(boxTypes, (a,b) -> b[1] - a[1]);
        for(int i = 0; i < boxTypes.length; i++){
            int numberOfBoxes = boxTypes[i][0];
            int numberOfUnitesPerBox = boxTypes[i][1];
            
            if(truckSize <= numberOfBoxes){
                res += numberOfUnitesPerBox * truckSize;
                break;
            }
            else{
                truckSize -= numberOfBoxes;
                res += numberOfBoxes * numberOfUnitesPerBox;
            }
        }
        return res;
    }
}

Posted 2022-06-28Updated 2022-07-01LeetCode / Medium2 minutes read (About 227 words)

1647. Make Character Frequencies Unique

Question

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return* the minimum number of characters you need to delete to make s good.*

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Solution

数组统计+哈希表
用数组统计记录每个字符出现的数量。
count记录需要减少的字符数量。

遍历统计数组，如果哈希表中已经记录，则将数组统计减少，直到归零。
每减少一次则为count加一。
如果哈希表中未记录，则将当前数字添加到哈希表中。

Code

class Solution {
    public int minDeletions(String s) {
        int count = 0;
        HashSet<Integer> set = new HashSet<>();
        int[] bin = new int[26];
        for(char c : s.toCharArray()){
            bin[c - 'a']++;
        }
        
        for(int i = 0; i < 26; i++){
            while(bin[i] !=0 && set.contains(bin[i])){
                bin[i]--;
                count++;
            }
            set.add(bin[i]);
        }
        return count;
    }
}

Posted 2022-06-27Updated 2022-06-27LeetCode / Mediuma few seconds read (About 100 words)

1689. Partitioning Into Deci-Binary Numbers

Question

A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not.

Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.

Solution

遍历所有字符，返回字符串中的最大整数。

Code

class Solution {
    public int minPartitions(String n) {
        char max = '0';
        for(char s : n.toCharArray()){
            if(s > max) max = s;
        }
        return max - '0';
    }
}

Posted 2022-06-26Updated 2022-06-25LeetCode / Medium3 minutes read (About 390 words)

1423. Maximum Points You Can Obtain from Cards

Question

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Solution 1

这种取两端的问题可以转化为取中间连续k个元素之和最小。

计算所有数字的和sum。
然后用维护一个宽度为k的窗口内的加和temp，并记录其最小值min。

返回sum - min，结果即是取两侧时可以取的最大值。

Code

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, sum = 0;
        for(int point : cardPoints) sum += point; //求所有数值的和
        if(k == n) return sum;
        int left = 0, right = n-k, temp = 0, min = 0;
        
        for(int i = 0; i < n-k; i++){
            temp += cardPoints[i];
            min = temp;
        }
        while(right < n){   //维护窗口内的temp，并更新min
            temp += cardPoints[right] - cardPoints[left];; 
            min = Math.min(min, temp);
            right++;
            left++;
        }
        return sum - min;
    }
}

Solution 2

分别计算从两侧开始的加和并记录在两个数组left[]和right[]上。

然后分别取两个指针，左侧指针l从0开始遍历到k，右侧指针对应的位置为l+n-k。计算并更新最大值max。

Code

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, max = 0;
        int[] left = new int[n+1], right = new int[n+1];
        
        for(int i = 0; i < n; i++){
            left[i+1] = left[i] + cardPoints[i];
            right[n-i-1] = right[n-i] + cardPoints[n-i-1];
        }
        
        for(int l = 0; l <= k; l++){
            max = Math.max(max, left[l] + right[n-k+l]);
        }
        
        return max;
    }
}

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution

记忆化搜索

DFS

Code

Question

Solution

Backtracking 回溯

Code

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Recents

Archives

Links