- 算法
- 题目
- 1.红黑树
- 2.基本排序算法汇总(桶排序,归并,快排,希尔,插入,选择,冒泡)
- 3.数组中出现次数超过一半的数字-Python版
- 4.求100以内的质数
- 5.无重复字符的最长子串-Python实现
- 6.通过2个5/6升得水壶从池塘得到3升水
- 7.什么是MD5加密，有什么特点？
- 8.什么是对称加密和非对称加密
- 9.如何判断单向链表中是否有环？
- 10.斐波那契数列
- 11.如何翻转一个单链表？
- 12.两数之和 Two Sum
- 13.搜索旋转排序数组 Search in Rotated Sorted Array
- 14.Python实现一个Stack的数据结构
- 15.写一个二分查找
- 16.set 用 in 时间复杂度是多少，为什么？
- 17.列表中有n个正整数范围在[0，1000]，进行排序；
- 题目
算法题直接刷leetcode即可
红黑树与AVL的比较：
AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；
红黑是用非严格的平衡来换取增删节点时候旋转次数的降低；
所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。
红黑树详解: https://xieguanglei.github.io/blog/post/red-black-tree.html
教你透彻了解红黑树: https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md
https://blog.csdn.net/mrlevo520/article/details/77829204 https://blog.csdn.net/stdio1916/article/details/90485867
归并排序
def merge_sort(arr1):
if len(arr1) < 2:
return arr1
half = int(len(arr1) / 2)
left_arr1 = merge_sort(arr1[:half])
right_arr1 = merge_sort(arr1[half:])
return merge(left_arr1, right_arr1)
def merge(left, right):
result = []
while left and right:
result.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
result.extend(left)
result.extend(right)
return result快速
def quick_sort(arr1):
if len(arr1) < 2:
return arr1
else:
pivot = arr1[0]
less = [i for i in arr1[1:] if i < pivot]
greater = [j for j in arr1[1:] if j >= pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)插入
def insert_sort(relist):
len_ = len(relist)
for i in range(1,len_):
for j in range(i):
if relist[i] < relist[j]:
relist.insert(j,relist[i])
relist.pop(i+1)
break
return relist冒泡
def bubble_sort(arr1):
for i in range(len(arr1)):
for j in range(len(arr1[1:])):
if arr1[i] < arr1[j]:
arr1[i], arr1[j] = arr1[j], arr1[i]
return arr1
# -*- coding:utf-8 -*-
class Solution:
def more_than_half(self, numbers):
# write code here
dict = {}
for num in numbers:
if num not in dict:
dict[num] = 1
else:
dict[num]+=1
if dict[num] > len(numbers)/2:
return num
return 0
class Solution(object):
def lengthOfLongestSubstring(self, s):
res = 0;i = 0; val = ""
for j in range(len(s)):
if s[j] not in s[i:j]:
res = max(res,j+1-i)
else:
i += s[i:j].index(s[j]) + 1
return res
# 快慢指针
class Solution(object):
def hasCycle(self, head):
if(head == None or head.next == None):
return False
node1 = head
node2 = head.next
while(node1 != node2):
if(node2 == None or node2.next == None):
return False
node1 = node1.next
node2 = node2.next.next
return True
def fib();
a, b = 0, 1
while true:
yield a
a, b = b, a+b
from itertools import islice
print list(islice(fib(), 5))
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 申请两个节点，pre和 cur，pre指向None
pre = None
cur = head
# 遍历链表，while循环里面的内容其实可以写成一行
# 这里只做演示，就不搞那么骚气的写法了
while cur:
# 记录当前节点的下一个节点
tmp = cur.next
# 然后将当前节点指向pre
cur.next = pre
# pre和cur节点都前进一位
pre = cur
cur = tmp
return pre
class Solution(object):
def twoSum(self, nums, target):
_dict = {}
for i, m in enumerate(nums):
if _dict.get(target - m) is not None:
return [_dict.get(target - m), i]
_dict[m] = i
def binary_chop(alist, data):
"""
非递归解决二分查找
"""
n = len(alist)
first = 0
last = n - 1
while first <= last:
mid = (last+first)//2
if alist[mid] > data:
last = mid - 1
elif alist[mid] < data:
first = mid + 1
else:
return True
return False
def binary_chop2(alist, data):
"""
递归解决二分查找
"""
n = len(alist)
if n < 1:
return False
mid = n // 2
if alist[mid] > data:
return binary_chop2(alist[0:mid], data)
elif alist[mid] < data:
return binary_chop2(alist[mid+1:], data)
else:
return True
if __name__ == "__main__":
lis = [2,4, 5, 12, 14, 23]
if binary_chop(lis, 12):
print('ok')
else:
print('false')