算法题记录 29

声明

到目前为止，随机一题产生的周赛题目已经做完。接下来会以周赛题+某知识点题目的形式进行单独记录。

编程基础

3110.字符串的分数（1152）

给你一个字符串 s 。一个字符串的 分数 定义为相邻字符 ASCII 码差值绝对值的和。

请你返回 s 的 分数 。

涉及知识点

字符串

解决思路

送分题

class Solution:
    def scoreOfString(self, s: str) -> int:
        result=0
        for i in range(len(s)-1):
            result+=abs(ord(s[i])-ord(s[i+1]))
        return result

2469.字符串的分数（1153）

给你一个四舍五入到两位小数的非负浮点数 celsius 来表示温度，以 摄氏度（Celsius）为单位。

你需要将摄氏度转换为 开氏度（Kelvin）和 华氏度（Fahrenheit），并以数组 ans = [kelvin, fahrenheit] 的形式返回结果。

返回数组 ans 。与实际答案误差不超过 10-5 的会视为正确答案。

涉及知识点

数组

解决思路

送分题

class Solution:
    def convertTemperature(self, celsius: float) -> List[float]:
        return [celsius+273.15,celsius*1.80+32.00]

2413.最小偶倍数（1145）

给你一个正整数 n ，返回 2 和 n 的最小公倍数（正整数）。

涉及知识点

数学

解决思路

送分题

class Solution:
    def smallestEvenMultiple(self, n: int) -> int:
        x=gcd(n,2)
        return n*2//x

2236.判断根结点是否等于子结点之和（简单）

给你一个 二叉树 的根结点 root，该二叉树由恰好 3 个结点组成：根结点、左子结点和右子结点。

如果根结点值等于两个子结点值之和，返回 true ，否则返回 false 。

涉及知识点

树

解决思路

送分题

class Solution:
    def checkTree(self, root: Optional[TreeNode]) -> bool:
        return True if root.left.val+root.right.val==root.val else False

1486.数组异或操作（1181）

给你两个整数，n 和 start 。

数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。

请返回 nums 中所有元素按位异或（XOR）后得到的结果。

涉及知识点

循环

解决思路

送分题

class Solution:
    def xorOperation(self, n: int, start: int) -> int:
        result=start
        for i in range(1,n):
            result=result^(start+2*i)
        return result

1512.好数对的数目（1161）

给你一个整数数组 nums 。

如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。

返回好数对的数目。

涉及知识点

哈希表

解决思路

送分题

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        ans = 0
        cnt = defaultdict(int)
        for x in nums:  
            ans += cnt[x]
            cnt[x] += 1
        return ans

1534.统计好三元组（1279）

给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。

如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个 好三元组 。

0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c
其中 |x| 表示 x 的绝对值。

返回 好三元组的数量 。

涉及知识点

循环

解决思路

送分题

class Solution:
    def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
        count=0
        for i in range(len(arr)):
            for j in range(i+1,len(arr)):
                for k in range(j+1,len(arr)):
                    if abs(arr[i]-arr[j])<=a and abs(arr[j]-arr[k])<=b and abs(arr[i]-arr[k])<=c:
                        count+=1
        return count

258.各位相加（简单）

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。

涉及知识点

模拟

解决思路

送分题

class Solution:
    def addDigits(self, num: int) -> int:
        def cal(num:int)->int:
            tmp=0
            while num!=0:
                tmp+=num%10
                num=num//10
            return tmp
        while num>=10:
            num=cal(num)
        return num

231.2的幂（简单）

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

涉及知识点

数学

解决思路

送分题

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n<=0:
            return False
        while n!=1:
            tmp=n%2
            if tmp!=0:
                return False
            n=n//2
        return True

326.3的幂（简单）

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

涉及知识点

数学

解决思路

送分题

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n<=0:
            return False
        while n!=1:
            tmp=n%3
            if tmp!=0:
                return False
            n=n//3
        return True

263.丑数（简单）

丑数 就是只包含质因数 2、3 和 5 的 正 整数。

给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

涉及知识点

数学

解决思路

送分题

class Solution:
    def isUgly(self, n: int) -> bool:
        if n==0:
            return False
        for i in (2,3,5):
            while n%i==0:
                n=n//i
        if n!=1:
            return False
        else:
            return True

1470.重新排列数组（1121）

给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,…,xn,y1,y2,…,yn] 的格式排列。

请你将数组按 [x1,y1,x2,y2,…,xn,yn] 格式重新排列，返回重排后的数组。

涉及知识点

数组

解决思路

送分题

class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        x=nums[:n]
        y=nums[n:]
        return [i for j in zip(x,y) for i in j]

867.转置矩阵（1259）

给你一个二维整数数组 matrix， 返回 matrix 的 转置矩阵 。

矩阵的 转置 是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。

涉及知识点

数组

解决思路

送分题

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        M, N = len(matrix), len(matrix[0])
        res = [[0] * M for i in range(N)]
        for i in range(M):
            for j in range(N):
                res[j][i] = matrix[i][j]
        return res

1422.分割字符串的最大得分（1238）

给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个 非空 子字符串（即 左 子字符串和 右 子字符串）所能获得的最大得分。

「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。

涉及知识点

数组

解决思路

送分题

class Solution:
    def maxScore(self, s: str) -> int:
        c=Counter(s[1:])
        m,result=c['1'],c['1']
        if s[0]=='0':
            m+=1
            result+=1
        for i in s[1:-1]:
            if i=='0':
                result+=1
                m=max(result,m)
            else:
                result-=1
        return m

2586.统计范围内的元音字符串数（1179）

给你一个下标从 0 开始的字符串数组 words 和两个整数：left 和 right 。

如果字符串以元音字母开头并以元音字母结尾，那么该字符串就是一个 元音字符串 ，其中元音字母是 ‘a’、’e’、’i’、’o’、’u’ 。

返回 words[i] 是元音字符串的数目，其中 i 在闭区间 [left, right] 内。

涉及知识点

字符串

解决思路

送分题

class Solution:
    def vowelStrings(self, words: List[str], left: int, right: int) -> int:
        count=0
        for i in range(left,right+1):
            if words[i][0] in 'aeiou' and words[i][-1] in 'aeiou':
                count+=1
        return count

852.山脉数组的峰顶索引（1182）

给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。

返回峰值元素的下标。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

涉及知识点

二分

解决思路

送分题

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left, right = 0, len(arr) - 2
        while left + 1 < right:
            mid = (left + right) // 2
            if arr[mid] > arr[mid + 1]:
                right = mid
            else:
                left = mid
        return right

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。