leetcode刷题记

leetcode刷题记

文章目录

• leetcode之两数之和(一)
• • 题目内容
  • 解题思路
  • • 暴力O(n^2)
    • 哈希表(O(n))
• leetcode之两数相加(二)
• • 题目内容
  • 解题思路
  • • O(n)
• leetcode之无重复字符的最长子串(三)
• • 题目内容
  • 解题思路
  • • 暴力(O(n^3))
    • 滑动窗口(O(n^2))
• leetcode之最长回文子串(四)
• • 题目内容
  • 解题思路
  • • O(n^2)
• leetcode之Z字形变换(五)
• • 题目内容
  • 解题思路
• leetcode之整数反转(六)
• • 题目内容
  • 解题思路
• leetcode之整数反转(七)
• • 题目内容
  • 解题思路
• leetcode之回文数(八)
• • 题目内容
  • 解题思路
• leetcode之盛最多水的容器(九)
• • 题目内容
  • 解题思路
  • • 暴力（O(n^2)）
    • 双指针
• leetcode之最长公共前缀(十)
• • 题目内容
  • 解题思路
• leetcode之三数之和(十一)
• • 题目内容
  • 解题思路
  • • 暴力
    • 双指针
• leetcode之最接近的三数之和(十二)
• • 题目内容
  • 解题思路
  • • 双指针
• leetcode之电话号码字母组合(十三)
• • 题目内容
  • 解题思路
• leetcode之四数之和(十三)
• • 题目内容
  • 解题思路
• leetcode之有效的括号(十五)
• • 题目内容
  • 解题思路
• leetcode之合并两个有序链表(十七)
• • 题目内容
  • 解题思路
• leetcode之括号生成(十八)
• • 题目内容
  • 解题思路
• leetcode之合并K个升序链表(十九)
• • 题目内容
  • 解题思路
• leetcode之两两交换链表中的节点(二十)
• • 题目内容
  • 解题思路
• leetcode之删除有序数组中的重复项(二十一)
• • 题目内容
  • 解题思路
• leetcode之移除元素(二十二)
• • 题目内容
  • 解题思路
• leetcode之下一个排列(二十三)
• • 题目内容
  • 解题思路

leetcode之两数之和(一) 题目内容

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

解题思路 暴力O(n^2)

两层for循环，最暴力的一种方法。

class Solution:
    def twoSum(self, nums, target):
        res = []
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    res.append(i)
                    res.append(j)
        return res

哈希表(O(n))

暴力太慢了，第二层for其实就是找一个数变成target，这一步可以使用hash表来解决

class Solution2:
    def twoSum(self, nums, target):
        my_dict = {}
        res = []
        for i in range(len(nums)):
            my_dict[nums[i]] = i
        for j in range(len(nums)):
            kk = my_dict.get(target - nums[j])
            if kk:
                res.append(j)
                res.append(kk)
                break
        return res

leetcode之两数相加(二) 题目内容

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

 

示例 1：


输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

https://leetcode-cn.com/problems/add-two-numbers/

解题思路 O(n)

因为是逆序的，所以从左到右就是从个位开始到最后一位，那就简单了

class Solution:
    def list_change_node(self, node_list):
        node = ListNode(0)
        tmp = node
        for i in node_list:
            tmp.next = ListNode(i)
            tmp = tmp.next
        return node.next

    def node_change_list(self, node):
        l = []
        tmp = node
        while tmp:
            l.append(tmp.val)
            tmp = tmp.next
        return l

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        tmp1 = l1
        tmp2 = l2
        node_list = []
        is_carry = False  # 记录是否进位
        while tmp1 or tmp2 or is_carry:
            t1 = 0 if not tmp1 else tmp1.val
            t2 = 0 if not tmp2 else tmp2.val
            a = t1 + t2 if not is_carry else t1 + t2 + 1
            node_list.append(a % 10)
            is_carry = True if int(a / 10) else False
            if tmp1:
                tmp1 = tmp1.next
            if tmp2:
                tmp2 = tmp2.next
        if node_list[-1] == 0 and len(node_list) != 1:
            node_list.pop()
        node = ListNode(0)
        tmp = node
        for i in node_list:
            tmp.next = ListNode(i)
            tmp = tmp.next
        return node.next

leetcode之无重复字符的最长子串(三) 题目内容

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

 

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:

输入: s = ""
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 暴力(O(n^3))

最简单的，前2层for循环寻找字符串的子串，最后一个for判断这个字串是否无重复

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_num = 0
        for i in range(len(s)):
            for j in range(i, len(s)):
                # 判断者之间有没有重复字符
                dict = {}
                is_ok = True
                for k in range(i, j + 1):
                    if dict.get(s[k]):
                        is_ok = False
                        break
                    dict[s[k]] = 1
                now_str = s[i:j + 1]
                if is_ok and len(now_str) > max_num:
                    max_num = len(now_str)
        return max_num

滑动窗口(O(n^2))

既然是找最大，就不需要重复查找，前面解法中的前两个for循环可以省掉j再次回头，比如已经找到了无重复子串大小为3，那么下次就不需要从头再找，直接在j=i+3的地方查找。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_num = 0
        i = 0
        j = 0
        while j < len(s):
            # 判断者之间有没有重复字符
            dict = {}
            is_ok = True
            for k in range(i, j + 1):
                if dict.get(s[k]):
                    is_ok = False
                    break
                dict[s[k]] = 1
            if is_ok:
                max_num = j + 1 - i
                j += 1
            else:
                i += 1
                j += 1

        return max_num

leetcode之最长回文子串(四) 题目内容

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
示例 4：

输入：s = "ac"
输出："a"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 O(n^2)

首先先确定什么是回文字符串，总而言之是左右对称的字符串，分为奇数情况和偶数情况，奇数情况的例子：aba、ahjha，偶数情况例子: bb，jjjj，kllk，于是就有了以下代码

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest_num = 0
        longest_str = ""
        # 奇数情况
        for i in range(len(s)):
            index_i = i - 1
            index_j = i + 1
            now_num = 1
            while index_i >= 0 and index_j < len(s) and s[index_i] == s[index_j]:
                now_num += 2
                index_i -= 1
                index_j += 1
            if now_num > longest_num:
                longest_num = now_num
                longest_str = s[index_i + 1:index_j]
        # 偶数情况
        for i in range(len(s)):
            index_i = i
            index_j = i + 1
            now_num = 0
            while index_i >= 0 and index_j < len(s) and s[index_i] == s[index_j]:
                now_num += 2
                index_i -= 1
                index_j += 1
            if now_num > longest_num:
                longest_num = now_num
                longest_str = s[index_i + 1:index_j]
        return longest_str

leetcode之Z字形变换(五) 题目内容

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

解题思路

找规律

• numRows=1时，就是一条直线，输入=输出

• numRows=2时：

  1. 第一行隔2
  2. 第二行隔2

• numRows=3时：

  1. 第一行隔4
  2. 第二行隔2，2
  3. 第三行隔4

• numRows=4时：

  1. 第一行隔6
  2. 第二行隔4，2，4，2
  3. 第三行隔2，4，2，4
  4. 第四行隔6

• numRows=5时：

  1. 第一行隔8
  2. 第二行隔6，2，6，2
  3. 第三行隔4，4，4，4
  4. 第四行隔2，6，2，6
  5. 第五行隔8

至此规律就出来了，开始撸代码

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        res = ""
        cnt = 0
        step = 2 * numRows - 2
        while cnt < numRows:
            tmp = cnt
            if cnt == 0 or cnt == numRows - 1:
                while tmp < len(s):
                    res += s[tmp]
                    tmp += step
            else:
                first_step = step - cnt * 2
                second_step = cnt * 2
                now_cnt = 0
                while tmp < len(s):
                    res += s[tmp]
                    if now_cnt % 2 == 0:
                        tmp += first_step
                    else:
                        tmp += second_step
                    now_cnt += 1
            cnt += 1
        return res

leetcode之整数反转(六) 题目内容

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。
 

示例 1：

输入：x = 123
输出：321
示例 2：

输入：x = -123
输出：-321
示例 3：

输入：x = 120
输出：21
示例 4：

输入：x = 0
输出：0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

不多bb了，直接上代码，用字符串方式解决

import math


class Solution:
    def reverse(self, x: int) -> int:
        if x == 0:
            return 0
        is_neg = True if x < 0 else False
        r_x_str_list = list(str(x).strip("0")) if not is_neg else list(str(x)[1:].strip("0"))
        r_x_str_list.reverse()
        r_x_str = ''.join(r_x_str_list) if not is_neg else "-" + ''.join(r_x_str_list)
        return int(r_x_str) if int(r_x_str) >= -math.pow(2, 31) and int(r_x_str) < math.pow(2, 31) else 0

这么解决并非最优，使用除法和取模解决才是最佳方法…

leetcode之整数反转(七) 题目内容

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-to-integer-atoi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

不多bb了，直接上代码，用字符串方式解决

import math


class Solution:
    def myAtoi(self, s: str) -> int:
        s_pre = s.strip()
        if len(s_pre) == 0:
            return 0
        ch = s_pre[0]
        if not (ch == '+' or ch == '-' or ch.isdigit()):
            return 0
        res = ''
        for i in range(1, len(s_pre)):
            if s_pre[i].isdigit():
                res += s_pre[i]
            else:
                break
        res = ch + res
        try:
            f_res = int(res)
        except:
            return 0
        if f_res < -math.pow(2, 31):
            f_res = int(-math.pow(2, 31))
        if f_res >= math.pow(2, 31):
            f_res = int(math.pow(2, 31) - 1)
        return f_res

leetcode之回文数(八) 题目内容

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
示例 1：
输入：x = 121
输出：true
示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
示例 4：
输入：x = -101
输出：false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

python一行搞定

class Solution:
    def isPalindrome(self, x: int) -> bool:
        return True if str(x) == ''.join(list(reversed(list(str(x))))) else False

leetcode之盛最多水的容器(九) 题目内容

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
示例 3：
输入：height = [4,3,2,1,4]
输出：16
示例 4：
输入：height = [1,2,1]
输出：2
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 暴力（O(n^2)）

class Solution:
    def maxArea(self, height) -> int:
        max_area = 0
        for i in range(len(height)):
            for j in range(i + 1, len(height)):
                area = (j - i) * min(height[i], height[j])
                if area > max_area:
                    max_area = area
        return max_area

直接超时

双指针

矩形的面积与两个因素有关：

矩形的长度：两条垂直线的距离
矩形的宽度：两条垂直线其中较短一条的长度
因此，要矩阵面积最大化，两条垂直线的距离越远越好，两条垂直线的最短长度也要越长越好。
我们设置两个指针 left 和 right，分别指向数组的最左端和最右端。此时，两条垂直线的距离是最远的，若要下一个矩形面积比当前面积来得大，必须要把 height[left] 和 height[right] 中较短的垂直线往中间移动，看看是否可以找到更长的垂直线。

class Solution:
    def maxArea(self, height) -> int:
        max_area = 0
        i = 0
        j = len(height) - 1
        while i != j:
            if height[i] > height[j]:
                area = (j - i) * height[j]
                j -= 1
            else:
                area = (j - i) * height[i]
                i += 1
            if area > max_area:
                max_area = area
        return max_area

leetcode之最长公共前缀(十) 题目内容

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

 

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

直接遍历

class Solution:
    def longestCommonPrefix(self, strs) -> str:
        res = ''
        index = 0
        min_len = len(min(strs, key=lambda x: len(x)))
        while index < min_len:
            is_ok = True
            s_str = strs[0][index]
            for t_str in strs:
                if t_str[index] != s_str:
                    is_ok = False
                    break
            if is_ok:
                res += s_str
            else:
                break
            index += 1
        return res

leetcode之三数之和(十一) 题目内容

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 暴力

穷举法，回溯法直接暴力枚举
直接遍历

class Solution:
    def threeSum(self, nums):
        res = []
        for i in range(len(nums)):
            self.huisu(nums, i, [nums[i]], res)
        return [list(elem) for elem in res]

    def huisu(self, nums, now_index, now_res, res):
        if len(now_res) == 3 and sum(now_res) == 0:
            elem = tuple(sorted(now_res))
            if elem not in res:
                res.append(elem)
            return
        if len(now_res) == 3:
            return
        for i in range(now_index + 1, len(nums)):
            now_res.append(nums[i])
            self.huisu(nums, i, now_res, res)
            now_res.pop()

原地爆炸，直接超时

双指针

解题思路：
https://leetcode-cn.com/problems/3sum/solution/three-sum-giftu-jie-by-githber/
代码：

class Solution:
    def threeSum(self, nums):
        res = []
        nums.sort()
        for i in range(len(nums)):
            now = nums[i]
            j_k_sum = -now
            j = i + 1
            k = len(nums) - 1
            while j < k:
                if nums[j] + nums[k] == j_k_sum:
                    res.append(tuple(sorted([nums[i], nums[j], nums[k]])))
                    j += 1
                elif nums[j] + nums[k] < j_k_sum:
                    j += 1
                else:
                    k -= 1
        return [list(elem) for elem in list(set(res))]

leetcode之最接近的三数之和(十二) 题目内容

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

解题思路 双指针

暴力就不写了，和上一题一样双指针！
代码：

from typing import List


class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        min_res = 999999
        res = 0
        for i in range(len(nums)):
            j = i + 1
            k = len(nums) - 1
            while j < k:
                t = nums[i] + nums[j] + nums[k]
                cha = abs(t - target)
                if cha < min_res:
                    min_res = cha
                    res = t
                # print(nums[i], nums[j], nums[k], min_res, res)
                if t >= target:
                    k -= 1
                else:
                    j += 1
        return res

leetcode之电话号码字母组合(十三) 题目内容

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

穷举法，回溯法直接暴力枚举，遇到这种有限问题都可以使用回溯法，回溯大法好

from typing import List


class Solution:
    map_dict = {
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z']
    }

    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []
        res = []
        self.recursion(digits, 0, [], res)
        return res

    def recursion(self, digits, index, now_res, res):
        if index == len(digits):
            res.append("".join(now_res))
            return
        for i in self.map_dict[digits[index]]:
            now_res.append(i)
            self.recursion(digits, index + 1, now_res, res)
            now_res.pop()

leetcode之四数之和(十三) 题目内容

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

 

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：

输入：nums = [], target = 0
输出：[]

解题思路

和前面的双指针思路是一样的

from typing import List


class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = set()
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                k = j + 1
                l = len(nums) - 1
                while k < l:
                    target_tmp = nums[i] + nums[j] + nums[k] + nums[l]
                    if target_tmp > target:
                        l -= 1
                    elif target_tmp < target:
                        k += 1
                    else:
                        res.add(tuple(sorted([nums[i], nums[j], nums[k], nums[l]])))
                        k += 1
        return [list(i) for i in res]

leetcode之有效的括号(十五) 题目内容

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

 

示例 1：


输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

先计算出链表的长度，再给链表加个头，最后计算出删除节点的前一个节点位置，进行替换 *** 作

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def list_to_node(self, my_list):
        head = ListNode()
        tmp = head
        for i in my_list:
            tmp.next = ListNode(i)
            tmp = tmp.next
        return head.next

    def node_to_list(self, head):
        res = []
        tmp = head
        while tmp:
            res.append(tmp.val)
            tmp = tmp.next
        return res

    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # 计算链表的个数
        cnt = 0
        tmp = head
        while tmp:
            tmp = tmp.next
            cnt += 1
        tmp_head = ListNode()
        tmp_head.next = head
        rm_cnt = cnt - n
        tmp = tmp_head
        tmp_cnt = 0
        while tmp_cnt < rm_cnt:
            tmp = tmp.next
            tmp_cnt += 1
        tmp.next = tmp.next.next
        return tmp_head.next


if __name__ == '__main__':
    s = Solution()
    head = [1, 2, 3, 4, 5]
    n = 5
    h = s.list_to_node(head)
    res = s.removeNthFromEnd(h, n)
    print(s.node_to_list(res))

leetcode之合并两个有序链表(十七) 题目内容

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

简单，直接上代码

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode()
        tmp = head
        tmp1 = l1
        tmp2 = l2
        while tmp1 and tmp2:
            if tmp1.val >= tmp2.val:
                tmp.next = ListNode(tmp2.val)
                tmp2 = tmp2.next
            else:
                tmp.next = ListNode(tmp1.val)
                tmp1 = tmp1.next
            tmp = tmp.next
        while tmp1:
            tmp.next = ListNode(tmp1.val)
            tmp1 = tmp1.next
            tmp = tmp.next
        while tmp2:
            tmp.next = ListNode(tmp2.val)
            tmp2 = tmp2.next
            tmp = tmp.next
        return head.next

leetcode之括号生成(十八) 题目内容

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

回溯法破万法：
回溯定义以下几个变量：

• res用于存储最终结果
• now_res 用于存储当前状态结果
• left_num，左括号数量，用于回溯的返回条件，不可大于n
• stack_num，栈的数量，遇到右括号数量减去1，不可小于0

class Solution:
    def generateParenthesis(self, n: int):
        res = []
        self.huisu(n, res, [], 0, 0)
        return res

    def huisu(self, n, res, now_res, left_num, stack_num):
        if left_num > n or stack_num < 0:
            return
        if len(now_res) == 2 * n:
            res.append("".join(now_res))
            return
        # 假如下一个是左括号
        now_res.append("(")
        self.huisu(n, res, now_res, left_num + 1, stack_num + 1)
        now_res.pop()
        # 右括号
        now_res.append(")")
        self.huisu(n, res, now_res, left_num, stack_num - 1)
        now_res.pop()

leetcode之合并K个升序链表(十九) 题目内容

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

解题思路

很简单，直接上代码

class Solution:
    def mergeKLists(self, lists):
        tmp_nodes = [i for i in lists]
        head = ListNode()
        t = head
        while 1:
            min_node_index = -1
            min_val = 999999
            for i, node in enumerate(tmp_nodes):
                if node and node.val < min_val:
                    min_val = node.val
                    min_node_index = i
            if min_node_index == -1:
                break
            t.next = ListNode(tmp_nodes[min_node_index].val)
            t = t.next
            tmp_nodes[min_node_index] = tmp_nodes[min_node_index].next
        return head.next

leetcode之两两交换链表中的节点(二十) 题目内容

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：

输入：head = []
输出：[]
示例 3：

输入：head = [1]
输出：[1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

用三指针完成问题，一般链表问题都会加个头节点，具体见代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        t_head = ListNode()
        t_head.next = head
        tmp_node = t_head
        # 三指针
        t1 = tmp_node
        t2 = tmp_node.next
        t3 = tmp_node.next.next
        while t3:
            t2.next = t3.next
            t3.next = t2
            t1.next = t3
            if t2.next:
                t1 = t2
                t3 = t2.next.next
                t2 = t2.next
            else:
                break
        return tmp_node.next

leetcode之删除有序数组中的重复项(二十一) 题目内容

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

双指针，具体见代码

class Solution:
    def removeDuplicates(self, nums) -> int:
        if len(nums) < 2:
            len(nums)
        index_i = 0
        index_j = 1
        while index_j < len(nums):
            if nums[index_i] == nums[index_j]:
                del nums[index_j]
            else:
                index_i += 1
                index_j += 1
        return len(nums)

leetcode之移除元素(二十二) 题目内容

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

简单，具体见代码

class Solution:
    def removeElement(self, nums, val: int) -> int:
        if len(nums) == 0:
            return 0
        index = 0
        while index < len(nums):
            if nums[index] == val:
                del nums[index]
            else:
                index += 1
        return len(nums)

leetcode之下一个排列(二十三) 题目内容

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
示例 4：
输入：nums = [1]
输出：[1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

像 [3,2,1] 这样递减的，没有下一个排列，已经稳定了，没法变大。
像 [1,5,2,4,3,2] 这种，怎么稍微变大？

从低位挑一个大一点的数，尽量低位，换掉它前面一个小一点的数。

即从右往左，寻找第一个比右邻居小的数，把它换到后面去

“第一个”意味着会尽量在低位，“比右邻居小”意味着它是从右往左的第一个波谷

比如，1 5 (2) 4 3 2，中间这个 2。

接着依然从右往左，寻找第一个比这个 2 微大的数。15 (2) 4 (3) 2，交换后变成 15 (3) 4 (2) 2。

还没结束！变大的幅度可以再小一点，仟位微变大了，后三位可以再小一点。

后三位肯定是递减的，翻转，变成[1,5,3,2,2,4]，即为所求。

class Solution:
    def nextPermutation(self, nums) -> None:
        if len(nums) < 2:
            return
        index_i = len(nums) - 1
        is_fine = False
        while index_i >= 0 and not is_fine:
            now_val = nums[index_i]
            min_val = 999999999
            min_val_index = 0
            for i in range(index_i, len(nums)):
                if nums[i] > now_val and nums[i] - now_val < min_val:
                    min_val = nums[i] - now_val
                    min_val_index = i
            if min_val != 999999999:
                nums[min_val_index], nums[index_i] = nums[index_i], nums[min_val_index]
                is_fine = True
                break
            index_i -= 1
        if not is_fine:
            nums.sort()
            return
        # 冒泡排序，升序排列
        for i in range(index_i + 1, len(nums)):
            for j in range(len(nums) - 1, i, -1):
                if nums[j] < nums[j - 1]:
                    nums[j], nums[j - 1] = nums[j - 1], nums[j]