Maokt - 个人主页动态 - 牛客网

发布(508) 评论刷题收藏

2021-06-28 14:05

西北工业大学数据分析师

题解 | #构建乘积数组#

算法思想一：表格分区，两次遍历   解题思路：       B[0]=   1   A[1]   A[2]   ...   A[n-2]   A[n-1]     B[1]=   A[0]   1   A2   ...   A[n-2]   A[n-1]     B[2]=   A[0]   A1   1   ...   A[n-2]   A[n-1]     ...   ...   ...   ...   ...   ...   ...     B[n-2]=   A[0]   A[1]   A[2]   ...   1   A[n-1]     B[n-1]=   A[0]   A[1] ...

0 点赞评论收藏

分享

2021-07-24 11:22

已编辑

西北工业大学数据分析师

题解 | #包含min函数的栈#

算法思想一：定义辅助栈   解题思路：   1、要用两个栈，stack用于存储元素，mins用于存储最小值，每个位置的元素都有一个对应的最小值，也就是stack和mins的长度同步增加和减少；当需要得到目前栈中的最小值的时候，直接返回mins的栈顶元素即可 2、在mins栈中先添加一个最大值，因为以后每次添加都会和栈顶元素比较，如果栈为空的话代码要多写几行，先放一个最大值会方便一点      代码展示：   Python版本   # -*- coding:utf-8 -*- class Solution:     ...

0 点赞评论收藏

分享

2021-06-28 09:43

西北工业大学数据分析师

题解 | #顺时针打印矩阵#

算法思想一：按层模拟遍历   解题思路:   可以将矩阵看成若干层，首先打印最外层的元素，其次打印次外层的元素，直到打印最内层的元素。   对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 (top,left)，右下角位于(bottom,right)，按照如下顺序遍历当前层的元素。 1、从左到右遍历上侧元素，依次为(top,left) 到(top,right)。 2、从上到下遍历右侧元素，依次为(top+1,right) 到 (bottom,right)。 3、如果 left<right 且top<bottom，则从右到左遍历下侧元素，依次为(bottom,...

0 点赞评论收藏

分享

2021-06-28 08:37

西北工业大学数据分析师

2021.06.28 在牛客打卡141天！

0 点赞评论收藏

分享

2021-06-25 17:30

西北工业大学数据分析师

题解 | #二叉树的镜像#

算法思想一：递归   解题思路：   根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。   解题步骤：   1、特判：如果pRoot为空，返回空   2、交换左右子树 3、把pRoot的左子树放到Mirror中镜像一下 4、把pRoot的右子树放到Mirror中镜像一下 5、返回根节点root      图解：      代码展示：   Python版本   class Solution:     def Mirror(self , pRoot )...

シkid~：借层楼说话：说实话，无论如何，这道题都需要去遍历整棵树。对于树的遍历操作，无论是迭代（显示的使用栈或队列）还是递归（隐式地维护一个O(n)大小的栈），都是需要O(n)的空间的。这道题居然说能够在空间复杂度为O(1)的情况下解除，我很不理解（虽然题目解释说O(1)是原地操作，但是我是不能接受的）。牛客给我的最大的一个印象就是，空间复杂度和时间复杂度求不对，或者说理解有问题。

0 点赞评论收藏

分享

2021-06-25 09:09

西北工业大学数据分析师

题解 | #树的子结构#

算法思想一：递归   解题思路：   1.这道题判断是否是子结构，主要看pRoot2和pRoot1的根节点的值是否一样，一样的话再同时递归， 2.判断left节点，如果pRoot2的左节点为null,则说明pRoot2的left节点满足条件。 3.若pRoot2的节点不为null,并且pRoot1的left节点为null,或者说它们二者的值不一样，说明pRoot2不是pRoot1的子结构。 4.pRoot1和pRoot2的right节点和第2.3步一样的判断，当left和right同时成立，pRoot2才是pRoot1的子结构 5.因为题目约定空树不是任意一个数的子结构，所以pRoot1和pR...

牛客80822961...：我怎么感觉你的「非递归」版本，本质上还是递归吧

0 点赞评论收藏

分享

2021-06-25 08:46

西北工业大学数据分析师

2021.06.25 在牛客打卡140天！

0 点赞评论收藏

分享

2021-06-24 14:26

西北工业大学数据分析师

题解 | #合并两个排序的链表#

算法思想一：迭代   解题思路：   设置result为哑结点，放置于新链表之前，最后返回的就是result.next；设置cur为当前节点，从result开始 当两个链表都非空时进入循环，令新链表的下一个节点cur.next为val更小的节点，相应的链表节点后移一位，每次循环记得cur也要后移一位 如果循环结束后还有链表非空，cur指向非空链表，返回result.next      图解：      代码展示：   # -*- coding:utf-8 -*- # class ListNode: #   &nbs...

0 点赞评论收藏

分享

2021-06-24 13:13

西北工业大学数据分析师

2021.06.24 在牛客打卡139天！

0 点赞评论收藏

分享

2021-06-23 17:32

西北工业大学数据分析师

题解 | #反转链表#

算法思想一：双指针迭代   解题思路：   （1）定义两个指针： pre 和 cur ；pre 在前 cur 在后。 （2）每次让 pre 的 next 指向 cur ，实现一次局部反转 （3）局部反转完成之后， pre 和 cur 同时往前移动一个位置 （4）循环上述过程，直至 pre 到达链表尾部      图解：      代码展示：   # -*- coding:utf-8 -*- # class ListNode: #     def __init__(self, ...

0 点赞评论收藏

分享

2021-06-23 16:27

西北工业大学数据分析师

题解 | #链表中倒数最后k个结点#

算法思想一：快慢指针   解题思路：   第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动，当第一个指针到链表的末尾的时候，返回第二个指针即可       图解：      代码展示：   class Solution:     def FindKthToTail(self , pHead , k ):         # write code her...

一入秋招深似海：第二种思想出栈后的元素重新组成链表多此一举，直接返回出栈第k次的ListNode结点即可（出栈和入栈并不会影响ListNode结点中的指针地址）

0 点赞评论收藏

分享

2021-06-23 15:27

西北工业大学数据分析师

题解 | #调整数组顺序使奇数位于偶数前面#

算法思想一：使用辅助数组   解题思路：   创建两个全新的数组，遍历原数组将其奇数和偶数分别存放在两个数组中，最后将两个数组合并（奇数组放在偶数组前面）      图解：   数组：【1，2，3，4】       步骤   原数组   奇数组   偶数组     1   【1，2，3，4】   【1】   【】     2   【1，2，3，4】   【1】   【2】     3   【1，2，3，4】   【1，3】   【2】     4   【1，2，3，4】   【1，3】   【2，4】     最后合并奇数组、偶数组为【1，3，2，4】         代码展示：   clas...

0 点赞评论收藏

分享

2021-06-23 10:58

已编辑

西北工业大学数据分析师

题解 | #数值的整数次方#

算法思想一：直接暴力法   解题思路：   将 exponent 分为正 负数，当为负数时将 exponent 转为正数，并采用循环计算 exponent 次幂，然后将结果转为其倒数   当为正数时，可直接采用循环计算 exponent 次幂       代码展示：    # -*- coding:utf-8 -*- class Solution:     def Power(self, base, exponent):      &n...

0 点赞评论收藏

分享

2021-06-23 09:17

西北工业大学数据分析师

题解 | #二进制中1的个数#

算法思路一：位运算右移   解题思路：   判断 n 最右一位是否为 11 ，根据结果计数。将 n 右移一位（本题要求把数字 n 看作无符号数，因此使用 无符号右移 操作）   算法流程： 初始化数量统计变量 res = 0。 循环逐位判断： 当 n = 0时跳出。 res += n & 1 ： 若 n & 1 = 1，则统计数 resres 加一。 n >>= 1 ： 将二进制数字 n 无符号右移一位（ Java 中无符号右移为 ">>>...

0 点赞评论收藏

分享

2021-06-23 08:49

西北工业大学数据分析师

2021.06.23 在牛客打卡138天！

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务