0%

day2-算法-数组与矩阵

发表于 更新于 Valine：
本文字数： 2.2k 阅读时长 ≈ 2 分钟

数组中重复的数字

题目链接

牛客网(opens new window)

题目描述

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

1
2
3
4
5
Input:
{2, 3, 1, 0, 2, 5}

Output:
2

解决思路：

不消耗额外空间的办法：由于范围是在n-1内，可以循环检查每个下标的数字是否等于下标，不等于则将其与下标处的数字所在的索引互换位置，若发现重复则返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean duplicate(int[] nums, int length, int[] duplication) {
            if (nums == null || length <= 0)
                return false;
            for (int i = 0; i < length; i++) {
                while (nums[i] != i) {
                    if (nums[i] == nums[nums[i]]) {
                        duplication[0] = nums[i];
                        return true;
                    }
                    swap(nums, i, nums[i]);
                }
            }
            return false;
}

消耗额外空间的做法：使用HashSet，每次检查数字重复即可

1
2
3
4
5
6
7
8
9
10
HashSet<Integer> hashSet = new HashSet<>();
            for (int i = 0; i < length; i++) {
                if (hashSet.contains(numbers[i])){
                    duplication[0] = numbers[i];
                    return true;
                } else {
                    hashSet.add(numbers[i]);
                }
            }
            return false;

二维数组中的查找

题目链接

牛客网(opens new window)

题目描述

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

1
2
3
4
5
6
7
8
9
10
11
Consider the following matrix:
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.

解题思路

由于二维数组从左上角到右下角顺序递增，因此选择从右上角开始查询，若比目标值大则向左移动，否则向下移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean Find(int target, int [][] array) {
        if(array == null || array.length==0 || array[0].length==0)    return false;
        int i = 0, j = array[0].length-1;
        while(array[i][j]!=target){
            if(i==array.length-1 && j==0){
                return false;
            }else if(array[i][j]>target){
                if(j==0)    return false;
                j--;
            }else{
                if(i==array.length-1)    return false;
                i++;
            }
        }
        return true;
    }

替换空格

题目链接

牛客网(opens new window)

题目描述

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

1
2
3
4
5
Input:
"A B"

Output:
"A%20B"

解题思路

api法

1
return str.toString().replace(" ", "%20");

直接改造StringBuffer，无额外空间：

  • 首先对stringbuffer进行扩充，每遇到一个空格便在末尾添加两个空格

  • 并设置两个指针p1,p2分别指向扩充前的末尾和扩充后的末尾

  • p1不断向前移动，当遇到非空格时，p2填充并前移；当遇到空格时，p2填充%20并前移，直到p1与p2重合或p1走到初始阶段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public String replaceSpace(StringBuffer str) {
        int p1 = str.length() - 1;
        for (int i = 0; i <= p1; i++) {
            if (str.charAt(i) == ' ') str.append("  ");
        }
        int p2 = str.length() - 1;
        while (p1 >= 0 && p2 > p1) {
            char c =str.charAt(p1--);
            if (c == ' ') {
                str.setCharAt(p2--, '0');
                str.setCharAt(p2--, '2');
                str.setCharAt(p2--, '%');
            } else {
                str.setCharAt(p2--, c);
            }
        }
        return str.toString();
    }