|
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
10/10 801. 使序列递增的最小交换次数
dp
只能相同位置交换
所以对于位置i 必定满足
nums1[i]>nums1[i-1] nums2[i]>nums2[i-1] 或者
nums1[i]>nums2[i-1] nums2[i]>nums1[i-1] 此时需要交换i位置
设dp[i][0]为不交换i位置满足条件的最小次数 dp[i][1]为交换i位置的最小次数
如果仅满足条件1 则i位置情况与前一位置相同
dp[i][0] = dp[i-1][0] dp[i][1] = dp[i-1][1]+1
如果仅满足条件2 则需要交换一次
dp[i][0] = dp[i-1][1] dp[i][1] = dp[i-1][0]+1
如果同事满足1,2 则找最小次数
dp[i][0] = min(dp[i-1][0],dp[i-1][1]) dp[i][1] = min(dp[i-1][0],dp[i-1][1])+1
def minSwap(nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: int
"""
n = len(nums1)
dp0,dp1 = 0,1
for i in range(1,n):
t1 = nums1[i]>nums1[i-1] and nums2[i]>nums2[i-1]
t2 = nums1[i]>nums2[i-1] and nums2[i]>nums1[i-1]
if t1 and t2:
dp0,dp1 = min(dp0,dp1),min(dp0,dp1)+1
elif t1:
dp0,dp1 = dp0,dp1+1
else:
dp0,dp1 = dp1,dp0+1
return min(dp0,dp1)
10/11 1790. 仅执行一次字符串交换能否使两个字符串相等
排序两个字符串 如果不同必定不可
从头遍历 如果差异大于2个及不可
def areAlmostEqual(s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
if sorted(list(s1))!=sorted(list(s2)):
return False
diff = 0
for i in range(len(s1)):
if s1[i]!=s2[i]:
diff+=1
if diff>2:
return False
return True
10/12 817. 链表组件
将nums放入hash表中
遍历链表 判断是否在hash表中
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def numComponents(head, nums):
"""
:type head: ListNode
:type nums: List[int]
:rtype: int
"""
m = {}
for num in nums:
m[num]=1
ans = 0
has = False
while head:
if head.val in m:
if not has:
ans +=1
has = True
else:
has = False
head = head.next
return ans
10/13 769. 最多能完成排序的块
数组内每个数都不一样 排序后arr[i]=i
如果arr[0~x]间的最大值为x 则说明这个范围内可以排序成与最后结果相同
如果arr[0~x] max=x arr[0~y] max=y y>x 则arr[0~y] 可以分割为[0x],[x+1y]
所以只要判断有多少个max(arr[0~i]) = i即可
def maxChunksToSorted(arr):
"""
:type arr: List[int]
:rtype: int
"""
ans = 0
mx = 0
for i,x in enumerate(arr):
mx=max(mx,x)
if mx==i:
ans +=1
return ans
10/14 940. 不同的子序列 II
动态规划 dp[i] 代表以s[i]结尾的子序列数目
如果a<b s[a]=s[b] 则dp[a],dp[b]会存在重复的子序列
但是dp[a]必定是dp[b]的真子集 只要将dp[a]中的s[a]变为s[b]及全部包含进了dp[b]
所以对于dp[i]只要记录[0~i-1]间的最近的不同字符dp
res[025]分别记录az最近的位置
def distinctSubseqII(s):
"""
:type s: str
:rtype: int
"""
res = [-1]*26
MOD = 10**9+7
n= len(s)
dp = [1]*n
for i,c in enumerate(s):
for j in range(26):
if res[j]!=-1:
dp[i] = (dp[i]+dp[res[j]])%MOD
res[ord(s[i])-ord('a')] = i
ans = 0
for i in range(26):
if res[i]!=-1:
ans = (ans+dp[res[i]])%MOD
return ans
10/15 441. 用栈操作构建数组
遍历target 如果当前数值i<target[loc] 则push,pop
一直到i=target[loc] push,loc+1
def buildArray(target, n):
"""
:type target: List[int]
:type n: int
:rtype: List[str]
"""
loc = 0
i = 1
ans = []
while loc<len(target):
ans.append("Push")
if target[loc]>i:
ans.append("Pop")
else:
loc+=1
i+=1
return ans
10/16 886. 可能的二分法
统计dis[x] = [] 代表x不喜欢的人
group[n] 用来标记每一个人属于哪个组 1或-1
遍历每一个人 如果当前人没有被分组 则将其分到1组
遍历其不喜欢得人 如果该人已经分组判断是否相同 如果相同则失败
否则 将其分到另外一组
def possibleBipartition(n, dislikes):
"""
:type n: int
:type dislikes: List[List[int]]
:rtype: bool
"""
dis = [[] for _ in range(n)]
for x,y in dislikes:
dis[x-1].append(y-1)
dis[y-1].append(x-1)
group = [0]*n
for i,c in enumerate(group):
if c==0:
l = [i]
group[i]=1
while l:
tmp = []
for x in l:
for y in dis[x]:
if group[x]==group[y]:
return False
if group[y] == 0:
group[y] = -group[x]
tmp.append(y)
l = tmp
return True
|