Leetcode -463.岛屿的周长

题目：给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。
整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。
格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 1：
输入：grid = [[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0], [1, 1, 0, 0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

示例 2：
输入：grid = [[1]]
输出：4

示例 3：
输入：grid = [[1, 0]]
输出：4

思路是每判断一个正方形如果是陆地，就判断它的上下左右边是否是有效边，如果是有效边则统计此有效长度；如图，中间蓝色部分的长度就是我们需要判断的部分；

详细解释看以下代码以及注释：

		//用来作当前坐标的上下左右坐标的判断，当x为0时，y要为1
		const int dx[4] = { 0,0,1,-1 };
		const int dy[4] = { 1,-1,0,0 };
		
		int islandPerimeter(int** grid, int gridSize, int* gridColSize)
		{
		    //ans记录有效边长的长度，即个数，因为边长等于1
		    int ans = 0;
		
		    //n为二维数组中的行数
		    //gridColSize这个指针数组，指向的数组是，每一行中元素的个数，所以数组中的元素都是相等的；即*gridColSize等价于gridColSize[0]
		    int n = gridSize, m = *gridColSize;
		
		    //i遍历每一行
		    for (int i = 0; i < n; i++)
		    {
		        //j遍历每一行的每一个正方形
		        for (int j = 0; j < m; j++)
		        {
		            //如果当前正方形为陆地，就判断其上下左右四个正方形的有效性
		            //tx < 0代表当前正方形为第一行的正方形的上面的一条边，即为有效长度
		            //ty < 0代表当前正方形为最左边的正方形的左边的一条边，即为有效长度
		            //tx == n代表当前正方形为最后一行的正方形的下面的一条边，即为有效长度
		            //ty == m代表当前正方形为最右边的正方形的右边的一条边，即为有效长度
		            //!grid[tx][ty]等价于 grid[tx][ty] == 0 ，即它的相邻边为湖水，所以这条相邻边为有效长度
		            if (grid[i][j])
		            {
		                for (int k = 0; k < 4; k++)
		                {
		                    int tx = i + dx[k];
		                    int ty = j + dy[k];
		                    if (tx < 0 || ty < 0 || tx == n || ty == m || !grid[tx][ty])
		                    {
		                        ans += 1;
		                    }
		                }
		            }
		        }
		    }
		    return ans;
		}

Leetcode - 476.数字的补码

题目：对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

例如，整数 5 的二进制表示是 “101” ，取反后得到 “010” ，再转回十进制表示得到补数 2 。
给你一个整数 num ，输出它的补数。

示例 1：
输入：num = 5
输出：2
解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。

示例 2：
输入：num = 1
输出：0
解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。

思路是要找到num二进制中最高位的1，然后减去1之后与num按位异或，就能得到补码；如图，假设num = 8：

此时flag向左移动四位之后跳出循环，但flag为3：

此时flag = 3，但是num的最高位1是需要向左移动四位，所以将1向左移动flag+1位；然后减1得到mask，再进行按位异或：

相异位1，相同为0，刚好符合将num二进制中的1变成0，0变成1，所以最后结果为：

		int findComplement(int num)
		{
		    //flag记录num最高位的1的后一位
		    int flag = 0;
		
		    //找到num最高位的1
		    //因为32位二进制最高位的1是符号位，所以不作判断，所以最多向左移动30位
		    for (int i = 1; i <= 30; i++)
		    {
		        if (num >= (1 << i))
		        {
		            flag = i;
		        }
		        else
		        {
		            break;
		        }
		
		    }
		
		    //如果flag等于30，即num的1在它二进制的位数中的顺数第2位，已经算是最高位了，
		    //所以直接与0x7fffffff按位异或，0x7fffffff就是二进制中，除了第一位是0，其余都是1
		
		    //如果flag不等于30，即num的1不在最高位，直接按照思路按位异或即可
		    int mask = (flag == 30 ? 0x7fffffff : (1 << (flag + 1)) - 1);
		    return num ^ mask;
		}