leetcode常规算法题复盘（基础篇）—

leetcode常规算法题复盘（基础篇）——线性表java实现

根据清华大学出版社的《数据结构及应用算法教程》第二章内容，线性表包括顺序存储模式及链式存储模式，以下为根据书中内容通过java语言实现的顺序表及链表。

其中元素类型通过泛型化进行约束。

此处特别鸣谢CSDN爪哇大佬的博客，地址：https://blog.csdn.net/qq_40794973/article/details/101555091?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_baidulandingword-3&spm=1001.2101.3001.4242

顺序表：

  1 import java.util.Arrays;
  2 /**
  3  * 顺序线性表的实现
  4  */
  5 public class LineList<E>{
  6 　　private int size;   //长度
  7 　　private Object[] array;  //底层数组
  8 　　private final int default_length=16; //默认长度
  9  /**
 10   * 无参构造方法
 11   */
 12 　　public LineList(){
 13 　　　　size = 0;
 14   //使用默认长度构造数组
 15 　　　　array = new Object[default_length];
 16　　 }
 17  /**
 18   * 指定长度进行构造
 19   * @param length 指定初始长度
 20   */
 21  public LineList(int length){
 22   if(length<0){
 23    throw new IllegalArgumentException("初始长度不合法:"+length);
 24   }
 25   //使用指定长度构造数组
 26   array = new Object[length];
 27  }
 28 
 29  /**
 30   * 指定初始化元素和长度进行构造
 31   * @param element 初始化元素
 32   * @param length 初始化长度
 33   */
 34  public LineList(E element,int length){
 35   if(length<1){
 36    throw new IllegalArgumentException("初始长度不合法:"+length);
 37   }
 38   //使用指定长度构造数组
 39   array = new Object[length];
 40   //初始化第一个元素
 41   array[0] = element;
 42   size++;
 43  }
 44  /**
 45   * 指定初始化元素进行构造
 46   * @param element 初始化元素
 47   */
 48  public LineList(E element){
 49   //使用默认长度初始化数组
 50   array = new Object[default_length];
 51   //初始化第一个元素
 52   array[0] = element;
 53  }
 54 
 55  /**
 56   * 获取元素个数
 57   */
 58  public int size() {
 59   return size;
 60  }
 61 
 62  /**
 63   * 判断是否为空
 64   */
 65  public boolean isEmpty() {
 66   return size==0;
 67  }
 68 
 69  /**
 70   * 判断是否包含此元素
 71   */
 72  public boolean contains(E e) {
 73   if(indexOf(e) == -1){
 74    return false;
 75   }
 76   return true;
 77  }
 78 
 79  /**
 80   * 格式化为数组
 81   */
 82  public Object[] toArray() {
 83   return Arrays.copyOf(array, size);
 84  }
 85 
 86  /**
 87   * 向线性表尾部添加一个元素
 88   * @param e
 89   * @return
 90   */
 91  public void add(E e) {
 92   extendCapacity(size+1);
 93   array[size]=e;
 94   size++;
 95  }
 96 
 97  /**
 98   * 扩容
 99   * @param length 需要的长度
100   */
101  private void extendCapacity(int length){
102   //当前数组长度和需要的长度取最大
103   int minCapacity = Math.max(array.length, length);
104   //判断是否需要扩容
105   if(minCapacity - array.length>0){
106    //数组长度增加一半
107    int newLength = array.length + array.length/2;
108    //如果新的长度还比需求要小,将需求的长度作为数组长度
109    if(newLength < minCapacity){
110     newLength=minCapacity;
111    }
112    //数组长度不能超过Integer.Max_Value
113    if(newLength > Integer.MAX_VALUE - 8){
114     newLength = Integer.MAX_VALUE;
115    }
116    //数组扩容
117    array = Arrays.copyOf(array, newLength);
118   }
119  }
120  /**
121   * 从线性表中移除所有此元素
122   * @param e 需要移除的元素
123   * @return
124   */
125  public void removeAll(E e) {
126   if(e==null){
127    for(int i=0;i<size;i++){
128     if(array[i]==null){
129      fastRemove(i);
130     }
131    }
132   }else{
133    for(int i=0;i<size;i++){
134     if(e.equals(array[i])){
135      fastRemove(i);
136     }
137    }
138   }
139  }
140 
141  /**
142   * 删除索引处元素,后面的元素依次前移
143   * @param index 需要删除的索引
144   */
145  private void fastRemove(int index){
146   if(size-index-1>0){  
147    //数组从index+1开始全部前移
148    System.arraycopy(array, index+1, array, index, size-1);
149   }
150   //最后一个元素请空
151   array[--size]=null;
152  }
153 
154  /**
155   * 清空线性表
156   */
157  public void clear() {
158   //将数组全部填充为null
159   Arrays.fill(array, null);
160   //将元素个数改为0
161   size=0;
162  }
163  /**
164   * 获得索引处的元素
165   * @param index
166   * @return 索引处的元素
167   */
168  @SuppressWarnings("unchecked")
169  public E get(int index) {
170   checkIndex(index);
171   return (E)array[index];
172  }
173 
174  /**
175   * 验证是否为索引越界
176   * @param index
177   */
178  private void checkIndex(int index){
179   if(index>=size || index<0){
180    throw new IndexOutOfBoundsException("索引越界");
181   }
182  }
183 
184  /**
185   * 将索引处的元素修改为新的元素
186   * @param index 索引位置
187   * @param element 元素
188   * @return 原索引处的元素
189   */
190  @SuppressWarnings("unchecked")
191  public E set(int index, E element) {
192   checkIndex(index);
193   E e = (E)array[index];
194   array[index]=element;
195   return e;
196  }
197 
198  /**
199   * 在指定的索引处插入指定的元素
200   * @param index 索引位置
201   * @param element 元素
202   */
203  public void add(int index, E element) {
204   //验证索引
205   checkIndex(index);
206   //是否需要扩容
207   extendCapacity(size+1);
208   //复制数组
209   System.arraycopy(array, index, array, index+1, size-index);
210   array[index]=element;
211  }
212 
213  /**
214   * 移除索引处的元素
215   * @param index 索引
216   * @return 删除了的元素
217   */
218  @SuppressWarnings("unchecked")
219  public E remove(int index) {
220   checkIndex(index);
221   //取得索引位置的元素
222   E e = (E)array[index];
223   fastRemove(index);
224   return e;
225  }
226 
227  /**
228   * 取得元素第一次出现的位置的索引
229   * @param e 要查找的元素
230   * @return 如果为-1说明线性表没有这个元素
231   */
232  public int indexOf(E e) {
233   if(e==null){//注意此处e==null的含义是传入了一个值为空的e值，但e并不是没有，还是应该在Object array里寻找同样为空的位置。
234    for(int i=0;i<size;i++){
235     if(e==array[i]){
236      return i;
237     }
238    }
239   }
240   for(int i=0;i<size;i++){
241    if(e.equals(array[i])){
242     return i;
243    }
244   }
245   return -1;
246  }
247 
248  /**
249   * 取得元素最后一次出现的位置的索引
250   * @param e 要查找的元素
251   * @return 如果为-1说明线性表没有这个元素
252   */
253  public int lastIndexOf(E e) {
254   //判断元素是否为null
255   if(e==null){    
256    for(int i=size-1;i>=0;i--){
257     if(e==array[i]){
258      return i;
259     }
260    }
261   }
262   for(int i=size-1;i>=0;i--){
263    //如果为null这里会跑出NullPoint异常
264    //所以前面要加上验证是否为Null
265    if(e.equals(array[i])){
266     return i;
267    }
268   }
269   return -1;
270  }
271 
272  /**
273   * 截取线性表
274   * @param fromIndex 开始索引
275   * @param toIndex 结束索引
276   * @return 截取的线性表
277   */
278  @SuppressWarnings("unchecked")
279  public LineList<E> subList(int fromIndex, int toIndex) {
280   //判断开始索引是否越界
281   if(fromIndex<0 || fromIndex >=size){
282    throw new IndexOutOfBoundsException("开始索引越界:"+fromIndex);
283   }
284   //判断结束索引是否越界
285   if(toIndex >=size || fromIndex <0){
286    throw new IndexOutOfBoundsException("结束索引越界:"+toIndex);
287   }
288   //判断开始索引和结束索引是否正确
289   if(fromIndex > toIndex){
290    throw new IllegalArgumentException("参数不正确,开始索引应大于等于结束索引");
291   }
292   LineList<E> list = new LineList<E>();
293   for(int i=fromIndex,j=toIndex;i<=j;i++){
294    list.add((E)array[i]);
295   }
296   return list;
297  }
298 }

链表：

①用常规方式实现有虚拟头结点的链表

  1 public class LinkedList<E> {
  2     private class Node {
  3         public E e;
  4         public Node next;
  5         public Node(E e, Node next) {
  6             this.e = e;
  7             this.next = next;
  8         }
  9         public Node(E e) {
 10             this(e, null);
 11         }
 12         public Node() {
 13             this(null, null);
 14         }
 15         @Override
 16         public String toString() {
 17             return e.toString();
 18         }
 19     }
 20     private Node dummyHead;
 21     private int size;
 22     public LinkedList() {
 23         dummyHead = new Node();
 24         size = 0;
 25     }
 26     // 获取链表中的元素个数
 27     public int getSize() {
 28         return size;
 29     }
 30     // 返回链表是否为空
 31     public boolean isEmpty() {
 32         return size == 0;
 33     }
 34     // 在链表的index(0-based)位置添加新的元素e
 35 // 在链表中不是一个常用的操作，练习用
 36     public void add(int index, E e) {
 37         if (index < 0 || index > size) {
 38             throw new IllegalArgumentException("Add failed. Illegal index.");
 39         }
 40         Node prev = dummyHead;
 41         for (int i = 0; i < index; i++) {
 42             prev = prev.next;
 43         }
 44         prev.next = new Node(e, prev.next);
 45         size++;
 46     }
 47     // 在链表头添加新的元素e
 48     public void addFirst(E e) {
 49         add(0, e);
 50     }
 51     // 在链表末尾添加新的元素e
 52     public void addLast(E e) {
 53         add(size, e);
 54     }
 55     // 获得链表的第index(0-based)个位置的元素
 56 // 在链表中不是一个常用的操作，练习用：
 57     public E get(int index) {
 58         if (index < 0 || index >= size) {
 59             throw new IllegalArgumentException("Get failed. Illegal index.");
 60         }
 61         Node cur = dummyHead.next;
 62         for (int i = 0; i < index; i++) {
 63             cur = cur.next;
 64         }
 65         return cur.e;
 66     }
 67     // 获得链表的第一个元素
 68     public E getFirst() {
 69         return get(0);
 70     }
 71     // 获得链表的最后一个元素
 72     public E getLast() {
 73         return get(size - 1);
 74     }
 75     // 修改链表的第index(0-based)个位置的元素为e
 76     // 在链表中不是一个常用的操作，练习用：
 77     public void set(int index, E e) {
 78         if (index < 0 || index >= size) {
 79             throw new IllegalArgumentException("Set failed. Illegal index.");
 80         }
 81         Node cur = dummyHead.next;
 82         for (int i = 0; i < index; i++) {
 83             cur = cur.next;
 84         }
 85         cur.e = e;
 86     }
 87     // 查找链表中是否有元素e
 88     public boolean contains(E e) {
 89         Node cur = dummyHead.next;
 90         while (cur != null) {
 91             if (cur.e.equals(e)) {
 92                 return true;
 93             }
 94             cur = cur.next;
 95         }
 96         return false;
 97     }
 98     // 从链表中删除index(0-based)位置的元素, 返回删除的元素
 99     // 在链表中不是一个常用的操作，练习用
100     public E remove(int index) {
101         if (index < 0 || index >= size) {
102             throw new IllegalArgumentException("Remove failed. Index is illegal.");
103         }
104         Node prev = dummyHead;
105         for (int i = 0; i < index; i++) {
106             prev = prev.next;
107         }
108         Node retNode = prev.next;
109         prev.next = retNode.next;
110         retNode.next = null;
111         //疑问：这里为什么不释放结点retNode？
112         size--;
113         return retNode.e;
114     }
115     // 从链表中删除第一个元素, 返回删除的元素
116     public E removeFirst() {
117         return remove(0);
118     }
119     // 从链表中删除最后一个元素, 返回删除的元素
120     public E removeLast() {
121         return remove(size - 1);
122     }
123     // 从链表中删除元素e
124     public void removeElement(E e) {
125         Node prev = dummyHead;
126         while (prev.next != null) {
127             if (prev.next.e.equals(e)) {
128                 break;
129             }
130             prev = prev.next;
131         }
132         if (prev.next != null) {
133             Node delNode = prev.next;
134             prev.next = delNode.next;
135             delNode.next = null;
136             size--;
137         }
138     }
139     @Override
140     public String toString(){
141         StringBuilder res = new StringBuilder();
142         //Node cur = dummyHead.next;
143         //while(cur != null){
144         //    res.append(cur + "->");
145         //    cur = cur.next;
146         //}
147         for(Node cur = dummyHead.next ; cur != null ; cur = cur.next) {
148             res.append(cur + "->");
149         }
150         res.append("NULL");
151         return res.toString();
152     }
　　}

②用递归的方式实现链表

  1 /**
  2  * Recursion
  3  */
  4 public class LinkedListR<E> {
  5     private class Node {
  6         public E e;
  7         public Node next;
  8         public Node(E e, Node next) {
  9             this.e = e;
 10             this.next = next;
 11         }
 12         public Node(E e) {
 13             this(e, null);
 14         }
 15         public Node() {
 16             this(null, null);
 17         }
 18         @Override
 19         public String toString() {
 20             return e.toString();
 21         }
 22     }
 23  
 24     // 在链表的递归实现中，我们不使用虚拟头结点，也能无差异的处理位置0的问题：
 25     private Node head;
 26     private int size;
 27     public LinkedListR() {
 28         head = null;
 29         size = 0;
 30     }
 31     // 获取链表中的元素个数
 32     public int getSize() {
 33         return size;
 34     }
 35     // 返回链表是否为空
 36     public boolean isEmpty() {
 37         return size == 0;
 38     }
 39     // 在链表的index(0-based)位置添加新的元素e
 40     public void add(int index, E e) {
 41         if (index < 0 || index > size) {
 42             throw new IllegalArgumentException("Add failed. Illegal index.");
 43         }
 44         head = add(head, index, e);
 45         size++;
 46     }
 47     // 在以node为头结点的链表的index位置插入元素e，递归算法
 48     private Node add(Node node, int index, E e) {
 49         if (index == 0) {
 50             return new Node(e, node);
 51         }
 52         node.next = add(node.next, index - 1, e);
 53         return node;
 54     }
 55     // 在链表头添加新的元素e
 56     public void addFirst(E e) {
 57         add(0, e);
 58     }
 59     // 在链表末尾添加新的元素e
 60     public void addLast(E e) {
 61         add(size, e);
 62     }
 63     // 获得链表的第index(0-based)个位置的元素
 64     public E get(int index) {
 65         if (index < 0 || index >= size) {
 66             throw new IllegalArgumentException("Get failed. Illegal index.");
 67         }
 68         return get(head, index);
 69     }
 70     // 在以node为头结点的链表中，找到第index个元素，递归算法
 71     private E get(Node node, int index) {
 72         if (index == 0) {
 73             return node.e;
 74         }
 75         return get(node.next, index - 1);
 76     }
 77     // 获得链表的第一个元素
 78     public E getFirst() {
 79         return get(0);
 80     }
 81     // 获得链表的最后一个元素
 82     public E getLast() {
 83         return get(size - 1);
 84     }
 85     // 修改链表的第index(0-based)个位置的元素为e
 86     public void set(int index, E e) {
 87         if (index < 0 || index >= size) {
 88             throw new IllegalArgumentException("Update failed. Illegal index.");
 89         }
 90         set(head, index, e);
 91     }
 92     // 修改以node为头结点的链表中，第index(0-based)个位置的元素为e，递归算法
 93     private void set(Node node, int index, E e) {
 94         if (index == 0) {
 95             node.e = e;
 96             return;
 97         }
 98         set(node.next, index - 1, e);
 99     }
100     // 查找链表中是否有元素e
101     public boolean contains(E e) {
102         return contains(head, e);
103     }
104     // 在以node为头结点的链表中，查找是否存在元素e，递归算法
105     private boolean contains(Node node, E e) {
106         if (node == null) {
107             return false;
108         }
109         if (node.e.equals(e)) {
110             return true;
111         }
112         return contains(node.next, e);
113     }
114     // 从链表中删除index(0-based)位置的元素, 返回删除的元素
115     public E remove(int index) {
116         if (index < 0 || index >= size) {
117             throw new IllegalArgumentException("Remove failed. Index is illegal.");
118         }
119         Pair<Node, E> res = remove(head, index);
120         size--;
121         head = res.getKey();
122         return res.getValue();
123     }
124     // 从以node为头结点的链表中，删除第index位置的元素，递归算法
125     // 返回值包含两个元素，删除后的链表头结点和删除的值：）
126     private Pair<Node, E> remove(Node node, int index) {
127         if (index == 0) {
128             return new Pair<>(node.next, node.e);
129         }
130         Pair<Node, E> res = remove(node.next, index - 1);
131         node.next = res.getKey();
132         return new Pair<>(node, res.getValue());
133     }
134     // 从链表中删除第一个元素, 返回删除的元素
135     public E removeFirst() {
136         return remove(0);
137     }
138     // 从链表中删除最后一个元素, 返回删除的元素
139     public E removeLast() {
140         return remove(size - 1);
141     }
142     // 从链表中删除元素e
143     public void removeElement(E e) {
144         head = removeElement(head, e);
145     }
146     // 从以node为头结点的链表中，删除元素e，递归算法
147     private Node removeElement(Node node, E e) {
148         if (node == null) {
149             return null;
150         }
151         if (node.e.equals(e)) {
152             size--;
153             return node.next;
154         }
155         node.next = removeElement(node.next, e);
156         return node;
157     }
158     @Override
159     public String toString() {
160         StringBuilder res = new StringBuilder();
161         Node cur = head;
162         while (cur != null) {
163             res.append(cur + "->");
164             cur = cur.next;
165         }
166         res.append("NULL");
167         return res.toString();
168     }
169 }