【412】【统计近似相等数对 I】
我的思路:
两层循环找数组两个数
然后进行1次过滤,如果数字相同直接下一组
不相同的话就要进行2次过滤
方便处理,转移到str格式
change函数用于比较两个输入的字符串是否相同
change中使用两层循环暴力调用两位数位进行交换比较(记得打回原形)
调用ifqual(使用Int函数)比较调换的结果是否符合题意
此处tips:change函数需要调用2次(str1和str2分别处理,防止3和30的情况不通过)
超级复杂的情况下通过了!!!
class Solution:def ifqual(self,str1,str2):return int(str1)==int(str2)def change(self,str1,str2):str1 = list(str1)n=len(str1)for i in range(n):for j in range(i+1,n):str1[i],str1[j]=str1[j],str1[i]if self.ifqual("".join(str1),str2):return Truestr1[i],str1[j]=str1[j],str1[i] return Falsedef countPairs(self, nums: List[int]) -> int:n=len(nums)ret=0for i in range(n):for j in range(i+1,n):if nums[i]==nums[j]:ret+=1else:num1=str(nums[i])num2=str(nums[j])if self.change(num1,num2) or self.change(num2,num1):ret+=1return ret
复杂度还是太高了。
保留,等待大佬题解
大佬题解:
class Solution:def countPairs(self, nums: List[int]) -> int:nums.sort()ret=0dict=defaultdict(int)for num in nums:#不交换st={num}#num的长度s=list(str(num))m=len(s)#数位交换for i in range(m):for j in range(i+1,m):s[i],s[j]=s[j],s[i]st.add(int(''.join(s)))#换回来s[i],s[j]=s[j],s[i]ret+=sum(dict[v] for v in st)dict[num]+=1return ret