leetcode做题笔记42

**LeetCode 做题笔记42**

**前言**

本文是 LeetCode 做题笔记的第42 部分。我们将在这里记录一些常见的问题、解法思路以及相关的代码示例。

**1.两数之和 (Add Two Numbers)*** **问题描述**: 给定两个非负整数 num1 和 num2，返回它们的和。
* **示例**:

| num1 | num2 | 返回值 |
| --- | --- | --- |
|5 |0 |5 |
|3 |4 |7 |

* **解法思路**: 我们可以将两个数字转换为链表，然后进行相加。
* **代码示例**:

# Definition for singly-linked list.
class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef addTwoNumbers(l1, l2):
 dummyHead = ListNode(0)
 p, q = dummyHead, l1 carry =0 while q != None:
 x = q.val if q else0 y = p.next.val if p.next else0 sum = carry + x + y carry = sum //10 sum %=10 p.next = ListNode(sum)
 p = p.next q = q.next if carry >0:
 p.next = ListNode(carry)
 return dummyHead.next# Test the functionl1 = ListNode(5)
l2 = ListNode(0)

l1.next = ListNode(3)
l2.next = ListNode(4)

result = addTwoNumbers(l1, l2)

while result != None:
 print(result.val, end=" ")
 result = result.next# Output:70

**2. 最长公共前缀 (Longest Common Prefix)*** **问题描述**: 给定一个字符串数组 strs，返回其最长公共前缀。
* **示例**:

| strs | 返回值 |
| --- | --- |
| ["flower","flow","flight"] | "fl" |

* **解法思路**: 我们可以使用 Trie 来存储所有的字符串，然后找到最长公共前缀。
* **代码示例**：

class TrieNode:
 def __init__(self):
 self.children = {}
 self.is_word = Falsedef longestCommonPrefix(strs):
 root = TrieNode()
 for word in strs:
 node = root for char in word:
 if char not in node.children:
 node.children[char] = TrieNode()
 node = node.children[char]
 node.is_word = True prefix = ""
 node = root while len(node.children) ==1 and node.is_word:
 char = next(iter(node.children))
 prefix += char node = node.children[char]
 return prefix# Test the functionstrs = ["flower","flow","flight"]

result = longestCommonPrefix(strs)

print(result) # Output: "fl"

**3. 最长回文子串 (Longest Palindromic Substring)*** **问题描述**: 给定一个字符串 s，返回其最长回文子串。
* **示例**:

| s | 返回值 |
| --- | --- |
| "babad" | "bab" |

* **解法思路**: 我们可以使用动态规划来找到最长回文子串。
* **代码示例**：

def longestPalindrome(s):
 n = len(s)
 # Initialize the dp table dp = [[False] * n for _ in range(n)]
 max_length =1 start =0 # Fill the dp table for i in range(n -1, -1, -1):
 for j in range(i, n):
 if s[i] == s[j]:
 if j - i < 2:
 dp[i][j] = True else:
 dp[i][j] = dp[i +1][j -1]
 # Update the maximum length and start position if dp[i][j] and (j - i +1) > max_length:
 max_length = j - i +1 start = i return s[start:start + max_length]

# Test the functions = "babad"

result = longestPalindrome(s)

print(result) # Output: "bab"

**4. 最小栈 (Min Stack)*** **问题描述**: 设计一个支持 `push`、`pop`、`top` 操作且在 `O(1)` 时间内找到最小元素的栈。
* **示例**:

| operation | stack |
| --- | --- |
| push(-2) | [-2] |
| pop() | [] |
| top() | -2 |

* **解法思路**: 我们可以使用两个栈来实现最小栈。
* **代码示例**：

class MinStack:
 def __init__(self):
 self.stack = []
 self.min_stack = []

 def push(self, x: int) -> None:
 self.stack.append(x)
 # Update the min stack if not self.min_stack or x <= self.min_stack[-1]:
 self.min_stack.append(x)

 def pop(self) -> None:
 if self.stack:
 popped = self.stack.pop()
 # Update the min stack if popped == self.min_stack[-1]:
 self.min_stack.pop()

 def top(self) -> int:
 return self.stack[-1]

 def getMin(self) -> int:
 return self.min_stack[-1]

# Test the functionminStack = MinStack()
minStack.push(-2)
print(minStack.getMin()) # Output: -2minStack.pop()
print(minStack.top()) # Output: -2

**5. 最大栈 (Max Stack)*** **问题描述**: 设计一个支持 `push`、`pop`、`top` 操作且在 `O(1)` 时间内找到最大元素的栈。
* **示例**:

| operation | stack |
| --- | --- |
| push(-2) | [-2] |
| pop() | [] |
| top() | -2 |

* **解法思路**: 我们可以使用两个栈来实现最大栈。
* **代码示例**：

class MaxStack:
 def __init__(self):
 self.stack = []
 self.max_stack = []

 def push(self, x: int) -> None:
 self.stack.append(x)
 # Update the max stack if not self.max_stack or x >= self.max_stack[-1]:
 self.max_stack.append(x)

 def pop(self) -> None:
 if self.stack:
 popped = self.stack.pop()
 # Update the max stack if popped == self.max_stack[-1]:
 self.max_stack.pop()

 def top(self) -> int:
 return self.stack[-1]

 def getMax(self) -> int:
 return self.max_stack[-1]

# Test the functionmaxStack = MaxStack()
maxStack.push(-2)
print(maxStack.getMax()) # Output: -2maxStack.pop()
print(maxStack.top()) # Output: -2

**6. 最长上升子序列 (Longest Increasing Subsequence)*** **问题描述**: 给定一个整数数组 `nums`，返回其最长上升子序列的长度。
* **示例**:

| nums | 返回值 |
| --- | --- |
| [10,9,2,5,3,7,101,18] |4 |

* **解法思路**: 我们可以使用动态规划来找到最长上升子序列的长度。
* **代码示例**：

def lengthOfLIS(nums):
 n = len(nums)
 # Initialize the dp table dp = [1] * n for i in range(n -1, -1, -1):
 for j in range(i +1, n):
 if nums[i] < nums[j]:
 dp[i] = max(dp[i], dp[j] +1)
 return max(dp)

# Test the functionnums = [10,9,2,5,3,7,101,18]

result = lengthOfLIS(nums)

print(result) # Output:4

**7. 最长回文子序列 (Longest Palindromic Subsequence)*** **问题描述**: 给定一个整数数组 `nums`，返回其最长回文子序列的长度。
* **示例**:

| nums | 返回值 |
| --- | --- |
| [1,3,5,7] |4 |

*