本文分析包括数组(字符串)、链表、队列(双端队列)、栈和树的简要分析和解题思路
数组
数据结构分析
数组是一个非常常见且基础的数据结构,且在不同的编程语言中都有着很相似的性质,而围绕着他们的算法面试题也是最多的;很多时候,在分析数组(字符串)相关面试题的时候,我们往往要针对数组(字符串)中的每一个元素(字符)进行处理
在对这种题型的分析中,我们很可能需要把字符串转换成字符数组或字符串数组,通过使用数组的特性,而去操作字符串本身
数组题型多种多样,这里举一个比较典型的例子,Leetcode-344-反转字符串
这个题目规定了,我们需要原地修改数组,使用O(1)的额外空间解决问题,其实意思就是说,我需要使用一个临时变量,而不是一个同等大小的数组,通过循环反向放入构建而成
当读懂了题目,我们很容易能得到思路
既然不能使用另外的数组,那我们就通过交换头尾相对应的元素来完成;
我们可以使用一个指针指向第一个元素,从最前向后移动;
使用第二个指针指向最后一个元素,从最后向前移动;
两个指针的元素分别通过一个临时变量进行交换;
当两个指针指向同一个数,或者第二个指针指向的是第一个指针前边的数,则代表我们完成了本次反转
示例代码如下
public void reverseString(char[] s) {
/*
* 必须说明,这个题目给的参数为char[],如果是String s,则可以通过
* s.toCharArray() 将字符串转换成字符数组
*/
int sLen = s.length;
for(int left=0, right=sLen-1; left<right; left++, right--){
char temp = s[right];
s[right] = s[left];
s[left] = temp;
}
}
这道题目我们规定了两个指针,而这种解题思路又被称为双指针,Leetcode可以通过"双指针"这个标签实现专项练习,点我查看例题
数据结构总结
至此,我们可以总结一下数组这种数据结构的优点
首先是优点
- 构建一个数组非常简单
- 能让我们在O(1)的时间里根据数组的下标(index)查询某个元素
然后是缺点
- 构建时必须分配一段连续的空间
- 查询某个元素是否存在时需要遍历整个数组,耗费O(n)的时间(其中,n是元素的个数)
- 删除和添加某个元素时,同样需要耗费O(n)的时间
在选择数据结构去辅助你的算法的时候,一定要充分考虑这个数据结构的缺点能不能接受,比如快速查询元素是个非常棒的特性,但是时间复杂度O(n)删除和增加操作很多时候是不能接受的,也就是说,如果你的算法需要你对元素进行随机的删除,增加等,则一定要慎重选择数组作为辅助数据结构,对于其他的数据结构也是一个道理。
例题
最后,让我们看看数组题目中,比较常见难度的题目,LeetCode-242-有效的字母异位词
如果对字符和排序比较敏感,你就能知道,char这个基本数据类型,在ASCII编码中都是各个固定的数值,都是一个整数,即使用’b’-‘a’,就等于1,同理’c’-‘a’=2,所以,看到这个题目可以想到,是否可以把字符串转换成char数组,然后对char数组排序,排序之后的char数组转换成字符串再对比一下就可以了;
这个思路很正确,Java中也提供了相应的sort排序方法,但是我们要考虑,排序方法中,最快的排序时间复杂度是O(nlogn),这个题目是不是可以冲一冲O(n)的时间复杂度呢
那么这时候我们换一个思路
即我们知道字母只有26个,则我们可以通过一个长度为26的int[]来保存字母出现的次数,数组的下标即代表是第几个字母,如int[0]为a,int[1]为b;
这样我们可以先把第一个字符串按照一个一个的字符,统计各个字符出现的频次,比如第一个字符为"aabbcceezz",则我们使用int数组是可得int[0]=2,int[1]=2;int[2]=2,int[4]=2,int[25]=2;
扫描完之后我们再按照同样的方法去扫描第二个字符串,和刚刚的思路相反,之前每次统计频次是次数+1,现在我们要-1,比如我们第二个字符串为"ccaabbeezz",则我扫描第一个之后,c相应的次数就-1,即扫描第一个字符后,int[2]=1,这样如果两个字符串相等,则每个下标相应的元素都应该被减成0;
当如果第二个字符和第一个字符不一样的时候,则必定会出现一个字母,相应下标-1之后小于0,这时候就代表两个字符串不相等,我们也只需要考虑这种不同的情况
示例代码
/**
* 代码中出现了很多直接通过下标取数据的操作,这时候实际是使用了
* 数组根据下标查询的时间复杂度为O(1),这么写单纯是为了代码可读
* 性,实际上不要这么写
*/
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()){
return false;
}
char[] sChars = s.toCharArray();
char[] tChars = t.toCharArray();
int[] nums = new int[26];
for(int i=0; i<sChars.length; i++){
nums[sChars[i]-'a'] = nums[sChars[i]-'a']+1;
}
for(int j=0; j<tChars.length; j++){
nums[tChars[j]-'a'] = nums[tChars[j]-'a']-1;
if(nums[tChars[j]-'a'] < 0){
return false;
}
}
return true;
}
链表
在LeetCode中,题库第一个简单题之后就是一个中等难度的链表题目,很多同志连构建方法都没搞懂就卡在了第二道题,很像是背了四年单词,只背到了abandon
数据结构分析
链表分为单链表和双链表;
单链表是指链表中的每个元素实际上是一个单独的对象,而所有对象都通过每个元素中的引用字段链接在一起,即每一个元素的引用区域,指向下一个元素;
而双链表是指,双链表的每个结点中都含有两个引用字段,即一个元素的后引用区域指向下一个元素,或者后一个元素的前引用区域指向上一个元素;
而这种引用指向的结构可以想到,它其实是为了解决数组的一个缺点,即需要申请一块连续的空间;但同时,链表也失去了数组通过下标快速查询的能力
数据结构总结
根据这个结构,我们可以总结一下链表的优缺点
首先是优点
- 链表可以灵活的分配内存空间
- 链表能在O(1)的时间复杂度下删除或添加元素(对于单链表,是前一个元素已知;对于双链表,是后一个元素已知的情况下才是O(1)的时间复杂度)
然后是缺点
- 链表查询元素需要O(n)的时间复杂度(即每次查询都要从头开始一个一个的查)
那么根据优缺点,我们就能看出链表和数组的不同,这让他们也有了不同的使用场景,比如当你的算法中,元素的个数不确定,又有很多的删除添加操作,则应该使用链表;如果你的算法中元素个数确定,大部分的操作都是查询,没什么删除添加操作,则选择数组更好。
根据数据结构的特性,可以归为一下几种链表类的题型和解题技巧
- 利用快慢指针(有时候需要用到三个指针)
- 反转链表
- 倒数第k个元素
- 寻找列表中中间位置的元素
- 判断列表是否有环
- ···
- 构建一个虚假链表头,常用于返回新的链表时(如果不使用虚假的链表头,则每次构建都要增加一个if-else去判断链表头是否为空,如果有一个虚假链表头,则只需要不断往后增加元素,最后返回的时候去掉这个假的链表头即可)
- 两个排序链表,进行整合排序
- 将链表的奇偶数按原定顺序分离,生成前半部分奇数,后半部分偶数的链表
常见题型
- 题型
- 单链表反转
- 链表中环的检测
- 两个有序链表合并
- 删除链表倒数第n个节点
- 求链表的中间节点
- 要注意的边界条件
- 如果链表为空
- 如果链表只包含一个节点
- 如果链表只包含两个节点
- 代码逻辑在处理头结点和尾节点的时候,能否正常工作
使用链表的时候,可以在纸上画出链表结点的相应关系,链表相对来说已经比较抽象,所以画出修改的方法也有助于自己的理解
从链表的题型来看,尤其是像K个一组,或者按顺序合并链表等的操作中,可以明显看出链表的很多操作都是同一种类型的操作,只是将这种操作重复了好多次,所以链表的很多题型,都可以使用递归的思想进行,这篇文章就讲个几个比较常见的链表使用递归思想的题目
例题
接下来我们看一道例题,LeetCode-25-K个一组,翻转链表
示例代码
public ListNode reverseKGroup(ListNode head, int k) {
int j = k;
ListNode next = null;
ListNode prev = null;
ListNode curr = head;
int l = k;
ListNode test = head;
while(test != null && l>0){
test = test.next;
l--;
}
if(test == null && l != 0){
return head;
}
while(curr != null && j>0){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
j--;
}
if(curr == null && j != 0){
return prev;
}
head.next = reverseKGroup(curr, k);
return prev;
}
在这个题目中,最重要的部分就是
while(curr != null && j>0){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
j--;
}
这段代码是所有翻转链表都会用到的,只要记住这段代码,翻转链表类的题目就不是问题
栈
数据结构分析
栈是LeetCode题目中中等难度偏上时经常会使用到的数据结构。
栈的最大特点就是后进先出(LIFO),对于栈来说,所有的操作都是在栈的顶部完成的,所以实际上对栈的数据操作只有三个
- 查看栈顶部的元素
- 向栈顶部压入元素
- 从栈顶部弹出元素
这里其实可以看一下Java容器Stack的源代码,也是只有这么几个操作
public class Stack<E> extends Vector<E> {
//构造方法
public Stack() {
}
/**
* 将元素从栈的顶部压入,并将压入的元素作为值返回
*/
public E push(E item) {
addElement(item);
return item;
}
/**
* 弹出栈顶部的元素,并将弹出的元素作为值返回
*/
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
/**
* 查看栈顶部的元素,注意和pop区分,peek方法并不会移除顶部元素
*/
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
/**
* 判断堆栈是否为空
*/
public boolean empty() {
return size() == 0;
}
/**
* 返回对象在堆栈中的位置,以 1 为基数
*/
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1224463164541339165L;
}
看完这段代码有的同志们可能就发现了,虽然方法就只有这么几个,但是想peek,pop这种操作,实际上使用的方法是继承自Vector的方法,这里就要牵扯出接下来的概念:
即构建一个栈,应该是使用数组还是链表,大概思考一下就知道,这两种方法实现栈这种数据结构并不难,具体的实现方法可以看这里。
用数组实现的栈,称为顺序栈;用链表实现的栈,称为链式栈;
因为Java的Stack实现自Vector,而Vector是一个动态数组,所以我们可以认为Java自带的Stack是一个顺序栈,可能这时候你已经想到了,数组实现的栈有一个很大的问题;
就是当数组容量已经用完,但是又需要入栈的时候,按照数组动态扩容,是需要申请一个更大的内存做一个容量更大的数组,然后将现有的元素全部放进新的数组,这个扩容的过程岂不是又用了O(n)的时间复杂度?
但是如果用均摊分析法来考虑,有很多很多很多元素需要入栈的时候,如果我们按照每次增加两倍的方法去扩容数组,那个O(1)时间复杂度的入栈操作比O(n)时间复杂度的扩容操作要多得多,所以平均下来,时间复杂度还是O(1),即不论如何,栈的入栈操作,时间复杂度都是O(1)
数据结构总结
那么我们什么时候需要用到栈呢?
很明显,当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选“栈”这种数据结构。
非常典型的用法
这里可以讲个题外话,就是浏览器左上角的前进后退按钮,这种前进后退的操作,其实就可以用栈来操作;
我可以构建两个栈,当新页面产生的时候就push进去,点了后退就pop栈顶url,然后把这个pop的值push进另一个栈,这样点击前进的时候就可以把第二个栈的栈顶元素pop出来到第一个栈,完美实现前进后退功能;
例题
LeetCode-20-有效的括号
示例代码
/**
* 这里先用hash表存一下({[代码就不会显得这么蠢
* 这样写比较容易懂,将就一下吧
*/
public boolean isValid(String s) {
if(s.length()%2 != 0){
return false;
}
Stack<String> stringStack = new Stack<String>();
String[] strings = s.split("");
if("}".equals(strings[0]) || "]".equals(strings[0]) || ")".equals(strings[0])){
return false;
}
for(String l : strings){
if(stringStack.isEmpty()){
stringStack.push(l);
}else{
if(("}".equals(l) && "{".equals(stringStack.peek()))
|| ("]".equals(l) && "[".equals(stringStack.peek()))
|| (")".equals(l) && "(".equals(stringStack.peek()))){
stringStack.pop();
}else{
stringStack.push(l);
}
}
}
return stringStack.isEmpty();
}