程序员面试金典2

1.魔术索引（1）

class MagicIndex {
public:
bool findMagicIndex(vector<int> A, int n) {
int len=A.size();
if(len<=0||len!=n) return false;

int left=0,right=len-1,mid;
while(left<=right){
            mid=(left+right);
if(A[mid]==mid)
return true;
else{
if(A[mid]<mid)
                    left=mid+1;
else right=mid-1;
            }
        }

return false;
    }
};

切记二分查找是left<=right...

 

2.魔术索引2（切记抓住数据规律）

class MagicIndex {
public:
bool findMagicIndex(vector<int> A, int n) {
return find(A,A.size(),0,A.size()-1);
    }

private:
bool find(vector<int>& data,const int& len,int left,int right){
if(right<left||left<0||right>=len)
return false;

int mid=left+(right-left)/2;
int midval=data[mid];
if(midval==mid)
return true;

//搜索左半部分
int leftindex=((mid-1)<midval)?(mid-1):midval;
if(find(data,len,left,leftindex))
return true;

int rightindex=((mid+1)>midval)?(mid+1):midval;
if(find(data,len,rightindex,right))
return true;

return false;
    }
};

 

3.机器人走方格

看着别人的思路，尽然能错n次，数组越界都不知道。。。无语

class Robot {
public:
int countWays(vector<vector<int>> map, int x, int y) {

if (x <= 0 || y <= 0 || x > 50 || y > 50)
return -1;

int i, j;
long vec[51][51] = { 0 };

//注意数值是否越界
for (i = 0; i < x; i++)
        {
if (map[i][0] != 1) break;
else vec[i][0] = 1;
        }
for (i = 0; i < y; i++)
        {
if (map[0][i] != 1) break;
else vec[0][i] = 1;
        }

for (i = 1; i < x; i++)
        {
for (j = 1; j < y; j++)
            {
if (map[i][j] == 1)
                    vec[i][j] = (vec[i - 1][j] + vec[i][j - 1]) % 1000000007;
            }
        }
return vec[x-1][y-1];
    }
};

 

4.硬币表示

没看懂，待后续进一步学习dp。。。

class Coins {
public:
int countWays(int n) {
if (n <= 0) return 0;
else return getnum(n);
    }

private:
int getnum(int n)
    {
int i, j, tmp = 0, data[4] = { 25,10,5,1 };
int dpcoin[100001] = { 0 };

        dpcoin[0] = 1;
for (i = 0; i < 4; i++)
        {
for (j = data[i]; j <= n; j++)
            {
                dpcoin[j] = (dpcoin[j] + dpcoin[j - data[i]]) % 1000000007;
            }
        }

return dpcoin[n];
    }
};

 

3.输出单层二叉树节点

class TreeLevel {
public:
    ListNode* getTreeLevel(TreeNode* root, int dep) {

if (NULL == root || dep < 0)
return NULL;

if (0 == dep) { //根节点判断
            ListNode *res = new ListNode(root->val);
return res;
        }

int nextlevel = 0, delnum = 1, depth = 1;
        ListNode *res = NULL, *pnode;
        queue<TreeNode*> sdata;
        sdata.push(root);

while (!sdata.empty()) {

            TreeNode* tmp = sdata.front();
if (depth == dep) {
if (res == NULL) {
                    res = new ListNode(tmp->val);
                    pnode = res;
                }
else {
                    ListNode* next = new ListNode(tmp->val);
                    pnode->next = next;
                    pnode = pnode->next;
                }
            }
if (tmp->left != NULL) {
++nextlevel;
                sdata.push(tmp->left);
            }
if (tmp->right != NULL) {
++nextlevel;
                sdata.push(tmp->right);
            }
--delnum;sdata.pop();

if (0 == delnum) {

if (depth == dep)
break;  //指定层节点输出完毕

                ++depth;
                delnum = nextlevel;
                nextlevel = 0; //置零统计下一层数目
            }
        }
return res;
    }
};

 

4.链式A+B

class Plus {
public:
    ListNode* plusAB(ListNode* a, ListNode* b) {

if (NULL == a || NULL == b)
return NULL;

int val;
bool sign = false;
        ListNode *tmp1 = a, *tmp2 = b, *res, *pnode;

        res = new ListNode(-1);pnode = res;

while (tmp1&&tmp2)
        {
if (sign)
                val = tmp1->val + tmp2->val + 1;
else val = tmp1->val + tmp2->val;

if (val >= 10) //确定是否需要进位
                sign = true;
else sign = false;
            pnode->next = new ListNode(val % 10);
            pnode = pnode->next;

            tmp1 = tmp1->next;
            tmp2 = tmp2->next;
        }

if (tmp1)
        {
while (tmp1)
            {
if (sign)
                    val = tmp1->val + 1;
else val = tmp1->val;

if (val >= 10)
                    sign = true;
else sign = false;

                pnode->next = new ListNode(val % 10);
                pnode = pnode->next;
                tmp1 = tmp1->next;
            }
        }
if (tmp2)
        {
while (tmp2)
            {
if (sign)
                    val = tmp2->val + 1;
else val = tmp2->val;

if (val >= 10)
                    sign = true;
else sign = false;

                pnode->next = new ListNode(val % 10);
                pnode = pnode->next;
                tmp2 = tmp2->next;
            }
        }
if (sign)
        {
            pnode->next = new ListNode(1);
        }

        pnode = res->next;
delete res;
return pnode;
    }
};

 

5.最小调整有序

有一个整数数组，请编写一个函数，找出索引m和n，只要将m和n之间的元素排好序，整个数组就是有序的。

注意：n-m应该越小越好，也就是说，找出符合条件的最短序列。

class Rearrange {
public:
    vector<int> findSegment(vector<int> A, int n) {

        vector<int> res(2,0);
if (n != A.size()) return res;

        vector<int> sortvt(A);
        sort(sortvt.begin(), sortvt.end());

int left = 0, right = n - 1;
while (left <= n - 1)
        {
if (sortvt[left] != A[left])
break;
else ++left;
        }
if (left == n) //A为有序数组
return res;

while (right >= left)
        {
if (sortvt[right] != A[right])
break;
else --right;
        }

        res[0] = left;
        res[1] = right;
return res;
    }
};