牛客网面试编程题总结（持续更新）
目录
- 面试题回顾（持续更新）
- 完整流程：从头到尾打印[2020年3月31日]
- 二叉树重建算法：重建二叉树[2020年3月31日]
- 队列模拟方法：用两个栈实现队列[2020年4月2日]
- 最小值旋转问题：旋转数组的最小数字[2020年4月2日]
- 质因数分解统计：质因数的统计[2020年4月3日]
- 台阶问题递推解法：跳台阶[2020年4月4日]
- 二进制位计数技巧：二进制中的个数[2020年4月7日]
- 快速幂计算方法：数值的整数次方
面试编程题总结（持续更新）
完整地展示或演示日期：完整地展示或演示 日期：完整地展示或演示
请接收一个链表，并按照指定顺序生成一个ArrayList。具体来说，请采用栈结构来实现逆序处理。
请接收一个链表，并按照指定顺序生成一个ArrayList。具体来说，请采用栈结构来实现逆序处理。
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> value;//注意vector的用法
ListNode *p=NULL;//将p指向头结点
p=head;
stack<int> stk;//栈的使用方式
while(p!=NULL){
stk.push(p->val);//压栈操作
p=p->next;
}
while(!stk.empty()){//while循环中的条件要放.empty()
value.push_back(stk.top());//这是动态数组vector的存数方式。
stk.pop();
}
return value;
}
};总结：
1.这种题目逆序的还是要想到栈的先进后出的特性。
2.掌握vector data：实现了动态数组，用于元素数量变化的对象数组。
vector插入元素的形式是：data.push_back(元素);
vector清空容器：data.clear()；
vector容器的长度：data.size()；
访问vector元素的方式：与访问数组的方式相同
要特别注意vector
3.c++中栈的用法：
push(): 向栈内压入一个成员；
pop(): 从栈顶弹出一个成员；
empty(): 如果栈为空返回true，否则返回false；
top(): 返回栈顶，但不删除成员；
size(): 返回栈内元素的大小；
4.特别注意结构体中value是怎么声明的，别一上来就是p->value;
方法二：数组翻转
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> value;
ListNode *p=NULL;
p = head;
while(p!=NULL){//直接先压如动态数组之中
value.push_back(p->val);
p = p ->next;
}
int temp=0;
int i = 0;
int j=value.size()-1;
while(i<j){//然后直接进行数组翻转就可以了
temp= value[i];
value[i]=value[j];
value[j] = temp;
i++;
j--;
}
return value;
}
};这个跟上面的主要区别在于, 该方法充分利用了vector类数组的性质. 也就是说, 我们可以直接将vector当作一个数组处理, 进而实现代换操作.
class Solution{
public:
vector<int> printListFromTailTohead(ListNode *head){
ListNode *p =NULL;
p = head;
if(p!=NULL){
if(p->next!=NULL){//不断的往下面递归，跑到最末尾。
printListFromTailToHead(p->next);
}
value.push_back(p->val);//跑到最末尾的时候，执行的就是这一句了。
}
return value;
}
};总结：这种方法非常巧妙，在递归过程中不断检查节点p的下一个节点是否为null时，在递归深入到链表末端时（此时节点p所存储的数据即为链表的最后一个元素），就可以将这个元素依次推入到vector容器中，并最终只需调用value()函数即可完成整个操作流程。
重建二叉树2020.3.31
请给出所给二叉树的前序遍历与中序遍历结果，并要求恢复该二叉树的结构。已知输入的前序序列与中序序列均不包含重复元素。例如给出前序序列{1;2;4;7;3;5;6;8}与中序序列{4;7;2;1;5;3;8;6}；则可恢复该二叉树的结构并返回结果
import java.util.*;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length==0){//这是比较小心的操作，当length==0时，直接return null
return null;
}
int rootVal = pre[0];//首先，根据先序遍历拿到根节点
if(pre.length==1)
return new TreeNode(rootVal);//这是返回一课树的表现
TreeNode root = new TreeNode(rootVal);//新建一棵树，开始装左右树。
int rootIndex = 0;//
for(int i=0;i<in.length;i++){//从这个for循环中拿到中序遍历的根节点的地方
if(rootVal==in[i]){
rootIndex = i;
break;
}
}
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,rootIndex+1),Arrays.copyOfRange(in,0,rootIndex));//这个地方就只能靠递归建树了。给出左子树中，先序，中序遍历的序列
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,rootIndex+1,pre.length),Arrays.copyOfRange(in,rootIndex+1,in.length));//这个地方就只能靠递归建树了。给出右子树中，先序，中序遍历的序列
return root;//到最后，你就会因为给出的序列只有一个节点，跳出这个递归
}
}总结：明确指出，在实现递归时必须处理产生的条件。
在此时需要特别注意判断结点数目分别为零和一的情况。
随后确定中序遍历序列中的根节点位置。
随后就可以采用递归的方式进行处理。
对于root节点的左子树范围进行，
在Java中实现这一功能通常会使用Arrays.copyOfRange方法。
注意该函数需要先导入java.util.*包，
并正确指定参数original、from和to，
其中from包含但to不包含
Create copies of arrays using the Arrays.copyOf method.
Extract a range of elements from an array using the Arrays.copyOfRange method.
Copy elements from one array to another using the System.arraycopy method.
Make a clone of an array name using the clone() method.
通过两个栈的巧妙组合来构建队列（日期）：2020年4月2日
class Solution
{
public:
void push(int node) {
stack1.push(node);//先入栈1
}
int pop() {
int a;
if(stack2.empty()){
while(!stack1.empty()){
a = stack1.top();//你要先拿到这个值，再push，或pop，不然，一旦不拿着，直接push或pop就没了
stack2.push(a);
stack1.pop();
}
}
a = stack2.top();
stack2.pop();
return a;
}
private:
stack<int> stack1;
stack<int> stack2;
};总结 ：整体的思路其实很简单，就是在
入队列：直接压栈1
出队列：先判断栈2是否为空，若为空，就得把栈1 的所有元素搞到栈2，让元素把顺序反过来。然后，再开始真正的从栈2出元素。不然，或栈2 不为空的话，就直接从栈2出元素就好了。你画个图，也许就能明白了。
但要注意，我代码中的那一点。出栈时，一定先用stack.top()，拿到要出栈的元素，不然，你压栈的时候，就没办法压了。
旋转数组的最小数字2020.4.2
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
//二分查找使用时，要把0个元素和1个元素的情况都要考虑到。
int length_vector=rotateArray.size();//首先，一定要先考虑特殊情况，length=0的情况
if(length_vector==0)
return 0;
int low = 0;//二分查找的固定套路
int high = length_vector-1;
if(low==high)//只有一个元素时的情况。
return rotateArray[low];
while(low<high){
if(rotateArray[low]<rotateArray[high])//这个if考虑的是旋转后的数组是有序的时候
return rotateArray[low];
if(high==low+1)//这个考虑的是当只有两个元素得到时候
return rotateArray[high];
int mid = (high+low)/2;
if(rotateArray[low]>=rotateArray[mid]&&rotateArray[high]>=rotateArray[mid]){//这个if考虑的是，数组中出现相同元素的时候，只能采用顺序查找了。
int index = low;
for(int i=low+1;i<=high;i++){
if(rotateArray[index]>rotateArray[i])
index = i;//把最小元素的下标就可以找出来了。
}
return rotateArray[index];
}
if(rotateArray[low]<rotateArray[mid])//二分查找的经典方式。
low = mid+1;
else if(rotateArray[high]>rotateArray[mid]) //最小元素在low~mid之间
high=mid-1;
}
return -1;
}
};总结
质因数的统计2020.4.3
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[100006];
int main(){
int n;
cin>>n;
int ans = 0;
for(int i=1;i<=n;i++){//把这个范围内要弄的数放在数组中比较方便
a[i]=i;
}
for(int i=2;i<=n;i++){//确保从a[2]开始，因为质因数的分解从2开始数。
if(a[i]>1){//这是循环的破出条件。
for(int j=2;j<=sqrt(n);j++){//注意这里的sqrt很重要，减少了很多数的比较
while(a[i]%j==0){//不断的除，就能得到想要的那个质数。
a[i] = a[i]/j;
ans++;
// cout<<ans<<endl;
}
}
}
}
for(int i=1;i<=n;i++){//这个地方应该只是确保把本来就是质数的那一个
//也就是上面的循环没有处理的那个算进来，不然，就会少了本来就是质数的那一份。
if(a[i]>1)
ans++;
}
cout<<ans;
return 0;
}总结 ：基本把思路已经写在代码中了，这个代码已经很容易理解了。
跳台阶2020.4.4
题目描述
这只青蛙每一次可以跃过1级台阶，并且也可以跃过2级台阶。请求出该青蛙在面对一个n级台阶时总共有多少种不同的跳跃方法（注意：如果跳跃的先后次序不同，则视为不同的情况）。
class Solution {
public:
int jumpFloor(int number) {
if(number<1){
return 0;
}
else if(number==1){
return 1;
}
else if(number==2){
return 2;
}
else{
int result =0;
int pre1 =0;
int pre2 = 1;
for(int i=1;i<=number;i++){
result = pre1+pre2;
pre1 = pre2;
pre2 = result;
}
return result;
}
}
};总结 :值得深入思考一下,其实这个题目本质上也是一个斐波那契数列问题.虽然递归是一种可行的方法,但这种方案往往会导致资源的巨大浪费,在很多情况下,这样的问题通常难以顺利解决.
二进制领域中的相关数据（2020年4月7日）
#include<cstdio>
#include<iostream>
using namespace std;
int NumberOf1_low(int n) {
int count = 0;
int flag = 1;
while (flag != 0) {
if ((n & flag) != 0) {
count++;
}
flag = flag << 1;//将flag的1进行移位，逐位与n进行相比。
//注意，若对n进行移位，负数会导致死循环，因为对n进行右移时，
//是补1的，所以不能那么做。
}
return count;
}
int main(){
int n;
cin>>n;
cout<<NumberOf1_low(n);
return 0;
}或许还做得不够充分。最初只想到需要用二进制的形式来表示它，并通过逐步地进行循环运算来统计其中有多少个1。然而，在n和1之间进行与操作的时候，它们之间的数值自然以二进制形式呈现
数值的整数次方
public class Solution {
public double Power(double base, int exponent) {
int n=exponent;
//首先要区分好情况。
if(exponent<0){
if(base==0)
throw new RuntimeException("分母不能为0");
exponent = -exponent;
}
else if(exponent==0){
return 1;
}
double res =1,cur =base;
while(exponent!=0){//这个是快速幂的解法，也就是把指数分解成二进制，然后，逐步的乘
if((exponent&1)==1)//如果这个位为1，那就是要乘了。
res*=cur;
cur*=cur;//不管上面这个If是否有执行，那个指数肯定是要翻倍的，比较是2的多少次方。
exponent=exponent>>1;//右移一位，逐渐看一下指数的二进制形式的各个位。
}
if(n>=0)//判断当时的指数是正数还是负数。
return res;
else{
return 1/res;
}
}
}总结