数据结构与算法系列八(递归见面礼)

2019/04/10 10:10
阅读数 15

1.引子

1.1.为什么要学习数据结构与算法?

有人说,数据结构与算法,计算机网络,与操作系统都一样,脱离日常开发,除了面试这辈子可能都用不到呀!

有人说,我是做业务开发的,只要熟练API,熟练框架,熟练各种中间件,写的代码不也能“飞”起来吗?

于是问题来了:为什么还要学习数据结构与算法呢?

#理由一:
    面试的时候,千万不要被数据结构与算法拖了后腿
#理由二:
    你真的愿意做一辈子CRUD Boy吗
#理由三:
    不想写出开源框架,中间件的工程师,不是好厨子

1.2.如何系统化学习数据结构与算法?

我想好了,还是需要学习数据结构与算法。但是我有两个困惑:

1.如何着手学习呢?

2.有哪些内容要学习呢?

学习方法推荐:

#学习方法
1.从基础开始,系统化学习
2.多动手,每一种数据结构与算法,都自己用代码实现出来
3.思路更重要:理解实现思想,不要背代码
4.与日常开发结合,对应应用场景

学习内容推荐:

数据结构与算法内容比较多,我们本着实用原则,学习经典的、常用的数据结构、与常用算法

#学习内容:
1.数据结构的定义
2.算法的定义
3.复杂度分析
4.常用数据结构
    数组、链表、栈、队列
    散列表、二叉树、堆
    跳表、图
5.常用算法
    递归、排序、二分查找
    搜索、哈希、贪心、分治
    动态规划、字符串匹配

2.考考你

到目前为止,基于线性表的数据结构我们都看完了,简单回顾一下,它们是:数组、链表、栈、队列。这些数据结构是其它数据结构与算法的基础,需要重点关注。

这一篇开始,我们开启算法的列车了,请系好安全带!第一个要看的算法是:递归。递归这两个字你一定很熟悉,有没有?

如果没有的话,我们先举一个例子。从2016年开始到如今,知识付费发展的如火如荼。如果你也是其中的一员,比如说在xx平台购买了xx课程。大多数平台都会告诉你,将你购买的课程分享出去,假如有人通过你分享的链接购买了该课程,那么平台会给你佣金返现。

既然与钱有关系,那就比较麻烦了!对于平台来说,有这么几个问题需要搞清楚。比如说:1.谁是一级推荐人?

2.谁是二级推荐人......?

3.谁是最终推荐人?

因为不同级的推荐人,返现佣金的比例可不一样,千万别返错了,对吧。关于这种类似求推荐人的问题,有请我们今天的主角登场,它就是:递归

#递归稍微有些复杂,我们通过两篇来学习:
1.第一篇是见面礼:
  1.1.体会两个生活中的小案例
  
2.第二篇是重头戏:
  2.1.详细分析递归的实现
  2.2.递归实现的注意事项

3.案例

3.1.求最终推荐人

简述:

1.A在某某知识付费平台购买了课程:xx。并将链接分享到了微信朋友圈

2.B通过A分享的链接,购买了课程:xx。并且将链接分享到了微信朋友圈

3.C通过B分享的链接,购买了课程:xx。并且将连接分享到了微信朋友圈

4.以此类推下去......

5.假如以C为起点,如何求出课程:xx的最终推荐人?

6.假设数据库中存储的数据是这样的:

 

 

求解:

1.你肯定想到了,这个问题好简单,经常写如下类似这样的代码:

/**
* 求最终推荐人
*/
public String findRootRecommend(String userId,String xx){
    // 根据购买课程用户id、课程  查询数据库,获取推荐用户id
    String 【分享用户id】 = select 【分享用户id】 from 【购买课程表】 where 【用户id】 = 【userId】 and 【课程id】 = 【xx】;
    
    // 判断是否是根据好友分享购买的课程
    if(分享用户id == null){
        return userId;
    }
    
    // 递归查找
    return findRootRecommend(分享用户id,xx);
}

3.2.电影院看电影

简述:

1.你与女朋友正在电影院看电影,电影已经放映

2.突然,女朋友问你:我们坐在电影院的第几排?

3.你一看,坏了:电影院一片漆黑,伸手不见五指

4.这个问题必须要回答,因为是女朋友问的,你该怎么办?

求解:

1.别忘了,你是程序员,对于程序员来说,这个问题太简单了

2.用递归:先问前一排的人,他们在第几排?

3.前一排的人,再问他的前一排,在第几排?

4.以此类推......

5.一直问到第一排的人,第一排不需要再问了,直接回答在第一排

6.第二排的人:在第一排的人基础上 + 1

7.以此类推......

8.每一排都在前一排的基础上 + 1,最后到了你们这一排,女朋友得到了满意的答案

9.你很骄傲有没有?用代码回答,类似这样:

public int movies(int n){
    // 如果是第一排,返回1
    if(n == 1){ return 1;}
    
    // 递归向前一排询问
    return movies(n - 1) + 1;
}

 

原文出处:https://www.cnblogs.com/itall/p/12408767.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部