1. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'
出处：
https://edu.csdn.net/practice/25116234
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: void DFS(vector<vector<int>> &mark, vector<vector<char>> &grid, int x, int y) { mark[x][y] = 1; static const int dx[] = {-1, 1, 0, 0}; static const int dy[] = {0, 0, -1, 1}; for (int i = 0; i < 4; i++) { int newx = dx[i] + x; int newy = dy[i] + y; if (newx < 0 || newx >= mark.size() || newy < 0 || newy >= mark[newx].size()) { continue; } if (mark[newx][newy] == 0 && grid[newx][newy] == '1') { DFS(mark, grid, newx, newy); } } } int numIslands(vector<vector<char>> &grid) { int island_num = 0; vector<vector<int>> mark; for (int i = 0; i < grid.size(); i++) { mark.push_back(vector<int>()); for (int j = 0; j < grid[i].size(); j++) { mark[i].push_back(0); } } for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[i].size(); j++) { if (mark[i][j] == 0 && grid[i][j] == '1') { DFS(mark, grid, i, j); island_num++; } } } return island_num; } }; int main() { Solution s; vector<vector<char>> grid = { {'1','1','1','1','0'}, {'1','1','0','1','0'}, {'1','1','0','0','0'}, {'0','0','0','0','0'}}; cout << s.numIslands(grid) << endl; grid = { {'1','1','0','0','0'}, {'1','1','0','0','0'}, {'0','0','1','0','0'}, {'0','0','0','1','1'}}; cout << s.numIslands(grid) << endl; return 0; }
输出：
1
3
2. 出现最多的整数及次数
原标题：计算出现次数最多的整数及其出现次数
【问题描述】 输入一组无序的整数，编程输出其中出现次数最多的整数及其出现次数。
【输入形式】
先从标准输入读入整数的个数（大于等于1，小于等于100），然后在下一行输入这些整数，各整数之间以一个空格分隔。
【输出形式】
在标准输出上输出出现次数最多的整数及其出现次数，两者以一个空格分隔；若出现次数最多的整数有多个，则按照整数升序分行输出。
【样例输入】
10
0 -50 0 632 5813 -50 9 -50 0 632
【样例输出】
-50 3
0 3
【样例说明】
输入了10个整数，其中出现次数最多的是-50和0，都是出现3次。
以下程序实现了这一功能，请你填补空白处的内容：
···c++
#include <stdio.h> int main() { int a[50], b[50], c[50], n, i, j, t, max; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &a[i]); } for (i = 1; i < n; i++) for (j = 0; j < n - 1; j++) { if (a[j] > a[j + 1]) { t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } j = 0; t = -1; for (i = 0; i < n - 1; i++) { ____________________; } b[j] = n - 1 - t; c[j] = n - 1; max = b[0]; for (i = 1; i <= j; i++) { if (max < b[i]) { max = b[i]; } } for (i = 0; i <= j; i++) if (b[i] == max) { t = c[i]; printf("%d %d\n", a[t], b[i]); } return 0; } ```
出处：
https://edu.csdn.net/practice/25116235
代码：
#include <stdio.h> int main() { int a[50], b[50], c[50], n, i, j, t, max; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &a[i]); } for (i = 1; i < n; i++) for (j = 0; j < n - 1; j++) { if (a[j] > a[j + 1]) { t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } j = 0; t = -1; for (i = 0; i < n - 1; i++) { if (a[i] != a[i + 1]) { b[j] = i - t; c[j] = i; t = i; j++; } } b[j] = n - 1 - t; c[j] = n - 1; max = b[0]; for (i = 1; i <= j; i++) { if (max < b[i]) { max = b[i]; } } for (i = 0; i <= j; i++) if (b[i] == max) { t = c[i]; printf("%d %d\n", a[t], b[i]); } return 0; }
输入输出：
10
0 -50 632 0 5813 -50 9 -50 0 632
-50 3
0 3
3. 两数相除
https://edu.csdn.net/practice/23819518
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
提示：
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。
#include <bits/stdc++.h> using namespace std; class Solution { public: int divide(int dividend, int divisor) { int signal = 1; unsigned int dvd = dividend; if (dividend < 0) { signal *= -1; dvd = ~dvd + 1; } unsigned int dvs = divisor; if (divisor < 0) { signal *= -1; dvs = ~dvs + 1; } int shift = 0; while (dvd > dvs << shift) { shift++; } unsigned int res = 0; while (dvd >= dvs) { while (dvd < dvs<<shift) { shift--; } res |= (unsigned int)1 << shift; dvd -= dvs << shift; } if (signal == 1 && res >= INT_MAX) { return INT_MAX; } else { return res * signal; } } }; int main() { Solution s; cout << s.divide(10, 3) << endl; cout << s.divide(7, -3) << endl; return 0; }
输出：
3
-2
