LeetCode简单题目(#53 #58 #66 #67 #69 #70 #83 #88)-8道

逃离我推掉我的手 2023-06-11 04:30 5阅读 0赞

> leetcode题库中共有350道简单题目。  
> 本文记录已解决的题目和代码。  
> 本文中的序号是leetcode题目中的真实序号。

### 文章目录 ###

*  53 最大子序和
 *   *  描述
     *  代码
     *  大佬代码
 *  58 最后一个单词的长度
 *   *  描述
     *  代码
 *  66 加一
 *   *  描述
     *  代码
 *  67 二进制求和
 *   *  描述
     *  代码
 *  69 x的平方根
 *   *  描述
     *  代码
     *  大牛解法
     *  牛顿迭代法
 *  70 爬楼梯
 *   *  描述
     *  代码
     *  大神多种解法
 *  83 删除排序链表中的重复元素
 *   *  描述
     *  代码
 *  88 合并两个有序数组
 *   *  描述
     *  代码
     *  大牛更多解法

# 53 最大子序和 #

## 描述 ##

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:  
输入: \[-2,1,-3,4,-1,2,1,-5,4\] 输出: 6  
解释: 连续子数组 \[4,-1,2,1\] 的和最大，为 6。  
进阶:  
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解

## 代码 ##

class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            sum_num,temp_max = 0,nums[0]
            for i in range(len(nums)):
                if sum_num > 0:
                    sum_num += nums[i]
                else:
                    sum_num = nums[i]
                if sum_num > temp_max:
                    temp_max = sum_num
            if temp_max > sum_num:
                return temp_max
            return sum_num

## 大佬代码 ##

class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
             """
            for i in range(1, len(nums)):
                nums[i]= nums[i] + max(nums[i-1], 0)
            return max(nums)

# 58 最后一个单词的长度 #

## 描述 ##

给定一个仅包含大小写字母和空格 ’ ’ 的字符串，返回其最后一个单词的长度。  
如果不存在最后一个单词，请返回 0 。  
说明：一个单词是指由字母组成，但不包含任何空格的字符串。

示例:  
输入: “Hello World”  
输出: 5

## 代码 ##

class Solution:
        def lengthOfLastWord(self, s: str) -> int:
            return len(s.split()[-1]) if s.strip() else 0

# 66 加一 #

## 描述 ##

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。  
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。  
你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:  
输入: \[1,2,3\]  
输出: \[1,2,4\]  
解释: 输入数组表示数字 123。  
示例 2:  
输入: \[4,3,2,1\]  
输出: \[4,3,2,2\]  
解释: 输入数组表示数字 4321。

## 代码 ##

class Solution:
        def plusOne(self, digits: List[int]) -> List[int]:
            digits_str = ''.join(str(i) for i in digits)
            return list(str(int(digits_str) + 1))
    
    # 1行解决
    class Solution:
        def plusOne(self, digits: List[int]) -> List[int]:
            return map(int, str(int(''.join(map(str,digits))) + 1))

# 67 二进制求和 #

## 描述 ##

给定两个二进制字符串，返回他们的和（用二进制表示）。  
输入为非空字符串且只包含数字 1 和 0。

示例 1:  
输入: a = “11”, b = “1”  
输出: “100”  
示例 2:  
输入: a = “1010”, b = “1011”  
输出: “10101”

## 代码 ##

class Solution:
        def addBinary(self, a: str, b: str) -> str:
            return bin(int(a,2) + int(b,2))[2:]

int(‘101’,2)可以把二进制字符串转换为十进制  
bin(1231)把十进制数字转换为二进制字符串（加前缀’0b’）  
见https://blog.csdn.net/u012063703/article/details/42609833

# 69 x的平方根 #

## 描述 ##

实现 int sqrt(int x) 函数。  
计算并返回 x 的平方根，其中 x 是非负整数。  
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:  
输入: 4  
输出: 2  
示例 2:  
输入: 8  
输出: 2  
说明: 8 的平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

## 代码 ##

def mySqrt(x: int) -> int:
        i = 0
        while i*i <= x:
            i += 1
        return int(i-1) if i > 1 or not x else 1

## 大牛解法 ##

https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/

## 牛顿迭代法 ##

class Solution:
        def mySqrt(self, x):
            """
            :type x: int
            :rtype: int
            """
            if x <= 1:
                return x
            r = x
            while r > x/r:
                r = (r + x/r) // 2
            return int(r)

# 70 爬楼梯 #

## 描述 ##

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。  
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？  
注意：给定 n 是一个正整数。

示例 1：  
输入： 2 输出： 2  
解释： 有两种方法可以爬到楼顶。

1.  1 阶 + 1 阶
2.  2 阶  
    示例 2：  
    输入： 3 输出： 3  
    解释： 有三种方法可以爬到楼顶。
3.  1 阶 + 1 阶 + 1 阶
4.  1 阶 + 2 阶
5.  2 阶 + 1 阶

## 代码 ##

# 动态规划解法
    class Solution:
        def climbStairs(self, n: int) -> int:
            a, b = 0, 1
            for i in range(n + 1):
                a, b = b, a + b
            return a

## 大神多种解法 ##

https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode/

# 83 删除排序链表中的重复元素 #

## 描述 ##

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:  
输入: 1->1->2  
输出: 1->2  
示例 2:  
输入: 1->1->2->3->3  
输出: 1->2->3

## 代码 ##

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def deleteDuplicates(self, head: ListNode) -> ListNode:
            temp_node = head
            while temp_node and temp_node.next:
                if temp_node.val == temp_node.next.val:
                    temp_node.next = temp_node.next.next
                else:
                    temp_node = temp_node.next
            return head

# 88 合并两个有序数组 #

## 描述 ##

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。  
说明:  
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。  
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:  
输入:  
nums1 = \[1,2,3,0,0,0\], m = 3  
nums2 = \[2,5,6\], n = 3  
输出: \[1,2,2,3,5,6\]

## 代码 ##

def merge(nums1,m, nums2, n):
        """
        Do not return anything, modify nums1 in-place instead.
        """
        i,j = 0,0
        while j < n and i < (m+n):
            if nums2[j] <= nums1[i]:
                nums1.insert(i,nums2[j])
                j += 1
                i += 1
            else:
                i += 1
        p = len(nums1) - 1
        while len(nums1) > (m+j) and not nums1[p]:
            nums1.pop()
            p -= 1
        nums1.extend(nums2[j:])

## 大牛更多解法 ##

https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetcode/