LeetCode简单题目(#118 #119 #121 #122 #125 #136 #141 #155)-8道

分手后的思念是犯贱 2023-05-30 08:44 43阅读 0赞

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

### 文章目录 ###

*  118 杨辉三角
 *   *  描述
     *  代码
     *  官方解答
 *  119 杨辉三角II
 *   *  描述
     *  代码
     *  大神解法
 *  121 买卖股票的最佳时机
 *   *  描述
     *  代码
     *  大神解法
 *  122 买卖股票的最佳时机 II
 *   *  描述
     *  代码
     *  大神解法-贪心算法
 *  125 验证回文串
 *   *  描述
     *  代码
 *  136 只出现一次的数字
 *   *  描述
     *  代码
     *  众多解法
     *  大神解法-异或
     *  大神解法-妙
 *  141 环形链表
 *   *  描述
     *  代码
     *  大神解法
 *  155 最小栈
 *   *  描述
     *  代码
     *  大神解法

# 118 杨辉三角 #

## 描述 ##

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。  
在杨辉三角中，每个数是它左上方和右上方的数的和。

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

## 代码 ##

def generate(self, numRows: int) -> List[List[int]]:
        all_list = []
        cur_list,last_list = [1],[1]
        for i in range(numRows):
            all_list.append(last_list)
            cur_list = [1]
            for j in range(i+1):
                if j < i:
                    cur_list.append(last_list[j]+last_list[j+1])
            cur_list.append(1)
            last_list = cur_list
    
        return all_list

## 官方解答 ##

> https://leetcode-cn.com/problems/pascals-triangle/solution/yang-hui-san-jiao-by-leetcode/

# 119 杨辉三角II #

## 描述 ##

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。  
在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:  
输入: 3  
输出: \[1,3,3,1\]  
进阶：  
你可以优化你的算法到 O(k) 空间复杂度吗？

## 代码 ##

class Solution:
        def getRow(self, rowIndex: int) -> List[int]:
            cur_list,last_list = [1],[1]
            for i in range(rowIndex):
                cur_list = [1]
                for j in range(i+1):
                    if j < i:
                        cur_list.append(last_list[j]+last_list[j+1])
                cur_list.append(1)
                last_list = cur_list
    
            return cur_list

## 大神解法 ##

> 作者：leicj  
> 链接：https://leetcode-cn.com/problems/pascals-triangle-ii/solution/python3-yang-hui-san-jiao-ii-by-leicj/

def getRow(rowIndex):
        # j行的数据, 应该由j - 1行的数据计算出来.
        # 假设j - 1行为[1,3,3,1], 那么我们前面插入一个0(j行的数据会比j-1行多一个),
        # 然后执行相加[0+1,1+3,3+3,3+1,1] = [1,4,6,4,1], 最后一个1保留即可.
        r = [1]
        for i in range(1, rowIndex + 1):
            r.insert(0, 0)
            # 因为i行的数据长度为i+1, 所以j+1不会越界, 并且最后一个1不会被修改.
            for j in range(i):
                r[j] = r[j] + r[j + 1]
        return r

# 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:
        def maxProfit(self, prices: List[int]) -> int:
            buy_price = prices[0] if len(prices) else 0
            max_profit = 0
            for i in range(len(prices)-1):
                if buy_price > prices[i]:
                    buy_price = prices[i]
                if prices[i+1] > prices[i]:
                    max_profit = max(prices[i+1]-prices[i],prices[i+1]-buy_price,max_profit)
                
            return max_profit

## 大神解法 ##

> https://leetcode-cn.com/u/gaussic/

class Solution:
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            min_p, max_p = 999999, 0
            for i in range(len(prices)):
                min_p = min(min_p, prices[i])
                max_p = max(max_p, prices[i] - min_p)
            return max_p

# 122 买卖股票的最佳时机 II #

## 描述 ##

给定一个数组，它的第 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 天接连购买股票，之后再将它们卖出。  
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

## 代码 ##

class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            buy_price = prices[0] if len(prices) else 0
            max_profit,max_sum_profit = 0,0
            for i in range(len(prices)-1):
                if buy_price > prices[i]:
                    buy_price = prices[i]
                if prices[i+1] > prices[i]:
                    max_sum_profit += prices[i+1]-prices[i]
                    max_profit = max(prices[i+1]-prices[i],prices[i+1]-buy_price,max_profit)
                
            return max(max_profit,max_sum_profit)

## 大神解法-贪心算法 ##

> 作者：jyd  
> 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/best-time-to-buy-and-sell-stock-ii-zhuan-hua-fa-ji/

class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            profit = 0
            for i in range(1, len(prices)):
                tmp = prices[i] - prices[i - 1]
                if tmp > 0: profit += tmp
            return profit

# 125 验证回文串 #

## 描述 ##

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。  
说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:  
输入: “A man, a plan, a canal: Panama”  
输出: true  
示例 2:  
输入: “race a car”  
输出: false

## 代码 ##

class Solution:
        def isPalindrome(self, s: str) -> bool:
            join_str = ''.join([i for i in s.lower() if i.isalnum()])
            return join_str == join_str[::-1]

# 136 只出现一次的数字 #

## 描述 ##

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。  
说明：  
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:  
输入: \[2,2,1\]  
输出: 1  
示例 2:  
输入: \[4,1,2,1,2\]  
输出: 4

## 代码 ##

class Solution:
        def singleNumber(self, nums: List[int]) -> int:
            nums_dic = {
        i:0 for i in nums}
            for n in nums:
                nums_dic[n] += 1
            for k in nums_dic:
                if nums_dic[k] == 1:
                    return k

## 众多解法 ##

> https://leetcode-cn.com/problems/single-number/solution/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode/

## 大神解法-异或 ##

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

## 大神解法-妙 ##

> https://leetcode-cn.com/u/tuotuoli/

class Solution:
        def singleNumber(self, nums: List[int]) -> int:
            return sum(set(nums))*2-sum(nums)

# 141 环形链表 #

## 描述 ##

给定一个链表，判断链表中是否有环。  
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：  
输入：head = \[3,2,0,-4\], pos = 1  
输出：true  
解释：链表中有一个环，其尾部连接到第二个节点。  
示例 2：  
输入：head = \[1,2\], pos = 0  
输出：true  
解释：链表中有一个环，其尾部连接到第一个节点。  
示例 3：  
输入：head = \[1\], pos = -1  
输出：false  
解释：链表中没有环。  
进阶：  
你能用 O(1)（即，常量）内存解决此问题吗？

## 代码 ##

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            if not head: return False
            node_list = [head]
            while head.next:
                if head.next in node_list:
                    return True
                node_list.append(head.next)
                head = head.next
            return False

## 大神解法 ##

> https://leetcode-cn.com/u/yybeta/

class Solution:
        def hasCycle(self, head):
            if not head:
                return False
            while head.next and head.val != None:
                head.val = None  # 遍历的过程中将值置空
                head = head.next
            if not head.next:  # 如果碰到空发现已经结束，则无环
                return False
            return True  # 否则有环

# 155 最小栈 #

## 描述 ##

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。  
push(x) – 将元素 x 推入栈中。  
pop() – 删除栈顶的元素。  
top() – 获取栈顶元素。  
getMin() – 检索栈中的最小元素。  
示例:

MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin();   --> 返回 -3.
    minStack.pop();
    minStack.top();      --> 返回 0.
    minStack.getMin();   --> 返回 -2.

## 代码 ##

class MinStack:
        import math
        def __init__(self):
            """
            initialize your data structure here.
            """
            self.stack = []
            self.temp_num = 0
            # self.sort_list = []
            self.min_num = math.inf
    
        def push(self, x: int) -> None:
            self.stack.append(x)
            self.min_num = min(self.stack)
    
        def pop(self) -> None:
            self.temp_num = self.stack.pop()
            if self.stack:
                self.min_num = min(self.stack)
            return self.temp_num
    
        def top(self) -> int:
            return self.stack[-1]
    
        def getMin(self) -> int:
            return self.min_num
    
    # Your MinStack object will be instantiated and called as such:
    # obj = MinStack()
    # obj.push(x)
    # obj.pop()
    # param_3 = obj.top()
    # param_4 = obj.getMin()

## 大神解法 ##

> 作者：liweiwei1419  
> 链接：https://leetcode-cn.com/problems/min-stack/solution/shi-yong-fu-zhu-zhan-tong-bu-he-bu-tong-bu-python-/

class MinStack:
    
        # 辅助栈和数据栈同步
        # 思路简单不容易出错
    
        def __init__(self):
            # 数据栈
            self.data = []
            # 辅助栈
            self.helper = []
    
        def push(self, x):
            self.data.append(x)
            if len(self.helper) == 0 or x <= self.helper[-1]:
                self.helper.append(x)
            else:
                self.helper.append(self.helper[-1])
    
        def pop(self):
            if self.data:
                self.helper.pop()
                return self.data.pop()
    
        def top(self):
            if self.data:
                return self.data[-1]
    
        def getMin(self):
            if self.helper:
                return self.helper[-1]