有没有做微信的动态图网站,外链收录网站,手机百度下载,wordpress怎么安装?一、前言
从今天开始#xff0c;笔者也开始从0学习数据结构和算法#xff0c;但是因为这次学习比较捉急#xff0c;所以记录的内容并不会过于详细#xff0c;会从基础和底层代码实现以及力扣相关题目去写相关的文章#xff0c;对于详细的概念并不会过多讲解
二、数组基础…一、前言
从今天开始笔者也开始从0学习数据结构和算法但是因为这次学习比较捉急所以记录的内容并不会过于详细会从基础和底层代码实现以及力扣相关题目去写相关的文章对于详细的概念并不会过多讲解
二、数组基础
数组这个结构其实就是将数据码成一排进行存放 如上就是一个数组有6个空间可以存放6个元素。且命名可以随意例如我student数组可以叫students也可以是studentList。 具体这个元素是什么类型在Java中要求是固定的比如6个Int类型6个String类型或者6个Object自定义类型。在数组中有一个很重要的概念叫作索引 在计算机的视角中索引从0开始之后依次递增如果我们数组空间为n那我们最后一个元素的索引是n-1,第一个元素的索引是0有了索引我们就可以直接访问数组第i个元素是什么。 例如我现在要对students数组中取索引为2的数据那么students[2]即可取出而students[2]对应的是数组的第三个元素。 索引可以有语意也可以没有语意。例如我是一个学生列表我的学生学号就对应的索引此时索引有语意。再或者说我是一个分数列表那对于这个列表的元素分数想放在哪个索引对应的空间就放在哪里此时索引没有语意。
代码实现
在java中如果我要声明一个数组非常简单 比如我声明一个Int类型的数组就是int[] arrString类型数组就是String[] 而给这个数组赋值的对象可以通过new int[n]/new String[n]这样的形式n代表你想开辟的数组的空间大小例如拿上面的6个空间的数组举例 public static void main(String[] args) {//想要使用数组就需要事先开辟空间就必须声明数组能装多少个元素int[] arr new int[6];}而我们要对这个数组进行赋值操作也很简单写一个for循环我们可以根据java中数组的方法arr.length()对其进行循环为数组的每一个元素进行赋值吗arr.length()就是代表这个数组的长度即数组的空间大小,然后arr[i] i即可为数组的每一个元素赋值。 public static void main(String[] args) {//想要使用数组就需要事先开辟空间就必须声明数组能装多少个元素int[] arr new int[6];for (int i 0; i arr.length; i) {arr[i] i;}}而通过arr.length()去进行for循环比你要通过直接拿一个具体的数字硬编码的形式去进行赋值要好很多代码更加的灵活例如你的数组长度可能会发生变化你通过arr.length()的话只需要专注于你的数组长度即可。 当然java中声明数组有另外的形式当你想要在数组声明的时候就有它的初始值那这种情况下new int[]方括号内就可以不带空间大小而是通过new int[]{}的形式花括号内填写元素的初始值。 例如我声明一个scores数组初始化3个初始值我就可以这样写
int[] scores new int[]{99,100,98};这样我们的数组就开辟成有3个Int值的数组我们可以写一个for循环打印验证下
int[] scores new int[]{99,100,98};for (int i 0; i scores.length; i) {System.out.println(scores[i]);}当然你也可以使用java的for增强循环意义就是在scores数组中取出每一个score元素。在这个基础上我把每一个score元素的值打印出来这种特性是因为数组有这可迭代的能力或者叫作可遍历的能力这里不过多强调。
int[] scores new int[]{99,100,98};for (int score : scores) {System.out.println(score);}大家都可以试一下两种形式的结果都是一样的。 而我们如果想要修改数组中元素的值也非常简单比如我想将上面的scores索引为0的元素的值修改为100代码如下
scores[0] 100;数组优点
数组最大的优点就是快速查询例如students[2],快速查询索引为2的学生。 之前我们讲解索引的时候说过索引有语意和没有语意的区别那么为了更好地放大数组的优点数组最好应用于“索引有语意”的情况。而对于索引没有语意的情况往往会使用其他的数据结构进行查询这就是后话了。 很多场景中虽然我们能给索引定义出来语意但并非所有语意的索引都适用于数组例如我想通过以人的身份证号作为索引去找对应的人的一些属性。而由于身份证号作为索引一般都非常的大对于计算机来说开辟一个身份证号数字大小的空间是不值当甚至不可能的且就算可以也会浪费相当多的空间例如我数组就十个人我要用身份证号作为索引去开辟那势必会浪费特别大的空间。
在索引无语义的情况下使用数组 如果索引有语意那么使用数组就太简单了直接根据索引查询具体的元素即可 但是如果我们就是使用数组去处理索引没有语意的情况也可以处理但是会出现很多新的问题 ①数组只是一个提供待存放元素的空间的工具 例如我们的数组有6个空间但是我们现在需要考察的或者说只放了三个元素那么访问没有元素的空间可能就是非法的因为从用户的角度来看是没有3,4,5对应的元素的。 那么问题一就是索引没有语意如何表示没有元素的空间 问题二如何添加元素如何删除元素例如我们之前创建数组的时候已经规定好了大小如果我们要再往其中添加元素超过了预定的空间大小该怎么办呢这些都会一一解决。 而java为我们提供的数组是没有这些方法的我们必须自己编写 其实我们可以将Java提供的数组称为静态数组我们自己编写的数组称为动态数组。 由于数组本身是静态的,创建的时候必须指定它的大小我们管这个叫容量capacity也就是我们的数组空间最多可以装多少个元素。 ps:我们数组空间最多可以装多少个元素和我们数组空间实际有多少个元素没有关系。我们把数组空间实际有多少个元素称为size,而数组初始化的时候一个元素都没有此时size0,其实就指向了第一个没有元素的索引。而后面对数组操作的时候我们就需要维护数组的size例如增加或者删除元素的时候。 动态数组代码实现
那么我们现在就可以实现开始的动态数组了
package com.mbw.Array;public class DynamicArray {//初始化数组private int[] array;//数组实际元素个数private int size;//之前讲解过capacity容量这个属性其实它本质上等于array.length,所以没有必要设计//带有初始容量的构造函数public DynamicArray(int capacity){array new int[capacity];size 0;}//不带初始容量的构造函数所以我们给它预先创建一个容量为10的数组容量够不够后面可以解决public DynamicArray(){array new int[10];size 0;}//判断数组是否为空public boolean isEmpty(){return size 0;}//获取数组当前元素个数public int gitSize(){return size;}//获取数组容量public int getLength(){return array.length;}
}三、向动态数组中添加元素
①向数组末尾添加元素 之前说过size指向数组中第一个没有元素的索引,我们向数组末尾添加元素其实就相当于在size的位置添加元素例如我们现在需要向数组末尾添加一个66的元素其实就相当于是在size0这个位置添加一个66的元素与此同时由于元素个数为1size1往后挪一格指向索引为1的没有元素的位置。 那么按照这样的逻辑我们的代码可以这样写 public void addLast(int e){array[size] e;size ;}②向任意位置添加元素 比如我现在想要在索引为1的位置添加一个元素那么我从size-1的索引对应的元素开始一直到Index对应的元素为止这中间的所有原来的元素都要往后挪动一格然后此时index对应的元素虽然还是原来的值但是此时我们可以将它放心的把新的值赋值给它了。因为此时我其他的元素已经做了往后挪的处理。最后将size即可。 那么由上述逻辑我们可以写出以下程序
public void add(int index, int e) {//如果size容量则报错if (size array.length) {throw new IllegalArgumentException(add failed,array is full);}//如果index比size还要大(中间会出现非法元素)或者index0也需报错if (index 0 || index size) {throw new IllegalArgumentException(add failed,index should 0 or index size);}//如果此时index 就等于 size此时相当于前面的向数组末尾增加元素不用走for循环if (index size) {array[index] e;size;return;}//然后从最后一个元素开始一直到需要添加的位置为结尾将该元素赋值给后一个空间for (int i size - 1; i index; i--) {array[i 1] array[i];}array[index] e;size;}那么有了上述逻辑代码其实我们之前写的向数组末尾添加元素就可以改写为
//往数组末尾添加元素public void addLast(int e) {add(size, e);}那想必你还可以拓展向数组头增加元素的方法
public void addFirst(int e) {add(0, e);}然后我们就可以试一下为了方便后续验证我们可以重写toString()方便我们查看数组详情 Overridepublic String toString() {return DynamicArray{ array Arrays.toString(array) , size size , capacity getLength() };}然后试一下刚才我们写的add(): public static void main(String[] args) {DynamicArray dynamicArray new DynamicArray();dynamicArray.add(dynamicArray.size, 20);dynamicArray.add(dynamicArray.size, 23);dynamicArray.add(dynamicArray.size, 25);dynamicArray.addLast(100);dynamicArray.addFirst(10);dynamicArray.add(1, 30);System.out.println(dynamicArray.toString());}四、获取数组索引对应的元素和修改对应索引的元素
这两个方法都比较简单 ①获取数组索引对应的元素 我们需要注意index的范围Index0不用多说当Indexsize我们知道size是指向第一个没有元素的索引所以我们自然不能让index等于size哪怕size指向的这个元素确实因为删除方法有值但其实这个元素仍然是非法的我们不能让用户访问到。 //获取index索引上的元素public int get(int index){if(index 0 || index size){throw new IllegalArgumentException(get failed;index should 0 or index size);}return array[index];}②修改Index索引对应的元素 同理我们可以写出以下代码 //修改Index索引上的元素public void set(int index, int e){if(index 0 || index size){throw new IllegalArgumentException(get failed;index should 0 or index size);}array[index] e;}五、包含、搜索和删除
首先说一下包含 ①查看元素是否存在数组当中 逻辑很简单我们只需从索引为0开始size为结尾遍历一遍我们的数组如果存在那么就返回true如果没有则返回false //查看数组是否包含epublic boolean contains(int e){for(int i 0;i size; i){if(array[i] e){return true;}}return false;}②返回具体元素对应的索引 这个逻辑其实很像上述之前的包含若存在则返回找到的元素的索引没找到返回无效索引-1 public int find(int e){for(int i 0;i size; i){if(array[i] e){return 1;}}return -1;}但是有些比较细心的朋友可能会觉得这个程序存在纰漏如果我的数组存在同样的元素值那这个就不太对了我们这个程序顶多称为若存在则返回找到的第一个元素的索引没找到返回无效索引-1。如果需要详细一点可以返回一个int数组或者列表将找到的元素对应的索引全部放到其中返回。 ③删除指定位置元素 删除其实逻辑很简单了解了add其实就是从最后一个元素开始一直到index对应的索引位置结束将其中的元素往后挪一个位置删除就是反过来我们从要删除的索引的后一个位置开始一直到size前一个数组最后一个有值元素对应的空间索引对应的元素往前挪一格其实说是挪动更像是一次赋值,最后size别忘了减一 可能有伙伴会觉得我这样删除size减一后不就和它的意义不一致了吗因为我的size指向的是第一个没有元素的空间现在却指向了往前挪动的所有元素中最后一个索引对应的元素可是大家可以想一下size指向了有值的元素对客户是否有影响呢其实是没有的客户通过方法是访问不到size对应的元素的值的也不会影响我的add等操作所以其实size–后存在有值元素也不会影响后续的操作那么根据上述逻辑我们可以完成删除代码 //从数组中删除Index位置的元素返回删除的元素public int remove(int index{//如果size容量则报错//如果index比size还要大(中间会出现非法元素)或者index0也需报错if (index 0 || index size) {throw new IllegalArgumentException(add failed,index should 0 or index size);}int result array[index];for(int i index 1;i size ; i){array[i-1] array[i];}size --;return result;}那有了删除代码我们可以同add完成删除第一个和删除最后一个元素 public int removeFirst(){return remove(0);}public int removeLast(){return remove(size - 1);}且大家可以不用担心删除空数组删除的情况如果说此时数组是空数组size0调用删除第一个元素方法index0,那么会被上面remove的if语句中size index命中从而抛出异常如果调用删除最后一个元素的方法idex-1-1,从而被上面remove的if语句中index 0命中从而抛出异常. 那我们有些朋友可能不想删除指定位置的元素而是想从数组中删除特定元素的值。那么我们就可以结合之前的find()和remove()完成这个操作需要注意的是由于find存在只能找到第一个元素对应的索引的问题我们的这个删除特定元素方法也只能删除一个如果数组存在相同元素的话那么其实是没有删除干净的感兴趣的小伙伴可以自行拓展 public void deleteElement(int e){int index find(e);if(index ! -1){remove(index);}}我们可以试验一下
public static void main(String[] args) {DynamicArray dynamicArray new DynamicArray();dynamicArray.add(dynamicArray.size, 20);dynamicArray.add(dynamicArray.size, 23);dynamicArray.add(dynamicArray.size, 25);dynamicArray.addLast(100);dynamicArray.addFirst(10);dynamicArray.add(1, 30);System.out.println(dynamicArray.toString());//删除四个元素dynamicArray.remove(1);dynamicArray.deleteElement(100);dynamicArray.removeFirst();dynamicArray.removeLast();System.out.println(dynamicArray.toString());}最后应该剩下的就是20,23结果也是正确的size2,前两个元素就是20,23. 感兴趣的小伙伴还可以对这个基础的数组进行扩展比如添加泛型等等这个届时和后面的动态数组的拓展代码我会一起给一个示范代码
package com.mbw.array;import java.util.Arrays;public class DynamicArrayT {//初始化数组private T[] array;//数组实际元素个数private int size;//之前讲解过capacity容量这个属性其实它本质上等于array.length,所以没有必要设计//带有初始容量的构造函数public DynamicArray(int capacity) {array (T[])new Object[capacity];size 0;}//不带初始容量的构造函数所以我们给它预先创建一个容量为10的数组容量够不够后面可以解决public DynamicArray() {array (T[])new Object[10];size 0;}//判断数组是否为空public boolean isEmpty() {return size 0;}//获取数组当前元素个数public int gitSize() {return size;}//获取数组容量public int getLength() {return array.length;}//往数组末尾添加元素public void addLast(T e) {add(size, e);}public void addFirst(T e) {add(0, e);}public void add(int index, T e) {//如果size容量则报错if (size array.length) {throw new IllegalArgumentException(add failed,array is full);}//如果index比size还要大(中间会出现非法元素)或者index0也需报错if (index 0 || index size) {throw new IllegalArgumentException(add failed,index should 0 or index size);}if (index size) {array[index] e;size;return;}//然后从最后一个元素开始一直到需要添加的位置为结尾将该元素赋值给后一个空间for (int i size - 1; i index; i--) {array[i 1] array[i];}array[index] e;size;}//获取index索引上的元素public T get(int index){if(index 0 || index size){throw new IllegalArgumentException(get failed;index should 0 or index size);}return array[index];}//修改Index索引上的元素public void set(int index, T e){if(index 0 || index size){throw new IllegalArgumentException(get failed;index should 0 or index size);}array[index] e;}//查看数组是否包含epublic boolean contains(T e){for(int i 0;i size; i){if(array[i] e){return true;}}return false;}//查看元素对应的数组索引位置,若存在则返回找到的第一个元素的索引没找到返回无效索引-1public int find(T e){for(int i 0;i size; i){if(array[i] e){return i;}}return -1;}//从数组中删除Index位置的元素返回删除的元素public T remove(int index){//如果size容量则报错//如果index比size还要大(中间会出现非法元素)或者index0也需报错if (index 0 || index size) {throw new IllegalArgumentException(add failed,index should 0 or index size);}T result array[index];for(int i index 1;i size ; i){array[i-1] array[i];}size --;return result;}public T removeFirst(){return remove(0);}public T removeLast(){return remove(size - 1);}public void deleteElement(T e){int index find(e);if(index ! -1){remove(index);}}Overridepublic String toString() {return DynamicArray{ array Arrays.toString(array) , size size , capacity getLength() };}public static void main(String[] args) {DynamicArrayInteger dynamicArray new DynamicArray();dynamicArray.add(dynamicArray.size, 20);dynamicArray.add(dynamicArray.size, 23);dynamicArray.add(dynamicArray.size, 25);dynamicArray.addLast(100);dynamicArray.addFirst(10);dynamicArray.add(1, 30);System.out.println(dynamicArray.toString());dynamicArray.remove(1);dynamicArray.deleteElement(100);Integer removeFirst dynamicArray.removeFirst();Integer removeLast dynamicArray.removeLast();System.out.println(removeFirst);System.out.println(removeLast);System.out.println(dynamicArray.toString());}
}六、动态数组
我们之前实现的数组仍然存在一个问题它内部其实使用的还是一个java的静态数组对于静态数组来说它的容量是有限的可是很多时候我们使用数组类很难预估我们究竟会放多少元素类容量太大浪费空间容量太小又有可能不够用所以我们需要一种解决方案使得我们数组容量是可伸缩的这就是动态数组。 例如对于下面一个capacity4的数组目前已经放满了如果我还想接着往下增加元素根据现有逻辑是会抛出异常的但是我们可以通过一些其他方法实现这个操作我们可以开辟一个新的数组newData新的数组要比原来的容量大上一些比如之前是4个空间我新数组的容量就是8然后将原来数组的元素放到新数组newData中从而达成通过NewData取代原来的数组并且扩容的目的。 那么对于扩容的大小我们更希望它能和原来的数组是成比例的正相关的而不是在其基础上增加一个固定的常数比如我如果固定增加的太小那么当我的数组容量达到很大时候这个时候就会频繁触发扩容反之扩容一次增加的容量太大那么在一开始数组容量很小的时候一次性扩容很大的容量就会造成很多的空间浪费。所以我们就每次扩容为原来数组的2倍即可。当然关于倍数的选择和你具体的业务有关拿我们java的动态数组arrayList来说它每次扩容就是原来的1.5倍。 所以我们可以有如下代码
private void resize(int newCapacity){T[] newArray (T[])new Object[newCapacity];for (int i 0; i size; i) {newArray[i] array[i];}array newArray;}如上risize()扩容方法大家可能会想for循环每次新增一旦需要扩容每次都要for循环会不会太影响效率这个我们后面的文章会专门解析这个问题。而对于引用问题原来的数组由于我们将新数组替代它了原来的数组就会被java的垃圾回收机制回收掉不会影响内存空间。下面我们就可以应用resize()了 在add方法如果满了则扩容为原来2倍 public void add(int index, T e) {//如果index比size还要大(中间会出现非法元素)或者index0也需报错if (index 0 || index size) {throw new IllegalArgumentException(add failed,index should 0 or index size);}//如果size容量则自动扩容每次扩容为原来数组容量的2倍if (size array.length) {resize(2 * array.length);}if (index size) {array[index] e;size;return;}//然后从最后一个元素开始一直到需要添加的位置为结尾将该元素赋值给后一个空间for (int i size - 1; i index; i--) {array[i 1] array[i];}array[index] e;size;}在remove方法如果发现当前size是数组容量的1/2那么我们可以将数组缩小为原来的1/2 public T remove(int index) {//如果size容量则报错//如果index比size还要大(中间会出现非法元素)或者index0也需报错if (index 0 || index size) {throw new IllegalArgumentException(add failed,index should 0 or index size);}T result array[index];for (int i index 1; i size; i) {array[i - 1] array[i];}size--;//如果发现size当前数组容量一半则将数组缩容至原来一半if (size array.length / 2) {resize(array.length / 2);}return result;}然后我们可以测试一下
public static void main(String[] args) {DynamicArrayInteger dynamicArray new DynamicArray();for (int i 0; i dynamicArray.getLength(); i) {dynamicArray.addLast(i);}System.out.println(dynamicArray.toString());dynamicArray.addLast(100);System.out.println(dynamicArray.toString());dynamicArray.addFirst(101);System.out.println(dynamicArray.toString());dynamicArray.removeLast();dynamicArray.removeLast();System.out.println(dynamicArray.toString());}结果符合代码逻辑至此我们从底层实现的自定义动态数组就完成了。 而对于泛型数组这里我给一个整体的代码实现有java功底的朋友应该不会觉得困难
package com.mbw.array;import java.util.Arrays;public class DynamicArrayT {//初始化数组private T[] array;//数组实际元素个数private int size;//之前讲解过capacity容量这个属性其实它本质上等于array.length,所以没有必要设计//带有初始容量的构造函数public DynamicArray(int capacity) {array (T[]) new Object[capacity];size 0;}//不带初始容量的构造函数所以我们给它预先创建一个容量为10的数组容量够不够后面可以解决public DynamicArray() {array (T[]) new Object[10];size 0;}//判断数组是否为空public boolean isEmpty() {return size 0;}//获取数组当前元素个数public int gitSize() {return size;}//获取数组容量public int getLength() {return array.length;}//往数组末尾添加元素public void addLast(T e) {add(size, e);}public void addFirst(T e) {add(0, e);}public void add(int index, T e) {//如果index比size还要大(中间会出现非法元素)或者index0也需报错if (index 0 || index size) {throw new IllegalArgumentException(add failed,index should 0 or index size);}//如果size容量则自动扩容每次扩容为原来数组容量的2倍if (size array.length) {resize(2 * array.length);}if (index size) {array[index] e;size;return;}//然后从最后一个元素开始一直到需要添加的位置为结尾将该元素赋值给后一个空间for (int i size - 1; i index; i--) {array[i 1] array[i];}array[index] e;size;}//获取index索引上的元素public T get(int index) {if (index 0 || index size) {throw new IllegalArgumentException(get failed;index should 0 or index size);}return array[index];}//修改Index索引上的元素public void set(int index, T e) {if (index 0 || index size) {throw new IllegalArgumentException(get failed;index should 0 or index size);}array[index] e;}//查看数组是否包含epublic boolean contains(T e) {for (int i 0; i size; i) {if (array[i] e) {return true;}}return false;}//查看元素对应的数组索引位置,若存在则返回找到的第一个元素的索引没找到返回无效索引-1public int find(T e) {for (int i 0; i size; i) {if (array[i] e) {return i;}}return -1;}//从数组中删除Index位置的元素返回删除的元素public T remove(int index) {//如果size容量则报错//如果index比size还要大(中间会出现非法元素)或者index0也需报错if (index 0 || index size) {throw new IllegalArgumentException(add failed,index should 0 or index size);}T result array[index];for (int i index 1; i size; i) {array[i - 1] array[i];}size--;//如果发现size当前数组容量一半则将数组缩容至原来一半if (size array.length / 2) {resize(array.length / 2);}return result;}public T removeFirst() {return remove(0);}public T removeLast() {return remove(size - 1);}public void deleteElement(T e) {int index find(e);if (index ! -1) {remove(index);}}Overridepublic String toString() {return DynamicArray{ array Arrays.toString(array) , size size , capacity getLength() };}public static void main(String[] args) {DynamicArrayInteger dynamicArray new DynamicArray();for (int i 0; i dynamicArray.getLength(); i) {dynamicArray.addLast(i);}System.out.println(dynamicArray.toString());dynamicArray.addLast(100);System.out.println(dynamicArray.toString());dynamicArray.addFirst(101);System.out.println(dynamicArray.toString());dynamicArray.removeLast();dynamicArray.removeLast();System.out.println(dynamicArray.toString());}private void resize(int newCapacity) {T[] newArray (T[]) new Object[newCapacity];for (int i 0; i size; i) {newArray[i] array[i];}array newArray;}
}
