刷题日记 | 《剑指 Offer（第 2 版）》刷题总结

©一颗斯特拉
【注】
题目来自《剑指 Offer（第 2 版）》

---

面试题03. 数组中重复的数字（4月13号）

01 知识点

「bool变量」

这个类型占1个字节，而且无论给这个类型的变量赋任何非0整数值，其值都是1，这也说明了它不是其他整数类型的别名。
1.memset函数
函数原型：

void *memset(void *s, int v, size_t n）
s可以是数组名，也可以是指向某一内在空间的指针；
v为要填充的值；
n为要填充的字节数；

2.bool函数的用法

「return 0/return 1/return -1的区别」

---

面试题29. 顺时针打印矩阵（4月8号）

01 知识点

「二维vector」

1.初始化
一维和二维动态数组初始化为：

std::vector <int> vec(10,90); //将10个一维动态数组初始为90
std::vector<std::vector<int> > vec(row,vector<int>(col,0)); //初始化row * col二维动态数组，初始化值为0,其实就是每一行初始化为列数个0

2.获取长度
获取一维数组长度：

int size = vec.size();

获取二维数组长度：

int size_row = vec.size(); //获取行数
int size_col = vec[0].size(); //获取列数

02 反思总结

1.LeetCode测试
LeetCode的测试集是非常广的，例如此题中有输入矩阵为空的情况。这就要求在算法中考虑矩阵为空输出空数组的情况，C++中返回空数组为return {}。

03 源代码

#include<iostream>
#include<vector>
//要使用vector,需要添加头文件

using namespace std;

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> re;//建立一个空的一维向量
        //易漏:输入空矩阵的例外情况
        if(matrix.empty()){
            return {};//如果是空返回空数组
        }
        int min_row,min_col,max_row,max_col;//分别为左上角和右下角的元素
        int size_row = matrix.size();  //获取行数
        int size_col = matrix[0].size();  //获取列数
        int i,j;//循环变量
        for(min_row=0,min_row=0,max_row=size_row-1,max_col=size_col-1;(min_row<=max_row) && (min_col<=max_col);min_row++,min_col++,max_row--,max_col--){//嵌套收缩。需考虑不是方阵的情况
            //从左到右打印
            for (i = min_row,j=min_col;j<= max_col;j++){
                re.push_back(matrix[i][j]);
            }
            //从上到下打印
            for (i = min_row + 1,j =max_col;i<= max_row;i++){
                re.push_back(matrix[i][j]);
            }
            //从右到左打印
            for (i = max_row,j=max_col-1; (j>=min_col)&&(min_row!=max_row); j--){//易错：这里添加min_row!=max_row是防止只有一行会左右重复打印的情况
                re.push_back(matrix[i][j]);
            }
            //从下到上打印
            for (i=max_row-1,j =min_col; (i>=min_row+1)&&(min_col!=max_col); i--){//易错：这里添加min_col!=max_col是防止只有一列会出现上下重复打印的情况
                re.push_back(matrix[i][j]);
            }
        }
        return re;
    }
};

int main() {
    Solution s;
    vector<vector<int> > matrix(3, vector<int>(3));
    int b[3][3] = {{1, 2, 3},
                   {4, 5, 6},
                   {7, 8, 9}};
    //用二维数组给二维向量赋值
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            matrix[i][j] = b[i][j];
        }
    }

    vector<int> res(s.spiralOrder(matrix));//此时调用的是 vector<int>::vector(const vector<int> &r)这个拷贝构造函数
    for(int i=0;i<9;i++)
    {
        printf("%d ", res[i]);
    }
}

【运行结果】

1 2 3 6 9 8 7 4 5

---

面试题57. 和为s的两个数字（4月14号）

01 知识点

「C语言跳出多重循环的方法」

「双指针」

---

面试题58 - II. 左旋转字符串（4月9号）

01 知识点

「string的常见用法」

1.substr函数

s.substr(pos1,n)//返回字符串位置为pos1后面的n个字符组成的串
s.substr(pos)//得到一个pos到结尾的串

2.字符串的拼接
C++中string类，字符串的拼接可直接用+号。

02 反思总结

1.超出时间限制

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        //先把最前面一位取出，再将字符串整体往前移动一位
        char head;
        for(int i=0;i<n;i++){
            head=s[0];
            for(int j=1;j<s.size();j++){
                s[j-1]=s[j];
            }
            s[s.size()-1]=head;
        }
        return s;
    }

【运行结果】

28 / 34 个通过测试用例
状态：超出时间限制

为什么会超出时间限制？是因为这个算法在k很大时需要移动的次数太多了。这里用string的库函数解决更好。

---