leetcode刷题 237~

题目237题

删除链表里的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

思路

诡异的题目

实现

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

题目238题

除自身以外数组的乘积

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

思路

1.乘积=当前左边乘积*当前右边乘积

实现

1.
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)-1
        leftout =[1]
        rightout = [1]
        result = []
        for i in range(0, length):
            temp = nums[i] * leftout[i]
            leftout.append(temp)
        for i in range(length, 0,-1):
            temp = nums[i] * rightout[length -i]
            rightout.append(temp)
        rightout = rightout[::-1]
        for i in range(length+1):
            result.append(leftout[i]*rightout[i])
        return result

题目240题

搜索二维矩阵II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:

现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。

给定 target = 20，返回 false。

思路

由于矩阵是有序的，可以将矩阵视为搜索二叉树，矩阵的右上角为根节点，左方为左子节点且小于当前节点，下方为右子节点且大于当前节点。

实现

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        row_len = len(matrix)
        if row_len == 0:
            return False
        col_len = len(matrix[0])
        row,col = 0, col_len-1
        while 0 <=row < row_len and 0<= col< col_len:
            if target > matrix[row][col]:
                row += 1
            elif target < matrix[row][col]:
                col -= 1
            else:
                return True
        return False

题目241题

为运算表达式设计优先级

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

思路

分治的思想：

1. 分解：按运算符分成左右两部分，分别求解
2. 解决：实现一个递归函数，输入算式，返回算式解
3. 合并：根据运算符合并左右两部分的解，得出最终解

实现

class Solution:
    def diffWaysToCompute(self, input: str) -> List[int]:
        if input.isdigit():
            return [int(input)]
        result = []
        for i,char in enumerate(input):
            if char in ["+","-","*"]:
                left = self.diffWaysToCompute(input[:i])
                right = self.diffWaysToCompute(input[i+1:])
                for l in left:
                    for r in right:
                        if char == '+':
                            result.append(l + r)
                        elif char == '-':
                            result.append(l - r)
                        else:
                            result.append(l * r)
        return result

题目242题

有效的字母

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

思路

实现

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        dic = dict()
        for i in s:
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        for i in t:
            if i in dic:
                dic[i] -= 1
            else:
                return False
        for i in dic.values():
            if i != 0:
                return False
        return True

题目257题

二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

思路

二叉树的遍历

实现

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        result = []
        if not root:
            return []
        def search(node, path):
            if not node.left and not node.right:
                result.append(path+str(node.val))
            if node.left:
                search(node.left, path+str(node.val)+"->")
            if node.right:
                search(node.right, path+str(node.val)+"->")
                          
        search(root,'')
        return result

题目258题

各位相加

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

思路实现

1.
class Solution:
    def addDigits(self, num: int) -> int:
        nums = str(num)
        result = num
        while len(nums) != 1:
            result = 0
            for i in nums:
                result += int(i)
            nums = str(result)
        return result
2.

class Solution:

    def addDigits(self, num: int) -> int:

        if num == 0:

            return 0

        elif num%9 == 0:

            return 9

        else:

            return num%9

题目237题

只出现一次的数字III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

思路实现

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        count=[]
        for num in nums:
            if num in count:
                count.remove(num)
            else:
                count.append(num)
        return count

题目263题

丑数

编写一个程序判断给定的数是否为丑数。

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

思路实现

class Solution:
    def isUgly(self, num: int) -> bool:
        if num == 0:
            return False
        while num % 2 == 0:
            num = num//2
        while num % 3 == 0:
            num = num//3
        while num % 5 == 0:
            num = num//5
        return num == 1

题目264题

丑数II

编写一个程序，找出第 n 个丑数。

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

思路实现

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        i, j ,k = 0,0,0
        result = [1]
        while len(result) != n:
            ugly = min(result[i]*2,result[j]*3,result[k]*5)
            result.append(ugly)
            if ugly == result[i]*2:
                i += 1
            if ugly == result[j]*3:
                j += 1
            if ugly == result[k]*5:
                k +=1
        return result[-1]

题目268题

丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

思路实现

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        sum1 =  sum(nums)
        sum2 = (1+n)*n/2
        return int(sum2-sum1)

题目237题

H指数

给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数 不超过 h 次。）

例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。

思路实现

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort()
        citations.reverse()
        i = 0
        while i < len(citations) and citations[i] > i:
            i += 1
        return i

题目237题

H指数II

思路

二分法

实现

题目278题

第一个错误版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

思路

二分法

实现

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left = 1
        right = n
        while left <= right:
            mid = left + (right-left)//2
            if isBadVersion(mid):
                right = mid - 1
            else:      
                left = mid + 1
        return left

题目279题

完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.

思路

1.递归：

numSquares(n)=min(numSquares(n-k) + 1)，其中k是完全平方数

由此完成的算法时间超时遇到n=44无法通过，于是增加优化，去除重复，new_k <= pre_k,遇到n=165超时

2.动态规划

numSquares(n)=min(numSquares(n-k) + 1)

3.贪心算法

假设一个数可以组成，若不行两个数组成，以此类推

实现

1.
class Solution:
    def numSquares(self, n: int) -> int:
        result = float("inf")

        def square(n, pre):
            if n == 0:
                nonlocal result
                result = min(result,len(pre))
            elif n < 0:
                return
            first = int(n**0.5)
            visit = pre[-1] if len(pre) > 0 else first
            while first > 0 and first <= visit:
                num = first**2
                square(n-num, pre +[num])
                first -= 1
        
        square(n,[])
        return result
2.
class Solution:
    def numSquares(self, n: int) -> int:
        square_nums = [i**2 for i in range(0, int(math.sqrt(n))+1)]
        res = [float('inf') for _ in range(n+1)]
        res[0] = 0
        for i in range(1, n+1):
            for square in square_nums:
                if i < square:
                    break
                res[i] = min(res[i], res[i-square]+1)
        return res[-1]
3.

class Solution:
    def numSquares(self, n: int) -> int:
        square_nums = [i**2 for i in range(0, int(math.sqrt(n))+1)]
        
        def is_square(n,count):
            if count == 1:
                return n in square_nums
            for k in square_nums:
                if is_square(n - k, count - 1):
                    return True
            return False


        for i in range(1, n+1):
            if is_square(n,i):
                return i

题目283题

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

思路

双指针，一个指向当前，另一个指向非零

实现

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        notzero = 0
        for cur in range(len(nums)):
            if nums[cur] != 0:
                nums[cur],nums[notzero] = nums[notzero], nums[cur]
                notzero += 1

题目284题

顶端迭代器

给定一个迭代器类的接口，接口包含两个方法： next() 和 hasNext()。设计并实现一个支持 peek() 操作的顶端迭代器 -- 其本质就是把原本应由 next() 方法返回的元素 peek() 出来。

思路

实现

class PeekingIterator:
    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        self.container = []
        while iterator.hasNext():
            self.container.append(iterator.next())
        self.left = 0

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        return self.container[self.left]

        

    def next(self):
        """
        :rtype: int
        """
        self.left += 1
        return self.container[self.left-1]
        

    def hasNext(self):
        """
        :rtype: bool
        """
        return not self.left == len(self.container)

题目287题

寻找重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

思路

二分法

实现

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        size = len(nums)
        left, right = 1, size-1
        while left < right:
            mid = left + (right-left)//2
            cout = 0
            for num in nums:
                if num <= mid:
                    cout += 1
            if cout > mid:
                right = mid
            else:
                left = mid+1
        return left

题目237题

思路实现

题目237题

思路实现

题目237题

思路实现

题目237题

思路实现

题目237题

思路实现

题目237题

思路实现

题目237题

思路实现

题目237题

思路实现

题目237题

思路实现 

题目237题

思路实现

题目237题

思路实现

题目237题

思路实现