刷题打卡，第十二天
题目一、788.旋转数字
题目二、200.岛屿数量
题目三、509. 斐波那契数
题目一、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; } }
提交结果：
⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞，收藏以及关注是对作者最大的鼓励喔 ~~
贵在坚持：
