Repl.it (線上執行Python) ※支援手機(Android IOS)OneWildcardMask: 將輸入的IP位置用一組Network和WildcardMask表示。MultiWildcardMask: 用一或多組Network和WildcardMask去表示所有輸入的IP的。
1.The root is the maximum number in the array.
2.The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.3.The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
count = Counter(s1)
match_len = 0
p_len = len(s1)
for i, c in enumerate(s2):
while match_len and (c not in count or count[c] == 0):
count[s2[i - match_len]] += 1
match_len -= 1
if c in count and count[c] > 0:
match_len += 1
count[c] -= 1
if match_len == p_len:
return True
return False
class Solution:
def majorityElement(self, nums: List[int]) -> int:
import collections
counter = collections.Counter(nums)
n = len(nums)
for key in counter:
if counter[key] >= n/2:
return key
class Solution:
def firstUniqChar(self, s: str) -> int:
import collections
counter = collections.Counter(s)
for key in counter:
if counter[key] == 1: return s.index(key)
return -1
C#
public class Solution {
public int FirstUniqChar(string s) {
var counter = new Dictionary();
foreach(var c in s)
{
counter[c] = 1 + (counter.ContainsKey(c) ? counter[c] : 0);
}
foreach(var item in counter)
{
if(item.Value == 1)
{
return s.IndexOf(item.Key);
}
}
return -1;
}
}
class Solution:
def findComplement(self, num: int) -> int:
return ((1 << num.bit_length()) - 1 ) ^ num
C#
public class Solution {
public int FindComplement(int num) {
int r = 1;
while(r < num)
{r = (r << 1) + 1;}
return r ^ num;
}
}
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兩次或以上。看了前段班解法，回頭看題目才知道頂多重複兩次。(又再一次沒有看清楚題目
import comtypes.client, os try: os.remove(comtypes.client.gen_dir + r"\_75AAD71C_8F4F_4F1F_9AEE_3D41A8C9BA5E_0_1_0.py") os.remove(comtypes.client.gen_dir + r"\SKCOMLib.py") except: pass
Error in sys.excepthook: Original exception was:不以為意，因為運行不會受到任何影響。
程式碼：PotPlayerMini64.exe
引數："C:\BGM.dpl"
位置：J:\Program Files\DAUM\PotPlayer\""" 完成速度排行榜 Method: bstr json, Compress Ratio: 0.06：1 Data size: 400064(0.39MB), Wspeed:4.16025 MB/s, Rspeed:2.97668 MB/s, Uspeed:1.73516 MB/s Method: json zlib, Compress Ratio: 15.32：1, level = 6 Data size: 400064(0.39MB), Wspeed:2.99731 MB/s, Rspeed:2.76445 MB/s, Uspeed:1.43809 MB/s Method: str json, Compress Ratio: 0.06：1 Data size: 400064(0.39MB), Wspeed:3.16940 MB/s, Rspeed:2.35598 MB/s, Uspeed:1.35141 MB/s Method: json gz, Compress Ratio: 15.31：1, CompressLevel = 9 Data size: 400064(0.39MB), Wspeed:2.93210 MB/s, Rspeed:2.36939 MB/s, Uspeed:1.31044 MB/s Method: json xz, Compress Ratio: 330.09：1, preset = 6 Data size: 400064(0.39MB), Wspeed:0.81887 MB/s, Rspeed:1.98104 MB/s, Uspeed:0.57938 MB/s Method: json json, Compress Ratio: 0.06：1 Data size: 400064(0.39MB), Wspeed:0.57614 MB/s, Rspeed:2.28234 MB/s, Uspeed:0.46002 MB/s Method: bstr list, Compress Ratio: 0.08：1 Data size: 400064(0.39MB), Wspeed:3.77832 MB/s, Rspeed:0.34935 MB/s, Uspeed:0.31978 MB/s Method: str str(list), Compress Ratio: 0.10：1 Data size: 400064(0.39MB), Wspeed:3.58643 MB/s, Rspeed:0.33802 MB/s, Uspeed:0.30890 MB/s Method: str str(tuple), Compress Ratio: 0.10：1 Data size: 400064(0.39MB), Wspeed:3.59002 MB/s, Rspeed:0.33762 MB/s, Uspeed:0.30860 MB/s Method: json bz, Compress Ratio: 137.76：1, CompressLevel = 9 Data size: 400064(0.39MB), Wspeed:0.22510 MB/s, Rspeed:1.76317 MB/s, Uspeed:0.19962 MB/s """
a # call getter a = 1 # call setter del a # call deleter發生以上三種狀況，就會分別執行對應的函式。
吃到這個消息，如果又想用自製 ico 檔的，將原圖片透過這個網站將圖片轉成 .ico 就可以解決了。
ERROR:root:Some trouble with the icon (檔案位置): (0, 'LoadImage', 'No error message is available')
plt.rcParams['font.sans-serif'] = ['DFKai-SB'] #可以直接用上此行顯示中文字，如果不嫌棄標楷體的話""" 一定要使用「字體名稱」，不是字檔名kaiu。可以從新生的 json 檔搜尋字檔名(如: kaiu.ttf)，會看到有一項 "name": "DFKai-SB"，其餘字體也可以找到對應的name。"""
plt.rcParams['font.sans-serif'] = ['I.Ngaan']
plt.rcParams['axes.unicode_minus']=False
#axes.unicode_minus : True
axes.unicode_minus : False
