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)
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
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".'
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
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.
# 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
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.
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
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):
Write a function to compute the next state (after one update) of the board given its current state.
Follow up:
Credits: Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
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]]
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 |
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!
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:
a-f
) must be in lowercase.0
s. 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.Example 1:
Input:
26
Output:
"1a"
Example 2:
Input:
-1
Output:
"ffffffff"
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
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
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
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.
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)
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', 'a@b.com')
insert into Person (Id, Email) values ('2', 'c@d.com')
insert into Person (Id, Email) values ('3', 'a@b.com')
Write a SQL query to find all duplicate emails in a table named Person
.
+----+---------+
| Id | Email |
+----+---------+
| 1 | a@b.com |
| 2 | c@d.com |
| 3 | a@b.com |
+----+---------+
For example, your query should return the following for the above table:
+---------+
| Email |
+---------+
| a@b.com |
+---------+
Note: All emails are in lowercase.
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', 'a@b.com');''')
conn.execute('''INSERT INTO Person (Id, Email) VALUES ('2', 'c@d.com');''')
conn.execute('''INSERT INTO Person (Id, Email) VALUES ('3', 'a@b.com');''')
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 a@b.com 2 c@d.com 3 a@b.com Table updated successfully! a@b.com Closed database successfully!
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.
# 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)
# 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)])
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,3
→ 1,3,2
3,2,1
→ 1,2,3
1,1,5
→ 1,5,1
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
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 |
+------------+----------+--------+
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!
Date: 2018-2-24
Task: 232
Detail:
Implement the following operations of a queue using stacks.
Notes:
push to top
, peek/pop from top
, size
, and is empty
operations are valid.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()
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.
# 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
Date: 2018-3-20
Task: 664
Detail:
There is a strange printer with the following two special requirements:
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.
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
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
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)
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$
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: 未能独立完成!
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 i
and 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]]
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
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?
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
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.
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")