Tag: 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;

2015

Algorithm

使用二分法求整数幂

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