[数据结构与算法] Leetcode刷题小汇总

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Leetcode刷题小汇总 -> 正文阅读

[数据结构与算法]Leetcode刷题小汇总

消除重复项,合并区间：

例如：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
?

class Solution(object):
 ? ?def merge(self, intervals):
 ? ? ? ?intervals.sort() ?#对输入的列表进行排序
 ? ? ? ?he = [intervals[0]] ? ?#保存第一个数组并生成列表
 ? ? ? ?for i in intervals[1:]: ? ?
 ? ? ? ? ? ?if he[-1][1] >= i[0]: ? #如果新列表中最后一个数组的第2位大于后一个数组的第1位，将新列表中的进行替换
 ? ? ? ? ? ? ? ? he[-1][1] = max(i[1], he[-1][1]) ?
 ? ? ? ? ? ?else:
 ? ? ? ? ? ? ? ?he.append(i) ? ?#否则，直接无条件的添加
 ? ? ? ?return he

思路：合并是前一个数组的第二个数据大于第后一个数组的第一个数据，判断是否大于，大于的话进行合并并插入新的数组中，否则，直接进行插入。新数组首先存入第一个数组为参照，然后每次判断取最后一个数组进行比较。

python的数组的水平翻转：

intervals[::] = intervals[::-1]

python的逆时针翻转90：

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

for i in range(len(matrix)):
 ? ? ? ? ? ?for m in range(i):
 ? ? ? ? ? ? ? ?matrix[i][m],matrix[m][i] = matrix[m][i],matrix[i][m] ? #对角线翻转
 ? ? ? ?
 ? ? ? ?for h in range(len(matrix)):
 ? ? ? ? ? ?matrix[h][::] = matrix[h][::-1]

逆时针翻转，对角线翻转，在水平翻转就是逆时针翻转的效果。

最长的公共前缀：

示例 1：

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

class Solution(object):
 ? ?def longestCommonPrefix(self, strs):
 ? ? ? ?if len(strs) == 0: ? ?#如果为空字符串，则返回''
 ? ? ? ? ? ? ? ? ? ?return ''
 ? ? ? ?res = '' ? ?#用于存放
 ? ? ? ?for i in range(len(strs[0])): ? #以第一个字符串的大小为循环的参照
 ? ? ? ? ? ?for str in strs: ? ? ? ? ? #遍历列表中的每一个字符串
 ? ? ? ? ? ? ? ?if len(str) <= i: ? ? ? #如果小于i,当前的个数， <=,因为是从0开始的，数字从1开始的
 ? ? ? ? ? ? ? ? ? ?return res ? ? ? ? ? ? ? # ? ? ? ? ? ? ? ? ?  所以有等于号（特别注意）
 ? ? ? ? ? ? ? ?else:
 ? ? ? ? ? ? ? ? ? ?if str[i] != strs[0][i]: ? ?#或者字符串中的第i位与第一个字符串中的第i位不相等
 ? ? ? ? ? ? ? ? ? ? ? ?return res ? ? ? ? ? ? ? #直接返回
 ? ? ? ? ? ?res += strs[0][i] ? ? ? #遍历strs，处理不在其他中或其他字符串过短的问题，
 ? ? ? ?return res

直接取得第一个数据为参照，以它长度进行循环，如果有字符串小于当前的i，那么最长公共前缀不可能更大，直接放回，否则，判断当前字符串是否相等，不相等就直接返回，否则就存入res中并继续进行遍历。

中心元素的下标：

 ?all = sum(nums) ? #求和
 ? ? ? ?t = 0
 ? ? ? ?for i in range(len(nums)): ?
 ? ? ? ? ? ?if t * 2 + nums[i] == all: ? #判断左边的2倍加上中间的数是否等于sum,如果不存在，就查找失败
 ? ? ? ? ? ? ? ?return i 
 ? ? ? ? ? ?else:
 ? ? ? ? ? ? ? ?t += nums[i] ? ?#前i项和存入t中
?
 ? ? ? ?return -1

中心元素就是两边的数加起来等于0，那么中心元素的左半边的2倍在加上中心元素应该等于总和。

零矩阵编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

输入： [ [1,1,1], [1,0,1], [1,1,1] ] 输出： [ [1,0,1], [0,0,0], [1,0,1] ]

class Solution(object):
 ? ?def setZeroes(self, matrix):
 ? ? ? ?x_zero = []
 ? ? ? ?y_zero = []
 ? ? ? ?l = len(matrix)
 ? ? ? ?s = len(matrix[0])
 ? ? ? ?for i in range(l):
 ? ? ? ? ? ?for m in range(s):
 ? ? ? ? ? ? ? ?if matrix[i][m] == 0:
 ? ? ? ? ? ? ? ? ? ?x_zero.append(i)
 ? ? ? ? ? ? ? ? ? ?y_zero.append(m)
 ? ? ? ?for i in range(l):
 ? ? ? ? ? ?if i in x_zero:
 ? ? ? ? ? ? ? ?for d in range(s):
 ? ? ? ? ? ? ? ? ? ?matrix[i][d] = 0
?
 ? ? ? ?for i in range(s):
 ? ? ? ? ? ?if i in y_zero:
 ? ? ? ? ? ? ? ?for e in range(l):
 ? ? ? ? ? ? ? ? ? ?matrix[e][i] = 0

通过循环找出为0的数据并保存其x,y坐标，然后再将x，y的那一横,纵分别全部变成0，

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。

class Solution:
 ? ?def longestPalindrome(self, s: str) -> str:
 ? ? ? ?"""
 ? ? ?  回文串:正读和反读都一样的字符串(可以理解为对称的字符串)
 ? ? ?  思路: 1 分为奇数串('aba')和偶数串(’abba‘)两种情况
 ? ? ? ? ? ? 2 把每个字符当做回文串中间的字符，由内向外延展比较
 ? ? ? ? ? ? ?  (定义由内向外的两个索引值)
 ? ? ?  """
 ? ? ? ?res = ""
 ? ? ? ?for i in range(len(s)):
 ? ? ? ? ? ?# 奇数情况
 ? ? ? ? ? ?tmp = self.helper(s, i, i)
 ? ? ? ? ? ?if len(tmp) > len(res):
 ? ? ? ? ? ? ? ?res = tmp ? ? ? ? ? ? ?#res不断的进行迭代，将最长的字符串保存到res里面
 ? ? ? ? ? ?# 偶数情况
 ? ? ? ? ? ?tmp = self.helper(s, i, i+1)
 ? ? ? ? ? ?if len(tmp) > len(res):
 ? ? ? ? ? ? ? ?res = tmp
 ? ? ? ?return res
 ? ?
 ? ?def helper(self, s, l, r): ? ?
 ? ? ? ?while l >=0 and r < len(s) and s[l]==s[r]:
 ? ? ? ? ? ?l -= 1; r += 1
 ? ? ? ?return s[l+1:r]
?

给你一个字符串 s ，颠倒字符串中单词的顺序。

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：颠倒后的字符串中不能存在前导空格和尾随空格。

class Solution(object):
 ? ?def reverseWords(self, s):
 ? ? ? ?s1 = ' '.join(s.split()[::-1])
 ? ? ? ?return s1

' '.join(），可以去除多于的空格，split()[::-1]，加上前面的就是以空格数据依据，进行倒叙

最大字数组和：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

class Solution(object):
 ? ?def maxSubArray(self, nums):
 ? ? ? ?size = len(nums)
 ? ? ? ?if size == 0:
 ? ? ? ? ? ?print(0)
 ? ? ? ?dp = [0 for _ in range(size)] ? ?#创建一个长度为len的数组
?
 ? ? ? ?dp[0] = nums[0] ? ?#将第一个数据赋值给第一个
 ? ? ? ?for i in range(1, size):
 ? ? ? ? ? ?if dp[i - 1] >= 0: ? ? #如果前面的数据和大于0，就加起来存进去
 ? ? ? ? ? ? ? ?dp[i] = dp[i - 1] + nums[i]
 ? ? ? ? ? ?else:
 ? ? ? ? ? ? ? ?dp[i] = nums[i] ? ?#否则直接存进去
 ? ? ? ?return max(dp)

思路：累计最大，以前面为标准，如果前面的和为负数，会拉小数据，不加进去，直接保存当前 i 的数据，大于0则将数据加进去，最后求最大

反转字符串：

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

class Solution(object):
 ? ?def reverseString(self, s):
 ? ? ? ?"""
 ? ? ?  :type s: List[str]
 ? ? ?  :rtype: None Do not return anything, modify s in-place instead.
 ? ? ?  """
 ? ? ? ?m,n = 0, len(s)-1
 ? ? ? ?while m<n:
 ? ? ? ? ? ?s[m], s[n] = s[n],s[m]
 ? ? ? ? ? ?m += 1; n -= 1
 ? ? ? ?return s

day2:

数组拆分 I

示例 1：

输入：nums = [1,4,3,2] 输出：4 解释：所有可能的分法（忽略元素顺序）为：

(1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
(1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
(1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 所以最大总和为 4

思路：两两拆分，返回最小，实际上就是将排序之后的偶数项相加：

class Solution(object):
 ? ?def arrayPairSum(self, nums):
 ? ? ? ?"""
 ? ? ?  :type nums: List[int]
 ? ? ?  :rtype: int
 ? ? ?  """
 ? ? ? ?l = len(nums) ? ?#法1
 ? ? ? ?nums.sort()
 ? ? ? ?res = 0
 ? ? ? ?for i in range(l):
 ? ? ? ? ? ?if i%2 == 0:
 ? ? ? ? ? ? ? ?res += nums[i]
 ? ? ? ?return res
 ? ?
 ? ?return sum(sorted(nums)[::2]) ?#法2，原理差不多
 ? ?

两数之和 II - 输入有序数组

示例 1：

输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

思路：采用二分法，从两端的和开始判断，如果小于目标值，左边的向右移动，反之右边的向左边移

class Solution(object):
 ? ?def twoSum(self, numbers, target):
 ? ? ? ?l = len(numbers)
 ? ? ? ?l2 = l//2
 ? ? ? ?for i in range(l):
 ? ? ? ? ? ?for m in range(l):
 ? ? ? ? ? ? ? ?if numbers[i]+ numbers[m] == target and i != m:
 ? ? ? ? ? ? ? ? ? ?return [i+1,m+1] ? ?#暴力法，超时了。。。
 ?#优化 
class Solution(object):
 ? ?def twoSum(self, numbers, target):
 ? ? ? ?m = len(numbers)-1
 ? ? ? ?i = 0 
 ? ? ? ?while i< m: ? #i一定在m的左边
 ? ? ? ? ? ? ? ?if numbers[i]+numbers[m] < target:
 ? ? ? ? ? ? ? ? ? ?i += 1
 ? ? ? ? ? ? ? ?elif numbers[i]+numbers[m] > target:
 ? ? ? ? ? ? ? ? ? ?m -=1
 ? ? ? ? ? ? ? ?else:
 ? ? ? ? ? ? ? ? ? ?return [i+1,m+1]
 ? ? ? ?return -1
?

移除元素

示例 1：

输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

思路：主要是使用双指针，快指针和慢指针，当块指针不等于val的时候，将该数赋值给慢指针，也就是说快指针用于查找不等于val的数并将它赋值给慢指针，最后返回慢指针即达到移除元素：

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        l = len(nums)
        m = 0
        for i in range(l):
            if nums[i] != val:     #当快指针找到不等于val的数
                nums[m]= nums[i]    #将它赋值给慢指针m ，m并向后移动以便接下来进行下一个数的存储
                m += 1
        return m

最大连续1的个数

示例 1：

输入：nums = [1,1,0,1,1,1] 输出：3 解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

思路：遍历nums,将1的个数存下来，并对保存下来的个数进行比较，返回最大值。

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        res = 0
        count = 0
        l = len(nums)
        for i in range(l):
            if nums[i] == 1:
                count +=1     # count用于计数1出现的个数
            else:
                count = 0     # 当出现非1，则将count清零
            res = max(count,res)  #对count的计数和res取最大值
        return res

长度最小的子数组

示例 1：

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

思路：主要使用双指针滑动窗口，快的滑动，当数据大于目标值，则慢的哪一个向右滑动，并获得计算数组的长度

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
       
        l = len(nums)
        left = 0
        total = 0     # 用于存放总数
        right = 0
        count = len(nums)+1     
        while right <= l-1:     #右边的快的一个不能大于边界len()-1
            total += nums[right]      # Total 计算left到right之间的距离
            while total>= target:      # 总数大于目标值了，left向右移动
                count = min(right-left+1, count)   # 比较查找最小值
                total -= nums[left]           #减去left滑动的那个数值
                left += 1
            right += 1
        return (0 if count==len(nums)+1 else count)

杨辉三角

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

示例 1:

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

思路：输出的每一项个列表的个数逐个增多，用循环创建一个结构相似的表，在从第三行开始修改，该m位置上的数字等于上一行的m位置+m-1的位置的。

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        list = [[1]*i for i in range(1,numRows+1)]  # 创建基本的表结构
        for i in range(2,numRows):    # 从第3行开始遍历
            for m in range(1,i):
                list[i][m] = list[i-1][m] + list[i-1][m-1]  # 数据等于上一个两个数据相加
        return list

杨辉三角 II

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

示例 1:

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

思路与上面类似，多加一个为0,1的判断即可

class Solution(object):
 ? ?def getRow(self, rowIndex):
 ? ? ? ?list = [[1]*i for i in range(1, rowIndex+2)] ? #防止输入0,1，进行了rowIndex+2
 ? ? ? ?if rowIndex <= 1: ? ? ? ? ? ?# 为0,1时，都是1，可以直接返回
 ? ? ? ? ? ?return list[rowIndex]
 ? ? ? ?else:
 ? ? ? ? ? ?for i in range(2,rowIndex+1): ? ?#思路和上面类似
 ? ? ? ? ? ? ? ?for m in range(1,i):
 ? ? ? ? ? ? ? ? ? ?list[i][m] = list[i-1][m-1]+list[i-1][m]
 ? ? ? ? ? ?return list[rowIndex]

反转字符串中的单词 III

示例 1：

输入：s = "Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

class Solution(object):
 ? ?def reverseWords(self, s):
 ? ? ? ?return ?' '.join(word[::-1] for word in s.split())

s.split()转换为列表，进行遍历，对每一个单词单独进行反转，最后转成字符串在返回

删除排序数组中的重复项

给你一个 升序排列 的数组 nums ，请你?原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致。

示例 1：

输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

思路：和删除某个数字思路一样，使用双指针，一个快指针，一个慢指针，当快指针找到不等于慢指针的数（以为数组本来就是升序）则让慢指针向前+1，并把不一样的数字赋值给慢指针

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
     
        l = len(nums)
        m = 0
        for i in range(l):
            if nums[i] != nums[m]:
                m += 1
                nums[m]= nums[i]
        return m+1

对角线遍历

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

思路：将矩阵的坐标写出来，由图可以发现，下标加起来为偶数的在一起，下标加起来为奇数的在一起，创建一个数组嵌套5个数组分别存放，在一横排中，下标为奇数的却应该在该坐标的最后一个，偶数的在数组的第一个，于是。。。

class Solution(object):
 ? ?def findDiagonalOrder(self, mat):
 ? ? ? ?"""
 ? ? ?  :type mat: List[List[int]]
 ? ? ?  :rtype: List[int]
 ? ? ?  """
 ? ? ? ?l = len(mat)
 ? ? ? ?l1 = len(mat[0])
 ? ? ? ?res = [[] for _ in range(l + l1 - 1)] ?# 建立一个对角线个数的数组用于存放
 ? ? ? ?result = []
 ? ? ? ?for i in range(l):
 ? ? ? ? ? ?for m in range(l1): ? ? ?# 遍历数组
 ? ? ? ? ? ? ? ?if (i + m) % 2 != 0: ? ? # 为奇数的时候，直接添加到对应（i+m）的数组
 ? ? ? ? ? ? ? ? ? ?res[i + m].append(mat[i][m])
 ? ? ? ? ? ? ? ?else:
 ? ? ? ? ? ? ? ? ? ?res[i + m].insert(0, mat[i][m]) ?# 下标为偶数的时候，最先遍历到的应该在最后，所以把后加进来的insert到该数组的第一位
 ? ? ? ?for i in res:
 ? ? ? ? ? ?result += i ? ?# 遍历该数组加到一个新的数组
 ? ? ? ?return result

无重复字符的最长子串：

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

示例 1:

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

思路：使用滑动窗口的办法，遍历字符串，在发现相同的字符之后，那么剔除相同字符串以及之前的字符串，求长度的最大值

class Solution(object):
 ? ?def lengthOfLongestSubstring(self, s):
 ? ? ? ?a = [] ? ? # 用于临时存放暂未重复的字符
 ? ? ? ?count = 0 ? # 用于计数a的最长
 ? ? ? ?for i in s:
 ? ? ? ? ? ?if i in a:
 ? ? ? ? ? ? ? ?a = a[a.index(i) + 1:] # 当发现重复字符串，将该字符串以及之前的字符串剔除
 ? ? ? ? ? ?a.append(i)
 ? ? ? ? ? ?count = max(len(a), count)
 ? ? ? ?return count
 ? ? ? ?

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

示例 1：

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

思路：当然，看到题最先想到的是暴力法，O（n2）,超时了...

优化之后的思路：主要是使用双指针，盛最多水的容器=min(l,r)*两点距离，两个指针指向两端，然后将小的哪一个向内进行移动，用一个total接收结果，并取得最大值 ,时间复杂度为O（n）

# 暴力法，超时了...
class Solution(object):
 ? ?def maxArea(self, height):
 ? ? ? ?"""
 ? ? ?  :type height: List[int]
 ? ? ?  :rtype: int
 ? ? ?  """
 ? ? ? ?total = 0
 ? ? ? ?for i in range(len(height)):
 ? ? ? ? ? ?for m in range(len(height)):
 ? ? ? ? ? ? ? ?if i != m:
 ? ? ? ? ? ? ? ? ? ?lowwer = min(height[i], height[m])
 ? ? ? ? ? ? ? ? ? ?total = max(total, lowwer * (m - i))
 ? ? ? ?return total

class Solution(object):
 ? ?def maxArea(self, height):
 ? ? ? ?total = 0
 ? ? ? ?left = 0 ? 
 ? ? ? ?right = len(height) - 1
 ? ? ? ?while left < right: ? ?# 两端移动，荟聚与中间，所以right要大于Left
 ? ? ? ? ? ?s1 = min(height[left], height[right]) * (right - left)
 ? ? ? ? ? ?total = max(total, s1)
 ? ? ? ? ? ?if height[left] > height[right]: ?#left的数据大于right，移动right
 ? ? ? ? ? ? ? ?right -= 1
 ? ? ? ? ? ?else:
 ? ? ? ? ? ? ? ?left += 1 ? ?# 否则，移动left
 ? ? ? ?return total

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

思路：主要是使用二分法，用target和中间的数进行比较，如果mid大于target,那么结果一定在左边，反之亦然，每一次可以将范围缩小一半。具体的思路：在left和right中，让left找到刚刚小于target的坐标，将该坐标+1返回则是左边的边界值，让right找到刚刚大于target的坐标，并将该坐标-1即是右边的边界值：

class Solution(object):
 ? ?def searchRange(self, nums, target):
 ? ? ? ?"""
 ? ? ?  :type nums: List[int]
 ? ? ?  :type target: int
 ? ? ?  :rtype: List[int]
 ? ? ?  """
 ? ? ? ?left = self.seacher(nums, target)
 ? ? ? ?right = self.seacher(nums, target+1) ?# 右边的复用了左边查找的方法，将目标值+1，即参照比
 ? ? ? ?if left < right: ? ? ? ? ? ? ? ? ? ? ?# 目标值大1的数，mid刚好就是target，而多加了1
 ? ? ? ? ? ?return [left, right - 1] ? ? # 由于返回的right多加了1，所以减去了
 ? ? ? ?else:
 ? ? ? ? ? ?return [-1, -1]
?
 ? ?def seacher(self, nums, target):
 ? ? ? ?left = 0
 ? ? ? ?right = len(nums) ? ?# 左开右闭，所以不需要-1
 ? ? ? ?while left < right:
 ? ? ? ? ? ?mid = left + (right - left) // 2 ? # 找到中间的数
 ? ? ? ? ? ?if nums[mid] < target: ? # 找到left刚好小于target的下标
 ? ? ? ? ? ? ? ?left = mid +1 ? ? ? ?# +1返回则是边界值
 ? ? ? ? ? ?else:
 ? ? ? ? ? ? ? ?right = mid 
 ? ? ? ?return left
?

三数之和

给你一个包含 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]]

思路：排序+双指针法，由于不能重复，需要排除可能重复的

1、当i >0时，总结果一定大于0 ，直接break

2、当前一个数据和后一个数据相等的时候，pass,以免引起数据的重复

3、数据为空或者长度小于3的时候，直接返回

在循环的时候，也要注意双指针的排除重复项

class Solution(object):
 ? ?def threeSum(self, nums):
 ? ? ? ?lens = len(nums)
 ? ? ? ?res = []
 ? ? ? ?nums.sort()
 ? ? ? ?if not nums or lens < 3: ?#数据为空或者长度小于3的时候，直接返回
 ? ? ? ? ? ?return res
 ? ? ? ?else:
 ? ? ? ? ? ?for i in range(lens): 
 ? ? ? ? ? ? ? ?if nums[i] > 0: ? # 当i >0时，总结果一定大于0 ，直接break
 ? ? ? ? ? ? ? ? ? ?return res
 ? ? ? ? ? ? ? ?if i > 0 and nums[i] == nums[i - 1]: #跳过前一个数据和后一个数据相等的时候 
 ? ? ? ? ? ? ? ? ? ?continue
 ? ? ? ? ? ? ? ?l = i + 1
 ? ? ? ? ? ? ? ?r = lens - 1
 ? ? ? ? ? ? ? ?while l < r: ? # 双指针条件
 ? ? ? ? ? ? ? ? ? ?if nums[i] + nums[l] + nums[r] == 0: ?# 等于0直接加进列表
 ? ? ? ? ? ? ? ? ? ? ? ?res.append([nums[i], nums[l], nums[r]])
 ? ? ? ? ? ? ? ? ? ? ? ?while l<r and nums[l] == nums[l + 1]: ?# 同理，排除双指针重复项
 ? ? ? ? ? ? ? ? ? ? ? ? ? ?l += 1
 ? ? ? ? ? ? ? ? ? ? ? ?while l<r and nums[r] == nums[r - 1]:
 ? ? ? ? ? ? ? ? ? ? ? ? ? ?r -= 1
 ? ? ? ? ? ? ? ? ? ? ? ?l += 1
 ? ? ? ? ? ? ? ? ? ? ? ?r -= 1
 ? ? ? ? ? ? ? ? ? ?elif nums[i] + nums[l] + nums[r] > 0: # 当和>0，为了降低数据，r向左移
 ? ? ? ? ? ? ? ? ? ? ? ?r -= 1
 ? ? ? ? ? ? ? ? ? ?else: ? ? ? ? ? ? ? ? ? ? ? ? # 当和<0，为了增大数据，l向右移
 ? ? ? ? ? ? ? ? ? ? ? ?l += 1
 ? ? ? ?return res

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

class Solution(object):
 ? ?def letterCombinations(self, digits):
 ? ? ? ?"""
 ? ? ?  :type digits: str
 ? ? ?  :rtype: List[str]
 ? ? ?  """
 ? ? ? ?if digits == '':
 ? ? ? ? ? ?return []
 ? ? ? ?results = []
 ? ? ? ?my_dict = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno',
 ? ? ? ? ? ? ? ? ? ?'7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
 ? ? ? ?def dfs(k, result):
 ? ? ? ? ? ?if k == len(digits):
 ? ? ? ? ? ? ? ?results.append(result)
 ? ? ? ? ? ? ? ?return results
 ? ? ? ? ? ?for i in my_dict[digits[k]]:
 ? ? ? ? ? ? ? ?dfs(k+1, result+i)
 ? ? ? ?
 ? ? ? ?dfs(0, '')
 ? ? ? ?return results

比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数，返回一个长度为 n + 1 的数组 ans 作为答案.

示例 1：

输入：n = 2 输出：[0,1,1] 解释： 0 --> 0 1 --> 1 2 --> 10

思路：bin(),转换为二进制，然后在计算1的个数

# 最开始的复杂版
class Solution(object):
 ? ?def countBits(self, n):
 ? ? ? ?"""
 ? ? ?  :type n: int
 ? ? ?  :rtype: List[int]
 ? ? ?  """
 ? ? ? ?res = []
 ? ? ? ?total = 0
 ? ? ? ?for i in range(n+1):
 ? ? ? ? ? ?s = bin(i)[2:]
 ? ? ? ? ? ?total = 0
 ? ? ? ? ? ?for m in s:
 ? ? ? ? ? ? ? ?total += int(m)
 ? ? ? ? ? ?res.append(total)
 ? ? ? ?return res

# 简化版
class Solution(object):
 ? ?def countBits(self, n):
 ? ? ? ?return [bin(i).count('1') for i in range(n + 1)]

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()" 输出：true

思路：将符号进行替换，判断最后的结果是否为空，为空说明全是符合

class Solution(object):
 ? ?def isValid(self, s):
 ? ? ? ?while '()' in s or '{}' in s or '[]' in s:
 ? ? ? ? ? ?s = s.replace('()','')
 ? ? ? ? ? ?s = s.replace('{}','')
 ? ? ? ? ? ?s = s.replace('[]','')
 ? ? ? ?return s== ''

删除链表的倒数第 N 个结点

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

示例 1：

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

思路：用栈的方法，将数据全部存放在栈中，然后将N+1个数据取了出来，将需要删除的前一个指针指向下一个的下一个指针，从而删除了第N个数据

class Solution(object):
 ? ?def removeNthFromEnd(self, head, n):
 ? ? ? ?a = head
 ? ? ? ?b = ListNode(0,head)
 ? ? ? ?c = b
 ? ? ? ?list1 = list()
 ? ? ? ?while c:
 ? ? ? ? ? ?list1.append(c)
 ? ? ? ? ? ?c = c.next
 ? ? ? ?for i in range(n):
 ? ? ? ? ? ?list1.pop()
 ? ? ? ?stack = list1[-1]
 ? ? ? ?stack.next = stack.next.next
 ? ? ? ?return b.next

颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2] 思路：总共3个颜色，只需要将两个颜色归位，那么剩下一个颜色就是在位置上的，可以使用单指针或者双指针的方法

单指针：

class Solution(object):
 ? ?def sortColors(self, nums):
 ? ? ? ?lens = len(nums)
 ? ? ? ?r = 0
 ? ? ? ?for i in range(lens): ? # 从头到尾进行遍历，找出为0的值
 ? ? ? ? ? ?if nums[i] == 0:
 ? ? ? ? ? ? ? ?nums[i], nums[r] = nums[r], nums[i] # 将它与r交换，r向后一个
 ? ? ? ? ? ? ? ?r += 1
 ? ? ? ?for m in range(r, lens): ?# 在上面遍历之后，前r都为0，所以遍历r以后的数据
 ? ? ? ? ? ?if nums[m] == 1: ? ?# 为1的时候将它提前，即与r交换
 ? ? ? ? ? ? ? ?nums[m], nums[r] = nums[r], nums[m]
 ? ? ? ? ? ? ? ?r += 1

双指针：两个指针在两端，分别将0和2的数据放在两端，那么中间必定为1，从而达到排列的效果

class Solution(object):
 ? ?def sortColors(self, nums):
 ? ? ? ?lens = len(nums)
 ? ? ? ?r = 0
 ? ? ? ?l = lens - 1
 ? ? ? ?n = 0
 ? ? ? ?while n <= l: ?# 两个指针相遇遍历结束的条件
 ? ? ? ? ? ?while n <= l and nums[n] == 2: ? # 当nums[n]为2的时候，将它置于最后
 ? ? ? ? ? ? ? ?nums[l], nums[n] = nums[n], nums[l]# 即与l交换
 ? ? ? ? ? ? ? ?l -= 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? # l向前移动1位
 ? ? ? ? ? ?if nums[n] == 0: ? ? # 当nums[n]为0的时候，将它置于最前
 ? ? ? ? ? ? ? ?nums[n], nums[r] = nums[r], nums[n] ?# 与r的数据进行交换
 ? ? ? ? ? ? ? ?r += 1
 ? ? ? ? ? ?n += 1 ? ?
 ? ? ? ?return nums
?

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。

思路：动态规划的思想，计算出每一步所需要的代价，那么第一横排和第一列只能单向的走，代价进行简单的累加即可，剩下的数据为该位置的数据加上上面或者左侧的数据，取最小值即可，最后返回最后一个数据即可。

class Solution(object):
 ? ?def minPathSum(self, grid):
 ? ? ? ?height = len(grid)
 ? ? ? ?wide = len(grid[0])
 ? ? ? ?dp = [[0] * wide for _ in range(height)] ?# 创建一个横列和给的列表相等的列表
 ? ? ? ?dp[0][0] = grid[0][0] ? ? ? ? ? ? # 将第一个数据加到新的列表中
 ? ? ? ?if not grid or not grid[0]: ? ?
 ? ? ? ? ? ?return 0
 ? ? ? ?for i in range(1, wide): ? ? # 对第1横排数据进行替换，每一个数据代价等于前面的累加
 ? ? ? ? ? ?dp[0][i] += grid[0][i] + dp[0][i - 1]
 ? ? ? ?for m in range(1, height): ? ?# 对第1列数据进行替换，每一个数据代价等于前面的累加
 ? ? ? ? ? ?dp[m][0] += grid[m][0] + dp[m - 1][0]
?
 ? ? ? ?for i in range(1, wide): ?
 ? ? ? ? ? ?for m in range(1, height): ? # 其他数据取（上面或者左边）最小值+该位置本该有的数据
 ? ? ? ? ? ? ? ?dp[m][i] = min(dp[m][i - 1], dp[m - 1][i])+grid[m][i]
 ? ? ? ?return dp[height-1][wide-1] ? ? ? # 直接返回右下角的数据

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例 1：

输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

服了，遇到这种回溯法，递归的就做不来。。。。copy了大佬的答案

思路：递归的思想，当（）的长度小于2n的时候不断的进行递归，每一次，+（或者+），直到最后长度等于2n

class Solution(object):
 ? ?def generateParenthesis(self, n):
 ? ? ? ?res = [] ? ?# 用于存放数据
?
 ? ? ? ?def func(s, left, right): ? 
 ? ? ? ? ? ?if left == right == n: ? # 返回的条件，左右括号等于n
 ? ? ? ? ? ? ? ?res.append(s)
 ? ? ? ? ? ? ? ?return
 ? ? ? ? ? ?elif right <= left <= n: ? # 当left大于right但是小于n时，一定还有符合条件的存在
 ? ? ? ? ? ? ? ?func(s + ')', left, right + 1) ?# 加）括号，左边的计数+1
 ? ? ? ? ? ? ? ?func(s + '(', left + 1, right) ? # 加（括号，右边的计数+1
?
 ? ? ? ?func('', 0, 0) ? # 传入原始的数据
 ? ? ? ?return res

机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1 输出：3

class Solution(object):
 ? ?def movingCount(self, m, n, k):
 ? ? ? ?"""
 ? ? ?  :type m: int
 ? ? ?  :type n: int
 ? ? ?  :type k: int
 ? ? ?  :rtype: int
 ? ? ?  """
 ? ? ? ?def back(i, j, s):
 ? ? ? ? ? ?if not 0<=i<m or not 0<=j< n or  (i//10 + i%10 + j//10 + j%10) > k or (i, j) in visited: ?
 ? ? ? ? ? ? ? ?return 0
 ? ? ? ? ? ?visited.add((i, j))
 ? ? ? ? ? ?return 1 + back(i + 1, j, s) + back(i, j - 1, s) + back(i + 1, j, s) + back(i, j + 1, s)
 ? ? ? ?visited = set()
 ? ? ? ?return back(0,0,k)
?
 ? ? ?

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

例如: 给定的树 A:

 3
/ \

4 5 / \ 1 2 给定的树 B：

4 / 1 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1] 输出：false

思路：使用先序遍历的方法，当B为空的时候，说明遍历完成，作为函数的出口，

返回的False的2中情况：

当a为空，b不为空的时候，说明b的数据多于a的，返回false
当值不相等的时候，返回

# Definition for a binary tree node.
# class TreeNode(object):
# ? ? def __init__(self, x):
# ? ? ? ? self.val = x
# ? ? ? ? self.left = None
# ? ? ? ? self.right = None
?
class Solution(object):
 ? ?def isSubStructure(self, A, B):
 ? ? ? ?"""
 ? ? ?  :type A: TreeNode
 ? ? ?  :type B: TreeNode
 ? ? ?  :rtype: bool
 ? ? ?  """
 ? ? ? ?def cur(A, B): ?
 ? ? ? ? ? ?if not B: return True ? # b为空，遍历结束
 ? ? ? ? ? ?if not A or A.val != B.val or (not A and not B): return False
 ? ? ? ? ? ?return cur(A.left, B.left) and cur(A.right, B.right) 
?
 ? ? ? ?return bool(A and B) and (cur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)) ?# 判断a或者b是否为空的条件， bool(A and B)

剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

/ \ 2 7 / \ / \ 1 3 6 9 镜像输出：

/ \ 7 2 / \ / \ 9 6 3 1

示例 1：

输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1

思路：主要是回溯算法，将一边的数据暂存，然后将数据进行交换。回溯遍历，结束的条件为不存在节点，即遍历到底了，如果不暂存，交换后就会对原来的数据进行覆盖

# Definition for a binary tree node.
# class TreeNode(object):
# ? ? def __init__(self, x):
# ? ? ? ? self.val = x
# ? ? ? ? self.left = None
# ? ? ? ? self.right = None
?
class Solution(object):
?
 ? ?def mirrorTree(self, root):
 ? ? ? ?if not root: return ?# 遍历完
 ? ? ? ?tmp = root.left ?# 暂存数据
 ? ? ? ?root.left = self.mirrorTree(root.right) 
 ? ? ? ?root.right = self.mirrorTree(tmp)
 ? ? ? ?return root

剑指 Offer 28. 对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

/ \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

/ \ 2 2 \ \ 3 3

# Definition for a binary tree node.
# class TreeNode(object):
# ? ? def __init__(self, x):
# ? ? ? ? self.val = x
# ? ? ? ? self.left = None
# ? ? ? ? self.right = None
?
class Solution(object):
 ? ?def isSymmetric(self, root):
 ? ? ? ?"""
 ? ? ?  :type root: TreeNode
 ? ? ?  :rtype: bool
 ? ? ?  """
 ? ? ? ?def search(l, r):
 ? ? ? ? ? ?if not l and not r: return True
 ? ? ? ? ? ?if not l or not r or l.val != r.val: return False
 ? ? ? ? ? ?return search(l.left, r.right) and search(l.right, r.left)
?
 ? ? ? ?return not root or search(root.left, root.right)

二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target = 5，返回 true。

思路：由于给定的二维数组是从上到下递增，从左到右递增，那么以18这个值为mid,进行比对，如果大于目标值，就向上，如果小于目标值，就向右

class Solution(object):
 ? ?def findNumberIn2DArray(self, matrix, target):
 ? ? ? ?c, m = len(matrix) - 1, 0
 ? ? ? ?while c >= 0 and m < len(matrix[0]): ?# len(matrix[0])可能为空，所以把 c >= 0放在前面
 ? ? ? ? ? ?if matrix[c][m] > target: ?# 大于目标值
 ? ? ? ? ? ? ? ?c -= 1 ? ? ? ? ? ? # 向上移动一行
 ? ? ? ? ? ?elif matrix[c][m] < target: ? # 小于目标值
 ? ? ? ? ? ? ? ?m += 1 ? ? ? ? ? ? ? ? ? # 向左移动一个位置
 ? ? ? ? ? ?else:
 ? ? ? ? ? ? ? ?return True
 ? ? ? ?return False

青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2 输出：2

思路：斐波那契,看到1或者2的时候，要警惕出来

class Solution(object):
 ? ?def numWays(self, n):
 ? ? ? ?a = 1
 ? ? ? ?b = 1
 ? ? ? ?for _ in range(n):
 ? ? ? ? ? ?a,b= b,a+b ?
 ? ? ? ?return a% 1000000007

矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true 示例 2：

class Solution(object):
 ? ?def exist(self, board, word):
 ? ? ? ?"""
 ? ? ?  :type board: List[List[str]]
 ? ? ?  :type word: str
 ? ? ?  :rtype: bool
 ? ? ?  """
 ? ? ? ?def dfs(i, j, k):
 ? ? ? ? ? ?if not 0<=i<len(board) or not 0<=j<len(board[0])or board[i][j]!= word[k]: 
 ? ? ? ? ? ? ? ?return False # 当i,j不属于范围或者值不等于word[i]，返回
 ? ? ? ? ? ?if k == len(word) - 1: return True # k为长度-1，表示全部进行了遍历
 ? ? ? ? ? ?board[i][j] = '' ?# 将遍历过的替换为‘’，防止重复遍历
 ? ? ? ? ? ?res = dfs(i + 1, j, k+1)or dfs(i-1,j,k+1) or dfs(i,j+1,k+1)or dfs(i,j-1,k+1)#进行上下左右的试探，只要找得到就会为True
 ? ? ? ? ? ?board[i][j] = word[k] # 将替换了的数据替换回去，避免影响后续遍历
 ? ? ? ? ? ?return res ? 
?
 ? ? ? ?for i in range(len(board)):
 ? ? ? ? ? ?for j in range(len(board[0])):
 ? ? ? ? ? ? ? ?if dfs(i,j,0):
 ? ? ? ? ? ? ? ? ? ?return True ?# 全部进行遍历，因为每一个数都可能是开始，只要res为True,返回真
 ? ? ? ?return False

给定一个字符串，求出全排：（要求不重复）

class Solution(object):
 ? ?def permutation(self, s):
 ? ? ? ?"""
 ? ? ?  :type s: str
 ? ? ?  :rtype: List[str]
 ? ? ?  """
 ? ? ? ?c, res = list(s), []
?
 ? ? ? ?def bracktrack(x):
 ? ? ? ? ? ?if x == len(c) - 1:
 ? ? ? ? ? ? ? ?res.append(''.join(c))
 ? ? ? ? ? ?p = set()
 ? ? ? ? ? ?for i in range(x,len(c)):
 ? ? ? ? ? ? ? ?if c[i] in p: continue
 ? ? ? ? ? ? ? ?p.add(c[i])
 ? ? ? ? ? ? ? ?c[i], c[x] = c[x], c[i]
 ? ? ? ? ? ? ? ?bracktrack(x+1)
 ? ? ? ? ? ? ? ?c[x], c[i] = c[i], c[x]
 ? ? ? ?bracktrack(0)
 ? ? ? ?return res
?
s = Solution()
m = s.permutation('abc')
print(m)