基础算法学习_输入一个01矩阵,1代表是草地

1.二叉树的层次遍历
描述
给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）

示例
输入：{1,2,3,4,#,#,5}
返回值：[[1],[2,3],[4,5]]

题解：递归(前序遍历)
主要思路：前序遍历，中、左、右
左边的节点一定先于右边节点遍历到，加入至对应的数组中，满足层序遍历的要求；
要点：
1、利用一个level变量标记当前递归的深度，将节点的值push到当前深度的数组的后面；
2、level变量大于res数组的size，说明第一次进入二叉树本层，对res扩容；

//前序遍历模板，前序遍历得到二叉树的层次遍历；
struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int val1,TreeNode *l = NULL,TreeNode *r = NULL){//构造函数
		val = val1;
		left = l;
		right = r;
	}
};

void f(TreeNode* root,int level,vector<vector<int>> &res){
	if(!root)return ;
	if(level>=res.size()){//最新的深度，申请一个数组存储；
		res.push_back(vector<int> {});
	}
	res[level].push_back(root->val);
	f(root->left,level+1,res);//遍历左子树;
	f(root->right,level+1,res);//遍历右子树；
}
vector<vector<int> > levelOrder(TreeNode* root) {
	// write code here
	vector<vector<int>> res;//存储最终结果；
	f(root,0,res);//前序遍历；
	return res;//返回结果；
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2.岛屿的数量
描述
给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
示例
输入：[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]
返回值：3
DFS：
从一个为1的根节点开始访问，从每个相邻1节点向下访问到顶点（周围全是水），依次访问其他相邻1节点到顶点，其中找到一个1就岛屿标志加一，通过递归遍历将此岛屿的周围是1的全部赋予0，再开始遍历下一个岛屿，直到遍历整个地图没有岛屿“1”为止。

//岛屿的数量
void dfs(char[][] grid, int r, int c) 
{
	int nr = grid.length;
	int nc = grid[0].length;

	if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
		return;
	}

	grid[r][c] = '0';//将周围1的都设置为0
	dfs(grid, r - 1, c);
	dfs(grid, r + 1, c);
	dfs(grid, r, c - 1);
	dfs(grid, r, c + 1);
}
int solve(char[][] grid) 
{
	if (grid == NULL || grid.length == 0) {
		return 0;
	}

	int nr = grid.length;//行列
	int nc = grid[0].length;
	int num_islands = 0;
	for (int r = 0; r < nr; ++r) {
		for (int c = 0; c < nc; ++c) {
			if (grid[r][c] == '1' ) {//寻找1
				num_islands++;
				dfs(grid, r, c);//行列，将周围的1都设置为0，设置好了之后再寻找下一个岛屿，也就是不相邻的1
			}
		}
	}

	return num_islands;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

3.最大数
描述:给定一个nums数组由一些非负整数组成，现需要将他们进行排列并拼接，每个数不可拆分，使得最后的结果最大，返回值需要是string类型，否则可能会溢出

提示:
1 <= nums.length <= 100
0 <= nums[i] <= 10000
示例
输入：[2,20,23,4,8]
返回值：“8423220”

设计思想:
这道题题目己经提示,输出用字符串的形式了,所以我们第一步就是把整数数组变为字符串数组,第二步就是将字符串数组排序，排序规则就是:每次将相邻的两个字符申正反拼接,然后比大小,从而确定相邻的两个字符申是否交换位置。还有一个细节就是如果排序好的数组第一个元素就是”0”,那么结果直接返回字符串”0”就好了,如果排序好后的数组第一个元素不是”0”,那么直接从头到尾拼接返回就好了。字符串拼接就是字符串相加。

//最大数
//定义一个排序规则
static bool cmp(string a,string b){
	return a + b > b + a;
}
string solve(vector<int>& nums) {
	vector<string> ve;
	//将整型的数字转化为字符串
	for(int i  = 0;i < nums.size();i ++){
		ve.push_back(to_string(nums[i]));
	}
	//排序
	sort(ve.begin(),ve.end(),cmp);//cmp排序规则，利用此排序规则就可以得到拼接顺序
	//这个地方需要注意如果第一个字符串已经是0了，那么直接输出0
	if(ve[0] == "0") return "0";

	string res =""; //结果字符串
	for(int i = 0;i < ve.size();i ++){//字符串相加就是将字符串拼接起来。
		res += ve[i];//将排序好后的字符串一次相加就是最终的结果
	}
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

来源https://www.nowcoder.com/