History

Bomb Enemy

Date: 2017-10-30

Task: 361

Detail:

Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.
 The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
 Note that you can only put the bomb at an empty cell.
 Example:
 For the given grid
  0 E 0 0
  E 0 W E
  0 E 0 0
return 3. (Placing a bomb at (1,1) kills 3 enemies)
In [1]:
def bomb_enemy(cells):
    print(cells)
    row_len, col_len = len(cells), len(cells[0])
    print(row_len, col_len)
    result = 0
    col_hits = [0] * col_len
    row_hits = 0
    print(col_hits)
    for index_row, row in enumerate(cells):
        print(index_row, row)
        for index_cell, cell in enumerate(row):
            print(index_cell, cell)
            if index_cell == 0 or row[index_cell - 1] == 'W':
                row_hits = 0
                k = index_cell
                while k < col_len:
                    if row[k] == 'W':
                        break
                    row_hits += row[k] == 'E'
                    k += 1
            if index_row == 0 or cells[index_row - 1][index_cell] == 'W':
                col_hits[index_cell] = 0
                k = index_row
                while k < row_len:
                    if cells[k][index_cell] == 'W':
                        break
                    col_hits[index_cell] += cells[k][index_cell] == 'E'
                    k += 1
            if cell == '0':
                result = max(result, row_hits + col_hits[index_cell])
    return result


print(bomb_enemy([['0', 'E', '0', '0'],
                  ['E', '0', 'W', 'E'],
                  ['0', 'E', '0', '0']]))

print(bomb_enemy([['0', 'W', 'E', 'W'],
                  ['W', 'W', '0', 'W'],
                  ['0', 'W', 'E', 'W']]))
[['0', 'E', '0', '0'], ['E', '0', 'W', 'E'], ['0', 'E', '0', '0']]
3 4
[0, 0, 0, 0]
0 ['0', 'E', '0', '0']
0 0
1 E
2 0
3 0
1 ['E', '0', 'W', 'E']
0 E
1 0
2 W
3 E
2 ['0', 'E', '0', '0']
0 0
1 E
2 0
3 0
3
[['0', 'W', 'E', 'W'], ['W', 'W', '0', 'W'], ['0', 'W', 'E', 'W']]
3 4
[0, 0, 0, 0]
0 ['0', 'W', 'E', 'W']
0 0
1 W
2 E
3 W
1 ['W', 'W', '0', 'W']
0 W
1 W
2 0
3 W
2 ['0', 'W', 'E', 'W']
0 0
1 W
2 E
3 W
2

Ones and Zeroes

Date: 2017-11-6

Task: 474

Detail:

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

Note:
  1. The given numbers of 0s and 1s will both not exceed 100
  2. The size of given string array won't exceed 600.'

Example 1:
  Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
  Output: 4

  Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10”,“0001”,“1”,“0”


Example 2:
  Input: Array = {"10", "0", "1"}, m = 1, n = 1
  Output: 2

  Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".'
In [2]:
def find_max_form(strs, m, n):
    """
    :type strs: List[str]
    :type m: int
    :type n: int
    :rtype: int
    """
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for s in strs:
        zero_count, one_count = s.count('0'), s.count('1')
        for x in range(m, zero_count - 1, -1):
            for y in range(n, one_count - 1, -1):
                dp[x][y] = max(dp[x - zero_count][y - one_count] + 1, dp[x][y])
    return dp[m][n]


print(find_max_form(["10", "0001", "111001", "1", "0"], 5, 3))

print(find_max_form(["10", "0", "1"], 1, 1))

print(find_max_form(
    ["11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01",
     "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01",
     "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01",
     "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01",
     "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01",
     "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01",
     "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01",
     "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01",
     "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01",
     "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01",
     "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01",
     "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01",
     "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01",
     "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11",
     "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01", "11", "01"], 50, 50))
4
2
50

Serialize and Deserialize Binary Tree

Date: 2017-11-13

Task: 297

Detail:

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

  Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

  For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note:
  Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Credits:
  Special thanks to [@Louis1992](https://leetcode.com/discuss/user/Louis1992) for adding this problem and creating all test cases.
In [3]:
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Codec:
    @staticmethod
    def serialize(root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """

        def build(node):
            if node:
                nodes.append(str(node.val))
                build(node.left)
                build(node.right)
            else:
                nodes.append('#')

        nodes = []
        build(root)
        return ' '.join(nodes)

    @staticmethod
    def deserialize(data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """

        def parse():
            _node = next(nodes)
            if _node == '#':
                return None
            node = TreeNode(int(_node))
            node.left = parse()
            node.right = parse()
            return node

        nodes = iter(data.split())
        return parse()

        # Your Codec object will be instantiated and called as such:
        # codec = Codec()
        # codec.deserialize(codec.serialize(root))


t11 = TreeNode(1)
t21 = TreeNode(2)
t22 = TreeNode(3)
t33 = TreeNode(4)
t34 = TreeNode(5)
t21.left = None
t21.right = None
t22.left = t33
t22.right = t34
t11.left = t21
t11.right = t22

s = Codec.serialize(t11)
ds = Codec.deserialize(s)
print(s, ds, s == Codec.serialize(ds))
1 2 # # 3 4 # # 5 # # <__main__.TreeNode object at 0x0000000005839A90> True

Partition to K Equal Sum Subsets

Date: 2017-11-20

Task: 698

Detail:

 Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4

Output: True

 Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums. Note:

1 <= k <= len(nums) <= 16.
0 < nums[i] < 10000.
In [4]:
class Solution(object):
    @staticmethod
    def can_partition_k_subsets(nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        if k < 1:
            return False
        sum_nums = sum(nums)
        if sum_nums % k != 0:
            return False

        def partition(_nums, used_nums, start, _k, current_sum, current_index, aim_sum):
            if _k == 1:
                return True
            if current_sum == aim_sum:
                return partition(_nums, used_nums, 0, _k - 1, 0, 0, aim_sum)
            for i in range(start, len(_nums), 1):
                if used_nums[i] is None:
                    used_nums[i] = 1
                    current_index += 1
                    if partition(_nums, used_nums, i + 1, _k, current_sum + _nums[i], current_index, aim_sum):
                        return True
                    used_nums[i] = None
            return False

        tmp_nums = [None] * len(nums)
        return partition(nums, tmp_nums, 0, k, 0, 0, sum_nums / k)


print(Solution.can_partition_k_subsets([1], 1))
print(Solution.can_partition_k_subsets([1, 2], 1))
print(Solution.can_partition_k_subsets([1, 2], 2))
print(Solution.can_partition_k_subsets([1, 2], 3))
print(Solution.can_partition_k_subsets([2, 2], 2))
print(Solution.can_partition_k_subsets([1, 1, 2], 2))
print(Solution.can_partition_k_subsets([1, 1, 1, 1], 2))
print(Solution.can_partition_k_subsets([4, 3, 2, 3, 5, 2, 1], 4))
True
True
False
False
True
True
True
True

Game of Life

Date: 2017-11-27

Task: 289

Detail:

 According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

 Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

  1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population..
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

 Write a function to compute the next state (after one update) of the board given its current state.

Follow up:

  1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
  2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

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

In [5]:
def game_of_life(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
    m = len(board)
    n = len(board[0])

    for i in range(0, m):
        for j in range(0, n):
            lives = live_neighbors(board, m, n, i, j)
            if board[i][j] == 1 and 2 <= lives <= 3:
                board[i][j] = 3
            if board[i][j] == 0 and lives == 3:
                board[i][j] = 2
    for i in range(0, m):
        for j in range(0, n):
            board[i][j] >>= 1


def live_neighbors(board, m, n, i, j):
    lives = 0
    for x in range(max(i - 1, 0), min(i + 1, m - 1) + 1):
        for y in range(max(j - 1, 0), min(j + 1, n - 1) + 1):
            lives += board[x][y] & 1
    lives -= board[i][j] & 1
    return lives


test_board = [[]]
game_of_life(test_board)
print(test_board)

test_board = [[1, 1], [1, 0]]
game_of_life(test_board)
print(test_board)

test_board = [[1, 0], [0, 0]]
game_of_life(test_board)
print(test_board)

test_board = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
game_of_life(test_board)
print(test_board)
[[]]
[[1, 1], [1, 1]]
[[0, 0], [0, 0]]
[[1, 0, 1], [0, 0, 0], [1, 0, 1]]

Swap Salary

Date: 2017-12-4

Task: 627

Detail:

SQL Schema

create table if not exists salary(id int, name varchar(100), sex char(1), salary int);
Truncate table salary;
insert into salary (id, name, sex, salary) values ('1', 'A', 'm', '2500');
insert into salary (id, name, sex, salary) values ('2', 'B', 'f', '1500');
insert into salary (id, name, sex, salary) values ('3', 'C', 'm', '5500');
insert into salary (id, name, sex, salary) values ('4', 'D', 'f', '500');

Given a table salary, such as the one below, that has m=male and f=female values. Swap all f and m values (i.e., change all f values to m and vice versa) with a single update query and no intermediate temp table.

| id | name | sex | salary |
|----|------|-----|--------|
| 1  | A    | m   | 2500   |
| 2  | B    | f   | 1500   |
| 3  | C    | m   | 5500   |
| 4  | D    | f   | 500    |

| id | name | sex | salary |
|----|------|-----|--------|
| 1  | A    | f   | 2500   |
| 2  | B    | m   | 1500   |
| 3  | C    | f   | 5500   |
| 4  | D    | m   | 500    |
In [6]:
import sqlite3

conn = sqlite3.connect('salary.db')
print("Opened database successfully!")
try:
    conn.execute('''CREATE TABLE IF NOT EXISTS salary(id INT, name VARCHAR(100), sex char(1), salary INT);''')
    conn.execute('''DELETE FROM salary;''')
    conn.execute('''INSERT INTO salary (id, name, sex, salary) VALUES ('1', 'A', 'm', '2500');''')
    conn.execute('''INSERT INTO salary (id, name, sex, salary) VALUES ('2', 'B', 'f', '1500');''')
    conn.execute('''INSERT INTO salary (id, name, sex, salary) VALUES ('3', 'C', 'm', '5500');''')
    conn.execute('''INSERT INTO salary (id, name, sex, salary) VALUES ('4', 'D', 'f', '500');''')
    salaries = conn.execute('''SELECT * FROM salary;''')
    for salary in salaries:
        print(salary[0], salary[1], salary[2], salary[3])
    print("Table updated successfully!")
    conn.execute('''UPDATE salary SET sex  = CASE
                    WHEN sex = 'm' THEN 'f'
                    WHEN sex = 'f' THEN 'm'
                    END
    WHERE sex IN ('f', 'm');''')
    salaries = conn.execute('''SELECT * FROM salary;''')
    for salary in salaries:
        print(salary[0], salary[1], salary[2], salary[3])
finally:
    conn.close()
    print("Closed database successfully!")
Opened database successfully!
1 A m 2500
2 B f 1500
3 C m 5500
4 D f 500
Table updated successfully!
1 A f 2500
2 B m 1500
3 C f 5500
4 D m 500
Closed database successfully!

Swap Salary

Date: 2017-12-11

Task: 405

Detail:

 Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

  1. All letters in hexadecimal (a-f) must be in lowercase.
  2. The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character '0'; otherwise, the first character in the hexadecimal string will not be the zero character.
  3. The given number is guaranteed to fit within the range of a 32-bit signed integer.
  4. You must not use any method provided by the library which converts/formats the number to hex directly.

Example 1:

Input:
26

Output:
"1a"

Example 2:

Input:
-1

Output:
"ffffffff"
In [7]:
ALL_CHARS = '0123456789abcdef'


def toHex(num):
    """
    :type num: int
    :rtype: str
    """
    return ''.join(ALL_CHARS[(num >> 4 * i) & 15] for i in range(7, -1, -1)).lstrip('0') or '0'


print(toHex(26))
print(toHex(16))
print(toHex(0))
print(toHex(-1))
print(toHex(-2))
print(toHex(-16))
1a
10
0
ffffffff
fffffffe
fffffff0

Search Insert Position

Date: 2017-12-18

Task: 35

Detail:

 Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

 You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

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

Example 1:

Input: [1,3,5,6], 0
Output: 0
In [8]:
def searchInsert(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    return len([i for i in nums if i < target])

print(searchInsert([1, 3, 5, 6], 5))
print(searchInsert([1, 3, 5, 6], 2))
print(searchInsert([1, 3, 5, 6], 7))
print(searchInsert([1, 3, 5, 6], 0))
2
1
4
0

Search in Rotated Sorted Array

Date: 2017-12-27

Task: 33

Detail:

 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

 (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

 You are given a target value to search. If found in the array return its index, otherwise return -1.

 You may assume no duplicate exists in the array.

In [9]:
def search(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    low, high = 0, len(nums) - 1
    while low < high:
        mid = int((low + high) / 2)
        if (nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]):
            low = mid + 1
        else:
            high = mid
    return low if target in nums[low:low + 1] else -1


assert -1 == search([], 1)
assert -1 == search([4, 5, 6, 7, 0, 1, 2], 8)
assert 5 == search([4, 5, 6, 7, 0, 1, 2], 1)
assert 1 == search([4, 5, 6, 7, 0, 1, 2], 5)

Duplicate Emails

Date: 2018-1-3

Task: 182

Detail:

SQL Schema

Create table If Not Exists Person (Id int, Email varchar(255))
Truncate table Person
insert into Person (Id, Email) values ('1', '[email protected]')
insert into Person (Id, Email) values ('2', '[email protected]')
insert into Person (Id, Email) values ('3', '[email protected]')

Write a SQL query to find all duplicate emails in a table named Person.

+----+---------+
| Id | Email   |
+----+---------+
| 1  | [email protected] |
| 2  | [email protected] |
| 3  | [email protected] |
+----+---------+

For example, your query should return the following for the above table:

+---------+
| Email   |
+---------+
| [email protected] |
+---------+

Note: All emails are in lowercase.

In [10]:
import sqlite3

conn = sqlite3.connect('duplicate_emails.db')
try:
    print("Opened database successfully!")
    conn.execute('''CREATE TABLE IF NOT EXISTS Person (Id INT, Email VARCHAR(255));''')
    conn.execute('''DELETE FROM Person;''')
    conn.execute('''INSERT INTO Person (Id, Email) VALUES ('1', '[email protected]');''')
    conn.execute('''INSERT INTO Person (Id, Email) VALUES ('2', '[email protected]');''')
    conn.execute('''INSERT INTO Person (Id, Email) VALUES ('3', '[email protected]');''')
    emails = conn.execute('''SELECT * FROM Person;''')
    for email in emails:
        print(email[0], email[1])
    print("Table updated successfully!")
    emails = conn.execute('''SELECT Email FROM Person GROUP BY Email HAVING count(*) > 1;''')
    for email in emails:
        print(email[0])
finally:
    conn.close()
    print("Closed database successfully!")
Opened database successfully!
1 [email protected]
2 [email protected]
3 [email protected]
Table updated successfully!
[email protected]
Closed database successfully!

Second Minimum Node In a Binary Tree

Date: 2018-1-10

Task: 671

Detail:

 Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes.

 Given such a binary tree, you need to output the second minimum value in the set made of all the nodes' value in the whole tree.

 If no such second minimum value exists, output -1 instead.

Example 1:

Input: 
    2
   / \
  2   5
     / \
    5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

Input: 
    2
   / \
  2   2

Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.
In [11]:
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def findSecondMinimumValue(root):
    """
    :type root: TreeNode
    :rtype: int
    """
    sec_min = internal(root, root, [float('inf')])
    return -1 if sec_min[0] == float('inf') else sec_min[0]


def internal(root, node, holder):
    if not node:
        return holder
    if root.val < node.val < holder[0]:
        holder[0] = node.val
    internal(root, node.left, holder)
    internal(root, node.right, holder)
    return holder


t0 = TreeNode(0)
t10 = TreeNode(1)
t11 = TreeNode(2)
t20 = TreeNode(10)
t22 = TreeNode(8)
t23 = TreeNode(4)
t0.left = t10
t0.right = t11
t10.left = t20
t11.left = t22
t11.right = t23

assert 1 == findSecondMinimumValue(t0)

Max Points on a Line

Date: 2018-1-17

Task: 149

Detail:

 Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

In [12]:
# Definition for a point.
class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b


def maxPoints(points):
    """
    :type points: List[Point]
    :rtype: int
    """
    points_len = len(points)
    if points is None or points_len == 0:
        return 0
    if points_len == 1:
        return 1
    max_count = 0
    if points_len > 1:
        max_count = 2
    for point_left in points:
        x_left = point_left.x
        y_left = point_left.y
        map_count = {}
        duplicate = 1
        for point_right in filter(lambda p: p != point_left, points):
            x_right = point_right.x
            y_right = point_right.y
            if x_left == x_right and y_left == y_right:
                duplicate += 1
            else:
                dx = x_right - x_left
                dy = y_right - y_left
                gcd = greatest_common_divisor(dx, dy)
                dx_gcd = dx / gcd
                dy_gcd = dy / gcd
                if dx_gcd in map_count:
                    if dy_gcd in map_count[dx_gcd]:
                        map_count[dx_gcd][dy_gcd] = map_count[dx_gcd][dy_gcd] + 1
                else:
                    map_count[dx_gcd] = {dy_gcd: 1}
        max_count = max(max_count, duplicate)
        for map_count_value in map_count.values():
            for map_count_internal_value in map_count_value.values():
                max_count = max(max_count, map_count_internal_value + duplicate)
    return max_count


def greatest_common_divisor(a, b):
    return a if b == 0 else greatest_common_divisor(b, a % b)


p0 = Point(0, 1)
p00 = Point(0, 0)
p10 = Point(1, 0)
p1_1 = Point(1, -1)
p1 = Point(1, 1)
p2 = Point(2, 2)
p3 = Point(3, 3)
p4 = Point(1, 2)
p5 = Point(2, 4)
p6 = Point(1, 3)

assert 0 == maxPoints([])
assert 1 == maxPoints([p0])
assert 2 == maxPoints([p0, p00])
assert 2 == maxPoints([p00, p10])
assert 2 == maxPoints([p00, p1_1, p1])
assert 2 == maxPoints([p3, p5, p6])
assert 2 == maxPoints([p3, p4, p5, p6])
assert 3 == maxPoints([p1, p2, p3, p4, p5, p6])
assert 2 == maxPoints([Point(0, 0), Point(94911151, 94911150), Point(94911152, 94911151)])
assert 3 == maxPoints([Point(0, 0), Point(-1, -1), Point(2, 2)])

Next Permutation

Date: 2018-1-31

Task: 31

Detail:

 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

 If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

 The replacement must be in-place, do not allocate extra memory.

 Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

  1,2,31,3,2   3,2,11,2,3   1,1,51,5,1

In [13]:
def frequencySort(s):
    """
    :type s: str
    :rtype: str
    """
    char_frequency_count = {}
    for c in s:
        if c in char_frequency_count:
            char_frequency_count[c] = char_frequency_count[c] + 1
        else:
            char_frequency_count[c] = 1
    result = ""
    for cc in sorted(char_frequency_count.items(), key=lambda item: item[1], reverse=True):
        count = 0
        while count < cc[1]:
            count += 1
            result += cc[0]
    return result


sort = frequencySort("tree")
assert "eert" == sort or "eetr" == sort
sort = frequencySort("cccaaa")
assert "aaaccc" == sort or "cccaaa" == sort
sort = frequencySort("Aabb")
assert "bbAa" == sort or "bbaA" == sort

Department Highest Salary

Date: 2018-2-11

Task: 184

Detail:

 SQL Schema

Create table If Not Exists Employee (Id int, Name varchar(255), Salary int, DepartmentId int)
Create table If Not Exists Department (Id int, Name varchar(255))
Truncate table Employee
insert into Employee (Id, Name, Salary, DepartmentId) values ('1', 'Joe', '70000', '1')
insert into Employee (Id, Name, Salary, DepartmentId) values ('2', 'Henry', '80000', '2')
insert into Employee (Id, Name, Salary, DepartmentId) values ('3', 'Sam', '60000', '2')
insert into Employee (Id, Name, Salary, DepartmentId) values ('4', 'Max', '90000', '1')
Truncate table Department
insert into Department (Id, Name) values ('1', 'IT')
insert into Department (Id, Name) values ('2', 'Sales')

 The Employee table holds all employees. Every employee has an Id, a salary, and there is also a column for the department Id.

+----+-------+--------+--------------+
| Id | Name  | Salary | DepartmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Henry | 80000  | 2            |
| 3  | Sam   | 60000  | 2            |
| 4  | Max   | 90000  | 1            |
+----+-------+--------+--------------+

 The Department table holds all departments of the company.

+----+----------+
| Id | Name     |
+----+----------+
| 1  | IT       |
| 2  | Sales    |
+----+----------+

 Write a SQL query to find employees who have the highest salary in each of the departments. For the above tables, Max has the highest salary in the IT department and Henry has the highest salary in the Sales department.

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| Sales      | Henry    | 80000  |
+------------+----------+--------+
In [14]:
import sqlite3

conn = sqlite3.connect('department_highest_salary.db')
try:
    print("Opened database successfully!")
    conn.execute('''CREATE TABLE IF NOT EXISTS Employee (Id INT, Name VARCHAR(255), Salary INT, DepartmentId INT);''')
    conn.execute('''CREATE TABLE IF NOT EXISTS Department (Id INT, Name VARCHAR(255));''')
    conn.execute('''DELETE FROM Employee;''')
    conn.execute('''INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES ('1', 'Joe', '70000', '1');''')
    conn.execute('''INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES ('2', 'Henry', '80000', '2');''')
    conn.execute('''INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES ('3', 'Sam', '60000', '2');''')
    conn.execute('''INSERT INTO Employee (Id, Name, Salary, DepartmentId) VALUES ('4', 'Max', '90000', '1');''')
    conn.execute('''DELETE FROM Department;''')
    conn.execute('''INSERT INTO Department (Id, Name) VALUES ('1', 'IT');''')
    conn.execute('''INSERT INTO Department (Id, Name) VALUES ('2', 'Sales');''')
    ee = conn.execute(
        '''SELECT d.Name AS Department, e.Name AS Employee, e.Salary
           FROM Department AS d, Employee AS e, 
           (SELECT DepartmentId, Name, max(Salary) AS highest FROM Employee GROUP BY DepartmentId) AS h
           WHERE e.Salary = h.highest AND e.DepartmentId = h.DepartmentId AND e.DepartmentId = d.Id;''')
    for e in ee:
        print(e[0], e[1], e[2])
finally:
    conn.close()
    print("Closed database successfully!")
Opened database successfully!
IT Max 90000
Sales Henry 80000
Closed database successfully!

Implement Queue using Stacks

Date: 2018-2-24

Task: 232

Detail:

Implement the following operations of a queue using stacks.

  • push(x) -- Push element x to the back of queue.
  • pop() -- Removes the element from in front of queue.
  • peek() -- Get the front element.
  • empty() -- Return whether the queue is empty.

Notes:

  • You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is emptyoperations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
In [15]:
class MyQueue:

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

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: void
        """
        self.in_stack.append(x)

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        if not self.out_stack:
            in_stack_len = len(self.in_stack)
            count = 0
            while self.in_stack:
                count += 1
                if count == in_stack_len:
                    return self.in_stack.pop()
                self.out_stack.append(self.in_stack.pop())
        result = self.out_stack[-1]
        self.out_stack = self.out_stack[:-1]
        return result

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        result = None
        if not self.out_stack:
            count = 0
            while self.in_stack:
                count += 1
                result = self.in_stack.pop()
                self.out_stack.append(result)
        else:
            result = self.out_stack[-1]
        return result

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return len(self.in_stack) == 0 and len(self.out_stack) == 0


# Your MyQueue object will be instantiated and called as such:
queue = MyQueue()
queue.push(1)
assert 1 == queue.pop()
assert queue.empty()
queue.push(2)
assert 2 == queue.peek()
assert not queue.empty()
queue.push(3)
assert 2 == queue.peek()
assert not queue.empty()

queue = MyQueue()
queue.push(1)
queue.push(2)
assert 1 == queue.peek()

queue = MyQueue()
queue.push(1)
queue.push(2)
assert 1 == queue.peek()
assert 1 == queue.pop()
assert not queue.empty()

queue = MyQueue()
queue.push(1)
queue.push(2)
assert 1 == queue.peek()
assert 1 == queue.pop()
assert 2 == queue.pop()
assert queue.empty()

Serialize and Deserialize BST

Date: 2018-3-5

Task: 449

Detail:

 Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

 Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

 The encoded string should be as compact as possible.

 Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

In [16]:
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """

        def build(node):
            if node:
                nodes.append(str(node.val))
                build(node.left)
                build(node.right)
            else:
                nodes.append('#')

        nodes = []
        build(root)
        return ' '.join(nodes)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """

        def parse():
            _node = next(nodes)
            if _node == '#':
                return None
            node = TreeNode(int(_node))
            node.left = parse()
            node.right = parse()
            return node

        nodes = iter(data.split())
        return parse()


# Your Codec object will be instantiated and called as such:
t11 = TreeNode(1)
t21 = TreeNode(2)
t22 = TreeNode(3)
t33 = TreeNode(4)
t34 = TreeNode(5)
t21.left = None
t21.right = None
t22.left = t33
t22.right = t34
t11.left = t21
t11.right = t22

codec = Codec()
s = codec.serialize(t11)
ds = codec.deserialize(s)
# 1 2 # # 3 4 # # 5 # # <__main__.TreeNode object at 0x0000000000D35320> True
print(s, ds, s == codec.serialize(ds))
1 2 # # 3 4 # # 5 # # <__main__.TreeNode object at 0x00000000058939E8> True

Strange Printer

Date: 2018-3-20

Task: 664

Detail:

There is a strange printer with the following two special requirements:

  1. The printer can only print a sequence of the same character each time.
  2. At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.

Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

Example 1:

Input: "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".

Example 2:

Input: "aba"
Output: 2
Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.

Hint: Length of the given string will not exceed 100.

In [17]:
class Solution:
    @staticmethod
    def strangePrinter(s):
        """
        :type s: str
        :rtype: int
        """
        cache = {}

        def dp(i, j):
            if i > j:
                return 0
            if (i, j) not in cache:
                result = dp(i + 1, j) + 1
                for k in range(i + 1, j + 1):
                    if s[k] == s[i]:
                        result = min(result, dp(i, k - 1) + dp(k + 1, j))
                cache[i, j] = result
            return cache[i, j]

        return dp(0, len(s) - 1)


assert Solution.strangePrinter("aaa") == 1
assert Solution.strangePrinter("aba") == 2
assert Solution.strangePrinter("abc") == 3

Elimination Game

Date: 2018-3-27

Task: 390

Detail:

 There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

 Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

 We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

 Find the last number that remains starting with a list of length n.

Example:

Input:
  n = 9,
  1 2 3 4 5 6 7 8 9
  2 4 6 8
  2 6
  6

Output:
  6
In [18]:
class Solution:
    @staticmethod
    def lastRemaining(n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return 1
        step = 1
        ahead = 1
        forward = True
        while n > 1:
            if forward or n % 2 == 1:
                ahead = ahead + step
            n = n / 2
            step = step * 2
            forward = not forward
        return ahead


assert 1 == Solution.lastRemaining(1)
assert 1 == Solution.lastRemaining(2)
assert 2 == Solution.lastRemaining(3)
assert 6 == Solution.lastRemaining(9)

Non-negative Integers without Consecutive Ones

Date: 2018-4-3

Task: 600

Detail:

 Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.

Example 1:

Input: 5
Output: 5
Explanation: 
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.

Note: $1 \lt= n \lt= 10^9$

In [19]:
class Solution:
    @staticmethod
    def findIntegers(num):
        """
        :type num: int
        :rtype: int
        """
        # A[0] is the lowest bit, A[-1] is the highest bit
        A = bin(num)[2:][::-1]
        # dp[i][0] is the number of integers with (i+1) bits, highest bit is 0 and without consecutive ones
        # dp[i][1] is the number of integers with (i+1) bits, highest bit is 1 and without consecutive ones
        dp = [[1, 1] for _ in range(len(A))]
        # res is the number of integers less than A[:i] without consecutive ones.
        res = 1 if A[0] == '0' else 2
        for i in range(1, len(A)):
            dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
            dp[i][1] = dp[i - 1][0]
            # try to get the number of integers less than A[:i+1]
            if A[i - 1:i + 1] == '01':
                # if A[i-1:i+1]=='01', we can append '1' after integers less than A[:i] without consecutive ones,
                # also any integer with (i+1) bits, highest bit is '0', without consecutive ones
                # is less than A[:i+1]
                res += dp[i][0]
            elif A[i - 1:i + 1] == '11':
                # if A[i-1:i+1]=='11', then any integer with i+1 bits and without consecutive ones
                # is less than A[:i+1]
                res = dp[i][0] + dp[i][1]
            # if A[i]=='0', the number of integers  with i+1 bits, less than A[:i+1]  and without
            # consecutive ones is the same as A[:i]
        return res


assert 5 == Solution.findIntegers(5)
# Tips: 未能独立完成!

Number of Boomerangs

Date: 2018-4-24

Task: 447

Detail:

 Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between iand j equals the distance between i and k (the order of the tuple matters).

 Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:
 [[0,0],[1,0],[2,0]]

Output:
 2

Explanation:
 The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]
In [20]:
def numberOfBoomerangs(points):
    """
    :type points: List[List[int]]
    :rtype: int
    """
    count = 0
    for point in points:
        boomerangs = {}
        for point_ in points:
            x = point[0] - point_[0]
            y = point[1] - point_[1]
            boomerangs[x * x + y * y] = boomerangs.get(x * x + y * y, 0) + 1
        for boom in boomerangs:
            count += boomerangs[boom] * (boomerangs[boom] - 1)
    return count


num = numberOfBoomerangs([[0, 0], [1, 0], [2, 0]])
assert 2 == num

Circular Array Loop

Date: 2018-5-7

Task: 457

Detail:

 You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it's negative (-n), move backward n steps. Assume the first element of the array is forward next to the last element, and the last element is backward next to the first element. Determine if there is a loop in this array. A loop starts and ends at a particular index with more than 1 element along the loop. The loop must be"forward"or"backward'.

Example 1: Given the array [2, -1, 1, 2, 2], there is a loop, from index 0 -> 2 -> 3 -> 0.

Example 2: Given the array [-1, 2], there is no loop.

Note: The given array is guaranteed to contain no element "0".

 Can you do it in $O(n)$ time complexity and $O(1)$ space complexity?

In [21]:
def circularArrayLoop(nums):
    """
    :type nums: List[int]
    :rtype: bool
    """
    records = {}
    len_nums = len(nums)
    visited = [False for _ in range(0, len_nums, 1)]
    for i in range(0, len_nums):
        if visited[i]:
            continue
        now = i
        while True:
            visited[now] = True
            next_ = (now + nums[now]) % len_nums
            if next_ < 0:
                next_ += len_nums
            if next_ == now or nums[next_] * nums[now] < 0:
                break
            if next_ in records.keys():
                return True
            records[now] = next_
            now = next_
    return False


is_loop = circularArrayLoop([2, -1, 1, 2, 2])
assert is_loop is True
is_loop = circularArrayLoop([-1, 2])
assert is_loop is False

Stickers to Spell Word

Date: 2018-6-4

Task: 691

Detail:

 We are given N different types of stickers. Each sticker has a lowercase English word on it.

 You would like to spell out the given target string by cutting individual letters from your collection of stickers and rearranging them.

 You can use each sticker more than once if you want, and you have infinite quantities of each sticker.

 What is the minimum number of stickers that you need to spell out the target? If the task is impossible, return -1.

Example 1:

Input:

["with", "example", "science"], "thehat"

Output:

3

Explanation:

We can use 2 "with" stickers, and 1 "example" sticker.
After cutting and rearrange the letters of those stickers, we can form the target "thehat".
 Also, this is the minimum number of stickers necessary to form the target string.

Example 2:

Input:

["notice", "possible"], "basicbasic"

Output:

-1

Explanation:

We can't form the target "basicbasic" from cutting letters from the given stickers.

Note:

 stickers has length in the range [1, 50].

 stickers consists of lowercase English words (without apostrophes).

 target has length in the range [1, 15], and consists of lowercase English letters.

 In all test cases, all words were chosen randomly from the 1000 most common US English words, and the target was chosen as a concatenation of two random words.

 The time limit may be more challenging than usual. It is expected that a 50 sticker test case can be solved within 35ms on average.

In [22]:
import sys


def minStickers(stickers, target):
    """
    :type stickers: List[str]
    :type target: str
    :rtype: int
    """
    len_target = len(target)
    m = 1 << len_target
    dp = [sys.maxsize for _ in range(0, m)]
    dp[0] = 0
    for i in range(0, m):
        if dp[i] == sys.maxsize:
            continue
        for sticker in stickers:
            current = i
            for sticker_char in sticker:
                for n in range(0, len_target):
                    if target[n] == sticker_char and not ((current >> n) & 1):
                        current |= 1 << n
                        break
            dp[current] = min(dp[current], dp[i] + 1)
    return -1 if dp[m - 1] == sys.maxsize else dp[m - 1]


assert 3 == minStickers(["with", "example", "science"], "thehat")
assert -1 == minStickers(["notice", "possible"], "basicbasic")