文章目录

• 前言
• 关于编译环境
• 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[pivot]>numbers[high]，说明 numbers[pivot] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分
• 第三种情况是 numbers[pivot]==numbers[high]，由于有重复元素的存在，所以我们需要继续判断
• 当整个循环结束时，我们就得到了最小值的索引位置了

结语

🌻 以上就是本次的做题记录啦，希望大家看完有所收获。