【剑指offer】10~11.斐波那契数列（C# 实现）
文章目录
- 前言
- 关于编译环境
- 10- I. 斐波那契数列
- 10- II. 青蛙跳台阶问题
- 11. 旋转数组的最小数字
- 结语
前言
🍀 大家好，我是哈桑。这是自己的 C# 做题记录，方便自己学习的同时分享出来。
关于编译环境
注意，笔者使用的编译环境是 .NET 7 和 C# 11。
10- I. 斐波那契数列
题目描述：
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例：
输入：n = 2
输出：1
代码实现：
public class Solution {
public int Fib(int n) {
double MOD = Math.Pow(10,9) + 7 ;
if(n < 2)
{
return n;
}
double p = 0, q = 0, r =1;
for(int i = 2; i < n+1;i++)
{
p = q;
q = r;
r = (p + q) % MOD;
}
return (int)r;
}
}
运行结果：
思路讲解：
- 根据斐波那契数列数列的逻辑，而第一二项分别为0和1，从第三项开始的值为前两项的和。可以使用循环和条件判断语句翻译这些逻辑
- 创建 double 变量 p，q，r 分别表示数列的前三项。通过循环不断将变量 p、q 和 r 向前推进一位，直到走到 n 的位置
- 循环结束将变量 r 强制转换为 int 类型返回即可
代码实现2：
public class Solution {
public int Fib(int n) {
int[] f = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 134903163, 836311896, 971215059, 807526948, 778742000, 586268941, 365010934, 951279875, 316290802, 267570670, 583861472, 851432142, 435293607, 286725742, 722019349, 8745084, 730764433, 739509517, 470273943, 209783453, 680057396, 889840849, 569898238, 459739080, 29637311, 489376391, 519013702, 8390086, 527403788, 535793874, 63197655, 598991529, 662189184, 261180706, 923369890, 184550589, 107920472, 292471061, 400391533, 692862594, 93254120, 786116714, 879370834, 665487541, 544858368, 210345902, 755204270, 965550172, 720754435, 686304600, 407059028, 93363621, 500422649, 593786270, 94208912, 687995182 };
return f[n];
}
}
运行结果2：
思路讲解：
- 直接将所有结果按顺序存放在数组 f 中，根据索引值 n 返回数组中的元素即可
- 虽然思路很简单，但也是一种解决方法
10- II. 青蛙跳台阶问题
题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例：
输入：n = 2
输出：2
代码实现：
public class Solution {
public int NumWays(int n) {
int a = 1, b = 1, sum;
for(int i = 0; i < n; i++)
{
sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return a;
}
}
运行结果：
思路讲解：
- 像这类求解有多少种可能性的题目一般都有规律可循，也就是函数 f(n) 和 f(n - 1)…f(1) 之间是有联系的
- 通过观察可以发现，青蛙跳台阶问题符合 f(n) = f(n - 1) + f(n -2) 的规律，接下里把这种规律翻译成代码即可
- 思路和前面的斐波那契数列题目相差无几，这里不再赘述
11. 旋转数组的最小数字
题目描述：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。给你一个可能存在重复元素值的数组 numbers，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
示例：
输入：numbers = [3,4,5,1,2]
输出：1
代码实现：
public class Solution {
public int MinArray(int[] numbers) {
Array.Sort(numbers);
return numbers[0];
}
}
运行结果：
思路讲解：
- 首先题目明确要求返回数组中的最小元素，抛开是不是旋转数组不管，我们可以直接对数组进行升序排序，然后直接返回数组的第一个元素即可
- 使用 Array.Sort 方法排序，返回 numbers[0] 元素
代码实现2：
public class Solution {
public int MinArray(int[] numbers) {
int low = 0;
int high = numbers.Length - 1;
while(low < high)
{
int pivot = low + (high - low) / 2;
if (numbers[pivot] < numbers[high])
{
high = pivot;
}else if (numbers[pivot] > numbers[high])
{
low = pivot + 1;
}else
{
high--;
}
}
return numbers[low];
}
}
运行结果2：
思路讲解： （使用二分查找，点击了解更多。）
- 生成 low 和 high 整数变量分别表示 0 和 数组长度减一，使用循环语句进行判断
- 第一种情况 numbers[pivot]<numbers[high] 时，说明 numbers[pivot] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分
- 第二种情况是 numbers[pivot]>numbers[high]，说明 numbers[pivot] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分
- 第三种情况是 numbers[pivot]==numbers[high]，由于有重复元素的存在，所以我们需要继续判断
- 当整个循环结束时，我们就得到了最小值的索引位置了
结语
🌻 以上就是本次的做题记录啦，希望大家看完有所收获。