[LeetCode] 234. Palindrome Linked List

Problem : https://leetcode.com/problems/palindrome-linked-list/

Use post-order traversal to check the input string recursively.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        left = 0
        
        def postorder(node, right):
            nonlocal head
            nonlocal left
            
            if node:
                tmp = postorder(node.next, right + 1)
                if not tmp:
                    return tmp
                
                if left < right:
                    if node.val != head.val:
                        return False
                
                    head = head.next
                    left += 1
                
                return True
                
            return True
        
        return postorder(head, 0)

[LeetCode] 233. Number of Digit One

Problem : https://leetcode.com/problems/number-of-digit-one/

class Solution:
    def countDigitOne(self, n: int) -> int:
        result, a, b = 0, 1, 1
        
        while n > 0:
            result += (n + 8) // 10 * a
            if n % 10 == 1:
                result += b
                
            b += n % 10 * a
            a *= 10
            
            n //= 10
            
        
        return result

[LeetCode] 232. Implement Queue using Stacks

Problem : https://leetcode.com/problems/implement-queue-using-stacks/

Use 2 stacks

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = []
        

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.stack.append(x)
        

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        result = 0
        tmp = []
        while len(self.stack) > 1:
            tmp.append(self.stack.pop())
        
        result = self.stack.pop()
        while tmp:
            self.stack.append(tmp.pop())
        
        return result
        

    def peek(self) -> int:
        """
        Get the front element.
        """
        result = 0
        tmp = []
        while len(self.stack) > 1:
            tmp.append(self.stack.pop())
        
        result = self.stack[0]
        while tmp:
            self.stack.append(tmp.pop())
        
        return result
        

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.stack) == 0
        


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

[LeetCode] 231. Power of Two

Problem : https://leetcode.com/problems/power-of-two/

Iteration solution:

Time complexity = O ( Log N )

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        while n > 1:
            if n % 2 != 0:
                return False

            # n = n // 2
            n = n >> 1
           
        return n == 1

Recursion solution:

Time complexity = O ( Log N )

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        
        if n == 1:
            return True
        
        return n % 2 == 0 and self.isPowerOfTwo(n >> 1)

Bit manipulate solution:

Time complexity = O ( 1 )

 
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:   
        
        count = 0
        while n > 0 and count <= 1:
            count += n & 1
            n >>= 1
        
        return count == 1

Number may have only one bit equals to 1 if it is power of 2.

With that observation in mind, we have the one liner solution:

n & (n-1) can trim the first '1' bit from right.

n & (n-1) == 0 means number n only as one '1' bit.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:    
        return n > 0 and (n - 1) & n == 0

n & (-n) can extract the firt '1' bit from right.

n & (-n) == n also means number n only as one '1' bit.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and n & (-n) == n

Edited on 05/03/2021. Add the one liner solution.

Edited on 11/07/2021. Add the second one liner solution base on bit manipulation.

[LeetCode] 230. Kth Smallest Element in a BST

Problem: https://leetcode.com/problems/kth-smallest-element-in-a-bst/

In-order traverse the BST until collected K elements.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        
        gen = inorder(root)
        return [next(gen) for _ in range(k)][-1]

Edited on 06/06/2021. Update the inorder traversal approach.

[LeetCode] 229. Majority Element II

Problem : https://leetcode.com/problems/majority-element-ii/

The total number of majority elements should less than 3.

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        a = b = 0
        cnt1 = cnt2 = 0
        N = len(nums)
        
        for n in nums:
            if n == a:
                cnt1 += 1
            elif n == b:
                cnt2 += 1
            elif cnt1 == 0:
                a = n
                cnt1 += 1
            elif cnt2 == 0:
                b = n
                cnt2 += 1
            else:
                cnt1 -= 1
                cnt2 -= 1
        
        cnt1 = cnt2 = 0
        
        for n in nums:
            if n == a:
                cnt1 += 1
            if n == b:
                cnt2 += 1
        
        # verify the majority elements
        result = []
        if cnt1 > N // 3:
            result.append(a)
        if cnt2 > N // 3 and a != b:
            result.append(b)
        
        return result

[LeetCode] 228. Summary Ranges

Problem : https://leetcode.com/problems/summary-ranges/

For number A,  create the initial range [A, A].  If the next number B = A + 1, then extends the range as [A, B]. Otherwise create new initial range [B, B] and append to the result list.

Time Complexity = O ( N )

Space Complexity = O ( N )

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        result = []
        
        for n in nums:
            if result and n == result[-1][1] + 1:
                result[-1][1] = n
            else:
                result.append([n, n])
        
        return ["{}->{}".format(a, b) if a != b else "{}".format(a) for a, b in result]

[LeetCode] 227. Basic Calculator II

Problem : https://leetcode.com/problems/basic-calculator-ii/

Use stack to postpone the operator evaluation.

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack();
        
        int num = 0;
        Character opt = '+'; 
            
        for (int i = 0; i <= s.length(); i++) {
            if (i == s.length() || s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '*' || s.charAt(i) == '/') {
                if (opt == '+') {
                    stack.push(num);
                } else if (opt == '-') {
                    stack.push(-1 * num);
                } else if (opt == '*') {
                    stack.push(stack.pop() * num);
                } else if (opt == '/') {
                    stack.push(stack.pop() / num);
                }
                
                opt = i < s.length() ? s.charAt(i) : '+';
                num = 0;
                
            } else if (Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
            }
        }
        
        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        
        return result;
    }
}

Edited on 12/24/2021. Updated for a simpler stack based solution.

[LeetCode] 226. Invert Binary Tree

Problem : https://leetcode.com/problems/invert-binary-tree/

Invert the tree recursively.

/**
 * 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 invertTree(TreeNode root) {
        return root != null ? 
                new TreeNode(root.val, invertTree(root.right), invertTree(root.left))
                : null;
    }
}

Updated on 02/17/2023. Replaced with a Java solution.

[LeetCode] 225. Implement Stack using Queues

Problem : https://leetcode.com/problems/implement-stack-using-queues/

Use 2 queues in turn to save items.

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.q1 = deque()
        self.q2 = deque()
        

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        
        # use empty queue to save item
        if self.q1:
            self.q1.append(x)
        else:
            self.q2.append(x)
        

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        
        # push items to the empty queue, then pop the last item
        if self.q1:
            while len(self.q1) != 1:
                self.q2.append(self.q1.popleft())
            return self.q1.popleft()
        else:
            while len(self.q2) != 1:
                self.q1.append(self.q2.popleft())
            return self.q2.popleft()

    def top(self) -> int:
        """
        Get the top element.
        """
        # return the last item of the non-empty queue
        if self.q1:
            return self.q1[-1]
        else:
            return self.q2[-1]
        

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        
        # stack is empty if both queue is empty
        return len(self.q1) == 0 and len(self.q2) == 0
        


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()