在参加牛客活动的太平湖水怪很有礼貌 - 个人主页动态 - 牛客网

发布(18) 刷题

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

2022-04-21 17:09

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

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

0 点赞评论收藏

转发

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

2022-04-18 19:22

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

思路：利用栈（自己想的） 设置两个栈，一个odd_stack，存放序号为奇数的节点，一个even_stack，存放序号为偶数的节点，遍历所有节点，依次将相应的节点放入两个栈。 设置pre指针，如果两个栈内节点数量相等，pre设为None；如果不相等（一定是odd_stack比even_stack多一个），从odd_stack中pop出一个节点（即链表的最后一个节点，没有和它相互交换的节点），将这个节点作为pre，此时两个栈的节点数量是相等的了。 当2个栈都非空时，每次同时从两个栈中pop出一个节点，even_stack中pop出的节点cur作为前面的节点，odd_stack中pop出的节点p...

0 点赞评论收藏

转发

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

2022-04-18 18:53

31.下一个排列

思路： 从后往前遍历，遇到的第一个非升序数的下标记为k，k表示“小数”；如果走出循环没有break，表示这个排列是全降序的（从前往后），因此返回全排列的第一个，也就是这个排列的逆序。 对于k后面的数，从后往前遍历，找到第一个比k大的数，对应的下标记为m，m表示“大数”，然后将“小数”和“大数”交换。 3.对于k后面的数，必然是降序的，因此做一个逆序，使得其升序。 class Solution: def nextPermutation(self, nums: List[int]) -> None: """ Do not return anythi...

0 点赞评论收藏

转发

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

2022-04-17 14:15

23.合并k个升序链表

思路： 如何合并2个升序链表 递归法：l1的值小于l2，则l1的下一个节点为l1剩下的节点与l2节点合并的结果；反之，l2的下一个节点为l2剩下的节点和l1合并的结果。 对k个链表，将其中2个链表合并为1个，直到所有链表合为了1个。 class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: if not lists: return None if lists == [[]]: ...

0 点赞评论收藏

转发

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

2022-04-17 13:50

22.括号生成

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

0 点赞评论收藏

转发

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

2022-04-16 19:42

20.有效的括号

思路：利用栈+哈希表 注意点： 奇数个符号直接返回False 遇到左括号，依次压入栈 遇到右括号，如果栈为空，返回False；否则，弹出栈顶的左括号，判断是否是该右括号对应的左括号（因为最新的右括号必须先闭合），若不是，返回False。 4.遍历完所有字符，最后判断栈是否空，若非空，返回False，否则返回True。 class Solution: def isValid(self, s: str) -> bool: if len(s)%2 != 0: return False r_map = {')':'(',']':...

0 点赞评论收藏

转发

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

2022-04-15 16:44

13.罗马数字转整数

利用规律，一般而言，罗马数字的字符是从大到小排列的，特殊的如IV=4=-1+5，所以扫描每个字符，如果该字符比后一个字符大，则加上对应的数，如果比后一个字符小，则减去对应的数，注意i从0到l-2，l-1在for循环外单独处理。 class Solution: def romanToInt(self, s: str) -> int: hash_map = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000} num = 0 for i in range(len(s)-1): ...

0 点赞评论收藏

转发

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

2022-04-15 11:05

11.盛最多水的容器

思路：双指针法 初始：左指针l指向height[0],右指针r指向height[l-1] 当前的容量=min(height[l],height[r])*(r-l) 移动height[l]和height[r]中较小值对应的指针，因为容器的宽度(r-l)会随着左右指针的相互靠近不断减小，若移动较大值对应的指针，不会得到更大的容量。 class Solution: def maxArea(self, height: List[int]) -> int: #双指针法 left = 0 right = len(height)-1 ...

0 点赞评论收藏

转发

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

2022-04-14 14:37

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中字符s[i]的时候，当i%t<r-1时，向下走，z_array的坐标x加1，y不动，否则向右上走，x减1,y加1。 class Solution: def convert(self, s: str, numRows: int) -> str: n = len(...

0 点赞评论收藏

转发

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

2022-04-14 14:28

05.最长回文子串

思路：动态规划,一个回文串的头尾应该相等，且去掉头尾之后依然是回文串。 dp[i][j]表示下标从i到j的连续子串是否为回文串 当s[i]==s[j]时，也就是子串头尾相等时，如果去掉子串的头尾得到的子串是回文串，则子串为回文串，因此当L=j-i+1>3时，dp[i][j] = dp[i+1][j-1];L<3(即L=2)时，dp[i][j]=True。 当s[i]!=s[j]时，dp[i][j]=False。 对每一个dp[i][j],若为True,判断L是否大于最大长度，如果是，更新最大长度，并记录子串的起始位置i。 class Solution: def longe...

0 点赞评论收藏

转发

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

2022-04-18 17:03

已编辑

特别注意path[:]这个坑 class Solution(object): def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ global res global path res = [] path = [] def backtrack(nums): global res global p...

0 点赞评论收藏

转发

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

2022-03-29 14:21

题解 | #质数因子#

按照一般的写法，python在一个用例会超时，因此关键在于第一个while循环的条件，i只用从2到sqrt(N)，而不是N。 我自己的理解是当sqrt(N)为整数时，i=sqrt(N)时，进入第二个while循环，N = N/i = N/sqrt(N) = sqrt(N), 然后继续第二个while循环，N = N/i = sqrt(N)/sqrt(N) = 1,也就是此时N已经为1，不能再分解了，因此没有必要再进入下一个（第一个）while循环；当sqrt(N)不是整数，那第一个while循环，i最后的取值是小于sqrt(N)的最大整数。 所以退出第一个while循环后，判断一下当前N，如果...

0 点赞评论收藏

转发

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

2022-03-28 21:07

分割回文串

设切割点为i，i从1到len(s)+1,则s的左半边为s[:i],右半边位s[i:] 当左半边为回文串时，对右半边进行递归求解切割得到的回文串集合,然后合并左半边和右半边切割得到的所有可能的回文串集合；当左半边不是回文串时，不做操作，切割点后移，相当于剪枝 设置递归的终止条件，空字符串、单字符串或遍历完所有切割点时返回 class Solution(object): def partition(self, s): """ :type s: str :rtype: List[List[str]] """ #...

0 点赞评论收藏

转发

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

2022-04-15 21:06

已编辑

15.三数之和

首先对nums进行排序 设置left，right两个指针，三数之和大于0，right左移；小于0，left右移；等于0，加入结果集，此处要注意不能直接break，进行下一个i的判断，而是还要将left右移以及right左移，因为还有接下来还可能存在等于0的情况。 最后进行去重，注意list类型不能作为set的元素。 class Solution(object): def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ ...

0 点赞评论收藏

转发

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

2022-03-26 10:13

首先判断是否存在环（slow走一步，fast走两步，若有环，两者必定在环中相遇） 再判断进入环的位置（index1和index2分别从头结点和相遇节点出发，都各走一步，当两者相遇时即为入环位置） #双指针法 #首先判断是否存在环 fast = slow = head pos = -1 while fast: fast = fast.next if fast: fast = fast.next slow = sl...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务