面试题4：替换空格

字符串是由若干字符组成的序列。

c/c++中每个字符串都以字符'\0'作为结尾，因此每个字符串中都有一个额外字符的开销。

为了节省内存，c/c++把常量字符串放到单独的一个内存区域。当几个指针赋值给相同的常量字符串时，他们实际会指向相同的内存地址，但用常量内存初始化数组，则不会指向同一个内存地址。

在c#中封装的字符串类型System.String，其内容是不能改变的，一旦试图改变 其内容，就会产生新的实例。

面试题4：替换空格

先计算出空格数量，得出替换后的字符串长度，再进行移动，时间复杂度为o（n）

若边判断空格，边替换，则每次替换要移动后续的字符串，使得时间复杂度达到o（n2）

//题目描述 // //请实现一个函数，将一个字符串中的空格替换成"%20"。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 #include<string> #include<iostream> #include<windows.h> using namespace std; class Solution { public: void replaceSpace(char *str,int length) { int cnt=0; for(int i=0;i<length;i++){ if(*(str+i)==' ')cnt++; } int len=length+2*cnt; for(int i=length;i>0;i--){ if(*(str+i)==' '){ str[len--]='0'; str[len--]='2'; str[len--]='%'; }else{ str[len--]=*(str+i); } } } }; int main(){ char str[]="We Are Happy"; // 如果使用char* str="We Are Happy"就会出错 Solution test=Solution(); test.replaceSpace(str,12); cout<<str; system("pause"); return 0; }

已使用 Microsoft OneNote 2010 创建
一个用于存放所有笔记和信息的位置

面试题5：从尾到头打印链表

链表是由指针把若干个结点连接成链状结构，是一种动态的数据结构。在创建链表时，无须知道链表的长度，当插入一个结点时，只需为新节点分配内存，然后调整指针的指向。由于链表是按需分配内存的，故其空间效率比较高。

面试题5：从尾到头打印链表

//题目描述 // //输入一个链表，从尾到头打印链表每个节点的值。 // //输入描述: //输入为链表的表头 // // // //输出描述: //输出为需要打印的"新链表"的表头 #include<iostream> #include<vector> #include<stack> #include<windows.h> using namespace std; struct ListNode {         int val;         struct ListNode *next;       ListNode(int x) :              val(x), next(NULL) {        } }; // 栈的思想 // 0ms 8552k class Solution { public:     vector<int> printListFromTailToHead(struct ListNode* head) {         stack<int>s=stack<int>(); while(head!=NULL){ s.push(head->val); head=head->next; } vector<int>res=vector<int>(s.size()); int k=0; while(!s.empty()){ res[k++]=s.top(); s.pop(); } return res;     } }; // 0ms 8568k class Solution { public:     vector<int> printListFromTailToHead(struct ListNode* head) {         vector<int>res=vector<int>(); stack<int>s=stack<int>(); while(head!=NULL){ s.push(head->val); head=head->next; } while(!s.empty()){ res.push_back(s.top()); s.pop(); } return res;     } }; // 递归思想 // 0ms 8552k class Solution { public:     vector<int> printListFromTailToHead(struct ListNode* head) {         vector<int>res=vector<int>(); if(head!=NULL){ res=printListFromTailToHead(head->next); res.push_back(head->val); } return res;     } };

递归在本质上就是一个栈结构。但当链表很长时，就会导致函数调用的层级很深，从而可能导致函数调用栈溢出，显式用栈基于循环实现的鲁棒性好一些。

已使用 Microsoft OneNote 2010 创建
一个用于存放所有笔记和信息的位置

面试题3：二维数组中的查找

数组概念

数组占据一块连续的内存并按照顺序存储数据。

创建数组时，需要首先指定数组的容量大小，然后根据大小分配内存。因此数组的空间效率不高。

内存连续的特点使得可根据下标在o(1)时间读/写任何元素，故时间效率很高。可用它实现简单的哈希表。

为了解决数组空间效率不高的问题，设计了多种动态数组，例如c++中的vector。为了避免浪费，先为数组开辟较小的空间，然后向数组中添加数组。当数据的数目超过数组的容量时，将重新分配一块更大的空间（stl的vector每次扩充容量，新容量都是前一次的两倍），将之前数据复制到新数组，再将之前的内存释放，从而减少内存的浪费。但每次扩充数组容量都有大量的额外操作，因此使用动态数组时，要尽量减少改变数组容量大小的次数。

c/c++中，数组与指针的关系

――数组名字即为指针

在c/c++中，没有记录数组的大小，因此用指针访问数组中的元素时，要防止数组越界操作。

输出为：20，4，4 （第一个计算数组大小，后两个计算的都是指针的大小，对于32位系统中，任意指针求sizeof得到结果都是4）

在c/c++中，当数组作为函数参数进行传递时，数组自动退化为同类型指针，例如size3。

面试题3：二维数组中的查找

<<solution3.cpp>>

//题目描述 // //在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 // //输入描述: //array： 待查找的二维数组 //target：查找的数字 // // // //输出描述: //查找到返回true，查找不到返回false #include<iostream> #include<vector> using namespace std; class Solution { public:     bool Find(vector<vector<int> > array,int target) { int n=array.size(),m=array[0].size(); int l=0,r=n-1,t=0,d=m-1; return biFind(array,target,l,r,t,d);     } bool biFind(vector<vector<int> > array,int target,int l,int r,int t,int d){ if(l>r)return false; if(t>d)return false; int midx=(l+r)/2; int midy=(t+d)/2; if(array[midx][midy]==target)return true; bool flag=false; if(array[midx][midy]>target){ flag=biFind(array,target,l,midx-1,t,d); if(!flag)flag=biFind(array,target,l,r,t,midy-1); }else{ flag=biFind(array,target,midx+1,r,t,d); if(!flag)flag=biFind(array,target,l,r,midy+1,d); } return flag; } }; int main(){ int a[2][3]={{1,2,3},{4,5,6}}; vector<vector<int> > array(2); for(int i=0;i<2;i++){ array[i].resize(3); for(int j=0;j<3;j++) array[i][j]=a[i][j]; } Solution test=Solution(); cout<<test.Find(array,5); system("pause"); return 0; }

使用以上方法，将出现重复查找的情况。考虑数组特性，每行从左到右递增，每列从上到下递增，搜索起点可以为右上角或左下角。若为右上角，则先列再行，若为左下角，则先行再列。

这种情况，最差为O（m+n）？

class Solution { public:     bool Find(vector<vector<int> > array,int target) { int m=array.size(),n=array[0].size(); int l=0,r=n-1; while(l>=0&&l<m&&r>=0&&r<n){ if(target==array[l][r])return true; if(target>array[l][r])l++; else r--; } return false;     } };

已使用 Microsoft OneNote 2010 创建
一个用于存放所有笔记和信息的位置