程序员面试金典

时间：2022-12-29 00:37:41

1.有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶、3阶。请实现一个方法，计算小孩有多少种上楼的方式。为了防止溢出，请将结果Mod 1000000007

给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100000。

int countWays(int n) {
// write code here

if(n<=0) return 0;
else if(1==n) return 1;
else if(2==n) return 2;
else if(3==n) return 4;

long long i,n1=1,n2=2,n3=4,n4;
for(i=4;i<=n;i++){
            n4=((n1+n2)%1000000007+n3)%1000000007;
            n1=n2%1000000007;
            n2=n3%1000000007;
            n3=n4%1000000007;
        }
return n4;
    }

中间计算结果会溢出，故如此处理。。。

 

2.编写一个函数，确定需要改变几个位，才能将整数A转变成整数B。

给定两个整数int A，int B。请返回需要改变的数位个数。

int calcCost(int A, int B) {
// write code here

int i=0,x=A^B;
while(x){
++i;
            x=x&(x-1);
        }
return i;
    }

 

3.从尾到头打印链表

输入一个链表，从尾到头打印链表每个节点的值。

vector<int> printListFromTailToHead(struct ListNode* head) {
        stack<int> value;
        vector<int> res;

if(NULL==head) return res;
else if(head->next==NULL){
            res.push_back(head->val);
return res;
        }

struct ListNode* temp=head;
while(temp){
            value.push(temp->val);
            temp=temp->next;
        }

int val;
while(value.size()>0){
            val=value.top();
            value.pop();
            res.push_back(val);
        }

return res;
    }

 

4.奇偶位交换

请编写程序交换一个数的二进制的奇数位和偶数位。（使用越少的指令越好）

给定一个int x，请返回交换后的数int。

 int exchangeOddEven(int x) {
// write code here

//奇数位右移，0xaaaa aaaa=10101010 10101010 10101010 10101010 10101010 10101010 10101010 10101010b; 
int odd=(x&0xaaaaaaaa)>>1;  
//偶数位左移,0x5555 5555=01010101 01010101 01010101 01010101 01010101 01010101 01010101 01010101b;
int eve=(x&0x55555555)<<1;
return odd|eve;
    }

简直了，不能再巧妙了。

 

5.实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。

给定带删除的节点，请执行删除操作，若该节点为尾节点，返回false，否则返回true

bool removeNode(ListNode* pNode) {
// write code here

if(NULL==pNode) return false;
else if(pNode->next==NULL){
return false;
        }else{
            pNode->val=pNode->next->val;
            pNode->next=pNode->next->next;
return true;
        }
    }

 

6.有序数组合并

有两个从小到大排序以后的数组A和B，其中A的末端有足够的缓冲空容纳B。请编写一个方法，将B合并入A并排序。

给定两个有序int数组A和B，A中的缓冲空用0填充，同时给定A和B的真实大小int n和int m，请返回合并后的数组。

（此题的鲁棒性不行，未做特例判断，后续添加）

class Merge {
public:
    vector<int> mergeAB(vector<int> A, vector<int> B, int n, int m) {
// write code here

int i=n-1,j=m-1,k=n+m-1;

while(i>=0&&j>=0){
if(A[i]>B[j]){
                A[k]=A[i];
--k;--i;
            }else if(A[i]<B[j]){
                A[k]=B[j];
--k;--j;
            }else{
                A[k]=A[i];
--k;--i;
                A[k]=B[j];
--k;--j;
            }
        }

if(i>=0){
for(i;i>=0;--i,--k){
                A[k]=A[i];
            }
        }else{
for(j;j>=0;--j,--k){
                A[k]=B[j];
            }
        }

return A;
    }
};

 

7.最大连续数列和

对于一个有正有负的整数数组，请找出总和最大的连续数列。

给定一个int数组A和数组大小n，请返回最大的连续数列的和。保证n的大小小于等于3000。

class MaxSum {
public:
int getMaxSum(vector<int> A, int n) {
// write code here

int len=A.size();
if(0==len){
return 0;
        }else if(1==len){
return A[0];
        } 

int i,cursum=A[0],sum=A[0];
for(i=1;i<len;i++){

if(cursum<0){
                cursum=A[i];
            }else{
                cursum+=A[i];
            }

if(sum<cursum){
                sum=cursum;
            }
        }

return sum;
    }
};

 

8.阶乘尾零

class Factor {
public:
int getFactorSuffixZero(int n) {
// write code here

int res=0;

while(n){
            res+=n/5;
            n/=5;
        }

return res;
    }
};

 

9.基本字符串压缩

利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如，字符串“aabcccccaaa”经压缩会变成“a2b1c5a3”。若压缩后的字符串没有变短，则返回原先的字符串。

给定一个string iniString为待压缩的串(长度小于等于3000)，保证串内字符均由大小写英文字母组成，返回一个string，为所求的压缩后或未变化的串。

（原本想着偷懒，调用库函数实现整数转换为字符串，不过发现那似乎是CString的专利，string如此很麻烦，还是造了一个简陋的*）

class Zipper {
public:
string zipString(string iniString) {
// write code here

int i=0,n=1,len=iniString.length();
char s=iniString[0];
string str(" "),num;
        str[0]=s;

for(i=1;i<len;i++){

if(iniString[i]==s){
++n;
            }else{ 
                str+=num2str(n);
                str+=iniString[i];

//重新初始化
                s=iniString[i]; n=1;
            }
        }
        str+=num2str(n);

if(str.length()<len){
return str;
        }else{
return iniString;
        }
    }

private:
//此处num必然大于等于1，为避免外界调用,设置为私有格式
//num=0时需特殊对待,负数的话可以考虑传递进来的时候传入一个负数标志
string num2str(int num) {

int i = 0, n = 0;
string s1, s2;

while (num) {    
           n = num % 10;
           num = num / 10;
           s1 += '0' + n;
       }

for (i = s1.length()-1;i >= 0;--i) {    
           s2 += s1[i];
       }
return s2;
    }
};

 

10.二叉平衡树检查

注意这里面的运算优先级。。。三目运算符的优先级较低

程序员面试金典程序员面试金典
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Balance {
public:
bool isBalance(TreeNode* root) {
// write code here

int depth=0;
if(NULL==root)
return true;
else return BalaceDepth(root,depth);
    }

bool BalaceDepth(TreeNode* root,int& depth){

if(NULL==root){
            depth=0;return true;
        }

int left=0,right=0,diff;
if(BalaceDepth(root->left,left)&&BalaceDepth(root->right,right)){
            diff=left-right;
if(diff<=1&&diff>=-1){
//三目运算符的优先级较低,如果不添加括号,会先执行+left
                depth=1+(left>right?left:right);
return true;
            }
return false;
        }
return false;
    }
};
View Code

 

标签：

相关文章