剑指Offer(3-10)

数组中重复的数字

题链
题解1:利用哈希表记录每个数字出现的次数,当数字出现次数超过1时返回该数字即可

public int findRepeatNumber(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int num : nums){
            if(map.containsKey(num)){
                return num;
            }else{
                map.put(num,1);
            }
        }
        return 0;
    }
1
2
3
4
5
6
7
8
9
10
11

题解2:原地哈希.从前往后遍历,如果nums[i[的值和下标i不同,则把nums[i]和nums[nums[i]]的值交换,通过这种方式来表示nums[i]值出现过1次,如果nums[i]和nums[nums[i]]的值相同,说明nums[i]的值出现了第2次,直接返回nums[i]即可.

public int findRepeatNumber(int[] nums) {
       for(int i = 0; i < nums.length; i++){
       		while(nums[i] != i){
       			if(nums[nums[i]] == nums[i]){
       				return nums[i];
       			}
       			int tmp = nums[i];
       			nums[i] = nums[nums[i]];
       			nums[nums[i]] = tmp;
       		}
       }
       return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

二维数组中的查找

题链
题解:根据二维数组的排列规则,我们可以从二维数组的右上角开始查找,记右上角元素为key,待查找元素为target,如果key等于target返回true,如果key小于target,说明这一行的元素都比target小,所以直接在下一行找即可,即让行数+1;当key大于target,说明这一列的元素都比target大,所以直接前一列找即可,即让列数-1.当遍历完整个数组仍没有找到匹配的key则返回false.

    int[][] mat;
    int t;
    int m,n;
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        mat = matrix;
        t = target;
        m = mat.length;
        if(mat == null || m == 0){
            return false;
        }
        n = mat[0].length;
        int i = 0,j = n-1;
        while(i < m && j >= 0){
            if(matrix[i][j] == target){
                return true;
            }
            if(matrix[i][j] > target){
                j--;
            }else{
                i++;
            }
        }
        return false;
    }

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

替换空格

题链
题解:这道题很简单,根据题目遍历将对应空格替换即可.但需要注意转换后的字符串长度一定是大于等于原来的字符串,所以不能在原字符串上操作.

 public String replaceSpace(String s) {
        StringBuilder curS = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == ' '){
                curS.append("%20");
            }else{
                curS.append(s.charAt(i));
            }
        }
        return new String(curS);
    }
1
2
3
4
5
6
7
8
9
10
11

从尾到头打印链表

题链
题解:建立一个List表顺序存储链表的每个节点的值,然后逆序打印List即可.

 public int[] reversePrint(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while(cur != null){
            list.add(cur.val);
            cur = cur.next;
        }
        int k = 0;
        int[] res = new int[list.size()];
        for(int i = res.length-1;i>=0;i--){
            res[i] = list.get(k);
            k++;
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

重建二叉树

题链
题解:二叉树的题目基本上都是用递归去解决的.根据前序遍历结果我们知道一个子树的根节点,通过中序遍历我们可以知道根节点对应的左树和右树.依据这个特性,我们可以从前向后遍历前序数组,对于前序数组中的每一个值key,寻找其在中序数组中的位置index,index左侧的所有元素为值为key的根节点的子树的左子树,index右侧所有元素为右子树.递归遍历这一部分即可.
所以一共要实现的功能要3个,第1个是主函数中从前序数组的首元素进入到递归中;第2个是递归函数,在函数要构造出子树根节点的值并递归遍历根节点对应的左子树和右子树,第3个是一个辅助函数,查找前序数组中的元素在中序数组中的下标值.

 public TreeNode buildTree(int[] preorder, int[] inorder) {
       if(preorder == null || preorder.length == 0){
           return null;
       }
        return func(inorder,preorder,0,inorder.length-1,0);
    }
    public TreeNode func(int[] inorder,int[] preorder,int pre,int next,int index){
        if(pre > next){
            return null;
        }
        if(pre == next){
            return new TreeNode(inorder[pre]);
        }
        int key = preorder[index];
        int mid = getIndex(inorder,key);
        TreeNode root = new TreeNode(key);
         root.left = func(inorder,preorder,pre,mid-1,index+1);
         //注意右子树的递归遍历参数列表中的index应该为左子树中元素的总个数+1+index(index衡量的其实是偏移程度)
        root.right = func(inorder,preorder,mid+1,next,index+mid-pre+1);
        return root;
    }
    public int getIndex(int[] inorder,int key){
        int n = inorder.length;
        int i = 0;
        for(; i < n; i++){
            if(inorder[i] == key){
                break;
            }
        }
        return i;
    }
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
26
27
28
29
30
31

用两个栈实现队列

题链
题解:首先我们知道栈的特性是先进后出,队列的特性是先进先出.因此我们在进方面其实不需要作什么特殊处理,直接按照栈进即可.需要处理的是出这一方面,这也很好解决,在进的时候我们只往一个栈中进元素,在出时,将进栈中的元素全部导入到出栈,然后弹出出栈的栈顶元素即可.

	Deque<Integer> d1;
    Deque<Integer> d2;
    public CQueue() {
        d1 = new LinkedList<>();
        d2 = new LinkedList<>();
    }

    public void appendTail(int value) {
        d1.push(value);
    }

    public int deleteHead() {
        if(d2.isEmpty()){
            if(d1.isEmpty()){
                return -1;
            }
             while(!d1.isEmpty()){
            d2.push(d1.pop());
        }
        }
       
        return d2.pop();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

斐波那契数列

题链
题解:…面试中能够遇到这道题的不是大牛就是大废.具体应该怎么写在学校学C语言的时候应该已经写烂了吧…

	 int MOD = (int)(Math.pow(10,9)+7);
    public int fib(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        int n1 = 0;
        int n2 = 1;
        int n3 = n1 + n2;
        while(n >= 2){
            n3 = (n1 + n2)%MOD;
            n1 = n2;
            n2 = n3;
            n--;
        }
        return n2;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19