题目:给定一个 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;
}
题目:对整数的二进制表示取反(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;
}