2760. Longest Even Odd Subarray With Threshold
Posted Updated LeetCode / Easy2 minutes read (About 229 words)

2760. Longest Even Odd Subarray With Threshold

Question

You are given a 0-indexed integer array nums and an integer threshold.

Find the length of the longest subarray of numsstarting at index l and ending at index r (0 <= l <= r < nums.length) that satisfies the following conditions:

  • nums[l] % 2 == 0
  • For all indices i in the range [l, r - 1], nums[i] % 2 != nums[i + 1] % 2
  • For all indices i in the range [l, r], nums[i] <= threshold
Read more
2259. Remove Digit From Number to Maximize Result
Posted Updated LeetCode / Easya minute read (About 184 words)

2259. Remove Digit From Number to Maximize Result

Question

You are given a string number representing a positive integer and a character digit.

Return the resulting string after removing exactly one occurrence of digit from number such that the value of the resulting string in decimal form is maximized. The test cases are generated such that digit occurs at least once in number.

Read more
1572. Matrix Diagonal Sum
Posted Updated LeetCode / Easya minute read (About 132 words)

1572. Matrix Diagonal Sum

Question

Given a square matrix mat, return the sum of the matrix diagonals.

Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.

Read more
26. Remove Duplicates from Sorted Array
Posted Updated LeetCode / Easy2 minutes read (About 300 words)

26. Remove Duplicates from Sorted Array

Question

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k* after placing the final result in the first k slots of *nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Solution

由于数组本身已经排序，只要比较当前nums中的元素是否大于上一个保存的数值就可以决定是否保留。
创建一个k记录遍历的位置，每次比较nums[k]与nums[i]的位置元素的大小，如果当前的nums[i]大于nums[k]，则将k位置向后移动1，并将下一个位置记录为nums[i]。

最后返回k+1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[k] < nums[i]){
                k++;
                nums[k] = nums[i];
            }
        }
        return k + 1;
    }
}
606. Construct String from Binary Tree
Posted Updated LeetCode / Easy2 minutes read (About 277 words)

606. Construct String from Binary Tree

Question

Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.

Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.

Solution

DFS搜索，先序遍历到每个节点将其加入StringBuffer。
如果当前节点有左子节点或右子节点，则递归左子节点，并在前后添加一对括号。（如果有右子节点的情况即使左子节点为空也需要添加一对括号加以区别。）
如果当前节点有右子节点，则递归右子节点，并在前后添加一对括号。

Code

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
/**
 * 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 {
    StringBuffer sb;
    public String tree2str(TreeNode root) {
        sb = new StringBuffer();
        dfs(root);
        return sb.toString();
    }
    
    private void dfs(TreeNode root){
        if(root == null) return;
        sb.append(root.val);
        
        boolean hasLeft = root.left != null, hasRight = root.right != null;
        
        if(hasLeft || hasRight) sb.append("(");
        dfs(root.left);
        if(hasLeft || hasRight) sb.append(")");
        
        if(hasRight) sb.append("(");
        dfs(root.right);
        if(hasRight) sb.append(")");
    }
}
383. Ransom Note
Posted Updated LeetCode / Easya minute read (About 125 words)

383. Ransom Note

Question

Given two strings ransomNote and magazine, return true* if ransomNote can be constructed by using the letters from magazine and false otherwise*.

Each letter in magazine can only be used once in ransomNote.

Solution

数组统计，统计magazine内的字符。
遍历ransomNote，如果对字符数组位置为0则返回false。
每次遍历减少数组统计结果。

最后返回true。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] bin = new char[26];
        
        for(char c : magazine.toCharArray()) bin[c-'a']++;
        for(char c : ransomNote.toCharArray()){
            if(bin[c-'a'] == 0) return false;
            bin[c-'a']--;
        }
        
        return true;
    }
}
326. Power of Three
Posted Updated LeetCode / Easya few seconds read (About 109 words)

326. Power of Three

Question

Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer n is a power of three, if there exists an integer x such that n == 3<sup>x</sup>.

Solution

与isPowerOfFour相同，如果n小于0则返回false。
如果n等于1则返回true。
递归，如果n可以整除3，则返回isPowerOfThree(n / 3)。
否则返回false。

Code

1
2
3
4
5
6
7
8
class Solution {
    public boolean isPowerOfThree(int n) {
        if(n <= 0) return false;
        if(n == 1) return true;
        if(n % 3 == 0) return isPowerOfThree(n / 3);
        else return false;
    }
}
234. Palindrome Linked List
Posted Updated LeetCode / Easy4 minutes read (About 603 words)

234. Palindrome Linked List

Question

Given the head of a singly linked list, return true if it is a palindrome.

Solution 1

快慢指针，快指针遍历到底时慢指针正好到一半。
根据快指针的位置判断奇数个还是偶数个。
如果是奇数个则翻转链表时需要向前移动一位。

接下来翻转后半段链表。
翻转完成后从第一段的头部和翻转过的链表头部开始遍历。
如果两个节点的值不同则返回false。

遍历完毕返回true。

Code

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
/**
 * 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 boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode slow = head, fast = head;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode curr = fast == null ? slow : slow.next, prev = null;   //make sure curr is the head of the 2nd part
        
        while(curr != null){    //reverse the 2nd part of the nodes
            ListNode temp = curr.next; //preserve nodes that after current node
            curr.next = prev; //add previous node to the current node's next
            prev = curr; //save previous node
            curr = temp; //update current node
        }
        
        while(head != null && prev != null){
            if(head.val != prev.val) return false;
            prev = prev.next;
            head = head.next;
        }
        return true;
    }
}

Solution 2

快慢指针的原理，不是记录长度而是当快指针遍历到链表尾时停止。
然后对照栈内的值是否和剩余的值相等。

Code

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
/**
 * 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 boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        Stack<ListNode> stack = new Stack<>();

        while(fast != null && fast.next != null){
            stack.add(slow);

            slow = slow.next;
            fast = fast.next.next;
        }
        
        if(fast != null) slow = slow.next;
        
        while(!stack.isEmpty()){
            if(stack.pop().val != slow.val) return false;
            slow = slow.next;
        }
        
        return true;
    }
}

Solution 3

回文，先计算链表长度。
记录链表长度是否为奇数。

如果链表长度为偶数，则将一半的节点放入栈中。
如果为奇数则抛弃一个节点。
剩下一半的节点和栈顶节点比较，如果值不相同则返回false。

遍历完成返回true。

Code

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
/**
 * 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 boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode root = head;
        Stack<ListNode> stack = new Stack<>();
        
        while(root != null){
            root = root.next;
            len++;
        }
        
        root = head;
        for(int i = 0; i < len/2; i++){
            stack.add(root);
            root = root.next;
        }
        
        if(len % 2 != 0) root = root.next;
        
        for(int i = 0; i < len/2; i++){
            if(stack.peek().val == root.val) stack.pop();
            else return false;
            root = root.next;
        }
        return true;
    }
}
342. Power of Four
Posted Updated LeetCode / Easya few seconds read (About 102 words)

342. Power of Four

Question

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4<sup>x</sup>.

Solution

递归，如果n小于等于零则返回false。
如果n等于1则返回true。

如果n可以除以4，则递归返回n/4。

Code

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean isPowerOfFour(int n) {
        if(n <= 0) return false;
        if(n == 1) return true;
        
        if(n % 4 == 0) return isPowerOfFour(n / 4);
        else return false;
    }
}
804. Unique Morse Code Words
Posted Updated LeetCode / Easya minute read (About 149 words)

804. Unique Morse Code Words

Question

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows:

  • 'a' maps to ".-",
  • 'b' maps to "-...",
  • 'c' maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Given an array of strings words where each word can be written as a concatenation of the Morse code of each letter.

  • For example, "cab" can be written as "-.-..--...", which is the concatenation of "-.-.", ".-", and "-...". We will call such a concatenation the transformation of a word.

Return the number of different transformations among all words we have.

Solution

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] alphabet = new String[]{".-","-...","-.-.","-..",".","..-.","--.",
                                         "....","..",".---","-.-",".-..","--","-.",
                                         "---",".--.","--.-",".-.","...","-","..-",
                                         "...-",".--","-..-","-.--","--.."};
        HashSet<String> set = new HashSet<>();
        
        for(String word : words){
            StringBuffer sb = new StringBuffer();
            for(char c : word.toCharArray()){
                sb.append(alphabet[c - 'a']);
            }
            set.add(sb.toString());
        }
        
        return set.size();
    }
}
13. Roman to Integer
Posted Updated LeetCode / Easy2 minutes read (About 342 words)

13. Roman to Integer

Question

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Solution

倒叙遍历，记录几个mark以标注是否出现对应的字母。

初始res为0，根据字符加减数值。
如果出现则将mark设置为真。
如果mark为真，且上一个字符出现对应需要减去的罗马字符，则改加为减。

最后返回res值。

Code

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
class Solution {
    public int romanToInt(String s) {
        int res = 0;
        boolean markX = false, markC = false, markM = false;
        
        for(int i = s.length()-1; i >= 0; i--){
            char c = s.charAt(i);
            if(c == 'I'){
                if(markX) res -= 1;
                else res += 1;
            }
            else if(c == 'V'){
                markX = true;
                res += 5;
            }
            else if(c == 'X'){
                markX = true;
                if(markC) res -= 10;
                else res += 10;
            }
            else if(c == 'L'){
                markC = true;
                res += 50;
            }
            else if(c == 'C'){
                markC = true;
                if(markM) res -= 100;
                else res += 100;
            }
            else if(c == 'D'){
                markM = true;
                res += 500;
            }
            else if(c == 'M'){
                markM = true;
                res += 1000;
            }
        }
        return res;
    }
}
746. Min Cost Climbing Stairs
Posted Updated LeetCode / 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

1
2
3
4
5
6
7
8
9
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];
    }
}
1710. Maximum Units on a Truck
Posted Updated LeetCode / 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] = [numberOfBoxes<sub>i</sub>, numberOfUnitsPerBox<sub>i</sub>]:

  • numberOfBoxes<sub>i</sub> is the number of boxes of type i.
  • numberOfUnitsPerBox<sub>i</sub> 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 Updated LeetCode / Easya minute read (About 155 words)

2319. Check if Matrix Is X-Matrix

Question

A square matrix is said to be an X-Matrix if both of the following conditions hold:

  1. All the elements in the diagonals of the matrix are non-zero.
  2. All other elements are 0.

Given a 2D integer array grid of size n x n representing a square matrix, return true* if grid is an X-Matrix*. Otherwise, return false.

Solution

遍历，直接判断是否在对角线上，如果在且位置为0，则返回false。
如果不在对角线上，且位置部位0，则返回false。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean checkXMatrix(int[][] grid) {
        int n = grid.length;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == j || i + j == n - 1){
                    if(grid[i][j] == 0) return false;
                }
                else if(grid[i][j] != 0) return false;
            }
        }
        return true;
    }
}
Posted Updated LeetCode / Easya minute read (About 119 words)

2315. Count Asterisks

Question

You are given a string s, where every two consecutive vertical bars '|' are grouped into a pair. In other words, the 1st and 2nd '|' make a pair, the 3rd and 4th '|' make a pair, and so forth.

Return *the number of '*' in s, excluding the '*' between each pair of *'|'.

Note that each '|' will belong to exactly one pair.

Solution

统计“|”字符出现的数量，如果数量为偶数时，则计算出现的“*”符号。

Code

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int countAsterisks(String s) {
        int num = 0, count = 0;
        for(char c : s.toCharArray()){
            if(c == '|') num++;
            else if((num & 1) == 0 && c == '*') count++;
        }
        return count;
    }
}
Follow

Recents

Archives

Links

×