leetcode（3）

Love The Way You Lie 2022-03-08 01:24 107阅读 0赞

**目录**

2.两数相加

70.爬楼梯

83.删除有序链表中的重复元素

88合并两个有序的数组

118.杨辉三角

119. 杨辉三角 II

121.买卖股票的最佳时机

122.买卖股票的最佳时机2

125.验证回文串

136.只出现一次的数字

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

### 2.两数相加 ###

给出两个 **非空** 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 **逆序** 的方式存储的，并且它们的每个节点只能存储 **一位** 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

**示例：**

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 0 -> 8
    原因：342 + 465 = 807

# Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            if l1 is None:
                return l2
            if l2 is None:
                return l1 
            
            carry = 0    
            dummy = ListNode(0)    #先设置第一个节点值为0
            p = dummy # dummy保存着第一个节点指针
            while l1 and l2:
                p.next = ListNode((l1.val + l2.val + carry) %10)
                carry = (l1.val + l2.val + carry) // 10
                l1 = l1.next 
                l2 = l2.next 
                p = p.next 
                
            if l1:    #如果l1的长度大于l2
    
                while l1:
                    p.next = ListNode((l1.val + carry)%10)
                    carry = (l1.val + carry)  // 10
                    l1= l1.next 
                    p = p.next 
            if l2:
                while l2:
                    p.next = ListNode((l2.val + carry)%10)
                    carry = (l2.val + carry) //10
                    l2 = l2.next 
                    p = p.next 
                
            if  carry:
                p.next = ListNode(1)
            return dummy.next

### 70.爬楼梯 ###

假设你正在爬楼梯。需要 *n* 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

**注意：**给定 *n* 是一个正整数。

**示例 1：**

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

**示例 2：**

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

class Solution(object):
        def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            pre, cur = 0, 1
            for i in range(n):
                pre, cur = cur, pre+ cur 
            return cur

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

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

**示例 1:**

输入: 1->1->2
    输出: 1->2

**示例 2:**

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

# Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def deleteDuplicates(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            cur = head 
            
            while cur:
                runner = cur.next 
                while runner and cur.val == runner.val:
                    runner = runner.next 
                cur.next = runner #相当于删除了重复的元素
                cur = runner #重新更新cur
            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]

class Solution(object):
        def merge(self, nums1, m, nums2, n):
            """
            :type nums1: List[int]
            :type m: int
            :type nums2: List[int]
            :type n: int
            :rtype: None Do not return anything, modify nums1 in-place instead.
            """
            #从两有序数组的最后数组开始比较
            while m > 0 and n > 0:
                if nums1[m-1] < nums2[n-1]:
                    nums1[m-1+n] = nums2[n-1]
                    n -= 1
                else:
                    nums1[m-1+n], nums1[m-1] = nums1[m-1], nums1[m-1+n]
                    m -= 1
            if m == 0 and n > 0:
                nums1[:n] = nums2[:n]

### 118.杨辉三角 ###

给定一个非负整数 *numRows，*生成杨辉三角的前 *numRows* 行。

![PascalTriangleAnimated2.gif][]

在杨辉三角中，每个数是它左上方和右上方的数的和。

**示例:**

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

class Solution(object):
        def generate(self, numRows):
            """
            :type numRows: int
            :rtype: List[List[int]]
            """
            result = []
            
            for i in range(numRows):    #代表有几行
                result.append([])
                for j in range(i+1):
                    if j in (0, i): #如果是边界
                        result[i].append(1)
                    else:
                        result[i].append(result[i-1][j-1] + result[i-1][j]) #前一行的两个元素相加
            return result

### [119. 杨辉三角 II][119. _ II] ###

给定一个非负索引 *k*，其中 *k* ≤ 33，返回杨辉三角的第 *k* 行。

![PascalTriangleAnimated2.gif][]

在杨辉三角中，每个数是它左上方和右上方的数的和。

下一行的第j 个元素等于上一行的第 j 个元素和 j-1个元素相加

**示例:**

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

class Solution(object):
        def getRow(self, rowIndex):
            """
            :type rowIndex: int
            :rtype: List[int]
            """
            result = [1] + [0] * rowIndex
            
            for i in range(rowIndex):
                result[0] = 1
                for j in range(i+1, 0, -1): #此时result[i+1]必定是 0 
                    result[j] = result[j] + result[j-1]
                    
            return result

### 121.买卖股票的最佳时机 ###

给定一个数组，它的第 *i* 个元素是一支给定股票第 *i* 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

**示例 1:**

输入: [7,1,5,3,6,4]
    输出: 5
    解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
         注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

**示例 2:**

输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            max_profit, min_price = 0, float('inf')
            
            for price in prices:
                min_price = min(price, min_price)   #找到数组中最小的数值
                max_profit = max(max_profit, price - min_price) #使用当前值减去最小值，取最大的
                
            return max_profit

### 122.买卖股票的最佳时机2 ###

给定一个数组，它的第 *i* 个元素是一支给定股票第 *i* 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

**示例 1:**

输入: [7,1,5,3,6,4]
    输出: 7
    解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
         随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

**示例 2:**

输入: [1,2,3,4,5]
    输出: 4
    解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
         注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
         因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

**示例 3:**

输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            
            if len(prices) <= 1:
                return 0
            
            result = 0
            for i in range(1, len(prices)):
                if prices[i] > prices[i-1]: #找到后一项比前一项大的数
                    result += prices[i] - prices[i-1]
                    
            return result

### 125.验证回文串 ###

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

**说明：**本题中，我们将空字符串定义为有效的回文串。

**示例 1:**

输入: "A man, a plan, a canal: Panama"
    输出: true

**示例 2:**

输入: "race a car"
    输出: false

class Solution(object):
        def isPalindrome(self, s):
            """
            :type s: str
            :rtype: bool
            """
            
            i, j = 0, len(s)-1
            while i < j:
                while i < j and not s[i].isalnum():
                    i += 1
                while i < j and not s[j].isalnum(): #判断是否是 空格或其他标点
                    j -= 1
                    
                if s[i].lower() != s[j].lower(): # 将字母全部转换成小写字母
                    return False
                else:
                    i += 1
                    j -= 1
                
            return True

### 136.只出现一次的数字 ###

给定一个**非空**整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

**说明：**

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

**示例 1:**

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

**示例 2:**

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

\#使用异或来解决

0^4 = 4

4^1 = 5

5^2 = 7

7^1 = 6 \#再次出现相同的数字则减去

6^2 = 4

class Solution(object):
        def singleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            a = 0
            for num in nums:
                a = a ^ num 
            return a

[PascalTriangleAnimated2.gif]: /images/20220308/da954cfc321d40089973a83e0ec1785f.png
[119. _ II]: https://leetcode-cn.com/problems/pascals-triangle-ii/