我今天是打算去维妈买螃蟹的。
因为昨天自行车放在学校没有骑回家，所以今天是坐电车去学校的。上车的时候，算了一下边际成本，愉快的刷了卡。
到了州立图书馆之后，本来是说要去吃DonDon的，但是想到学校旁边的Don Tojo就突然想吃点别的了。于是找了一家网红店吃了一份鳗鱼饭。
吃完饭，捋了捋自己狂放不羁的头发，顺道去了一趟理发店。理完发，神清气爽的去了维妈。
发现没开门。
之后回学校坐定开始学校，打算随手水道题，于是瞄了一眼问题列表，选了Trie Tree。
以前写Trie都是要写好久的，但是这次居然五分钟不到就一次性Bug Free了，蛮开心的。
↓Code inside ↓
Continue readingGiven a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.
Example:
Input: nums =[0, 1, 3, 50, 75], lower = 0 and upper = 99, Output:["2", "4->49", "51->74", "76->99"]
class Solution:
def findMissingRanges(self, nums, lower: int, upper: int):
nums.insert(0, lower-1) # Left Bound
nums.append(upper+1) # Right Bound
res = []
for i in range(len(nums)-1):
left, right = nums[i], nums[i + 1]
if left != right:
if right - left == 2:
res.append(str(left+1))
elif right - left > 2:
res.append(str(left+1) + "->" + str(right-1))
return res
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
nums = set(nums)
ans = 0
for x in nums:
# Find the first element in one segment
if x-1 not in nums:
y = x + 1
# reach the last consecutive element in one element
while y in nums:
y += 1
ans = max(ans, y - x)
return ans
class Solution:
def longestConsecutive(self, nums) -> int:
UF = {}
nums = set(nums)
if not nums:
return 0
# for num in nums:
# UF[num] = num
def find(x):
if x != UF[x]:
UF[x] = find(UF[x])
return UF[x]
def union(x, y):
UF.setdefault(x, x)
UF.setdefault(y, y)
UF[find(x)] = find(y)
for n in nums:
if (n - 1) in nums:
union(n - 1, n)
if (n + 1) in nums:
union(n, n + 1)
ans = 1
for num in nums:
if num in UF:
ans = max(ans, find(num) - num + 1)
return ans
# coding=utf8
import os
import sys
import atexit
def daemonize(pid_file=None):
"""
Create daemon process
:param pid_file: File that saves process id
:return:
"""
# Fork a subprocess from parent process
pid = os.fork()
# The id of subprocess equals 0, and of parent process must larger than 0
if pid:
# Exit from parent process(sys.exit() executes flush while os._exit() doesn't)
sys.exit(0)
# The subprocess defaults the working directory of its parent process.
os.chdir('/')
# The subprocess defaults umask(File permission mask), reset it to 0(Fully control) in order to avoiding R/W operations.
os.umask(0)
# Let the subprocess be the leader of the conversation and the process.
os.setsid()
# Second Fork
_pid = os.fork()
if _pid:
# Exit subprocess
sys.exit(0)
# Grandson process is daemon right now. Redirecting stdin/stdout/stderr descriptions to avoid errors in the printing process.
# Flush stdout/stderr buffer
sys.stdout.flush()
sys.stderr.flush()
# Atomically close and duclipate file description, and redirect into /dev/null(Drop off all input and output)
with open('/dev/null') as read_null, open('/dev/null', 'w') as write_null:
os.dup2(read_null.fileno(), sys.stdin.fileno())
os.dup2(write_null.fileno(), sys.stdout.fileno())
os.dup2(write_null.fileno(), sys.stderr.fileno())
# Write PID
if pid_file:
with open(pid_file, 'w+') as f:
f.write(str(os.getpid()))
# Register Exit function for abnormal exit
atexit.register(os.remove, pid_file)
__asm
{
moveax, dword ptr[i]
inc eax
mov dword ptr[i], eax
}
lock inc dword ptr[i]
On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.
Now, a move consists of removing a stone that shares a column or row with another stone on the grid.
What is the largest possible number of moves we can make?
Example 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] Output: 5
Example 2:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] Output: 3
Example 3:
Input: stones = [[0,0]]
At very first I read this problem, the MOVE operation is described as confusing as heck. I read some explanations on the discussboard, and then finally got the actual meaning.
We can treat each coordinate as two parts (x and y), and can maintain an Union-Find in order to calculate how many groups in the entire field.
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
UF = {}
def find(x):
if x != UF[x]:
UF[x] = find(UF[x])
return UF[x]
def union(x, y):
UF.setdefault(x, x)
UF.setdefault(y, y)
UF[find(x)] = find(y)
for i, j in stones:
print(i, j, ~j)
union(i, ~j)
return len(stones) - len({find(x) for x in UF})
A string S represents a list of words.
Each letter in the word has 1 or more options. If there is one option, the letter is represented as is. If there is more than one option, then curly braces delimit the options. For example, "{a,b,c}" represents options ["a", "b", "c"].
For example, "{a,b,c}d{e,f}" represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"].
Return all words that can be formed in this manner, in lexicographical order.
Example 1:
Input: "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]
Example 2:
Input: "abcd" Output: ["abcd"]
Note:
1 <= S.length <= 50class Solution:
def expand(self, S):
def func(remain, result, results):
if not remain:
results.append(result)
else:
# if a single character appear at the first of the remain string
if remain[0] != "{":
func(remain[1:], result + remain[0], results)
return
else:
temp = list()
i = 0
# find elements in the first brace of the remain string
while remain[i] != "}":
if remain[i].isalpha():
temp.append(remain[i])
i += 1
for t in temp:
func(remain[i + 1:], result + t, results)
results = []
func(S, "", results)
return results
I wanted you to see what real courage is, instead of getting the idea that courage is a man with a gun in his hand. It’s when you know you’re licked before you begin anyway and you see it through no matter what. You rarely win, but sometimes you do.
我想让你见识一下什么事真正的勇气。勇气并不是一个人手里拿着枪，而是当你还未开始就已知道自己会输，可你依然要去做，而且无论如何都要把它坚持到底。你很少能赢，但有时也会。
Given the root of a binary tree, each node in the tree has a distinct value.
After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).
Return the roots of the trees in the remaining forest. You may return the result in any order.
Example 1:
Input: root = [1,2,3,4,5,6,7], to_delete = [3,5] Output: [[1,2,null,4],[6],[7]]
Constraints:
1000.1 and 1000.to_delete.length <= 1000to_delete contains distinct values between 1 and 1000.# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
forest = []
to_delete = set(to_delete)
def buttom_up(root):
if root:
left, right = dfs(root.left), dfs(root.right)
root.left, root.right = left, right
if root.val in to_delete:
if left: forest.append(left)
if right: forest.append(right)
else:
return root
dfs(root)
return ([] if root.val in to_delete else [root]) + forest
#########################################################
to_delete_set = set(to_delete)
res = []
def top_down(root, is_root):
if not root:
return None
root_deleted = root.val in to_delete_set
if is_root and not root_deleted:
res.append(root)
root.left = helper(root.left, root_deleted)
root.right = helper(root.right, root_deleted)
return None if root_deleted else root
top_down(root, True)
return res
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].
Examples:
s = "3[a]2[bc]", return "aaabcbc". s = "3[a2]", return "accaccacc". s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
class Solution:
def decodeString(self, s: str) -> str:
stack = list()
times = list()
for i, v in enumerate(s):
if v.isdigit():
# Single Digit, like 1,2,3...
if not s[i-1].isdigit():
times.append(int(v))
# Multiple digits, like 100, 200...
else:
times[-1] = times[-1] * 10 + int(v)
# push
elif v != "]":
stack.append(v)
# reach "]"
else:
# Retrive string in cloest level square brackets
b = ""
t = stack.pop()
while t != "[":
b = t + b
t = stack.pop()
stack.append(b * times.pop())
return "".join(stack)