本文共 7102 字，大约阅读时间需要 23 分钟。

1.16 算法：二维数组中的查找

力扣：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

方法一：遍历数组

bool findNumberIn2DArray(int** matrix, int matrixSize, int* matrixColSize, int target){
       int i, j;    if (matrixSize == 0) return false;    for (i = 0; i < matrixSize; i++) {
    //行        for (j = 0; j < *matrixColSize; j++) {
               if(matrix[i][j] == target) return true;        }    }    return false;}

直接遍历数组所有元素，找出target。

时间复杂度为O(nxm)

空间复杂度为O(1)

方法二：线性查找

先从右上角查找，因为整体的趋势是从左到右，从上到下递增的。所以我们从排除比target大的元素开始，从右上角开始向左排除，直到遇到比target小的元素，然后从那一列开始排除，直到遇到比target大的元素，然后再往左直到遇到比target大的元素，然后再往下……

就是遇到大的往小的方向走，遇到小的往大的方向走，最后要么找到target，要么超出范围！！！对于这种排好序的结构应该都是可以用的。

结束的条件就是：

• 找到target，直接return true;
• 超出下标，代表没有找到，直接return false;

class Solution {
   public:    bool findNumberIn2DArray(vector
   
    
     >& matrix, int target) {
           int i, j;        if (matrix.empty()) {
               return false;        }        //两层条件控制下标范围 从右上角开始，所以要限制左边和下边的范围        //i行j列（i，j）        for (i = 0, j = matrix[0].size()-1; i < matrix.size() && j >= 0;) {
                  if (matrix[i][j] == target) return true;            else if (matrix[i][j] > target) j--;            else i++;        }        return false;    }};
    
   

1.17 算法：替换空格

力扣：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/solution/mian-shi-ti-05-ti-huan-kong-ge-ji-jian-qing-xi-tu-/

方法一：C++string类处理函数

基于一个新的string，进行重构string。

class Solution {
   public:    string replaceSpace(string s) {
           string ret;        for (auto &p : s) {
               if (p == ' ') {
                   ret.append("%20");            } else {
                   ret.push_back(p);            }        }        return ret;    }};

用到了C++ string类的几个方法，即追加字符串的几个函数：

• append()
• push_back()：一次只能操作一个字符

append

使用示例：

#include 
   
    #include 
    
      int main() {
       std::basic_string
     
       str = "string";    const char* cptr = "C-string";    const char carr[] = "Two and one";     std::string output;     // 1) 后附 char 3 次。    // 注意，这是仅有的接受 char 的重载。    output.append(3, '*');    std::cout << "1) " << output << "\n";     //  2) 后附整个 string    output.append(str);    std::cout << "2) " << output << "\n";     // 3) 后附字符串的一部分（此情况为最后 3 个字母）case)    output.append(str, 3, 3);    std::cout << "3) " << output << "\n";     // 4) 后附 C 字符串的一部分    // 注意，因为 `append` 返回 *this ，我们能一同链式调用    output.append(1, ' ').append(carr, 4);    std::cout << "4) " << output << "\n";     // 5) 后附整个 C 字符串    output.append(cptr);    std::cout << "5) " << output << "\n";     // 6) 后附范围    output.append(std::begin(carr) + 3, std::end(carr));    std::cout << "6) " << output << "\n";     // 7) 后附 initializer_list    output.append({
    ' ', 'l', 'i', 's', 't' });    std::cout << "7) " << output << "\n";}输出如下：1) ***2) ***string3) ***stringing4) ***stringing Two 5) ***stringing Two C-string6) ***stringing Two C-string and one7) ***stringing Two C-string and one list
     
    
   

push_back

C++ 的字符串库

其中std::basic_string模板的常用操作如下：

可见这里用到的两个操作都是在这里面的。

方法二：遍历+字符数组

由于空格要替换为%20，那么，可以声明一个字符数组，大小是字符串的3倍。依次遍历字符串，逐渐将字符填入字符数组之中，当遇到空格时，变为添加%、2、0三个字符。最后，生成新的字符串，截取字符数组中有效的部分即可，即字符数组从0开始，长度为有效存储进字符数组的长度。

1.18 算法：从尾到头打印链表

力扣：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

方法一：遍历求长度后逐一打印

很简单，先遍历链表求出链表长度，然后再遍历一次利用数组随机存取的特性将val插入数组输出，要注意的是参数的传递，从局部变量传递一个数组出去：

• static声明为静态变量
• 使用全局变量传递
• malloc分配空间，传递后记得释放空间

然后是要注意空链表的判断，输出的大小为0.

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */int* reversePrint(struct ListNode* head, int* returnSize){
       int i, length;    struct ListNode *p = (struct ListNode*) malloc(sizeof(struct ListNode));    if (head == NULL) return NULL;    p = head;    for (i = 0; p != NULL; ++i) {
           p = p->next;    }    length = i;    int *ret = (int*)malloc(sizeof(int) * length);    p = head;    for (i = 0; i < length; ++i) {
           ret[length - i - 1] = p->val;        p = p->next;    }     free(p);    *returnSize = length;    return ret;}

方法二：递归

递归到最后，返回的时候每次将元素放在最后一个位置：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:    vector
   
     ret;    vector
    
      reversePrint(ListNode* head) {
           if (head == NULL) return ret;   //停止条件        ret = reversePrint(head->next);  //陷入递归        ret.push_back(head->val);        //返回时的操作，加入到最后面                return ret;    }};
    
   

方法三：入栈+出栈

先遍历链表，同时入栈，由于栈具有先进后出的特性，所以出栈的时候就相当于反向输出，然后在出栈的同时push_back加入数组。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:    vector
   
     ret;    vector
    
      reversePrint(ListNode* head) {
           stack
     
       s;        //先入栈        while (head) {
               s.push(head->val);            head = head->next;        }		//出栈到数组中        while (!s.empty()) {
               ret.push_back(s.top());            s.pop();        }        return ret;    }};
     
    
   

大佬代码

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:    vector
   
     res;    vector
    
      reversePrint(ListNode* head) {
           //方法1：reverse反转法        /*        while(head){            res.push_back(head->val);            head = head->next;        }        //使用algorithm算法中的reverse反转res        reverse(res.begin(),res.end());        return res;        */        //方法2：入栈法        /*        stack
     
       s;        //入栈        while(head){            s.push(head->val);            head = head->next;        }        //出栈        while(!s.empty()){            res.push_back(s.top());            s.pop();        }        return res;        */        //方法3：递归        /*        if(head == nullptr)            return res;        reversePrint(head->next);        res.push_back(head->val);        return res;        */        //方法4：改变链表结构        ListNode *pre = nullptr;        ListNode *next = head;        ListNode *cur = head;        while(cur){
               next = cur->next;//保存当前结点的下一个节点            cur->next = pre;//当前结点指向前一个节点，反向改变指针            pre = cur;//更新前一个节点            cur = next;//更新当前结点        }        while(pre){
   //上一个while循环结束后，pre指向新的链表头            res.push_back(pre->val);            pre = pre->next;        }        return res;    }};作者：wangxiaole链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/solution/csan-chong-jie-fa-reversefan-zhuan-fa-dui-zhan-fa-/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     
    
   

1.19 对一维数组的引用

如下定义是否正确？

int & a[10];

答案：不正确

这里要明白定义一个数组的三要素：

• 数据类型，不能是引用！！！
• 数组名
• 元素数，必须是大于1的常量表达式

数组中的类型不能是引用，因为引用时不能赋值的，而数组元素可以被赋值.

再比如要定义一个数组的引用：

int a[3] = {
   1,2,3};int (&p)[3] = a;   //定义的时候要指明长度

1.20 一维数组的初始化问题

问如下数组初始化之后元素的值：

int x[4] = {
   0};int y[4] = {
   1};

答案：x[4] = {0,0,0,0} y[4] = {1,0,0,0}

在数组元素初始化的时候，如果没有显式提供元素初值，初始化规则和普通变量相同，即：

• 函数体内定义时，元素初始化为0
• 函数体外定义时，元素本来是无初始化的，如果初始化一部分元素，其他元素被初始化为0