leetcode（2）

缺乏、安全感 2022-03-09 09:42 152阅读 0赞

**目录**

1.实现strStr()方法

2.全排列

3.搜索插入位置

4.报数

53.最大子序和

58.最后一个单词的长度

66.加一

67.二进制求和

69 X 的平方根

--------------------

### 1.实现strStr()方法 ###

实现 [strStr()][strStr] 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 **-1**。

**示例 1:**

输入: haystack = "hello", needle = "ll"
    输出: 2

**示例 2:**

输入: haystack = "aaaaa", needle = "bba"
    输出: -1

**说明:**

当 `needle` 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

class Solution(object):
        def strStr(self, haystack, needle):
            """
            :type haystack: str
            :type needle: str
            :rtype: int
            """
            if needle == "":
                return 0
            for i in range(len(haystack) - len(needle) + 1):
                if haystack[i: i + len(needle)] == needle:
                    return i
            return -1

为什么需要加1

st = "hell0"
    print(st[1:8])
    print(st[1:2])  #最后一位是 小括号的 打印出 e

### 2.全排列 ###

给定一个**没有重复**数字的序列，返回其所有可能的全排列。

**示例:**

输入: [1,2,3]
    输出:
    [
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,1,2],
      [3,2,1]
    ]

#全排列
    num = [1, 2 ,3]
    print(num[: 0] + num[1: ])   #返回的是数组 [1, 3]
    print(num[1] + num[2])
    
    nums = [1, 2 ,3]
    class Solution(object):
        def permute(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            if len(nums) <= 1:
                return [nums]   #退出递归的条件
            
            result = []
            for i, num in enumerate(nums):
                n = nums[ :i] + nums[i+1: ] #选择除了第 i 位的元素的数组
                print(n)
                for y in self.permute(n):
                    print("this is y: " + str(y))
                    result.append([num] + y)    #第一次是选定了 num值，为 1， 则n 为[2, 3]
            return result 
        
    s = Solution()
    print(s.permute(nums))

### 3.搜索插入位置 ###

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

**示例 1:**

输入: [1,3,5,6], 5
    输出: 2

**示例 2:**

输入: [1,3,5,6], 2
    输出: 1

**示例 3:**

输入: [1,3,5,6], 7
    输出: 4

**示例 4:**

输入: [1,3,5,6], 0
    输出: 0

class Solution(object):
        def searchInsert(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            if target > nums[len(nums) - 1]:
                return len(nums)
            
            for i in range(len(nums)):
                if nums[i] >= target:
                    return i

### 4.报数 ###

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1.     1
    2.     11
    3.     21
    4.     1211
    5.     111221

`1` 被读作 `"one 1"` (`"一个一"`) , 即 `11`。  
`11` 被读作 `"two 1s"` (`"两个一"`）, 即 `21`。  
`21` 被读作 `"one 2"`, "`one 1"` （`"一个二"` , `"一个一"`) , 即 `1211`。

给定一个正整数 *n*（1 ≤ *n* ≤ 30），输出报数序列的第 *n* 项。

注意：整数顺序将表示为一个字符串。

# 1.     1
    # 2.     11
    # 3.     21
    # 4.     1211
    # 5.     111221
    class Solution(object):
        def countAndSay(self, n):
            """
            :type n: int
            :rtype: str
            """
            seq = '1'
            for i in range(n-1):    #此处需要将 n 减去 1
                seq = self.getSeq(seq)
            return seq
        
        def getSeq(self, seq):
            i, result_seq = 0, ''  
            while i < len(seq):
                count = 1   #重置 count
                while i < len(seq)-1 and seq[i] == seq[i+1]:    # 计算相同的元素的值的个数
                    count += 1
                    i += 1
                result_seq += str(count) + seq[i]   # 添加到字符串中
                i += 1
            return result_seq
                
    s = Solution()        
    print(s.countAndSay(4))

### 53.最大子序和 ###

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

**示例:**

输入: [-2,1,-3,4,-1,2,1,-5,4],
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

#最大子序列和
    nums = [-2,1,-3,4,-1,2,1,-5,4]
    
    class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if max(nums) < 0:   #如果列表中全部元素小于 0 ，则最大的就是最大的负数
                return max(nums)
            
            local_num, global_num = 0, 0
            for num in nums:
                local_num = max(0, local_num + num)
                global_num = max(local_num, global_num) #始终保存着最大的数值
                
            return global_num 
        
    s = Solution()         
    print(s.maxSubArray(nums))

方法2：

class Solution(object):
        def maxSubArray(self, nums):
            sum = 0
            max_sub_sum = nums[0]
            for num in nums:
                sum += num
                if sum > max_sub_sum:
                    max_sub_sum = sum
                if sum < 0:
                    sum = 0
            return max_sub_sum

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

给定一个仅包含大小写字母和空格 `' '` 的字符串，返回其最后一个单词的长度。

如果不存在最后一个单词，请返回 0 。

**说明：**一个单词是指由字母组成，但不包含任何空格的字符串。

**示例:**

输入: "Hello World"
    输出: 5

s = "Hello World hha"
    
    class Solution(object):
        def lengthOfLastWord(self, s):
            """
            :type s: str
            :rtype: int
            """
            count , final_count = 0, 0
            for i in range(len(s)):
                if s[i] == ' ':
                    count = 0
                else:
                    count += 1
                    final_count = count #用来保存最后一次的输出值
            return final_count 
        
    sa = Solution()
    print(sa.lengthOfLastWord(s))

### 66.加一 ###

给定一个由**整数**组成的**非空**数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

**示例 1:**

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

**示例 2:**

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

digits = [9, 9, 9]
    class Solution(object):
        def plusOne(self, digits):
            """
            :type digits: List[int]
            :rtype: List[int]
            """
            for i in reversed(range(len(digits))):
                if digits[i] == 9:
                    digits[i] = 0
                else:
                    digits[i] += 1
                    return digits   #退出函数
            #如果是999的情况下
            digits[0] = 1
            digits.append(0)
            return digits 
    s = Solution() 
    print(s.plusOne(digits))
        
    # for i in range(len(digits)-1, -1, -1):
    #     print(i)
    # for i in reversed(range(len(digits))):
    #     print("reversed", i)

### 67.二进制求和 ###

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为**非空**字符串且只包含数字 `1` 和 `0`。

**示例 1:**

输入: a = "11", b = "1"
    输出: "100"

**示例 2:**

输入: a = "1010", b = "1011"
    输出: "10101"

# 输入: a = "1010", b = "1011"
    # 输出: "10101"
    
    a = "1010"
    b = "1011"
    class Solution(object):
        def addBinary(self, a, b):
            """
            :type a: str
            :type b: str
            :rtype: str
            """
            #从后面开始进行计算，carry保存着进一位的值
            result, val, carry = "", 0, 0
            for i in range(max(len(a), len(b))):
                val = carry
                if i < len(a):
                    val += int(a[-(i+1)])
                if i < len(b):
                    val += int(b[-(i+1)])
                    
                carry, val = val//2, val % 2  #保存进制位，并计算进制val
                result += str(val)
            
            if carry:
                result += str(1)
            return result[::-1]
        
    s = Solution()            
    print(s.addBinary(a, b))
    
    # for i in range(len(a)):
    #     print(a[-(i+1)])
    print(b[::-1])    
    print(1%2)

### 69 X 的平方根 ###

实现 `int sqrt(int x)` 函数。

计算并返回 *x* 的平方根，其中 *x* 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

**示例 1:**

输入: 4
    输出: 2

**示例 2:**

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

x = 16
    class Solution(object):
        def mySqrt(self, x):
            """
            :type x: int
            :rtype: int
            """
            if x < 2:
                return x 
            
            left, right = 1, x //2
            while left <= right:
                mid = (left + right) // 2   # 取最中间的数值
                if mid > x / mid:
                    right = mid-1
                else:
                    left = mid + 1
            print(right)
                   
            return left-1
    s = Solution()
    print(s.mySqrt(x))

151.翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

**示例 1：**

输入: "the sky is blue"
    输出: "blue is sky the"

**示例 2：**

输入: "  hello world!  "
    输出: "world! hello"
    解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

**示例 3：**

输入: "a good   example"
    输出: "example good a"
    解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

**说明：**

*  无空格字符构成一个单词。
 *  输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 *  如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

s = "a good   example"
    class Solution(object):
        def reverseWords(self, s):
            """
            :type s: str
            :rtype: str
            """
            if s == "":
                return s 
            
            ls = s.split()
            if ls == []:
                return ""
            
            result = ""
            for i in range(len(ls)):
                if i == len(ls)-1:  #由于最后一项不能有 空字符串
                    result += ls[len(ls)-1-i]
                else:
                    result += ls[len(ls)-1-i] + " "
            return result 
        
    s1 = Solution()
    print(s1.reverseWords(s))
    
    # print(s.split())
    # print(s.strip())
    # for i in s.split():
    #     print(i)

[strStr]: https://baike.baidu.com/item/strstr/811469