顺序表常用操作和笔试题

1、顺序表的常用操作

       1.1 顺序表的创建

          如下代码所示：创建了一个默认空间为10的整型顺序表，如果空间不足则会以1.5倍扩容。

List<Integer> list = new ArrayList<>();

          创建一个空间为15的整型顺序表

List<Integer> list2 = new ArrayList<>(15);

         创建一个顺序表其中存储的元素为其他数据结构（代码中以链表为例）

         //创建链表LinkedList linkedList = new LinkedList<>();linkedList.add(1);linkedList.add(2);linkedList.add(3);//存储链表的顺序表ArrayList<LinkedList> list1 = new ArrayList<>(linkedList);

         1.2 尾插法

 list.add(1);list.add(2);list.add(3);

                输出结果： 

                                

        1.3 在指定位置插入

list.add(2,188);

                输出结果：

                                

        1.4 在尾部插入数据结构的元素

                这里与add（）方法做对比，证明addAll（）方法插入的是元素 ，而add（）方法则是将整个链表尾插。

  //创建链表LinkedList linkedList = new LinkedList<>();linkedList.add(1);linkedList.add(2);linkedList.add(3);//存储链表的顺序表ArrayList<LinkedList> list1 = new ArrayList<>();//在尾部插入链表list1.add(linkedList);System.out.println(list1);//在尾部插入链表的元素list1.addAll(linkedList);System.out.println(list1);

                输出结果：

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​   

1.5 删除指定下标的元素 

        List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(2,188);System.out.println(list);//删除2下标的元素list.remove(2);System.out.println(list);

        输出结果：

1.6 删除第一个值为val的元素 

      List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(2,188);System.out.println(list);//删除值为188的元素list.remove(new Integer(188));System.out.println(list);

                运行结果如下：

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        

1.7 获取下标位置的元素

     List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(2,188);//获取下标为2的元素System.out.println(list.get(2));

                运行结果：

        ​​​​​​​        ​​​​​​​        ​​​​​​​        

1.8 设置下标x的元素为val 

        List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(2,188);System.out.println(list);//将下标为2的元素改为999list.set(2,999);System.out.println(list);

                运行结果：

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​                

1.9 判断元素是否存在顺序表中 

    List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(2,188);System.out.println(list);//判断188是否在顺序表中System.out.println(list.contains(188));

                 运行结果：

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​​​​​​​​

1.10 清空顺序表 

  //清空顺序表list.clear();

        这里博主所列的方法有限，想了解更多方法的同学可以自行去文档中进行查找：​​​​​​​列表 （Java Platform SE 8 ） (oracle.com)

2、面试题

        2.1 27. 移除元素 - 力扣（LeetCode）

           分析：依题意，这道题我们需要将数组不等于val的元素放到数组的前面，使得数组的前k个元素包含不等于val的元素，最后返回k的值。

           解题：设置一个usesized下标，将不等于val值的元素放到数组的usedsized中，再让usesized++即可。

           代码：

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

        2.2 26. 删除有序数组中的重复项 - 力扣（LeetCode）

                分析： 我们需要在一个非严格递增的数组上，原地将不重复的元素放到数组的前k个位置上，然后返回k。

                解题思路：设置一个k下标遍历数组并且将k下标的元素与k-1下标的元素进行比较（因为这里的数组非严格递增，若相等会排列在一起），若不相等则放到原数组的usesized下标中。需要注意的是：这里0下标的元素一定是第一次出现的，因此，k和usesized下标均是从1开始。

class Solution {public int removeDuplicates(int[] nums) {int usesized = 1;for(int i = 1; i < nums.length;i++){if(nums[i] != nums[i-1]){nums[usesized] = nums[i];usesized++;}}return usesized;
}
}

 2.3 88. 合并两个有序数组 - 力扣（LeetCode）

                分析：我们需要将两个递增的数组合并成一个递增的总数组，并且这项操作需要原地完成，题目中两个数组的元素个数均已给出。下面是本题的图解：​​​​​​​

                 解题思路：建立3个下标，分别为 i、j、k，由于合并后的数组需要升序，我们最好从两个升序数组的最后一个元素进行比较，因此，i为nums1的元素个数-1，j为nums2的元素个数-1，k为nums1的元素个数+nums2的元素个数 - 1。将nums1[i]和nums[j]进行比较，大的放到nums1[k]上。然后，让k-- 和 i 或 j--（哪个放入k中哪个就--），循环条件是任意一个数组的下标（i或j）走完，最后，再让没走完的那个数组的所有元素放入nums[k]中，k--。

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int i = m - 1;int j = n - 1;int k = m + n - 1;while(i >= 0 && j >= 0){if(nums1[i] > nums2[j]){nums1[k] = nums1[i];i--;k--;}else{nums1[k] = nums2[j];j--;k--;}}while(i >= 0){nums1[k] = nums1[i];i--;k--;}while(j >= 0){nums1[k] = nums2[j];j--;k--;}}}

2.4 118. 杨辉三角 - 力扣（LeetCode） 

        首先，点进去链接会发现一件事情，那就是这个函数的返回值，我们不认识！！！

        我们可以这么理解，那就是顺序表中存储着顺序表，那么顺序表中存储顺序表是什么东西呢？我们画个图看看：

        看着这个图是不是很熟悉：没错，就是二维数组。

        分析：我们需要完成上图所示的杨辉三角，在杨辉三角中，每个数都等于上一行的前一列和本列的和。

        解题思路：先建立好一个二维数组，定义列和行；然后先处理第一行，将第一行的1先添加入二维数组中；后面我们就可以开始处理后面的行：由图可知，每一行的第一列和最后一列的元素都是1，所以，我们需要在处理中间列之前和之后添加一个1上去，下面就是整个程序最难的部分，处理中间列：我们需要先获取上一行prevRow = ret.get（i-1），至于循环的次数，我们可以看到中间列一共有i-2列，因此，我们的循环条件是：j从1开始，j < i。获取上一行的前一列的元素和上一行的本列元素：prevRow.get(j-1) + prev.get(j)。

class Solution {public static List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();List<Integer> row = new ArrayList<>();row.add(1);ret.add(row);//第一行已经处理完//下面代码从第2行开始for (int i = 1; i < numRows; i++) {List<Integer> curRow = new ArrayList<>();curRow.add(1);//当前行的第一个元素//这里处理中间列//上一行List<Integer> prevRow = ret.get(i-1);for (int j = 1; j < i; j++) {int x = prevRow.get(j) + prevRow.get(j-1);curRow.add(x);}curRow.add(1);//当前行的最后一个元素ret.add(curRow);}return ret;}
}

 2.5 cvte面试题

        

        分析：本题需要建立一个Arraylist，将str1与str2中的元素进行比较，然后把str2中没有的元素丢进Arraylist里面。

        解题思路：遍历str1，看其中的元素是否包含在str2中（使用字符串中的charAt()和contains()方法）

public class Test {public static List<Character> func1(String s1,String s2){//遍历s1看其中是否存在s2中的元素List<Character> list = new ArrayList<>();for (int i = 0; i < s1.length(); i++) {char ch = s1.charAt(i);if(!s2.contains(ch + "")){list.add(ch);}}return list;}public static void main(String[] args) {String str1 = "welcome to cvte";String str2 = "cvte";List<Character> ret = func1(str1,str2);for (char ch: ret){System.out.print(ch);}}
}