VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > 编程开发 > Java教程 >
  • 算法-数组与矩阵

简介:算法篇-数组与矩阵。

 

    知君何事泪纵横,断肠声里忆平生。

 

一、数组中重复的数字

1、题目描述

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字是重复的,也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

输入:[2,3,1,0,2,5,3]

输出:2

2、解题思路

要求时间复杂度 O(N),空间复杂度 O(1)。因此不能使用排序的方法,也不能使用额外的标记数组。

对于这种数组元素在 [0, n-1] 范围内的问题,可以将值为 i 的元素调整到第 i 个位置上进行求解。在调整过程中,如果第 i 位置上已经有一个值为 i 的元素,就可以知道 i 值重复。

以 (2, 3, 1, 0, 2, 5) 为例,遍历到位置 4 时,该位置上的数为 2,但是第 2 个位置上已经有一个 2 的值了,因此可以知道 2 重复:

3、代码示例

复制代码
 1 import java.util.*;
 2 
 3 public class Solution {
 4     public int duplicate (int[] numbers) {
 5         int length = numbers.length;
 6         if(length == 0 || length ==1){
 7             return -1;
 8         }
 9         Arrays.sort(numbers);  // 利用Arrays从小到大排序
10         for(int i = 0; i < length -1; i++){
11             if(numbers[i] == numbers[i + 1]){
12                 return numbers[i];
13             }
14         }
15         return -1;
16     }
17 }
复制代码

 二、二维数组中的查找

1、题目描述

给定一个二维数组,其每一行从左到右递增排序,从上到下也是递增排序。给定一个数,判断这个数是否在该二维数组中。

输入:7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出:true

2、解题思路

要求时间复杂度 O(M + N),空间复杂度 O(1)。其中 M 为行数,N 为 列数。

该二维数组中的一个数,小于它的数一定在其左边,大于它的数一定在其下边。因此,从右上角开始查找,就可以根据 target 和当前元素的大小关系来快速地缩小查找区间,每次减少一行或者一列的元素。当前元素的查找区间为左下角的所有元素。

3、代码示例

复制代码
 1 public class Solution {
 2     public boolean Find(int target, int [][] array) {
 3         boolean flag = false;
 4         for(int i = 0; i < array.length; i++){
 5             for(int j = 0; j < array[i].length; j++){
 6                 if(array[i][j] == target){
 7                     flag = true;
 8                     break;
 9                 }
10             }
11             if(flag){
12                 break;
13             }
14         }
15         return flag;
16     }
17 }
复制代码

三、替换空格

1、题目描述

将一个字符串中的空格替换成 "%20"。

输入:"We Are Happy"

输出:"We%20Are%20Happy"

2、解题思路

① 在字符串尾部填充任意字符,使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符(%20),所以当遍历到一个空格时,需要在尾部填充两个任意字符。

② 令 P1 指向字符串原来的末尾位置,P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历,当 P1 遍历到一个空格时,就需要令 P2 指向的位置依次填充 02%(注意是逆序的),否则就填充上 P1 指向字符的值。从后向前遍是为了在改变 P2 所指向的内容时,不会影响到 P1 遍历原来字符串的内容。

③ 当 P2 遇到 P1 时(P2 <= P1),或者遍历结束(P1 < 0),退出。

3、代码示例:

复制代码
1 import java.util.*;
2 
3 
4 public class Solution {
5 
6     public String replaceSpace (String s) {
7         return s.replace(" ", "%20");
8     }
9 }
复制代码

四、顺时针打印矩阵

1、题目描述

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵:

[[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]]

则依次打印出数字:

[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]

输入:[[1,2],[3,4]]

输出:[1,2,4,3]

2、解题思路

一层一层从外到里打印,观察可知每一层打印都有相同的处理步骤,唯一不同的是上下左右的边界不同了。因此使用四个变量 r1, r2, c1, c2 分别存储上下左右边界值,从而定义当前最外层。打印当前最外层的顺序:从左到右打印最上一行->从上到下打印最右一行->从右到左打印最下一行->从下到上打印最左一行。应当注意只有在 r1 != r2 时才打印最下一行,也就是在当前最外层的行数大于 1 时才打印最下一行,这是因为当前最外层只有一行时,继续打印最下一行,会导致重复打印。打印最左一行也要做同样处理。

 

 

 3、代码示例

复制代码
 1 import java.util.ArrayList;
 2 
 3 public class Solution {
 4     public ArrayList<Integer> printMatrix(int [][] matrix) {
 5        int n = matrix.length;
 6        int m = matrix[0].length;
 7        int left = 0;
 8        int right = m - 1;
 9        int top = 0;
10        int tail = n - 1;
11        ArrayList list = new ArrayList<>();
12        while(true){
13            for(int i = left; i <= right; i++){
14                list.add(matrix[top][i]);
15            }
16            if(++top > tail){
17                break;
18            }
19            for(int i = top; i <= tail; i++){
20                list.add(matrix[i][right]);
21            }
22            if(--right < left){
23                break;
24            }
25            for(int i = tail; i >= top; i--){
26                list.add(matrix[i][left]);
27            }
28            if(++left > right){
29                break;
30            }
31        } 
32         return list;
33     }
34 }
复制代码

五、第一个只出现一次的字符位置

1、题目描述

在一个字符串中找到第一个只出现一次的字符,并返回它的位置。字符串只包含 ASCII 码字符。

输入:"google"

输出:4

2、解题思路

最直观的解法是使用 HashMap 对出现次数进行统计:字符做为 key,出现次数作为 value,遍历字符串每次都将 key 对应的 value 加 1。最后再遍历这个 HashMap 就可以找出出现次数为 1 的字符。

考虑到要统计的字符范围有限,也可以使用整型数组代替 HashMap。ASCII 码只有 128 个字符,因此可以使用长度为 128 的整型数组来存储每个字符出现的次数。

3、代码示例

复制代码
 1 public class Solution {
 2     public int FirstNotRepeatingChar(String str) {
 3         for(int i = 0; i < str.length(); i++){
 4             // str.charAt(i) 取ASC码
 5             // str.indexOf(str.charAt(i)) 取ASC码第一次出现的索引下标位置
 6             // str.lastIndexOf(str.charAt(i)) 取ASC码最后一次出现的
 7             if(str.indexOf(str.charAt(i)) != str.lastIndexOf(str.charAt(i))){
 8                 continue;
 9             }
10             return i;
11         }
12         return -1;
13     }
14 }
复制代码



出处:
https://www.cnblogs.com/taojietaoge/p/14950177.html


相关教程