【Java】List接口的应用，与C++中vector应用比较 (一)

Dear 丶 2022-08-22 01:19 205阅读 0赞

【写作原因】

在解决【LeetCode.113 Path Sum II】时，我分别采用Java和C++，感觉其中差异有整理一下的必要。

【动态数组的创建】

在编程中，很多情况下，在预编译过程阶段，数组的长度是不能预先知道的，必须在程序运行时动态的给出，但是问题是，编程语言C/C++、Java要求定义数组时，必须明确给定数组的大小，要不然编译通不过。形如LeetCode113题，求满足要求的二叉树路径，由于二叉树结构多样，遍历路径繁多，事先无法确定路径长度。这时候，我们需要创建一个容量可以根据实际需要变化数组（或者存储器）。

**\[一\]****在C++中，最常用的方法是：采用new方法创建动态数组和采用vector容器来创建可变长数组**。

1、new 方法：int \*p=new int\[num\];创建一个容量为num的int型数组，num可来自外部输入、函数传递等，int型指针p指向动态数组的首地址，在动态数组创建完成后，我们可以下标访问数组元素：p\[0\],p\[1\]...，但是new方法不能创建二维数组，只能创建一维数组，并且创建后数据元素操作缺乏灵活性；用得最多的地方当属创建链表结点；

2、vector容器：相比于new方法，vector容器功能非常强大，具有高度的灵活性，常用基本操作：

(1)头文件\#include<vector>.

(2)创建一维vector对象，vector<int> vec;二维vector<vector<int>> vec2;

(3)尾部插入数字：vec.push\_back(a);

(4)尾部元素弹出：vec.pop\_back();相当于删除尾部元素；

(5)使用下标访问元素，cout<<vec\[0\]<<endl;记住下标是从0开始的,和数组的访问形式一样。

(6)插入元素：vec.insert(vec.begin()+i,a);在第i+1个元素前面插入a;

(7)删除元素：vec.erase(vec.begin()+2);删除第3个元素

vec.erase(vec.begin()+i,vec.end()+j);删除区间\[i,j-1\];区间从0开始

(8)向量大小:vec.size();

(9)清空:vec.clear();

(10)初始化赋值：  
   vector c1(c2)      // 复制一个vector（c2也是一个vector）  
   vector c(n)        // 创建一个vector，含有n个数据，数据均已缺省构造产生  
   vector c(n, elem) // 创建一个含有n个elem元素的vector  
   vector c(beg,end) // int array\[\]=\{1,2,3\}，beg=array,end=array+3，用数组为vector赋值

由于我们可以通过push\_back()和pop\_back()这两个函数动态改变vector中数据，从而采用vector很容易实现动态存储空间的建立，这种方法在C++中应用极为广泛。

3、常用算法

1) 使用reverse将元素翻转：需要头文件\#include<algorithm>

reverse(vec.begin(),vec.end());将元素翻转(在vector中，如果一个函数中需要两个迭代器，一般后一个都不包含.)

2) 使用sort排序：需要头文件\#include<algorithm>，

sort(vec.begin(),vec.end());(默认是按升序排列,即从小到大).

可以通过重写排序比较函数按照降序比较，如下：

定义排序比较函数：

bool Comp(int a,int b)  
                      \{  
                             return a>b;  
                       \}  
            调用时:sort(vec.begin(),vec.end(),Comp)，这样就降序排序。

**\[二\] 在Java中，最常用的方式是：采用ArrayList和List接口**

java集合的主要分为三种类型：  
             Set（集）  
             List（列表）  
             Map（映射）  
      要深入理解集合首先要了解下我们熟悉的数组：数组是大小固定的，并且同一个数组只能存放类型一样的数据（基本类型/引用类型），而JAVA集合可以存储和操作数目不固定的一组数据。 所有的JAVA集合都位于 java.util包中！ 在Java中有一个Array类，专门用于操作数组，很有用，但是，它无法实现数组的容量动态增减，所以，要用到集合，集合有很多优点，这个问题可以单独写篇文章了，这里不详述了！！！

1、ArrayList：Java动态数组是一种可以任意伸缩数组长度的对象，在Java中比较常用的是ArrayList创建动态数组，简单例子：

ArrayList temp = new ArrayList(); //创建一个ArrayList对象，temp为对象的引用
    for( int i=0;i <10;i++ ) //给数组增加10个Int元素 
    temp.Add(i); 
    temp.RemoveAt(5);//将第6个元素移除 
    for( int i=0;i<3;i++ ) //再增加3个元素 
    temp.Add(i+20); 
    Int32[] values = (Int32[])temp.ToArray(typeof(Int32));//返回ArrayList包含的数组

1）ArrayList是Array的复杂版本   
ArrayList内部封装了一个Object类型的数组，从一般的意义来说，它和数组没有本质的差别，甚至于ArrayList的许多方法，如Index、IndexOf、Contains、Sort等都是在内部数组的基础上直接调用Array的对应方法。   
    2）内部的Object类型的影响   
对于一般的引用类型来说，这部分的影响不是很大，但是对于值类型来说，往ArrayList里面添加和修改元素，都会引起装箱和拆箱的操作，频繁的操作可能会影响一部分效率。 但是恰恰对于大多数人，多数的应用都是使用值类型的数组。   
消除这个影响是没有办法的，除非你不用它，否则就要承担一部分的效率损失，不过这部分的损失不会很大。   
    3）数组扩容   
这是对ArrayList效率影响比较大的一个因素。   
每当执行Add、AddRange、Insert、InsertRange等添加元素的方法，都会检查内部数组的容量是否不够了，如果是，它就会以当前容量的两倍来重新构建一个数组，将旧元素Copy到新数组中，然后丢弃旧数组，在这个临界点的扩容操作，应该来说是比较影响效率的。

2、Java中List接口：

我们知道，Java中，接口不是类，不能使用new方法进行实例化；但是，接口可以声明接口变量，如List temp;接口变量必须引用实现了接口的类的对象，如ArrayList类实现了List接口，那么：List<String> temp=new ArrayList<String>()就是合法的。

List的特征是其元素以线性方式存储，集合中可以存放重复对象。 List接口主要实现类包括：  
       (1) ArrayList() : 代表长度可以改变得数组。可以对元素进行随机的访问，向ArrayList()中插入与删除元素的速度慢。   
       (2)LinkedList(): 在实现中采用链表数据结构。插入和删除速度快，访问速度慢。

List接口常用方法如下：

![Center][]

通过上述List接口提供的方法，我们可以对List列表中的数据进行“丰富”的操作，下面以一个实例来理解List接口的应用：【LeetCode】113. Path Sum II 解法：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public List<List<Integer>> pathSum(TreeNode root, int sum) 
        {
    	   List<List<Integer>> result=new ArrayList<List<Integer>>();//List接口引用ArrayList类的对象
    	   List<Integer> temp=new ArrayList<Integer>();//List引用ArrayList对象，存放当前路径
    	   
    	   if(root==null)return result;
    	   DFS(result,temp,root,sum);
    	   return result;
        }
        
        void DFS(List<List<Integer>> result,List<Integer> temp,TreeNode root,int sum)
        {
    	   if(root==null)return;
    	   if(root.left==null&&root.right==null)
    	   {
    		   temp.add(root.val);//当前路径中添加元素
    		   if(sumOfPath(temp)==sum)
    			   result.add(new ArrayList(temp));//注意List接口的add()方法的用法
    		   temp.remove(temp.size()-1);//当前路径末端元素弹出，注意下标从0开始
    		   return;
    	   }
    	   else
    	   {
    		   temp.add(root.val);//当前路径添加元素，采用add()
    		   DFS(result,temp,root.left,sum);
    		   DFS(result,temp,root.right,sum);
    		   temp.remove(temp.size()-1);//当前路径弹出末端元素
    	   }
       }
       
       int sumOfPath(List<Integer> temp)
       {
    	   int sum=0;
    	   for(int i=0;i<temp.size();i++)
    	   {
    		   sum+=temp.get(i);//采用get()方法获取下标为i的元素
    	   }
    	   return sum;
       }
    }

后续再补充......

看考文章：[http://blog.csdn.net/speedme/article/details/22398395][http_blog.csdn.net_speedme_article_details_22398395]

[Center]: /images/20220724/6784e1bee33344e2bd8c11fd5cae84f1.png
[http_blog.csdn.net_speedme_article_details_22398395]: http://blog.csdn.net/speedme/article/details/22398395