python - 循环队列（数组下标） + 洗牌（随机数且不重复） + 检查数组重复

74 阅读 0 评论 49 点赞

我是靠谱客的博主笨笨台灯，最近开发中收集的这篇文章主要介绍python - 循环队列（数组下标） + 洗牌（随机数且不重复） + 检查数组重复，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题：

最近在学习算法方面的东西。目前可能会对算法进行罗列，现罗列循环队列和检查数组重复。

洗牌问题是某面试题。

解决方案：

用计算机求解现实问题，需要解决三个关键问题：

计算机求解数学模型的建立

人类语言描述的问题

数学模型的转换和算法设计

---

数据结构不仅要能在计算机系统内表达原始问题，还要有利于设计算法。

算法设计是对表达在定义好的数据结构上的数据的一系列操作和转换。

数据结构的定义要对这些操作和转换提供尽可能的便利。

---

讨论：

1、看上去局面不大，比较零散，可能需要一个大的背景问题来结合阐述会比较有效果。

2、复杂的算法，感觉都离不开递归。

# coding:utf-8

'''
算法的三个意义：
1-代码处理更一致，可能伴随浪费少部分资源，换来简单的处理体验；
2-代码行数更少，采用一种更高效的方式，体现高水准；
3-代码时间复杂度更低，一般是将O(n)降为O(lgn)，将O(n2)降为O(nlgn)，若n很大时，效果明显。
算法只针对代码，需要结合数据结构。
建模的方法有PPDCS，如何将模型落地？此时要用到数据结构，接着才有算法。
比如链表、栈、队列、决策树、深度优先、广度优先，先定义这些。因为这些是基础，是算法的开始。
结合具体的问题模型，选择合适的数据结构组合。
从算法的三个意义出发，完成并交付代码。
穷举所有的数据结构:
---
数据结构
链表：单双向链表，循环链表
队列：单双向队列
栈
大小顶堆
多叉树
排序二叉树

图论
DFS深度优先遍历
BFS广度优先遍历
最短路径问题
拓扑排序问题

字符串
字符串哈希
回文问题
子串问题

动态规划
背包问题
最长递增子串问题
---
穷举所有的算法：
...


'''

import os
import sys
import random

def find_repeat(list0, num):
    '''查找一个数组中相同数字的重复次数
    [0, 0, 3, 2, 1, 0, 0, 1, 2, 0]
    [0, 0, 0, 0]
    [5, 2, 2, 1]'''
    # list0 = []
    # for i in range(0, 10, 1):
    #     list0.append(random.randint(0, 3))
    # print list0
    # list1 = []
    # for i in range(0, 4, 1):
    #     list1.append(0)
    # print list1
    # for i in range(0, 10, 1):
    #     list1[int(list0[i])] += 1
    # print list1
    list1 = []
    for i in range(0, num+1, 1): # 需要浪费数组第0位
        list1.append(0)
    for i in range(0, len(list0), 1):
        list1[int(list0[i])] += 1
    print list1

def queue_ring(str0):
    '''环形队列'''
    list0 = list(str0)
    length = len(list0)
    list1 = []
    n = 10
    print list0
    for i in range(0, n, 1):
        list1.append(0)
    for i in range(0, length, 1):
        m = i % n # 环形队列的重点语句
        list1[m] = list0[i]
        print list1

def shuffle(n):
    '''
    返回n维数组，要求数组中每个数都不一样，且范围为1-n。
    '''
    list0 = []
    list0.append(random.randint(1,n))
    m = 1
    while(m != n):
        # print '***'
        flag = 0
        data0 = random.randint(1,n)
        # print data0
        if data0 not in list0:
            # print list0
            list0.append(data0)
            m += 1
        # for i in list0:
        #     if data0 == i:
        #         print i
        #         flag = 1
        #         break
        # if flag == 0:
        #     list0.append(data0)
        #     m += 1
    print list0
    return list0


if __name__ == '__main__':
    # find_repeat()
    str0 = '1234567890abcdefghijklmn'
    queue_ring(str0)
    # print complex(1, 2) + complex(3, 4)
    # print complex(1, 2) - complex(3, 4)
    # print complex(1, 2) * complex(3, 4)
    # print complex(1, 2) / complex(3, 4)
    num = 10
    # print shuffle(num)
    find_repeat(shuffle(num), num)

'''
['1', '2', '3', '4', '5', '6', '7', '8', '9', '0', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n']
['1', 0, 0, 0, 0, 0, 0, 0, 0, 0]
['1', '2', 0, 0, 0, 0, 0, 0, 0, 0]
['1', '2', '3', 0, 0, 0, 0, 0, 0, 0]
['1', '2', '3', '4', 0, 0, 0, 0, 0, 0]
['1', '2', '3', '4', '5', 0, 0, 0, 0, 0]
['1', '2', '3', '4', '5', '6', 0, 0, 0, 0]
['1', '2', '3', '4', '5', '6', '7', 0, 0, 0]
['1', '2', '3', '4', '5', '6', '7', '8', 0, 0]
['1', '2', '3', '4', '5', '6', '7', '8', '9', 0]
['1', '2', '3', '4', '5', '6', '7', '8', '9', '0']
['a', '2', '3', '4', '5', '6', '7', '8', '9', '0']
['a', 'b', '3', '4', '5', '6', '7', '8', '9', '0']
['a', 'b', 'c', '4', '5', '6', '7', '8', '9', '0']
['a', 'b', 'c', 'd', '5', '6', '7', '8', '9', '0']
['a', 'b', 'c', 'd', 'e', '6', '7', '8', '9', '0']
['a', 'b', 'c', 'd', 'e', 'f', '7', '8', '9', '0']
['a', 'b', 'c', 'd', 'e', 'f', 'g', '8', '9', '0']
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', '9', '0']
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', '0']
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
['k', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
['k', 'l', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
['k', 'l', 'm', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
['k', 'l', 'm', 'n', 'e', 'f', 'g', 'h', 'i', 'j']
[4, 7, 5, 2, 6, 9, 10, 3, 1, 8]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
'''