Category: Algorithm

2018

Algorithm

求一个数组的波峰

三个月前有人问我一道有趣的算法题，当时想了很久才想出来，现在写篇博客记录一下。 给定一个很长的数组 arr，已知数组长度为 length 且 length >= 3，数组的第一个元素不比第二个元素大，最后一个元素不比倒数第二个元素大。求这个数组中 任意一个 波峰的数组下标。PS：不比前一个元素小且不比后一个元素小的元素称为波峰。 既然 arr[1] >= arr[0]，那么只要再满

2017

Algorithm

双向链表和哈希表实现 LRUCache

背景LRUCache 是一个很常用的缓存实现，本文会首先介绍一下 LRUCache 的定义，然后尝试用 Python 实现它。 定义LRUCache 首先是一个 Cache，那么对于一个 Cache 而言，肯定需要提供 get 和 set 两个方法，而且，这两个方法的时间复杂度越低越好，最好达到 O(1) 级别。 LRU 是 Least Recently Used 的缩写，近期最少使用策略。LRU

2016

Algorithm

简明数据结构

数据结构是一门重要的计算机基础课，知识点多且难度不小，这里整理了数据结构中比较容易遗忘的内容。 在这篇博客中，我尽量用我认为最容易理解的方式描述算法，力求简明扼要；相关代码可能不完整，如有兴趣欢迎访问我的 GitHub。 字符串快速匹配 - KMP 求解 next 数组（即部分匹配值） 123456789int q = 1, k = 0;next[0] = 0;for (q = 1; q &l

2015

Algorithm

使用二分法求整数幂

引言在实际应用中，求幂是一种常用的运算。那么在求幂时，我们是不是经常这样写： 1234567int power(int x, int n){ int result = 1; while (n--) result *= x; return result;} 这种写法简单直观，但时间复杂度较高。 解决思路为了降低时间开销，我们可以使用二分法。 举个