数组链表在笔试中常见的编程题做题技巧

Myth丶恋晨 2021-07-24 22:52 274阅读 0赞

### 文章目录 ###

*  删除数组中重复出现的数
 *  数组问题的解决方案:
 *  链表问题的解决方案:
 *   *  链表中常见的题目:
 *  数组和链表在备战笔试的必刷题
 *   *  第一题:两数之和
     *  第二题:移除元素
     *  第三题:斐波那契数列求值

# 删除数组中重复出现的数 #

![image-20200923231321501][]

> 拿到这个题先分析:
> 
> 1.  给出的条件:排序好的数组
> 2.  要求:`原地`删除重复的元素
> 3.  返回移除元素数组之后的数组的长度

> 原地删除,不能使用额外的空间,要删除重复的元素,首先要获得数组中的元素,那一定就要遍历数组,提供的是排序,因此只需要比较互相相邻的多个元素就可以确定是否是重复的元素

class Solution { 
        public int removeDuplicates(int[] nums) { 
            //1.要求原地删除数组中重复的元素
            //首先的想法是如何删除数组中重复的元素---暴力法->遍历数组
            //原地删除,就是不使用额外的空间
            if (nums.length==0){ 
                return 0;
            }
            int i = 0;
            for (int j = 1; j < nums.length; j++) { 
                if (nums[j] != nums[i]){ 
                    i++;
                    nums[i] = nums[j];
                }
            }
            return i + 1;
    
        }
    }

![image-20200923235250767][]

时间复杂度分析:使用了双指针的方式,在数组的原地重新赋值,实现了对重复元素的删除,时间复杂度:只使用了一层的for循环来遍历数组,因此时间复杂度是O(N)

# 数组问题的解决方案: #

1.  暴力
2.  双指针双指针分为双层循环双指针(可以用来遍历到数组中的每一个元素和其相邻的元素,注意j的起始位置)和前后往中间推动的双指针(比如最大的盛水容器)
3.  看清是否需要原地操作数组(有的题目会要求原地操作,这时就不能使用额外的存储空间来存储中间结果)
4.  那么没有要求原地操作数组的题目是可以使用额外的空间来存储中间结果的
5.  使用哈希表或者其他的数据结构可以简化时间复杂度  
    实际上就是使用了哈希表等数据结构相当于在遍历数组时,将第一层的遍历结果都存储起来了,在数组遍历的第二层需要操作数组中  
    具体的元素的时候就可以直接获取到数组中的元素,而不需要再一次的遍历来获取.
6.  在解决数组问题时,一定注意数组元素的位置(数组的首元素,要操作或者要判断的最后一个元素),而且要注意该元素的前一个元素和后一个元素的位置,一般这就是要访问的点.
7.  关于数组的访问的时间复杂度是O(1),能够实现对于元素的随机访问,但是对于查询的效率不高,平均是O(n)的时间复杂度,因此为了提高数组的查询的效率,可以使用跳表,既是在数组的基础上创建索引(但是跳表的查询是要求该数组是有序的,这一点要格外的注意).

**这里给出遍历数组访问前一个元素和该元素的后一个元素的代码**

public static void main(String[] args) { 
            int [] arr = new int[10];
            for (int i = 0; i < arr.length; i++) { 
                for (int j = i+1; j < arr.length-1 ; j++) { 
    
                }
            }
        }

# 链表问题的解决方案: #

先给出链表的数据结构在Java中的实现

import java.util.Queue;
    import java.util.Stack;
    
    /** * @author 雷雨 * @date 2020/9/16 19:49 * 链表的实现 */
    public class ListNodes { 
        public static void main(String[] args) { 
            Stack stack = new Stack();
    
        }
        MyNodes head = null;
        public void add(int data){ 
            MyNodes newNode = new MyNodes(data);
           if (head==null){ 
               head=newNode;
               return;
           }
           MyNodes temp = head;
           while (temp!=null){ 
               temp = temp.next;
           }
           temp.next = newNode;
    
        }
    }
    class MyNodes{ 
        MyNodes next = null;
        int data;
        public MyNodes(int data){ 
            this.data =data;
        }
    }

1.  首先明确链表的特性,链表不能实现元素的随机访问,但是可以实现低时间复杂度的插入和删除,那么在算法题中如果使用到了链表,那么最最关键也就是使用到链表的添加元素和删除元素的操作.
2.  链表的插入和删除的效率很高,都是0(1)的时间复杂度,但是对于查询访问的时间复杂度很低,平均是0(n)的时间复杂度

## 链表中常见的题目: ##

1.  删除重复元素
2.  反转链表

反转链表的处理思路是:

第一种思路:可以使用额外的存储空间的话,那么就创建一个新的链表,然后一直去访问原链表的尾节点将其放入新创建的链表中

第二种思路:不使用额外的存储空间的话,那就**采用双指针,一个指针指向头,一个指针指向**尾,每次都同时这两个结点的前后节点(用来改变链表的指针指向).

**归根结底就是链表的基本操作的变形**,特别去注意链表的插入和删除时的代码实现.

# 数组和链表在备战笔试的必刷题 #

## 第一题:两数之和 ##

![image-20200923203724588][]

> 做算法题,`如果刚开始没有思路,先想一些比较low的作法,只要是能完成题目的要求也是可以的`,然后再想办法将算法优化.往往第一个思路会给后面算法的优化提供很好的思路.

当我拿到这道题目的时候,没思路,那么就`暴力法`

针对该题的暴力法:就是遍历整个数组,将数组中的每个数都与数组中其他的数配对,寻找是否有相加的结果是target的组合,如果有,那么就输出他们的下标值。

class Solution { 
        public int[] twoSum(int[] nums, int target) { 
            //1.比较容易想到的方法就是使用暴力法,穷举出所有的数的组合
            //缺点也很明显,就是时间复杂度比较高是n^2
            //时间复杂度比较低的算法是使用哈希表的方式
            for (int i = 0; i < nums.length; i++) { 
                for (int j = i + 1; j < nums.length ; j++) { 
                    if (nums[i] == target - nums[j]){ 
                        return new int[]{ i,j};
                    }
                }
            }
            throw new IllegalArgumentException("No two sum solution");
        }
    }

**想要提升算法的能力,一定要在做题之前和做题之后分析自己算法的时间复杂度(一般情况下,不太考虑空间复杂度)**

> 我们使用了暴力法,在遍历数组中每个元素和别的元素进行组合的时候使用了双层的for循环,因此时间复杂度是n^2,这个时间复杂度算是比较高阶的时间复杂度了,是比较low的算法。

要解决这个两数之和的算法，我们还可以使用哈希表，但是我希望做一个系统方法记录，因此哈希表的算法在之后整理了哈希表的算法总结之后再回过头来讲解这道题的解法。

## 第二题:移除元素 ##

![image-20200923235918768][]

这个题和删除排序数组中的重复项非常的相似,可以同样使用数组+双指针的方式解答

class Solution { 
        public int removeElement(int[] nums, int val) { 
            int i = 0;
            for (int j = 0; j < nums.length; j++) { 
                if (nums[j] != val){ 
                    nums[i] =nums[j];
                    i++;
                }
            }
            return i;
    
        }
    }

![image-20200924000914888][]

时间复杂度分析:单层for循环,O(n)的时间复杂度

## 第三题:斐波那契数列求值 ##

![image-20200924092833167][]

这个题是学习数据结构和算法中非常常见的一道题

> 拿到题,可以直接根据题目的需求,可以直接思考暴力求解的方式(因为该题目的思路,题目已经说明的非常清晰了)

class Solution { 
        public int fib(int N) { 
    
            //1.第一种方法,就是使用暴力法,递归迭代算出所以的N对应的值,直到算出N对应的fib返回
            
            if (N==0){ 
                return 0;
            }else if (N==1){ 
                return 1;
            }else { 
                return fib(N-1)+fib(N-2);
            }
        }
    }

时间复杂度分析:使用了递归,循环调用自己的函数,时间复杂度是N^2

思考:可优化的地方,我们在求fib的时候会发现,我们其实重复的求了很多个值的fib,而这都是耗费时间的。`如果能够将求出的fib(n)的值都存储起来,在需要的时候直接访问到`,那么时间的花费应该会减少

因此就有了第二种方法:记忆式的自底向上fib求值

class Solution { 
        public int fib(int N) { 
    
            /**第二种方式:记忆式的自底向上 * 相当于每次都求出了n的fib的具体数值并存储起来(下次需要的时候就不用重复的求值),这样的算法就是 * 降低了时间复杂度的算法,然后n一直的递增的,直到n递增到N的时候,计算出fib(N),然后返回 * */
            if (N <= 1){ 
                return N;
            }
            return memoize(N);
    
        }
        public int memoize(int N){ 
            int [] cache = new int[N+1];
            cache[1] = 1;
            for (int i = 2; i <= N ; i++) { 
                cache[i] = cache[i - 1] + cache[i - 2];
            }
            return cache[N];
        }
    }

整体的思路:`使用了一个数组将之前求出的比较小的fib(n)的值存储起来,在求fib(n)比较大的数值时,使用之前存储起来的值即可,不需要重复的求fib(n)`

\*\*时间复杂度分析:\*\*因为要层fib(2)开始循环求值到fib(n),因此使用了一个for循环,因此复杂度应为0(n).

**需要注意的点:**

1.  在解决算法问题时,往往暴力求解方法中重复求值的地方(或者有规律可循的地方)就是我们可优化算法的地方
2.  思考如何将重复的事情优化并转化为数据结构是非常重要的。

[image-20200923231321501]: /images/20210724/8f88c129c6a344b8b88d3c001dbca9ca.png
[image-20200923235250767]: /images/20210724/d339335a5de24429a2eb11f932629def.png
[image-20200923203724588]: /images/20210724/1f214e203fbe4a86b525cddb66700bea.png
[image-20200923235918768]: /images/20210724/1e04a4b5f2b44b19823aed01cf1527ce.png
[image-20200924000914888]: /images/20210724/ae39657b796b45d0a0eae659f7aa5e40.png
[image-20200924092833167]: /images/20210724/cc6ecb1ab85f4eb99fa9429f5b06cf23.png