我岂能忍!面试官居然用数据结构和算法“羞辱”我

你的名字 2022-12-29 11:24 9阅读 0赞

## 引言 ##

原文链接：[我岂能忍!面试官居然用数据结构和算法“羞辱”我][Link 1] 希望点进去的小伙伴关注一下我的公众号哟，文末有二维码，谢谢！

如果大家是因为标题而进来，那我实话告诉你吧，真事！以后我会分享数据结构与算法相关的文章。为什么要学数据结构与算法，我总结了如下几点：

*  锻炼思维和问题处理能力
 *  提高代码效率
 *  大厂面试必备
 *  情怀（大学没认真学）

## 1、基础知识复习 ##

虽然作为一名Java程序员来说，学数据结构与算法的目的不是为了搞学术研究，但是其基础知识和概念还是要过一些的。

**逻辑结构：**

*  集合结构
 *  线性结构
 *  树形结构
 *  图形结构

**物理结构：**

*  顺序存储结构
 *  链式存储结构

逻辑结构是面向问题的，而物理结构就是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。

**算法的五个基本特性：**

*  输入
 *  输出
 *  有穷性
 *  确定性
 *  可行性

**算法设计的要求：**

*  正确性
 *  可读性
 *  健壮性
 *  时间效率高和存储量低

### **1.1、时间复杂度** ###

首先，时间复杂度的计算公式为：T(n)=O(f(n))，这种表示法称为：大O符号表示法。

T(n)表示语句总的执行次数，而n表示问题的规模，因为语句总的执行次数是与问题的规模有关系的，因此它俩可以用函数表示。

首先来看一个例子，来看看我们是如何推导出时间复杂度的。

int i=0;
    int j=0;
    while (i<n){
      i++;
      j=i;
    }

这段代码的时间复杂度T(n)=O(n)，为什么呢？

*  首先第一行代码会被执行1次
 *  第二行代码会被执行1次
 *  第三行代码中的n就是问题的规模
 *  而i<n会被执行n次
 *  i++会被执行n次
 *  j=i会被执行n次

上述代码一共执行3n+2次，当n无穷大，2可以忽略，其倍数3也可以忽略，因此f(n)=n。

<table>  常用时间复杂度表  
 <tbody> 
  <tr> 
   <th>执行次数</th> 
   <th>函数阶</th> 
   <th>非正式术语</th> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">12</td> 
   <td style="vertical-align:top;">O(1)</td> 
   <td style="vertical-align:top;">常数阶</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">2n+3</td> 
   <td style="vertical-align:top;">O(n)</td> 
   <td style="vertical-align:top;">线性阶</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">3n²+2n+1</td> 
   <td style="vertical-align:top;">O(n2)</td> 
   <td style="vertical-align:top;">平方阶</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">5log2n+20</td> 
   <td style="vertical-align:top;">O(logn)</td> 
   <td style="vertical-align:top;">对数阶</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">2n+3nlog2n+19</td> 
   <td style="vertical-align:top;">O(nlogn)</td> 
   <td style="vertical-align:top;">nlogn阶</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">6n3+2n2+3n+4</td> 
   <td style="vertical-align:top;">O(n3)</td> 
   <td style="vertical-align:top;">立方阶</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">2n</td> 
   <td style="vertical-align:top;">O(2n)</td> 
   <td style="vertical-align:top;">指数阶</td> 
  </tr> 
 </tbody> 
</table>

常用的时间复杂度所耗费的时间从小到大依次是：

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

像O(n3)，过大的n都会使得结果变得不现实。同样指数阶O(2n)和阶乘阶O(n!)等除非是很小的n值，否则哪怕n只是100，都是噩梦般的运行时间。

另外，还有平均时间复杂度、最坏时间复杂度等概念。

### **1.2、空间复杂度** ###

算法空间复杂度S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于

n所占存储空间的函数。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)。

如果算法执行所需要的存储量不随某个变量n的变化而变化，则此算法空间复杂度为一个常量，记为O(1),如下代码所示。

int i=1;
    int j=2;
    int m=i+j;

而下面的代码表示的是一个数组，该数组的长度是随n变化而变化的，因此其空间复杂度为O(n)。

int[] m = new int[n];

我们在写代码时，完全可以用空间换取时间。

## 2、数组、链表、栈、队列 ##

大家接触到最多的数据结构，就是这四种了吧，所以我觉得没必要讲太多。

下面列出数组和链表的关键特性和两者的区别。

**数组特点：**

*  用一块连续的内存存储：空间利用率低，内存要求比较高
 *  查询简单，增加和删除困难：从头部插入（后面所有元素向后搬移）和删除（后面所有元素向前搬移）效率低
 *  按索引随机访问效率高，为O(1) ，从数组首地址向后偏移即可
 *  数组的大小是固定的，不能进行动态扩展

**链表特点：**

*  由一系列结点组成，结点可以动态生成
 *  结点包括两部分：数据和指向下一个结点的指针
 *  查询慢，插入删除快
 *  占用不连续空间（不能随机访问，只能从头到尾遍历），空间利用率高

除了单向链表，还有双向链表、单向循环链表、双向循环链表等，这些都是链表的变种，不足为惧。

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;">操作</td> 
   <td style="vertical-align:top;">数组</td> 
   <td style="vertical-align:top;">链表</td> 
  </tr> 
  <tr> 
   <td colspan="1" style="vertical-align:top;">随机访问</td> 
   <td colspan="1" style="vertical-align:top;">O(1)</td> 
   <td colspan="1" style="vertical-align:top;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">头部插入元素</td> 
   <td style="vertical-align:top;">O(n)</td> 
   <td style="vertical-align:top;">O(1)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">头部删除元素</td> 
   <td style="vertical-align:top;">O(n)</td> 
   <td style="vertical-align:top;">O(1)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">尾部插入元素</td> 
   <td style="vertical-align:top;">O(1)</td> 
   <td style="vertical-align:top;">O(1)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">尾部删除元素</td> 
   <td style="vertical-align:top;">O(1)</td> 
   <td style="vertical-align:top;">O(1)</td> 
  </tr> 
 </tbody> 
</table>

栈：后进先出，LIFO

队列：先进先出，FIFO

栈和链表是两种特殊的线性结构，它们可以基于数据和链表实现。

### **2.1、栈的应用场景-十进制数转二进制数** ###

**十进制数转二进制数的算法：**

*  每次除以2，其余数入栈，商如果为0则结束，不为0则继续除以2，依次类推。
 *  结束后，将栈中元素全部出栈，即为所求的二进制数。

**用Java代码实现如下：**

Stack<Integer> stack = new Stack<>();
        
    public void ten2Two(int x){
        int a = x/2;
        int b = x%2;
        // 入栈
        stack.push(b);
        if(a!=0){
            ten2Two(a);
        }else{
            // 求解结束，所有元素出栈
            Iterator<Integer> iterator = stack.iterator();
            while (iterator.hasNext()){
                System.out.print(stack.pop());
            }
        }
    }

关于数据结构与算法的入门知识就讲到这里吧，为什么呢？因为我要赶紧去刷题啦！

觉得写得不错的小伙伴，扫码关注一下我的公众号吧，谢谢呀！

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70][]

[Link 1]: https://mp.weixin.qq.com/s?__biz=MzI1NTc1MDU3Mw==&tempkey=MTA5Ml9CSCtXcmlkcytkcDhxNWpxNVRPdWZWbzk3T3AxSUJlOHpzbnZmTVR4WDlNbVk4TDJnczN0UHBMUjZYc1RlMDlYTGowU3VKdENJdHNHVlg2N2dOeklmNHJRQVc4UmhvS09JSlA3bjN3NHZsUTJxQTNBNUF5a0dURjFHSC0tcHJma090TVZnZFNrMFRhYzZYRVRJcVUxcXA0VWZ1MkRnQ2tJUENSaW5Rfn4%3D&chksm=6a307a5f5d47f3499c52b9deaea798ab7032ea1bad146c93b846b2976a5559465c327cb235f3&__mpa_temp_link_flag=1&token=869464904#rd
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70]: /images/20221120/14bcddc0cffb42f59cfa1aece6446990.png