Dylan.K's Blog

阿德的个人博客

0%

发表于 更新于 分类于

思想

朴素的字符串匹配算法是从前到后连续的一个字符一个字符的比较判断是否一致，其时间复杂度为O(mn)，其中m为匹配模式的字符串长度，而n为待匹配的字符串长度。

KMP算法欲改进的就是在匹配时连续一个一个匹配会有做无用功的时候，可以跳过一些字符再比较。而可以跳过的字符通过计算匹配模式字符串的哪些前缀和后缀相同可得。

时间复杂度可以降为线性的O(m+n)。

代码实现

阅读全文 »

发表于 分类于

问题：找出数组中第i小的元素。

思想

采用“排序+索引”的方法，其时间复杂度依赖排序算法，为O(nlogn)，并非最有效的算法。

采用类似快速排序的算法思想来进行选择，可将时间复杂度在问题平均分布的情况下降为线性的O(n)。

不同于快排的是，在定位到中位并进一步递归查找时，不需要左右两边都递归调用，仅一边递归调用即可。

阅读全文 »

发表于 更新于 分类于

堆是一个数组，可以将其视为一个近似的完全二叉树。换言之，即将一维的数组以二维的二叉树结构形式来对待处理。

思想

在递增排序中，利用最大堆根节点为最大值的性质，每次取最大堆的根节点元素放到数组末尾，以此前推形成递增排序结果。

  • 首先构造初始最大堆
  • 交换最大堆的根节点元素与堆尾元素
  • 缩小堆规模
  • 重新调整最大堆

时间复杂度: O(nlogn)

构造初始最大堆时间复杂度为O(n)，每次重整最大堆的时间复杂度为O(logn)，n-1次重整最大堆时间复杂度为O(nlogn)，总时间复杂度为O(n)+O(nlogn)即为O(nlogn)。

阅读全文 »

发表于 更新于 分类于

1 采用分治法

思想

将数组划分为左右两部分，查找左半部分与右半部分的最大子数组 与 当前问题类似，采用递归即可。

主要问题集中如何解决“最大子数组出现在跨域左右两部分”的时候，此时仅需从中间位置向两边查找最大和的边界位置即可。

时间复杂度: O(nlogn)

实现代码

阅读全文 »

发表于 更新于 分类于

慢慢来，头绪很乱，让我慢慢说

2009年10月21日 09:40

我现在需要冷静，想说的话很多，很多，头绪很乱，就让我慢慢来，让我慢慢地说吧。

很多人问过我：怎么没有女朋友，为什么不去找，自己一个人多无聊啊。我说，我也不知道，也想不清楚，但如果我找到了，那么这个人将会是我娶进家门的人，是要过一辈子的人。我不想，也不喜欢玩弄情感。我很喜欢看那些电视剧，演绎一段轰轰烈烈的爱情，但我知道那些通常，或者大多情况下是不现实的。对我来说，只要她能幸福，能快快乐乐，就是我的幸福，我就知足了。所以我一直慢慢的找，慢慢的等。现在的人都太浮躁了，能耐得住性子的人很少。不过，呵呵，还是被我找到了，嘿嘿。

阅读全文 »

发表于 更新于 分类于

1 安装wget

1
sudo yum install wget

2 安装JDK

进入java官网下载jdk

https://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html

使用 jdk-8u191-linux-x64.tar.gz 

1
wget https://download.oracle.com/otn-pub/java/jdk/8u191-b12/2787e4a523244c269598db4e85c51e0c/jdk-8u191-linux-x64.tar.gz?AuthParam=1545469560_2e48f0e88b95e6414505d6bf5ff4cefb

或者 jdk-8u191-linux-x64.rpm 

1
rpm -ivh jdk-8u191-linux-x64.rpm
阅读全文 »

发表于 更新于 分类于

1 主从配置

以单机172.17.0.133为例

Redis master配置

编辑/etc/redis/6380.conf

1
2
3
4
5
6
7
8
bind 172.17.0.133
port 6380
pidfile /var/run/redis_6380.pid
logfile /var/log/redis_6380.log
dir /var/lib/redis/6380
maxmemory-policy noeviction
appendonly yes
appendfsync everysec
阅读全文 »

发表于 更新于 分类于

1 安装Ruby

Redis cluster的运行需要使用Ruby

1
2
3
4
5
6
7
8
9
10
11
12
wget https://cache.ruby-lang.org/pub/ruby/2.6/ruby-2.6.1.tar.gz

tar -zxvf ruby-2.6.1.tar.gz

cd ruby-2.6.1
./configure

sudo make

sudo make install

gem install redis
阅读全文 »