涉及到数组、字符串的分治,二分查找等时,二分时候的边缘值怎么计算?到底是该取n/2还是n+1/2还是n-1/2?以leetcode旋转矩阵为例,详细解读!

最近在做题,发现许多题都喜欢在边缘值上面小小捉弄一下做题人。
看过这篇博客,让你在面对循环的判断条件时候,再也不发怵。

题目描述

比如,leetcode旋转矩阵:
给你一幅由 N × N 矩阵表示的图像,其中每个像素的大小为 4 字节。请你设计一种算法,将图像旋转 90 度。

不占用额外内存空间能否做到?

示例 1:
给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],
原地旋转输入矩阵,使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
示例 2:
给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 
原地旋转输入矩阵,使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]
注意:本题与主站 48 题相同:https://leetcode-cn.com/problems/rotate-image/

这里思路其实就是按序推导出每个位置的旋转后位置应该在哪里,推导出一个方程组然后按照方程组的顺序进行连环赋值就可以了。四个为一组,什么什么的,想看题解具体可以看这篇博客:最近做leetbook的一些积累

那么,这个里面有一个挺重要的点,就是传入的 N × N N\times N N×N,这个N到底是奇数还是偶数。

  • 如果是偶数的话,挺好说的,直接把这个 N × N N\times N N×N大矩阵等分成四块儿,每一块儿的长 × \times ×宽都是 N 2 × N 2 \frac{N}{2} \times \frac{N}{2} 2N​×2N​。遍历某一块儿即可完成整体的旋转。不明白的去看上面的博客里对应部分的思路推导。
  • 但是如果N是奇数的话,我们会发现,大矩阵中间的那一个块儿是完全不需要移动的,需要移动的就是除了中间一块儿的其他的块儿。但是如果还要等分成四块儿的话,就得长和宽不均等分配,每一块儿的长 × \times ×宽这个时候变成了 N − 1 2 × N + 1 2 \frac{N-1}{2} \times \frac{N+1}{2} 2N−1​×2N+1​。

这个思路本身没什么问题,问题就出在了写代码上面。
如果我们要让我们的代码尽可能地简单,就是要不管传入的是长宽为奇数的矩阵还是长宽为偶数的矩阵,都要让一个循环来解决这个问题。

重点:结论(仅适用于地板除法例如c++)

先说结论,大家看完结论如果能记住的话可以直接点个赞然后关掉这个博客啦~^O^
对于 i n t   x < s t a t e m e n t int \ x < statement int x<statement这类问题:(仅适用于地板除法例如c++)

statement n为奇数 n为偶数
n + 1 2 \frac{n+1}{2} 2n+1​ 结果比下面两个大1 结果与 n 2 \frac{n}{2} 2n​相同
n 2 \frac{n}{2} 2n​ 结果与 n − 1 2 \frac{n-1}{2} 2n−1​相同 结果与 n + 1 2 \frac{n+1}{2} 2n+1​相同
n − 1 2 \frac{n-1}{2} 2n−1​ 结果与 n 2 \frac{n}{2} 2n​相同 比上面两个小1

自己动手算算,是不是这样?

用在leetcode旋转矩阵中:

class Solution {
public:
	void rotate(vector<vector<int> >& matrix)
	{
		int temp = 0;
		int n = matrix.size();
		//-------------------------------------
		for (int row = 0; row < (n + 1) / 2; row++)
		{
			for (int col = 0; col < n / 2; col++)
			{
		//-------------------------------------
				temp = matrix[row][col];
				matrix[row][col] = matrix[n - col - 1][row];
				matrix[n - col - 1][row] = matrix[n - row - 1][n - col - 1];
				matrix[n - row - 1][n - col - 1] = matrix[col][n - row - 1];
				matrix[col][n - row - 1] = temp;
			}
		}
	}
};

两个横线的*,就是重头戏。我本处针对长和宽一个是 n − 1 2 \frac{n-1}{2} 2n−1​一个是 n + 1 2 \frac{n+1}{2} 2n+1​的,采取的是行数是长的(比如说n=5时,采取三行两列的分割方式),所以在第一个循环的判断条件处,写的是row < (n + 1) / 2。此处如果是偶数,那么没毛病,依然是两等分(地板除法),如果是奇数,那么这里也没毛病;下面的col < n / 2,如果是奇数的话,那么没毛病,跟 n − 1 2 \frac{n-1}{2} 2n−1​的结果是一样的。如果是偶数的话,那也没毛病,也是等分。

仔细推敲一下,看是不是?如果这里自己分析透彻了,那么之后再碰到这种类似的问题,都不用怕了!
如果您感觉本博客对您有帮助,请帮忙点一个赞,谢谢~

上一篇:菜鸡的数学笔记


下一篇:POJ1182 食物链(并查集)