欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Arrays工具、二维数组以及LeetCode练习题

程序员文章站 2022-03-30 21:17:33
1 Arrays PS:Arrays位于java.util包下 使用二分法查询 key 元素在 a 数组中的索引,如果数组不包含这个值,则返回负数。使用前要求这个数组是升序排列,才能得到正确结果。 1 int binarySearch(type[] a, int fromIndex, int toI ......

1 arrays

ps:arrays位于java.util包下

1 int binarysearch(type[] a, type key); 

使用二分法查询 key 元素在 a 数组中的索引,如果数组不包含这个值,则返回负数。使用前要求这个数组是升序排列,才能得到正确结果。

1 int binarysearch(type[] a, int fromindex, int toindex, type key);
和上面类似,但是只从 fromindex 到 toindex 范围内找元素,一样要求数组是升序的。
1 type[] copyof(type[] originla , int length);

复制一个数组,length 是新数组的长度。如果 length 小于原数组,则只复制前length长度的值;如果大于原数组,后面补0、false、null。

1 type[] copyof(type[] originla , int from, int to);

与前面类似,但是只复制规定范围内的元素。

1 boolean equals(type[] a1 , type[] a2) 

如果 a1 和 a2 长度相等且元素相同,则返回 true,否则返回false。

1 void fill(type[] a , type val) 

该方法会把 a 数组的所有元素都赋值为val的值。

1 void fill(type[] , int fromindex , int toindex, type val)

与上方法类似,规定了范围。

1 void sort(type[] a) 

该方法对 a 数组的元素进行升序排列。特别的是,如果 a 是字符串数组,则按照字符串长度的升序排列。

1 void sort(type[] a , int fromindex int toindex) 

类似,仅对范围内排序。

1 string tostring(type[] a) 

将一个数组转换成一个字符串,该方法按顺序把多个数组元素连成一个字符串,用逗号和空格分隔每个元素,外面用 '[' 、']'括起来。

2 java 8 之后 arrays 增强功能

下面方法中,parallel 代表可以用多 cpu 提高性能,xxx 或 xxx 代表数据类型,比如int,double
1 void parallelprefix(xxx[] array, xxxbinaryoperator op) 
2 void parallelprefix(xxx[] array , int fromindex , toindex , xxxbinaryoperator op)

该方法使用 op 参数指定的计算公式计算得到的结果作为新的数组元素。op 计算公式包括 left 、 right 两个形参,其中 left 代表新数组中钱一个前一个索引处的元素,right 代表 array 数组中当前索引处的元素。新数组的第一个元素无须计算,直接等于 array数组的第一个元素。

1 void setall(xxx[] array , inttoxxxfunction generator)

该方法用指定的生成器为所有数组元素设置值,该生成器控制数组元素的值的生成算法。

1 void parallelsetall(xxx[] array , inttoxxxfunction generator)

与上方法类似,增加了并行能力,利用多 cpu 提升性能

1 void parallelsort (xxx[] a) 
2 void parallelsort (xxx[] a , int fromindex , int toindex)

与之前arrays里面的sort方法类似,增加了并行能力,可以利用多 cpu 提高性能。

增强功能的程序示例:

 1 import java.util.arrays;
 2 import java.util.function.intbinaryoperator;
 3 import java.util.function.intunaryoperator;
 4 public class arraystest {
 5     public static void main(string[] args) {
 6         int[] array1 = new int[] {3, -4, 25, 16, 30, 18};
 7         //用arrays类的方法排序
 8         arrays.parallelsort(array1);
 9         system.out.println(arrays.tostring(array1));
10         int[] array2 = new int[] {3, -4, 25, 16, 30, 18};
11         //前一个索引的元素乘以当前元素得到新数组,需要import java.util.function.intbinaryoperator
12         arrays.parallelprefix(array2, new intbinaryoperator() {
13             public int applyasint(int left , int right) {
14                 return left * right;
15             }
16         });
17         system.out.println(arrays.tostring(array2));
18         int array3[] = new int[5];
19         //使用当前索引*5的方法生成元素,需要import java.util.function.intunaryoperator
20         arrays.parallelsetall(array3, new intunaryoperator() {
21              //operand 是当前索引
22             public int applyasint(int operand) {
23                 return operand * 5;
24             }
25         });
26         system.out.println(arrays.tostring(array3));
27     }
28 }

输出结果:

Arrays工具、二维数组以及LeetCode练习题

3 二维数组

3.1 二维数组原理

因为数组元素可以是引用类型,所以可以让数组作为数组的元素,这样就产生了二维数组。java 中二维数组不要求是矩阵形式。

3.2 定义二维数组

1 type[][] arrayname; 

其实质还是一维数组,只是数组的元素也是引用。

3.3 初始化

1 arrayname = new type[length][] 

这里相当于定义了 length 个type[]类型的变量。接下来继续初始化

1 arrayname[0] = new type[2] 

这里把一个长度为2的数组赋给前面定义的一维数组的第一个元素,此时arrayname[0][0]和arrayname[0][1]的值都是0(如果type是 int 的时候),一维数组的其它元素都是null;

一个初始化好的二维数组在内存中的示意图:

Arrays工具、二维数组以及LeetCode练习题

3.4 常用初始化方法

  • 同时定义二维数组的两个维数(矩形数组)
1 int[][] arrayname = new int[3][4]
  • 显示定义(静态)二维数组(不一定是矩形)
1 int [][] a = {{1,2},{3,4,0,9},{5,6,7}}; 
2 或者 
3 string[][] str1 = new string[][]{new string[3] , new string[]{"hello"}}
4 简化版
5 string[][] str2 = {new string[3] , new string[]{"hello"}}; 

4 leetcode 练习

13.罗马数字转整数

罗马数字包含以下七种字符: i, v, x, l,c,d 和 m。

字符          数值
i             1
v             5
x             10
l             50
c             100
d             500
m             1000

例如, 罗马数字 2 写做 ii ,即为两个并列的 1。12 写做 xii ,即为 x + ii 。 27 写做 xxvii, 即为 xx + v + ii 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 iiii,而是 iv。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 ix。这个特殊的规则只适用于以下六种情况:

  • i 可以放在 v (5) 和 x (10) 的左边,来表示 4 和 9。
  • x 可以放在 l (50) 和 c (100) 的左边,来表示 40 和 90。
  • c 可以放在 d (500) 和 m (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

解题思路

遵循一个逻辑,如果某个字符代表的值大于等于它的下一个字符代表的值,则是“加”;如果小于它的下一个字符代表的值,则是“减”。注意最后一个字符没有“下一个”,一定是加。

源码

 1 class solution {
 2     public int romantoint(string s) {
 3         char[] ch = s.tochararray();
 4         int result = 0;
 5         for(int i = 0; i < ch.length; i++){
 6             if(i == ch.length - 1){
 7                 result += getnum(ch[i]);
 8             }else if (getnum(ch[i]) >= getnum(ch[i+1])){
 9                 result += getnum(ch[i]);
10             }else{
11                 result -= getnum(ch[i]);
12             }
13         }
14         return result;
15     }
16     
17     public static int getnum(char tmp){
18         switch(tmp){
19             case 'm':
20                 return 1000;
21             case 'd':
22                 return 500;
23             case 'c':
24                 return 100;
25             case 'l':
26                 return 50;
27             case 'x':
28                 return 10;
29             case 'v':
30                 return 5;
31             case 'i':
32                 return 1;
33         }
34         return 0;
35     }
36 }

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

源码

 1 class solution {
 2     public string longestcommonprefix(string[] strs) {
 3         string commonprefix = "";
 4         int length = ~0>>>1;
 5         if(strs.length == 0)
 6             return commonprefix;
 7         for (int i = 0; i < strs.length; i++){
 8             if(strs[i].length() < length)
 9                 length = strs[i].length();
10         }//求出最短字符长度
11         /*可用这种方法求最短长度
12     arrays.sort(strs);//按长度排列
13 int len=math.min(strs[0].length(),strs[strs.length-1].length());
14         */
15         hashmap<integer , character> map = new hashmap<integer , character>(); 
16         for(int i = 0; i < strs[0].length();i++){
17             map.put(i , strs[0].charat(i));
18         }//将第一个字符串每个字符加入hashmap
19         outer:
20         for(int i =0; i < length; i++){
21             for(int j = 0; j < strs.length; j++){
22                 if(map.get(i) == strs[j].charat(i)){}
23                 else{
24                     break outer;
25                 }//如果和该位置字符不匹配则退出循环
26             }//每完成一次循环将该位置字符加到结果上
27             commonprefix += strs[0].charat(i);
28         }
29         return commonprefix;
30     }
31 }