在参加牛客活动的太平湖水怪很有礼貌

题解

/ 注册

全部文章 / 题解（共18篇）

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

思路：先用二分查找法判断元素是否存在，返回index，若为-1，返回[-1,-1]，否则继续下一步。左右边界l和r初始设为index，分别向左和向右滑动直到对应的数组值不等于target，然后返回[l,r]。 class Solution: def searchRange(self,...

Python3 二分查找

2022-04-21

0 273

24.两两交换链表中的节点

思路：利用栈（自己想的）设置两个栈，一个odd_stack，存放序号为奇数的节点，一个even_stack，存放序号为偶数的节点，遍历所有节点，依次将相应的节点放入两个栈。设置pre指针，如果两个栈内节点数量相等，pre设为None；如果不相等（一定是odd_stack比even_stack多...

Python3 栈

2022-04-18

0 220

31.下一个排列

思路：从后往前遍历，遇到的第一个非升序数的下标记为k，k表示“小数”；如果走出循环没有break，表示这个排列是全降序的（从前往后），因此返回全排列的第一个，也就是这个排列的逆序。对于k后面的数，从后往前遍历，找到第一个比k大的数，对应的下标记为m，m表示“大数”，然后将“小数”和“大数”交换...

Python3 分析找规律

2022-04-18

0 213

23.合并k个升序链表

思路：如何合并2个升序链表递归法：l1的值小于l2，则l1的下一个节点为l1剩下的节点与l2节点合并的结果；反之，l2的下一个节点为l2剩下的节点和l1合并的结果。对k个链表，将其中2个链表合并为1个，直到所有链表合为了1个。 class Solution: def mergeKL...

Python3 递归

2022-04-17

0 222

22.括号生成

思路：回溯，当左括号少于n时，可以继续加左括号；当右括号少于左括号时，可以继续加右括号。通过left和right分别表示当前左右括号的数量。 class Solution: def generateParenthesis(self, n: int) -> List[str]: ...

Python3 回溯

2022-04-17

0 174

20.有效的括号

思路：利用栈+哈希表注意点：奇数个符号直接返回False 遇到左括号，依次压入栈遇到右括号，如果栈为空，返回False；否则，弹出栈顶的左括号，判断是否是该右括号对应的左括号（因为最新的右括号必须先闭合），若不是，返回False。 4.遍历完所有字符，最后判断栈是否空，若非空，返回False...

Python3 栈

2022-04-16

0 158

13.罗马数字转整数

利用规律，一般而言，罗马数字的字符是从大到小排列的，特殊的如IV=4=-1+5，所以扫描每个字符，如果该字符比后一个字符大，则加上对应的数，如果比后一个字符小，则减去对应的数，注意i从0到l-2，l-1在for循环外单独处理。 class Solution: def romanToInt(s...

Python3 模拟

2022-04-15

0 204

11.盛最多水的容器

思路：双指针法初始：左指针l指向height[0],右指针r指向height[l-1] 当前的容量=min(height[l],height[r])*(r-l) 移动height[l]和height[r]中较小值对应的指针，因为容器的宽度(r-l)会随着左右指针的相互靠近不断减小，若移动较大值对...

Python3 双指针

2022-04-15

0 217

06.Z字形变换

思路：二维矩阵模拟构造二维矩阵z_array，将s中的字符按照z字形填入，然后按照行列读出z_array的非空字符。 z_array的行数为r=numRows,一个画z字形的周期t=r+r-2=2r-2,每个周期有r-1列，一共有int(len(s)/t)+1个周期，因此可以计算出列数。填入s...

Python3 数组模拟

2022-04-14

0 249

05.最长回文子串

思路：动态规划,一个回文串的头尾应该相等，且去掉头尾之后依然是回文串。 dp[i][j]表示下标从i到j的连续子串是否为回文串当s[i]==s[j]时，也就是子串头尾相等时，如果去掉子串的头尾得到的子串是回文串，则子串为回文串，因此当L=j-i+1>3时，dp[i][j] = dp[i+1]...

Python3 字符串动态规划

2022-04-14

0 195