Fork me on GitHub

Posted on

Description

https://leetcode.com/problems/game-of-life/description/

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
class Solution:
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if board is None or len(board) == 0:
            return
        
        directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.transform(i, j, board, directions)
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                board[i][j] >>= 1
        
    def transform(self, x, y, board, directions):
        
        count = 0
        for direction in directions:
            if direction[0] + x >= 0 and direction[0] + x < len(board) and \
                direction[1] + y >= 0 and direction[1] + y < len(board[0]) and \
                    board[direction[0] + x][direction[1] + y] & 1 == 1:
                count += 1
        
        if (board[x][y] & 1) == 1:
            if count == 2 or count == 3:
                board[x][y] = board[x][y] + 2
        else:
            if count == 3:
                board[x][y] = board[x][y] + 2

Posted on

Description

https://leetcode.com/problems/flatten-nested-list-iterator/description/

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
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class NestedIterator {
public:
    NestedIterator(vector<NestedInteger>& nestedList) {
        this->index = 0;
        this->list = new vector<int>();
        this->parse(nestedList);
        this->length = this->list->size();
    }
    
    void parse(vector<NestedInteger>& nestedList) {
        for(int i = 0; i < nestedList.size(); i++){
            if(nestedList[i].isInteger() == true) this->list->push_back(nestedList[i].getInteger());
            else this->parse(nestedList[i].getList());
        }
    }

    int next() {
        int ret = (*this->list)[index];
        this->index += 1;
        return ret;
    }

    bool hasNext() {
        return this->index < this->length;
    }
private:
    vector<int>* list;
    int index;
    int length;
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */

Posted on

Description

https://leetcode.com/problems/trapping-rain-water/description/

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
class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_left = [0 for i in range(len(height))] 
        maximun_left = - 1
        for index in range(0, len(height) - 1):
            if height[index] > maximun_left:
                maximun_left = height[index]
            max_left[index + 1] = maximun_left
        
        max_right = [0 for i in range(len(height))]
        maximun_right = -1
        for index in range(len(height) - 1, 0, -1):
            if height[index] > maximun_right:
                maximun_right = height[index]
            max_right[index - 1] = maximun_right
           
        ##Traverse all the index
        ret = 0
        for i in range(len(height)):
            bar = min(max_left[i], max_right[i])
            if bar > height[i]:
                ret += (bar - height[i])
                
        return ret

Posted on

Description

https://leetcode.com/problems/reverse-words-in-a-string/description/

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
class Solution {
public:
    void reverseWords(string &s) {
        if (s.length() == 0) return;
        reverse(s.begin(), s.end());
        
        string::iterator iter = s.begin();
        string::iterator begin = iter;
        while (begin != s.end() ) {
            while (begin != s.end() && *begin == ' ') begin += 1;
            if(iter != s.begin() && begin != s.end()){
                *iter = ' ';
                iter += 1;
            }
            string::iterator origin = iter;
            while (begin != s.end() && *begin != ' ') {
                *iter = *begin;
                iter += 1;
                begin += 1;
            }
            reverse(origin, iter);
        }
        s.resize(iter - s.begin());
        return;
    }
};

Posted on

Description

https://leetcode.com/problems/data-stream-as-disjoint-intervals/description/

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
# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class SummaryRanges:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.interval_list = []

    def addNum(self, val):
        """
        :type val: int
        :rtype: void
        """
        index = 0
        while index < len(self.interval_list):
            if val <= self.interval_list[index].start:
                break
            index += 1  
        independ = True
        if index >= 1 and (self.interval_list[index - 1].end + 1 == val or self.interval_list[index - 1].end == val):
            self.interval_list[index - 1].end = val 
            independ = False
        if index < len(self.interval_list) and (self.interval_list[index].start == val + 1 or self.interval_list[index].start ==val):
            self.interval_list[index].start = val
            independ = False
        if index >= 1 and index < len(self.interval_list) and self.interval_list[index].start == self.interval_list[index - 1].end:
            self.interval_list[index - 1].end = self.interval_list[index].end
            del self.interval_list[index]
            index -= 1
        
        if independ == True and (index == 0 or val > self.interval_list[index - 1].end + 1):
            self.interval_list.insert(index, Interval(val, val))

    def getIntervals(self):
        """
        :rtype: List[Interval]
        """
        return self.interval_list


# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(val)
# param_2 = obj.getIntervals()

Posted on

Description

https://leetcode.com/problems/partition-list/description/

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        smaller = ListNode(-1)
        bigger = ListNode(-1)
        tra_smaller = smaller
        tra_bigger = bigger
        traverse = head
        
        while traverse != None:
            if traverse.val < x:
                tra_smaller.next = traverse
                traverse = traverse.next
                tra_smaller = tra_smaller.next
            else:
                tra_bigger.next = traverse
                traverse = traverse.next
                tra_bigger = tra_bigger.next
        tra_bigger.next = None
        tra_smaller.next = bigger.next
        return smaller.next

Posted on

Description

https://leetcode.com/problems/max-points-on-a-line/description/

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
# Definition for a point.
# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution:
    def gcd(self, target):
        if target[0] == 0 or target[1] == 0:
            return 1
        left =abs(target[1])
        right =abs(target[0])
        while right % left != 0:
            temp = left
            left = right % left
            right = temp
            
        sign = 1 if target[0] > 0 else -1
        return left * sign
        
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        if points is None or len(points) == 0:
            return 0
        if len(points) == 1:
            return 1
        
        points_gradient = [{} for i in range(len(points))]
        counter = [1 for i in range(len(points))]
        for i in range(len(points) - 1):
            for j in range(i + 1, len(points)):
                if (points[i].x == points[j].x and points[i].y == points[j].y):
                    counter[i] += 1
                    counter[j] += 1
                    continue
                
                raw_gradient = None
                if points[i].x == points[j].x:
                    raw_gradient = (1, 0)  
                elif points[i].y == points[j].y:
                    raw_gradient = (0, 1)
                else:
                    raw_gradient = ((points[i].y - points[j].y), (points[i].x - points[j].x))
                
                gradient = (raw_gradient[0] / self.gcd(raw_gradient), raw_gradient[1] / self.gcd(raw_gradient))
                
                if points_gradient[i].get(gradient) is None:
                    points_gradient[i][gradient] = 1
                else:
                    points_gradient[i][gradient] += 1
                if points_gradient[j].get(gradient) is None:
                    points_gradient[j][gradient] = 1
                else:
                    points_gradient[j][gradient] += 1
                    
        ret = -1
        print(points_gradient)
        for (index, item) in enumerate(points_gradient):
            ret = max(ret, (max(item.values()) if item else 0) + counter[index])
            
        return ret

Posted on

Description

https://leetcode.com/problems/minimum-window-substring/description/

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
class Solution:
    def Valid(self, dic):
        for item in dic.values():
            if item > 0:
                return False
        
        return True
        
        
    
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        
        counter_t = {}
        for ch in t:
            if not counter_t.get(ch):
                counter_t[ch] = 1
            else:
                counter_t[ch] += 1
        counter_s = {}
        for index in range(len(s)):
            if not counter_s.get(s[index]):
                counter_s[s[index]] = [[index], 0]
            else:
                counter_s[s[index]][0].append(index)
        
        start = 0
        while start < len(s):
            if counter_t.get(s[start]) is None:
                start += 1
                continue
            if counter_t.get(s[start]) >= 0:
                break
            counter_t[s[start]] -= 1
            start += 1
        print(counter_t)
                
                
        end = start 
        while end < len(s):
            if counter_t.get(s[end]) is not None:
                counter_t[ s[end] ] -= 1
                
            if not self.Valid(counter_t):
                end += 1
            else:
                break
        
        if not self.Valid(counter_t):
            return ""
        minum_start = start
        minum_end = end
        minum = end - start
        
        while start <= end:
            while start <= end:
                if counter_t.get(s[start]) is None:
                    start += 1
                    continue
                    
                if counter_t.get(s[start]) >= 0:
                    break
                    
                counter_t[ s[start] ] += 1
                start += 1
            if end - start < minum:
                minum_start = start
                minum_end = end
                minum = end - start
                print(start, end, counter_t)
            
            result_list = counter_s.get(s[start])
            next_end = None
            for index in range(result_list[1], len(result_list[0])):
                if result_list[0][index] > end:
                    next_end = result_list[0][index]
                    result_list[1] = index + 1
                    break
            
            if next_end is None:
                break
            
            for index in range(end + 1, next_end + 1):
                if counter_t.get(s[index]) is not None:
                    counter_t[s[index]] -= 1      
            end = next_end
            
        return s[minum_start: minum_end + 1]

Posted on

Description

https://leetcode.com/problems/unique-paths-ii/description/

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
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if obstacleGrid is None or len(obstacleGrid) == 0:
            return 0
        
        ret = [ [0 for i in range(len(obstacleGrid[0]))] for j in range(len(obstacleGrid)) ]
        
        for i in range(len(obstacleGrid[0])):
            if obstacleGrid[0][i] == 0:
                ret[0][i] = 1
            else:
                break
            
        for j in range(len(obstacleGrid)):
            if obstacleGrid[j][0] == 0:
                ret[j][0] = 1
            else:
                break
        
        for i in range(1, len(obstacleGrid)):
            for j in range(1, len(obstacleGrid[0])):
                if obstacleGrid[i][j] == 0:
                    left  = (0 if obstacleGrid[i][j - 1] == 1 else ret[i][j - 1])     
                    up = (0 if obstacleGrid[i - 1][j] == 1 else ret[i - 1][j])
                    ret[i][j] = left + up
        
        return ret[-1][-1]

Posted on

Description

https://leetcode.com/problems/first-missing-positive/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums is None or len(nums) == 0:
            return 1
        
        for i in range(len(nums)):
            while nums[i] != i + 1 and nums[i] <= len(nums) and nums[i] > 0 and nums[nums[i] - 1] != nums[i]:
                temp = nums[i]
                nums[i] = nums[temp - 1]
                nums[temp - 1] = temp
                print (nums)
        
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
            
        return len(nums) + 1