czxttkl

Code

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

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # dummy node, the node before head
        node_prev = ListNode(0)
        node_prev.next = head
        node_prev_bak = node_prev
            
        while node_prev.next and node_prev.next.next:
            node1, node2 = node_prev.next, node_prev.next.next
            
            # doing the actual swap
            node_prev.next = node2
            node1.next = node2.next
            node2.next = node1
            
            node_prev = node1
            
        return node_prev_bak.next
        
        

Idea

Very straightforward. Every time, you do the swapping on the two nodes.

Reference

https://discuss.leetcode.com/topic/18860/7-8-lines-c-python-ruby

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Code

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        if len(nums) < 4: 
            return []

        res = []
        nums = sorted(nums)

        for i in xrange(len(nums)-3):
            if i > 0 and nums[i-1] == nums[i]:
                continue
            for j in xrange(i+1, len(nums)-2):
                if j > i+1 and nums[j-1] == nums[j]:
                    continue
                m, n = j+1, len(nums)-1
                while m < n:
                    if nums[i]+nums[j]+nums[m]+nums[n] == target:
                        res.append((nums[i], nums[j], nums[m], nums[n]))
                        while m < n and nums[m] == nums[m+1]:
                            m += 1
                        while m < n and nums[n] == nums[n-1]:
                            n -=1
                        m += 1
                        n -= 1
                    elif nums[i]+nums[j]+nums[m]+nums[n] < target:
                        m += 1
                    else:
                        n -= 1

        return res
        

Idea

As usual, sort the array first. Then create four indices, i, j, m and n. Every time, fix i and j and move m and n as to approach target. Be very careful about dealing with duplicates. (line 16-17, 19-20, 25-28).

Also see 2Sum and 3Sum. 

Reference: https://discuss.leetcode.com/topic/12368/clean-accepted-java-o-n-3-solution-based-on-3sum/2

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

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

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        i = 0
        head_bak, n_to_last, n_plus_1_to_last = head, head, head
        
        while head:
            i += 1
            if i >= n+1:
                n_to_last = n_to_last.next
            if i >= n+2:
                n_plus_1_to_last = n_plus_1_to_last.next
            head = head.next
        
        if i == n:
            return head_bak.next
        else:
            n_plus_1_to_last.next = n_to_last.next
            return head_bak
        

Another idea can be seen: https://discuss.leetcode.com/topic/7031/simple-java-solution-in-one-pass

11110
11010
11000
00000

11000
11000
00100
00011

Code

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0

        res = 0
        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                if grid[i][j] == '1':
                    res += 1
                    self.explore(grid, i, j)
        return res

    def explore(self, grid, i, j):
        grid[i][j] = "*"
        # down, up, right, left
        for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            if 0 <= i+di < len(grid) and 0 <= j+dj < len(grid[0]) \
                and grid[i+di][j+dj] == '1':
                    self.explore(grid, i+di, j+dj)

Idea

Whenever you see an 1, increment result by 1. The method explore visits adjacent 1’s in a DFS manner. Every visited cell will be re-marked so that no future visit will happen.

If the grid size is N^2, then the time complexity is O(N^2) and the space complexity is O(N^2) as well because DFS recursive calls can visit up to all cells and take O(N^2) stack frame.

Reference: https://discuss.leetcode.com/topic/11590/simple-java-solution

Code

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        left, right = 0, len(nums)-1
        for i in xrange(len(nums)):
            while nums[i] == 2 and i < right:
                nums[i], nums[right] = nums[right], nums[i]
                right -= 1
            while nums[i] == 0 and i > left:
                nums[i], nums[left] = nums[left], nums[i]
                left += 1
            

Idea

Put all 2’s after `right`. Put all 1’s before `left`.

Reference: https://discuss.leetcode.com/topic/5422/share-my-one-pass-constant-space-10-line-solution

A post to review RadixSort. The idea is to 

Code

class RadixSort():

    def sort(self, nums):
        max_num = max(nums)

        exp = 1
        while max_num / exp:
            nums = self.count_sort(nums, exp)
            exp = exp * 10

        return nums

    def count_sort(self, nums, exp):
        # how many numbers have 0~9 for the current position
        digit_counts = [0] * 10

        for n in nums:
            digit_counts[(n / exp) % 10] += 1

        # accumulate counts
        for i in xrange(1, 10):
            digit_counts[i] += digit_counts[i-1]

        outputs = [0] * len(nums)
        # traverse from tail to head because we want to keep original order
        # of numbers having same digit on the current position
        for n in nums[::-1]:
            outputs[digit_counts[(n / exp) % 10] - 1] = n
            digit_counts[(n / exp) % 10] -= 1

        return outputs


if __name__ == "__main__":
    s = RadixSort()
    print s.sort([4,3,1,20,100])

Idea

Traverse digits: for each digit, count how many numbers have 0~9 on that digit and put the counts in a bucket (digit_count). Then, convert the bucket into accumulated counts. For example, if digit_count[0]=3 and digit_count[1]=4, then after the conversion, digit_count[1]=7 because we know numbers with 1 on that digit will be put in the position between `[3, 7)` (position starts from 0).  

Then we can reorder the numbers. We reorder from right to left (line 27~29) because we want to keep the original order of numbers which have the same digit on the current digit position.

If a number at most uses $latex d$ digits, radix sort uses time $latex O(d(n+d))$ and space $latex O(n+d)$.  

Reference: http://www.geeksforgeeks.org/radix-sort/

Also see MergeSort and QuickSort.

Code

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 0
        major = ''
        for n in nums:
            if count == 0:
                major = n
            if n == major:
                count += 1
            else:
                count -= 1
        return major

Idea

This is the algorithm called Moore voting. More details can be found: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/. My understanding is that major is the current number whose occurrences has not been outnumbered by other numbers. The majority element will eventually has its occurrence count being positive. 

Code

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        
        for i in xrange(32):
            ones, zeros = 0, 0
            for n in nums:
                # right shift for negative number is weird 
                # in Python. So apply on absolute value.
                if (abs(n) >> i) & 1:
                    ones += 1
                else:
                    zeros += 1
            if ones > zeros:
                ans = ans | (1 << i)
                
        # in python, you need to count signs separately.        
        positive, negative = 0, 0
        for n in nums:
            if n > 0:
                positive += 1
            else:
                negative += 1
        if positive > negative:
            return ans
        else:
            return -ans

Idea

Borrow the idea from Single Number II. Count one’s and zeros appearing in each bit. The majority element dominates those counts so you can reconstruct the number.

Reference: https://discuss.leetcode.com/topic/6286/share-my-solution-java-count-bits

Code (divide and conquer)

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return None
        if len(nums) == 1:
            return nums[0]
        a = self.majorityElement(nums[:len(nums)/2])
        b = self.majorityElement(nums[len(nums)/2:])
        if a == b:
            return a
        else:
            return a if nums.count(a) > len(nums)/2 else b

Idea

THink from top to bottom. When nums have two partitions, and we already know a is the majority element of the first partition (line 11) and b is the majority element of the second partition (line 12). If c is the majority element, then either:

1. a == b == c, i.e., c is the majority element in both partitions
2. a != b. then c must be equal to either a or b. 

We can prove 2 by contradiction. If c != a and c != b, then c is not the majority element in either partition. That means, occurrences(c in 1st partition) <= len(1st partition)/2 and occurrences(c in 2nd partition) <= len(2nd partition)/2. Therefore, occurences(c in nums) <= len(nums)/2, which contradicts with the fact that c is the majority element. So we recursively can prove the correctness of every level of divide-and-conquer.

Code (Sorting)

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sorted(nums)[len(nums)/2]

Idea

After sorting, the majority element must occupy the position len(nums)/2

Code

# The knows API is already defined for you.
# @param a, person a
# @param b, person b
# @return a boolean, whether a knows b
# def knows(a, b):

class Solution(object):
    def findCelebrity(self, n):
        """
        :type n: int
        :rtype: int
        """
        # pick up two candidates, exclude at least one each time
        candidates = set(range(n))
        while len(candidates) > 1:
            a, b = candidates.pop(), candidates.pop()
            if knows(a, b) and not knows(b, a):
                candidates.add(b)
            elif not knows(a, b) and knows(b, a):
                candidates.add(a)

        if len(candidates) == 1:
            c = candidates.pop()
            # when only one candidate is left, we still need to ensure
            # his celebrity by definition
            for i in xrange(n):
                if i != c and not (knows(i, c) and not knows(c, i)):
                    return -1
            return c
        else:
            return -1

Idea

This is my first attack. Create a set of candidates. Exclude at least one candidate by determining two candidates’ relationship each time. When there is only one candidate c left, we still need to check by definition whether knows(i, c) and not knows(c, i) for all i != c. 

An improved idea is to think this problem as numerical comparisons. knows(a,b) means a < b. The celebrity will be the largest element among all peers.

Therefore, the code could be:

# The knows API is already defined for you.
# @param a, person a
# @param b, person b
# @return a boolean, whether a knows b
# def knows(a, b):

class Solution(object):
    def findCelebrity(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0: 
            return -1
        
        x = 0
        for i in xrange(1, n):
            if knows(x, i):
                x = i
        
        for i in xrange(n):
            if i != x and not (knows(i, x) and not knows(x, i)):
                return -1
        return x

Reference: https://discuss.leetcode.com/topic/25720/java-python-o-n-calls-o-1-space-easy-to-understand-solution

Code

class Solution(object):
    def maxSubArrayLen(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        sum = 0
        max_res = 0
        # key: sum of all elements so far, value: the index so far
        sum_map = dict()

        for i, n in enumerate(nums):
            sum += n
            if sum == k:
                max_res = i + 1
            elif sum_map.get(sum-k, None) is not None:
                max_res = max(max_res, i - sum_map[sum-k])
            # if sum already exists in sum_map, its index should be
            # smaller than the current index. Since we want to find
            # the maximum length of subarray, the smaller index
            # should be kept.
            if sum_map.get(sum, None) is None:
                sum_map[sum] = i

        return max_res

Idea

The obvious brute-force way is to have two pointers, i and j (0 <=i<len(nums), i+1<=j <len(nums)), and test whether nums[i:j+1] sum to k. This takes O(n^2) time where n is the length of nums.

Our code uses the following idea: Create a dictionary sum_map which records the sum of all previous elements when traversing nums. Its key is the sum of all elements so far and its value is the current index. 

During the traversal, we can check whether the current sum so far equals to k (line 15-16). We can also check whether sum_map contains sum-k as a key. If so, that means a subarray can be found between `sum_map[sum-k]` and `i`.

Reference: https://discuss.leetcode.com/topic/33259/o-n-super-clean-9-line-java-solution-with-hashmap

Code

class Solution(object):
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        for idx, (chr_s, chr_t) in enumerate(zip(s, t)):
            if chr_s != chr_t:
                # when s and t have same length, 
                # the only possibility is they only differ at this index 
                if len(s) == len(t):
                    return s[idx+1:] == t[idx+1:]
                # if s is longer than t, the only possibility is 
                # s has an insertion at idx
                elif len(s) > len(t):
                    return s[idx+1:] == t[idx:]
                # otherwise,, the only possibility is t has an insertion
                # at idx
                else:
                    return s[idx:] == t[idx+1:]

        return abs(len(s) - len(t)) == 1

Idea

See comments. There are only three conditions to determine if two strings are one edit distance apart.

Reference: https://discuss.leetcode.com/topic/30308/my-clear-java-solution-with-explanation