欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指Offer题解(持续更新中……)

程序员文章站 2022-06-14 23:03:26
...

第2️⃣章

03 | 数组中重复的数字

问题描述

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

解题思路

  • 把数字i放到num[i]上
  • 如果num[i]上已经有i了,那么就是重复的数字了

代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            while (i != nums[i]) {
                if (nums[nums[i]] != nums[i]) {
                    swap(nums,i,nums[i]);
                } else {
                    return nums[i];
                }
            }
        }
        return ans;
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

其他方法分析

方法 时间复杂度 空间复杂度
题解方法 O(n) O(1)
哈希表 O(n) O(n)
先排序后遍历数组 O(nlogn) O(1)
二分法 O(nlogn) O(1) 不会修改原数组

若果不允许修改数组呢?(二分法,详情见书,时间复杂度O(nlogn))

04 | 二维数组中的查找

问题描述

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

解题思路

  • 数组右上角(或者左下角)的元素很特殊,该元素的行中它是最大的,列中它是最小的
  • 所以可以将target与它比较
    • 若等于,则返回true
    • 若martix[右上] < target,则martix[右上]左侧比它还要小的一行就不用考虑了
    • 若martix[右上] > target,则martix[右上]下侧比它还要大的一列就不用考虑了
  • 一行/一列被去掉后会出现新的martix[右上],继续判断直至没有元素可以比较

代码

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

09 | 用两个栈实现队列

问题描述

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

解题思路

  • 可以想象两个区域,排队区进入区
  • 入队的元素先进入排队区,出队的元素从进入区选择
  • 当即将进如区为空时,将排队区的元素全部依次进入进入区(即先进去排队区的,先出进入区(将栈倒置即可))

代码

class CQueue {
    Stack<Integer> stact1 = new Stack<>();
    Stack<Integer> stact2 = new Stack<>();

    public CQueue() {

    }
    
    public void appendTail(int value) {
        stact1.push(value);
    }
    
    public int deleteHead() {
        if (stact1.isEmpty() && stact2.isEmpty()){
            return -1;
        }
        if (stact2.isEmpty()){
            while (!stact1.isEmpty()){
                stact2.push(stact1.pop());
            }
        }
        return stact2.pop();
        
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

相关题目-225. 用两个队列实现栈

15 | 二进制中1的个数

问题描述

请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

解题思路

  • 将二进制数 -1 即可将二进制数最低位的 1 置位 0 ,比该 1 位数还低的 0 置位 1,如1100 - 1 = 1011
  • 将 -1 后的数与原数作 & 操作,即可将原数中最低位的 1 去除

代码

public class Solution {
    // you need to treat n as an unsigned value

    //《剑指Offer》书上的思路1
    public int hammingWeight(int n) {
        int flag = 1;
        int count = 0;
        while (flag != 0){ //应该是flag会爆掉变成0
            if ((flag & n) == flag) {
                count++;
            }
            flag = flag << 1;
        }
        return count;
    }


    // //《剑指Offer》书上的思路2
    public int hammingWeight(int n) {
        String s = Integer.toBinaryString(n);
        int count = 0;
        for(char c:s.toCharArray()){
            if (c == '1'){
                count++;
            }
        }
        return count;
    }
}

第3️⃣章

第4️⃣章

30 | 包含min函数的栈

问题描述

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

解题思路

  • 栈顶元素为最小元素时,若进行出栈操作,则需要对栈内所有元素进行比较,复杂度:O(N)
  • 使用辅助栈来存储各个时刻栈内的最小元素

代码

class MinStack {

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> auxStack = new Stack<>();


    /** initialize your data structure here. */
    public MinStack() {

    }
    
    public void push(int x) {
        stack.push(x);
        if (auxStack.empty() || x < auxStack.peek()) {
            auxStack.push(x);
        } else {
            auxStack.push(auxStack.peek());
        }
    }
    
    public void pop() {
        stack.pop();
        auxStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return auxStack.peek();
    }
}

第5️⃣章

第6️⃣章

57 | 和为s的两个数字

题目描述

输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

解题思路

  • 少了就加一点,多了就减一点

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        int sum = 0;
        while (true) {
            sum = nums[i] + nums[j];
            if (sum == target) {
                break;
            } else if (sum < target){
                i++;
            } else {
                j--;
            }
        }
        return new int[]{nums[i],nums[j]};
    }
}

57-II | 和为s的连续正数序列

题目描述

输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。
序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

解题思路

  • 少了就加一点,多了就减一点

代码

class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1,j = 2;
        int sum = 3;
        ArrayList<int[]> ans = new ArrayList<>();
        while (i <= target/2)
        {
            if (sum > target) {
                sum -= i;
                i++;
            } else if (sum < target){
                j++;
                sum += j;
            }

            if (sum == target) {
                int[] temp = new int[j-i+1];
                for (int k = i; k <= j; k++){
                    temp[k-i] = k;
                }

                ans.add(temp);
                
                sum -= i;
                i++;
            }
        }
        return ans.toArray(new int[ans.size()][]);
    
    }
}

第7️⃣章