精选算法入门——day3
题目一
题干
大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。斐波那契数列的表达式如下图：
解题思路一
这条题目属于经典中的经典了，我们用表达式可能不太清楚，我们用表格来表示：
| 项数 | 斐波那契数 |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| …… | …… |
也就是说第n项的结果是由第n-1项和第n-2项相加得到的，就比如第四项的结果是3，它是由第三项（2）与第二项（1）相加得到的。那么我们可以用迭代的方式来解决这个问题，具体计算如图所示：
首先我们将first和second都赋值为1，然后将first(1)+second(1)相加得到third(2)，然后再将second赋值给first，再把third赋值给second，再将first(1)+second(1)相加得到third(3)，以此类推。但是需要注意的是循环的次数，如果n=3，就循环一次，n=4，就循环两次，因此我们可以设置while(n>2)，当然我们还有一个问题，我们的返回值肯定是third这个毋庸置疑，但是我们也要考虑n=1和n=2的情况，我们直到n=1和n=2，返回值都应该是1，那么我们可以将third初始化为1。下面是完整代码：
代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
*/
public int Fibonacci (int n) {
// write code here
int first = 1;
int second = 1;
int third = 1;
while(n > 2){
third = first + second;
first = second;
second = third;
n--;
}
return third;
}
}
解题思路二
这道题还有没有其他的解题思路呢？当然有，我们看下面这个图：
从图中可以看到，我们求f(5),就需要求f(4)和f(3)，求f(4)就需要求f(3)和f(2)，直到最后为f(1)和f(2)，因此我们将一个大的问题分为了小问题，再将小问题再化为小小问题，因此我们可以采用递归来解决这个问题。下面是完整代码：
代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
*/
public int Fibonacci (int n) {
if(n <= 2){
return 1;
}
return Fibonacci(n-1) + Fibonacci(n-2);
}
}
解题思路三
有同学要说，这个代码少，看着简洁，肯定是一个好的方法，但事实是这样吗？其实不然，这种方法存在一个弊端，为什么这么说，从上面的图我们可以发现，单单的f(3)就被求了两次，一次是求f(4)（f(4)=f(3)+f(2)）时，一次是求f(5)（f(5) = f(4)+f(3)）时，就相当于不停的重复计算，这样一来时间复杂度就增加了，那么有什么好的方法嘛？我们可以想象一下，当我们记不住事的时候，我们怎么办？有同学要说，拿笔记下来不就行了？确实是这样的，我们也可以用这种思想，我们可以定义一个map，比如说求n=5，我们就到map里面去找，有没有n=4和n=3的结果，如果有，就把两者相加，没有就计算n=4（n=3），计算完n=4（n=3）后，再把n=4（n=3）的结果记录到map里面。下面为完整代码：
代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
*/
private Map<Integer,Integer> map = new HashMap<>();
public int Fibonacci (int n) {
if(n <= 2){
return 1;
}
int pre = 0;
if(map.containsKey(n-1)){
pre = map.get(n-1);
} else {
pre = Fibonacci(n-1);
map.put(n-1,pre);
}
int ppre = 0;
if(map.containsKey(n-2)){
ppre = map.get(n-2);
} else {
ppre = Fibonacci(n-2);
map.put(n-2,ppre);
}
return pre+ppre;
}
}
题目二
题干
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算
不同的结果）。
解题思路
青蛙🐸跳台阶也算得上一个经典的问题了，这个问题我专门做过一篇博客，链接如下：青蛙跳台阶问题（Java语言），这一次我们重新审视一下这个问题。
我们假设青蛙🐸已经在第n个台阶了，那么我们知道，此青蛙🐸是从n-1个台阶跳一格到第n个台阶，或者从第n-2个台阶跳两格到第n个台阶，因此我们可以得到f(n) = f(n-1) + f(n-2)，也就是说，青蛙跳到第n个台阶的总跳法数=第n-1个台阶的总跳法数+第n-2个台阶的总跳法数。我们再来看一下这个式子：f(n) = f(n-1) + f(n-2)，是不是很熟悉，没错，就是我们上面的斐波那契数列。那么我们就只需要确定f(1)和f(2)就可以了，青蛙🐸跳上第一个台阶有一种跳法，青蛙🐸跳上第二个台阶有两种跳法，也就是说f(1)=1，f(2) = 2。具体的代码我也不再写了。
题目三
题干
我们可以用 2×1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个 2×1 的小矩形无重叠地覆盖一个 2×n 的大矩形，总共有多少种方法？比如：n=3时， 2×3 的矩形块有3种覆盖方法：
解题思路
这道题拿到手上感觉很简单，其实也是无从下手的感觉，那么我们应该如何解决这类问题呢？我们画个图理解一下：
我们假设覆盖一个 2×n 的大矩形，共有f(n)种方法，也就是图中左边的样子，我们可以把f(n)拆分为右边两种，也就是覆盖2×(n-1)的大矩形（它的左边竖着放一个小矩形)的方法数和覆盖2×(n-2)的大矩形的方法数（它的左边横着放两个小矩形），有同学要问下面这个方法不是可以竖着放两个小矩形嘛？这样是不行的，为什么不行呢？我们看当我们竖着放的时候，其实就和上面（n-1）的重复了，由此我们总结f(n) = f(n-1)+f(n-2)。耶？这个好像还是斐波那契数列，那么我们再看他的初始情况，当n=1时，f(n)=1，当n=2时，f(n)=2，由此问题解决，具体的代码部分也不再详细写出来了。
题目四
题干
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解题思路一
这条题目拿到手，第一感觉是将该数和1进行按位与操作，然后再将1左移一位，直到循环结束。我们通过画图来理解：
上面的数字为输入的数字（n），下面的数字为移动的数字（初始为1），当n和1进行按位与操作时，如果等于1那么证明二进制中存在一个1，那么计数器count++，并且数字1左移一位。如果n和1（左移后数字不是1了，这里为了方便理解就还说是1）进行按位与操作时等于0，那么证明该二进制位置不是数字1，计数器不变，数字1左移一位，直到循环结束，下面是完整代码。
代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
*/
public int NumberOf1 (int n) {
// write code here
int count = 0;
int a = 1;
for(int i=0; i<32; i++){
if((a&n) != 0){
count++;
}
a = a<<1;
}
return count;
}
}
解题思路二
我们发现在解题思路一中好是好，但是有一个问题，什么问题？我们发现，不管n这个数的二进制位上是0还是1，移动的数字都要左移，当二进制中0很多1很少的时候效率就很低，因为我们要找的是二进制位上的1，0是我们做的无用功，就好比说，老板布置一个任务给你，这个任务麻烦多（0多），好处少（1少），但是你又不得不干，那肯定很烦呀。那么还有什么方法嘛？我们直接上图：
我们可以看到初始输入n为1100 0011，此时计算n和n-1按位与操作，得到结果1100 0010，此时我们把这个新的结果赋值给n，如此循环，循环一次，计数器count就+1，问题就解决了，有同学会问为什么呢？我们直到一个数减去1，就要往前面借一个1，并且所借1后面的所有数字都要取反（例如：1000 0000，减去1后，他的最左边的1被借走了，并且后面的数字全部取反，也就是0111 1111），那么按位与操作就相当于把所借的“1”给消除掉，循环了几次，也就消除了几个“1”，那么就能够得到结果了。下面为完整代码：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
*/
public int NumberOf1 (int n) {
// write code here
int count = 0;
while(n != 0){
n = n & (n-1);
count++;
}
return count;
}
}
题目五
题干
输入一个链表，输出该链表中倒数第k个结点。
解题思路一
这道题目的难点就在于，在单链表的情况下如何输出链表中倒数第k个节点，我们直到单链表只能由前往后，无法由后往前，有一个非常简单的思路，首先我们遍历整个链表，并记下链表的长度，然后由倒数求出整数多少个。这个思路比较简单我们就不画图解决了，我们直接上代码：
代码
public ListNode function(ListNode head, int k) {
if (head == null){
return null;
}
int count = 0;
ListNode tmp = head;
while (tmp != null) {
count++;
tmp = tmp.next;
}
int key = count - k;
for (int i = 0; i < key; i++) {
head = head.next;
}
return head;
}
解题思路二
当然我们也可以用快慢指针的方法来解决，什么意思？我们通过画图来理解一下：
例如当我们求倒数第二个节点时，我们可以先让fast指针先走一格，然后fast和slow同时走，当fast指针到达终点的时候，slow指针就是我们求的节点，为什么呢？其实道理很简单，我们要求倒数第k个节点，那么它距离最后一个节点的距离是k-1，也就可以让一个指针（fast）先走k-1个位置，在让slow和fast一起走，最后fast到达最后一个节点，那么slow也就到了。下面我们通过代码来实现。
代码：
public ListNode function(ListNode head, int k) {
if (head == null){
return null;
}
ListNode fast=head;
ListNode slow=head;
for (int i = 0; i <k-1; i++) {
fast = fast.next;
}
while (fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
原文地址：https://blog.csdn.net/qq_57563254/article/details/142791187
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！