《剑指offer》牛客网61-67

发表于 | 阅读数
字数统计: 1.8k | 阅读时长 ≈ 8

61.序列化二叉树

题目描述
请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

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
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

}
*/
public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if(root == null){
            sb.append("#!");
            return sb.toString();
        }
        sb.append(root.val + "!");
        sb.append(Serialize(root.left));
        sb.append(Serialize(root.right));
        return sb.toString();
  }
    int index = -1;
    TreeNode Deserialize(String str) {
        index++;
        String[] str1 = str.split("!");
        int len = str1.length;
        if(index > len)
            return null;
        TreeNode node = null;
        if(!str1[index].equals("#")){
            node = new TreeNode(Integer.valueOf(str1[index]));
            node.left = Deserialize(str);
            node.right = Deserialize(str);
        }
        return node;
  }
}

62.二叉搜索树的第k个结点

题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

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
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

}
*/
import java.util.ArrayList;
// {8,6,10,5,7,9,11},8
// null,5
public class Solution {
    ArrayList<TreeNode> list = new ArrayList<>(); // (1)

    TreeNode KthNode(TreeNode pRoot, int k)
    {
        addNode(pRoot);
     
        if(k>=1 && list.size()>=k) {
            return list.get(k-1);
        }
     
        return null;
     
    }
     
    // 中序遍历
    void addNode(TreeNode cur) {   // (2)
        if(cur != null) {
            addNode(cur.left);
            list.add(cur);
            addNode(cur.right);
        }
    }

}

63.数据流中的中位数

题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.PriorityQueue;

public class Solution {

    PriorityQueue<Integer> min=new PriorityQueue<>();
    PriorityQueue<Integer> max=new PriorityQueue<>((a,b)->b-a);
     
    public void Insert(Integer num) {
        max.add(num);
        min.add(max.remove());
        if (min.size()>max.size())
            max.add(min.remove());
    }
     
    public Double GetMedian() {
        if (min.size() == max.size()){
            return (max.peek()+min.peek())/2.0;
        } else{
            return(double)max.peek();
        }
    }

}

64.滑动窗口的最大值

题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

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

public class Solution {
    public ArrayList<Integer> maxInWindows(int[] num, int size) {

        ArrayList<Integer> list = new ArrayList<Integer>();
        Deque<Integer> deque = new LinkedList<Integer>();
        if (num == null || size <= 0 || size > num.length) {
            return list;
        }
     
        for (int i = 0; i < num.length; i++) {
     
            while (!deque.isEmpty() && num[i] >= num[deque.peekLast()]) {
                deque.removeLast();
            }
            if (!deque.isEmpty() && i - deque.peekFirst() >= size) {
                deque.removeFirst();
            }
            deque.addLast(i);
            if (i >= size - 1) {
                list.add(num[deque.peekFirst()]);
            }
        }
        return list;
    }

}

65.矩阵中的路径

题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    boolean[] visited = null;
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        visited = new boolean[matrix.length];
        for(int i = 0; i < rows; i++)
            for(int j = 0; j < cols; j++)
                if(subHasPath(matrix,rows,cols,str,i,j,0))
                    return true;
        return false;
    }

    public boolean subHasPath(char[] matrix, int rows, int cols, char[] str, int row, int col, int len){
        if(matrix[row*cols+col] != str[len]|| visited[row*cols+col] == true) return false;
        if(len == str.length-1) return true;
        visited[row*cols+col] = true;
        if(row > 0 && subHasPath(matrix,rows,cols,str,row-1,col,len+1)) return true;
        if(row < rows-1 && subHasPath(matrix,rows,cols,str,row+1,col,len+1)) return true;
        if(col > 0 && subHasPath(matrix,rows,cols,str,row,col-1,len+1)) return true;
        if(col < cols-1 && subHasPath(matrix,rows,cols,str,row,col+1,len+1)) return true;
        visited[row*cols+col] = false;
        return false;
    }

}

66.机器人的运动范围

题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

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 Solution {
    public int movingCount(int threshold, int rows, int cols) {
    int flag[][] = new int[rows][cols]; //记录是否已经走过
    return helper(0, 0, rows, cols, flag, threshold);
}

    private int helper(int i, int j, int rows, int cols, int[][] flag, int threshold) {
    if (i < 0 || i >= rows || j < 0 || j >= cols ||
            numSum(i) + numSum(j) > threshold || flag[i][j] == 1)
        return 0;
    flag[i][j] = 1;
    return helper(i - 1, j, rows, cols, flag, threshold)
            + helper(i + 1, j, rows, cols, flag, threshold)
            + helper(i, j - 1, rows, cols, flag, threshold)
            + helper(i, j + 1, rows, cols, flag, threshold) + 1;

}

private int numSum(int i) {
    int sum = 0;
    while (i > 0) {
        sum += i % 10;
        i = i / 10;
    }
    return sum;
}

}

67.剪绳子

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
输入描述:
输入一个数n，意义见题面。（2 <= n <= 60）
输出描述:
输出答案。
示例1
输入
8
输出
18

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int cutRope(int target) {
        if(target<2)
            return 0;
        if(target==2)
            return 1;
        if(target==3)
            return 2;
        if(target==4)
            return 4;
        int of3=target/3;
        if(target-of3==1)
            of3--;
        int of2=(target-of3*3)/2;
        return (int) Math.pow(3,of3)*(int)Math.pow(2,of2);

    }

}
-------------本文结束感谢您的阅读-------------
0%