Hexo

Posted 2022-08-23Updated 2022-08-23LeetCode / Easya few seconds read (About 109 words)

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 == 3x.

Solution

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

Code

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

Posted 2022-08-22Updated 2022-08-22LeetCode / 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

/**
 * 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

/**
 * 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

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

Posted 2022-08-22Updated 2022-08-22LeetCode / 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 == 4x.

Solution

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

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

Code

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

Posted 2022-08-21Updated 2022-08-21LeetCode / Medium / 复习3 minutes read (About 466 words)

659. Split Array into Consecutive Subsequences

Question

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).

All subsequences have a length of 3** or more**.

Return true* if you can split nums according to the above conditions, or false otherwise*.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

Solution

用优先级队列储存每个可组成的列表。
优先级队列根据列表的长度排列。

用哈希表记录每个列表的尾数，和其对应的优先级队列。
遍历所有数字，如果存在当前数字num-1为尾数的队列，则获取长度最小的列表，并添加当前数字num在列表中。
然后将新的优先级队列放入哈希表中。

遍历整个哈希表中的数组，如果有数组的长度小于3，则返回false，否则返回true。

Code

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer, PriorityQueue<List<Integer>>> map = new HashMap<>();
        
        for(int num : nums){
            PriorityQueue<List<Integer>> last = map.getOrDefault(num - 1, null);
            PriorityQueue<List<Integer>> curr = map.getOrDefault(num, new PriorityQueue<List<Integer>>((a,b) -> a.size() - b.size()));

            if(last == null || last.size() == 0){
                List<Integer> arr = new ArrayList<>();
                arr.add(num);
                curr.add(arr);
                map.put(num, curr);
            }
            else{
                List<Integer> arr = last.poll();
                arr.add(num);
                curr.add(arr);
                map.put(num, curr);
            }
        }                   
                                      
        for(int last : map.keySet()){
            for(List<Integer> arr : map.get(last)){
                if(arr.size() < 3) return false;
            }
        }
        return true;
        
    }
}

Solution 2

不需要保存整个列表，只需要保存对应末尾数字的列表长度即可。

Code

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        
        for(int num : nums){
            PriorityQueue<Integer> last = map.getOrDefault(num - 1, null);
            PriorityQueue<Integer> curr = map.getOrDefault(num, new PriorityQueue<Integer>());

            if(last == null || last.size() == 0){
                curr.add(1);
                map.put(num, curr);
            }
            else{
                int min = last.poll();
                curr.add(min+1);
                map.put(num, curr);
            }
        }                   
                                      
        for(int last : map.keySet()){
            for(int len : map.get(last)){
                if(len < 3) return false;
            }
        }
        return true;

    }
}

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

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();
    }
}

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Solution 3

Code

Question

Solution

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Recents

Archives

Links