class Solution:
def isValidSequence(self, root: TreeNode, arr: List[int]) -> bool:
if root and arr and root.val == arr[0]:
if len(arr) == 1 and root.right is None and root.left is None: return True
return self.isValidSequence(root.left, arr[1:]) or self.isValidSequence(root.right, arr[1:])
else:
return False
 |
| 基礎假設 |
 |
| 計算流程 |
class Solution:
def canJump(self, nums: List[int]) -> bool:
remainJump = 1
nums.pop()
for num in nums:
remainJump -= 1
remainJump = max(remainJump, num)
if remainJump == 0: return False
return True
C#
public class Solution {
public bool CanJump(int[] nums) {
int remainJumps = 1;
int index = 0;
foreach(var num in nums)
{
remainJumps -= 1;
remainJumps = num > remainJumps ? num: remainJumps;
if (remainJumps==0 && index < nums.Length-1)
{
return false;
}
index++;
}
return true;
}
}
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
from functools import lru_cache
@lru_cache(None)
def dfs(y,x):
if y == rows or x == cols:return []
d2 = dfs(y+1, x) + dfs(y, x+1)
distance = grid[y][x] + (min(d2) if d2 else 0)
return [distance]
return dfs(0,0)[0]
又或者迴圈所有位置，每個位置加上左方與上方的最小值，等到迴圈結束，此時右下角為最短距離。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid: return 0
landNums = 0
memo = set()
rows, cols = len(grid), len(grid[0])
def search(y,x):
if y == rows or y < 0 or x == cols or x < 0:
return
if (y,x) in memo: return
else: memo.add((y,x))
if grid[y][x] == "1":
search(y-1,x)
search(y+1,x)
search(y,x-1)
search(y,x+1)
for y in range(rows):
for x in range(cols):
if (y,x) not in memo and grid[y][x] == "1":
search(y,x)
landNums += 1
return landNums
如果想省點空間，把傳入的二維串列當成 memo 使用也是一種選擇，還能稍微加速。
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
product = 1
count = 0
for num in nums:
if num: product *= num
else: count += 1
if count >= 2: return [0 for _ in nums]
elif count == 1: return [0 if num else product for num in nums]
return [product // num for num in nums]
class Solution:
def stringShift(self, s: str, shift: List[List[int]]) -> str:
right = 0
for each in shift:
right += each[1] if each[0] else -each[1]
right %= len(s)
return s[-right:] + s[:-right]
1 which means a street connecting the left cell and the right cell.對於這種地圖或是面積的圖像問題，我總是感到棘手，也許有一套通用思路，不過可能需要很多經驗值累積才能解得順手。
2 which means a street connecting the upper cell and the lower cell.
3 which means a street connecting the left cell and the lower cell.
4 which means a street connecting the right cell and the lower cell.
5 which means a street connecting the left cell and the upper cell.
6 which means a street connecting the right cell and the upper cell.
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
n = len(stones)
while n > 1:
stones.sort(reverse = True)
v = stones.pop(0)
while n > 1 and v >= stones[0]:
v -= stones.pop(0)
n -= 1
if v == 0: n-= 1
else: stones.append(v)
if stones: return stones[-1]
else: return 0
在電腦科學中，Knuth-Morris-Pratt字串尋找演算法（簡稱為KMP演算法）可在一個主文字字串S內尋找一個字W的出現位置。此演算法通過運用對這個詞在不匹配時本身就包含足夠的資訊來確定下一個匹配將在哪裡開始的發現，從而避免重新檢查先前匹配的字元。(維基百科)來講一下一般的字串搜尋，假設一個情境：
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
newS = ""
for char in S:
if char == "#":
if newS: newS = newS[:-1]
else:
newS += char
newT = ""
for char in T:
if char == "#":
if newT:
newT = newT[:-1]
else:
newT += char
return newS == newT
不過呢，題目希望我們能在 O(N)時間 並 O(1)空間 完成。class Solution:
def middleNode(self, head: ListNode) -> ListNode:
if not head: return head
FP, SP = head, head
while FP and FP.next:
FP = FP.next.next
SP = SP.next
return SP
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head: return True
len_head = 1
SP = FP = head
while FP.next:
len_head += 1
FP = FP.next
#
stack = []
for _ in range(len_head//2):
stack.append(SP.val)
SP = SP.next
if len_head%2==1: SP = SP.next
while stack:
if SP.val != stack.pop():
return False
SP = SP.next
return True
Remove all elements from a linked list of integers that have value val.給一串 Linked List ，要刪除其中節點等於 val 的節點，並回傳頭節點。
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
def nextNode(node):
if node:
node.next = nextNode(node.next)
if node.val == val: return node.next
return node
return nextNode(head)
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
memo = set()
PointerA, PointerB = headA, headB
while PointerA:
memo.add(PointerA)
PointerA = PointerA.next
while PointerB:
if PointerB in memo: return PointerB
PointerB = PointerB.next
return None
有效歸有效，不過會消耗掉大量記憶體，在一個提示空間複雜度 O(1) 之下，這方法似乎不是最好的。Given an array of strings, group anagrams together.
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],把文字做分類，anagrams 意思是「 a word, phrase, or name formed by rearranging the letters of another, such as cinema , formed from iceman.」(google翻譯)
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head: return head
fastPointer, slowPointer = head, head
while 1:
# FastPointer go 2 steps forward
for _ in range(2):
if fastPointer.next:
fastPointer = fastPointer.next
if fastPointer == slowPointer:
return True
else:
return False
# SlowPointer go 1 steps forward
for _ in range(1):
slowPointer = slowPointer.next
Given a 2D board and a list of words from the dictionary, find all words in the board.很像找詞遊戲，看看版面上有沒有要搜尋的詞。不過跟一般的規則不同的是，它可以轉彎。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
return sum([max(prices[i]-prices[i-1], 0) for i in range(1,len(prices))])
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Follow up:
「If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.」
class Solution:
def generateParenthesis(self, n):
result = []
def nextIdx(ln, rn, text):
if ln == 0 and rn == 0:
result.append(text)
if ln - 1 >= 0:
nextIdx(ln-1, rn, text+"(")
if rn - 1 >= ln:
nextIdx(ln, rn-1, text+")")
nextIdx(n, n, "")
return result
這是最直觀的寫法，速度也不錯。class Solution:
def solveSudoku(self, board) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def getCandidate(y, x):
Candidates = {}.fromkeys([str(i) for i in range(1,10)])
for x2 in range(9):
if board[y][x2] in Candidates: del Candidates[board[y][x2]]
for y2 in range(9):
if board[y2][x] in Candidates: del Candidates[board[y2][x]]
for y2 in range(y//3*3, y//3*3+3):
for x2 in range(x//3*3, x//3*3+3):
if board[y2][x2] in Candidates: del Candidates[board[y2][x2]]
return Candidates.keys()
def nextStep(level):
try:
row, col, _ = stepPos[level]
for num in getCandidate(row, col):
board[row][col] = num
if nextStep(level+1):
return True
else:
board[row][col] = "."
except:
return True
stepPos = []
for y in range(9):
for x in range(9):
if board[y][x] == ".":
stepPos.append((y, x, len(getCandidate(y, x))))
stepPos.sort(key=lambda x: x[2])
nextStep(0)
當中多了一作法，在找出所有可下位置時算出可能的數字數，接著再用可能數字數從小到大排序，就會從最少可能組合開始下起，這就像我們玩數獨一般，會從最少可能性的地方找起。class Solution:
def solveSudoku(self, board) -> None:
"""
Do not return anything, modify board in-place instead.
"""
Candidates = {*'123456789'}
memoCol = {}
memoRow = {}
memoArea = {}
for i in range(9):
memoCol[i] = set()
memoRow[i] = set()
memoArea[i] = set()
def getCandidate(y, x):
return Candidates - memoArea[x//3+y//3*3] - memoCol[x] - memoRow[y]
def nextStep(level):
try:
row, col = stepPos[level]
for num in getCandidate(row, col):
memoCol[col].add(num)
memoRow[row].add(num)
memoArea[col//3+row//3*3].add(num)
board[row][col] = num
if nextStep(level+1):
return True
else:
board[row][col] = "."
memoCol[col].discard(num)
memoRow[row].discard(num)
memoArea[col//3+row//3*3].discard(num)
except:
return True
stepPos = []
for y in range(9):
for x in range(9):
v = board[y][x]
if v == ".":
stepPos.append((y,x))
else:
memoCol[x].add(v)
memoRow[y].add(v)
memoArea[x//3+y//3*3].add(v)
nextStep(0)
class Solution:
def singleNumber(self, nums: List[int]) -> int:
memo = {}
memo2 = {}
for num in nums:
if num in memo2:
continue
else:
if num in memo:
del memo[num]
memo2[num] = 0
continue
memo[num] = num
for key in memo: return memo[key]
我在想，有沒有甚麼只循環過一遍就能得到解法？不要有跑完N兩次或以上。看了前段班解法，回頭看題目才知道頂多重複兩次。(又再一次沒有看清楚題目