每日算法题:Day 10

作者:TeddyZhang,公众号:算法工程师之路

Day 10, Linux知识点走起~

1

编程题

【剑指Offer】顺时针打印数组

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路: 这道题目需要我们学会如何设置变量,让程序更加好写一些,当我们通过设置上、下、左、右四个变量,可以很轻松的完成矩阵最外圈的打印,然后依次从外围向内打印!共需要四个打印过程!需要注意的是,当一个矩阵为列向量或者行向量又或者循环达到一个列向量或者行向量时,需要通过条件语句对后两个打印过程进行剔除,否则会造成重复打印,比如矩阵[1,2,3,4]打印成[1,2,3,4,3,2,1]

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        int rows = matrix.size();
        int cols = matrix[].size();
        vector<int> res;

        // 输入的二维数组非法,返回空的数组
        if (rows ==  || cols == )  return res;

        // 定义四个关键变量,表示左上和右下的打印范围
        int left = , top = , right = cols - , bottom = rows - ;
        while (left <= right && top <= bottom)
        {
            // 从左向右打印
            for (int i = left; i <= right; ++i)  
                res.push_back(matrix[top][i]);
            // 从上到下打印
            for (int i = top + ; i <= bottom; ++i)  
                res.push_back(matrix[i][right]);
            // 从右向左打印
            if (top != bottom)  // 为了避免矩阵是个行向量,重复打印
            for (int i = right - ; i >= left; --i)  
                res.push_back(matrix[bottom][i]);
            // 从下到上打印
            if (left != right)  // 为了避免矩阵是个列向量,重复打印
            for (int i = bottom - ; i > top; --i)  
                res.push_back(matrix[i][left]);
            left++,top++,right--,bottom--;
        }
        return res;
    }
};

【剑指Offer】包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

思路: 由于这个题目要求在O(1)找到最小值,首先我们先来看下数据在栈中如何储存,假设有一些数据这样依次入栈:6,4,3,5,4,此时最小值为3,但随着push和pop操作,其最小值都会更新,我们使用另外一个栈来储存每个阶段的最小值!怎么储存呢?

操作栈:6,4,3,5,4 最小栈:6,4,3,空,空

当压入一个数时,我们判断这个数是否小于等于栈顶,若是,此时最小值更新,我们将这个数压入到最小栈中!因此最小栈的栈顶储存的是每个操作(push或pop)后的栈的最小值

当弹出时,检查是否与最小栈栈顶相同,换句话说是否是操作栈的最小值,若是,则最小栈也需要弹出!

class Solution {
private:
    stack<int> sta;
    stack<int> minSta;   // 辅助栈
public:
    void push(int value) {
        sta.push(value);
        if(minSta.empty()){
            minSta.push(value);
        }else if(value <= minSta.top()){
            minSta.push(value);
        }
    }
    void pop(){
        if(sta.top() == minSta.top()){
            minSta.pop();   // 但sta弹出时,如果和minSta相同,那么minSta也弹出
        }
        sta.pop();
    }
    int top() {
        return sta.top();
    }
    int min() {
        return minSta.top();
    }
};

2

概念题

【Linux】GCC编译流程是什么?请简述一下

GCC是一组编译器的集合,其可以将一个源文件(.c)编译成可执行文件(linux中的.out文件),主要流程如下:

源文件——>预处理——>编译——>汇编——>链接——>可执行文件

预处理:C 编译器对各种预处理命令进行处理,包括头文件包含、宏定义的扩 展、条件编译的选择等,具体编译指令为: gcc -o test.i -E test.c

编译:进行语法检查,并将源文件翻译成汇编文件,命令为: gcc -o test.s -S test.i

汇编:将汇编语言转换成为二进制语言(机器码),命令为: gcc -o test.o -c test.s

链接:将各个模块的.o文件进行符号链接形成一个可执行文件 gcc -o test.o test.out

【Linux】GCC编译时常用的命令选项整理!

  • -V 查看gcc版本,显示gcc执行的详细过程
  • -o 指定输出文件,但不能与源文件名字一致
  • -E 只进行源文件的预处理过程
  • -S 只进行编译的过程,生成汇编文件
  • -c 编译和汇编,生成二进制文件,但不会进行链接
  • -g 在编译输出时加入gdb调试,可以进行代码的调试工作

通常情况下,一个test.c必须经过test.i,test.s,test.o,才能编程可执行文件a.out.

【Linux】chmod命令如何使用?文件的操作权限是什么?

chmod可以更改文件的权限,为不同的用户设定不同的权限!格式如下: chmod [ugoa][+-=][rwxX(八进制表示)] 文件名 其中:

  • 操作对象:u 主用户 g 同组的其他用户 o 其他用户 a 所有用户
  • 权限类别:r 读 w 写 x 可执行 X 所有权限
  • 权限设定:+ 增加权限 - 取消权限 = 唯一指定权限

chmod u+x, g-x, o-x a.txt 或者 chmod 100 a.txt 表示a.txt只有主用户有执行权限,其他用户没有,111为8进制。

3

原文发布于微信公众号 - 算法工程师之路(Zleopard7319538)

原文发表时间:2019-08-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券