本文共 6187 字,大约阅读时间需要 20 分钟。
武汉加油,中国加油。希望疫情早日结束。
由于疫情,二狗寒假在家不能到处乱逛,索性就在家里系统的刷一下算法的内容,一段时间下来倒也有些小小的收获。只是一来家中的小破笔记本写起博客来实在不是很顺手,二来家中吃喝玩乐的诱惑也不少了,就连着几天没有更新,惭愧惭愧。看来2020年还是要加强自己计划的执行能力。
每个人都有适合自己的学习方式。虽然也挺喜欢看书,但对我来说,在学习新内容,不熟悉的内容的时候单纯的啃课本还是有些事倍功半,尤其是像算法这种这么容易看得一脸懵逼的内容。大名鼎鼎的《算法导论》买回来了挺长时间了,只看了感兴趣的几章,并且在看得时候经常怀疑自己,我是不是脑子不行啊,要不转行算了(苦笑)。基于之前学习数据库的经验,趁着寒假整了个算法的音频课程听了一下,感觉还不错,恩,看来我比较适合这种方式吧。以后再要学习什么新东西的时候记得提醒自己,先选对了学习的方式哈。
女朋友问我,算法是什么,学这个有啥用? 其实之前我也没有想明白,最开始从leetcode刷题目的很简单,多长点见识,万一面试用上了呢。所以女朋友这么问的时候我就随口一胡扯:武功知道吧,之前的实战经验算是身法,这玩意儿(算法)是心法。现在对这个抖机灵的回答还有点小骄傲,我还挺机智的呀。可不是嘛,各种常见的数据结构,常见的算法,各大高级语言都帮我们实现好了,大家日常“CRUD”哪里用得上这些啊?但其实也不对,比如两种数据结构都可以做的时候,哪种更合适呢?如果想效率更高呢?如果必须要在限制的空间内完成呢?或者接地气一点:和同事关于内容battle的时候,怎么优雅地说服他呢?
来点干货:
反正博客写给自己看,记录一下这两天笔记中让我有耳目一新的感觉的内容吧。
数组:
- 数组是一种线性表数据结构。它用一组连续的内存空间,存储一组具有相同类型的数据,最大的特点是支持随机访问。
- 根据下标来随机访问数组中的元素,所以数组这种结构的”查找“其实很高效。
- 又因为它是连续存储的,所以相对来说,”插入“和”删除“这两个操作会比较低效。因为这两个操作很有可能使得数组内大量元素重新移动位置。
- 因为是连续的内存空间,所以如果内存中剩下一个40m的内存块,一个60m的内存块,其实是无法申请一个80m大小的数组的。但是链表可以。
链表:
- 与数组相反,链表不需要连续的内存,它通过”指针“来将一组零散的内存块串起来使用。所以上面数组中的那种情况,链表是可以完成的。
- 相对数组来说,链表的”插入“和”删除“会高效很多,毕竟只要改变相关联的指针的指向即可。
这两种数据结构实在是太基础了,基础到基本不会用到。拿二狗子来说,如果有类似的东西需要实现的话我会怎么做呢,我会申请一个List出来,剩下的都交给List去做了。但看看上面两中数据结构的比较,其实差别还是挺大的。而关于List,写这篇博客的时候我又去微软官方文档瞅了一眼:
- List<T>类是 ArrayList<T>类的泛型等效项。 它通过使用大小根据需要动态增加的数组来实现IList<T>泛型接口。
-
在决定是使用List<T> 还是 ArrayList类(两者都具有类似的功能)时,请记住List<T> 类在大多数情况下性能更佳并且是类型安全的。 如果引用类型用于 List<T>类的类型
T
,则这两个类的行为是相同的。 但是,如果将值类型用于类型T
,则需要考虑实现和装箱问题。 - 如果值类型用于类型
T
,则编译器将为该值类型专门生成 List<T>类的实现。 这意味着,在使用元素之前,不需要对 List<T>对象的 list 元素进行装箱,在创建了大约500个列表元素后,不会对其进行装箱的内存列表元素大于用于生成类实现的内存。
看来,List应该是用数组来实现的,并且.net有一些特殊的处理使得这家伙既安全,又高效。至于第三条,看来如果要存储的是值类型的数据,并且数据量较多的情况下还是使用List比较高效。另外微软也是建议大家尽量使用List而不是自己手动实现,原因如下:
使用 List<T> 类的特定于类型的实现,而不是使用 ArrayList类或自行编写强类型包装集合,这一点非常有利。 原因在于,你的实现必须执行 .NET Framework 的操作,并且公共语言运行时可以共享你的实现不能的 Microsoft 中间语言代码和元数据。
栈
后进者先出,先进者后出,是一种”操作受限“的线性表。
队列
先入队列的先出队列,后入的后出。同样,队列也是一种”操作受限“的线性表。
这两种数据机构也很常见,新的发现是在做练习时遇到了这样一道题,怎么用栈来实现一个队列,题目不难,但是挺有趣的。贴一下题目与笔者的做法,题目来源于Leetcode。
232. 使用栈实现队列的下列操作:
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。peek() -- 返回队列首部的元素。empty() -- 返回队列是否为空。示例:MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2); queue.peek(); // 返回 1queue.pop(); // 返回 1queue.empty(); // 返回 false说明:你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。1 public class MyQueue 2 { 3 private Stack stack1; 4 private Stack stack2; 5 6 /** Initialize your data structure here. */ 7 public MyQueue() 8 { 9 stack1 = new Stack ();10 stack2 = new Stack ();11 }12 13 /** Push element x to the back of queue. */14 public void Push(int x)15 {16 if(stack1.Count > 0 ||(stack1.Count == 0 && stack2.Count == 0))17 {18 stack1.Push(x);19 }20 else21 {22 while(stack2.Count > 0)23 {24 stack1.Push(stack2.Pop());25 }26 27 stack1.Push(x);28 }29 }30 31 /** Removes the element from in front of queue and returns that element. */32 public int Pop()33 {34 if (stack1.Count > 0)35 {36 while (stack1.Count > 0)37 {38 stack2.Push(stack1.Pop());39 }40 }41 42 return stack2.Pop();43 }44 45 /** Get the front element. */46 public int Peek()47 {48 if (stack1.Count > 0)49 {50 while (stack1.Count > 0)51 {52 stack2.Push(stack1.Pop());53 }54 }55 56 return stack2.Peek();57 }58 59 /** Returns whether the queue is empty. */60 public bool Empty()61 {62 return (stack1.Count == 0 && stack2.Count == 0);63 }64 }
上面的做法还行,思路是利用两个栈来进行实现。而想到这个方法时其实是有点小开心的,有点灵机一动的快感,哈哈。队列中的入队操作会将一个元素添加到队列中去,而这个队列会在当前队列中所有元素都出队之后才会被访问到。而栈呢,如果不向栈中添加新的元素,那么下一次出栈操作就会把这个元素给pop出来。因此很容易联想到用两个栈来实现,当需要出队列的时候,我们就把栈中的元素依次pop,并push到另一个栈中,这样最先进入栈中的元素反而就到了栈顶。剩下的就和队列很类似了。
其实算法的学习中还有很多”类似“的情况,但前提是你要了解两种不同数据结构的特点与作用。优势是什么,劣势是什么。而数据结构与算法也不是孤立的,比如大家都了解的各种排序,如插入排序,冒泡排序,快速排序等等都不是单一孤立使用的。比如各大高级语言的集合类一般都会提供排序方法,作为码农我们直接拿来主义就可以使用了。但其实它们内部是会根据不同的数据量啊,大小等进行不同的处理,调用不同的算法来进行实现的。这些其实也都挺有意思的。
附加一道题目:
这道题其实感觉有些类似与脑筋急转弯,启发是有时候可能是我们没有按照计算机的方式去思考,反而复杂化了。反正笔者看这道题的解法和欢乐多的网友类似----原来我是个傻子,哈哈。Leetcode第6题:
将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,排列如下:
L C I R
E T O E S I I GE D H N之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"。请你实现这个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);
示例 1:输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"示例 2:输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"解释:L D R
E O E I IE C I H NT S Gpublic class Solution { public string Convert(string s, int numRows) { if(numRows == 1) { return s; } var charArray = s.ToCharArray(); string[] resultList = new string[Math.Min(charArray.Length, numRows)]; int currentRow = 0; bool goDown = false; for (int i = 0; i < charArray.Length; i++) { resultList[currentRow] = resultList[currentRow] + charArray[i]; if (currentRow == 0 || currentRow == numRows - 1) { goDown = !goDown; } currentRow = goDown ? currentRow + 1 : currentRow - 1; } string result = string.Empty; for (int i = 0; i < resultList.Length; i++) { result += resultList[i]; } return result; }}
官方的解法传送门在这里, 。
我原本的思路是如何把字符串处理成想要的格式,然后再依次输出。但是看了高手的解答真的很惊喜,何必这样呢,其实我们更简单一些,所见即所得的输出不好嘛,每行看到的是什么就把什么输出就好了,总之感觉十分奇妙。
这两天还看了一些二分法和树的内容,但是还没找些题练练手,晚些再水一篇博客把,嘿嘿。
另外,希望疫情早点结束,大家的生活回到正规,感谢在一线奋战的医务工作者们。
转载地址:https://blog.csdn.net/qq_45534061/article/details/113803252 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!