[数据结构与算法][Leetcode] 每日两题 399 1005 -day29

399. 除法求值

并查集 大佬的代码

看这个也行 https://blog.csdn.net/m0_64204369/article/details/121694930

class UnionFind:
    def __init__(self):
        """
        记录每个节点的父节点
        记录每个节点到根节点的权重
        """
        self.father = {}
        self.value = {}
    
    def find(self,x):
        """
        查找根节点
        路径压缩
        更新权重
        """
        root = x
        # 节点更新权重的时候要放大的倍数
        base = 1
        while self.father[root] != None:
            root = self.father[root]
            base *= self.value[root]
        
        while x != root:
            original_father = self.father[x]
            ##### 离根节点越远，放大的倍数越高
            self.value[x] *= base
            base /= self.value[original_father]
            #####
            self.father[x] = root
            x = original_father
         
        return root
    
    def merge(self,x,y,val):
        """
        合并两个节点
        """
        root_x,root_y = self.find(x),self.find(y)
        
        if root_x != root_y:
            self.father[root_x] = root_y
            ##### 四边形法则更新根节点的权重
            self.value[root_x] = self.value[y] * val / self.value[x]

    def is_connected(self,x,y):
        """
        两节点是否相连
        """
        return x in self.value and y in self.value and self.find(x) == self.find(y)
    
    def add(self,x):
        """
        添加新节点，初始化权重为1.0
        """
        if x not in self.father:
            self.father[x] = None
            self.value[x] = 1.0

            
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        uf = UnionFind()
        
        for (a,b),val in zip(equations,values):
            uf.add(a)
            uf.add(b)
            uf.merge(a,b,val)
    
        res = [-1.0] * len(queries)

        for i,(a,b) in enumerate(queries):
            if uf.is_connected(a,b):
                res[i] = uf.value[a] / uf.value[b]
        return res

1005. K 次取反后最大化的数组和

方法1： 每次排序 然后改最后一个

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        
        for i in range(k):
        	nums.sort()
            nums[0] = -nums[0]
        

方法2：

找到 0界点 然后先改负数部分 然后改 负数和正数绝对值最小的那个

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
		nums.sort()
        left,right =0,len(nums)-1
        while left<right-1:
            mid = (left +right) //2
            if nums[mid]>=0 :
                right = mid
            else :
                left = mid
        mid = left
        if mid+1 >=k:
            for i in range(k):
                nums[i] = -nums[i]
        else :
            for i in range(mid+1):
                nums[i] = -nums[i]
            #print(nums)
            if (k-mid+1)%2:
                if nums[mid]>nums[mid+1]:
                    nums[mid+1] =-nums[mid+1]
                else :
                    nums[mid] = -1**(k-mid+1) *nums[mid]
        #print(left,right,mid,nums)
        return sum(nums)