数据结构和算法 -- 数组

Posted on   |   In   |     |  

策略 & 注意点

array 在内存里是连续存储的，意味着 immutable length 和 no holes allowed。带来的优点是支持随机访问，缺点是当 resize array 的时候需要 copy 原有的所有元素，当删除一个不在末尾的元素时，又要 shift 很多元素。

数组最需要注意的：

  1. length 问题，最后一个数 array[len(array)-1]
  2. 指针问题，deepcopy or shallowcopy，对原数组进行多次变形并需纪录每次结果时，要注意 deepcopy 而不是存指针。res.append(list(nums))，如 permutation 这种题。
  3. 可以用虚拟边界
  4. 利用 array 的 index 可以做很多事情（利用 nums[i] 和 nums[nums[i]]）。如 Find the Duplicate Number，把 array 变成 linkedlist，或者

Efficiency

Insertion at back: O(1)
Insertion at front: O(n)
Insertion in middle: O(n)
Searching (using linear search): O(n)
Deletion: O(n)
Access to an element with its index: O(1)

python lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
The list data type has some more methods. Here are all of the methods of list objects:
list.append(x)
Add an item to the end of the list; equivalent to a[len(a):] = [x].
list.extend(L)
Extend the list by appending all the items in the given list; equivalent to a[len(a):] = L.
list.insert(i, x)
Insert an item at a given position. The first argument is the index of the element before which to insert, so a.insert(0, x) inserts at the front of the list, and a.insert(len(a), x) is equivalent to a.append(x).
list.remove(x)
Remove the first item from the list whose value is x. It is an error if there is no such item.
list.pop([i])
Remove the item at the given position in the list, and return it. If no index is specified, a.pop() removes and returns the last item in the list. (The square brackets around the i in the method signature denote that the parameter is optional, not that you should type square brackets at that position. You will see this notation frequently in the Python Library Reference.)
list.index(x)
Return the index in the list of the first item whose value is x. It is an error if there is no such item.
list.count(x)
Return the number of times x appears in the list.
list.sort(cmp=None, key=None, reverse=False)
Sort the items of the list in place (the arguments can be used for sort customization, see sorted() for their explanation).
list.reverse()

Java Arrays

在 java 里，array 有一个方法，clone()，属于 shallow copy。有一个 immutable field，length。
Java Arrays 好用的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int[] a = { 7, 1, 2, 3, 4, 5 };
int[] b = { 7, 1, 2, 3, 4, 5 };
System.out.println("a equals b: " + Arrays.equals(a, b));
System.out.println("a: " + Arrays.toString(a));
Arrays.sort(a);
int[] c = Arrays.copyOf(b, b.length);
// public static void arraycopy(Object source, int srcIndex, Object
// destination, int destIndex, int length)
int[] d = new int[b.length];
System.arraycopy(b, 0, d, 0, 3);
int[] e = b.clone(); // shallow copy, only reference
System.out.println("Sorted a: " + Arrays.toString(a));
System.out.println("c (copied from b): " + Arrays.toString(c));
System.out.println("d (copied from b): " + Arrays.toString(d));
System.out.println("e (copied from b): " + Arrays.toString(e));

outputs

1
2
3
4
5
6
a equals b: true
a: [7, 1, 2, 3, 4, 5]
Sorted a: [1, 2, 3, 4, 5, 7]
c (copied from b): [7, 1, 2, 3, 4, 5]
d (copied from b): [7, 1, 2, 0, 0, 0]
e (copied from b): [7, 1, 2, 3, 4, 5]

Java List

1
2
3
4
5
6
7
8
add(object) : adds a new element to the end
add(index, object) : inserts a new element at the specified
index
set(index, object) : replaces an existing element at the
specified index with the new element.
get(index) : returns the element at the specified index.
remove(index) : deletes the element at the specified index.
size() : returns the number of elements.

Java 7，ArrayList 用的是 doubling-up policy。也就是说，假定 ArrayList 的初始 capacity 为 4，那么加入第 n(n<=4) 个元素的 running time 是 1，而加入第 5 个 item 时，running time 是 5 而不是 1，因为要重新创建一个 double-size list 再把原来的元素 copy 进去。同样的，加入第 9 个元素时的 running time 是 9 而不是 1。用 amortized 的方法可以发现 add(E e) 的操作的 running time 是一个常数，也就是 O(1)。

例题

66. Plus One

Problem

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

Similar problems (M) Multiply Strings (E) Add Binary (M) Add Two Numbers (M) Plus One Linked List
2.445. Add Two Numbers 369. Plus One Linked List
43. Multiply Strings

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        if digits[-1] != 9:
            digits[-1] += 1
            return digits
        i = len(digits) - 1
        while i >= 0 and digits[i] == 9:
            digits[i] = 0
            i -= 1
        if i == -1:
            cur = [1]
            cur.extend(digits)
            return cur
        digits[i] += 1
        return digits

67. Add Binary

Problem

Given two binary strings, return their sum (also a binary string).

For example,
a = “11”
b = “1”
Return “100”.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
'''
Solution:
    1. do it as we do the math
        make sure a is longer than b
        while pb>=0, start from right to left, calculate sum value at each digit and update result and carry.
            cur=int(a[pa])+int(b[pb])+carry
            res=str(cur%2)+res
            carry=cur/2
        while pa>=0, do similar task
            cur=int(a[pa])+carry
            res=str(cur%2)+res
            carry=cur/2
        deal with carry if carry==1
            res='1'+res
    2. do it recursively
        when a[-1]=='1' and b[-1]=='1', recursive case would be
            addBinary(self.addBinary(a[:-1],b[:-1]),'1')+'0'
                current layer: '0'
                previous digit: a[:-1]+b[:-1]+'1'
                    add previous digit as usual: addBinary(a[:-1],b[:-1])
                    add one: addBinary(prev,'1')
                => addBinary(addBinary(a[:-1],b[:-1]),'1')+'0'
'''
'''
class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        if not a: return b
        if not b: return a
        if a[-1]=='0' and b[-1]=='0':
            return self.addBinary(a[:-1],b[:-1])+'0'
        if a[-1]=='1' and b[-1]=='1':
            return self.addBinary(self.addBinary(a[:-1],b[:-1]),'1')+'0'
        else:
            return self.addBinary(a[:-1],b[:-1])+'1'
            '''
class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        # make sure a is longer than b
        if len(a) < len(b):
            a, b = b, a
        pa = len(a) - 1
        pb = len(b) - 1
        res, carry = '', 0
        while pb >= 0:
            cur = int(a[pa]) + int(b[pb]) + carry
            carry = cur / 2
            res = str(cur % 2) + res
            pb -= 1
            pa -= 1
        while pa >= 0:
            cur = int(a[pa]) + carry
            carry = cur / 2
            res = str(cur % 2) + res
            pa -= 1
        if carry == 1:
            res = '1' + res
        return res

228. Summary Ranges

Problem

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return [“0->2”,”4->5”,”7”].

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def summaryRanges(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """
        def joinStr(start,end):
            if start==end:
                return str(nums[start])
            else:
                return str(nums[start])+'->'+str(nums[end])
        if not nums:
            return []
        res=[]
        start,end=0,0
        while end+1<len(nums):
            if nums[end]+1==nums[end+1]:
                end+=1
            else:
                res.append(joinStr(start,end))
                start=end+1
                end=start
        res.append(joinStr(start,end))
        return res

360. Sort Transformed Array

Problem

Given a sorted array of integers nums and integer values a, b and c. Apply a function of the form f(x) = ax2 + bx + c to each element x in the array.

The returned array must be in sorted order.

Expected time complexity: O(n)

Example:

1
2
3
4
5
6
7
nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5,
Result: [3, 9, 15, 33]
nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5
Result: [-23, -5, 1, 7]

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
'''
Notes:
    Because the input is sorted and the function is a second degree polynomial, simply applying the function will result in at most two increasing/decreasing runs. Which Python's sort function will recognize and simply reverse/merge in O(n).
    Refer links:
        https://en.wikipedia.org/wiki/Timsort
        http://blog.csdn.net/yangzhongblog/article/details/8184707
Tips:
    heapq.merge(*iterables): Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns an iterator over the sorted values.
'''
# Method 1
'''
class Solution(object):
    def sortTransformedArray(self, nums, a, b, c):
        return sorted(a*x*x + b*x + c for x in nums)
    '''   
# Method 2: two parts solution
'''
from collections import deque
import heapq
class Solution(object):
    def sortTransformedArray(self, nums, a, b, c):
        """
        :type nums: List[int]
        :type a: int
        :type b: int
        :type c: int
        :rtype: List[int]
        """
        """
        # can simply use heapq.merge()
        def mergeLists(left,right):
            lp,rp=0,0
            res=[]
            while lp<len(left) and rp<len(right):
                if left[lp]<=right[rp]:
                    res.append(left[lp])
                    lp+=1
                else:
                    res.append(right[rp])
                    rp+=1
            while lp<len(left):
                res.append(left[lp])
                lp+=1
            while rp<len(right):
                res.append(right[rp])
                rp+=1
            return res
            """
        if not nums: return None
        d=deque()
        if a==0:
            if b>0:
                for n in nums:
                    d.append(n*b+c)
            else:
                for n in nums:
                    d.appendleft(n*b+c)
        else:
            left=deque()
            right=deque()
            if a>0:
                line=float(-1*b)/(2*a)
                for n in nums:
                    if n<line:
                        left.appendleft(a*n*n+b*n+c)
                    else:
                        right.append(a*n*n+b*n+c)
            else:
                line=float(-1*b)/(2*a)
                for n in nums:
                    if n<line:
                        left.append(a*n*n+b*n+c)
                    else:
                        right.appendleft(a*n*n+b*n+c)
            #d=mergeLists(left,right)
            d=heapq.merge(left,right)
        return list(d)
        '''
# Method 3: two pointers solution
class Solution(object):
    def sortTransformedArray(self, nums, a, b, c):
        """
        :type nums: List[int]
        :type a: int
        :type b: int
        :type c: int
        :rtype: List[int]
        """
        def f(x):
            return a*x*x+b*x+c
        start,end=0,len(nums)-1
        res=[]
        while start<=end:
            resS,resE=f(nums[start]),f(nums[end])
            if a>0:
                if resS<resE:
                    res.append(resE)
                    end-=1
                else:
                    res.append(resS)
                    start+=1
            else:
                if resS>resE:
                    res.append(resE)
                    end-=1
                else:
                    res.append(resS)
                    start+=1
        if a>0:
            return res[::-1]
        return res

346. Moving Average from Data Stream

Problem

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
For example,
MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
'''
Solution:
- maintain a deque of at most 'size' length, for each next call, enque the number, calculate average, check if the length of deque is 3, if it is, popleft, and finally return the average. Time complexity O(n); Space complexity O(size)
Follow-up:
- make it O(1), save the sum each time, that is for each next call, enque the number, add to global sum, calculate average, check if the length of deque is 3, if it is, pop left, minus popped number from sum, and finally return the average.
'''
from collections import deque
class MovingAverage(object):
    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.q=deque()
        self.size=size
        self.sum=0
    def next(self, val):
        """
        :type val: int
        :rtype: float
        """
        self.q.append(val)
        self.sum+=val
        avg=self.sum/float(len(self.q))
        if len(self.q)==self.size:
            self.sum-=self.q.popleft()
        return avg
# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)

75. Sort Colors

subarray 问题

Problem

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library’s sort function for this problem.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
'''
Solution:
- quicksort?  Time complexity: O(nlogn)
- 3 numbers, so count and reset, Time complexity: O(n), Space complexity: O(3)->O(1), two-pass
- subarray with different states, Time complexity: O(n)
Attention:
- for solution 3, boundary is tricky, remember pointer is not included
Test case:
- [0]
- [0,0,0]
'''
class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if len(nums)<=1:
            return
        left,right,cur=0,len(nums)-1,0
        while cur<=right:
            if nums[cur]==0:
                nums[cur],nums[left]=nums[left],nums[cur]
                left+=1
                cur+=1
            elif nums[cur]==2:
                nums[cur],nums[right]=nums[right],nums[cur]
                right-=1
            else:
                cur+=1
    '''            
    # two-pass solution: count and reset            
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if len(nums)<1:
            return
        a0,a1,a2=0,0,0
        for n in nums:
            if n==0: a0+=1
            elif n==1: a1+=1
            elif n==2: a2+=1
        for i in range(len(nums)):
            if a0>0:
                nums[i]=0
                a0-=1
            elif a1>0:
                nums[i]=1
                a1-=1
            elif a2>0:
                nums[i]=2
                a2-=1
    '''

53. Maximum Subarray

Problem

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
'''
Solution:
- subarray: 2 pointers: head,tail
- any repeated work? no   any meaningless work? yes    check the sum-array and we can find that the non-max-sum either subtract one more number or miss one more addition --> cur_sum=max(cur_sum,nums[start]+cur_sum)
'''
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cur_sum,max_sum=nums[0],nums[0]
        for start in range(1,len(nums)):
            cur_sum=max(nums[start],nums[start]+cur_sum)
            max_sum=max(cur_sum,max_sum)
        return max_sum
    '''
    # brute-force, time limit exceeded
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums)==0:
            return 0
        global_sum=nums[0]
        for i in range(0,len(nums)-1):
            part_sum=nums[i]
            if part_sum>global_sum:
                global_sum=part_sum
            for j in range(i+1,len(nums)):
                part_sum+=nums[j]
                if part_sum>global_sum:
                    global_sum=part_sum
        part_sum=nums[-1]
        if part_sum>global_sum:
            global_sum=part_sum
        return global_sum
    '''

Snapchat 面经

Problem

Returns unsorted part of an array.
For example, input -> [1,2,5,7,6,4,9], output -> [5,7,6,4]

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
'''
Solution:
    Easiest way is to sort the array and compare it with the original array, get the first and last digit of different number, and return the list.
    It takes O(nlogn) time.
Followup -> O(n) time
    Use two pointers, lastDigit and firstDigit, and two global variables, curMax and curMin
    For a sorted array, if we start for left to right curMax should be current number, and if we start from right to left, curMin should be current number.
    So starts from left to right, keep track of curMax, first update curMax, and then check if current number is current max, if not, update lastDigit, repeat till we finish the loop.
    Then starts from right to left, keep track of curMin, first update curMin, and then check if current number is current min, if not, update firstDigit, repeat till we finish the loop.
    Return array[firstDigit,lastDigit+1]
    Time complexity: O(n)
'''
def solution(array):
    if not array:
        return []
    # keep track of current maximum and minimum
    lastDigit, firstDigit = 0, len(array) - 1
    curMax, curMin = array[0], array[len(array) - 1]
    for i in xrange(len(array)):
        curMax = max(array[i], curMax)
        if array[i] < curMax:
            lastDigit = i
    for i in xrange(len(array) - 1, -1, -1):
        curMin = min(array[i], curMin)
        if array[i] > curMin:
            firstDigit = i
    return array[firstDigit:lastDigit + 1]
print solution([])
print solution([1, 2, 5, 7, 6, 4, 9])
print solution([1, 2, 5, 5, 1])

Finding sum of Absolute Difference of Every pair of integer from an array

Problem

Given an array, find the sum of the absolute difference of every pair of integers.
For example: Given a[]= {2, 3, 5, 7 };
output would be (3-2) + (5-2) + (7-2) + (5-3) + (7-3) + (7-5) = 17.
It must be done better than O(n^2).
The original array isn’t necessarily sorted.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'''
First, sort the array. Let's say the sorted array looks like [-5, 2, 3, 5].  To consider only distinct pairs, for each element, pair it with only the elements that came before it. That means that the contribution of 3 to the total result is abs(3 - 2) + abs(3 - (-5)). Because the array is sorted, all the elements that came before are smaller or equal, so this can safely be rewritten as 3 * 2 - (2 + (-5)). In general terms, the contribution of arr[i] to the sum is arr[i] * i - sum (arr[0...i-1]). Fortunately, we can maintain the sum term as we go, avoiding expensive recomputation. We'll get the answer when we sum the contributions of each arr[i].
This code runs in O(n)O(n) time after sorting, so the overall algorithm is O(nlogn)O(nlog⁡n), unless the data you have makes it easy to sort faster than that.
Depending on the meaning of the term "distinct pairs", you may need to dedupe the array before running the linear pass over the data. That is, if on an input like [1, 2, 1, 2, 3], you wouldn't want to count (2, 1) several times (even though there's several ways the pair can form), then you should just dedupe the input. Convert [1, 2, 1, 2, 3] to [1, 2, 3].
'''
def solution(arr):
    if not arr:
        return 0
    arr.sort()
    total = 0
    arraySum = 0
    for i in range(0, len(arr)):
        total += (arr[i] * i - arraySum)
        arraySum += arr[i]
    return total

11. Container With Most Water

Problem

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.

Note: You may not slant the container and n is at least 2.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
'''
Solution:
    check every possible container (each combination of (i,j) where i,j < len(height))
    v=(j-i)*min(height[i],height[j])
    cur_max=max(v,cur_max)
    takes O(n^2) time
Followup: make it O(n)
    if we choose i=0 and an any other number in array, we can ensure v<height[0]*l where l=len(height), same reason, if we choose j=len(height)-1 and an any other number in array, we can ensure v<height[-1]*l
    thus, we start from i=0 and j=len(height)-1 and get a container with volume v1, then in order to get a larger container, we wanna a heigher boundary(height), so we discard the smaller number between height[i] and height[j], and get a new volume v2, repeat this process till i==j
'''
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height or len(height)==1:
            return 0
        start,end=0,len(height)-1
        cur_max=float('-inf')
        while start<end:
            cur=(end-start)*min(height[start],height[end])
            cur_max=max(cur,cur_max)
            if height[start]>height[end]:
                end-=1
            else:
                start+=1
        return cur_max

84. Largest Rectangle in Histogram

Problem

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
'''
Solution:
A simple solution is to one by one consider all bars as starting points and calculate area of all rectangles starting with every bar. Finally return maximum of all possible areas. Time complexity of this solution would be O(n^2).
We can use Divide and Conquer to solve this in O(nLogn) time. The idea is to find the minimum value in the given array. Once we have index of the minimum value, the max area is maximum of following three values.
a) Maximum area in left side of minimum value (Not including the min value)
b) Maximum area in right side of minimum value (Not including the min value)
c) Number of bars multiplied by minimum value.
The areas in left and right of minimum value bar can be calculated recursively. If we use linear search to find the minimum value, then the worst case time complexity of this algorithm becomes O(n^2). In worst case, we always have (n-1) elements in one side and 0 elements in other side and if the finding minimum takes O(n) time, we get the recurrence similar to worst case of Quick Sort.
Followup:
- O(n)?
    - avoid repeated work
    - identify a rectangle: identify 2 boundaries
    - if cur>stack.peek() --> offer, else --> continously poll
    For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate such area for every bar ‘x’ and find the maximum of all areas, our task is done.
    How to calculate area with ‘x’ as smallest bar? We need to know index of the first smaller (smaller than ‘x’) bar on left of ‘x’ and index of first smaller bar on right of ‘x’. Let us call these indexes as ‘left index’ and ‘right index’ respectively.
    We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’. Following is the complete algorithm.
    1) Create an empty stack.
    2) Start from first bar, and do following for every bar ‘hist[i]’ where ‘i’ varies from 0 to n-1.
    ……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
    ……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).
    3) If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.
Corner case: [0]
'''
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        if not heights: return 0
        stack=[]
        max_area=0
        for i in range(len(heights)+1):
            while stack and (i==len(heights) or heights[i]<heights[stack[-1]]):
                height=heights[stack.pop()]
                leftBound=0 if not stack else stack[-1]+1
                rightBound=i
                cur_area=(rightBound-leftBound)*height
                max_area=max(cur_area,max_area)
            stack.append(i)
        return max_area
    '''
    # primitive, 2 loops
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        if not heights: return 0
        max_area=0
        for i in range(len(heights)):
            max_area=max(heights[i],max_area)
            min_height=heights[i]
            for j in range(i,len(heights)):
                min_height=min(min_height,heights[j])
                max_area=max(min_height*(j-i+1),max_area)
        return max_area
        '''
    '''
    # DP: avg: O(nlogn)   worst: O(n^2)
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        # DP Solution
        def maxArea(left,right):
            if right-left==1:
                return heights[left]
            if right==left:
                return 0
            minHeight=min(heights[left:right])
            minHeightIndex=heights[left:right].index(minHeight)+left
            maxLeft=maxArea(left,minHeightIndex)
            maxRight=maxArea(minHeightIndex+1,right)
            cur=minHeight*(right-left)
            return max(maxLeft,maxRight,cur)
        if not heights: return 0
        return maxArea(0,len(heights))
        '''

463. Island Perimeter

Problem

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example:

1
2
3
4
5
6
7
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]
Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:

island.jpg

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution(object):
    '''
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        newGrid=[[0]*(len(grid[0])+2) for i in range(len(grid)+2)]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                newGrid[i+1][j+1]=grid[i][j]
        res=0
        for i in range(1,len(newGrid)-1):
            for j in range(1,len(newGrid[0])-1):
                if newGrid[i][j]==1:
                    # check around
                    if newGrid[i][j-1]==0:
                        res+=1
                    if newGrid[i][j+1]==0:
                        res+=1
                    if newGrid[i-1][j]==0:
                        res+=1
                    if newGrid[i+1][j]==0:
                        res+=1
        return res
        '''
    '''
    Simplify version
    '''
    def islandPerimeter(self, grid):
        def water_around(y, x):
            return ((x == 0              or grid[y][x-1] == 0) +
                    (x == len(grid[0])-1 or grid[y][x+1] == 0) +
                    (y == 0              or grid[y-1][x] == 0) +
                    (y == len(grid)-1    or grid[y+1][x] == 0) )
        return sum(water_around(y, x) for y in xrange(len(grid)) for x in xrange(len(grid[0])) if grid[y][x])

448. Find All Numbers Disappeared in an Array

Problem

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]

Tags: Array
Similar Problems: (H) First Missing Positive (M) Find All Duplicates in an Array

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
'''
Soltuion:
    Bucket sort.
    The idea is simple, we're gonna make all numbers into the corrent position. Each element w should be put into the w th position of the array.If nums[i] != i + 1 and nums[i] != nums[nums[i] - 1], then we swap nums[i] with nums[nums[i] - 1], for example, nums[0] = 4 and nums[3] = 7, then we swap nums[0] with nums[3]. So In the end the array will be sorted and if nums[i] != i + 1, then i + 1 is missing.
    The example run as follows
    [4,3,2,7,8,2,3,1]
    [7,3,2,4,8,2,3,1]
    [3,3,2,4,8,2,7,1]
    [2,3,3,4,8,2,7,1]
    [3,2,3,4,8,2,7,1]
    [3,2,3,4,1,2,7,8]
    [1,2,3,4,3,2,7,8]
    Since every swap we put at least one number to its correct position, the time is O(n)
Special case: [2,2]
'''
class Solution(object):
    '''
    brute-force: O(n^2)
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums: return []
        res=[]
        for i in range(1,len(nums)+1):
            if i not in nums:
                res.append(i)
        return res
        '''
    '''
    Sort: O(nlogn)
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums: return []
        nums.sort()
        i=0
        n=len(nums)
        res=[]
        for cur in nums:
            if cur==i:
                continue
            if cur==i+1:
                i+=1
                continue
            while i < cur-1:
                i+=1
                res.append(i)
            i=cur
        while i<n:
            i+=1
            res.append(i)
        return res
        '''
    Sort: O(n)
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []
        for i in range(len(nums)):
            while nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        res = []
        print nums
        for i, num in enumerate(nums):
            if i + 1 != num:
                res.append(i + 1)
        return res
    '''
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # Use nums as hashmap
        # For each number i in nums, mark the number that i points as negative.
        # Then filter the list, get all the indexes that points to a positive number
        for i in range(len(nums)):
            index = abs(nums[i]) - 1
            nums[index] = - abs(nums[index])
        return [i + 1 for i in range(len(nums)) if nums[i] > 0]
        '''

442. Find All Duplicates in an Array

Problem

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]

Tags: Array
Similar Problems: (E) Find All Numbers Disappeared in an Array

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
'''
Solution:
    Bucket sort. Each element w should be put into the w th position of the array.
'''
class Solution(object):
    '''
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        hashset=set()
        res=[]
        for n in nums:
            if n in hashset:
                res.append(n)
            else:
                hashset.add(n)
        return res
        '''
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums: return []
        res=[]
        for i in range(len(nums)):
            while nums[i] != nums[nums[i]-1]:
                nums[nums[i]-1],nums[i]=nums[i],nums[nums[i]-1]
        for i,n in enumerate(nums):
            if i+1 != n:
                res.append(n)
        return res

41. First Missing Positive

Problem

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Tags: Array
Similar Problems: (M) Missing Number (H) Find the Duplicate Number (E) Find All Numbers Disappeared in an Array

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
'''
Solution:
    Bucket sort is the only way. As only the elements between 1...n are useful, each element w should be put into the w th position of the array. As it is possible there is some other element v in the w th position, take the v out before overwriting and then iteratively use the same logic on v and go on.
    Time complexity: each element is looped 2 times and swapped 1 time, so the whole time compexity is O(n)
    Space: O(1) apparently
'''
class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        for i in xrange(len(nums)):
            while nums[i] > 0 and nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i, num in enumerate(nums):
            if i + 1 != num:
                return i + 1
        return n + 1

287. Find the Duplicate Number

Problem

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

Tags: Binary Search Array Two Pointers
Similar Problems: (H) First Missing Positive (E) Single Number (M) Linked List Cycle II (M) Missing Number

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
'''
Solution:
    The main idea is the same with problem Linked List Cycle II. Use two pointers the fast and the slow. The fast one goes forward two steps each time, while the slow one goes only step each time. They must meet the same item when slow==fast. In fact, they meet in a circle, the duplicate number must be the entry point of the circle when visiting the array from nums[0]. Next we just need to find the entry point. We use a point(we can use the fast one before) to visit form begining with one step each time, do the same job to slow. When fast==slow, they meet at the entry point of the circle.
'''
class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return -1
        fast = nums[nums[0]]
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]
        head = 0
        while head != slow:
            head = nums[head]
            slow = nums[slow]
        return slow
徐阿衡 wechat
欢迎关注：徐阿衡的微信公众号
客官，打个赏呗~