每日算法题：Day 23（Python）

作者：TeddyZhang，公众号：算法工程师之路

Day 23, Python知识点走起~

1

编程题

【剑指Offer】圆圈中最后剩下的数

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

思路： 这很直接的思路是循环链表的方式，本来想要用list容器做的，但最后OJ过不了，所以最后还是使用vector容器吧，由于这些小朋友是一个圈的形式，因此当找到第一个小朋友时假设为temp，则下一个m-1的位置为temp = (tmp+m-1) % data.size()，注意由于temp找到时会被删掉，因此其下一个的位置仍然是temp, 只不过data.size()会减小一个！

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if ((m <= ) && (n <= ))
            return -1;
        vector<int> data;
        for (int i = ; i < n; i++)
            data.push_back(i);
        int temp = ;
        while (data.size() > )
        {
            temp = (temp + m-1) % data.size();
            data.erase(data.begin()+temp);
        }
        return data[];
    }
};

【剑指Offer】求1+2+3+…..+n

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

思路： 由于题目好多运算符不能用，我们只有想到使用递归的方法，但是递归一般要判断递归结束条件，但题目又不让使用if语句，因此我们可以使用&&运算符，也就是这句话：res && (res+=Sum_Solution(n-1))，也就是res为零时，与运算符的右边将不执行，因此递归结束，返回最后的res即可得到总和，非常棒的思路！

class Solution {
public:
    int Sum_Solution(int n) {
        int res = n;
        res && (res += Sum_Solution(n-1));
        return res;
    }
};

2

概念题

【Python】请按alist中元素的age由大到小排序

利用sorted函数中的参数key和reverse, 注意sorted函数默认是从小到大排列的!

alist = [{'name':'a','age':},{'name':'b','age':},{'name':'c','age':}]
def sort_by_age(list1):
    return sorted(alist,key=lambda x:x['age'],reverse=True)

【Python】生成器、可迭代对象和迭代器的区别

可以使用isinstance()函数来判断一个对象是否为Itreator, Iterable.

• 可迭代对象：凡是可以用for循环及逆行遍历取值的对象称为可迭代对象，可迭代对象可以在一个周期中使用无限轮次的循环遍历。一个可迭代对象主要包括序列和迭代器两种！
• 迭代器：在一个类的内部重载了__iter__和 __next__两个内置函数，并且可以使用next()函数不断的返回下一个值，直到最后抛出StopIteration错误表示无法继续返回下一个值了。
• 生成器：生成器是一种特殊得迭代器，也是可迭代对象，但是和迭代器不同的是边遍历边输出，并不是一次性获取所有得结果。

生成器本质是一个函数，通常配合yield使用，当第一次调用next，程序会运行到yield位置，输出结果并将函数挂起，当第二次调用时，会直接跳转到挂起位置接着执行！

注意：集合数据类型list, dict, str等时可迭代对象，但不是迭代器！生成器实质保存得是一种计算方法，并没有将运行过程所有的值进行保存，而迭代器会对数据进行一次全部获取，然后依次遍历！

【Python】for循环实质以及生成器实现！

利用iter可以将一个可迭代对象变成一个迭代器

for x in [,,,,]:
    pass
# 等价于下面得方式，首先将list变成迭代器，然后使用next进行获取
while True:
    try:
        x = next(it)
    except StopIteration:
        break

生成器实现，在普通函数中将输出用yield关键字进行输出，虽然每次运行都需要使用next获取，但一般直接使用for进行迭代就可以了，for循环就相当于内部实现了next

def fib(max):
    n, a, b = , , 
    while n < max:
        yield b     # 每次运行到这里会输出并将函数挂起
        a, b = b, a + b
        n = n + 
    return 'done'

for n in fib():   # 使用for循环来代替next进行获取
    print(n)

3

资源分享

欢迎关注我的个人公众号 （算法工程师之路），公众号内有大量视频资料和电子书资料以及算法笔记，回复关键字即可获取！

公众号简介：分享算法工程师必备技能，谈谈那些有深度有意思的算法，主要范围：C++数据结构与算法/深度学习（CV），立志成为Offer收割机！坚持分享算法题目和解题思路（Day By Day)