牛客281174060号

题解

/ 注册

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

题解 | #判断是否为回文字符串#

两个指针分别位于首尾，不断向中间靠拢，看是否每次首尾字符都一样，不一样就return false，如果全部一样就return true。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param str string字符串待判断的字符串 # @r...

Python3

2022-04-23

0 394

题解 | #括号生成#

递归求解该题，对于n个括号的情况，首先返回n-1个括号的所有结果，然后把一个新的括号插入到n-1个括号结果的每个情况中，组成新的情况，这个插入方法为：新的括号插在最前面，插在最后面，插在每一个(的后面。需要注意的是，对于n-1个括号返回的结果，便利每个结果进行新括号插入时，会有几种情况下是重复的，解...

Python3

2022-04-23

0 285

题解 | #N皇后问题#

我的解题思路如下：对于n*n的这样一个棋盘，其实N皇后问题可以转化为这样一个问题，给定一个list，[0,1,2,```,n-1]，index代表行，list[i]代表第i行的皇后所在的列，比如list[1]=2,代表第1行的皇后在第2列，皇后的方法其实有n!种，也就是这个list的一个全排列，这种...

Python3

2022-04-22

1 435

题解 | #打家劫舍(二)#

还是dp，只是相较于没有首末次约束的情况下多了一个思维过程而已。由于不能同时偷首末家，因此一共有三种可能：偷最多的钱要么是1.偷了首家，不偷末家，要么是2.偷了末家，不偷首家，要么是3.首末家都没偷。因此可以做两个dp向量，一个dp不包括首家，一个dp不包括末家，最后返回两者较大者即可。 # # 代...

Python3

2022-04-21

5 498

题解 | #判断是不是完全二叉树#

本题使用层序遍历，如果遇到none的结点，就将标记变量标记为1，然后继续层序遍历，若后面没有结点了，就是完全二叉树，如果后面还有结点就不是。主要就是考察层序遍历，之前我写的层序遍历都很复杂，把每一层都存起来才行，这次用了queue的方法写了一遍，感觉不错。 class TreeNode: ...

Python3

2022-04-20

0 370

题解 | #判断是不是二叉搜索树#

看了题解我的方法最麻烦了，先说下题解的好方法：中序遍历，序列升序则是二叉搜索树； 2.递归法，遍历第一个节点，判断该结点是否在指定范围内，然后遍历该结点的左右子节点，遍历左结点时，范围是父节点范围的左边界和父节点值作为有边界，依次类推。 3.我实现的方法：递归法，判断左右子树是不是二叉搜索树，...

Python3

2022-04-19

0 338

题解 | #寻找第K大#

最简单的方法就是排序，返回第n-k大的即可，此外可以使用最大堆，这些复杂度都是O(nlogn)的。我在代码里自己写了一遍quicksort，mergesort，用python的sort试了一下，用最大堆试了一下，发现单纯用quicksort是不能行的，其他都是可以通过的。 # # 代码中的类名、方...

Python3

2022-04-19

0 436

题解 | #打家劫舍(一)#

很简单的dp，设定dp[i]为偷窃到第i家为止不被发现的做多的钱，状态转移方程如下： dp[i]=max{dp[i−1],nums[i]+dp[i+2]}dp[i]=max\{dp[i-1],nums[i]+dp[i+2] \}dp[i]=max{dp[i−1],nums[i]+dp[i+2]} 其...

Python3

2022-04-18

0 280

题解 | #数组中的逆序对#

该题最关键的是要想到逆序对的数量和对数组进行排序，调换元素位置的数量是一致的。举个例子[2,1,3,5,4]进行排序时，首先1,2要换一下位置，然后5,4要换一下位置，所以调换位置的数量是2，逆序数也是2.也就是说逆序对数量其实就是排序过程中调换位置的数量。所以只需要记录下排序过程中的位置调换数量就...

Python3

2022-04-17

2 432

题解 | #最长的括号子串#

用dp来解，设dp[i]为以第i个字符为结尾的最长匹配括号序列。状态转移方程为： if s[i+1]+s[i]==′()′,dp[i+1]=dp[i−2]+2if \ s[i+1]+s[i]=='()',dp[i+1]=dp[i-2]+2if s[i+1]+s[i]==′()′...

Python3

2022-04-16

0 272