LeetCode

1. Two Sum   easy

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        for (int i = 0; i < (int) nums.size(); i++) {
            if (m.count(target - nums[i])) return {m[target - nums[i]], i};
            else m[nums[i]] = i;
        }
    }
};

2. Add Two Numbers   medium

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        return addHelper(l1, l2, 0);
    }
private:
    ListNode* addHelper(ListNode* l1, ListNode* l2, int carry) {
        if (!l1 && !l2) {
            if (carry) return new ListNode(carry);
            else return NULL;
        } else {
            int l1v = l1 ? l1->val : 0;
            int l2v = l2 ? l2->val : 0;
            ListNode* node = new ListNode((l1v + l2v + carry) % 10);
            carry = (l1v + l2v + carry) / 10;
            l1 = l1 ? l1->next : NULL;
            l2 = l2 ? l2->next : NULL;
            node->next = addHelper(l1, l2, carry);
            return node;
        }
    }
};

3. Longest Substring Without Repeating Characters   medium

Given a string, find the length of the longest substring without repeating characters.

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        d = []
        ntmp = 0
        nmax = 0
        for c in s:
            if not c in d:
                d.append(c)
                ntmp += 1
            else:
                loc = len(d) - d[::-1].index(c)
                d = d[loc:]
                d.append(c)
                ntmp = len(d)
            if ntmp > nmax:
                nmax = ntmp
        return nmax

4. Median of Two Sorted Arrays   hard

There are two sorted arrays nums1 and nums2 of size m and n respectively.

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        i = 0
        j = 0
        s = []
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                s.append(nums1[i])
                i += 1
            else:
                s.append(nums2[j])
                j += 1
        if i == len(nums1):
            s = s + nums2[j:]
        else:
            s = s + nums1[i:]
        if len(s) % 2 != 0:
            ind = int((len(s) + 1) / 2)
            return float(s[ind-1])
        else:
            ind = int(len(s) / 2)
            return float((s[ind-1] + s[ind]) / 2)

5. Longest Palindromic Substring   medium

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        s = list(s)
        ret = []
        maxl = 0
        for i in range(len(s)):
            # as a middle element
            for hf in range(len(s)):
                if i - hf < 0 or i + hf >= len(s):
                    break
                if s[i-hf] == s[i+hf]:
                    l = 2 * hf + 1
                    if l > maxl:
                        maxl = l
                        ret = s[i-hf:i+hf+1]
                else:
                    break
            # as a left element
            for hf in range(len(s)):
                if i - hf < 0 or i + hf + 1 >= len(s):
                    break
                if s[i-hf] == s[i+hf+1]:
                    l = 2 * (hf + 1)
                    if l > maxl:
                        maxl = l
                        ret = s[i-hf:i+hf+2]
                else:
                    break
        return "".join(ret)

6. ZigZag Conversion   medium

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

class Solution:
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        n = len(s)
        rn = []
        if numRows == 1:
            return s
        for i in range(numRows):
            pd = 2 * (numRows - 1 - i)
            qd = 2 * i
            if pd == 0 or qd == 0:
                d = [max(pd, qd), max(pd, qd)]
            else:
                d = [pd, qd]
            ii = i
            flag = True
            while ii < len(s):
                rn.append(s[ii])
                ii += d[0] if flag == True else d[1]
                flag = not flag
        return "".join(rn)

7. Reverse Integer   easy

Given a 32-bit signed integer, reverse digits of an integer.

class Solution:
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        x_abs = abs(x)
        y_abs = 0
        n = 1
        while int(x_abs / (10**n)) > 0:
            n += 1
        while x_abs / 10 > 0:
            n -= 1
            y_abs += int(x_abs % 10) * (10 ** n)
            x_abs  = int(x_abs / 10)
        y = y_abs if x > 0 else 0 - y_abs
        if y >= -2**31 and y <= 2**31-1:
            return y
        else:
            return 0

8. String to Integer (atoi)   medium

Implement atoi which converts a string to an integer.

class Solution:
    digits = [str(x) for x in range(10)]
    def initFilter(self, str):
        istr = ''
        for s in str:
            if s in self.digits:
                istr += s
            else:
                break
        return istr
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        str = str.lstrip(' ')
        if len(str) == 0 or str == '+' or str == '-':
            return 0
        if str[0] not in self.digits + ['+', '-']:
            return 0
        if str[0] in self.digits:
            d = int(self.initFilter(str))
            if d > (2 ** 31 - 1):
                return 2**31 - 1
            else:
                return d
        if str[0] in ['+', '-']:
            if str[1] in self.digits:
                if str[0] == '+':
                    d = int(self.initFilter(str[1:]))
                else:
                    d = -int(self.initFilter(str[1:]))
            else:
                d = 0
            if d < -2**31:
                return -2**31
            elif d > 2**31 - 1:
                return 2**31 - 1
            else:
                return d

9. Palindrome Number   easy

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

class Solution:
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        s = str(x)
        return True if s == s[::-1] else False

10. Regular Expression Matching   hard

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if len(p) == 0:
            return True if len(s) == 0 else False
        if len(p) == 1:
            if len(s) == 0:
                return False
            elif len(s) == 1 and p == '.':
                return True
            elif p == s:
                return True
            else:
                return False
        if p[1] != '*':
            if len(s) == 0:
                return False
            if p[0] == s[0] or p[0] == '.':
                return self.isMatch(s[1:], p[1:])
            else:
                return False
        else:
            if len(s) == 0:
                return self.isMatch(s, p[2:])
            if p[0] == s[0] or p[0] == '.':
                return self.isMatch(s[1:], p) or self.isMatch(s, p[2:])
            else:
                return self.isMatch(s, p[2:])

11. Container With Most Water   medium

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

class Solution:
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        cap = 0
        i = 0
        j = len(height) - 1
        while i < j:
            cap_tmp = (j - i) * min(height[i], height[j])
            if cap_tmp > cap:
                cap = cap_tmp
            if height[i] > height[j]:
                j -= 1
            else:
                i += 1
        return cap

12. Integer to Roman   medium

class Solution:
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        roman_tbl = {1: 'I', 4: 'IV', 5: 'V', 9: 'IX', 10: 'X',
                     40: 'XL', 50: 'L', 90: 'XC', 100: 'C',
                     400: 'CD', 500: 'D', 900: 'CM', 1000: 'M'}
        max_sort_keys = list(roman_tbl.keys())
        max_sort_keys.sort(reverse=True)
        num_roman = ""
        for i in max_sort_keys:
            while num / i >= 1:
                num -= i
                num_roman += roman_tbl.get(i)
        return num_roman

13. Roman to Integer   easy

class Solution:
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman_tbl = {'I': 1, 'IV': 4, 'V': 5, 'IX': 9, 'X': 10,
                     'XL': 40, 'L': 50, 'XC': 90, 'C': 100,
                     'CD': 400, 'D': 500, 'CM': 900, 'M': 1000}
        num = 0
        while len(s) > 0:
            if len(s) >= 2 and s[:2] in roman_tbl.keys():
                num += roman_tbl.get(s[:2])
                s = s[2:]
            else:
                if s[:1] in roman_tbl.keys():
                    num += roman_tbl.get(s[:1])
                    s = s[1:]
        return num

14. Longest Common Prefix   easy

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ""
        min_str = min(strs, key=len)
        out_str = ""
        for i in range(len(min_str)):
            test_str = min_str[:i+1]
            test_results = [s.startswith(test_str) for s in strs]
            if all(test_results):
                out_str = test_str
            else:
                break
        return out_str

15. 3Sum   medium

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        for t in range(0, len(nums) - 2):
            if t > 0 and nums[t] == nums[t-1]: continue
            l = t + 1; r = len(nums) - 1
            while l < r:
                three_sum = nums[t] + nums[l] + nums[r]
                if three_sum == 0:
                    res.append([nums[t], nums[l], nums[r]])
                    l += 1; r -= 1
                    while l < r and nums[l] == nums[l-1]: l += 1
                    while l < r and nums[r] == nums[r+1]: r -= 1
                elif three_sum < 0:
                    l += 1
                else:
                    r -= 1
        return res

16. 3Sum Closest   medium

class Solution:
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        d = float('inf')
        result = target
        for t in range(len(nums) - 2):
            if t != 0 and nums[t] == nums[t-1]:
                continue
            l = t + 1; r = len(nums) - 1
            while l < r:
                sum_tri = nums[t] + nums[l] + nums[r]
                if sum_tri - target == 0:
                    return sum_tri
                elif sum_tri > target:
                    if sum_tri - target < d:
                        d = sum_tri - target
                        result = sum_tri
                    r -= 1
                else: # sum_tri < target
                    if target - sum_tri < d:
                        d = target - sum_tri
                        result = sum_tri
                    l += 1
        return result

17. Letter Combinations of a Phone Number   medium

import itertools

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if len(digits) == 0:
            return []
        calc_tbl = {'1': [], '2': ['a', 'b', 'c'], '3': ['d', 'e', 'f'],
                    '4': ['g', 'h', 'i'], '5': ['j', 'k', 'l'], '6': ['m', 'n', 'o'],
                    '7': ['p', 'q', 'r', 's'], '8': ['t', 'u', 'v'], '9': ['w', 'x', 'y', 'z']}
        alt_btn = []
        for d in digits:
            alt_btn.append(calc_tbl.get(d))
        print(alt_btn)
        res = list(itertools.product(*alt_btn))
        return ["".join(x) for x in res]

18. 4Sum   medium

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        results = []
        for i1 in range(len(nums) - 3):
            if i1 != 0 and nums[i1] == nums[i1-1]:
                continue
            for i2 in range(i1+1, len(nums) - 2):
                if i2 != i1+1 and nums[i2] == nums[i2-1]:
                    continue
                target_p = target - nums[i1] - nums[i2]
                i3 = i2 + 1; i4 = len(nums) - 1
                while i3 < i4:
                    duo_sum = nums[i3] + nums[i4]
                    if duo_sum == target_p:
                        results.append([nums[x] for x in [i1, i2, i3, i4]])
                        i3 += 1; i4 -= 1
                        while i3 < i4 and nums[i3] == nums[i3-1]: i3 += 1
                        while i3 < i4 and nums[i4] == nums[i4+1]: i4 -= 1
                    elif duo_sum > target_p:
                        i4 -= 1
                    else:
                        i3 += 1
        return results

19. Remove Nth Node From End of List   medium

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        slider = head
        cache = []
        i = 0
        while slider != None:
            cache.append(slider)
            slider = slider.next
            i += 1
        if i == n:
            head = head.next
        else:
            target = cache[i - n - 1]
            target.next = target.next.next
        return head

20. Valid Parentheses   easy

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        par_pairs = [('{', '}'), ('[', ']'), ('(', ')')]
        par_stack = []
        for c in s:
            if c in [p[0] for p in par_pairs]:
                par_stack.append(c)
            else:
                if par_stack == []:
                    return False
                ppair = (par_stack[-1], c)
                if ppair in par_pairs:
                    par_stack = par_stack[:-1]
                else:
                    return False
        return False if par_stack else True

21. Merge Two Sorted Lists   easy

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 and not l2:
            return None
        x = ListNode(0)
        head = x
        while l1 and l2:
            if l1.val < l2.val:
                tmp = l1
                l1 = l1.next
            else:
                tmp = l2
                l2 = l2.next
            x.val = tmp.val
            x.next = tmp
            x = x.next
        if l1 != None:
            x.val = l1.val
            x.next = l1.next
        if l2 != None:
            x.val = l2.val
            x.next = l2.next
        return head

22. Generate Parentheses   medium

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        def genP(pstr, l, r):
            if r >= l >= 0:
                if not r:
                    yield pstr
                for i in genP(pstr + "(", l - 1, r): yield i
                for i in genP(pstr + ")", l, r - 1): yield i
        return list(genP("", n, n))

23. Merge k Sorted Lists   hard

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        def mergeSort(x, y):
            header = ListNode(0)
            live_header = header
            while x and y:
                if x.val < y.val:
                    live_header.next = x
                    x = x.next
                else:
                    live_header.next = y
                    y = y.next
                live_header = live_header.next
            live_header.next = x if x else y
            return header.next

        k = len(lists)
        if k == 0:
            return []
        if k == 1:
            return lists[0]
        if k == 2:
            return mergeSort(lists[0], lists[1])
        if k > 2:
            return mergeSort(self.mergeKLists(lists[0:int(k/2)]), self.mergeKLists(lists[int(k/2):]))

24. Swap Nodes in Pairs   medium

class Solution:
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        if not head.next:
            return head
        remaining = head.next.next
        header = head.next
        head.next.next = head
        head.next = self.swapPairs(remaining)
        return header

25. Reverse Nodes in k-Group   hard

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head: return None
        s = []
        raw_k = k
        while head and k > 0:
            s.append(head)
            head = head.next
            k -= 1
        rheader = ListNode(0)
        header = rheader
        if k > 0: s.reverse()
        while s:
            header.next = s.pop()
            header = header.next
        header.next = self.reverseKGroup(head, raw_k)
        return rheader.next

26. Remove Duplicates from Sorted Array   easy

class Solution:
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        j = 0
        for i in range(1, len(nums)):
            if not nums[i] == nums[j]:
                nums[j+1] = nums[i]
                j += 1
        return len(nums[:j+1])

27. Remove Element   easy

class Solution:
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        j = 0
        for i in range(len(nums)):
            if not nums[i] == val:
                nums[j] = nums[i]
                j += 1
        return len(nums[:j])

28. Implement strStr()   easy

class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        return haystack.find(needle)

29. Divide Two Integers   medium

class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        r = int(dividend / divisor)
        if r < -2**31:
            return -2**31
        elif r > 2**31 - 1:
            return 2**31 - 1
        else:
            return r

30. Substring with Concatenation of All Words   hard

class Solution:
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        res = []
        if not words: return res
        w = words.copy()
        wl = len(w[0])
        anchor = 0
        i = anchor
        while anchor + wl * len(words) <= len(s):
            win = s[i:i+wl]
            if win in w:
                w.remove(win)
                i += wl
            else:
                w = words.copy()
                anchor += 1
                i = anchor
            if not w:
                res.append(anchor)
                w = words.copy()
                anchor += 1
                i = anchor
        return res

31. Next Permutation   medium

class Solution:
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        a = len(nums)
        for i in range(len(nums) - 1):
            if nums[i] < nums[i+1]:
                a = i
        if not a < len(nums):
            for i in range(int(len(nums)/2)):
                tmp = nums[i]
                nums[i] = nums[len(nums) - 1 - i]
                nums[len(nums) - 1 - i] = tmp
        else:
            b = len(nums)
            for i in range(a, len(nums)):
                if nums[i] > nums[a]:
                    b = i
            tmp = nums[a]
            nums[a] = nums[b]
            nums[b] = tmp
            for i in range(int((len(nums) - a) / 2)):
                tmp = nums[a + i + 1]
                nums[a + i + 1] = nums[len(nums) - i - 1]
                nums[len(nums) - i - 1] = tmp

32. Longest Valid Parentheses   hard

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> dp(s.size(), 0);
        int maxLen = 0;
        for (int i = 0; i < dp.size(); i++) {
            if (s[i] == '(') dp[i] = 0;
            else {
                // assert(s[i] == ')');
                if (s[i-1] == '(') dp[i] = i >= 2 ? dp[i-2] + 2 : 2;
                else {
                    // assert(s[i-1] == ')');
                    if (i - dp[i-1] - 1 >= 0 && s[i - dp[i-1] - 1] == '(') 
                        dp[i] = dp[i-1] + 2 + (i - dp[i-1] - 2 >= 0 ? dp[i - dp[i-1] - 2] : 0);
                }
            }
            maxLen = dp[i] > maxLen ? dp[i] : maxLen;
        }
        return maxLen;
    }
};

33. Search in Rotated Sorted Array   medium

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return searchHelper(nums, target, 0, (int)nums.size()-1);
    }
private:
    int searchHelper(vector<int>& nums, int target, int l, int r) {
        if (l > r) return -1;
        int mid = (l + r) / 2;
        if (target < nums[mid]) {
            if (nums[mid] < nums[r]) return searchHelper(nums, target, l, mid-1);
            else {
                if (nums[l] > target) return searchHelper(nums, target, mid+1, r);
                else return searchHelper(nums, target, l, mid);
            }
        } else if (target > nums[mid]) {
            if (nums[mid] > nums[l]) return searchHelper(nums, target, mid+1, r);
            else {
                if (target > nums[r]) return searchHelper(nums, target, l, mid-1);
                else return searchHelper(nums, target, mid+1, r);
            }
        } else return mid;
    }
};
int main() {
    Solution *s = new Solution();
    vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    int target = 0;
    cout << s->search(nums, target) << endl;
}

34. Find First and Last Position of Element in Sorted Array   medium

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int t = bsearch(nums, target, 0, (int)nums.size()-1);
        int x = t, y = t;
        while (x-1 >= 0 && nums[x-1] == target) x--;
        while (y+1 < (int)nums.size() && nums[y+1] == target) y++;
        return {x, y};
    }
private:
    int bsearch(vector<int>& nums, int target, int l, int r) {
        if (l > r) return -1;
        int mid = (l + r) / 2;
        if (nums[mid] < target) return bsearch(nums, target, mid+1, r);
        else if (nums[mid] > target) return bsearch(nums, target, l, mid-1);
        else return mid;
    }
};

39. Combination Sum   medium

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> alt;
        sort(candidates.begin(), candidates.end());
        dfs(candidates, alt, target, ans, 0);
        return ans;
    }
private:
    void dfs(vector<int>& candidates, vector<int>& alt, int rest, vector<vector<int>>& ans, int s) {
        for (int i = s; i < (int) candidates.size(); i++) {
            if (candidates[i] > rest) break;
            else if (candidates[i] == rest) {
                alt.push_back(candidates[i]);
                ans.push_back(alt);
                alt.pop_back();
                break;
            }
            else {
                alt.push_back(candidates[i]);
                dfs(candidates, alt, rest - candidates[i], ans, i);
                alt.pop_back();
            }
        }
    }
};

46. Permutations   medium

Given a collection of distinct integers, return all possible permutations.

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        do {
            ans.push_back(nums);
        } while (next_permutation(nums.begin(), nums.end()));
        return ans;
    }
};

48. Rotate Image   medium

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = (int) matrix.size();
        for (int i = 0; i < n/2; i++) {
            for (int j = i; j < n-1-i; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][i];
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                matrix[j][n-1-i] = tmp;
            }
        }
    }
};

49. Group Anagrams   medium

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> um;
        for (auto& x : strs) {
            string tmp = x;
            sort(tmp.begin(), tmp.end());
            if (um.count(tmp) > 0) um[tmp].push_back(x);
            else um[tmp] = {x};
        }
        vector<vector<string>> ans;
        for (auto& x : um) {
            ans.push_back(x.second);
        }
        return ans;
    }
};

55. Jump Game   medium

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.
class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i-1], nums[i-1]) - 1;
            if (dp[i] < 0) return false;
        }
        return dp.back() >= 0;
    }
};

56. Merge Intervals   medium

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(),
             [](auto& x, auto& y) {return x.start < y.start;});
        vector<Interval> ans;
        for (int i = 0; i < intervals.size(); i++) {
            if (i == 0) ans.push_back(intervals[i]);
            else {
                Interval& tmp = ans.back();
                if (intervals[i].start > tmp.end) ans.push_back(intervals[i]);
                else tmp.end = intervals[i].end > tmp.end ? intervals[i].end : tmp.end;
            }
        }
        return ans;
    }
};

67. Add Binary   easy

class Solution {
public:
    string addBinary(string a, string b) {
        int alen = (int) a.size();
        int blen = (int) b.size();
        int carry = 0;
        string res;
        while (alen > 0 || blen > 0) {
            int abit = alen <= 0 ? 0 : a.at(alen - 1) - '0';
            int bbit = blen <= 0 ? 0 : b.at(blen - 1) - '0';
            int cbit = carry;
            int bits = abit + bbit + cbit;
            res.insert(res.begin(), '0' + bits % 2);
            carry = bits / 2;
            alen--;
            blen--;
        }
        if (carry) res.insert(res.begin(), '1');
        return res;
    }
};

75. Sort Colors   medium

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int i = 0;
        int l = 0, r = (int)nums.size() - 1;
        while (i <= r) {
            if (nums[i] == 0) swap(nums[l++], nums[i]);
            if (nums[i] == 2) swap(nums[r--], nums[i]);
            else i++;
        }
    }
};

78. Subsets   medium

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans = {{}};
        for (int i = 0; i < (int)nums.size(); i++) {
            int n = (int) ans.size();
            for (int j = 0; j < n; j++) {
                vector<int> tmp = ans[j];
                tmp.push_back(nums[i]);
                ans.push_back(tmp);
            }
        }
        return ans;
    }
};

79. Word Search   medium

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board.at(0).size(); j++) {
                if (this->search(board, word, i, j)) return true;
            }
        }
        return false;
    }
private:
    bool search(vector<vector<char>> board, string word, int i, int j) {
        int row = (int) board.size();
        int col = (int) board[0].size();
        if (word.empty()) return true;
        if (i < 0 || i >= row || j < 0 || j >= col) return false;
        if (board[i][j] == '*' || board[i][j] != word[0]) return false;
        word.erase(word.begin());
        board[i][j] = '*';
        bool res = search(board, word, i + 1, j) ||
                   search(board, word, i - 1, j) ||
                   search(board, word, i, j + 1) ||
                   search(board, word, i, j - 1);
        return res;
    }
};

81. Search in Rotated Sorted Array II   medium

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        return binary_search(nums.begin(), nums.end(), target);
    }
};

86. Partition List   medium

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *left = new ListNode(0);
        ListNode *right = new ListNode(0);
        ListNode *left_head = left;
        ListNode *right_head = right;
        while (head) {
            if (head->val < x) {
                left->next = head;
                left = left->next;
            } else {
                right->next = head;
                right = right->next;
            }
            head = head->next;
        }
        right->next = NULL;
        left->next = right_head->next;
        return left_head->next;
    }
};

90. Subsets II   medium

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans = {{}};
        for (auto num : nums) {
            int n = (int) ans.size();
            for (int i = 0; i < n; i++) {
                vector<int> tmp(ans[i].begin(), ans[i].end());
                tmp.push_back(num);
                if (!count(ans.begin(), ans.end(), tmp)) ans.push_back(tmp);
            }
        }
        return ans;
    }
};

100. Same Tree   easy

Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL) return true;
        else if (p == NULL || q == NULL) return false;
        else if (p->val != q->val) return false;
        else {
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
    }
};

101. Symmetric Tree   easy

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return helper(root->left, root->right);
    }
private:
    bool helper(TreeNode* l, TreeNode* r) {
        if (!l && !r) return true;
        else if (!l || !r) return false;
        else if (l->val != r->val) return false;
        else {
            return helper(l->left, r->right) && helper(l->right, r->left);
        }
    }
};

104. Maximum Depth of Binary Tree   easy

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        vector<TreeNode*> vec;
        TreeNode* node;
        int depth = 0;
        vec.push_back(root);
        while (!vec.empty()) {
            int n = (int)vec.size();
            for (int i = 0; i < n; i++) {
                if (vec[i]->left) vec.push_back(vec[i]->left);
                if (vec[i]->right) vec.push_back(vec[i]->right);
            }
            vec.erase(vec.begin(), vec.begin() + n);
            depth++;
        }
        return depth;
    }
};

105. Construct Binary Tree from Preorder and Inorder Traversal   medium

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return helper(preorder, inorder, 0, (int)preorder.size(), 0, (int)inorder.size());
    }
private:
    TreeNode* helper(vector<int>& preorder, vector<int>& inorder,
                     int pre1, int pre2, int in1, int in2) {
        if (pre1 >= pre2 || in1 >= in2) return NULL;
        int m = preorder[pre1];
        int insplit = distance(inorder.begin(), find(inorder.begin() + in1, inorder.begin() + in2, m));
        int presplit = pre1 + insplit - in1 + 1;
        TreeNode* root = new TreeNode(m);
        root->left = this->helper(preorder, inorder, pre1 + 1, presplit, in1, insplit);
        root->right = this->helper(preorder, inorder, presplit, pre2, insplit + 1, in2);
        return root;
    }
};

112. Path Sum   easy

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        if (!root->left && !root->right && root->val == sum) return true;
        sum -= root->val;
        return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
    }
};

113. Path Sum II   medium

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if (!root) return {};
        vector<vector<int>> res;
        stack<pair<TreeNode*, vector<int>>> stk;
        stk.push({root, {root->val}});
        while (!stk.empty()) {
            TreeNode *pNode = stk.top().first;
            vector<int> vVals = stk.top().second;
            stk.pop();
            if (pNode->left) {
                vector<int> vTmp = vVals;
                vTmp.push_back(pNode->left->val);
                stk.push({pNode->left, vTmp});
            }
            if (pNode->right) {
                vector<int> vTmp = vVals;
                vTmp.push_back(pNode->right->val);
                stk.push({pNode->right, vTmp});
            }
            if (!pNode->left && !pNode->right) {
                if (accumulate(vVals.begin(), vVals.end(), 0, plus<int>()) == sum)
                    res.push_back(vVals);
            }
        }
        return res;
    }
};

114. Flatten Binary Tree to Linked List   medium

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        if (root->left) flatten(root->left);
        if (root->right) flatten(root->right);
        TreeNode* tmp = root->right;
        root->right = root->left;
        root->left = NULL;
        while (root->right) root = root->right;
        root->right = tmp;
    }
};

119. Pascal's Triangle II   easy

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> up = {1};
        while (rowIndex--) {
            vector<int> down = {};
            up.insert(up.begin(), 0);
            up.push_back(0);
            for (int i = 0; i < (int)up.size() - 1; i++) {
                down.push_back(up[i] + up[i + 1]);
            }
            up = down;
        }
        return up;
    }
};

127. Word Ladder   medium

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

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        queue<string> words;
        set<string> dict(wordList.begin(), wordList.end());
        if (!dict.count(endWord)) return 0;
        words.push(beginWord);
        int steps = 0;
        while (!words.empty()) {
            size_t t = words.size();
            steps++;
            while (t--) {
                string word = words.front();
                words.pop();
                if (word == endWord) return steps;
                for (auto i = 0; i < (int)word.length(); i++) {
                    char ch = word[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        word[i] = c;
                        if (word == endWord) return steps + 1;
                        if (!dict.count(word)) continue;
                        dict.erase(word);
                        words.push(word);
                    }
                    word[i] = ch;
                }
            }
        }
        return 0;
    }
};

139. Word Break   medium

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && find(wordDict.begin(), wordDict.end(), s.substr(j, i-j)) != wordDict.end()) {
                    dp[i] = true; break;
                }
            }
        }
        return dp[s.size()];
    }
};

142. Linked List Cycle II   medium

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head) return NULL;
        ListNode *slow = head;
        ListNode *fast = head;
        while (slow->next && fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode *node = head;
                while (node != slow) {
                    slow = slow->next;
                    node = node->next;
                }
                return node;
            }
        }
        return NULL;
    }
};

147. Insertion Sort List   medium

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* newHead = new ListNode(-numeric_limits<int>::max());
        while (head) {
            ListNode* tmp = head->next;
            this->insertOne(newHead, head);
            head = tmp;
        }
        return newHead->next;
    }
private:
    ListNode* insertOne(ListNode* head, ListNode* node) {
        ListNode* cHead = head;
        while (head->next != NULL && head->next->val < node->val) {
            head = head->next;
        }
        node->next = head->next;
        head->next = node;
        return cHead;
    }
};

172. Factorial Trailing Zeroes   easy

class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        while (n) {
            ans += n / 5;
            n /= 5;
        }
        return ans;
    }
};

189. Rotate Array   easy

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = (int) nums.size();
        if (n > 1) {
            k %= n;
            reverse(nums.begin(), nums.begin() + n - k);
            reverse(nums.end() - k, nums.end());
            reverse(nums.begin(), nums.end());
        }
    }
};

191. Number of 1 Bits   easy

class Solution {
public:
    int hammingWeight(uint32_t n) {
        bitset<32> b(n);
        return b.count();
    }
};

198. House Robber   easy

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0: return 0
        s = [0 for _ in range(len(nums))]
        for i in range(len(nums)):
            if i == 0:
                s[0] = nums[0]
            elif i == 1:
                s[1] = max(s[0], nums[1])
            else:
                s[i] = max(s[i-1], s[i-2] + nums[i])
        return max(s)

201. Bitwise AND of Numbers Range   medium

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int i = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            i++;
        }
        return (m << i);
    }
};

202. Happy Number   easy

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> us = {n};
        vector<int> sn;
        while (true) {
            sn = splitNum(n);
            for_each(sn.begin(), sn.end(), [](int& x){x *= x;});
            n = accumulate(sn.begin(), sn.end(), 0, plus<int>());
            if (n == 1) return true;
            else if (us.count(n)) break;
            else us.insert(n);
        }
        return false;
    }
private:
    vector<int> splitNum(int n) {
        vector<int> ans;
        while (n) {
            ans.push_back(n % 10);
            n /= 10;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

219. Contains Duplicate II   easy

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int, vector<int>> dict;
        int key;
        for (int i = 0; i < (int)nums.size(); i++) {
            key = nums[i];
            if (dict.count(key) == 0) dict[key].push_back(i);
            else if (i - dict[key].back() <= k) return true;
            else dict[key].push_back(i);
        }
        return false;
    }
};

226. Invert Binary Tree   easy

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return root;
        if (!root->left && !root->right) return root;
        TreeNode *tmp;
        tmp = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(tmp);
        return root;
    }
};

231. Power of Two   easy

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n == 0) {
            return false;
        }
        while ((n & 1) != 1) {
            n = (n >> 1);
        }
        if (n == 1) {
            return true;
        } else {
            return false;
        }
    }
};

238. Product of Array Except Self   medium

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = (int)nums.size();
        vector<int> before(n, 1);
        vector<int> after(n, 1);
        int tmp = 1;
        for (int i = 1; i < n; i++) {
            before[i] = nums[i - 1] * tmp;
            tmp = before[i];
        }
        tmp = 1;
        for (int i = n - 2; i >= 0; i--) {
            after[i] = nums[i + 1] * tmp;
            tmp = after[i];
        }
        vector<int> res(n);
        for (int i = 0; i < n; i++) {
            res[i] = before[i] * after[i];
        }
        return res;
    }
};

274. H-Index   medium

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index. According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end(), greater<int>());
        for (int i = 0; i < (int)citations.size(); i++) {
            if (citations[i] >= i + 1) {
                if (i == citations.size() - 1) return i + 1;
                if (citations[i + 1] <= i + 1) return i + 1;
            }
        }
        return 0;
    }
};

319. Bulb Switcher   medium

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

328. Odd Even Linked List   medium

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head) return head;
        if (!head->next) return head;
        ListNode *odd = head;
        ListNode *even = head->next;
        ListNode *oddHead = odd;
        ListNode *evenHead = even;
        ListNode *node = head->next->next;
        bool isOdd = true;
        while (node) {
            if (isOdd) {
                odd->next = node;
                odd = odd->next;
            }
            else {
                even->next = node;
                even = even->next;
            }
            isOdd = !isOdd;
            node = node->next;
        }
        odd->next = evenHead;
        even->next = NULL;
        return oddHead;
    }
};

342. Power of Four   easy

class Solution {
public:
    bool isPowerOfFour(int num) {
        return (num > 0) && !(num & (num - 1)) && ((num - 1) % 3 == 0);
    }
};

395. Longest Substring with At Least K Repeating Characters   medium

class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = (int)s.size();
        if (n == 0 || n < k) return 0;
        map<char, int> dict;
        for (char c = 'a'; c <= 'z'; c++) {
            dict.insert({c, 0});
        }
        for (auto i : s) {
            dict.at(i)++;
        }
        for (int i = 0; i < n; i++) {
            if (dict[s[i]] < k) {
                int left = this->longestSubstring(s.substr(0, i), k);
                int right = this->longestSubstring(s.substr(i + 1), k);
                return max({left, right});
            }
        }
        return n;
    }
};

405. Convert a Number to Hexadecimal   easy

class Solution {
public:
    string toHex(int num) {
        string alpha[] = {"a", "b", "c", "d", "e", "f"};
        string ans;
        int rem;
        unsigned x = num;
        while (x) {
            rem = x % 16;
            if (rem < 10) ans = to_string(rem) + ans;
            else ans = alpha[rem - 10] + ans;
            x -= rem;
            x /= 16;
        }
        return ans.empty() ? "0" : ans;
    }
};

433. Minimum Genetic Mutation   medium

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2
class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        queue<string> q;
        set<string> visited;
        q.push(start);
        visited.insert(start);
        int mutations = 0;
        while (!q.empty()) {
            size_t t = q.size();
            while (t--) {
                string aq = q.front();
                q.pop();
                if (aq == end) return mutations;
                for (const string& gene : bank) {
                    if (visited.count(gene)) continue;
                    if (this->validMutation(aq, gene)) {
                        q.push(gene);
                        visited.insert(gene);
                    }
                }
            }
            mutations++;
        }
        return -1;
    }
private:
    bool validMutation(const string& x, const string& y) {
        int diff = 0;
        for (auto i = 0; i < (int)x.length(); i++) {
            if (x[i] != y[i]) diff++;
            if (diff > 1) break;
        }
        return diff > 1 ? false : true;
    }
};

462. Minimum Moves to Equal Array Elements II   medium

Input:
[1,2,3]

Output:
2

Explanation:
Only two moves are needed (remember each move increments or decrements one element):

[1,2,3]  =>  [2,2,3]  =>  [2,2,2]
class Solution {
public:
    int minMoves2(vector<int>& nums) {
        int n = (int) nums.size();
        sort(nums.begin(), nums.end());
        int target = nums[n / 2];
        int ans = 0;
        for (auto num : nums) {
            ans += abs(num - target);
        }
        return ans;
    }
};

477. Total Hamming Distance   medium

Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int res = 0;
        int n = (int)nums.size();
        vector<int> vb(32);
        for (auto num : nums) {
            bitset<32> v(num);
            for (int i = 0; i < 32; i++) {
                if (v[i] == 1) vb[i]++;
            }
        }
        for (auto k : vb) {
            res += k * (n - k);
        }
        return res;
    }
};

486. Predict the Winner   medium

Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return False.
class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int i = 0;
        int j = nums.size() - 1;
        int res = pickOne(nums, i, j);
        return res >= 0;
    }
private:
    int pickOne(vector<int>& nums, int i, int j) {
        if (i == j) return nums.at(i);
        int res1 = nums[i] - pickOne(nums, i + 1, j);
        int res2 = nums[j] - pickOne(nums, i, j - 1);
        return res1 > res2 ? res1 : res2;
    }
};

520. Detect Capital   easy

Input: "FlaG"
Output: False
class Solution {
public:
    bool detectCapitalUse(string word) {
        int n = (int)word.size();
        if (n == 0 || n == 1) return true;
        bool isCap = (word[0] >= 'a' && word[0] <= 'z') ? false : true;
        set<bool> res_set;
        for (auto c : word.substr(1)) {
            if (!isCap) {
                if (c < 'a' || c > 'z') return false;
            } else {
                if (c >= 'a' && c <= 'z') res_set.insert(true);
                else res_set.insert(false);
            }
        }
        return res_set.size() > 1 ? false : true;
    }
};

559. Maximum Depth of N-ary Tree   easy

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    int maxDepth(Node* root) {
        if (!root) return 0;
        if (root->children.empty()) return 1;
        int depth = 1;
        for (auto v : root->children) {
            depth = max(depth, this->maxDepth(v));
        }
        return depth + 1;
    }
};

576. Out of Boundary Paths   medium

There is an m by n grid with a ball. Given the start coordinate \((i, j)\) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod \(10^9 + 7\).

Input:m = 2, n = 2, N = 2, i = 0, j = 0
Output: 6
class Solution {
public:
    int findPaths(int m, int n, int N, int i, int j) {
        vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(m, vector<int>(n, 0)));
        for (int k = 1; k <= N; k++) {
            for (int x = 0; x < m; x++) {
                for (int y = 0; y < n; y++) {
                    long long v1 = (x == 0) ? 1 : dp[k - 1][x - 1][y];
                    long long v2 = (x == m - 1) ? 1 : dp[k - 1][x + 1][y];
                    long long v3 = (y == 0) ? 1 : dp[k - 1][x][y - 1];
                    long long v4 = (y == n - 1) ? 1 : dp[k - 1][x][y + 1];
                    dp[k][x][y] = (v1 + v2 + v3 + v4) % (int)(1e9 + 7);
                }
            }
        }
        return dp[N][i][j];
    }
};

589. N-ary Tree Preorder Traversal   easy

Given an n-ary tree, return the preorder traversal of its nodes' values.

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> preorder(Node* root) {
        if (!root) return {};
        stack<Node*> st;
        vector<int> result;
        Node* tmp;
        st.emplace(root);
        while (!st.empty()) {
            tmp = st.top(); st.pop();
            result.emplace_back(tmp->val);
            for (auto it = tmp->children.rbegin(); it < tmp->children.rend(); it++)
                st.emplace(*it);
        }
        return result;
    }
};

605. Can Place Flowers   easy

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Input: flowerbed = [1,0,0,0,1], n = 2
Output: False
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        bool prev = true;
        if (flowerbed.size() == 0) {
            return n == 0 ? true : false;
        }
        for (int i = 0; i < flowerbed.size(); i++) {
            if (flowerbed[i] == 1) prev = false;
            else if (!prev) prev = true;
            else if ((i == flowerbed.size() - 1) ||
                     (flowerbed[i+1] == 0)) {
                n--;
                prev = false;
            }
            if (n <= 0) return true;
        }
        return n > 0 ? false : true;
    }
};

645. Set Mismatch   easy

Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Input: nums = [1,2,2,4]
Output: [2,3]
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int x, y;
        unordered_set<int> us(nums.begin(), nums.end());
        int sum_nums = accumulate(nums.begin(), nums.end(), 0, plus<int>());
        int sum_us   = accumulate(us.begin(), us.end(), 0, plus<int>());
        x = sum_nums - sum_us;   
        y = (1 + (int)nums.size()) * (int)nums.size() / 2 - sum_us;
        return {x, y};
    }
};

654. Maximum Binary Tree   medium

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

  1. The root is the maximum number in the array.
  2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
  3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.empty()) return NULL;
        vector<int>::iterator target = max_element(nums.begin(), nums.end());
        vector<int> left(nums.begin(), target);
        vector<int> right(target + 1, nums.end());
        TreeNode *root = new TreeNode(*target);
        root->left = constructMaximumBinaryTree(left);
        root->right = constructMaximumBinaryTree(right);
        return root;
    }
};

697. Degree of an Array   easy

Input: [1, 2, 2, 3, 1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.
class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        map<int, int> m;
        for (auto i : nums) {
            if (m.count(i) == 0) m.insert(make_pair(i, 1));
            else m[i]++;
        }
        auto maxFreqIt = max_element(m.begin(), m.end(),
                                     [](const pair<int, int>& x, const pair<int, int>& y) {
                                         return x.second < y.second;});
        int maxFreq = (*maxFreqIt).second;
        vector<int> alts;
        for (auto i : m) {
            if (i.second == maxFreq) alts.push_back(i.first);
        }
        int ans = INT_MAX;
        int first, last;
        for (auto i : alts) {
            first = distance(nums.begin(), find(nums.begin(), nums.end(), i));
            last = distance(find(nums.rbegin(), nums.rend(), i), nums.rend() - 1);
            ans = min(ans, last - first + 1);
        }
        return ans;
    }
};

720. Longest Word in Dictionary   easy

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

Input: 
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation: 
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".
class Solution {
public:
    string longestWord(vector<string>& words) {
        string ans = "";
        set<string> s;
        sort(words.begin(), words.end());
        for (auto word : words) {
            if (word.size() == 1 || s.count(word.substr(0, word.size() - 1))) {
                ans = (word.size() > ans.size()) ? word : ans;
                s.insert(word);
            }
        }
        return ans;
    }
};

738. Monotone Increasing Digits   medium

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

Input: N = 332
Output: 299
class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string sn = to_string(N);
        int l = sn.size();
        if (l == 1) return N;
        int anchor = l;
        for (int i = l - 1; i > 0; i--) {
            if (sn[i - 1] > sn[i]) {
                sn[i - 1]--;
                anchor = i - 1;
            }
        }
        while(++anchor < l) {
            sn[anchor] = '9';
        }
        return stoi(sn);
    }
};

788. Rotated Digits   easy

Example:
Input: 10
Output: 4
Explanation: 
There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.
class Solution {
public:
    int rotatedDigits(int N) {
        int must_have[10] = {0};
        int cant_have[10] = {0};
        for (int i : {2, 5, 6, 9}) must_have[i] = 1;
        for (int i : {3, 4, 7}) cant_have[i] = 1;
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            int num = i;
            bool bMustHave = false;
            bool bCantHave = false;
            while (num > 0) {
                int r = num % 10;
                if (must_have[r]) bMustHave = true;
                if (cant_have[r]) {
                    bCantHave = true;
                    break;
                }
                num = num / 10;
            }
            if (bMustHave && !bCantHave) ans++;
        }
        return ans;
    }
};

804. Unique Morse Code Words   easy

Example:
Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation: 
The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

There are 2 different transformations, "--...-." and "--...--.".
class Solution {
public:
    int uniqueMorseRepresentations(vector<string>& words) {
        vector<string> morse = {".-","-...","-.-.","-..",".","..-.",
                                "--.","....","..",".---","-.-",".-..",
                                "--","-.","---",".--.","--.-",".-.",
                                "...","-","..-","...-",".--","-..-",
                                "-.--","--.."};
        unordered_set<string> us;
        string tmp;
        for (auto& w : words) {
            tmp.clear();
            for (auto& c : w) {
                tmp += morse[c - 'a'];
            }
            us.emplace(tmp);
        }
        return (int)us.size();
    }
};

823. Binary Trees With Factors   medium

Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].
class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& A) {
        const long m = pow(10, 9) + 7;
        sort(A.begin(), A.end());
        map<int, long> dp;
        for (int i = 0; i < A.size(); i++) {
            dp.insert(make_pair(A[i], 1));
            for (int j = 0; j < i; j++) {
                if (A[i] % A[j] == 0 && dp.count(A[i] / A[j])) {
                    dp[A[i]] += (dp[A[j]] * dp[A[i] / A[j]]) % m;
                }
            }
        }
        long ans = 0;
        for (auto& kv : dp) ans += kv.second;
        return ans % m;
    }
};

824. Goat Latin   easy

Input: "I speak Goat Latin"
Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"
class Solution {
public:
    string goatLatinWord(string s, int ind) {
        set<char> vowels({'a', 'e', 'i', 'o', 'u',
                          'A', 'E', 'I', 'O', 'U'});
        if (vowels.count(s[0])) {
            s += "ma";
        } else {
            char c = s[0];
            s.erase(s.begin());
            s.push_back(c);
            s += "ma";
        }
        while (ind--) {
            s += "a";
        }
        return s;
    }
    string toGoatLatin(string S) {
        int n = (int) S.size();
        string result;
        int begin = 0;
        int counter = 0;
        int ind = 1;
        string word;
        for (int i = 0; i < n; i++) {
            if (S[i] == ' ') {
                word = S.substr(begin, counter);
                result += this->goatLatinWord(word, ind++);
                result += " ";
                begin = i + 1;
                counter = 0;
            } else {
                counter++;
                continue;
            }
        }
        word = S.substr(begin, n);
        result += this->goatLatinWord(word, ind);
        return result;
    }
};

852. Peak Index in a Mountain Array   easy

Input: [0,2,1,0]
Output: 1
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        if (A.size() == 0 || A.size() == 1) return 0;
        int prev = A[0];
        for (int i = 1; i < (int)A.size(); i++) {
            if (A[i] > prev) prev = A[i];
            else return i - 1;
        }
        return A.size() - 1;
    }
};

863. All Nodes Distance K in Binary Tree   medium

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

Output: [7,4,1]
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        buildGraph(nullptr, root);
        queue<TreeNode*> q;
        unordered_set<TreeNode*> seen;
        vector<int> results;
        q.push(target);
        seen.insert(target);
        int depth = 0;
        while (!q.empty() && depth <= K) {
            int num = (int)q.size();
            while (num--) {
                TreeNode* node = q.front(); q.pop();
                if (depth == K) results.push_back(node->val);
                for (auto& child : graph[node]) {
                    if (!seen.count(child)) {
                        q.push(child);
                        seen.insert(child);
                    }
                }
            }
            depth++;
        }
        return results;
    }
private:
    unordered_map<TreeNode*, vector<TreeNode*>> graph;
    void buildGraph(TreeNode* parent, TreeNode* child) {
        if (parent) {
            graph[parent].push_back(child);
            graph[child].push_back(parent);
        }
        if (child->left) buildGraph(child, child->left);
        if (child->right) buildGraph(child, child->right);
    }
};

867. Transpose Matrix   easy

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]
class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& A) {
        vector<vector<int>> res;
        if (A.size() == 0) return res;
        if (A[0].size() == 0) return res;
        for (int i = 0; i < (int) A[0].size(); i++) {
            vector<int> tmp;
            for (int j = 0; j < (int) A.size(); j++) {
                tmp.push_back(A[j][i]);
            }
            res.push_back(tmp);
        }
        return res;
    }
};

894. All Possible Full Binary Trees   medium

A full binary tree is a binary tree where each node has exactly 0 or 2 children. Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree. Each node of each tree in the answer must have node.val = 0. You may return the final list of trees in any order.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int N) {
        if (N % 2 == 0) return {};
        if (N == 1) return {new TreeNode(0)};
        vector<TreeNode*> ans;
        for (int i = 1; i < N; i += 2) {
            for (const auto& left : allPossibleFBT(i)) {
                for (const auto& right : allPossibleFBT(N - i - 1)) {
                    TreeNode *root = new TreeNode(0);
                    root->left = left;
                    root->right = right;
                    ans.push_back(root);
                }
            }
        }
        return ans;
    }
};

896. Monotonic Array   easy

class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        set<bool> sb;
        for (size_t i = 0; i < A.size() - 1; i++) {
            if (A[i] > A[i + 1]) sb.insert(true);
            if (A[i] < A[i + 1]) sb.insert(false);
        }
        return sb.size() == 2 ? false : true;
    }
};

931. Minimum Falling Path Sum   medium

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation: 
The possible falling paths are:
- [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
- [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
- [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
The falling path with the smallest sum is [1,4,7], so the answer is 12.
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& A) {
        int n = (int) A.size();
        vector<vector<int>> mat(n+1, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int v1 = j > 0 ? mat[i][j-1] : INT_MAX;
                int v2 = mat[i][j];
                int v3 = j < n-1 ? mat[i][j+1] : INT_MAX;
                mat[i+1][j] = min(min(v1, v2), v3) + A[i][j];
            }
        }
        return *min_element(mat[n].begin(), mat[n].end());
    }
};
Edited by Isaac Gu on 2019-07-16 Tue 09:35