Shauby

分类

/ 注册

全部文章（共44篇）

题解 | #数字字符串转化成IP地址#

数字字符串转化成IP地址, 回溯相当于是找满足IP要求的数字字符组排列，最容易想到的就是用回溯基本要素1，终止条件：如果遍历到字符串末尾或者找出的字段数已经超过4基本要素2：元素选择：在某一个位置，可以选一个数作为IP地址的一个字段，也可以选两个数作为IP地址的一个字段，但第一位数不能是0，还可以...

字符串递归回溯 Python3

2022-08-24

0 319

题解 | #编辑距离(一)#

编辑距离(一)，动态规划，空间O(min(m,n) 尾部元素str[i]和str[j]相等，不用编辑，编辑距离就是str1[:i]到str2[:j]的编辑距离。尾部元素str[i]和str[j]不等：修改，对应的编辑距离是str1[:i]到str2[:j]的编辑距离+1。尾部元素str[i]和str...

动态规划 Python3 字符串

2022-08-23

0 297

题解 | #主持人调度（二）#

主持人调度（二）,官方题解1精简版（7行）与超详细思路梳理官方题解1挺巧妙的，试着梳理一下思路。求最小的主持人数，等价于求最大区间重叠数。然而区间在哪里具有最大重叠我们是不知道的，如果一个一个遍历去找时间得O(n^2)，如何O(nlogn)实现呢。我们的目标是找最大重叠，只要起点终点不混，不同区...

贪心 Python3

2022-08-21

0 339

题解 | #矩阵最长递增路径#

矩阵最长递增路径，dfs+动态规划心路历程：看一眼题，求最长路径，欧，简单，就是从一个起点开始，用dfs把每条能走的道都走一遍，最后看所有的路中谁最长，类似于求树的深度嘛。根据这样的想法写完代码，什么，居然没有过。再瞄了一眼题，欧，原来起点不固定，那加个循环，把矩阵中所有点都遍历一边，这样总能找到...

Python3 动态规划深度优先搜索递归

2022-08-20

0 394

题解 | #盛水最多的容器#

盛水最多的容器，把求面积放入条件内，多一行代码，但会比官方题解快 class Solution: def maxArea(self , height: List[int]) -> int: res = left = 0 right = len(heigh...

贪心双指针 Python3

2022-08-19

0 252

题解 | #旋转数组#

旋转数组，完全基于两两交换实现数组移位，时间O(n)，空间O(1) 思路：不断让前m和尾m个元素交换，维护一个指针start，它是交换完元素的终点，未交换元素的起点。每交换完成m个元素，start往右移动m。要注意的边界条件是，当start靠近尾部时，交换区间会重叠，此时交换之后，重叠区域会被错误的...

数组模拟 Python3

2022-08-18

0 236

题解 | #最长无重复子数组#

最长无重复子数组极简实现——8行方法1：主要借助列表的in属性，内部属性更快，自己手写查找会超时。借助index属性可以直接跳到重复元素后，提升速度。双指针，如果不在子数组内，右边扩张，如果在子数组内，左边跳到重复元素后。 class Solution: def maxLength(sel...

Python3 数组双指针哈希表

2022-08-18

0 304

题解 | #寻找峰值#

寻找峰值，复杂一点的解法+对官方题解的理解如果峰值存在于一个区间内，必有左端和右端单调性相反。由于没有想到官方题解那种间接使用nums[−1]=nums[n]=−∞和间接得到峰值的方法，所以添加了几对数组首尾的边界条件。对官方题解理解：数组首尾的单调性是已知的，左单增，右单减，所以官方题解直接...

二分查找 Python3 双指针

2022-08-17

0 307

题解 | #N皇后问题#

N皇后问题-官方题解简化版典型的回溯-排列问题，关键在于判断当前位置放皇后是否合法。最费力的方法是把与当前位置同列，左斜线，右斜线的所有坐标都遍历一遍，看这些坐标中是否已经有皇后了，但这样会涉及很多没有必要的访问。由于两个点（i,j）(m,n)在一条斜线上会满足，abs(i-m)=abs(j-n)...

回溯 Python3

2022-08-17

1 285

题解 | #把数字翻译成字符串#

把数字翻译成字符串，动态规划，时间O(n)，空间O(1) 数组任何一个位置的数字，既可以只看当前位置组成个位数，也可以结合之前位置构成多位数。由于字母编码只在1-26之间，所以只有两种方式——只取当前数字组成1位数编码或者取当前位置+前一个位置组成两位数编码。如果以nums[:i+1]译成字符串的...

字符串数组动态规划 Python3

2022-08-16

0 262