- 博客(121)
- 资源 (4)
- 收藏
- 关注
RSS订阅原创 面试题35：复杂链表的复制
题目：请实现函数ComplexListNode* Clone(ComplexListNode* pHead)，复制一个复杂链表，在复杂链表中，每个节点除了有一个m_pNext指针指向下一个节点，还有一个m_pSibling指针指向链表中的任意节点或者nullptr。节点的C++定义如下：struct ComplexListNode{ int m_nValue; ComplexListNode* m_pNext; ComplexListNode* m_pSibling;};/
2020-09-07 10:46:22
186
原创 面试题34：二叉树中和为某一值的路径
题目：输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。二叉树节点的定义如下：struct BinaryTreeNode{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;};void FindPath(BinaryTreeNode* pRoot,int expectedSum){ if(pRoot==nu
2020-09-07 09:33:42
166
原创 面试题33：二叉搜索树的后序遍历序列
题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。在后序遍历得到的序列中，最后一个数字是树的根节点的值。数组中前面的数字可以分为两部分：第一部分是左子树节点的值，它们都比根节点的值小；第二部分是右子树节点的值，它们都比根节点的值大。bool VerifySquenceOfBST(int sequence[],int length){ if(sequence==nullptr||length<
2020-09-07 09:03:47
191
原创 面试题32：从上到下打印二叉树
题目一：不分行从上到下打印二叉树从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。二叉树节点的定义如下：struct BinaryTreeNode{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;};void PrintFromTopToBottom(BinaryTreeNode* pTreeRoot){ if(!pTreeRoot) return
2020-08-21 15:46:57
127
原创 面试题31：栈的压入、弹出序列
题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。如果下一个弹出的数字刚好是栈顶数字，那么直接弹出；如果下一个弹出的数字不在栈顶，则把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止；如果所有数字都压入栈后仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列了。bool isPopOrder(const int* pPush,const int* pPop,int nLength){ bo
2020-08-14 16:11:51
89
原创 面试题30：包含min函数的栈
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O（1）。template <typename T>void StackWithMin<T>::push(const T& value){ m_data.push(value); if(m_min.size()==0||value<m_min.top()) m_min.push(value); e
2020-08-14 15:54:26
79
原创 面试题29：顺时针打印矩阵
题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。void PrintMatrixClockwisely(int** numbers,int columns,int rows){ if(numbers==nullptr||columns<=0||rows<=0) return; int start=0; while(columns>start*2&&rows>start*2) {
2020-08-14 15:03:51
68
原创 面试题28：对称的二叉树
题目：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。通过比较二叉树的前序遍历序列和对称前序遍历序列来判断二叉树是不是对称的。如果两个序列是一样的，那么二叉树就是对称的。bool isSymmetrical(BinaryTreeNode* pRoot){ return isSymmetrical(pRoot,pRoot);}bool isSymmetrical(BinaryTreeNode* pRoot1,BinaryTreeNode* pR
2020-08-14 14:18:31
80
原创 面试题27：二叉树的镜像
题目：请完成一个函数，输入一棵二叉树，该函数输出它的镜像。二叉树节点的定义如下：struct BinaryTreeNode{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;};先前序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的两个子节点。当交换完所有非叶节点的左右子节点之后，就得到了树的镜像。void MirrorRecursively(BinaryTreeNode *pNod
2020-08-14 14:08:17
83
原创 面试题26：树的子结构
题目：输入两颗二叉树A和B，判断B是不是A的子结构。二叉树节点的定义如下：struct BinaryTreeNode{ double m_dbValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;};在树A中找到和树B的根节点的值一样的节点R判断树A中以R为根节点的子树是不是包含和树B一样的结构bool HasSubtree(BinaryTreeNode* pRoot1,BinaryTreeNode* pR
2020-08-14 08:56:40
58
原创 面试题25：合并两个排序的链表
题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。链表节点定义如下：ListNode* Merge(ListNode* pHead1,ListNode* pHead2){ if(pHead1==nullptr) return pHead2; else if(pHead2==nullptr) return pHead1; ListNode* pMergedHead=nullptr; if(pHead1->
2020-08-14 08:30:30
76
1
原创 面试题24：反转链表
题目：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。链表节点定义如下：struct ListNode{ int m_nValue; ListNode* m_pNext;};ListNode* ReverseList(ListNode* pHead){ ListNode* pReversedHead=nullptr; ListNode* pNode=pHead; ListNode* pPrev=nullptr; while
2020-08-13 16:30:46
112
原创 面试题23：链表中环的入口节点
先定义两个指针P1和P2指向链表的头节点。如果链表中的环有n个节点，则指针P1先在链表上向前移动n步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口节点时，第一个指针已经围绕着环走了一圈，又回到了入口节点。对于环中节点的数目，在判断一个链表里是否有环时用到了一快一慢两个指针。如果两个指针相遇，则表明链表中存在环。两个指针相遇的节点一定在环中，可以从这个节点出发，一边继续向前移动一边计数，当再次回到这个节点时，就可以得到环中节点数了。ListNode* MeetingNode(ListNode
2020-08-13 15:53:22
87
原创 面试题22：链表中倒数第k个节点
题目：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第一个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。链表节点定义如下：struct ListNode{ int m_nValue; ListNode* m_pNext;};定义两个指针，第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针
2020-08-13 15:30:22
131
原创 面试题21：调整数组顺序使奇数位于偶数前面
题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。只完成基本功能的解法，仅适用于初级程序员可以维护两个指针：第一个指针初始化...
2020-08-13 14:36:33
183
原创 面试题20：表示数值的字符串
题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100“、”5e2“、”-123“、”3.1416“及”-1E-16“都表示数值，但”12e“、”1a3.14“、”1.2.3“、”±5“及”12e+5.4“都不是。bool isNumeric(const char* str){ if(str==nullptr) return false; bool numeric=scanInteger(&str); if(*
2020-08-13 10:59:42
70
原创 面试题19：正则表达式匹配
题目：请实现一个函数用来匹配包含’.‘和’*‘的正则表达式。模式中的字符’.'表示任意一个字符，而’*‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串“aaa”与模式“a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。bool match(char* str,char* pattern){ if(str==nullptr||pattern==nullptr) return false; ret
2020-08-13 10:38:07
101
原创 面试题18：删除链表的节点
题目一：在O（1）时间内删除链表节点。给定单向链表的头指针和一个节点指针，定义一个函数在O（1）时间内删除该节点。链表节点与函数的定义如下：struct ListNode{ int m_nValue; ListNode* m_pNext;};void DeleteNode(ListNode** pListHead,ListNdoe* pToBeDeleted);把下一个节点的内容复制到需要删除的节点上覆盖原有的内容，再把下一个节点删除。当要删除的节点位于链表的尾部，我们仍然
2020-08-13 09:56:36
118
原创 面试题17：打印从1到最大的n位数
题目：输入数字n，按顺序打印出从1到最大的n位十进制数，比如输入3，则打印出1、2、3一直到最大的3位数999。跳进面试官陷阱void Print1ToMaxOfNDigits_1(int n){ int number=1; int i=0; while(i++<n) number*=10; for(i=1;i<number;i++) printf("%d\t",i);}当输入的n很大的时候，求最大的n位数用整型或者长整
2020-08-13 08:57:54
92
原创 面试题16：数值的整数次方
题目：实现函数double Power（double base，int exponent），求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。自以为题目简单的解法double Power(double base,int exponent){ double result=1.0; for(int i=1;i<=exponent;++i) result*=base; return result;}全面但不够高效的解法，我们离Off
2020-08-11 09:18:46
85
原创 面试题15：二进制中1的个数
题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如，把9表示成二进制是1001，有2位是1。因此，如果输入9，则该函数输出2。可能引起死循环的解法先判断整数二进制表示中最右边一位是不是1；接着把输入的整数右移一位，此时原来处于从右边数起的第二位被移到最右边了，再判断是不是1；这样每次移动一位，直到整个整数变成0为止。int NumberOf1(int n){ int count=0; while(n) { if(n&1)
2020-08-09 16:29:11
90
原创 面试题14：剪绳子
题目：给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0]，k[1]，……，k[m]。请问k[0] x k[1] x……x k[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。动态规划int maxProductAfterCutting_solution1(int length){ if(length<2) return 0; if
2020-08-09 15:43:32
96
原创 面试题13：机器人的运动范围
题目：地上有一个m行n列的方格。一个机器人从坐标（0，0）的格子开始移动，它每次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35，37），因为3+5+3+7=18。但它不能进入方格（35，38），因为3+5+3+8=19。请问该机器人能够到达多少个格子？int movingCount(int threshold,int rows,int cols){ if(threshold<0||rows<=0||cols&
2020-08-09 14:57:03
57
原创 面试题12：矩阵中的路径
题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。bool hasPath(char* matrix,int rows,int cols,char* str){ if(matrix==0||rows<1||cols<1||str==nullptr) return false; bool *vi
2020-08-09 11:27:33
67
原创 面试题11：旋转数组的最小数字
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组{3，4，5，1，2}为{1，2，3，4，5}的一个旋转，该数组的最小元素为1.旋转之后的数组实际上可以划分为两个排序的子数组，而且前面子数组的元素都大于或者等于后面子数组的元素。最小的元素刚好是这两个子数组的分界线。使用两个指针，第一个指针总是指向前面递增数组的元素，而第二个指针总是指向后面递增数组的元素。最终第一个指针将指向前面子数组的最后一个元素，而第二个指针会
2020-08-09 10:41:57
90
原创 面试题10：斐波那契数列
题目一：求斐波那契数列的第n项写一个函数，输入n，求斐波那契数列的第n项。斐波那契数列的定义如下：效率很低的解法，挑剔的面试官不会喜欢long long Fibonacci(unsigned int n){ if(n<=0) return 0; if(n==1) return 1; return Fibonacci(n-1)+Fibonacci(n-2);}面试官期待的实用解法long long Fibonacci(unsi
2020-08-09 09:38:43
169
原创 面试题9：用两个栈实现队列
题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入节点和在队列头部删除节点的功能。template <typename T> class CQueue{ public: CQueue(void); ~CQueue(void); void appendTail(const T& node); T deleteHead(); p
2020-08-08 20:19:20
73
原创 面试题8：二叉树的下一个节点
题目：给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左右子节点的指针，还有一个指向父节点的指针。BinaryTreeNode* GetNext(BinaryTreeNode* pNode){ if(pNode==nullptr) return nullptr; BinaryTreeNode* pNext=nullptr; if(pNode->m_pRight!=nullptr)//存在右子树 {
2020-08-08 19:47:59
79
原创 面试题7：重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。二叉树节点的定义如下：struct BinaryTreeNode{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;};BinaryTreeNode* Construct(int* preorder,int* inorder,int length){ if(preorde
2020-08-08 19:27:40
117
原创 面试题6：从尾到头打印链表
题目：输入一个链表的头节点，从尾到头反过来打印出每个节点的值。链表节点定义如下：struct ListNode{ int m_nKey; ListNode* m_pNext;}每经过一个节点的时候，把该节点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出节点的值，此时输出的节点的顺序已经反转过来了。void PrintListReversingly_Iteratively(ListNode* pHead){ std::stack<ListNode> n
2020-08-08 16:32:46
97
原创 面试题5：替换空格
题目：请实现一个函数，把字符串中的每个空格替换成“%20”。例如，输入“We are happy.”，则输出“We%20are%20happy.”。先遍历一次字符串，统计出字符串中空格的总数，并由此计算出替换之后的字符串的总长度。从字符串的后面开始复制和替换，首先准备两个指针：P1和P2。P1指向原始字符串的末尾，而P2指向替换之后的字符串的末尾。接下来我们向前移动指针P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。碰到第一个空格之后，把P1向前移动一格，在P2之前插入字符，重复此操
2020-08-08 15:45:21
73
原创 面试题4：二维数组中的查找
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。首先选取数组中右上角的数字。如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除这个数字所在的行。也就是说，如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。
2020-08-08 14:54:13
78
原创 面试题3：数组中重复的数字
题目一：找出数组中重复的数字在一个长度为n的数组里的所有数字都在0——n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2，3，1，0，2，5，3}，那么对应的输出是重复的数字3或者3。从头到尾依次扫描这个数组中的每个数字。当扫描到下标为i的数字时，首先比较这个数字（用m表示）是不是等于i。如果是，则接着扫描下一个数字；如果不是，则再拿它和第m个数字进行比较。如果它和第m个数字相等，就找到了第一个重
2020-08-08 14:20:16
75
原创 面试题2：实现Singleton模式
题目：设计一个类，我们只能生成该类的一个实例。不好的解法一：只适用于单线程环境由于要求只能生成一个实例，因此我们必须把构造函数设为私有函数以禁止他人创建实例。我们可以定义一个静态的实例，在需要的时候创建该实例。public sealed class Singleton1{ //将构造函数设为私有函数以禁止他人创建实例 private Singleton1() { } private static Singleton1 instance=null;
2020-08-08 10:48:07
104
原创 面试题1：赋值运算符函数
题目：如下为类型CMyString的声明，请为该类型添加赋值运算符函数。class CMyString{ public: CMyString(char* pData=nullptr); CMyString(const CMyString& str); ~CMyString(void); private: char* m_pData;}注意事项：把返回值的类型声明为该类型的引用，并在函数结束前返回实例自身的
2020-08-05 11:10:33
98
原创 折半查找Java语言描述
思路每一次查找，将查找的区间从中间分为两部分，若查找值大于中间的元素，则在右侧区间继续查找；若查找值小于中间的元素，则在左侧区间继续查找。特点折半查找的先决条件是查找表中的数据元素必须有序。代码public int binarySearch(Comparable[] a,Comparable findElem){ int low=0; int high=a.length()-1; int mid; while(low<=high) {
2020-07-19 16:07:28
380
原创 经典排序算法Java语言描述
经典排序算法选择排序思路特点代码插入排序思路特点代码希尔排序思路特点代码归并排序思路特点原地归并自顶向下的归并排序自底向上的归并排序快速排序思路特点代码选择排序思路首先，找到数组中最小的那个元素；其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。特点运行时间和输入无关。为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。一个已经有序的数组或是主键全部相等
2020-07-18 16:17:47
108
原创 CCF:201909-2 小明种苹果（续）
问题描述思路该问题需要统计三个数据，剩下的苹果总数，发生苹果掉落的苹果树的个数和连续三棵发生掉落的组数。苹果的总数可以在输入数据时进行计算，当输入负数时苹果数将减少，输入正数时需要进行比较，若不相等则说明有苹果掉落，修改当前记录的苹果数，使用数组来标记当前的树是否发生了掉落，若有苹果掉落则修改相应的数组元素，连续三棵发生苹果掉落的组数可以使用求余运算来使苹果树围成一个圈统计数目。代码#include<iostream>#include<vector>using na
2020-05-13 16:11:04
141
原创 CCF:201612-2 工资计算
问题描述试题编号： 201612-2试题名称： 工资计算时间限制： 1.0s内存限制： 256.0MB问题描述： 小明的公司每个月给小明发工资，而小明拿到的工资为交完个人所得税之后的工资。假设他一个月的税前工资（扣除五险一金后、未扣税前的工资）为S元，则他应交的个人所得税按如下公式计算： 1） 个人所得税起征点为3500元，若S不超过3500，则不交税，3500元以上的部分才计...
2020-04-11 16:06:01
155
原创 CCF:201409-2 画图
问题描述试题编号： 201409-2试题名称： 画图时间限制： 1.0s内存限制： 256.0MB问题描述： 在一个定义了直角坐标系的纸上，画一个(x1,y1)到(x2,y2)的矩形指将横坐标范围从x1到x2，纵坐标范围从y1到y2之间的区域涂上颜色。 下图给出了一个画了两个矩形的例子。第一个矩形是(1,1) 到(4, 4)，用绿色和紫色表示。第二个矩形是(2, 3)到(6, ...
2020-04-11 14:52:21
94
页面地址重定位算法C++
2019-09-13
银行家算法C++实现（源代码）
2019-09-13
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人