czxttkl

General Idea:

You need to first flip matrix upside down. Then swap elements mirror to the diagonal.

<span class="hljs-comment"> # clockwise rotate
 # first reverse up to down, then swap the symmetry 
 # 1 2 3     7 8 9     7 4 1
 # 4 5 6  => 4 5 6  => 8 5 2
 # 7 8 9     1 2 3     9 6 3</span>

Code

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        matrix[:] = zip(*matrix[::-1])
        

Idea

Pythonic way. 

Code

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        
        self.upside_down(matrix)
        self.mirror_diag(matrix)

    def upside_down(self, matrix):
        n = len(matrix)
        for i in xrange(n/2):
            for j in xrange(n):
                matrix[i][j], matrix[n-i-1][j] = matrix[n-i-1][j], matrix[i][j]

    def mirror_diag(self, matrix):
        n = len(matrix)
        for i in xrange(n):
            for j in xrange(i+1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Idea

Self implement upside down and mirror.

Reference:

https://discuss.leetcode.com/topic/15295/seven-short-solutions-1-to-7-lines

https://discuss.leetcode.com/topic/6796/a-common-method-to-rotate-the-image/2

Code

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        pre = 0
        sum = 0
        mapping = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000} 
        for ch in s[::-1]:
            i = mapping[ch]
            if i >= pre:
                sum += i
            else:
                sum -= i
            pre = i

        return sum

Idea

Fun to know how to read Roman number!

Reference: 

https://discuss.leetcode.com/topic/821/my-solution-for-this-question-but-i-don-t-know-is-there-any-easier-way/2 (Answer from vera_qing)

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Code

from collections import deque 
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if digits == "": return []
        
        mapping = ["0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        res = deque([''])
        for i in digits:
            for j in xrange(len(res)):
                s = res.popleft()
                for k in mapping[int(i)]:
                    res.append(s + k)
        
        return list(res)

Idea

Use a FIFO queue. Therefore, we can maximally reduce extra space needed.

Reference: https://discuss.leetcode.com/topic/8465/my-java-solution-with-fifo-queue

Code

from collections import deque 
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if digits == "": return []
        
        mapping = ["0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        return reduce(lambda acc, d: [x+y for x in acc for y in mapping[int(d)]], digits, [''])

Idea 

Pythonic way using reduce.

Reference: https://discuss.leetcode.com/topic/11783/one-line-python-solution

https://leetcode.com/problems/3sum-closest/

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Code

import sys

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums = sorted(nums)
        min_diff = sys.maxint
         
        for i in xrange(len(nums)-2):
            j = i + 1
            k = len(nums)-1
            while j < k:
                cur_sum = nums[i] + nums[j] + nums[k]
                cur_diff = abs(cur_sum - target)
                if cur_diff < min_diff:
                     res = cur_sum
                     min_diff = cur_diff
                if cur_sum > target:
                     k -= 1
                elif cur_sum < target:
                     j += 1
                else:
                     return res

        return res

Idea

Sort the array first. Then, create three pointers, i, j and k, such that, when i is fixed, j and k are adjusted to make the 3sum approach the target. The total time complexity is O(N^2) where N is the length of nums.

Code 

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        M = ["", "M", "MM", "MMM"]
        C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
        X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
        I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
        return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10]

Idea

Nothing much.

Code

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        lp, rp = 0, len(height)-1
        max_area = 0
        while lp < rp:
            max_area = max(max_area, min(height[lp],height[rp]) * (rp-lp))
            if height[lp] < height[rp]:
                lp += 1
            else:
                rp -= 1
        return max_area

Idea

The time complexity is O(N). The idea is that if height[lp] < height[rp], then the bottleneck to determine the container volume is height[lp]. That means the container formed by height[lp] and height[rp'] for any rp' < rp must have smaller volume than that formed by height[lp] and height[rp]. In this case, lp should move to right.

You can easily deduct the other case: height[rp] < height[lp].

Reference: https://discuss.leetcode.com/topic/3462/yet-another-way-to-see-what-happens-in-the-o-n-algorithm

Code

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        lp, rp = 0, len(s)-1
        while lp < rp:
            while lp < rp and not s[lp].isalnum():
                lp += 1
            while lp < rp and not s[rp].isalnum():
                rp -= 1
            if s[lp].lower() != s[rp].lower():
                return False
            lp += 1
            rp -= 1
        
        return True

Idea

Not much to say. First time to use string.isalnum().

[
  ["aa","b"],
  ["a","a","b"]
]

Code

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        res = []
        self.recur(0, s, [], res)
        return res

    def recur(self, cur_idx, s, splits, res):
        if cur_idx == len(s):
            res.append(list(splits))
            return

        for i in xrange(cur_idx + 1, len(s)+1):
            if self.isPalindrome(s[cur_idx:i]):
                splits.append(s[cur_idx:i])
                self.recur(i, s, splits, res)
                splits.pop()

    def isPalindrome(self, ss):
        return ss == ss[::-1]

Idea

You progressively try every split position in the string. Check whether substring between the last split position to current split position is palindrome. If so, recursively try the rest of split positions, with the current substring being added to splits.

Reference: https://discuss.leetcode.com/topic/10955/clean-c-backtracking-solution 

https://leetcode.com/problems/pascals-triangle/

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

Code

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        if numRows == 0:
            return []
        
        res = [[1]]
        for i in xrange(2, numRows+1):
            new_row = [0] * i
            for j in xrange(i):
                if j == 0:
                    new_row[j] = 1
                elif j == i-1:
                    new_row[j] = 1
                else: 
                    new_row[j] = res[-1][j-1] + res[-1][j]
            res.append(new_row)
            
        return res   

Idea

Each element is the sum of adjacent elements in the above line. That’s how Pascal’s Triangle is defined: https://en.wikipedia.org/wiki/Pascal%27s_triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

Code 

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if len(triangle) == 0:
            return 0
        
        if len(triangle) == 1:
            return triangle[0][0] 
        
        last_level_sum = {0:triangle[0][0]}
        for i in xrange(1, len(triangle)):
            this_level_sum = {}
            for j in xrange(len(triangle[i])):    
                if j == 0:
                     this_level_sum[j] = last_level_sum[0] + triangle[i][j]
                elif j == len(triangle[i])-1:
                     this_level_sum[j] = last_level_sum[j-1] + triangle[i][j]
                else:
                     this_level_sum[j] = min(last_level_sum[j], last_level_sum[j-1]) + triangle[i][j]
        
            last_level_sum = this_level_sum         

        return min(last_level_sum.values())

Idea

You go from top to bottom. Record the minimum sum until every layer. If you use a bottom-up DP, the solution can be more elegant.

Reference:

https://discuss.leetcode.com/topic/1669/dp-solution-for-triangle/2