【Day12】力扣LeetCode刷题[788.旋转数字][200.岛屿数量][509. 斐波那契数]
【Day12】力扣LeetCode刷题[788.旋转数字][200.岛屿数量][509. 斐波那契数]
CSDN话题挑战赛第2期 参赛话题：学习笔记
刷题打卡，第十二天
题目一、788.旋转数字
原题链接：788.旋转数字
题目描述：
我们称一个数 X 为好数, 如果它的每位数字逐个地被
旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。 如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0,1, 和8被旋转后仍然是它们自己；2和5可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2和5互为镜像）；6和9同理，除了这些以外其他的数字旋转以后都不再是有效的数字。 现在我们有一个正整数N, 计算从1到N中有多少个数 X 是好数？ / 示例： 输入: 10 输出: 4 解释: 在[1, 10]中有四个好数： 2, 5, 6, 9。 注意 1 和 10 不是好数, 因为他们在旋转之后不变。 / 提示： N 的取值范围是 [1, 10000]。
解题思路：
题目给出1到N，要求从中找出好数的个数，那么我们肯定需要遍历从1到N个数；
每遍历到一个数，我们都需要获取这个数的个位数，十位数，百位数到前面的每位数字，从而通过每位数字来判断这个数是否为好数：
用sum来记录好数的个数；
定义一个标杆flag，默认为0，flag = 0 不是好数 ；最终flag = 1 是好数；
若出现3，4，7这样的旋转后已经不是一个数字位数，直接flag = 0，开始判断1到N中的下一个数；
若出现2，5，6，9这样旋转后为另一个数字的，flag暂时为1，若每位数字都判断完，flag依旧为1，说明是一个好数，sum+1；
提交代码：
class Solution {
public int rotatedDigits(int n) {
int sum = 0; //记录好数的数量
int flag = 0; //标记是否为好数0为否，是为1
for(int i = 1;i <= n; ++i){//遍历1到n寻找好数
int curr = i; //记录当前遍历到的数
while(curr > 0){
int num = curr%10; //获取每位数字
//遇到旋转后无效到的数字，不是好数，遍历i的下一个数
if(num == 3 || num == 4 || num == 7){
flag = 0;//为0，即不是好数
break;
}
//旋转后数字仍有效，且与原数字不同，说明是好数，sum+1
else if(num == 2 ||num == 5 ||num == 6 ||num == 9){
flag = 1;//为1，可能是好数
}
curr /= 10; //去掉最后一位数
}
if(flag == 1){//遍历完每位数字后，flag仍为1，是好数
++sum; //记录加一
flag = 0; //标杆恢复默认值0
}
}
return sum; //返回好数个数；
}
}提交结果：
题目二、200.岛屿数量
原题链接：200.岛屿数量
题目描述：
给你一个由
'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’
解题思路：
题目要求输出二维网格中的岛屿数量，我们可以遍历所有网格，若是得到网格中的土地（数值为 1） ，记录的岛屿数量就加1；
同时运用深度优先搜索的思想，将处于同一个岛屿上，数值为1的土地遍历，将数值改为2，代表已经遍历过了的土地；
继续遍历下一个网格，如果是海水‘0’或者遍历过的土地‘2’就直接掉过，最终返回记录下来的岛屿数量即可。
提交代码：
class Solution {
void DFS(char[][] grid,int sr,int sc){
//下标sr，或sc越过网络界限，返回；
//扫描的不是 未遍历的土地'1'，返回；
//用‘0’代表海，‘2’代表遍历过的土地
if(sr < 0 || sc < 0 ||sr >= grid.length || sc >= grid[0].length
|| grid[sr][sc] != '1'){
return;
}
grid[sr][sc] = '2';//记录遍历过的土地，记录为字符'2'
//遍历土地在网格中上下左右方向的格子
DFS(grid,sr+1,sc);
DFS(grid,sr-1,sc);
DFS(grid,sr,sc+1);
DFS(grid,sr,sc-1);
}
public int numIslands(char[][] grid) {
int sum = 0;//用于记录岛屿数量
for(int sr = 0;sr < grid.length;++sr){
for(int sc = 0;sc < grid[0].length;++sc){
if(grid[sr][sc] == '1'){
++sum; //遇到岛屿，sum+1
//遍历整个岛屿
DFS(grid,sr,sc);
}
}
}
return sum;
}
}提交结果：
题目三、509. 斐波那契数
原题链接：509. 斐波那契数
题目描述：
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。 / 示例 1： 输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1 / 示例 2： 输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2 / 示例 3： 输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3 提示： 0 <= n <= 30
解题思路：
斐波拉契数，通过循环，返回当前元素的前两个数之和即可；
提交代码：
class Solution {
public int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
int before = 0;
int after = 1;
int curr = 0;
for(int i = 1;i < n;++i){
curr = before + after;
before = after;
after = curr;
}
return curr;
}
}提交结果：
腾讯云开发者
