程序员面试之算法备忘录（一）| 数组

2016-05-31 本文已影响761人 rh_Jameson

前言

本文是题主准备面试时记录下的笔记整理而来，稍显粗陋，还请各位撸友勿喷哈！

Topic

目录
- 数组
- 字符串
- 链表
- 二叉树
- 排序
目标
- 熟练使用常用数据结构的基本操作
- 加深对常用算法与技巧的理解
- 面试
参考
- 《程序员面试金典》
- 《剑指offer》
- Leetcode
- 《结构之法 --July》

数组篇

左旋字符串/数组

1.问题描述

给定一字符串
将串的前若干个元素移到串的尾部

2.例子

"abcdefg",2 ==> "cdefgab"

3.Coding感想

关于三步反转法
- 对每段都做了两次反转，因此每段仍然有序
- 段与段之间反转了顺序

4.解决方案

(1) 暴力移位（By一个字符）

A. A[0]存入临时变量tmp

B. 数组其余元素放到数组后面

C. 旋转几位，就执行几次A,B

(2) 三步反转法

A. 要旋转的位置将串分为两段

B. 将这两段分别进行反转

C. 对整个字符串反转

Remove Duplicates

1.问题描述

定一个已排序数组
删除重复元素
返回删除后数组的长度
不能使用额外空间

2.例子

A = [1, 1, 2] ==> len = 2, A = [1, 2]

3.解决方案

两个游标遍历数组
- 两个游标指向的值不等
  - 游标相邻，则两个游标向前移动一位
  - 游标不相邻，快游标值赋给慢游标的下一位后，快游标进一位
- 相等则快游标前进一位
STL-distance()-unique()
- distance(A, unique(A, A + n))
- 注意引入#include<algorithm>
- unique()
  - 作用
    - 删除所有相邻的重复元素
    - 不是真的删除，而是放后面
  - 先排序后才能用unique（）
  - 原型：unique（begin，end）
  - 返回去重后最后一个元素的地址
- distance()
  - 原型distance（begin, end）
  - 返回两参数间的间隔长度

STL-泛型模板-upper_bound()
- upper_bound()
  - 定义
    - 返回的在前闭后开区间查找的关键字的上界
    - 返回一个迭代器，指向键值> key的第一个元素
  - 原型：upper_bound(first, last, value)
- lower_bound()
  - 返回一个迭代器，指向键值>= key的第一个元素

4.Coding遇到的问题

gdb display 可否同时设置多个变量？
使用string的append方法
- 原型：append(const value_type ptr)
  - append( string s )
  - append( "hello" )
  - append(const char* c)
- 与 “strA + strB”的对比
  - append更加灵活
  - append效率相对较低
- 相关链接
  - c++拼接字符串效率比较
char* c =new char(10); c = "hello";
- 如此赋值会有隐患: hello是常量，但c指向的是变量
- 应定义为const char*
- 相关链接
- warning：deprecated conversion from string constant to 'char *'
常量指针 vs 指针常量
参见《effective c++》思维导图笔记
获取数组的长度
- sizeof(array) / sizeof(array[0])
- 无法判断数组是否为空，因为数组一旦定义，里面便有随机值

5.代码示例：

/*************************************************************************
    > File Name:        1_1.rm_duplicates_from_sorted_Array.cpp
    > Description:      
                        （1）给一个已排序数组
                        （2）删除重复元素
                        （3）返回删除后数组的长度
                        （4）不能使用额外空间，必须用常量内存
                        （5）A = [1,1,2]   ==>   len = 2, A = [1, 2]
    > Conclusion:
                        （1）注重代码优化
                        （2）简化判定条件
                        （3）快慢游标遍历数组
    > Author:           rh_Jameson
    > Created Time:     2014年12月02日 星期二 12时03分26秒
 ************************************************************************/

#include<iostream>
#include<algorithm>
using namespace std;



//-------------------------------------原始版本：Acceped--------------------------------//

int removeDuplicatesOrigin(int A[],int n)
{
    int p = 0,q = 1;        //游标p，q

    if(n <= 0)              //判空 & 非法
    {
        return 0;
    }
    if(n == 1)              //数组只有一个元素的情况
    {
        return 1;
    }
    while(q != n)          
    {
        if(A[p] != A[q] && p == q - 1)           //A[p]和A[q]不等且p，q相邻时，p，q向前移动一位
        {
            p++;
            q++;
        }
        else if(A[p] != A[q] && p != q - 1)      //A[p]和A[q]不等且p,q不相邻时
        {
            p++;                                 //p向前移动一位
            A[p] = A[q];                         //将数组A下标q的值赋给下标p的值
            q++;                                 //q向前移动一位
        }            
        else if(A[p] == A[q])                      //A[p]和A[q]相等时，q向前移动一位
        {
            q++;
        }
    }
    return p + 1;                                //返回处理后数组的长度
}

//-------------------------------------优化版本：Acceped--------------------------------//
int removeDuplicatesOptimize(int A[],int n)
{
    int p = 0,q = 1;        //游标p，q

    if(n <= 0)              //判空 & 非法
    {
        return 0;
    }
    while(q != n)          
    {
        if(A[p] != A[q])           //A[p]和A[q]不等时，p，q向前移动一位
        {
            A[++p] = A[q];         //巧妙优化，p，q相邻，A[q] = A[q],p,q不相邻，A[p] = A[q] 
            q++;
        }
        else if(A[p] == A[q])      //A[p]和A[q]相等时，q向前移动一位
        {
            q++;
        }
    }
    return p + 1;                  //返回处理后数组的长度
}

//-------------------------------------优化版本2：Acceped--------------------------------//
int removeDuplicatesOptimize(int A[],int n)
{
    int p = 0,q = 1;        //游标p，q

    if(n <= 0)              //判空 & 非法
    {
        return 0;
    }
    while(q != n)          
    {
        if(A[p] != A[q])           //A[p]和A[q]不等时，p，q向前移动一位
        {     
            A[++p] = A[q];         //巧妙优化，p，q相邻，A[q] = A[q],p,q不相邻，A[p] = A[q] 
        }
        q++;
    }
    return p + 1;                  //返回处理后数组的长度
}




//==================================参考代码1：Accepted==================================//

/*
 * 该参考代码与上面优化版本的代码思路一直，不再赘释
 */
int removeDuplicatesLeetcode1(int A[],int n)
{
    if(n <= 0)
    {
        return 0;
    }
    int index = 0;
    for(int i = 1; i < n; ++i)
    {
        if( A[index] != A[i] )
        {
            A[++index] = A[i];
        }
    }
    return index + 1;

}


//==================================参考代码2：Accepted==================================//

/*
 * 使用STL distance(),unique()方法
 */
int removeDuplicatesLeetcode2(int A[],int n)
{
    return distance(A, unique(A, A + n) );
}



int main()
{
    //removeDuplicates
    int A[3] = {1,1,2};
    cout << removeDuplicatesLeetcode2(A, 3) << endl; 
}

Remove Duplicates II

1.问题描述

给一个已排序数组
删除重复次数大于2的元素
返回删除后数组的长度
不能使用额外空间

2.例子
A = [1,1,1,2,2,3] ==> A.len = 5, A = [1,1,2,2,3]

3.Coding感想

条件语句优化技能有待提高

4.解决方案

思路与上一道差不多，区别是引入计数变量
在第一次出现重复时，做相应处理
多次重复，只移动快游标
A[p] != A[q]时，注意将count重置为1

5.代码实例：

/*************************************************************************
    > File Name:        1_2.remove_duplicatesII.cpp
    > Description:      
                        （1）给一个已排序数组
                        （2）删除重复次数大于2的元素
                        （3）返回删除后数组的长度
                        （4）不能使用额外空间
                        （5）A = [1,1,1,2,2,3] ==> A.len = 5,A = [1,1,2,2,3]

    > Conclusion:
                        （1）条件语句优化技能有待提高
                        （2）策略：
                            A.思路与上一道差不多，区别是引入计数变量
                            B.在第一次出现重复时，做相应处理
                            C.多次重复，只移动快游标
                            D.A[p] != A[q]时，注意将count重置为1
    > Author:           rh_Jameson
    > Created Time:     2014年12月03日 星期三 13时23分00秒
 ************************************************************************/

#include<iostream>
using namespace std;

//============================原始版本：Accepted,88 ms==================================//
int removeDuplicates(int A[],int n)
{
    int count = 1;                  //计数变量
    int index = 0;                  //慢游标
    
    if(n <= 0)                      //判空，非法
    {
        return 0;
    }

    for(int i = 1; i < n; ++i) 
    {
        /*慢游标指向值不等于快游标指向值时*/
        if(A[index] != A[i])       
        {
            A[++index] = A[i];          //慢游标前进一位，将快游标指向值赋给慢游标指向值
            if(count != 1)              //重置count
            {
                count = 1;
            }
        }

        /*慢游标指向值等于快游标指向值时*/
        else if(count == 1)             //第一次出现重复的处理
        {
            count++;
            A[++index] = A[i];
            
        }
        else                            //多次重复的处理
        {
            count++;
        }
    }
    return index + 1;
}

//============================优化条件语句版本：Accepted,116 ms==================================//
int removeDuplicatesOpt(int A[],int n)
{
    int count = 1;                  //计数变量
    int index = 0;                  //慢游标
    
    if(n <= 0)                      //判空，非法
    {
        return 0;
    }

    for(int i = 1; i < n; ++i) 
    {
        if(A[index] == A[i])
        {
            count++;
            if(count == 2)
            {
                A[++index] = A[i];
            }
        }
        else
        {
            A[++index] = A[i];
            count = 1;
        }
    }
    return index + 1;
}

//============================参考版本：Accepted,68ms===============================//
    int removeDuplicates(int A[], int n) {
        if(n <= 2)                      //小于2直接返回n
        {
            return n;
        }
        //直接从下标2开始遍历
        int index = 2;
        for(int i = 2; i < n; ++i)
        {
            if(A[index - 2] != A[i])
            {
                A[index++] = A[i];
            }
        }
        return index;
    }



int main()
{
    int A[4] ={1,1,1,1};
//    int A[6] = {1,1,1,2,2,3};
    cout << removeDuplicatesOpt(A, 4);
    return 0;
}

Search In Rotated Sorted Array

1.问题描述

给定一旋转数组（数组分两段，各段均已排序）
段边界点不确定
给一关键字，查询数组中是否有该关键字
有则返回下标，无则返回-1
假设数组中无重复元素
A = [4,5,6,7,0,1,2]

2.例子
A = [4,5,6,7,0,1,2], 搜索关键字：0 ==> return 4

3.解决方案

两次折半策略
- 折半获取边界最大值
- 判断关键字在哪一段顺序序列上
- 在目标顺序序列上折半查找关键字
一次折半策略
- 折半mid,比较A[mid]和target
- mid将数组分两段，判断target是在哪一段
- target没找到或first与last未交错，循环A,B

4.Coding遇到的问题与感想

折半查找算法实现需注意的细节及优化
- 两种情况[0,n),[0,n]
  - right=n-1 => while(left <= right) => right=middle-1
  - right=n => while(left < right) => right=middle;
- 注意（min + max）/ 2溢出问题
- 折半改变min或max时，防止出现死循环
我想的策略复杂度为logn，但要两次折半来实现，非最优解法

5.代码示例：

/*************************************************************************
    > File Name:        1_3.search_in_rotated_sorted_array.cpp
    > Description:      
                        （1）给定一旋转数组（数组分两段，各段均已排序）
                        （2）段边界点不确定
                        （3）给一关键字，查询数组中是否有该关键字
                        （4）有则返回下标，无则返回-1
                        （5）假设数组中无重复元素
                        （6）A = [4,5,6,7,0,1,2]
    > Conclusion:      
                        （1）策略：     
                            A.折半获取边界最大值
                            B.判断关键字在哪一段顺序序列上
                            C.在目标顺序序列上折半查找关键字

                        （2）折半查找算法实现需注意的细节及优化
                            A.两种情况[0,n),[0,n]
                            B.注意（min + max）/ 2溢出问题
                            C.折半改变min或max时，防止出现死循环

                        （3）该策略复杂度为logn，但要两次折半来
                             实现，非最优解法
                        
                        （4）一次折半优化策略：
                            A.折半mid,比较A[mid]和target
                            B.mid将数组分两段，判断target是在哪一段
                            C.target没找到或first与last未交错，循环A,B
    > Author:           rh_Jameson
    > Created Time:     2014年12月03日 星期三 16时16分33秒
 ************************************************************************/

#include<iostream>
using namespace std;


//====================两次折半版本：Accepted，16 ms=========================//

//折半查找关键字
int binary_search(int A[], int &max, int &min, int target)
{
    int mid;
    while(min <= max)
    {
        //mid = (min + max) / 2;                //常规折半
        mid = min + (max - min) / 2;            //防止（min + max）溢出
        if(target > A[mid])
        {
            min = mid + 1;
        }
        else if(target < A[mid])
        {
            max = mid - 1;
        }
        else
        {
            return mid;
        }        
    }
    return -1;
}

//折半获取边界最大值leftMax
int binary_getMax(int A[], int &front, int &rear)
{
    int mid;

    while(front <= rear)
    {
        //mid = (front + rear) / 2;
        mid = front + (rear - front) / 2;               //防止溢出        
        //找到最大值，直接跳出循环
        if( A[mid] > A[mid - 1] && A[mid] > A[mid + 1] ||
            front == rear - 1 && A[mid] > A[mid + 1] ||
            front == mid && rear == mid )
        {
            break;
        }
        //mid非最大值，进行折半
        if(A[mid] >= A[front])
        {
            front = mid + 1;
        }
        else
        {
            rear = mid - 1;
        }
    }
    return mid;
}

int search(int A[],int n,int target)
{
    if(n <= 0)                                          //处理非法
    {
        return -1;
    }
    
    int front = 0;
    int rear = n - 1;
    
    //初始化边界值
    int leftMin = 0, leftMax, rightMin, rightMax = n-1;
    
    leftMax = binary_getMax(A, front, rear);               //折半获取边界最大值
    rightMin = leftMax + 1;
    
    //判断目标值在哪一段顺序序列上
    if(target > A[leftMin])                //折半查找需封装
    {
        return binary_search(A, leftMax,leftMin,target);    //折半查找左侧顺序序列
    }    
    else if(target == A[leftMin])
    {
        return leftMin;
    }
    else
    {
       return binary_search(A, rightMax, rightMin, target); //折半查找右侧顺序序列
    }
}



//==========================一次折半版本：Accepted,40ms===============================//
//折半mid,比较target，A[mid]
int searchOnce(int A[], int n, int target)
{
    int first = 0, mid, last = n - 1;
    while(first <= last)                                //first，last未交错，继续循环
    {
        mid = first + (last - first) / 2;
        if(target == A[mid])
        {
            return mid;
        }
        if(target == A[first])
        {
            return first;
        }
        else if(A[mid] >= A[first])
        {
            if(target > A[first] && target < A[mid])
            {
                last = mid - 1;    
            }
            else
            { 
                first = mid + 1;
            }                   
        }
        else
        {
            if(target < A[first] && target > A[mid])
            {
                first = mid + 1;
            }
            else
            {
                last = mid - 1;
            }
        }
    }
    return -1;
}

int main()
{
    //int A[7] = {4,5,6,7,0,1,2};
    int A[2] = {3,1};

    cout << searchOnce(A, 2, 1) << endl;
    return 0;
}

1_6.matrix_rotate

1.问题描述

N * N矩阵表示图像
每像素4字节
实现图像旋转90度
不用额外空间

2.策略一：四点轮换法

遍历行数N/2
将行中每个结点旋转到相应位置
通过tmp变量进行轮换
时间复杂度O（N^2）

3.策略二：对角线替换

交换对角线两边元素
对每一列元素进行逆置
- 逆时针旋转绕横轴
- 顺时针旋转绕纵轴

4.生成随机数

srand((int)time(NULL));
r = rand() % 10

5.传递二维数组参数

int a[10][10]
int a[][10]
不可以用二级指针
- int** a;
- 相关网址：http://www.wutianqi.com/?p=1822

6.代码示例：

/*************************************************************************
    > File Name:        Solution.h
    > Description:      
                        （1）问题描述
                            A.N * N矩阵表示图像
                            B.每像素4字节
                            C.实现图像旋转90度
                            D.不用额外空间
    > Conclusion:          
                        （1）策略一：四点轮换法
                            A.遍历行数N/2
                            B.将行中每个结点旋转到相应位置
                            C.通过tmp变量进行轮换
                            D.时间复杂度O（N^2）
                        
                        （2）策略二：对角线替换
                            A.交换对角线两边元素
                            B.对每一列元素进行逆置
                                a.逆时针旋转绕横轴
                                b.顺时针旋转绕纵轴
                            
                        （3）生成随机数
                            A.srand((int)time(NULL));
                            B.r = rand() % 10
                        
                        （4）传递二维数组参数
                            A.int a[10][10]
                            B.int a[][10]
                            C.不可以用二级指针
                                a.int** a;
                                b.相关网址：
                                    http://www.wutianqi.com/?p=1822
    
    > Author:           rh_Jameson
    > Created Time:     2014年12月14日 星期日 12时17分44秒
 ************************************************************************/

#ifndef _SOLUTION_H
#define _SOLUTION_H

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

class Solution {
public:
    void printMatrix(const int n,int a[][7]){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                cout << a[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
    }

//=======================矩阵旋转：四点轮换法,Accepted=======================//
    //逆时针旋转90度
    void matrix_rotate_reverse(const int n, int a[][7]){
        if(n == 0){
            cout << "空矩阵" << endl;
        }
        int col = n, len = n;
        int midline = n / 2, tmp;
        
        for(int i = 0; i < midline; ++i){
            for(int j = i; j < col - 1 - i; ++j){
                tmp = a[j][i];
                a[j][i] = a[i][len - 1 - j];
                a[i][len -1 -j] = a[len - 1 - j][len - 1 - i];
                a[len - 1 - j][len - 1 - i] = a[len - 1 - i][j];
                a[len - 1 - i][j] = tmp;
            }
        }
        printMatrix(n, a);
    }

    //顺时针旋转90度
    void matrix_rotateByExchg(const int n, int a[][7]){
        if(n == 0){
            cout << "空矩阵" << endl;
        }
        int col = n, len = n;
        int midline = n / 2, tmp;
        
        for(int i = 0; i < midline; ++i){
            for(int j = i; j < col - 1 - i; ++j){
                tmp = a[i][j];
                a[i][j] = a[len - 1 - j][i];
                a[len - 1- j][i] = a[len - 1 - i][len - 1 - j];
                a[len - 1 - i][len - 1 - j] = a[j][len - 1 - i];
                a[j][len - 1 - i] = tmp;
            }
        }
        printMatrix(n, a);
    }

//=====================矩阵旋转：对角线替换,Accepted======================//
    void swap(int &a, int &b){
        int tmp;
        tmp = a;
        a = b;
        b = tmp;
    }
    
    
    void matrix_rotate(const int n, int a[][7]){
        int len = n;
        //对角线两侧元素互换
        for(int i = 0; i < len; ++i){
            for(int j = i; j < len; ++j){
                swap(a[i][j],a[j][i]);
            }
        }
        //根据纵轴逆置元素
        for(int line = 0; line < len; ++line){
            for(int first = 0,last = len - 1; first < last; ++first, --last){
                swap(a[line][first],a[line][last]);
            }
        }
        printMatrix(n, a);
    }

};

#endif

1_7.matrix_clear_zero

1.问题描述：

M * N矩阵
若某个元素为0，所在行与列均清零

2.解决策略

策略一：哈希表保存清零的行与列
- 遍历矩阵
- 用map记录元素为0的行, 列
- 对相应行清零
- 相应列清零
策略二：复用0行0列记录要清零的行，列
- 不用额外空间，直接复用0行0列的空间
- 判断0行跟0列是否存在0，bool标志真/假
- 遍历其余行跟列
- 元素为0的行列，存到0行0列的相应位置
- 遍历清零
- 检测bool标志，判断0行0列是否存在0
- 存在，则对0行 / 0列清零

3.Coding遇到的问题

vector<vector<int> > m：
- 相当于二维数组 m[i][j]
- 行数：m.size()
- 列数：m[0].size()
- m[i][j]形式，通过2个for循环可生成随机矩阵
- vector形式不能生成
- 相关链接
map & hashtable：
- C++ STL严格来说没有实现哈希表结构
- map底层是红黑树，访问复杂度为logN
- 哈希表一般是常数时间访问
- 性能：unordered_map > hash_map > map
- 需要有序关联容器的话要用map
- 相关链接
  - STL---hash_map
  - c++ hash_map 详细介绍
  - map / hash_map / unordered_map 性能测试
  - C++ STL中哈希表 hash_map介绍

4.代码示例：

/*************************************************************************
    > File Name:        Solution.h
    > Description:      
                        （1）问题描述：
                            A.M * N矩阵
                            B.若某个元素为0，所在行与列均清零
    > Conclusion:
                        （1）策略一：哈希表保存清零的行与列
                            A.遍历矩阵
                            B.用map记录元素为0的行, 列
                            C.对相应行清零
                            D.相应列清零

                        （2）策略二：复用0行0列记录要清零的行，列
                            A.不用额外空间，直接复用0行0列的空间
                            B.判断0行跟0列是否存在0，bool标志真/假
                            C.遍历其余行跟列
                            D.元素为0的行列，存到0行0列的相应位置
                            E.遍历清零
                            F.检测bool标志，判断0行0列是否存在0
                            G.存在，则对0行 / 0列清零

                        （3）vector<vector<int> > m：
                            A.相当于二维数组 m[i][j]
                            B.行数：m.size()
                            C.列数：m[0].size()
                            D.m[i][j]形式，通过2个for循环可生成随机矩阵
                            E.vector形式不能生成
                            F.http://blog.csdn.net/qingdujun/article/details/17499871

                        （4）map & hashtable：
                            A.C++ STL严格来说没有实现哈希表结构
                            B.map底层是红黑树，访问复杂度为logN
                            C.哈希表一般是常数时间访问
                            D.性能：unordered_map > hash_map > map
                            E.需要有序关联容器的话要用map
                            F.http://blog.chinaunix.net/uid-20384806-id-3055333.html
                            G.http://yiluohuanghun.blog.51cto.com/3407300/1086355
                            H.http://blog.csdn.net/peter_teng/article/details/8433395
                            I.http://www.cnblogs.com/waytofall/archive/2012/06/04/2534386.html
    > Author:           rh_Jameson
    > Created Time:     2014年12月14日 星期日 22时24分29秒
 ************************************************************************/

#ifndef _SOLUTION_H
#define _SOLUTION_H

#include<iostream>
#include<string>
#include<algorithm>
#include<map>
//#include<hash_map>
using namespace std;

class Solution {
public:

    void printMatrix(int matrix[1][2]){
        int col_num = 2;
        int line_num = 1;
        for(int i = 0; i < line_num; ++i){
            for(int j = 0; j < col_num; ++j){
                cout << matrix[i][j] << " "; 
            }
            cout << endl;
        }
        cout << endl;
    }
//=====================map保存要清0的行与列：Accepted=====================//‘
    
    void setZeroesByHash(int matrix[5][4]) {
        int col_num = 4;
        int line_num = 5;
        map<int, int> col_map, line_map;            //记录清零的行与列
        int col_zero = 0, line_zero = 0;            //清零行，列的个数
        //遍历记录清零的行与列
        for(int i = 0; i < line_num; ++i){
            for(int j = 0; j < col_num; ++j){
                if(matrix[i][j] == 0){
                    line_map[++line_zero] = i;
                    col_map[++col_zero] = j;
                }
            }
        }
        int tmp;
        //所在行清零
        while(line_zero > 0){
            tmp = line_map[line_zero];
            for(int i = 0; i < col_num; ++i){
                matrix[tmp][i] = 0;
            }
            --line_zero;
        }
        printMatrix(matrix);
        //所在列清零
        while(col_zero > 0){
            tmp = col_map[col_zero];
            for(int i = 0; i < line_num; ++i){
                matrix[i][tmp] = 0;
            }
            --col_zero;
        }
        printMatrix(matrix); 
        
    }


//=====================不用额外空间实现：Accepted=====================//
    
    void setZeroes(int matrix[1][2]) {
        int col_num = 2;
        int line_num = 1;
        bool flag_line = false,flag_col = false;
        //判断第零行是否有0
        for(int i = 0; i < col_num; ++i){
            if(matrix[0][i] == 0){
                flag_line = true;
                break;
            }
        }
        //判断第零列是否有0
        for(int i = 0; i < line_num; ++i){
            if(matrix[i][0] == 0){
                flag_col = true;
                break;
            }
        }
        //将出现0的行，列记录到第0行和第零列上
        for(int i = 1; i < line_num; ++i){
            for(int j = 1; j < col_num; ++j){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        //清零
        for(int i = 1; i < line_num; ++i){
            for(int j = 1; j < col_num; ++j){
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
        }
        //判断第零行,第零列是否要清零
        if(flag_line){
            for(int i = 0; i < col_num; ++i){
                matrix[0][i] = 0;
            }
        }
        if(flag_col){
            for(int i = 0; i < line_num; ++i){
                matrix[i][0] = 0;
            }
        }
        printMatrix(matrix);    
    }
};

#endif

程序员面试之算法备忘录（一）| 数组

前言

Topic

数组篇

猜你喜欢

热点阅读

程序员面试之算法备忘录 （一）| 数组

前言

Topic

数组篇

猜你喜欢

热点阅读

程序员面试之算法备忘录（一）| 数组