联想|IT世界的诡异事件，2020为何算法和数据结构面试题会如此火爆？高通骁龙|骁龙865

文章图片

文章图片

文章图片

文章图片

文章图片

文章图片

只有熟练掌握基础的数据结构与算法，才能对复杂问题迎刃有余。
很多时候，你即使提前复习了这些最常见的面试算法题，你依旧无法通过算法面试！为什么？
1.你在提前准备复习的时候，在网上找了半天相应题目的分析文章，但你看了就是不懂。
2.你在面试的时候，卡壳了，一时间忘了怎么写代码了
怎么办？
面试结构框架图

这篇文章主要介绍算法和数据结构， 2020年新形势，很多大厂（阿里云、滴滴。。）对算法和数据结构考的很多

算法，主要是以下几种：

基础技巧：分治、二分、贪心
排序算法：快速排序、归并排序、计数排序
搜索算法：回溯、递归、深度优先遍历，广度优先遍历，二叉搜索树等
图论：最短路径、最小生成树
动态规划：背包问题、最长子序列

数据结构，主要有如下几种：

数组与链表：单 / 双向链表
栈与队列
哈希表
堆：最大堆／最小堆
树与图：最近公共祖先、并查集
字符串：前缀树（字典树）／后缀树

简单介绍一些
trapping-rain-water-1(雨水收集问题):

浏览器中的栈：

回溯法解题:

koko-eating-bananas:

一、垃圾回收机制面试题
引入：
任何语言在运行过程中都会创建对象，也就意味着需要在内存中为这些对象在内存中分配空间，在这些对象失去使用的意义的时候，需要释放掉这些内容，保证内存能够提供给新的对象使用。对于对象内存的释放就是垃圾回收机制，也叫做gc ，对于java开发者来说gc是一个双刃剑

c的垃圾回收是人工的，工作量大，但是可控性高。
java是自动化的，但是可控性很差，甚至有时会出现内存溢出的情况，
内存溢出也就是jvm分配的内存中对象过多，超出了最大可分配内存的大小。

1.提到java的垃圾回收机制就不得不提一个方法：

System.gc()用于调用垃圾收集器，在调用时，垃圾收集器将运行以回收未使用的内存空间。它将尝试释放被丢弃对象占用的内存。
然而System.gc（）调用附带一个免责声明，无法保证对垃圾收集器的调用。
所以System.gc()并不能说是完美主动进行了垃圾回收。

2.作为java程序员还是很有必要了解一下gc ，这也是面试过程中经常出现的一道题目。
我们从三个角度来理解gc 。

jvm怎么确定哪些对象应该进行回收
jvm会在什么时候进行垃圾回收的动作
jvm到底是怎么清楚垃圾对象的

3.jvm怎么确定哪些对象应该进行回收
【联想|IT世界的诡异事件，2020为何算法和数据结构面试题会如此火爆？】对象是否会被回收的两个经典算法：引用计数法，和可达性分析算法。
引用计数法
简单的来说就是判断对象的引用数量。
实现方式：给对象共添加一个引用计数器，每当有引用对他进行引用时，计数器的值就加1 ，当引用失效，也就是不在执行此对象是，他的计数器的值就减1 ，若某一个对象的计数器的值为0 ，那么表示这个对象没有人对他进行引用，也就是意味着是一个失效的垃圾对象，就会被gc进行回收。
但是这种简单的算法在当前的jvm中并没有采用，原因是他并不能解决对象之间循环引用的问题。
假设有A和B两个对象之间互相引用，也就是说A对象中的一个属性是B ， B中的一个属性时A这种情况下由于他们的相互引用，从而是垃圾回收机制无法识别。

因为引用计数法的缺点有引入了可达性分析算法，通过判断对象的引用链是否可达来决定对象是否可以被回收。可达性分析算法是从离散数学中的图论引入的，程序把所有的引用关系看作一张图，通过一系列的名为GC Roots的对象作为起始点，从这些节点开始向下搜索，搜索所走过的路径称为引用链。当一个对象到 GC Roots 没有任何引用链相连（就是从 GC Roots 到这个对象不可达）时，则证明此对象是不可用的。
如图：

4.在确定了哪些对象可以被回收之后， jvm会在什么时候进行回收

会在cpu空闲的时候自动进行回收
在堆内存存储满了之后
主动调用System.gc()后尝试进行回收

5.如何回收
如何回收说的也就是垃圾收集的算法。
算法又有四个：标记-清除算法复制算法标记-整理算法分代收集算法.
标记-清除算法。
这是最基础的一种算法，分为两个步骤，第一个步骤就是标记，也就是标记处所有需要回收的对象，标记完成后就进行统一的回收掉哪些带有标记的对象。这种算法优点是简单，缺点是效率问题，还有一个最大的缺点是空间问题，标记清除之后会产生大量不连续的内存碎片，当程序在以后的运行过程中需要分配较大对象时无法找到足够的连续内存而造成内存空间浪费。
执行如图:

复制算法。
复制将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。这样使得每次都是对其中的一块进行内存回收，内存分配时也就不用考虑内存碎片等复杂情况。只是这种算法的代价是将内存缩小为原来的一半。
复制算法的执行过程如图:

复制收集算法在对象存活率较高时就要执行较多的复制操作，效率将会变低。更关键的是，浪费了一半的空间。
标记-整理算法：
标记整理算法与标记清除算法很相似，但最显著的区别是：标记清除算法仅对不存活的对象进行处理，剩余存活对象不做任何处理，造成内存碎片；而标记整理算法不仅对不存活对象进行处理清除，还对剩余的存活对象进行整理，重新整理，因此其不会产生内存碎片。
标记整理算法的作用示意图如下:

分代收集算法:
法是一种比较智能的算法，也是现在jvm使用最多的一种算法，他本身其实不是一个新的算法，而是他会在具体的场景自动选择以上三种算法进行垃圾对象回收。
1.那么现在的重点就是分代收集算法中说的自动根据具体场景进行选择。这个具体场景到底是什么场景。
2.场景其实指的是针对jvm的哪一个区域， 1.7之前jvm把内存分为三个区域:新生代，老年代，永久代。

了解过场景之后再结合分代收集算法得出结论：
a)在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法。只需要付出少量存活对象的复制成本就可以完成收集。
b)老年代中因为对象存活率高、没有额外空间对他进行分配担保，就必须用标记-清除或者标记-整理。
总结:

注意:
在jdk8的时候java废弃了永久代，但是并不意味着我们以上的结论失效，因为java提供了与永久代类似的叫做“元空间”的技术。
废弃永久代的原因：由于永久代内存经常不够用或发生内存泄露，爆出异常java.lang.OutOfMemoryErroy 。元空间的本质和永久代类似。不过元空间与永久代之间最大的区别在于：元空间并不在虚拟机中，而是使用本地内存。也就是不局限与jvm可以使用系统的内存。理论上取决于32位/64位系统可虚拟的内存大小。
二、字符串反转
给定一个字符串，一个这个字符串的子串，将第一个字符串反转，但保留子串的顺序不变。
一般的方法是先扫描一边第一个字符串，然后用stack把它反转，同时记录下子串出现的位置。然后再扫描一遍把记录下来的子串再用stack反转。我用的方法是用一遍扫描数组的方法。扫描中如果发现子串，就将子串倒过来压入堆栈。
最后再将堆栈里的字符弹出，这样子串又恢复了原来的顺序。源代码如下：
#include <iostream>
#include <cassert>
#include <stack>
using namespace std;
//reverse the string 's1' except the substring 'token'.
constchar* reverse(const char* s1 const char* token)
{
assert(s1 && token);
stack<char> stack1;
const char* ptoken = token *head = s1 *rear = s1;
while (*head != '')
{
while(*head!= '' && *ptoken == *head)
{
ptoken++;
head++;

if(*ptoken == '')//contain the token
{
const char* p;
for(p=head-1;p>=rear;p--)
stack1.push(*p);
ptoken = token;
rear = head;

else
{
stack1.push(*rear);
head=++rear;
ptoken = token;

char * return_v = new char[strlen(s1)+1
;
int i=0;
while(!stack1.empty())
{
return_v[i++
= stack1.top();
stack1.pop();

return_v[i
='';
return return_v;

intmain(int argc char* argv[
)
{cout<<\"XXXX\";
cout<<reverse(\"xxxxx\"\" XXXX \");
return 0;

XXXX代表自己输入