面试题03. 数组中重复的数字 (难度:简单)

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

示例

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

思路

HashSet是Set接口的实现类,储存的是无序、唯一的对象。由于是无序的所以每组数据都没有索引,很多list可用的方法他都没有,凡是需要通过索引来进行操作的方法都没有,所以也不能使用普通for循环来进行遍历,只有加强型for和迭代器两种遍历方法。

hashset中的add()方法:只有set中尚未包含指定元素,则添加指定元素返回true,否则添加失败返回false。这样就方便判断对象中是否有重复值了。

代码实现

public class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> a=new HashSet<>();
        for(int num: nums){
            if(!a.add(num))
                return num;
        }
        return -1;
    }
}

面试题04. 二维数组中的查找 (难度:简单)

在一个 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。

限制:
0 <= n <= 1000
0 <= m <= 1000

思路

由于题目给定的是一个有序矩阵,那么不难发现在矩阵中有两个具有标志性的数,即左下角和右上角的数。它们具有特点:左下角的数小于所在行的其它数,大于所在列的其它数;右上角的数大于所在行的其它数,小于所在列的其它数。那么就可以通过与目标数进行比较,如果等于目标数,则直接返回true;否则“消去”所在行或所在列,进行下一轮比较。

时间复杂度:O(n+m)。访问到的下标的行最多增加 n 次,列最多减少 m 次,因此循环体最多执行 n + m 次。

空间复杂度:O(1)。

代码实现

public class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        //判断数组是否符合要求
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        //定义m,n获取行数和列数
        int m = matrix.length;
        int n = matrix[0].length;
        //从右上角开始搜索
        int row = 0;
        int col = n - 1;
        while (row < m && col >= 0) {
            if (target == matrix[row][col]) {
                //右上角的数恰好是目标数,则停止搜索,返回true
                return true;
            } else if (target < matrix[row][col]) {
                //右上角的数大于目标数,那么该列可以不再考虑了
                col--;
            } else {
                //右上角的数小于目标数,那么该行可以不再考虑了
                row++;
            }
        }
        return false;
    }
}

面试题05. 替换空格 (难度:简单)

请实现一个函数,把字符串 s 中的每个空格替换成”%20”。

示例

输入:s = “We are happy.”
输出:”We%20are%20happy.”

代码实现

public class Solution05 {
    public String replaceSpace(String s) {
        //其实可以直接使用库方法,但是太偷懒了
        //return s.replace(" ","%20");
        //使用StringBuilder构造字符串的方法来解决,其实和库函数的实现逻辑一样,逐个进行判断
        StringBuilder sb=new StringBuilder();
        for (int i=0;i<s.length();i++){
            char c=s.charAt(i);
            if(c==' '){
                sb.append("%20");
            }else{
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

面试题06. 从尾到头打印链表 (难度:简单)

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

示例

输入:head = [1,3,2]
输出:[2,3,1]

思路

链表特点是只能从前至后访问每个节点,而题目要求是倒序输出节点值,这种 先入后出 的需求可以借助 来实现。

代码实现

class Solution {
    //方法一:常规做法
    public int[] reversePrint(ListNode head) {
        ListNode newhead=head;
        int count=0;//节点个数
        while (newhead!=null){//遍历链表,获得节点个数,以便存储数据
            count++;
            newhead=newhead.next;
        }
        ListNode newhead2=head;
        int[] result=new int[count];//之前count的作用体现了
        for(int i=count-1;i>=0;i--){
            result[i]=newhead2.val;//把节点的值保存到数组里面
            newhead2=newhead2.next;
        }
        return result;
    }

    //方法二:利用栈先进后出的特点
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        while(head != null) {
            //压栈
            stack.push(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        int cnt = 0;
        while(!stack.isEmpty()) {
            //出栈
            res[cnt++] = stack.pop();
        }
        return res;
    }
}

评论