-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathalgorithm-comic.html
More file actions
249 lines (187 loc) · 13.3 KB
/
algorithm-comic.html
File metadata and controls
249 lines (187 loc) · 13.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
<!DOCTYPE html>
<html>
<head>
<!-- Document Settings -->
<meta charset="utf-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<!-- Page Meta -->
<title>Algorithm</title>
<meta name="description" content="学习的一些记录" />
<!-- Mobile Meta -->
<meta name="HandheldFriendly" content="True" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<!-- Brand icon -->
<link rel="shortcut icon" href="/assets/images/favicon.ico" >
<!-- Styles'n'Scripts -->
<link rel="stylesheet" type="text/css" href="/assets/css/screen.css" />
<link rel="stylesheet" type="text/css" href="//fonts.googleapis.com/css?family=Merriweather:300,700,700italic,300italic|Open+Sans:700,400" />
<link rel="stylesheet" type="text/css" href="/assets/css/syntax.css" />
<!-- highlight.js -->
<link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.3.0/styles/default.min.css">
<style>.hljs { background: none; }</style>
<!-- Ghost outputs important style and meta data with this tag -->
<link rel="canonical" href="http://localhost:4000//algorithm-comic" />
<meta name="referrer" content="origin" />
<link rel="next" href="/page2/" />
<meta property="og:site_name" content="Thinking" />
<meta property="og:type" content="website" />
<meta property="og:title" content="Algorithm" />
<meta property="og:description" content="学习的一些记录" />
<meta property="og:url" content="http://localhost:4000//algorithm-comic" />
<meta property="og:image" content="/assets/images/cover3.jpg" />
<meta name="twitter:card" content="summary_large_image" />
<meta name="twitter:title" content="Algorithm" />
<meta name="twitter:description" content="学习的一些记录" />
<meta name="twitter:url" content="http://localhost:4000//algorithm-comic" />
<meta name="twitter:image:src" content="/assets/images/cover3.jpg" />
<script type="application/ld+json">
{
"@context": "http://schema.org",
"@type": "Website",
"publisher": "Thinking",
"name": "Algorithm",
"url": "http://localhost:4000//algorithm-comic",
"image": "/assets/images/cover3.jpg",
"description": "学习的一些记录"
}
</script>
<meta name="generator" content="Jekyll 3.0.0" />
<link rel="alternate" type="application/rss+xml" title="Thinking" href="/feed.xml" />
</head>
<body class="home-template nav-closed">
<!-- The blog navigation links -->
<div class="nav">
<h3 class="nav-title">Menu</h3>
<a href="#" class="nav-close">
<span class="hidden">Close</span>
</a>
<ul>
<li class="nav-home " role="presentation"><a href="/">Home</a></li>
<li class="nav-about " role="presentation"><a href="/about">About</a></li>
<li class="nav-fables " role="presentation"><a href="/tag/fables">Fables</a></li>
<li class="nav-speeches " role="presentation"><a href="/tag/speeches">Speeches</a></li>
<li class="nav-fiction " role="presentation"><a href="/tag/fiction">Fiction</a></li>
<li class="nav-author " role="presentation"><a href="/author/casper">Casper</a></li>
<li class="nav-author " role="presentation"><a href="/author/edgar">Edgar</a></li>
<li class="nav-author " role="presentation"><a href="/author/abraham">Abraham</a></li>
<li class="nav-author " role="presentation"><a href="/author/martin">Martin</a></li>
<li class="nav-author " role="presentation"><a href="/author/lewis">Lewis</a></li>
</ul>
<a class="subscribe-button icon-feed" href="/feed.xml">Subscribe</a>
</div>
<span class="nav-cover"></span>
<div class="site-wrapper">
<!-- All the main content gets inserted here, index.hbs, post.hbs, etc -->
<!-- default -->
<!-- The comment above "< default" means - insert everything in this file into -->
<!-- the [body] of the default.hbs template, which contains our header/footer. -->
<!-- Everything inside the #post tags pulls data from the post -->
<!-- #post -->
<header class="main-header post-head " style="background-image: url(/assets/images/cover3.jpg) ">
<nav class="main-nav overlay clearfix">
<a class="blog-logo" href="/"><img src="/assets/images/ghost.png" alt="Blog Logo" /></a>
<a class="menu-button icon-menu" href="#"><span class="word">Menu</span></a>
</nav>
</header>
<main class="content" role="main">
<article class="post tag-test tag-content">
<header class="post-header">
<h1 class="post-title">Algorithm</h1>
<section class="post-meta">
<!-- <a href='/'></a> -->
<time class="post-date" datetime="2019-06-01">01 Jun 2019</time>
<!-- [[tags prefix=" on "]] -->
on
<a href='/tag/algorithm'>Algorithm</a>
</section>
</header>
<section class="post-content">
<p>«漫画算法»是一本偶然间发现的算法书，算是一份意外的收获吧。之前看到的很多书荐，买来都吃灰了也没翻过，这本算法书是第一次看完,小小总结一下。</p>
<p>这本书比较基础，算是入门级的算法书。主要讲解了基本的数据结构和排序算法，还有一些算法的实际应用。主要分为四部分。</p>
<ul>
<li>第一部分是算法的基本概述
<ul>
<li>衡量算法的复杂度方式，分别是时间和空间，同时列出了常遇到的时间复杂度的计算。</li>
</ul>
</li>
<li>第二部分是数据的结构构造
<ul>
<li>数据结构一般有物理结构和逻辑结构，物理结构是在内存中实际存在的结构，有数组和链表两种方式。数组对应查找多的比较有优势，链表对于修改比较多的有优势。链表反过来，对于查找不方便，但是对于插入，删除那些操作改动比较小。其实还有另外一种物理结构，这种是数组的变种-哈希表，这种数据结构主要是为了便于索引，通过对key值的一种计算，定位到数组中的下标去保存数据，这种对于数据的插入和查找都是比较方便的，基本是N(1)的时间复杂度。另外的逻辑结构就是栈，队列，树，图等存储结构。这些逻辑结构都可以用数组或链表这种物理结构来存储，但是作用不一样。栈是一种先进后出的逻辑，主要用来回溯用的。比如有递归逻辑的算法可以转化为用栈调用的方式，栈结构这种方式是为了把先前遍历过的数据用倒序的方式再取出来，类似历史的回溯，从金经历到现在，然后又从现在倒序，先清朝，到明朝，再到金的顺序。队列就不太一样了，队列是先进先出的一种结构，就是经过了那么多朝代，然后又按开始的那个朝代到现在再回放一次。栈和队列有两种比较实际的应用方式，栈用在二叉树的深度遍历上，因为栈需要按照遍历过的顺序再回退遍历另外一边，所以可以应用在这种场景。而队列是用在二叉树的广度遍历上，因为先前入队的元素需要按照顺序再次出来，然后又把出来那个元素的左右子树入队。</li>
</ul>
</li>
<li>第三部分是排序算法
<ul>
<li>主要有冒泡排序，快速排序，堆排序，基数排序和桶排序。对应的时间复杂度分别是O(n平方)，O(nlogn)，O(nlogn)，O(n + m)，O(n)。其中冒泡排序可以用变量去记录每轮是否存在交换，从而减少整体遍历的次数的方式去优化，还有另外可以通过每次遍历都是记录每轮遍历的边界值，然后下一轮遍历的时候可以少遍历些。快速排序也有两种方法，一种是双向遍历的方式，一种是单向遍历。堆排序是通过每次都移除顶点，然后再进行一次修复的过程，所以是O(nlogn)的操作。基数排序是用位相对位置的索引来记录数据出现的次数的算法，然后再按照出现的次数输入对应的数据，这种排序算法主要是用在数据分布比较均匀，相差不大的情况下的。如果相差比较大就要用到桶排序了。</li>
</ul>
</li>
<li>第四部分是面试时候遇到的算法问题
<ul>
<li>如何判断链表有环：有环代表可以用追及问题去记录环的节点数。可以设定两个指针，然后一直遍历，直到第一次相遇，然后继续行走，直到第二次相遇。</li>
<li>记录栈中最小值：这种是要添加另外一个栈来记录最小值，由于栈有后进先退的特点，所以单纯记录最小值还是不行的，还需要记录连续的最小值。可以假设栈底是最小的元素，然后遇到有比栈底小的元素就放入到最小栈中去，当栈中的最小数出栈时，对应的最小栈也要出栈。这种方式是为了在防止最小值出栈时没办法记录到下一个最小值的情况。</li>
<li>最大公约数：最大公约数用了另外一种技巧，是通过辗转相除或相减的方式去算。</li>
<li>如何判断一个数是否为2的整数次幂：2的整数幂转成二进制是高位为1，其它位为0的情况。这种数减1后变为二进制全为1，这时候与原来的数进行与运算，得出的结果如果是0，则表示那个整数是2的整数次幂。</li>
<li>无序数组排序后的最大相邻差：这种方式是利用基数排序算法排好序，然后统计0连续出现的个数最大的就是最大的相邻差。</li>
<li>如何用栈实现队列：这种算法的思想主要是用两个栈来实现，一个栈是用于正常的入队，在出队列的时候，由于需要先进先出，所以需要倒一下顺序，所以可以把第一个栈中的数据按顺序出栈，放到第二个栈中，这样顺序就倒过来了，这时候出队列就可以在第二个栈中出了。</li>
<li>如何求解金矿问题：金矿问题的最优解其实就是动态规划的问题。描述起来就是对于一个方案选择是先选择或者不选择时的最优解，然后逐层增加个数，逐渐选择最优的情况。</li>
<li>寻找缺失的整数：主要是运用到位运算来统计缺失了什么数，用到了一种常规的算法是分治法，这种方法是先分开，然后再求解。</li>
</ul>
</li>
<li>第五部分是算法的实际应用。
<ul>
<li>bitmap算法：位图元素是用来记录数据是否出现了，这种方式比较省内存，筛选数据比较容易</li>
<li>LRU算法：这种算法是为了在内存不够的情况下，可以去掉一些比较少用到的数据</li>
<li>A星寻路算法：这种算法是为了找到最短路径的算法</li>
</ul>
</li>
</ul>
</section>
</article>
</main>
<aside class="read-next">
<!-- [[! next_post ]] -->
<a class="read-next-story " style="background-image: url(/assets/images/cover3.jpg)" href="/ruby-rack">
<section class="post">
<h2>Ruby Middleware</h2>
<p></p>
</section>
</a>
<!-- [[! /next_post ]] -->
<!-- [[! prev_post ]] -->
<a class="read-next-story prev " style="background-image: url(/assets/images/cover3.jpg)" href="/rails-cookie-session">
<section class="post">
<h2>Rails Cookie Session</h2>
<p></p>
</section>
</a>
<!-- [[! /prev_post ]] -->
</aside>
<!-- /post -->
<!-- The tiny footer at the very bottom -->
<footer class="site-footer clearfix">
<section class="copyright"><a href="/">Thinking</a> © 2020</section>
<section class="poweredby">Proudly published with <a href="https://jekyllrb.com/">Jekyll</a> using <a href="https://github.com/jekyller/jasper">Jasper</a></section>
</footer>
</div>
<!-- highlight.js -->
<script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.3.0/highlight.min.js"></script>
<script>hljs.initHighlightingOnLoad();</script>
<!-- jQuery needs to come before `` so that jQuery can be used in code injection -->
<script type="text/javascript" src="//code.jquery.com/jquery-1.12.0.min.js"></script>
<!-- Ghost outputs important scripts and data with this tag -->
<!-- -->
<!-- Add Google Analytics -->
<!-- Google Analytics Tracking code -->
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-69281367-1', 'auto');
ga('send', 'pageview');
</script>
<!-- Fitvids makes video embeds responsive and awesome -->
<script type="text/javascript" src="/assets/js/jquery.fitvids.js"></script>
<!-- The main JavaScript file for Casper -->
<script type="text/javascript" src="/assets/js/index.js"></script>
</body>
</html>