栈栈的应用–括号匹配问题括号匹配问题: 给一个字符串, 其中包括小括号, 中括号, 大括号, 求该字符串中的括号是否匹配
例如:
- (){}[] 匹配
- ([{}]) 匹配
- ([)] 不匹配
- ()) 不匹配
代码:12345678910111213141516171819def brace_match(s): stack = [] dic = {'(':')', '{':'}', '[':']'} for ch in s: if ch in {'(', '{', '['&#...
基数排序(1) 基数排序思路基数排序 (Radix Sort) 是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
基数排序法会使用到桶 (Bucket)，顾名思义，通过将要比较的位（个位、十位、百位…），将要排序的元素分配至 0~9 个桶中，借以达到排序的作用，在某些时候，基数排序法的效率高于其它的比较性排序法
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
从最低位开始，依次进行一次排序
从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
(2) 举几个小例子例1: 将一个数字例如345, 随意取出任...
希尔排序(1) 希尔排序思路
希尔排序是一种分组插入排序算法。
首先取一个整数d1=n/2, 将元素分为d1个组. 每组相邻量元素之间距离为d1, 在各组内进行直接插入排序;
取第二个整数d2=d1/2, 重复上述分组排序过程, 直到di=1. 即所有元素在同一组内进行直接插入排序
(2) 代码实现1234567891011121314def insert_sort_part(li, d): # 分组插入排序实现 for i in range(d,len(li)): tmp = li[i] j = i - d while j >= 0 and li[j] > tmp:...
归并排序1. 一次归并假设现在的列表分两段有序, 如何将其合成为一个有序列表选取两段列表,分成两段,然后一一比较比较完成,这便是一次归并
2. 一次归并算法实现12345678910111213141516171819def merge(li, low, mid, high): i = low j = mid + 1 li_tmp = [] while i <= mid and j <= high: if li[i] <= li[j]: li_tmp.append(li[i]) i += 1 if li[i] >= li[j]: li_tmp.ap...
堆
在学习堆排序之前,先必须了解一下什么是堆
堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。而二叉树中,父节点与左右孩子节点的编号下标都有一定的关系:其中父节点与左孩子节点的关系是 i -> 2i+1, 父节点与右孩子节点的关系是 i -> 2i+2
注: 这里指节点的下标关系
堆的向下调整性质假设: 节点的左右字数都是堆,但自身不是堆
当根节点的左右字数都是堆时,可以通过一次向下的调整来将其变换成一个堆
挨个出数9是堆中数字最大,将9取出,为保证完全二叉树,将树中最后...
剑指offer：二进制中1的个数(1) 运用Python函数代码详细:
12345def numberOf1(n): if n >= 0: return bin(n).count('1') else: return bin(n & 0xffffffff).count('1')
或者:12def numberOf1(n): return bin(n & 0xffffffff).count('1')
这里bin函数将数字转换为二进制,count为Python内置函数,计算1的个数
(2) 基础数据类型123456def co...
题目描述1234亚马逊是一家纳斯达克上市公司，通过其财报我们可以解读它在给定时期内的股票走势信息。这些信息包括每天交易的最高价、最低价以及开盘价。假定你作为交易员，必须在股票开盘时做出买入或卖出的决定。你负责设计一个算法，根据给定的股价走势信息，决定买入和卖出策略，该策略必须保证你的交易获得的利润最大化。假设S数组有以下9个数值[10,4,8,7,9,6,2,5,3]
1. 暴力枚举法1234567891011121314# S定义股票开盘价S = [10,4,8,7,9,6,2,5,3]maxProfit = 0buyDay = 0sellDay = 0# 暴力枚举for i in r...
排序(1) 取出一个数列中唯一一个奇数出现的数字例如:
li = [1,2,1,3,2,1,1,2,2,3,3]
唯一一个奇数出现的数字为3
代码详细:12345li = [1,2,1,3,2,1,1,2,2,3,3]num = 0for i in li: num = num ^ i #这里运用了一个异或符号的小技巧 当然只能在数列中只存在唯一一个数字才可使用print(num)
(2) 快速排序12345678910111213141516def quick_sort(li, left, right): if left < right: mid = partition(li, ...
说明排序算法是《数据结构与算法》中最基本的算法之一。
排序算法可以分为内部排序和外部排序
内部排序是数据记录在内存中进行排序。
而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
用一张图概括：
关于时间复杂度：平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序线性阶 (O(n)) 排序 基数...
1. 斐波那契数列简单的递归数列问题
(1) 蓝桥杯入门训练:Fibonacci数列问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn除以10007的余数。
说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。
样例输入
10
样例输出
55
样例输入
...
