剑指offer1

剑指offer
Word count: 3.6k   |   Reading time≈ 16 min
难度 题号
简单 1-18
中等 19-45
较难 46+

1.二维数组中的查找

题目描述

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

示例：
矩阵：[
[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
给定20，返回false

解题思路

这题可以从左下角或者从右上角开始游走，重要的是数组要判空，不然可能会出现数组越界的问题。

code

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
class Solution {
     public boolean findNumberIn2DArray(int[][] matrix, int target) {
         //二维数组判空
        if(matrix==null||matrix.length==0||(matrix.length==1&&matrix[0].length==0)) return false;
        int row = matrix.length;//行数
        int col = matrix[0].length;//列数
        int left = row-1;//行
        int right = 0;//列
        for(int i = 0;i<row+col;i++){
            if(matrix[left][right]>target){
                left--;
                if(left==-1){
                    return false;
                }
            }else if(matrix[left][right]<target){
                right++;
                if(right==col){
                    return false;
                }
            }else {
                return true;
            }
        }
        return false;
    }
}

2.数组中的重复数字

题目描述

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

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

解题思路

一开始的思路是先用快排对数组进行排序，然后遍历数组，但是排序超时。
这时候可以选择用java中的set解题，在往set中添加元素的时候，添加成功返回true，说明不重复，反之说明重复。

第二遍做的时候，第一个想法是用哈希。代码也写上。4-11

code

1
2
3
4
5
6
7
8
9
10
11
12
13
class solution {
    public int findRepeatNumber(int[] nums) {
        //排序超时
        Set<Integer> set = new HashSet<Integer>();
        int result = -1;
        for (int i = 0; i < nums.length; i++) {
            if (set.add(nums[i]) == false) {
                return nums[i];
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
public static int duplicate (int[] numbers) {
    // write code here
    int[] hash = new int[numbers.length+2];
    //java中的数组默认都是0，所以哈希不用再考虑初始化
    for(int i = 0;i<numbers.length;i++){
        hash[numbers[i]]++;
        if(hash[numbers[i]]>1)return numbers[i];
    }
    return -1;
}

3.从尾到头打印链表

题目描述

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

示例1：

输入：head= [1,2,3]

输出：[2,3,1]

解题思路

这题可以先获取链表的长度，然后处理，这里为了熟悉栈的使用，使用压栈和出栈的方式解题。

利用栈的FILO特性

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for (int i = 0; i < size; i++) {
            print[i] = stack.pop().val;
        }
        return print;
    }
}

4.替换空格

题目描述

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

示例1：

1
2
输入：s = "We are happy."
输出："We%20are%20happy."

解题思路

直接调用s.replaceAlll()即可

code

java
1
2
3
4
5
6
class Solution {
        public String replaceSpace(String s) {
        String newStr = s.replaceAll(" ","%20");
        return newStr;
    }
}

5.两个栈实现队列

题目描述

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

解题思路

stack1作为push队列，pop时，如果stack2是空，将stack1复制到2，然后出栈顶，stack2不空时直接出栈。

code

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
32
import java.util.Stack;

class CQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

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

    public int deleteHead() {
        //2不空，直接出栈，空的时候复制再出栈
        if(stack2.isEmpty()){
            if(stack1.isEmpty()){
                return -1;
            }else {
                //复制出栈
                while (!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
                return stack2.pop();
            }
        }else {
            return stack2.pop();
        }
    }
}

6.青蛙跳台阶问题

题目描述

快乐的一只小青蛙，瓜瓜呱呱呱呱呱。一次可以跳一次台阶，也可以跳两层，问这个小青蛙跳n层台阶有多少种跳法。

0<=n<=100

对照上一题，是两种解决斐波那契的方法。

解题思路

动态规划问题。假设n级台阶的跳法为f(n)，则：

  • 第一次跳1级，还有f(n-1)种跳法
  • 第一次跳2级，还有f(n-2)种跳法

所以$f(n) = f(n-1)+f(n-2)$

code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numWays(int n) {
        int[] dp = new int[n+2];
        for(int i = 0;i<=n;i++){
            if(i==0 || i==1){
                dp[i]=1;
                continue;
            }
            dp[i] = (dp[i-1]+dp[i-2])%1000000007;
        }
        return dp[n];
    }
}

7.变态青蛙跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解题思路

假设跳到n有f(n)种跳法，则:

$f(n) = f(n-1)+f(n-2)+…+f(1)$

$f(n-1) = f(n-2)+f(n-3)+…+f(1)$

两个式子相减得到：$f(n) = 2f(n-1)$，然后就可以dp了。

code

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int jumpFloorII(int target) {
                //通过递推可以得到f(n) = 2f(n-1)
        int[] dp = new int[target+2];
        dp[1] = 1;
        for(int i = 2;i<=target;i++){
            dp[i] = 2*dp[i-1];
        }
        return dp[target];
    }
}

8.旋转数组中的最小数字

题目描述

把一个数组开始的几个元素搬到末尾，称为数组旋转，给出一个递增的数组的旋转，输出旋转数组中的最小元素。

解题思路

这题本质上是二分查找，实际上，暴力查找也过了的。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.*;

public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int min = Integer.MAX_VALUE;
        for(int i = 0;i<array.length;i++){
            if(array[i]<min){
                min = array[i];
            }
        }
        return min;
    }
}

9.合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，合并之后满足单调不递减。

解题思路

就是基本得链表操作。

code

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
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode newHead = new ListNode(-1);
        ListNode current = newHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        if (list1 != null) current.next = list1;
        if (list2 != null) current.next = list2;
        return newHead.next;
    }
}

10.数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解题思路

话不多说，就是hash

code

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
import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int all = array.length;
        int half = all/2+1;
        int test = Arrays.stream(array).max().getAsInt();
        int[] hash = new int[test+2];
        for(int i = 0;i<hash.length;i++){
            hash[i] = -1;
        }
        for(int i = 0;i<array.length;i++){
            if(hash[array[i]]==-1){
                hash[array[i]]=1;
            }else {
                hash[array[i]]++;
            }
        }
        for(int i = 0;i<array.length;i++){
            if(hash[array[i]]>=half){
                return array[i];
            }
        }
        return 0;
    }
}

11.连续子数组的最大和

题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).

1
输入的数组为{1,-2,3,10,—4,7,2,一5}，和最大的子数组为{3,10,一4,7,2}，因此输出为该子数组的和 18。

解题思路

看题目意思，再看时间复杂度，这题一定是DP没跑了。

状态转义方程是$dp[n] = max{dp[n-1]+arr[n],arr[n]}$

$dp[0] = arr[0]$

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;
public class Solution {
    public static void main(String[] args) {
        int[] array = new int[]{2,8,1,5,9};
        System.out.println(FindGreatestSumOfSubArray(array));
    }
    public static int FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length+2];
        dp[0] = array[0];
        int max = Integer.MIN_VALUE;
        for(int i = 1;i<array.length;i++){
            dp[i] = Math.max(dp[i-1]+array[i],array[i]);
            if(dp[i]>max)max = dp[i];
        }
        return max;
    }
}

12.第一个只出现一次的字符

题目描述

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

解题思路

本质上也是哈希，我这里用map统计，然后再遍历一遍就好了。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
                char[] st = str.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        //统计每个字符出现的次数。
        for(int i = 0;i<st.length;i++){
            if(map.get(st[i])==null){
                map.put(st[i],1);
                continue;
            }else {
                int index = map.get(st[i]);
                map.put(st[i],++index);
            }
        }

        for(int i = 0;i<st.length;i++){
            if(map.get(st[i])==1){
                return i;
            }
        }
        return -1;
    }
}

13.二叉树的深度

题目描述

输入二叉树，求树的深度。从根节点到叶节点经过的节点（含根，叶节点）形成树的路径，最长路径的长度为树的深度。

解题思路

关于树的题目，基本都是套用遍历的模板。或者是层次遍历。

code

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int TreeDepth(TreeNode root) {
                int lh,rh;
        if(root==null){
            return 0;
        }else {
            lh = TreeDepth(root.left);
            rh = TreeDepth(root.right);
            return 1+(lh>rh?lh:rh);
        }
    }
}

14.平衡二叉树

题目描述

输入一个二叉树，判断二叉树是不是平衡二叉树

解题思路

分别求左子树和右子树的高度，然后求差。树的递归思想

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
        public boolean IsBalanced_Solution(TreeNode root) {
        int res = depth(root);
        if(res==-1)return false;
        return true;
    }
    public int depth(TreeNode root){
        if(root==null) return 0;
        int left = depth(root.left);
        if(left == -1) return -1;
        int right = depth(root.right);
        if(right == -1) return -1;
        //返回-1表示不是平二二叉树；
        if(left-right<-1 || left-right>1)return -1;
        return 1+(left>right?left:right);
    }
}

15.不用加减乘除做加法

题目描述

写一个函数，求两个整数之和，函数内不能使用四则运算

解题思路

没有加减乘除，那就只能位运算了啊。位运算一般是有规律的，那先找一下规律啊，来计算$2+3$

0010

0011

0101

不考虑进位的加法可以直接采用异或操作，进位可以用与运算表示。进位用移位表示。

  • x^y：执行加法
  • (x&y)<<1：执行进位操作。

code

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int Add(int num1,int num2) {
        while (num2!=0){
            //不进位的加法
            int temp = num1^num2;
            //进位
            num2 = (num1&num2)<<1;
            num1 = temp;
        }
        return num1;
    }
}

16.构造乘积数组

题目描述

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]*A[1]*…*A[i-1]*A[i+1]*…*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）

对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

输入：[1,2,3,4,5]

输出：[120,60,40,30,24]

解题思路

不能用除法，那我直接模拟了。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
public class Solution {
    public int[] multiply(int[] A) {
        //问题在于不能用除法，复杂性会比较高
        int[] B = new int[A.length];
        for(int i = 0;i<A.length;i++){
            B[i]=1;
            for(int j=0;j<A.length;j++){
                if(j==i)continue;
                B[i]*=A[j];
            }
        }
        return B;
    }
}

17.二叉搜索树的第K个节点

题目描述

给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。

解题思路

二叉搜索树，中序遍历是递增的。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k) {
        //既然是二叉搜索树了，那终须遍历就是递增的序列。那就先终须遍历，存数组
        List<TreeNode> val = new LinkedList<>();
        val = Z(pRoot);
        //得到的val数组是递增序列
        if(k>=1 && val.size()>=k){
            return val.get(k-1);
        }
        return null;
    }

    public List<TreeNode> Z(TreeNode pRoot){
        List<TreeNode> res = new LinkedList<>();
        if(pRoot!=null){
            Z(pRoot.left);
            //村数组
            res.add(pRoot);
            Z(pRoot.right);
        }
        return res;
    }
}

18.斐波那契数列

题目描述

求Fibonacci数列的第n项

F(0)=0,F(1) =1

F(N) = F(N-1)+F(N-2)

答案取模1e9+7。

解题思路

直接递归超时，变成加法，存储前两个的状态。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int fib(int n) {
        if(n==0)return 0;
        if(n==1)return 1;
        int a = 0,b = 1;
        for(int i = 2;i<=n;i++){
            int temp = (a+b)%1000000007;
            a=b;
            b=temp;
        }
        return b;
    }
}

19.二进制中1的个数

题目描述

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。

解题思路

就移位运算呗。当然也可以更简单。

String s = Integer.toBinaryString(n);会将整数编程一个二进制的字符串

code

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.*;
public class Solution {
    public int NumberOf1(int n) {
        String s = Integer.toBinaryString(n);
        String[] split = s.split("");
        int a = 0;
        for(int i = 0;i<split.length;i++){
            if(split[i].endsWith("1"))a+;
        }
        return a;
    }
}

20.链表中倒数第K个节点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

如果该链表长度小于k，请返回空。

解题思路

看题解都是用的双指针，我这里用的是栈的方法。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ListNode FindKthToTail (ListNode pHead, int k) {
    // write code here
            ListNode tmp = pHead;
    Stack<ListNode> stack = new Stack<>();
    while (tmp!=null){
        stack.push(tmp);
        tmp = tmp.next;
    }
    if(stack.size()<k)return null;
    for(int i =0;i<k;i++){
        tmp = stack.pop();
    }
    return tmp;
}
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

请我喝杯咖啡吧~

支付宝
微信