- 博客(35)
- 收藏
- 关注
RSS订阅
原创 程序员面试宝典 知识点总结
1.C语言，printf计算参数是是从右向左计算的，如printf("%d,%d\n",a++,b++) 此时，先计算b++，然后计算a++。2.x&y+(x^y>>2) 表示x于y的平均数。分为三部分，第一部分是两个数二进制均为1的位，&后还为1，相当于取和后除以2。第二部分，两个数有一个为1的位相加，然后右移两位相当于除以二，第三部分，全为0的部分，取和无...
2018-09-11 15:16:43
553
原创 33 二叉搜索树的后序遍历
二叉搜索树：任意节点，左子树所有的节点比根节点小，右子树的所有节点比根节点大。题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。思路：1。后序遍历，先找到根节点，最后一个数2.判断第一个数是否小于根节点，若是，说明有左子树，向后遍历，直到大于根节点，则为右子树的开始元素3.继续遍历，若...
2018-07-31 10:18:43
130
转载 35 复杂链表的复制
题目：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）思路：1.复制每一个节点，接在原节点的后面。A->A'->B->B'->C->C' .......2.设置第二指向节点。假设n指向s，则复...
2018-07-30 16:54:06
156
原创 52 两个链表的第一个公共节点
题目：输入两个链表，找出它们的第一个公共结点。方法一：1.遍历两个链表，长度分布为m和n （m>n） 2.让长的先走（m-n）步， 3. 两链表同时同速开始遍历，当元素相同时，即为第一个公共节点。代码：/*struct ListNode { int val; struct ListNode *next; ...
2018-07-30 11:47:26
111
原创 23.链表中环的入口节点
题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。思路：代码：/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution {publ...
2018-07-29 16:20:22
102
转载 20 表示数值的字符串
题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。 思路： [sign]integral-digit
2018-07-27 16:35:08
142
转载 42.连续子数组的最大和
题目：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少...
2018-07-25 21:28:46
59
原创 面试题40 ：最小的k个数
题目：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。思路：1.最简单直观的办法，对输入的数组进行排序，取出前k个数。但时间复杂度为o(nlogn)。class Solution {public: vector<int> GetLeastNumbers_Solution(vector<i...
2018-07-24 21:28:23
119
原创 数组中出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。思路：思路一 对数组排序，如果符合条件的数存在，一定是数组中间的那个数。但用到了排序，时间复杂度至少o(nlogn)。 思路二：如果有符合条件的数字，则它出...
2018-07-24 11:31:19
83
转载 栈的压入与弹出序列
题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的） 思路：模拟堆栈操作：将原数列依次压栈，栈顶元素与所给出栈队列相比，如果相同则出栈，...
2018-07-24 10:35:45
151
转载 包含min函数的栈
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。思路：定义两个栈data 和Min 考虑使用2个栈，一个用于保存待压入的数据，另一个栈专门用于保存最小值。初始：2个栈都为空 将元素都压入进去。之后：如果待压入的元素 <= 最小值栈的栈顶元素 那么同样需要将元素压进2个栈。否则 只需要将元素压进数据栈。...
2018-07-23 22:05:38
98
原创 旋转数组的最小值
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 思路：用二分查找法，该数组是两个有序的数组组成。第一个数一定是大于或等于最后一个数。取中间值，如果中间值大于...
2018-07-20 10:43:46
459
转载 归并排序
首先将二个有序数列合并：，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。//将有序数组a[]和b[]合并到c[]中 void MemeryArray(int a[], int n, int b[], int m, int c[]) { int i, j, k; ...
2018-07-19 11:15:38
93
转载 二叉树为某一值的路径
题目：输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前) 思路：深度优先搜索。使用前序遍历，使用两个全局变量result和tmp，result来存放最终结果，tmp用来存放临时结果。每次遍历，我们先把root的值压入tmp，然后判断...
2018-07-17 14:59:16
112
原创 面试题28 对称的二叉树
题目：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。思路：我们通常有三种不同的二叉树遍历算法，即前序遍历、中序遍历和后序遍历。在这三种遍历算法中，都是先遍历左子结点再遍历右子结点。以前序遍历为例，我们可以定义一个遍历算法，先遍历右子结点再遍历左子结点，暂且称其为前序遍历的对称遍历。遍历第一棵树，前序遍历的遍历序列为{8,6,5,7,6...
2018-07-12 21:29:41
159
原创 面试题65：不用加法进行求和
题目：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。思路：首先看十进制是如何做的： 5+7=12，可以使用三步走：第一步：相加各位的值，不算进位，得到2。第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。 同样我们可以三步走的方式计算二进制值相加： 5...
2018-07-12 16:44:21
359
原创 面试题26 树的子结构
题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）思路：第一步：现在A中找到与B的根节点一样值的节点R 第二步：判断A中以R为根节点的子树是否包含和B一样的子结构。class Solution {public: bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {...
2018-07-12 15:36:00
130
原创 面试题 3 是数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。思路一：排序后遍历数组class Solution {public: // Parameters: // ...
2018-07-11 22:05:51
82
原创 调整数组顺序是奇数在偶数前面
题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。思路：建立一个双向队列，从数组的前后同时开始遍历，正向判断若为偶数，在从队列的队尾插入，反向判断，若为奇数，则从队列的头开始插入。 class Solution {public: void ...
2018-07-11 20:24:33
112
原创 剑指offer 面试题7 重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。思路：首先找到根结点的值（前序遍历第一个值），开辟一个空间存储根节点。然后在中序遍历中搜索该值，为中序遍历中的根节点，中序遍历中根节点前的值为左子树的值，右边...
2018-07-09 21:59:48
172
原创 按之字形顺序打印二叉树
题目：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。思路：与按行打印思路相思，定义一个队列，将元素的孩子一次插入队列，销毁该元素。但每行输出时要判断是奇数还是偶数，偶数列时用反转序列std::reverse(反转区间) ，然后再输出。class Solution {public: vecto...
2018-07-03 14:56:43
89
原创 剑指offer 面试题15：二进制中1的个数
题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。分析：首先把输入的数与 1做位 与 ，判断n的最低位是否为1，而后将1右移，再与n做位与，判断右数第二位是否为1。。。。。依次循环，最后判断出共有多少个1。class Solution {public: int NumberOf1(int n) { int count=0; u...
2018-06-27 21:38:30
80
原创 剑指offer 面试题10：斐波那契数列
题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39分析：首先想到的就是递归方法，但此时时间复杂度太大，主要原因就是有很多值是重复计算的，因为每一次函数调用都会在栈中分配内存空间，当递归调用的层数太多时就会造成栈溢出。class Solution {public: int Fibonacci(int n) { if(n...
2018-06-26 09:46:30
149
原创 剑指offer 面试题27 二叉树的镜像
题目：操作给定的二叉树，将其变换为源二叉树的镜像。二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5思路：遍历每个节点，如果该节...
2018-06-25 19:46:17
62
原创 剑指offer 面试题32：从上到下打印二叉树
题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印。/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};*/class Solution {public: ...
2018-06-25 19:30:46
147
原创 :分层打印二叉树
题目：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};...
2018-06-25 19:12:39
176
原创 剑指offer 面试题9 用两个栈去实现队列
题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。思路：由于栈是后入先出，队列是先入先出。实现时，输入元素时，将元素压入stack1中，删除元素时，先将stack1中的元素出栈，全部压入stack2中再出栈，这样元素的位置将倒置，实现先入先出的功能。操作：入队：将元素进栈1出队：判断栈2是否为空，如果为空，则将栈1中所有元素pop，并push进栈2，栈2出栈...
2018-06-25 15:26:44
68
转载 #ifndef 条件编译
条件指示符#ifndef 的最主要目的是防止头文件的重复包含和编译。假如你有一个C源文件，它包含了多个头文件，比如头文件A和头文件B，而头文件B又包含了头文件A，则最终的效果是，该源文件包含了两次头文件A。如果你在头文件A里定义了结构体或者类类型（这是最常见的情况），那么问题来了，编译时会报大量的重复定义错误。例如要编写头文件test.h在头文件开头写上两行：#ifndef _TEST_H#def...
2018-05-24 10:33:13
955
原创 剑指offer 面试题22 链表中倒数第k个节点
题目：输入一个链表，输出该链表中倒数第k个结点。思路一：最简单的思路是：先遍历一次链表，得出共n个节点，倒数第k个，既是正数第n-k+1个节点，直接遍历到第n-k+1个节点即可，但是需要遍历两次链表，如果需要遍历一次链表的方法时用思路二。思路二：定义两个指针，第一个指针先指向第k个节点，既向前走k-1步，然后另第二个指针指向头结点，然后两个指针一起向后移动，直到第一个指针走到最后一个节点时，此时第...
2018-05-17 19:33:52
153
原创 剑指offer 面试题25 合并两个排序链表
题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。思路：建立一个新的链表，定义两个指针分别指向两个链表的开头，比较两个值的大小，选取小的接在新链表的后面，然后将该指针后移，进行递归。注意，当其中一个指针指向NULL,则返回另一个指针。class Solution {public: ListNode* Merge(ListNode* pHea...
2018-05-17 15:07:44
136
转载 剑指offer 源代码链接（GitHub）
https://github.com/zhedahht/CodingInterviewChinese2
2018-05-17 10:12:49
9647
1
转载 剑指offer 面试题24 链表反转
题目:输入一个链表，反转链表后，输出链表的所有元素。思路：需要定义三个节点，当前节点pNode，前一节点pPre，和后一节点pNext。要将当前节点的下一节点pNode->next用下一节点储存起来，避免在反转时发生链表断裂。然后将当前节点指向前一节点，然后将当前节点的指针移到下一节点，前一节点和有一节点同时移动。要注意：如果只有一个节点，直接返回当前节点判断输入的链表是否为空注意防止反转后...
2018-05-16 20:42:42
117
原创 剑指offer 面试题6 从尾到头打印链表
题目：输入一个链表，从尾到头打印链表每个节点的值。遍历链表，输出是从头到尾，而我们需要的是从尾到头打印，这是典型的”先进后出"，可以用栈实现。也可以将数据导入vector中，从头开始，每一个节点的数据都插入vector的最开始（利用value.insert(value.begin(),head->val))，再遍历整个vector方法一：利用容器class Solution {public...
2018-05-16 16:18:19
180
原创 剑指offer 面试题5 替换空格
class Solution {public: void replaceSpace(char *str,int length) { if(str==NULL||length<=0) return; int i=0; int str_length= 0; int replac...
2018-05-15 22:03:21
129
原创 剑指offer 面试题4 二维数组的查找
从左下角开始比较，如果查找数更小，则上移，若更大，则右移。class Solution {public: bool Find(int target, vector<vector<int> > array) //二维向量，连个< 之间的空格不可少，n个外层向量向量，每个向量里又 { ...
2018-05-14 22:14:58
63
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人