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{ 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 ){ 128 if(array[i]==null){ 129 fastRemove(i); 130 } 131 } 132 }else{ 133 for(int i=0;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 ){ 235 if(e==array[i]){ 236 return i; 237 } 238 } 239 } 240 for(int i=0;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 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 list = new LineList (); 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{ 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{ 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 res = remove(head, index); 120 size--; 121 head = res.getKey(); 122 return res.getValue(); 123 } 124 // 从以node为头结点的链表中,删除第index位置的元素,递归算法 125 // 返回值包含两个元素,删除后的链表头结点和删除的值:) 126 private Pair remove(Node node, int index) { 127 if (index == 0) { 128 return new Pair<>(node.next, node.e); 129 } 130 Pair 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 }