剑指offer-Day1

发表于 | 分类于 |
字数统计: 840 | 阅读时长 ≈ 3

1.找出数组中重复的数字。【简单】

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

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

思路：
1.使用new map,遍历arr
2.如果map.has()为true,这个元素就是之前出现过的,返回这个元素。否则map.set()

js实现：

1
2
3
4
5
6
7
8
9
10
11
12

var findRepeatNumber = function(nums) {
    var map = new Map()
    for(let i = 0;i<nums.length;i++){
        if(!map.has(nums[i])){
            map.set(nums[i])
        }else{
            return nums[i]
        }
    }
    
};

2.在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。【中等】

示例:

现有矩阵 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]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

思路
1.先判断数组是否为空，不为空的时候再得到行数，列数
2.从最后一行开始循环，条件为j<列数且i>=0
3.如果值比目标小就列++，值比目标大就行–，等于的时候返回true
4.跳出循环就是false

java实现： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        //要先判断数组是否为空
       if(matrix.length==0||matrix==null||matrix[0].length==0){
           return false;
       }
    //不为空的时候再赋值矩阵的行列，否则如果为空的时候，matrix[0]就会报错index 0 out of bounds for length 0
       int r = matrix.length;
       int l = matrix[0].length;
       int i = r-1;
       int j = 0;

       while(j<l & i>=0){
           if(target > matrix[i][j]){
               j++;
           }else if(target < matrix[i][j]){
               i--;
           }else{
               return true;
           }
       }
        return false;
       
     }
}

3.小扣在秋日市集发现了一款速算机器人。店家对机器人说出两个数字（记作 x 和 y），请小扣说出计算指令：

"A" 运算：使 x = 2 * x + y；
"B" 运算：使 y = 2 * y + x。

在本次游戏中，店家说出的数字为 x = 1 和 y = 0，小扣说出的计算指令记作仅由大写字母 A、B 组成的字符串 s，字符串中字符的顺序表示计算顺序，请返回最终 x 与 y 的和为多少。

示例 1：

输入：s = "AB"

输出：4

解释：
经过一次 A 运算后，x = 2, y = 0。
再经过一次 B 运算，x = 2, y = 2。
最终 x 与 y 之和为 4。

思路：
获取字符串长度遍历，如果为A进行A运算，否则进行B运算

java代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int calculate(String s) {
        int i = 0;
        int x = 1;
        int y = 0;
        int len = s.length();
        if(len>0 && len<=10){
        while(i<len){
            if(s.charAt(i)=='A'){
                x = 2*x + y;
                i++;
            }else if(s.charAt(i)=='B'){
                y = 2*y + x;
                i++;
            }
        }
       
       }
        
       return x+y;
    }   
}


内存消耗不好

参考大佬：
因为无论是A还是B，最后都是2（x+y）。所以return 2*(x+y)*len;