# leetcode

**Repository Path**: fearlessboy/leetcode

## Basic Information

- **Project Name**: leetcode
- **Description**: LeetCode的一些题解记录，包括一些资料等等
- **Primary Language**: 其他
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-08-20
- **Last Updated**: 2022-08-31

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

##### 15. 三数之和

题目：https://leetcode.cn/problems/3sum/

题解一：

```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        res = []
        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            j, k = i + 1, n - 1
            while j < k:
                x = nums[i] + nums[j] + nums[k]
                if x == 0:
                    res.append([nums[i], nums[j], nums[k]])
                    while j < k and nums[k] == nums[k - 1]:
                        k -= 1
                    while j < k and nums[j] == nums[j + 1]:
                        j += 1
                    j += 1
                    k -= 1
                elif x < 0:
                    j += 1
                else:
                    k -= 1
        return res
```

##### 21. 合并两个有序链表

题目：https://leetcode.cn/problems/merge-two-sorted-lists/

题解一：

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        tail, p, q = dummy, list1, list2
        while p and q:
            if p.val < q.val:
                tail.next = p
                p = p.next
            else:
                tail.next = q
                q = q.next
            tail = tail.next
        tail.next = p or q or None
        return dummy.next
```

##### [33. 搜索旋转排序数组\*](<题解/33. 搜索旋转排序数组.md>)

##### 34. 在排序数组中查找元素的第一个和最后一个位置

题目：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

题解一：

```python
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = bisect_left(nums, target)
        if left >= len(nums) or nums[left] != target:
            return [-1, -1]
        return [left, bisect_right(nums, target) - 1]
```

##### 82. 删除排序链表中的重复元素 II

题目：https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/

题解一：

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(None)
        cur = head
        p = dummy
        while cur:
            if not cur.next or cur.next.val != cur.val:
                p.next = cur
                cur = cur.next
                p = p.next
            elif cur.next.val == cur.val:
                val = cur.val
                while cur and cur.val == val:
                    cur = cur.next
        p.next = None
        return dummy.next
```

##### 74. 搜索二维矩阵

题目：https://leetcode.cn/problems/search-a-2d-matrix/

题解一：

```python
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        r, c = len(matrix), len(matrix[0] or [])
        lo, hi, mid = 0, r * c - 1, 0
        while lo <= hi:
            mid = (lo + hi) >> 1
            if target == matrix[mid // c][mid % c]:
                return True
            elif target < matrix[mid // c][mid % c]:
                hi = mid - 1
            else:
                lo = mid + 1
        return False
```

##### 153. 寻找旋转排序数组中的最小值

题目：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/

题解一：

```python
class Solution:
    def findMin(self, nums: List[int]) -> int:
        lo, hi, mid = 0, len(nums) - 1, 0
        while lo < hi:
            mid = (lo + hi) >> 1
            if nums[mid] < nums[hi]:
                hi = mid
            else:
                lo = mid + 1
        return nums[lo]
```

##### 162. 寻找峰值

题目：https://leetcode.cn/problems/find-peak-element/

题解一：

```python
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = lo + (hi - lo >> 1)
            if nums[mid] < nums[mid + 1]:
                lo = mid + 1
            else:
                hi = mid
        return lo
```

##### 205. 同构字符串

题目：https://leetcode.cn/problems/isomorphic-strings/

题解一：

```python
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        ms, mt = {}, {}
        for i, ch in enumerate(s):
            if ms.get(ch) and ms.get(ch) != t[i]:
                return False
            ms.setdefault(ch, t[i])
            ch = t[i]
            if mt.get(ch) and mt.get(ch) != s[i]:
                return False
            mt.setdefault(ch, s[i])
        return True
```

##### 206. 反转链表

题目：https://leetcode.cn/problems/reverse-linked-list/

题解一：

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, cur, next = None, head, None
        while cur:
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        return prev
```

##### 392. 判断子序列

题目：https://leetcode.cn/problems/is-subsequence/

```python
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if not s:
            return True
        if not t:
            return False
        if s[0] == t[0]:
            return self.isSubsequence(s[1:], t[1:])
        return self.isSubsequence(s, t[1:])
```

##### 654. 最大二叉树

题目：https://leetcode.cn/problems/maximum-binary-tree/

题解一：

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:

        def loc(lo: int, hi: int) -> int:
            max, p = nums[lo], lo
            for i in range(lo, hi + 1):
                if nums[i] > max:
                    max, p = nums[i], i
            return p                

        def construct(lo: int, hi: int) -> TreeNode:
            if hi < lo:
                return None
            if lo == hi:
                return TreeNode(nums[lo])
            p = loc(lo, hi)
            root = TreeNode(nums[p])
            root.left = construct(lo, p - 1)
            root.right = construct(p + 1, hi)
            return root
        return construct(0, len(nums) - 1)

```

##### 655. 输出二叉树

题目：https://leetcode.cn/problems/print-binary-tree/

题解一：

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
        
        def height(root: Optional[TreeNode]) -> int:
            if not root:
                return 0
            return 1 + max(height(root.left), height(root.right))
        h = height(root)
        w = (1 << h) - 1
        res = [[""] * w for _ in range(h)]
        def fill(root: Optional[TreeNode], h, lo, hi):
            if not root:
                return
            mid = lo + hi >> 1
            res[h][mid] = str(root.val)
            fill(root.left, h + 1, lo, mid - 1)
            fill(root.right, h + 1, mid + 1, hi)
        
        fill(root, 0, 0, w - 1)
        return res
```

##### 724. 寻找数组的中心下标

题目：https://leetcode.cn/problems/find-pivot-index/

题解一：

```python
class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # sum, running sum
        s, rs = sum(nums), 0
        for i in range(len(nums)):
            if (rs * 2 + nums[i] == s):
                return i
            rs += nums[i]
        return -1
```



##### 1455. 检查单词是否为句中其他单词的前缀

题目：https://leetcode.cn/problems/check-if-a-word-occurs-as-a-prefix-of-any-word-in-a-sentence/

题解一：

```python
class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        words = sentence.split(' ')
        for i, w in enumerate(words):
            if w.startswith(searchWord):
                return i + 1
        return -1
```



##### 1480. 一维数组的动态和

题目：https://leetcode.cn/problems/running-sum-of-1d-array/

题解一：

```python
class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        sums = [nums[0]] * len(nums)
        for i in range(1, len(nums)):
            sums[i] = sums[i - 1] + nums[i]
        return sums
```