Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
Continue readingThere are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.
Continue readingGiven an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Continue readingGiven an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
You have a list of words and a pattern, and you want to know which words in words matches the pattern.
A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.
(Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.)
Return a list of the words in words that match the given pattern.
You may return the answer in any order.
Example 1:
Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}.
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,
since a and b map to the same letter.
Note:
1 <= words.length <= 501 <= pattern.length = words[i].length <= 20def F(w):
m = {}
return [m.setdefault(c, len(m)) for c in w]
return [w for w in words if F(w) == F(pattern)]
Today, I have taken an interview from Wechat.
To be honest, this question is easy, but I do not have sufficient time to complete coding. Maybe I took too much time in same trivial points with the “VERY PROFESSIONAL” interviewer.
The actual question is find the lowest common ancestor of three given nodes, but I thought we can expend this question to N nodes. For testing this question rapidly, I reuse the previous code of constructing a binary tree by the in-order and post-order traversals.
Continue readingKen Thompson wrote an editor and the reversal algorithm in 1971 that should be recorded in myth.
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.p could be empty and contains only lowercase letters a-z, and characters like ? or *.这个时候，有限状态机(FSM)就可以派上用场了。
class Solution:
def isMatch(self, s: str, p: str) -> bool:
"""
:type s: str
:type p: str
:rtype: bool
"""
transfer = {}
state = 0
# Build a Finite State Machine(FSM)
for char in p:
# If pattern is *, it can stay in the current state, or move to the next state via transfer links.
if char == '*':
transfer[state, char] = state
# If pattern is ? or characters, we move to the next state.
else:
transfer[state, char] = state + 1
state += 1
# the last state (Final one) is the accept state
accept = state
# the initial state starts from 0
state = {0}
for char in s:
# There are two ways to achieve state transfer.
# 1) We can use two rolling sets saving previous and current situations
# 2) We also can use python syntactic sugar (Actually as same as the first method)
# I personally think the first method is more readable.
new_state = set()
for token in [char, '*', '?']:
for at in state:
# For each previous state, we can parallelly move to next states
new_state.add(transfer.get((at, token)))
# Set the current state as the previous one
state = new_state
# the second method (elegant but not readable)
# state = set([transfer.get((at, token)) for at in state for token in [char, '*', '?']])
return accept in state
if __name__ == "__main__":
obj = Solution()
result = obj.isMatch("aa", "aa")
print(result)