Last updated
class Solution:
def search(self , nums: List[int], target: int) -> int:
if not nums:
return -1
# write code here
l, r = 0, len(nums)
while l<r:
mid = (l+r)//2
if nums[mid] <target:
# +1是确保在 r= l+1时 不会mid=l 导致死循环
l = mid+1
elif nums[mid] > target:
# -1 是确保在 r= l+1时 不会mid=r 导致死循环
r = mid-1
else:
#确保找到target后，l和r至少有一个是包含target
r = mid
if l< len(nums) and nums[l]==target:
return l
if r >=0 and nums[r] == target:
return r
return -1class Solution:
def helper(self, root, o1, o2):
if not root:
return -1
l = self.helper(root.left, o1, o2)
r = self.helper(root.right, o1, o2)
if (l and r ) or (root.val in [o1, o2] and (l or r)):
self.ancester = root.val
if root.val in [o1,o2] or l or r:
return 1
return -1
def helper2(self, root, o1, o2):
if not root:
return None
if root.val in [o1, o2]:
return root
t1 = self.helper2(root.left, o1,o2)
t2 = self.helper2(root.right, o1,o2)
if not t1:
return t2
if not t2:
return t1
return root
def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
# write code here
# self.ancester = -1
# self.helper(root, o1,o2)
# return self.ancester
val= self.helper2(root,o1,o2)
if val:
return val.val
return -1// Some code 最大累加和思路
def max_sum(nums):
max_sum = -float('inf')
res = max_sum
for i in range(len(nums)):
max_sum = max(max_sum, 0) + nums[i]
res = max(res, max_sum)
return res// Some code
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
"""
a b c d e
a 1 1 1 1 1
c 1 1 2 2 2
e 1 1 2 2 3
b s b i n i n m
j 0 0 0 0 0 0 0 0
m 0 0 0 0 0 0 0 1
j 0 0 0 0 0 0 0 1
k 0 0 0 0 0 0 0 1
b 1 1
k
j
k
v
dp[i][j] = s[:i] 和s2[:j] 最长公共子序列长度
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1] ) + 0 if s[i]!=s[j] else 1
"""
#长度+1 是为了考虑边界值， 从空值开始
dp = [ [0] * (len(text1)+1) for _ in range(len(text2)+1) ]
for r in range(1, len(text2)+1):
for c in range(1, len(text1)+1):
if text1[c-1] == text2[r-1]:
# 如果最后一个字符是一样的，那么dp[r][c]就是前一行和前一列的解+1
dp[r][c] = dp[r-1][c-1] + 1
else:
# 如果最后一个字符不一样, 那么就找上一次情况的解里面最大那个
dp[r][c] = max(max(dp[r-1][c], dp[r][c-1]), dp[r-1][c-1])
return dp[-1][-1]
class Solution:
def longestCommonSubsequence(self, s: str, t: str) -> int:
f = [0] * (len(t) + 1)
for x in s:
pre = 0 # f[0]
for j, y in enumerate(t):
tmp = f[j + 1]
f[j + 1] = pre + 1 if x == y else max(f[j + 1], f[j])
pre = tmp
return f[-1]
作者：灵茶山艾府
链接：https://leetcode.cn/problems/longest-common-subsequence/solutions/2133188/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-lbz5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。