精华内容
下载资源
问答
  • 列表之开放定址

    万次阅读 2015-07-12 00:13:46
    列表之开放定址列表的基本操作 插入操作_INSERT 查找操作_SEARCH 删除操作_DELETE 散列表的探查方法probe methods 散列表探查的定义 线性探查 二次探查 双重散列 总结注意: 本文中所有的代码你可以在这里:...

    注意:
    本文中所有的代码你可以在这里:

    https://github.com/qeesung/algorithm/tree/master/chapter11/11-4/openAddressing(这里会及时更新)

    或者这里:

    http://download.csdn.net/detail/ii1245712564/8891141

    找到

    散列表之开放定址法

    在前面的文章中我们介绍过《散列表之链接法》,在链接法中,如果不同键值却将有相同的映射值,即有不同键值的元素却映射到散列表中的同一位置,那么就采用链表的方法,将映射到同一位置的元素插入到同一个链表之中,当需要删除, 查询元素时,只需要遍历该链表即可,链接法在最坏情况下删除和查询元素的时间代价为 O(n)

    今天我们来讲散列表中另外一种解决冲突的方法,那就是开放定址法(open addressing)

    假如你在外面旅游时,吃坏东西,急需上厕所,当你好不容易找到一件洗手间的时候,发现排了好多人,这时你会怎么做?

    • 如果是链接法:排队不就行了,我就在外面等,迟早会排到我的
    • 如果是开放定址法:直接放弃现有厕所,去寻找新的厕所

    没错,放弃已被占用的位置,寻找新的插入位置就是开放定址法的思想,开放定址法中的开放二字指的是没有被占用的位置,定址指的是确定位置。开放定址法中,所有的元素都放在散列表中(链接法放在链表中)。也就是说散列表中的每一个位置,要么有元素,要么没有元素。当需要删除,查询元素时,我们从某一个位置开始,按照某种特定的确定下一个位置的方法来检查所有表项,直到找到目标元素,或者没有找到。

    散列表的基本操作

    散列表有三种最基本的操作:

    • 插入元素:INSERT(ele)
    • 查询元素:SEARCH(k)
    • 删除元素:DELETE(ele)

    下面我们给出开放定址法散列表的定义

    template < class T >
    class OpenAddressingTable
    {
        public:
            typedef size_t (*Hash_Func_Type)( const T & , size_t , size_t);// [> 定义散列函数的指针 <]
            /* 描述表的一个位置的状态 */
            enum ELE_STATUS{
                EMPTY=0,// 空的
                DELETED=1,// 被删除的
                FULL=2 //有元素的
            };
            // ====================  LIFECYCLE     =======================================
            OpenAddressingTable (size_t array_size ,Hash_Func_Type _hash_func=NULL) ; /** constructor      */
            ~OpenAddressingTable ()                                                 ; /** destructor       */
            /** ====================  MUTATORS      ======================================= */
            bool hash_insert(const T & t)                    ; /*  向散列表中插入新的元素 */
            bool hash_search(const T & t , T & target) const ; /*  在散列表中查找键值 */
            bool hash_delete(const T & t)                    ; /* 在散列表中删除键值对应的元素 */
            void hash_clear();
    
        private:
            /** ====================  DATA MEMBERS  ======================================= */
            T * array_ptr                 ; /*  散列表的数组指针 */
            const size_t array_size       ; /* 散列表数组的大小 */
            ELE_STATUS * status_array_ptr ; /* 用于存放各个位置的状态信息*/
            Hash_Func_Type HASH           ; /* 采用的散列函数,这个函数用户也可以自己指定 */
    
    }; /** -----  end of template class OpenAddressingTable  ----- */
    
    #include "open_addressing.cc"
    #endif   /* ----- #ifndef OPEN_ADDRESSING_INC  ----- */

    插入操作_INSERT

    只要我们找到的位置没有元素在里面,那么表示这个位置可以插入新的元素

    /**
     *  插入一个元素
     *  @param t 要插入的元素
     */
    template < class T >
    bool OpenAddressingTable<T>::hash_insert (const T & t)
    {
        size_t i = 0;
        while(i!= array_size)
        {
            size_t j = HASH(t , i , array_size); // 取出位置
            if(status_array_ptr[j] != FULL) // 判别元素是否是开放为空的
            {
                array_ptr[j] = t;   //插入元素
                status_array_ptr[j] = FULL;//并将该位置状态设为已经被插入
                return true;
            }
            ++i;
        }
        std::cerr<<"hash table overflow"<<std::endl;
        return false;
    }       /** -----  end of method OpenAddressingTable<T>::hash_insert  ----- */

    查找操作_SEARCH

    查找操作和插入操作比较类似,查找操作是要找到有非空位置,并判断是否是目标元素,当遇到为EMPTY的时候,说明之后元素也不必再检查,因为后面已经没有元素了

    /*
     * 查找元素
     * @param t      要查找的键值
     * @param target 返回找到的目标
     */
    template < class T >
    bool OpenAddressingTable<T>::hash_search (const T & t , T & target) const
    {
        size_t i = 0;
        while(i != array_size)
        {
            size_t j = HASH(t , i , array_size) ;
            if(status_array_ptr[j] == EMPTY) // 之后就再也没有元素了
                return false;
            else if (status_array_ptr[j] == FULL)
            {
                if(array_ptr[j].key == t.key )  
                {
                    target = array_ptr[j];
                    return true;
                }
            }
            ++i;
        }
        target = T();
        return false;
    }           /** -----  end of method OpenAddressingTable<T>::hash_search  ----- */

    删除操作_DELETE

    删除操作和上面两个操作也比较相似,但是有一点需要注意,那就是已删除元素的散列表位置不能标记为EMPTY,而是要标记为DELETED,因为在查找操作中是以EMPTY作为探查的终止,如果标记为EMPTY,那么在被删元素之后的那些元素就会丢失

    
    template < class T >
    bool OpenAddressingTable<T>::hash_delete (const T & t)
    {
        size_t i = 0;   
        while(i !=array_size)
        {
            size_t j = HASH(t , i , array_size);
            if(status_array_ptr[j] == EMPTY)
                return false;
            else if (status_array_ptr[j] == FULL)
            {
                if(array_ptr[j].key == t.key )  
                {
                    status_array_ptr[j] = DELETED;// 不应该是EMPTY
                    return true;
                }
            }
            ++i;
        }
        return false;
    }       /** -----  end of method OpenAddresingTable<T>::hash_delete  ----- */

    散列表的探查方法(probe methods)

    上文提到,我们从某一个位置开始,按照某种特定的确定下一个位置的方法来检查所有表项,而这种特定的确定下一个位置的方法就是我们这里的探查方法。

    在进入正题前,我们首先来看两个问题:

    问题一:为什么需要探查?

    回答一:前面我们讲过,开放定址法在一个位置被占用时,就会去寻找下一个新的位置,那这个找的方法也不是乱找。那么就需要按照一定的查找规律去一个一个的探查。


    问题二:什么样的探查才算是一个好的探查?

    回答二:一个好的探查一定是可以等可能的探查散列表中的所有表项的,每个关键字的探查序列等可能的为 <0,1,2,...,m1> <script type="math/tex" id="MathJax-Element-2"><0,1,2,...,m-1></script>的 m! 种排列中的一种。但是这种探查只是理想化的,我们只能做到尽可能的趋近。

    散列表探查的定义

    为了使用开放定址法插入一个元素,需要连续的检查散列表,直到找到一个新的空槽来放置带插入的元素为止。检查的顺序不一定是0,1,2,…,m-1的这种顺序,而是要依赖待插入的关键字key,为了确定探查哪些槽,我们将散列函数加以扩充,使之包含探查号作为第二个输入参数,于是散列函数就定义为:

    h:U×{0,1,2,...,m1}{0,1,2,...,m1}

    对于每一个关键字 k ,使用开放定址法得到的探查序列<h(k,0),h(k,1),...,h(k,m1)>都是 {0,1,2,...,m1} 的一个排列。

    在下面我们将介绍三种探查的方法,这三种探查的方法都能保证每一个关键字的探查序列都是 {0,1,2,3,...,m1} 的一个排序,但是并不能做到等可能的为 {0,1,2,3,...,m1}m! 排列中的一个。

    线性探查

    给定一个辅助散列函数 _h:U{0,1,2,...,m1} ,那么线性探查的散列函数为:

    h(k,i)=(_h(k)+i) modm,  i=0,1,2,...,m1

    首先我们探查 HashTable[_h(k)] modm 位置,如果发现已经被占用,那么就探查 HashTable[_h(k)+1] modm ,如果也被占用了,那么就探查 HashTable[_h(k)+2] modm ,以此类推,直到找到合适的位置,或者探查了 m 次以后到位置HashTable[_h(k)1] modm,那么探查停止。

    /**
     * 辅助散列函数
     * @param t          要插入的元素
     * @param array_size 散列表的大小
     */
    template < class T >
    size_t _hash (const T & t , size_t array_size) 
    {
        return t.key%array_size;
    }       /** -----  end of method OpenAddressingTable<T>::_hash  ----- */
    
    /**
     * 线性探查  
     * @param t           要插入的元素
     * @param offset      探查号
     * @param array_size  散列表大小
     */
    template < class T >
    size_t linear_probing (const T & t, size_t offset , size_t array_size) 
    {
        return (_hash(t , array_size)+offset)%array_size;
    }       /** -----  end of method OpenAddresingTable<T>::linear_probing  ----- */

    举个栗子:
    假设现在有大小为 5 的散列表,现在要插入三个元素{a1(key=0),a2(key=1),a3(key=5)}到散列表中

    Alt text

    插入 a1 , h(0,0)=0 ,位置 0 为空,可以直接插入

    Alt text

    插入a2, h(1,0)=1 ,位置 1 为空,可以直接插入

    Alt text

    插入a3,首先探查好 h(5,0)=0 ,发现位置 0 已有元素,那么接下来探查h(5,1)=1,发现位置 1 也有元素了,于是继续探查h(5,2)=2, 2 位置为空,可以插入

    Alt text

    可能你也发现上面的问题了,如果我们要查找a3,那么就要经过一个 a1 , a2 的探查,其中 a1 a3 的辅助散列值相同,要经过 a1 的探查还算是情有可原,但是 a2 a3 基本算是无关元素,我要找 a3 ,还要探查一次 a2 ,这样未免也太慢了,而且随着插入的元素越来越多,将会探查的不相关的元素就越来越多,连续被占用的糟会越来越长,那么效率就越来越低,这种问题称为一次群集线性探查一次群集最为严重探查方法,我们可以使用下面两种更为巧妙的探查方法来避免一次群集

    二次探查

    二次探查相对于线性探查来说,在散列函数中添加了一个二次项:

    h(k,i)=(_h(k)+c1i+c2i2) modm

    其中 h 是一个辅助散列函数, c1 , c2 为正常的辅助常数,初始的探查位置是 _h(k) modm 虽然 二次探查不存在像 线性探查哪样的严重群集,但是还是存在一定的群集现象,该群集现象称为 二次群集

    /**
     *  二次探查
     */
    template < class T >
    size_t quadratic_probing (const T & t , size_t offset , size_t array_size) 
    {
        return (_hash(t , array_size)+offset*offset)%array_size;
    }       /** -----  end of method OpenAddressingTable<T>::quadratic_probing  ----- */
    

    双重散列

    双重散列是用于开放定址法的最好的探查方法之一,因为双重散列对于任何一个键值来说,得到的探查序列都是足够随机的,双重散列采用下面的散列函数:

    h(k,i)=(h1(k)+ih2(k)) modm

    其中 h1 h2 分别是两个辅助散列函数,起始的散列表项为 h1(k) modm

    有一个散列函数就已经够头疼的了,现在还多了一个新的辅助散列函数,为了能查找整个散列表,值 h2(k) 必须要与散列表的大小 m 互素。有一种简便的方法可以保证这个条件成立,就是取m为2的幂,并设计一个总产生奇数的散列函数 h2 。另一种方法是取 m 为素数,并设计一个总产生比m小d额正整数的函数 h2

    比如在我们去 m 为一素数的时候,我们可以讲散列函数设计如下

    h1(k)=k modm,h2(k)=1+k mod(m1)

    /**
     *  双重散列的第二个辅助函数
     */
    template < class T >
    size_t _hash1 (const T & t  , size_t array_size) 
    {
        return (1+t.key%(array_size-1));
    }       /** -----  end of method OpenAddressingTable<T>::_hash1  ----- */
    
    
    /**
     *  双重散列
     */
    template < class T >
    size_t double_hashing (const T & t , size_t offset , size_t array_size) 
    {
        return (_hash(t , array_size)+offset*_hash1(t , array_size))%array_size ;
    }       /** -----  end of method OpenAddressingTable<T>::double_hash  ----- */

    总结

    开放定址法的所有元素都存在于散列表之内,每一个表项要么存在元素,要么就为空,当发生映射值冲突的时候我们可以探查新的位置。最好的探查方法是双重散列,因为双重散列产生的探查序列足够随机,不像线性探查二次探查哪样存在较为严重的群集现象。

    开放定址法相对于链接法来说,可以将存储链表指针的内存空出来存储更多的数据,直接跳过了指针的操作,而是用数组的直接访问来访问元素,但是如果探查散列函数设计差劲的话,将会严重拖慢散列表的速度!

    展开全文
  • Jupyter 使用列表实现筛选求素数 使用列表实现筛选求素数可以极大的提高计算机的运算速率。 maxNumber = int(input("请输入一个大于2的自然数:")) lst = list(range(2,maxNumber)) #最大整数的平方根 m = int...

    Jupyter 使用列表实现筛选法求素数

    使用列表实现筛选法求素数可以极大的提高计算机的运算速率。

    maxNumber = int(input("请输入一个大于2的自然数:"))
    lst = list(range(2,maxNumber))
    #最大整数的平方根
    m = int(maxNumber**0.5)
    for index , value in enumerate(lst):
        #如果当前数字已大于整数的平凡根,结束判断
        if value > m:
            break
        #对该位置之后的元素进行过滤
        lst[index+1:] = filter(lambda x : x%value !=0,lst[index+1:])
    print(lst)
    

    运行结果:

    在这里插入图片描述

    展开全文
  • 我们有些时候需要把两个列表合成一个元组列表。比如把[x,y,z] [1,2,3]合并成[(x,1),(y,2),(z,3)]。如果不嫌麻烦,我们可以使用for循环的方法来实现: list1 = ['x','y','z'] list2 = [1,2,3] list_m = [] for i in ...

    我们有些时候需要把两个列表合成一个元组列表。比如把[x,y,z] [1,2,3]合并成[(x,1),(y,2),(z,3)]。如果不嫌麻烦,我们可以使用for循环的方法来实现:

    list1 = ['x','y','z']
    list2 = [1,2,3]
    list_m = []
    for i in range(len(list1)):
    	tuple_temp = (list1[i],list2[i])
    	list_m.append(tuple_temp)
    print(list_m)
    

    这样就用面向过程的方法实现了这个功能,运行结果如下:

    [('x', 1), ('y', 2), ('z', 3)]
    [Finished in 0.5s]
    

    那么python中有没有这样的方法可以直接生成呢?答案是有的,这里就要用到zip(打包)函数,它是python的一个内置函数,用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表。如果使用dict方法,还可以生成字典,这个字典的键为第一个列表中的元素,值为第二个列表中的元素。

    list1 = ['x','y','z']
    list2 = [1,2,3]
    list_m = list(zip(list1,list2))
    list_d = dict(zip(list1,list2))
    print(list_m)
    print(list_d)
    

    结果如下:

    [('x', 1), ('y', 2), ('z', 3)]
    {'x': 1, 'y': 2, 'z': 3}
    [Finished in 0.8s]
    

    python用zip方法将两个单元素列表合并(打包)为一个元组(元素对)列表或者字典

    展开全文
  • 场景剖析需求问题

    千次阅读 2017-03-08 18:28:26
    场景来测试需求是指模拟特定场景边界发生的事情,通过事件来触发某个动作的发生,观察事件的最终结果,从而用来发现需求中存在的问题。我们通常以正常的用例场景分析开始,然后再着手其他的场景分析。  下面来...

    场景主要包括4种主要的类型:正常的用例场景,备选的用例场景,异常的用例场景,假定推测的场景。用场景法来测试需求是指模拟特定场景边界发生的事情,通过事件来触发某个动作的发生,观察事件的最终结果,从而用来发现需求中存在的问题。我们通常以正常的用例场景分析开始,然后再着手其他的场景分析。

      下面来看具体的例子:假设你现在需要完成的是一套出租车预定系统(顾客进行出租车的预定,系统完成扣款以及出租车司机的任务分配等相关的任务: 顾客中的大部分都是在出租车租赁公司立有相关存款账户的用户,他们一般通过电话的方式进行预约,有些是要求立马预定的,也有一些是预定几周后的,我们需要使用计算机系统来确保这些存款账户到目前为止是有效的,系统需要知道什么时候顾客需要出租车,以及接送地址和他们的目的地。接送地址一般来说是顾客账户信息上填写的地址,根据我们车辆调度员的经验,我们可以告诉顾客最佳的接送时间。系统会根据订阅情况产生一个司机工作编号并记录预定过程中的详细信息,并会根据接送时间的顺序对这些信息按照接送的时间进行排序,然后会给顾客一个订阅的确认信息,同时包括司机的工作编号)。与这个预定出租车用例相关的,就是给出租车司机分配具体工作的用例。用场景法来对这个需求进行测试,应该如何进行呢?

      首先我们来看一下正常用例场景的构建过程

      a.识别商业事件流:发现需求的过程包括研究和调查特定需求相关的业务规则和策略,调查包括一系列的业务事件以及商业规则的边界点。业务事件包括事件名,输入数据(由这个事件引起的输入数据),输出数据(为了响应这个事件产生的输出数据)

      b.画一个非正式的商业场景草图

      c.把这个场景草图形成场景的具体步骤

      以顾客预定出租车为例,这个事件是在当顾客决定需要一个出租车时发生的,这个事件导致客户和出租车公司之间发生一个预定请求的交互动作,当出租车公司收到预定请求时,它触发了安排出租车登记事件用来响应这个需求,从分析得出其中有一个需求是出租车公司需要提供一个预定确认响应信息给顾客的过程,那么什么是预定确认,在什么情况下这个确认信息会产生,其他与之相关的需求是什么?下面我们就通过构建场景的方式来进行细节上的分析

      a.事件源:顾客想预定出租车,发出出租车预定请求

      事件结果:安排出租车预定行为(包括许多商业逻辑规则),发送一个出租车预定确认信息给顾客

      事件名: 顾客想要预定出租车

      输入数据: 出租车预定请求

      输出数据:出租车预定确认响应

      b.场景草图如下:

      

      c.结构化场景:

      1.第一步 顾客告诉我们他想预定出租车

      2.调度员需要知道顾客的账户号码,那么他是否也需要知道顾客的账户姓名?调度员是否需要询问乘客的姓名?

      3.调度员核实账户号及支付信息的有效性,那是否也需要核对账户姓名的有效性?(关注衍生信息有效性的检查)

      4.调度员需要向顾客询问接送的日期,时间,地址和目的地

      5.调度员需要告诉顾客最佳的接送时间

      6.调度员分配一个工作接送号给司机,那这个工作号是从哪里产生的?(关注数据从哪里产生)

      7.调度员记录所有预约工作的细节

      8.调度员跟顾客确认订阅的详细信息

      场景模型基本上就是这样,预约出租车正常的用例场景如下:

      1.1 客户打电话到出租车公司预约出租车

      1.2 出租车调度员询问账号号码以及账号的姓名

      1.3 出租车调度员核实顾客的账号详情以及支付的方式

      1.4 调度员询问接送的地址,预定的接送时间以及目的地

      1.5 调度员告诉顾客最佳的接送时间

      1.6 调度员分配预定的工作号给出租车司机

      1.7 调度员记录详细的预定信息

      1.8 调度员反馈预定成功的确认信息给顾客

      备选的用例场景:从基本流开始,在某个特定条件下执行,然后重新加入基本流

      发现备选流的方法:对正常用例场景中的每一步列出一份问题检查列表:

      — 这一步是否如实按照规定的发生?

      — 对于描述中每一个名词,动词我们是否都知道精确的含义?—是否有任何数据上的遗漏?

      — 是否存在一些主观上的判断?

      — 我是否已经做了所有的假设?

      — 这么做是否真正有意义?

      备选用例场景分析如下:

      1.1 顾客打电话告诉我们他想预定出租车,那么顾客是一个个人还是一个组织?顾客是否经常通过电话进行交流?顾客是想预约一辆出租车还是可能会预约多辆出租车?

      1.2 出租车调度员向顾客询问账号号码,姓名以及乘客的姓名,是否只有调度员询问顾客还是有其他人也一起来询问?顾客是否都在出租车租赁公司有一个账号?是否可能会出现多个乘客的姓名?通过问这一系列问题,将会发现顾客未必都会有一个账号的,乘客也可能是多个,这样你就能构建一个备选流的用例场景了

      备选的用例场景一:

      1.3 预约出租车,顾客没有存款帐号

      出租车调度员询问顾客有关乘客的姓名和帐户信息

      出租车调度员核对客户的帐户信息

      出租车调度员增加“无账号”信息到预约详细信息中

      异常用例场景:异常用例是指当错误发生或者一个不需要的处理条件发生了

      发现异常用例场景的方法:

      — 什么样的数据条件将会导致这一步不能继续处理?

      — 什么样的历史数据将会导致这一步不能继续处理

      — 什么样的人为行为将会导致这一步不能继续处理

      异常用例场景分析如下:出租车调度员核实顾客的账户信息和支付方式,如果出租车调度员发现顾客提供了错误的账户信息将会发生什么?顾客的帐户支付方式过期了怎么办?如果顾客账号在预先约定好的时间内未进行及时支付将会怎么样?

      假定推测场景:以正常的用例场景作为起点,对每一个步骤鉴别约束条件:如果约束条件不存在的话,将会发生什么?

      假定推测场景分析如下:

      1.1 顾客打电话告诉我们要预定一辆出租车:其中一个约束就是顾客用电话联系,如果移除这个约束,顾客将会通过什么样的方式来联系?一个很明显的方式就是通过网络,也有可能是通过旅行社代理订购,或者是出租车的代金券,如果改用信用卡支付会是怎样的等等。一旦移除了约束,你就可以进行头脑风暴了,思考各种可能的情况,这样就可以发现更多需求中遗漏的点。

      总之,通过找出所有与业务流相关的过程,以及与这些过程相关的数据,观察文本之间的关联性,过程之间的依赖性,就能帮助你暴露更多需求方面的问题。大家赶紧去试试吧,相信能给你带来不一样的感受!

    展开全文
  • C语言递归实现数组逆序排列

    千次阅读 2019-09-23 13:12:42
    //C语言递归实现数组逆序排列 #include<stdio.h> #define N 7 int *reverse(int *a,int *b) { if(*a==0) return a ; reverse(a+1,b-1); *b=*a; } main() { int i; int static a[]={1,2,6,4,5,3,7},b...
  • 提出一种新方法scratch编写游戏-数字华容道。该仍然采用克隆,每个克隆体有25个造型。所有克隆体不移动,改变造型方法实现数字重新排列。
  •  之前老师就讲过了选择和冒泡,之后又提到了插入和排序,今天做了一个小DEMO,对比了一下四种方法的效率,当然看了很多大牛也博客,其实算法还设计了时间复杂度和空间复杂度,对于这两个概念,我只能从表面...
  • 散列(hash、关键字地址计算)

    千次阅读 2016-08-06 14:04:19
    散列,又称为hash或者关键字地址计算。时间复杂度为0(理想情况下),是一种key-value的存储方法。核心就是由hash函数决定关键字值和散列地址之间的关系,通过这种关系来组织存储并进行查找等操作。散列面临的...
  • 在Python中怎样用列表实现字典? 用列表实现字典最大的问题就是解决hash冲突,如果在列表中通过计算不同的key得到相同的相同了位置,这时候应该怎么办? 最简单的办法就是使用拉链. 拉链:就是在一个列表中每个位置...
  • 笔记本(用于)高效15法则 谷歌、苹果都在的深度工作凯文·克鲁斯(Kevin Kruse)第一章 数字1440的力量标注 (黄色) - ◎我是如何打败“岁月神偷”的 > 位置 190我 创造 了 一种“ 美元 每分钟” 的 分析 模式, ...
  • 关于散列表

    2015-03-24 20:35:26
    我一直只知道散列表,才知道散列表其实就是哈希表===怂~~~ 下面给出散列表的教程吧 散列表的概念 注意:  ①由同一个散列函数、不同的解决冲突方法构造的散列表,其平均查找长度是不相同的。  ②散列表的平均查找...
  • python递归找出列表中最大的数字

    千次阅读 2020-09-17 21:54:27
    # 设一个默认值,与列表里的值比大小,谁大留谁,依次递归,最后留下的就是最大值。 if len(list) >= 3: if list[0] <= list[1]: return maxList(list[1:]) else: num = list[0] list = list[2:] list...
  • 列表 基本概念

    千次阅读 2016-06-17 09:27:50
    列表列表 又叫 哈希表 (hash table)。通过访问key而直接访问存储的value值。它的key - value之间存在一个映射函数,我们可以通过key值和“看不到”的映射函数(散列函数)访问对应的value值。这加快...
  • 列表详解

    2019-11-17 12:40:54
    列表详解哈希函数和哈希值哈希碰撞拉链线性探测 哈希函数和哈希值 如果我们存储一些数据(以键值对的形式存储, 键为数字), 怎样能够让我们的查询速度达到最快呢? 我们如果顺序查找, 那时间复杂度就是O(n)O(n)...
  • 已知info=[1,2,3,4,5],两种方法,把列表变成info=[5,4,3,2,1] 算法源码 ##方法一 info=[1,2,3,4,5] info.reverse() ##列表里的倒置函数 print(info) ##方法二 info=[1,2,3,4,5] info[::-1] ##切片 print(info...
  • 表驱动

    千次阅读 2019-03-25 23:06:51
    表驱动: 一种编程模式,从表里面查找信息而不使用逻辑语句(if、case)。事实上,凡是能通过逻辑语句来选择的事物,都可以通过查表来选择。对简单的情况而言,使用简单的逻辑语句更为容易和直白,但随着逻辑链的...
  • 方程组求解的直接与迭代实现

    千次阅读 2018-12-14 20:25:01
    方程组求解的直接与迭代实现 问题描述 我们的目的在于求解如下所示的方程组: 其中的A11、A12、A21、A22A_{11}、A_{12}、A_{21}、A_{22}A11​、A12​、A21​、A22​以及右端项fff以不同的的稀疏存储方式存在...
  • 需求分析

    千次阅读 2019-01-18 17:36:37
    1. 5W1H分析 很多需求提出者不了解系统,他们只关心当前问题是否能够解决,PM必须详细了解需求的来龙去脉,以便能提出解决方案。在此推荐5W1H分析,用来收集需求内容。 (1)What(描述) 需求是什么? ...
  • 康奈尔笔记

    千次阅读 2014-08-10 16:43:14
    书写课堂笔记是为考试做准备的各种途径中一件十分耗时的方式,下周我将在课堂上采用8年来第一次使用的新的笔记策略:康奈尔笔记,他将帮助从密密麻麻的笔记本中解脱出来。 1、按照康奈尔笔记区划你的笔记 ...
  • LeetCode--回溯心得

    千次阅读 2018-12-08 12:50:09
    这两天在刷LeetCode37题解数独时,被这个回溯折腾的不要不要的,于是我疼定思疼发誓一定要找个能解决这类回溯的套路出来,方便以后快速解决此类题目。于是我在网上找了两个很经典的回溯题目--八皇后问题和迷宫...
  • 列表

    2012-06-05 10:20:16
    列表 搜索关键词:散列函数、散列表、哈希函数、哈希表、Hash函数、Hash表 散列方法不同于顺序查找、二分查找、二叉排序树及B-树上的查找。它不以关键字的比较为基本操作,采用直接寻址技术。在理想...
  • 毗邻目录: 这种方法说白了就是子类,依赖父类,父类依赖爷爷类,爷爷类可以有多个儿子类,跟父类平级的类。一层一层的。 预排序历遍: 这种算法比较高端,使用的是mysql官方推荐的左右算法。 使用场合...
  • 列表查找

    千次阅读 2013-09-21 19:49:53
    哈希表(hash)又称散列表,是除顺序表存储结构、链表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。设要存储的对象为n个,在内存中长度为m的连续存储单元,对象的关键字key为索引... 那么怎么样才是好的h
  • 机器学习-sklearn网格搜索

    千次阅读 2017-06-18 20:48:11
    网格搜索可以用来寻找合适的参数,尝试所有可能的参数组合。sklearn提供的GridSearchCV类,可以通过字典来提供分类器或回归器的类型对象。字典的键我们将要调整的参数,而字典的值就是需要尝试的参数值的相应列表...
  • 列表查找失败时的平均查找长度

    千次阅读 2021-01-14 20:54:40
    在利用线性探测再散列处理冲突的散列表中,很多人对计算失败时的平均查找长度,作除数应该是散列表长,还是散列函数:mod后面的数不清楚,首先接下来我们先解决这一问题. 问题一:其除以的数是mod后面的数还是散列表长? ...
  • 其中包括梯度,牛顿,拟牛顿(DFP/BFGS),约束变尺度(SQP),Lagrange乘子,信赖域等。 算法原理及简单推导 最速下降(梯度下降)  借助 梯度 ,找到下降最快的方向,大小为最大变化...
  • 在上面的例子中,我想查看Josh的rss feed列表,但是我又不想让他知道是我看的。我会大概每分钟左右发出一个请求 * * * * * wget -nc -nd http://www.willhackforsushi.com/subscriptions.xml 来监视这个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 57,282
精华内容 22,912
关键字:

怎样用列表法