中级提升班6

题目一打印目录

给你一个字符串类型的数组arr，譬如:

1	String[] arr = { "b\\cst", "d\\", "a\\d\\e", "a\\b\\c”};

你把这些路径中蕴含的目录结构给画出来，子目录直接列在父目录下面，并比父目录向右进两格，就像这样:

a
  b
    c
  d
    e
b
  cst
d

同一级的需要按字母顺序排列，不能乱。

解

经典前缀树题目

public static class Node {
    public String name;
    // 有序打印
    public TreeMap<String, Node> nextMap;

    public Node(String name) {
        this.name = name;
        nextMap = new TreeMap<>();
    }
}

public static void print(String[] folderPaths){
    if (folderPaths == null ||folderPaths.length == 0){
       return;
    }
    Node header = generateFolderTree(folderPaths);
    printProcess(header, 0);
}

public static Node generateFolderTree(String[] folderPaths) {
    Node head = new Node("");
    for (String foldPath : folderPaths) {
        String[] paths = foldPath.split("\\\\");
        Node cur = head;
        for (String path : paths) {
            if (!cur.nextMap.containsKey(path)) {
                cur.nextMap.put(path, new Node(path));
            }
            cur = cur.nextMap.get(path);
        }
    }
    return head;
}

public static void printProcess(Node node, int level) {
    if (level != 0) {
        System.out.println(get2nSpace(level) + node.name);
    }
    for (Node next : node.nextMap.values()) {
        printProcess(next, level + 1);
    }
}

private static String get2nSpace(int n) {
    String res = "";
    for (int i = 0; i < n; n++) {
        res += "  ";
    }
    return res;
}

题目二搜索二叉树转换双向链表

双向链表节点结构和二叉树节点结构是一样的，如果你把last认为是left，next认为是next的话。
给定一个搜索二叉树的头节点head，请转化成一条有序的双向链表，并返回链表的头节点。

剑指 Offer 36. 二叉搜索树与双向链表

解

使每个节点左子树形成链表，右子树形成链表，使当前节点与左链表的尾节点和有链表的首节点相连。

public static class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}

//  搜索二叉树转为为双向链表后，头和尾返回
public static class Info {
    public Node start;
    public Node end;

    public Info(Node start, Node end) {
        this.start = start;
        this.end = end;
    }
}
// 以x为头的整棵搜索二叉树，请全部以有序双向链表的方式，连好
// 并且返回，整个有序双向链表的头节点和尾节点
public static Info process(Node x) {
    if (x == null) {
        return new Info(null, null);
    }
    Info left = process(x.left);
    Info right = process(x.right);
    if (left.end != null) {
        left.end.right = x;
    }
    x.left = left.end;
    x.right = right.start;
    if (right.start != null) {
        right.start.left = x;
    }
    return new Info(left.start != null ? left.start : x, right.end != null ? right.end : x);
}

public Node treeToDoublyList(Node root) {
    if (root == null){
        return null;
    }
    Info info = process(root);
    Node header = info.start;
    Node tail = info.end;
    header.left = tail;
    tail.right = header;
    return header;
}

题目三最大搜索二叉子树

找到一棵二叉树中，最大的搜索二叉子树，返回最大搜索二叉子树的节点个数。

解

一个节点，左树是搜索二叉树，右树也是搜索二叉树，那么左树的最大值小与当前节点，右树的最小值大于当前节点。

递归需要4个值，子树的投节点，是否是搜索二叉树，最大值，最小值，二叉搜索子树的大小

已知一棵二叉树中没有重复节点，并且给定了这棵树的中序遍历数组和先序遍历数组，返回后序遍历数组。
比如给定:。

1	int[] pre = { 1,2,4.5, 3,6,7 } ;int[] in = { 4,2,5,1,6,3,7 };

返回:
{4,5,2,6,7,3,1}

题目四二叉树先序中序还原后序

已知一棵二叉树中没有重复节点，并且给定了这棵树的中序遍历数组和先序遍历数组，返回后序遍历数组。
比如给定:
int[] pre = { 1,2,4,5,3,6,7 } ;int[] in = { 4,2,5,1,6,3,7 };返回:
{4,5,2,6,7,3,1}

public static int[] getPostArray(int[] pre, int[] in) {
    if (pre == null) {
        return null;
    }
    int N = pre.length;
    int[] pos = new int[N];
    set(pre, in, pos, 0, N - 1, 0, N - 1, 0, N - 1);
    return pos;
}

// 利用pre[prei...prej] 结合in[ini...inj]
private static void set(int[] pre, int[] in, int[] pos, int prei, int prej, int ini, int inj, int posi, int posj) {

    if (prei > prej) {
        return;
    }
    if (prei == prej) {
        pos[posi] = pre[prei];
        return;
    }
    pos[posj] = pre[prei];
    int find = ini;
    for (; find <= inj; find++) {
        if (in[find] == pre[prei]) {
            break;
        }
    }
    set(pre, in, pos, prei + 1, prei + find - ini, ini, find - 1, posi, posi + find - ini - 1);
    set(pre, in, pos, prei + find - ini + 1, prej, find + 1, inj, posi + find - ini, posj - 1);

}

题目五路灯放法

小Q正在给一条长度为n的道路设计路灯安置方案。
为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用’.‘表示，不需要照亮的障碍物格子用’X‘表示。小Q现在要在道路上设置一些路灯，对于安置在pos位置的路灯，这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。小Q希望能安置尽量少的路灯照亮所有’.’区域，希望你能帮他计算一下最少需要多少盏路灯。
输入描述:
输入的第一行包含一个正整数t(1<= t<1000)，表示测试用例数
接下来每两行一个测试数据，第一行一个正整数n(1 <= n <= 1000),表示道路的长度。第二行一个字符串s表示道路的构造,只包含’.‘和’X’。
输出描述:
对于每个测试用例,输出一个正整数表示最少需要多少盏路灯。

public static int minLight(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    char[] str = s.toCharArray();
    int ans = 0;
    int i = 0;
    while (i < str.length) {
        if (str[i] == 'X') {
            i++;
        } else { // .
            ans++;
            // 来到当前位置，保证之前的灯，不会影响到当前位置
            if (i + 1 == str.length) {
                break;
            } else {
                if (str[i + 1] == 'X') {
                    i += 2;
                } else {
                    //下个位置是.在i+1放
                    i += 3;
                }
            }

        }
    }
    return ans;
}

还有一种解法，求连续.的个数除3后+1就是结果

题目六最大子数组和

为了保证招聘信息的质量问题，公司为每个职位设计了打分系统，打分可以为正数，也可以为负数，正数表示用户认可帖子质量，负数表示用户不认可帖子质量.打分的分数根据评价用户的等级大小不定，比如可以为41分，10分，30分，-10分寺。假攻数组A记录了一条帖子所有打分记录，现在需要找出帖子曾经得到过最高的分数是多少，用于后续根据最高分数来确认需要对发帖用户做相应的惩罚或奖励．其中，最高分的定义为:用户所有打分记录中，连续打分数据之和的最大值即认为是帖子曾经获得的最高分。例如:帖子10001010近期的打分记录为[1,1,-1,-10,11,4,-6,9,20,-10,-2],那么该条帖子曾经到达过的最高分数为11+4+(-6)+9+20=38。请实现一段代码，输入为帖子近期的打分记录，输出为当前帖子得到的最高分数。

leetcode 53 最大子数组和

解

0-n的数组，假设a-b最大，a-b累加和一定大于0，0-a累加和一定小于0

public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int cur = 0;
    int max = nums[0];
    for (int i = 0; i < nums.length; i++) {
        cur = Math.max(nums[i], cur + nums[i]);
        max = Math.max(max, cur);
    }

    return max;
}