idea's blog

蛇形遍历数组, 我的思路是使用两个点坐标再加上一个方向变量, 两个点同时在边缘上移动, 然后连线.

但是, 其实这个问题本质就是从一点出发, 不断地 walk, 一次只 walk 一步, 需要保留方向状态. 如果一次 walk 完斜线, 则不用方向状态, 因为可以根据 walk 的起点来判断.

void print_spiral(int m , int n){
	vector<vector<int>> matrix(m);
	for(int i=0; i<m; i++){
		matrix[i] = vector<int>(n);
	}
	
	int num = 1;
	matrix[0][0] = num++;
	int i=0;
	int j=0;
	while(1){
		if(i == m-1 && j == n-1){
			break;
		}
	
		if(i == 0 || j == n-1){
			j++;
			if(j >= n){
				j --;
				i ++;
			}
			while(1){
				matrix[i][j] = num++;
				if(j == 0 || i == m-1){
					break;
				}
				i++;
				j--;
			}
		}else{
			i++;
			if(i >= m){
				i --;
				j ++;
			}
			while(1){
				matrix[i][j] = num++;
				if(i == 0 || j == n-1){
					break;
				}
				i--;
				j++;
			}
		}
	

	}
	
	for(auto r : matrix){
		for(auto c : r){
			printf("%d ", c);
		}
		printf("\n");
	}
}

采用两点移动再连线的方案:

void print_spiral2(int m , int n){
	vector<vector<int>> matrix(m);
	for(int i=0; i<m; i++){
		matrix[i] = vector<int>(n);
	}
	
	int num = 1;
	matrix[0][0] = num++;
	int x0=0, y0=0; // 上右边缘上的点坐标
	int x1=0, y1=0; // 左下边缘上的点坐标
	int direction = 'd';
	while(1){
		if(x0 == m - 1 && y0 == n - 1){
			break;
		}

		y0 ++;
		if(y0 >= n){
			x0 ++;
			y0 = n - 1;
		}			
		x1 ++;
		if(x1 >= m){
			x1 = m - 1;
			y1 ++;
		}
		
		if(direction == 'd'){
			direction = 'u';
			for(int x=x0, y=y0; y>=y1; x++, y--){
				matrix[x][y] = num++;
			}
		}else{
			direction = 'd';
			for(int x=x1, y=y1; x>=x0; x--, y++){
				matrix[x][y] = num++;
			}
		}
	}
	
	for(auto r : matrix){
		for(auto c : r){
			printf("%2d ", c);
		}
		printf("\n");
	}
	printf("\n");
}

一半只 walk 一步的实现方法, 更面向对象一些:

void print_spiral3(int m , int n){
	vector<vector<int>> matrix(m);
	for(int i=0; i<m; i++){
		matrix[i] = vector<int>(n);
	}
	
	int num = 1;
	int x = 0, y = 0; // 坐标
	int direction = 'u'; // 在初始之前是 up
	while(1){
		matrix[x][y] = num++;
		if(x == m - 1 && y == n - 1){
			break;
		}
		if(direction == 'u'){
			if(x == 0 || y == n - 1){
				direction = 'd';
				y ++;
				if(y >= n){
					x ++;
					y = n - 1;
				}
			}else{
				x --;
				y ++;
			}
		}else{
			if(y == 0 || x == m - 1){
				direction = 'u';
				x ++;
				if(x >= m){
					x = m - 1;
					y ++;
				}
			}else{
				x ++;
				y --;
			}
		}
	}
	for(auto r : matrix){
		for(auto c : r){
			printf("%2d ", c);
		}
		printf("\n");
	}
	printf("\n");
}

最后这种方案, 一个可能的坑是把方向分成4个, 而不是2个.

Related posts:

1. PHP 解码 C 字符串
2. 关于 C++ 中的函数指针
3. C/C++ 语言 switch-case 后面的花括号
4. C++ const& 的坑
5. 正确的将浮点数转成整数的方法 – 避免强制类型转换