剑指offer3

剑指offer
Word count: 5k   |   Reading time≈ 21 min

41.表示数值的字符串

题目描述

实现一个函数来判断字符串是否表示数值(包括整数和小数)。

解题思路

  • 字母只能有e
  • 加减号只能在开头或者在e的后面
  • 只能有一个小数点……

等等。。。。看代码，仅供娱乐！

code

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public boolean isNumeric (String str) {
        try {
            Double val = Double.parseDouble(str);
            return true;
        }catch (Exception e) {
            return false;
        }
    }
}

42.字符流中第一个不重复的字符

题目描述

实现函数来找出字符流中第一个只出现一次的字符。

两个函数insert和FirstAppearingOnce函数，调用方式如下：

string caseout = “”;

1.读入测试用例字符串casein

2.如果对应语言有Init()函数的话，执行Init() 函数

3.循环遍历字符串里的每一个字符ch {

Insert(ch);

caseout += FirstAppearingOnce()

}

4.输出caseout，进行比较。

解题思路

这题看了很久，没看懂题目是什么意思，两个函数的意思是，首先Insert()函数是往字符串里面添加字符，每次添加字符，就会调用FirstAppearingOnce()函数判断当前字符串第一个不重复的字符。

这题有个知识点就是可以利用128长度的数组来哈希存放字符。

在每次给出一个字符的时候，如果当前字符的哈希值是0，表示暂时还不重复，可以添加进去，然后计数。如果哈希值是1的话，说明再添加一个肯定重复，之后也一定会重复，所以移除节点，同时计数。

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

public class Solution {
    LinkedList<Character> list = new LinkedList<>();
    int[] time = new int[128];
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        //如果是0，则添加
        if(time[ch]==0){
            list.add(ch);
        }else {
            list.remove(new Character(ch));
        }
        time[ch]++;
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        if(list.size() == 0){
            return '#';
        }else {
            return list.getFirst();
        }
    }
}

43.链表中环的入口节点

题目描述

给一个链表，若其中包含环，找出链表的换的入口节点，否则，输出null。

解题思路

遍历链表，将节点放入set集合中，如果有环，肯定某一步骤add()函数的返回值为false，返回即可。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //遍历链表，加入到set集合里面
        Set<ListNode> set = new HashSet<>();
        while (pHead!=null){
            boolean flag = set.add(pHead);
            if(flag){
                pHead = pHead.next;
            }else {
                return pHead;
            }
        }
        return null;
    }
}

44.二叉树的下一个节点

题目描述

给定一个二叉树其中的一个节点，请找出中序遍历的下一个节点并返回。注意，树中的节点不仅包含左右子树节点，同时包含指向父节点的next指针。

解题思路

首先暴力方法的解法是可以通过的，但是没什么意义，然后考虑有没有别的解法。

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
    33
    34
    35
    36
    import java.util.*;

    public class Solution {
        //定义集合存储中序遍历的二叉树
        List<TreeLinkNode> result = new LinkedList<>();
        public TreeLinkNode GetNext(TreeLinkNode pNode) {
            if(pNode == null)return null;
            TreeLinkNode temp = pNode;
            //找到根节点
            TreeLinkNode root = GetFather(pNode);
            //中序遍历二叉树
            middleSearch(root);
            //找到写一个节点
            int n = result.size();
            for(int i = 0;i<n;i++){
                if(result.get(i).equals(temp) && i+1!=n){
                    return result.get(i+1);
                }
            }
            return null;
        }
        //找根节点函数
        public TreeLinkNode GetFather(TreeLinkNode pNode){
            while (pNode.next!=null){
                pNode = pNode.next;
            }
            return pNode;
        }

        public void middleSearch(TreeLinkNode root){
            if(root == null)return;
            middleSearch(root.left);
            result.add(root);
            middleSearch(root.right);
        }
    }

45.把二叉树打印成多行

题目描述

从上到下按层打印二叉树，同一层节点从左至右输出，每一层输出一行。

解题思路

二叉树的层次遍历，BSF的模板化解题

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
33
34
35
36
37
38
39
40
41
import java.util.*;


/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(pRoot == null)
            return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(pRoot);
        
        while(!q.isEmpty()){
            int size = q.size();
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode now = q.poll();
                list.add(now.val);
                if(now.left != null)
                    q.add(now.left);
                if(now.right != null)
                    q.add(now.right);
            }
            res.add(list);
        }
        return res;
    }
    
}

46.数据流中的中位数

题目描述

如果从数据流中读出奇数个数值，中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，中位数就是所有数值排序之后中间两个数的平均值。使用insert()方法读取数据流，使用GetMedian()方法获取当前读取数据流中的中位数。

解题思路

这题其实可以直接使用暴力的方式解决，但是这种数据流的题目，似乎都可以使用某种巧妙的排序来解决。一个很小的改进是，在每次插入一个值的时候，有之前是有序的，所以可以使用插入排序的算法吗，进行一趟排序，避免了每次的大排序。

code

先给出暴力的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    List<Integer> list = new LinkedList<>();
    public void Insert(Integer num){
        list.add(num);
        Collections.sort(list);
    }

    public Double GetMedian(){
        Double result = 0.0;
        int middle = list.size()/2;
        if(list.size() %2 ==0){
            //中间两个数组的和
            return (double)(list.get(middle-1)+list.get(middle));
        }else {
            result = (double) list.get(list.size()/2);
        }
        return result;
    }
}

47.数组中的逆序对

题目描述

在数组的两个数字，如果前一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求这个数组中的逆序对的总数P。讲P对1000000007取模的结果输出。 即输出P%1000000007

解题思路

  • 暴力的解题方法超时
  • 原来这题就是一个排序算法，因为对于有序的数组来说，是不存在逆序对的，当出现逆序对的时候，说明需要交换，这里就可以利用归并排序的思想来解题了，主要是怎么去统计交换的次数。

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
33
34
35
36
37
38
39
40
41
42
43
private static void merge_sort(int[] array){
        merge_sort(array,0,array.length-1);
    }
    private static void merge_sort(int[] array,int begin,int end){
        if(begin>end){
            return;
        }
            int mid = (begin+end)/2;
            //不断的递归划分
            merge_sort(array,begin,mid);
            merge_sort(array,mid+1,end);
            //划分结束，进入合并阶段
            int[] temp = new int[end-begin+1];
            int i = begin,j = mid+1,p = 0;
            while (i<=mid && j<=end){
                if(array[i]<array[j]){
                    temp[p] = array[i];
                    p++;
                    i++;
                }else {
                    temp[p] = array[j];
                    p++;
                    j++;
                }
            }
            //左边部分还没完全放进去
            if(i<=mid){
                while (i<=mid){
                    temp[p++] = array[i];
                    i++;
                }
            }
            if(j<=end){
                while (j<=end){
                    temp[p++] = array[j];
                    j++;
                }
            }
            for(int k = 0;k<end-begin+1;k++){
                array[begin++] = temp[k];
            }
    }

然后在归并排序的基础上，求解，在merge的过程中，来统计次数，最终的代码如下：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class Solution {
    public int InversePairs(int [] array) {
        return merge(array, 0, array.length-1);
    }

    public int merge(int[] nums, int start, int end){
        if(start >= end){//分解到不能分解的时候的边界
            return 0;
     }
        int mid = (start + end)/2;// mid为中心左右各一半
        int count = 0;
        count += merge(nums, start, mid);
        count += merge(nums,mid+1, end);
        //上面两行是反复对问题进行分解，直到分解到最小
        //将最小问题合并成次小问题之后的处理，也是最核心的部分
        int[] temp = new int[end-start+1];
//temp数组:构建一个和当前合并的数组大小一样的数组，temp就是将两部分合并并且排序
        int i = start;//合并是左边和右边合并，一个指向左边的元素的指针
        int j = mid+1;//一个指向右边的元素的指针
        int p = 0;//temp中的指针
        while(i <= mid && j <= end){//左边部分的边界mid，右边部分的边界end
//这个while实际就是将两个部分，进行合并的时候排序。
            if(nums[i] < nums[j]){
                temp[p] = nums[i];
                p++;  //先复制，再++,对我而言可读性更高，逻辑理解更通顺。
                i++;
            }else{//否则，i就比j大，就说明出现了逆序对，因此维护count。
//这里值得说道说道，temp的长度等于左边+右边的长度。既然有了排序的念头，那么合并之前也排好了
//那么左边部分已经有序，右边部分也有序，比如此时进行{1,5,9}和{3,7,8}合并
//则i=1,mid=2,j=3时进入else，可以看到，通过mid-i+1=2，拿到的是{5,3}，{9,3}两组逆序对
//所以count+2,然后j的角标移动，下次比较的是5和7了。这样避免了重复的比较，提高了效率
//这样的操作必须配合排序，如果不排序，就不能这么玩，而不能这么玩的时候，过程如下：
//{1,5,9}和{3,7,8}合并,由于不知道是否有序，5和3形成逆序后，应当count++
//然后移动一次你自己标记的指针。然后你总会通过移动指针比较一次9和3，然后count++。
//而通过排序，这两个count++就变成了一次操作，因此，排序会提升效率，空间复杂度稍微高点。
//因为你用到了额外的数组，合并排序，并且再复制给原数组。
                count = (count+(mid-i+1))%1000000007;
                temp[p] = nums[j];
                p++;
                j++;
            }
        }
//下面的过程也值得一提，当两个序列合并时，左边或者右边先通过指针移动完毕，全复制进temp后，
//就需要将另一边的数据，也全部复制给temp。
//所以下面两个if分别对应左边先复制完了，专门去复制右边，和右边先复制完了，再去复制左边。
        if(i <= mid){
            while(i <= mid){
                temp[p++] = nums[i];
                i++;
            }
        }
        if(j <= end){
            while(j <= end){
                temp[p++] = nums[j];
                j++;
            }
        }
        for(int k = 0;k < end-start+1; k++){//将合并好的数组再复制回nums，以保证有序。
            nums[start+k] = temp[k];
        }
     return count;
    }
}
//这里再谈谈%1000000007的理解，应该是为了防止溢出，所以必须在每次加的时候进行操作
//而不能放在return语句中

48.矩阵中的路径(回溯)

题目描述

判断一个矩阵中是否存在一条包含某个字符串所有字符的路径，每一步可以往上下左右移动。如果一条路径经过了矩阵中的某一个格子，则该路径不能再次进入。

解题思路

明显的回溯搜索，这里需要对回溯和递归有深入的了解。一般回溯都隐藏在递归函数的下面。其实是一种纯暴力的搜索，穷举的过程就是遍历一棵多叉树，回溯算法的代码框架和多叉树遍历的代码框架类似：

  • 回溯算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    List<Value> result;
    void backtrack(路径,选择列表){
        if(满足结束条件){
            result.add(路径);
            return;
        }
        for(选择：选择列表){
            做选择;
            backtrace(路径，选择列表);
            撤销选择;
        }
    }

  • 多叉树搜索遍历

    1
    2
    3
    4
    5
    6
    7
    8
    void traverse(TreeNode root){
        if(root == null){
            return;
        }
        for(TreeNode chile:root.chileren){
            traverse(child);
        }
    }

这里通过全排列的题目进行抛砖引玉，题目就是输入一组不重复的数字，输出这些数字的全排列，代码示例如下：

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.*;

import java.util.*;
public class Solution {
    //存储全排列的结果
    List<List<Integer>> res = new LinkedList<>();
    //主函数，输入一组不重复的数字，返回全排列
    public List<List<Integer>> permute(int[] nums){
        //记录一次可行解
        LinkedList<Integer> track = new LinkedList<>();
        backtrace(nums,track);
        return res;
    }
    //回溯算法框架
    void backtrace(int[] nums,LinkedList<Integer> track){
        //到达叶子结点，将路径装入结果列表
        if(track.size()==nums.length){
            res.add(new LinkedList<>(track));
            return;
        }
        for(int i = 0;i< nums.length;i++){
            //排除不合法的选择
            if(track.contains(nums[i]))continue;
            //做选择
            track.add(nums[i]);
            //进入下一层决策树
            backtrace(nums,track);
            //取消选择
            track.removeLast();
        }
    }
}

这里顺便记录一下时间复杂度，对于递归函数来说，时间复杂度就是$递归函数本身的时间复杂度*递归函数调用的次数$​​​​，调用次数就是递归树上节点的个数，这里的trace的复杂度，首先一个for循环，是o(n)，然后里面的contains函数，也是o(n)，所以是$o(n^2)$​​​​​，递归树的节点$n!$​​​，所以总的时间复杂度就是$o(n^2)*o(n!)$​​​。

最后对于这题来说，方法就是从一点出发，然后不断的去上下左右寻找，寻找到一条路径，那么算法就结束了。关键是回溯的算法怎么写。

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
33
34
35
36
public class Solution {
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        char[] words = word.toCharArray();
        for(int i = 0;i<matrix.length;i++){
            for(int j = 0;j<matrix[0].length;j++){
                if(hashPath(matrix,words,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean hashPath(char[][] matrix,char[] words,int i,int j,int index){
        //先判断边界,这里的index记录了当前的路径长度
        if(i>=matrix.length || i<0 || j>=matrix[0].length || j<0 || matrix[i][j]!=words[index]){
            return false;
        }
        //递归查找
        if(index == words.length-1){
            return true;
        }
        //进入递归之前先加入
        char temp = matrix[i][j];
        matrix[i][j] = '/';
        if(hashPath(matrix,words,i-1,j,index+1)||
                hashPath(matrix,words,i+1,j,index+1)||
                hashPath(matrix,words,i,j+1,index+1)||
                hashPath(matrix,words,i,j-1,index+1)){
            //说明找到了可行解，释放，然后返回
            matrix[i][j] = temp;
            return true;
        }
        return true;
    }
}

49.剪绳子

题目描述

绳子长度n，剪成m段，每段k[1]…k[m]，求$k[1]*…*k[m]$​最大值。

条件：m,n整数，n>1,m>1,m<=n

解题思路

这题其实思路很简单，使用动态规划的方法，对于一段绳子，长度为i，比如绳子是6，可以先剪掉2（j），因为剪掉1没没收益，那么剩下4，也可以先减掉3，剩下3，最多先剪5，剩下1，先剪6的话，乘积就是0了，先剪掉2的话，dp[2] = 1，剩下i-j，剩下的i-j可以选择继续剪，也可以选择不剪了，如果不剪了，现在的乘积就是2*（6-2），也就是j*(i-j)。如果接着剪，那么乘积就是j*dp[i-j]，所以最后的状态转移方程就是：

$max(dp[i],max(j*(i-j),j*dp[i-j]))$​

code

1
2
3
4
5
6
7
8
9
10
11
public int cutRope(int target) {
    int[] dp = new int[target+1];
    dp[2] = 1;
    for(int i = 3;i<target+1;i++){
        for(int j = 2;j<i;j++){
            //模拟剪绳子
            dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
        }
    }
    return dp[target];
}

50.树的子结构

题目描述

输入两个树A，B，判断B树是不是A树的子树，规定空树不是任何树的子树

解题思路

这题一开始想的是子树的遍历有没有规律可循，后来发现没有，这里树的问题应该培养递归思维。

正确的匹配过程应该是这样的：

  • 遍历A中的节点Na（method A）
  • 以NA为节点的子树，是不是包含B（method B）
  • B中的逻辑是
    • A和B一起走，A走到null说明失败，B走到null说明成功
    • 然后AB同时向左，AB同时向右，返回结果

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        //遍历，2的节点全在1中并且顺序相同，是子树--->不妥
        if(root1==null || root2==null)return false;
        return oneNode(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);

    }
    //判断以一个节点为根的树是否包含
    public boolean oneNode(TreeNode A,TreeNode B){
        //如果走到了B的末尾，说明匹配成功了
        if(B==null)return true;
        if(A==null || A.val!=B.val)return false;
        return oneNode(A.left,B.left)&&oneNode(A.right,B.right);
    }
}

51.顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

解题思路

感觉是一道模拟题，代码的各种边界可能不是特别好写，那么好，这一题其实就是一个模拟。

思路是，先走最外面一圈，然后修改边界，走再里面一圈。

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
33
34
35
36
37
38
39
40
41
42
import java.util.ArrayList;
public class Solution {
    public static void main(String[] args) {

    }
    public static ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> res = new ArrayList<>();
        if(matrix==null || matrix.length == 0 || matrix[0].length==0){
            return res;
        }
        int hang = matrix.length-1,lie = matrix[0].length-1;
        //设置一开始的的边界
        int right = lie,down = hang,left = 0,up = 0;
        while (true) {
            //先走最上面一行
            for(int i = left;i<=right;i++){
                res.add(matrix[up][i]);
            }
            //往下,走完一行，往上走的途径少了一个
            up++;
            if(up>down)break;
            for(int i = up;i<=down;i++){
                res.add(matrix[i][right]);
            }
            //往左
            right--;
            if(right<left)break;
            for(int i = right;i>=left;i--){
                res.add(matrix[down][i]);
            }
            //往上
            down--;
            if(down<up)break;
            for(int i = down;i>=up;i--){
                res.add(matrix[i][left]);
            }
            left++;
            if(left>right)break;
        }
        return res;
    }
}

52.二叉树的后续遍历搜索

题目描述

输入一个整数数组，判断该数组是不是二叉搜索树后续遍历的结果，返回true或者false。空树不是二叉搜索树。

解题思路

二叉搜索树的定义是，所有左边比根小，所有右边比根大，且每一个子树也符合规则。

二叉搜索树的中序遍历是有序的，后续基本没啥规律。但是树啊，就一定用到递归了。先想办法从搜索树的后续遍历数组还原搜索树，然后终须遍历搜索树查看是否有序。

事实证明上述可以写出代码，但是超时。

利用后续遍历的特性，最后一个是根，然后前面可以划分成两个区间，前面比root小，后面比root大，然后再递归调用，不符合这样的条件的返回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
27
28
29
30
31
32
33
34
public class Solution {
    boolean flag = true;
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0)return false;
        help(sequence,0,sequence.length-1);
        return flag;
    }

    public void help(int[] arr,int left,int right){
        if(left<right){
            int root = arr[right];
            int index;
            //找到分割点
            for(index = left;index<right;index++){
                if(arr[index]>root){
                    break;
                }
            }
            int mid = index-1;
            while (index<right){
                if(arr[index]<root){
                    flag = false;
                    break;
                }
                index++;
            }
            if(flag){
                help(arr,left,mid);
                help(arr,mid+1,right-1);
            }
        }
    }

}

53.二叉树中和为某一个值的路径

题目描述

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

解题思路

肯定是回溯了.这里第21行，直接把path添加进去是不行的，因为java传的是引用。直接添加进去，最后每次的结果都会被修改。

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
import java.util.ArrayList;
import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        //用于回溯和每次的可行解
        ArrayList<Integer> each_res = new ArrayList<>();
        if(root==null)return res;
        back_trace(root,each_res,target);
        return res;
    }

    public void back_trace(TreeNode root,ArrayList<Integer> patch,int target){
        //回溯算法
        if(root==null)return;
        //先把当前根节点加入结果集
        patch.add(root.val);
        target -= root.val;
        if(target==0 && root.left==null && root.right==null){
            res.add(new ArrayList<>(patch));
        }else {
            back_trace(root.left,patch,target);
            back_trace(root.right,patch,target);
        }
        patch.remove(patch.size()-1);
    }

}
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

请我喝杯咖啡吧~

支付宝
微信