数据结构与算法（下）

3.1.17 快速排序

【考点映射】

【出现频度】★★★★☆

【难度】★★★☆

【参考答案】

快速排序(Quick Sort)使用分治法策略。它的基本思想是：在数据序列中选择一个元素作为基准值，每躺从数据序列的两端开始交替进行，将小于基准值元素交换到序列前端，将大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准值的最终位置。同时，序列被划分成两个子序列，再分别对两个子序列进行快速排序，直到子序列长度为1，则完成排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

动画图解：

代码示例（Python）：

def quick_sort(lists, left, right):
    '''
    快速排序（升序）【不稳定】
    原理：
    分治递归，给定一组序列，把序列分为两部分，前部分的所有元素比后部分的所有元素小，然后再对前后两部分进行快速排序，递归该过程，直到所有记录
    均有序为止。分三步走：
    (1)分解，array[m,...,n] 划分成 array1[m,..,k] 和 array2[k+1,...,n], 其中 array1 所有元素 < array2 所有元素
    (2)递归求解，递归array1, array2
    (3)合并，array[m,...,n] 自动排好序

    :param lists:
    :param left:
    :param right:
    :return lists:
    '''
    if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
    while left < right:
        while left < right and lists[right] >= key:
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left - 1)
    quick_sort(lists, left + 1, high)
    return lists

if __name__ == '__main__':
    # 测试代码
    lst = [5, 4, 3, 2, 1]
    # 调用归并排序
    sorted_list = quick_sort(lst, 0, len(lst) - 1)
    print(sorted_list)
    # 输出：[1, 2, 3, 4, 5]

---

3.1.18 斐波那契数列

【考点映射】

【出现频度】★★★☆

【难度】★★

【题目描述】

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、…… 基于python用多种方式，找到前n项斐波那契数列或找到第n项斐波那契数列的值。

【参考答案】

下面介绍3种解法：

解法一：递归法

递归法主要的好处在于，算法思路比较清晰，我们都知道除了前2个数之外，其他数都是由它的前两个数相加而得到。但是通过递归，我们只能获取第n项斐波那契数列的值，却难以得知前n项数列元素分别是什么。

解法二：迭代法

迭代法可以用一个列表，可以把前n项的斐波那契数列的数值都存储起来，这样我们就可以知道前n项数列元素都有哪些。但是假如n特别大，对于内存的占用也会较高。

解法三：升级版迭代法

可以用生成器代替列表，因为生成器不会把值都存入到内存中，仅当用到时才会动态计算，所以对于内存的占用会小很多。

代码示例（Python）：

# （1）递归法 返回 idx 位的数值，缺点：只能返回最终返回值
def fib_recursion(idx):
    if idx <= 2:
        return 1
    else:
        return fib_recursion(idx-1) + fib_recursion(idx-2)

# （2）迭代法 返回 idx 位之前的fib数列
def fib_iteration(idx):
    lst = []
    n,a,b = 0,0,1
    while n < idx:
        lst.append(b)
        a,b = b, a+b
        n += 1
    return lst

# （3）生成器法
def fib_generator(idx):
    n,a,b = 0,0,1
    while n < idx:
        yield b
        a,b = b, a+b
        n += 1

if __name__ == '__main__':
    idx = 6 
    # 递归法调用
    numb = fib_recursion(idx)
    print(numb)
    # 输出： 8
    
    # 迭代法调用
    lst = fib_iteration(idx)
    print(lst)
    # 输出： [1, 1, 2, 3, 5, 8]
    
    # 生成器法
    lst1 = fib_generator(idx)
    print(list(lst1))
    # 输出： [1, 1, 2, 3, 5, 8]

---

3.1.18 丑数

【考点映射】

【出现频度】★★☆

【难度】★★★☆

【题目描述】

只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。一般地，认为1是第一个丑数，1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18是最前面的13个丑数

【参考答案】

原理：本题可采用动态规划思想解题。后面的丑数一定是由前面的丑数乘以2、3或5得到。

所以第n个丑数一定是由前n-1个数中的某3个丑数（分别记为index2、index3、index5）分别乘以2、3或者5得到的数中的最小数，index2，index3，index5有个特点，即分别乘以2、3、5得到的数一定含有比第n-1个丑数大（可利用反证法：否则第n-1个丑数就是它们当中的一个）最小丑数，即第n个丑数由u[index2]2、u[index3]3、u[index5]*5中的最小数得出。让它们分别和第n个丑数比较，若和第n个丑数相等，则更新它们的值。

注：一次最少更新一个值（如遇到第n个丑数是6时，index2和index3都要更新）。

代码示例（Python）：

def ugly_num(n):
    # 边界值判断
    if n <= 0:
        return False
    t1 = 0
    t2 = 0
    t3 = 0
    res = [1]
    while len(res) < n:
        res.append(min(res[t1] * 2, res[t2] * 3, res[t3] * 5))
        if res[-1] == res[t1] * 2:
            t1 += 1
        if res[-1] == res[t2] * 3:
            t2 += 1
        if res[-1] == res[t3] * 5:
            t3 += 1
    return res[-1]


if __name__ == '__main__':
    # 测试代码
    # 求第10位丑数
    ugly_number = ugly_num(10)
    print(ugly_number)
    # 输出 12

---

3.1.19 如何对字符串进行反转

【考点映射】

【出现频度】★★★★☆

【难度】☆

【题目描述】

给定一个字符串，反转该字符串。
例如：s = "hello world" => s = "dlrow olleh"

【参考答案】

此题有两种解法：

解法1：双指针迭代法

解法2：python切片

解法1 是大家必须要掌握的方法，双指针迭代法运用非常广泛，特别适用于处理线性表，像反转链表、移动零、线性排序算法等等，都常常会用到双指针迭代。

解法2 是一种讨巧的办法，在工作中可以使用。但在面试中，如果用第二种方法可能会达不到面试官的考核目的，很大可能会被追问：“还有没有别的解法”，如果这个时候答不出其他的解法，可能会对面试结果产生影响。

代码示例（Python）：

# 普通方法：使用双指针遍历，交换两元素位置
def reverse_str(input_str):
    char_list = list(input_str)
    lens=len( char_list )
    i=0
    j=lens-1
    while i < j:
        tmp= char_list[i]
        char_list[i] = char_list[j]
        char_list[j]=tmp
        i+=1
        j-=1
    return ''.join(char_list)

# 切片法（Python） 
new_str = input_str[::-1]

---

3.1.20 统计字符串中每个字母出现的次数

【考点映射】

【出现频度】★★★☆

【难度】★★

【题目描述】

统计字符串s='I love python'中，每个字母出现的次数

【参考答案】

此题有三种解法：（Python版）

解法1：使用第三方库collections

解法2：利用字符串自带的count()方法进行字符统计

解法3：利用字典的特性来解题

代码示例（Python）：

# 给定一个字符串
s = 'I love python'

# 解法1：使用collections库中的Counter类去进行次数统计
from collections import Counter
d1 = dict(Counter(s))
# 结果：d = {'I': 1, ' ': 2, 'l': 1, 'o': 2, 'v': 1, 'e': 1, 'p': 1, 'y': 1, 't': 1, 'h': 1, 'n': 1}
# 假如说想要去掉空格的统计,只需要 d.pop(' ')即可，结果是：
# {'I': 1, 'l': 1, 'o': 2, 'v': 1, 'e': 1, 'p': 1, 'y': 1, 't': 1, 'h': 1, 'n': 1}

# 解法2：利用字符串自带count()方法进行字符统计
d2 = {}
for i in s:
    d2[i] = s.count(i)
# 结果：d = {'I': 1, ' ': 2, 'l': 1, 'o': 2, 'v': 1, 'e': 1, 'p': 1, 'y': 1, 't': 1, 'h': 1, 'n': 1}

# 解法3：利用循环和字典key不重复的特性，去统计字符
from collections import defaultdict
s = 'I love python'
d3 = defaultdict(int)
for i in range(len(s)):
    d3[s[i]] += 1
# 结果：defaultdict(<class 'int'>, {'I': 1, ' ': 2, 'l': 1, 'o': 2, 'v': 1, 'e': 1, 'p': 1, 'y': 1, 't': 1, 'h': 1, 'n': 1}) 

---