剑指offer 第一天

一些有用的废话

远程写代码注意点

• 思考清楚再开始编码 脑子永远应该在手前面 不止是面试，任何事都是如此。
• 良好的代码命名和缩进习惯 我叫sunny怎么了那篇招聘一个靠谱的 iOS第一题就是风格纠错题，大家可以去看看。
• 能够单元测试

高质量的代码

• 考虑边界 错误处理等

清晰的思路

• 举几个简单的例子
• 用图形表示抽象的数据结构
• 把复杂问题分解成若干子问题

应聘提问环节推荐问与招聘的职位或者项目相关的问题

数据结构

数组

数组根据下标读写的特点时间效率非常高，可以用数组实现简单的哈希表。

面试题 二维数组的查找

屏幕快照 2016-03-29 下午7.43.26.png

首先我们可以在纸上画出一个二维数组，假设查找7。当我们从右上角开始查找时，无非就三种情况，
该元素等于7，那么查找成功，打印出所在行列
该元素小于7，该行所有元素都小于7 该行不用找了
该元素大于7，该列所有元素都大于7 该列不用找了。
思路理清以后 可以写代码了
关键代码如下

void Find(int cols,int rows){
if (cols>0&&rows>0) {
    int row=0;
    int col=cols-1;
    while (row <rows && col>=0) {
        //右上角元素
        if (a[row][col]==x) {
            printf("%d行%d列",row+1,col+1);
            //return;
        }else if (a[row][col]>x){
            col--;
        }else{
            row++;
        }
    }
}
return;
   }

从左下角也可以，代码如下

void LeftFind(int cols,int rows){
if (cols>0&&rows>0){
int row=rows-1;
int col=0;
while (col<cols&&row>=0) {
    if (a[row][col]==x) {
        printf("%d行%d列",row+1,col+1);
        
    }else if (a[row][col]<x){
        col++;
    }else{
        row--;
    }
}
}
return;

}
本题的思考 当遇到一个复杂问题时，不要急着编码，可以通过画图用具体的例子寻找规律。

字符串

屏幕快照 2016-03-29 下午8.13.44.png
一种减少移动次数的方法 先遍历字符串统计出空格的总数，算好扩展后的字符串长度，然后从后向前替换。
关键代码如下

void ReplaceBlank(char string[]){
if (string==NULL) {
    return;
}
int index1=0;
int index2=0;
    int blankCount=0;
//遍历字符串,让index1指向最后一个字符 并统计空格数
while (string[index1]!='\0') {
   if (string[index1]==' ') {
        blankCount++;
    }
    index1++;
    
}

int newlength=index1+blankCount*2;
index2=newlength;
while (index1>=0&&index1<index2) {
    if (string[index1]==' ') {
        
        string[index2--]='0';
        string[index2--]='1';
        string[index2--]='%';
    }else{
        string[index2--]=string[index1];
        }
    index1--;
}
}

相关题目 两个排序好的数组a b a有足够空间容纳b 写一个函数把b中所有数字插到a中
本题的思考 合并数组和字符串，我们可以考虑通过从后向前复制减少移动次数
代码

void insert(){
int i=5;
int j=10;
for (int k=4; k>=0; k--) {
    //当b元素小于a时 移动a中元素
        while (b[k]<a[i]&&i>=0) {
            a[j]=a[i];
            j--;
            i--;
        }
    //b中元素大于等于a中的元素 插入a
        //如果a全部移到后面 那么不用比较 把b全部插入
        if (i==0) {
            while (k>=0) {
                a[j]=b[k];
                j--;
                k--;
                return;
            }
        }
        a[j]=b[k];
        j--;
     }
}