pretty.accident - 个人主页动态 - 牛客网

发布(126) 评论刷题

2020-07-07 20:11

华东理工大学测试开发

JZ40 数组中只出现一次的数字

题目描述 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 思路 创建一个set(或者unordered_set)，遍历数组，如果set中有，那就删除set中的这个数字；如果没有，就加入；最终set中留下的就是两个只出现一次的数字。 这里一开始遇到了一个问题，怎么去取set中的数字呢(注意不能用set[i]去取)，我这里是定义了一个迭代器begin 代码 class Solution { public: void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { ...

0 点赞评论收藏

分享

2020-07-07 19:46

华东理工大学测试开发

JZ39 平衡二叉树*

题目描述 输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树 思路 平衡二叉树：对于任何一棵子树，左右子树的高度相差不超过1对于任何一个节点满足条件：左右子树的高度相差不超过1跟左右子树要信息：高度 下面求高度对于任何一个节点的高度：左右子树的最大深度+1跟左右子树要信息：深度 代码 class Solution { public: bool IsBalanced_Solution(TreeNode* pRoot) { if(pRoot==NULL) return true; ...

0 点赞评论收藏

分享

2020-07-07 17:19

华东理工大学测试开发

JZ38 二叉树的深度

题目描述 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 思路 对于每一个节点来说，需要知道它左子树的深度和它右子树的深度，然后取较大值再加1，就是它自己的深度了 代码 class Solution { public: int TreeDepth(TreeNode* pRoot) { if(pRoot==NULL) return 0; return max(TreeDepth(pRoot->left),TreeDepth(pRoot->r...

0 点赞评论收藏

分享

2020-07-07 17:13

华东理工大学测试开发

JZ37 数字在排序数组中出现的次数

题目描述 统计一个数字在排序数组中出现的次数。 思路 暴力遍历法(果然我还是只能想到暴力法)，但是这种方法就没有体现出排序数组的优势啊

0 点赞评论收藏

分享

2020-07-07 17:05

已编辑

华东理工大学测试开发

JZ36 两个链表的第一个公共节点*

题目描述 输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的） 方法1(使用set) 思路 利用unordered_set容器存放数据不重复的思想，将链表1的节点全都放进unordered_set容器中去，然后遍历链表2，在容器中找有没有链表2的节点，第一次找到的节点就是两个链表的第一个公共节点 代码 class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { uno...

0 点赞评论收藏

分享

2020-07-07 16:30

华东理工大学测试开发

JZ35 数组中的逆序对****

题目描述 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

0 点赞评论收藏

分享

2020-07-07 16:08

华东理工大学测试开发

JZ34 第一次只出现一次的字符*

题目描述 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数） 思路 关键：可以定义一个哈希表来存放字符串中每个字符出现的次数——key为字符型(字符)，value为整型(个数) 第一次遍历字符串，数一下每个字符出现的次数(如果字符串中有这个字符，就直接value++；如果没有，就将这个字符存进去) 第二次遍历字符串，看哪一个是第一次只出现一次的字符 代码 class Solution { public: int FirstNotRepeatingChar(...

0 点赞评论收藏

分享

2020-07-06 16:27

华东理工大学测试开发

题目描述 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。 方法1(最笨的方法) 思路 依次判断每一个整数是否为丑数，但是这种方法的时间效率太低，因为需要对每一个整数进行判断(但是这种方法我也没想到)丑数满足：(1)包含2,3,5的因子 (2)只包含2,3,5的因子(1) 如果能整除2/3/5——number%2==0就代表含有2/3/5的因子(2) 只含有，如果能整除2，那就除以2；如果能整除3，那就除以3；如果能整除5，那就除以5；直到最后如果为1，则表示是...

0 点赞评论收藏

分享

2020-07-06 15:06

已编辑

华东理工大学测试开发

JZ32 把数组排成最小的数

题目描述 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。 思路 我一开始想的是：先将3,32组合好(332>323)，所以前面两个的组合为(323)，然后和后面再组合(323321>321323)，所以结果为321323这样是不对的，你不能把前面的组合好了再去和后面一个进行组合，虽然题目中的事例是可以的，但是再举个例子：输入：[3,5,1,4,2]照上面这么想的话结果就是：13542，1,3,5排好了但是2,4应该往里插入，这样就错了，结果应该是1234...

0 点赞评论收藏

分享

2020-07-02 19:47

华东理工大学测试开发

JZ31 1~n整数中出现的次数

题目描述 求出1~ 13的整数中1出现的次数,并算出100~ 1300的整数中1出现的次数？为此他特别数了一下1~ 13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。 思路 两种比较容易想到的方法(虽然我自己是没想到) 方法1 用to_string函数将整数化为字符串，然后数每个字符串中‘1’的个数但是比较耗时代码： class Solution { public: int NumberOf1Between1...

0 点赞评论收藏

分享

2020-07-02 19:15

华东理工大学测试开发

JZ30 连续子数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1) 思路 关键在于：最关键的不是当前值，而是前面的累加和，如果前面的累加和是小于0的，那么就可以直接抛弃，然后从当前重新开始累加；如果前面的累加和是大于...

0 点赞评论收藏

分享

2020-07-02 17:16

华东理工大学测试开发

JZ29 最小的k个数

题目描述 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。 思路 看到题目第一反应是用冒泡排序，但是不需要全部排完序，因为只要最小的k个数，所以外循环只需要k次就行了但是！！！注意，注意特殊情况，k大于数组长度的情况！！！ 我想说 几种排序方法每次面试笔试前都得看一下思路，最好能写一下程序 代码 class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { ...

0 点赞评论收藏

分享

2020-07-02 17:04

华东理工大学测试开发

JZ28 数组中出现次数超过一半的数字

题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 思路 将数组进行排序，然后遍历这个数组；定义一个count用于计数，定义一个pre用于保存前一个数字；若当前数等于前一个数，count++；若当前数不等于前一个数，则重置count，这里直接置为1(有先归0再++的含义)，并且将pre更新；比较count和half值，若大于，就返回当前数遍历结束后，直接返回0(如果遍历结束跳出循环了，说明没有个数大于一半的)注意：一开始没有考...

0 点赞评论收藏

分享

2020-07-02 16:13

华东理工大学测试开发

JZ27 字符串的排列****

题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。思路

0 点赞评论收藏

分享

2020-07-02 11:41

华东理工大学测试开发

JZ26 二叉搜索树与双向链表***

题目描述 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向 思路 大体思路懂了，但是递归还是有点迷糊通过画图我们可以知道，将二叉搜索树转换成双向链表，需要对根的左右指针进行操作，将根的左指针指向左子树的最右，将根的右指针指向右子树的最左关键点：按照中序遍历的顺序(左->根->右)所以当遍历到根的时候，左子树的最右就是当前链表的尾结点；而右子树的最左就是遍历右子树的第一个节点 代码 class Solution { public: TreeNode* Convert(TreeNode* pRootOfTree) ...

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务