笔 记 归 档

第一部分 数组

一、什么是数组


是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

二、数组相比于容器的优劣


1)优势
  • 支持随机访问,根据下标访问的时间复杂度为 $O(1)$。
  • 相比容器,数组性能更高。
2)劣势
  • 低效的「插入」和「删除」

    在插入和删除某个数据时,会有数据的移动操作。

    插入操作时间复杂度为 $O(n)$。移动数据采取的技巧是,将插入数据移动到数组最后。

    删除操作时间复杂度为 $O(n)$。为了减少移动操作,可以直接记录哪个数据被删除,

    当数组中每隔更多的空间时,进行一次整体的数据删除。大大减少了数据搬移带来的时间损耗。

  • 数组的访问越界问题

    当访问的存储空间已经越界时,可能程序仍然能够运行,这样会造成未知的 bug。

    一般会用容器来替代。

Note:对于数组以及 c++ vector 容器的选择问题,对于业务开发,用容器即可。但是对于性能要求特别高的地方,或者追求简洁的表达方式。可以直接操作数组。但是要求自己分配申请内存和删除

继续阅读笔 记 归 档

基础5丨递归

周末你带着女朋友去电影院看电影,女朋友问你,咱们现在坐在第几排啊?电影院里面太黑了,看不清,没法数,现在你怎么办?

别忘了你是程序员,你怎么会有女朋友,递归就开始排上用场了。于是你就问前面一排的人他是第几排,你想只要在他的数字上加一,就知道自己在哪一排了。但是,前面的人也看不清啊,所以他也问他前面的人。

就这样一排一排往前问,直到问到第一排的人,说我在第一排,然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排,于是你就知道答案了。这就是一个非常标准的递归求解问题的分解过程,去的过程叫“递”,回来的过程叫“归”。基本上,所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例子,我们用递推公式将它表示出来就是这样的:


f(n)=f(n-1)+1 其中,f(1)=1

f(n) 表示你想知道自己在哪一排,f(n-1) 表示前面一排所在的排数,f(1)=1 表示第一排的人知道自己在第一排。有了这个递推公式,我们就可以很轻松地将它改为递归代码,如下:


int f(int n) {
  if (n == 1) return 1;
  return f(n-1) + 1;
}

递归需要满足的条件

  1. 可以把问题划分成多个小问题
  2. 小问题除规模之外 思路应该与大问题一样 
  3.  存在递归终止条件
1、递归存在终止条件===》注意递归堆栈溢出

在实际的软件开发中,编写递归代码时,我们会遇到很多问题,比如堆栈溢出。而堆栈溢出会造成系统性崩溃,后果会非常严重。为什么递归代码容易造成堆栈溢出呢?我们又该如何预防堆栈溢出呢?

我在“栈”那一节讲过,函数调用会使用栈来保存临时变量。每调用一个函数,都会将临时变量封装为栈帧压入内存栈,等函数执行完成返回时,才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大,调用层次很深,一直压入栈,就会有堆栈溢出的风险。

比如前面的讲到的电影院的例子,如果我们将系统栈或者 JVM 堆栈大小设置为 1KB,在求解 f(19999) 时便会出现如下堆栈报错:

Exception in thread “main” java.lang.StackOverflowError

避免溢出

我们可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度(比如 1000)之后,我们就不继续往下再递归了,直接返回报错。还是电影院那个例子,我们可以改造成下面这样子,就可以避免堆栈溢出了。不过,我写的代码是伪代码,为了代码简洁,有些边界条件没有考虑,比如 x<=0。

int depth=0;

//全局变量 表示最深的递归深度

int f(int  n){

depth ++;

if(depth>1000) throw execption;

//如果最深递归深度大于1000 则释放

if(n=1) return 1;

return f(n-1)+1;

}

//递归

2、递归代码要警惕重复计算
将递归代码改写为非递归代码

递归就是借助栈来实现的

f(n)=f(n-1)+1

 

int f(int n);

int ret=0;

for (i=1;i<n;i++){

ret=ret+1;

}

总结:

递归将一个大问题可以划分成几个小问题进行解决,前提是这几个小问题思路和大问题一样,而且有结束的时候,递归可以用简单是代码进行实现,带来的缺点就是时间空间复杂度很高,而且容易溢出和重复,所以我们要注意递归溢出重复的问题

 

基础4 | 队列

栈:先进后出 想想青岛的栈桥

队列:先进先出 类似拉屎

如何理解“队列”?

队列这个概念非常好理解。你可以把它想象成排队买票,先来的先买,后来的人只能站末尾,不允许插队。

先进者先出,这就是典型的“队列”。我们知道,栈只支持两个基本操作:入栈 push()和出栈 pop()。队列跟栈非常相似,支持的操作也很有限,最基本的操作也是两个:入队 enqueue(),放一个数据到队列尾部;出队 dequeue(),从队列头部取一个元素

跟栈一样,队列可以用数组来实现,也可以用链表来实现。用数组实现的栈叫作顺序栈,用链表实现的栈叫作链式栈。同样,用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。

// 用数组实现的队列
public class ArrayQueue {
// 数组:items,数组大小:n
private String[] items;
private int n = 0;
// head表示队头下标,tail表示队尾下标
private int head = 0;
private int tail = 0;

// 申请一个大小为capacity的数组
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}

// 入队
public boolean enqueue(String item) {
// 如果tail == n 表示队列已经满了
if (tail == n) return false;
items[tail] = item;
++tail;
return true;
}

// 出队
public String dequeue() {
// 如果head == tail 表示队列为空
if (head == tail) return null;
// 为了让其他语言的同学看的更加明确,把–操作放到单独一行来写了
String ret = items[head];
++head;
return ret;
}
}

栈只需要一个栈顶指针就好 而队列需要两个指针 分别是head指针和tail指针 分别指向队首和队尾

你可以结合下面这幅图来理解。当 a、b、c、d 依次入队之后,队列中的 head 指针指向下标为 0 的位置,tail 指针指向下标为 4 的位置。

当我们调用两次出队操作之后,队列中 head 指针指向下标为 2 的位置,tail 指针仍然指向下标为 4 的位置。

// 入队操作,将item放入队尾
public boolean enqueue(String item) {
// tail == n表示队列末尾没有空间了
if (tail == n) {
// tail ==n && head==0,表示整个队列都占满了
if (head == 0) return false;
// 数据搬移
for (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
// 搬移完之后重新更新head和tail
tail -= head;
head = 0;
}

items[tail] = item;
++tail;
return true;
}

基础3丨栈

  1. 先进后出 后进先出

从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。

  • 数组栈
// 基于数组实现的顺序栈
public class ArrayStack {
 private String[] items; // 数组
 private int count; // 栈中元素个数
 private int n; //栈的大小

// 初始化数组,申请一个大小为n的数组空间
 public ArrayStack(int n) {
 this.items = new String[n];
 this.n = n;
 this.count = 0;
 }

// 入栈操作
 public boolean push(String item) {
 // 数组空间不够了,直接返回false,入栈失败。
 if (count == n) return false;
 // 将item放到下标为count的位置,并且count加一
 items[count] = item;
 ++count;
 return true;
 }
 
 // 出栈操作
 public String pop() {
 // 栈为空,则直接返回null
 if (count == 0) return null;
 // 返回下标为count-1的数组元素,并且栈中元素个数count减一
 String tmp = items[count-1];
 --count;
 return tmp;
 }
}

栈的扩容