算法总结2

多维数组和矩阵

顺时针打印

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

void print(int matrix[][],int len1,int len2){
    int lux = 0; //leftup.x
    int luy = 0; //leftup.y
    int rdx = len1-1; //rightdown.x
    int rdy = len2-1; //rightdown.y
    while(lux<=rdx&&luy<=rdy){
        int x = lux;
        int y = luy;
    	while(y <= rdy){ //打印上边界
        	cout << matrix[x][y++] << " ";
    	}
        y = rdy; //恢复
        x++;
        while(x <= rdx){  //打印右边界
            cout << matrix[x++][y] << " ";
        }
        x = rdx;
        y --;
        while(y >= luy){ //打印下边界
            cout << matrix[x][y--] << " ";
        }
        y = luy;
        x --;
        while(x > lux){ //打印左边界
            cout << matrix[x--][y] << " ";
        }
     	//更新两个顶点
        lux ++;
        luy ++;
        rdx --;
        rdy --;
    }
}

Z型打印

1 2 3 4

5 6 7 8

9 10 11 12

1 2 5 9 6 3 4 7 10 11 8 12

void print(int matrix[][],int len1,int len2){
    int x = 0;
    int y = 0;
    int direct = 0; //右0,下1,左下2,右上3
    while(x<=len1-1 && y<=len2-1){
        cout << matrix[x][y] << " ";
        if(x==len1-1&&y==len2-1)break;
        if(direct == 0){ 
        	// 按当前指向移动一步 
			y ++; 
			// 推算下一步移动方向 
        	direct = (x==0) ? 2 : 3; 
			//向右走后，处于上边界，下一步左下
			//向右走后，处于下边界，下一步右上 
        }
        else if(direct == 1){
        	x ++;
        	direct = (y==0) ? 3 : 2;
        }
        else if(direct == 2){
            x ++;
            y --; 
            //向左下走后，处于左边界没到底端，下一步向下 
            if(y==0&&x!=len1-1)direct = 1; 
            //向左下走后，处于下边界，下一步向右 
            if(x==len1-1)direct = 0;
            //否则继续按照原来的状态移动 
        }
        else {
            x --;
            y ++;
            if(x==0&&y!=len2-1)direct = 0;
            if(y==len2-1)direct = 1;
        }
    }
}

0所在的行列清零

如果矩阵中某个元素为0，则将其所在行和列清零

void solve(int matrix[][],int len1,int len2){
    int *recordRow = new int[len1]();
    int *recordCol = new int[len2]();
    for(int i = 0;i < len1;i ++){
        for(int j = 0;j < len2;j ++){
            if(matrix[i][j]==0){
                recordRow[i] = 1;
                recordCol[j] = 1;
            }
        }
    }
    for(int i = 0;i < len1;i ++){
        for(int j = 0;j < len2;j ++){
        	if(recordRow[i] == 1 || recordCol[j] == 1){
                matrix[i][j] = 0;
            }
        }
    }
}

边界为1的最大子方阵

只有0和1的NXN矩阵matrix，返回边框全是1的最大正方形边长长度

0 1 1 1 1

0 1 0 0 1

0 1 0 0 1

0 1 1 1 1

0 1 0 1 1 返回4

O(n^4)

int n = N;
while(n > 0){
    for(int i = 0;i <= N-n;i ++){
        for(int j = 0;j <= N-n;j ++){
            int flag = 0;
            //检查上边
            for(int x = j;x < j+n;x ++){
                if(matrix[i][x]==0){
                    flag = 1;
                    break;
                }
            }
            if(flag)break;
            //检查下边
            for(int x = j;x < j+n;x ++){
                if(matrix[i+n][x]==0){
                    flag = 1;
                    break;
                }
            }
            if(flag)break;
			//检查左边
            for(int x = i;x < i+n;x ++){
                if(matrix[x][j]==0){
                    flag = 1;
                    break;
                }
            }
            if(flag)break;
            //检查右边
            for(int x = i;x < i+n;x ++){
                if(matrix[x][j+n]==0){
                    flag = 1;
                    break;
                }
            }
            if(flag)break;
            return n;
        }
    }
    n--;
}

优化：打表预处理 O(n^3)

若matrix[i][j]为0，则record[i][j] = (0，0)；

若matrix[i][j]为1，则record[i][j] = (x，y)；

//x为该点下侧连续1的个数(包含本身)，y为该点右侧连续1的个数(包含本身)

int matrix[N][N] = {{0,1,1,1,1},
				    {0,1,0,0,1},
				    {0,1,0,0,1},
				    {0,1,1,1,1},
				    {0,1,1,0,1}};;
int record[N][N][2];

void pre(){
    for(int i = N-1;i >= 0;i --){
        for(int j = N-1;j >= 0;j --){
     		if(matrix[i][j]==0){
                record[i][j][0] = 0;
                record[i][j][1] = 0;
            } else {
                int right = (j+1<N)?record[i][j+1][0]+1:1;
                int down = (i+1<N)?record[i+1][j][1]+1:1;
                record[i][j][0] = right;
                record[i][j][1] = down;
            }      
        }
    }
}

//检查以(i,j)为顶点是否构成n阶正方形
bool check(int i,int j,int n){
    if(record[i][j][0]<n||record[i][j][1]<n)return false;
    if(record[i][j+n-1][1]<n||record[i+n-1][j][0]<n)return false;
    return true;
}

int cal(){
	int n = N;
	while(n > 0){
    	for(int i = 0;i <= N-n;i ++){
        	for(int j = 0;j <= N-n;j ++){
            	if(check(i,j,n))return n;
       		}
		}
		n--;
    }
}

子数组最大累加和

a = [1，-2，3，5，-2，6，-1] ，最大的和为[3，5，-2，6] (一定是连续的一段)

//递推
int find(int a[],int len){
    if(len == 0)return 0;
    int sum = a[0];
    int max = a[0];
    for(int i = 1;i < len;i ++){
        if(sum > 0)sum += a[i];
        else sum = a[i];
        if(sum > max)max = sum;
    }
    return max;
}

子矩阵最大累加和

-1 -1 -1

-1 2 2

-1 -1 -1

返回 4 (最大子矩阵为 2 2)

思路：

i = 0

第i行：-1 -1 -1 //求子数组最大累加和

合并i,i+1行：-2 1 1 //按列求和，再找子数组最大累加和

合并i,i+1,i+2行：-3 0 0

i = 1

... //依次合并到最后一行

int find(int a[],int len){
    if(len == 0)return 0;
    int sum = a[0];
    int max = a[0];
    for(int i = 1;i < len;i ++){
        if(sum > 0)sum += a[i];
        else sum = a[i];
        if(sum > max)max = sum;
    }
    return max;
}

int maxSum(int matrix[][],int len1,int len2){
    int beginRow = 0; //从第一行开始
    int *sum = new int[len2](); //按列求和
    int maxsum = 0;
    while(beginRow < len1){
        for(int i = beginRow;i < len1;i ++){
            //累加
            for(int j = 0;j < len2;j ++){
                sum[j] += matrix[i][j];
            }
            //求子数组最大累加和
            int tmp = find(sum,len2);
            if(maxsum < tmp)maxsum = tmp;
        }
        memset(sum,0,sizeof(sum)*4);
        beginRow ++;
    }
    return maxsum;
}

矩阵乘法

for(int i = 0;i < n;i ++){
    for(int j = 0;j < p;j ++){
        for(int k = 0;k < m;k ++){
            res[i][j] = m1[i][k] * m2[k][j];
        }
    }
}

空间复杂度分析

算法在计算机存储器上所占用的存储空间包括：

1.存储算法本身所占用的存储空间（写出较短的算法）

2.算法的输入输出数据所占用的存储空间（不随算法的不同而改变）

3.算法在运行过程中临时占用的存储空间（参数表中的形参变量，函数体中定义的局部变量）

一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小

注意：变量的内存分配发生在定义时

O(1)

算法执行所需要的临时空间不随着某个变量n的大小而变化

int flag[256]; //定义一个定长的数组空间复杂度不随n变化

functiontotal(n) {
	var sum = 0; //变量的内存分配在循环之外
	for (var i = 1; i <= n; i++) {
		sum += i;
	}
	return sum;
}

O(n)

for(i=0;i<n;i++){
    int temp = i; //变量的内存分配在循环内
    //TODO...
}

//递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间
//调用fun函数,每次创建1个变量k,调用n次
int fun(int n){
    int k = 10;
    if(k == n)return n; 
    else return fun(++n);
}

字符串

串内无重复字符

实现一个算法，确定一个字符串的所有字符是否全都不相同

拓展：假使不允许使用额外的数据结构

思路：应该先问面试官是ASCII字符串还是Unicode字符串

ASCII字符串

if(a.length > 256)return false;
int[] flag = new int[256]();
for(int i = 0;i < a.length;i ++){
    int c = (int)a[i];
    flag[c]++;
    if(flag[c]>1)return false;
}

若只含有a-z,用一个int型的位向量存储：

翻转字符串

1.reverse  
2.开辅助空间
3.翻转[begin,end]
for(int i = 0;i < (end-begin+1)/2;i ++){
   	swap(begin+i,end-i);
}

变形词

变形词：两个串有相同的字符及数量组成

给定两个字符串，确定其中一个字符串的字符重新排列后能否变成另一个字符串

1.若都是ASCII码，开128大小的数组。扫s1加一，扫s2减1，最后扫描一遍还有大于0的就8行
2.比较排序后两串是否相等

替换空格

将字符串中的空格全部替换为“%20”

//1
int count = s.length;
for(int i = 0;i < s.length;i ++)if(s[i] == ' ')count += 2;     
char[] a = new char[count]();
int p1 = 0;
int p2 = 0;
while(p1<s.length){
    if(s[p1] == ' '){
        a[p2++] = '%';
        a[p2++] = '2';
        a[p2++] = '0';
    }
    else a[p2++] = s[p1];
    p1++;
}
a[p2] = '\0';
//2
string a = "";
int p1 = 0;
while(p1 < s.length){
    if(s[p1] == ' ') a+="%20";
    else a+=s[p1];
    p1++;
}

压缩字符串

“aabcccccaaa”压缩为“a2b1c5a3”

if(s.length == 0)return "";  //边界
char last = s[0]; //上一个字符
int count = 1; //记录前一个字符的重复次数
string a = "";
for(int i = 1;i < s.length;i ++){
    if(s[i] == last)count ++;
    else{
        string+=last;
        string+=count+'0';
        count = 1;
    } 
    last = s[i];
}
if(count >= 1){  //最后一个
    string+=last;
    string+=count+'0';
}

两串的字符集相同

//1.ASCII:参考变形词开一个辅助空间，扫描s1+1，扫描s2-1，最后看是否有空串
//2.set，c++中的map和set都是红黑树实现的。java中hashset的底层是hashmap
bool check(string s1,string s2){
	set<char> ss1,ss2;
	for(int i = 0;i < s1.length();i ++)ss1.insert(s1[i]);
	for(int i = 0;i < s2.length();i ++)ss2.insert(s2[i]);
	if(ss1.size()!=ss2.size())return false;
	set<char>::iterator its1 = ss1.begin();
	set<char>::iterator its2 = ss2.begin();
	while(its1!=ss1.end()){ //比较两个集合是否相等，因为已经存在排序关系
		if((*its1)!=(*its2))return false;
		its1 ++;
		its2 ++;
	}
	return true;
}

动态申请二维数组

	int **f = new int*[len];
	// 为指针数组的每个元素分配一个数组
    for(int i = 0;i < len;i ++)f[i] = new int[len];

旋转词