LeetCode 20. Valid Parentheses

Problem:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Solution:

public class Solution {
    public boolean isValid(String s) {        
        
        Stack<Character> stack = new Stack<>();
        
        for (int i =0; i<s.length(); i++){
            if (s.charAt(i) == ')' && (stack.isEmpty() || stack.pop() != '(')) return false;
            if (s.charAt(i) == '}' && (stack.isEmpty() || stack.pop() != '{')) return false;
            if (s.charAt(i) == ']' && (stack.isEmpty() || stack.pop() != '[')) return false;
            if (s.charAt(i) == '{' || s.charAt(i) == '(' || s.charAt(i) == '[') stack.push(s.charAt(i));
        }
        return stack.isEmpty();
    }
}

LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

Problem:

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int[] preorder, inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        int n = preorder.length;
        return buildTree(0, n - 1, 0, n - 1);
    }
    
    private TreeNode buildTree(int pre1, int pre2, int in1, int in2) {
        if (pre2 < pre1) return null;
        if (pre2 == pre1) return new TreeNode(preorder[pre1]);
        TreeNode root = new TreeNode(preorder[pre1]);
        int pos = 0;
        for (int i = in1; i <= in2; i++) {
            if (inorder[i] == root.val) {
                pos = i;
                break;
            }
        }
        root.left = buildTree(pre1 + 1, pre1 + pos - in1, in1, pos - 1);
        root.right = buildTree(pre1 + pos - in1 + 1, pre2, pos + 1, in2);
        return root;
    }
}

LeetCode 150. Evaluate Reverse Polish Notation

Problem:

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution:

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<String> nums = new Stack<>();
        Stack<String> ops = new Stack<>();
        for (String token: tokens) {
            if (isOp(token)) {
                if (nums.isEmpty()) {
                    ops.push(token);
                }
                else {
                    String num1 = nums.pop();
                    String num2 = nums.pop();
                    int a = Integer.parseInt(num1);
                    int b = Integer.parseInt(num2);
                    if (token.equals("+")) {
                        nums.push(a + b + "");
                    }
                    else if (token.equals("-")) {
                        nums.push(b - a + "");
                    }
                    else if (token.equals("*")) {
                        nums.push(b * a + "");
                    }
                    else {
                        nums.push(b / a + "");
                    }
                }
            }
            else {
                nums.push(token);
            }
        }
        String last = nums.pop();
        return Integer.parseInt(last);
    }
    
    private boolean isOp(String s) {
        String ops = "+-*/";
        return ops.indexOf(s) > -1;
    }
}

LeetCode 127. Word Ladder

Problem:

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWordto endWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution:

Today I knew that building an adjacency map is a stupid, stupid solution when you have way more elements than path.

public class Solution {
    
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        wordList.add(endWord);
        Queue<String> current = new LinkedList<String>();
        int step = 1;
        current.offer(beginWord);
        while (!current.isEmpty()) {
            int size = current.size();
            while (size > 0) {
                String word = current.poll();
                if (word.equals(endWord))
                    return step;
                for (int i = 0; i < word.length(); i++) {
                    char[] arr = word.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        arr[i] = c;
                        String check = new String(arr);
                        if (!check.equals(word) && wordList.contains(check)) {
                            current.offer(check);
                            wordList.remove(check);
                        }
                    }
                }
                size--;
            }
            step++;
        }
        return 0;
    }
}

LeetCode 25. Reverse Nodes in k-Group

Problem:

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int count = countNodes(head);
        int num = count - count % k;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        int done = 0;
        while(done < num) {
            ListNode run = current;
            for (int i = 0; i <= k; i++)
                run = run.next;
            current.next = reverseK(current.next, k);
            for (int i = 0; i < k; i++)
                current = current.next;
            current.next = run;
            done += k;
        }
        return dummy.next;
    }
    
    private int countNodes(ListNode head) {
        int count = 0;
        ListNode current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }
    
    private ListNode reverseK(ListNode current, int k) {
        if (k == 1) {
            return current;
        }
        ListNode tail = current.next;
        ListNode head = reverseK(current.next, k - 1);
        tail.next = current;
        return head;
    }
}

LeetCode 77. Combinations

Problem:

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution:

Backtracking

public class Solution {
    List<List<Integer>> all;
    public List<List<Integer>> combine(int n, int k) {
        all = new ArrayList<List<Integer>>();
        List<Integer> option = new ArrayList<Integer>();
        choose(1, n, k, option);
        return all;
    }
    
    private void choose(int start, int n, int k, List<Integer> option) {
        if (k == 0) {
            List<Integer> copy = new ArrayList<Integer>(option);
            all.add(copy);
            return;
        }
        for (int i = start; i <= n - k + 1; i++) {
            option.add(i);
            choose(i+1, n, k-1, option);
            option.remove(option.size() - 1);
        }
    }
}

LeetCode 31. Next Permutation

Problem:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,31,3,2
3,2,11,2,3
1,1,51,5,1

Solution:

public class Solution {
    public void nextPermutation(int[] nums) {
        int i = 0;
        for (; i < nums.length - 1; i++) {
            if (nums[i] < nums[i+1]) break;
        }
        if (i == nums.length - 1) {
            Arrays.sort(nums);
            return;
        }
        for (i = nums.length - 1; i > 0; i--) {
            if (nums[i-1] < nums[i]) break;
        }
        int pivot = i - 1;
        for (i = nums.length - 1; i > 0; i--)
            if (nums[i] > nums[pivot]) break;
        swap(nums, pivot, i);
        reverse(nums, pivot + 1, nums.length - 1);
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    private void reverse(int[] nums, int i, int j) {
        for (int k = i; k <= (i + j)/2; k++) {
            swap(nums, k, j + i - k);
        }
    }
}

LeetCode 148. Sort List

Problem:

Sort a linked list in O(n log n) time using constant space complexity.

Solution:

Three way quick sort

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        head = quicksort(head);
        return head;
    }
    
    private ListNode quicksort(ListNode pivot) {
        if (pivot == null || pivot.next == null)
            return pivot;
        ListNode prev1 = new ListNode(0), prev2 = new ListNode(0), prev = new ListNode(0);
        ListNode dummy1 = prev1, dummy2 = prev2, dummy = prev;
        ListNode current = pivot;
        while (current != null) {
            if (current.val < pivot.val) {
                prev1.next = current;
                prev1 = prev1.next;
            }
            else if (current.val > pivot.val) {
                prev2.next = current;
                prev2 = prev2.next;
            }
            else {
                prev.next = current;
                prev = prev.next;
            }
            current = current.next;
        }
        prev1.next = prev2.next = prev.next = null;
        dummy1.next = quicksort(dummy1.next);
        dummy2.next = quicksort(dummy2.next);
        current = dummy1;
        while (current.next != null) current = current.next;
        current.next = dummy.next;
        prev.next = dummy2.next;
        return dummy1.next;
    }
}

LeetCode 5. Longest Palindromic Substring

Problem:

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Solution:

public class Solution {
    int pos, max;
    
    public String longestPalindrome(String s) {
        if (s.length() < 2) return s;
        for (int i = 0; i < s.length() - 1; i++) {
            extend(s, i, i);
            extend(s, i, i + 1);
        }
        return s.substring(pos, pos + max);
    }
    
    private void extend(String s, int low, int high) {
        while (low >= 0 && high < s.length() && s.charAt(low) == s.charAt(high)) {
            low--;
            high++;
        }
        if (high - low - 1 > max) {
            max = high - low - 1;
            pos = low + 1;
        }
    }
}

LeetCode 202. Happy Number

Problem:

Write an algorithm to determine if a number 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, and 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 numbers.

Example: 19 is a happy number

  • 12 + 92 = 82
  • 82 + 22 = 68
  • 62 + 82 = 100
  • 12 + 02 + 02 = 1

Credits:
Special thanks to @mithmatt and @ts for adding this problem and creating all test cases.

Solution:

public class Solution {
    Set<Integer> all = new HashSet<>();
    public boolean isHappy(int n) {
        if (n == 1) return true;
        if (all.contains(n)) return false;
        all.add(n);
        int trans = 0;
        while (n > 0) {
            trans += (n % 10) * (n % 10);
            n /= 10;
        }
        return isHappy(trans);
    }
}