又是思考很久的一天
DP果然是我的弱項
若想跟我一起做題目的話，我都會定時開直播唷(不過都在半夜就是了XD)
Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).
Note:
Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer. -3.
把 n 給二元化後，檢查裡面有多少 1 。
這題 Python 要做滿白癡的，所以後面有用個位移的作法。
tryit
class Solution:
#輸入的不是bin number
#python 白癡法
# def hammingWeight(self, n: int) -> int:
# return bin(n).count('1')
#利用位移
def hammingWeight(self, n: int) -> int:
ans = 0
while n:
if n%2:
ans+=1
n = n>>1
return ans
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
三角形數字塔，把數字連結起來，連到塔頂，找到最小的總和
從下往上把每一個最小可以是什麼找出來，若需要找路徑可以用額外方法存
2
1 9
6 5 1
4 4 8 1
class Solution:
#一開始我的寫法
def minimumTotal(self, triangle: List[List[int]]) -> int:
tL = len(triangle)-1
while tL != 0:
temp = tL
tL -= 1
# print(tL,temp)
while temp != 0:
triangle[tL][temp-1] = triangle[tL][temp-1] + min(triangle[tL+1][temp],triangle[tL+1][temp-1])
temp-=1
# print(triangle)
return triangle[0][0]
#以下皆參考別人
#別人的triangle bottom up的寫法
#我不覺得有比較好，但他比我有系統性
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
next_row = triangle[-1][:]
curr_row = [0] * n
for i in range(n - 2, -1, -1):
for j in range(i + 1):
lower_left = triangle[i][j] + next_row[j]
lower_right = triangle[i][j] + next_row[j + 1]
curr_row[j] = min(lower_left, lower_right)
curr_row, next_row = next_row, curr_row
return next_row[0] # because we swapped at last iteration
#別人recursion的寫法，會TLE但還是必須知道可以由這進行延伸
from functools import cache
def minimumTotal(self, triangle: List[List[int]]) -> int:
@cache #這是一個裝飾器，可以幫助記憶輸入相同函數所回傳的值，加這句後就不會TLE
def dfs(i, j):
if i == len(triangle):
return 0
lower_left = triangle[i][j] + dfs(i + 1, j)
lower_right = triangle[i][j] + dfs(i + 1, j + 1)
return min(lower_left, lower_right)
return dfs(0, 0)
#使用memorize的方式配合記憶處理，跟cache感覺很像
def minimumTotal(self, triangle: List[List[int]]) -> int:
memo = [[-1] * len(triangle) for _ in range(len(triangle))]
def dfs(i, j):
if i == len(triangle):
return 0
if memo[i][j] != -1:#如果跑過的東西就直接回傳
return memo[i][j]
lower_left = triangle[i][j] + dfs(i + 1, j)
lower_right = triangle[i][j] + dfs(i + 1, j + 1)
memo[i][j] = min(lower_left, lower_right)
return memo[i][j]
return dfs(0, 0)
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
抓取串列裡面的值，抓過的值的隔壁的值不能抓，求可以抓的最大值為多少。
#dp真的是我的弱項
class Solution:
#必須要隔一個房子搶劫
#從索引值0或1開始
#下一個必定是+2或+3
#memorize的寫法，我原本是沒想到我會寫出來啦，這是我的弱項
def rob(self, nums: List[int]) -> int:
nL = len(nums)
if nL == 1:
return nums[0]
dp = [-1 for i in range(nL)]
def recursion(index):
if index >= nL:
return 0
if dp[index] != -1:
return dp[index]
dp[index] = max(recursion(index+2),recursion(index+3)) + nums[index]
return dp[index]
return max(recursion(0),recursion(1))
#迴圈寫法
#別人的寫法
#我可不可以寫個我不會就去看解答阿==
#......我想想
#2 7 9 3 1
def rob(self, nums):
# f(0) = nums[0]
# f(1) = max(num[0], num[1])
# f(k) = max( f(k-2) + nums[k], f(k-1) )
# 從後面數回來，不是dp倒數第一個就是倒數第二個
'''
# Approach 1:- Construct dp table
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums) #儲存每格最大值用的
dp[0] = nums[0] #dp[0]一定只有第0個
dp[1] = max(nums[0], nums[1]) #dp[1]一定是0或1其一
for i in range(2, len(nums)): #dp[2]以上就是要比較(dp[i-1])或(dp[i-2]+自己)誰比較大
dp[i] = max(nums[i] + dp[i-2], dp[i-1])
return dp[-1] # 回傳最後的元素
'''
# Approach 2:- Constant space use two variables and compute the max respectively
prev = curr = 0
for num in nums:#這就是更簡化過後的dp，更省空間
temp = prev # This represents the nums[i-2]th value
prev = curr # This represents the nums[i-1]th value
curr = max(num + temp, prev) # Here we just plug into the formula
return curr
Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.
Return a list of all possible strings we could create. Return the output in any order.
把字母大小寫的每一種狀況都進行輸出(數學排列題)
class Solution:
#把字母大小寫的每一種狀況都進行輸出
#我一開始的寫法
#binary number
def letterCasePermutation(self, s: str) -> List[str]:
s = list(s.lower())
letterS = [i for i in range(len(s)) if not s[i].isdigit()]
lls = len(letterS)
ans = []
for i in range(2**lls):
temp = bin(i)[2:].zfill(lls)
tempL = s.copy()
for i in range(len(temp)):
if temp[i] == "1":
tempL[letterS[i]] = tempL[letterS[i]].upper()
ans.append("".join(tempL))
return ans
#參考別人寫法
class Solution(object):
def letterCasePermutation(self, S):
def backtrack(sub="", i=0):
if len(sub) == len(S):#當長度等同於字串長度時
res.append(sub)
else:
if S[i].isalpha():#判斷是不是字母
#string.swapcase()可以把字母大寫變小寫，小寫變大寫
backtrack(sub + S[i].swapcase(), i + 1)
backtrack(sub + S[i], i + 1)#不是字母就加數字&&加原字母
res = []
backtrack()
return res
iThome鐵人賽
看影片追技術