给你一个字符串类型的数组arr,譬如:
String[] arr = { "b\st", "d\", "a\d\e", "a\b\c" };
把这些路径中蕴含的目录结构给打印出来,子目录直接列在父目录下面,并比父目录向右进两格,就像这样:
a
b
c
d
e
b
cst
d
同一级的需要按字母顺序排列不能乱。
/**
* 给你一个字符串类型的数组arr,譬如:
* String[] arr = { "b\st", "d\", "a\d\e", "a\b\c" };
* 把这些路径中蕴含的目录结构给打印出来,子目录直接列在父目录下面,并比父目录向右进两格,就像这样:
* a
* b
* c
* d
* e
* b
* cst
* d
* 同一级的需要按字母顺序排列不能乱。
*/
public class PrintDir {
public static void printDir(String[] strs) {
if (strs == null || strs.length == 0) {
return;
}
// 生成前缀树
TreeNode prefixTree = getPrefixTree(strs);
// 打印前缀树
printPrefixTree(prefixTree, 0);
}
// 生成一棵前缀树,返回前缀树的根节点
private static TreeNode getPrefixTree(String[] strs) {
// 生成一个根节点
TreeNode root = new TreeNode("");
// 遍历每个单词,每个单词都在以'\'为分隔,挂在前缀树上
for (String word : strs) {
// 当前节点
TreeNode cur = root;
// 以'\'分隔每个单词
String[] dirs = word.split("\\\\");
// 挂在前缀树上
for (String dir : dirs) {
// 如果当前节点下面没有条路那么久建出来挂在当前节点下面,否则就复用当前节点
// 下面的路
if (!cur.nexts.containsKey(dir)) {
// 没有新建
cur.nexts.put(dir, new TreeNode(dir));
}
cur = cur.nexts.get(dir);
}
// 一条路径挂完了
cur.end = true;
}
return root;
}
private static void printPrefixTree(TreeNode root, int level) {
// 遍历前缀树打印
TreeNode cur = root;
// 如果当前是第0层直接打印
if (level == 0) {
System.out.println(cur.path);
} else {
System.out.println(blank(level) + cur.path);
}
// 深度遍历后续节点
for (Map.Entry entry : cur.nexts.entrySet()) {
printPrefixTree((TreeNode) entry.getValue(), level + 1);
}
}
// 加空格数
private static String blank(int level) {
String blank = "";
for (int i = 0; i < level; i++) {
blank += " ";
}
return blank;
}
public static void main(String[] args) {
String[] strs = new String[]{ "b\\st", "d\\", "a\\d\\e", "a\\b\\c" };
printDir(strs);
}
}
- 已知一棵二叉树中没有重复节点,并且给定了这棵树的中序遍历数组和先序遍历 数组,返回后序遍历数组。
比如给定:
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 class Post {
public static int[] post(int[] pre,int[] in){
if(pre == null || in == null || pre.length != in.length){
return null;
}
// 预处理
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < in.length; i++) {
map.put(in[i],i);
}
int[] post = new int[pre.length];
process(pre,0,pre.length-1,in,0,in.length-1,post,0,post.length-1,map);
return post;
}
// pre先序数组L1,R1分别表示先序中的子树的部分,同理in post有相同的含义
private static void process(int[] pre, int L1, int R1,
int[] in, int L2, int R2,
int[] post, int L3, int R3,
HashMap<Integer,Integer> map){
if(L1 > R1){
return;
}
if(L1 == R1){
post[L3] = pre[L1];
return;
}
// 先序数组第一元素填到后续,数组最后一个元素上
post[R3] = pre[L1];
// 找到中续遍历中的位置
int index = map.get(pre[L1]);
// for(int i = L2;i <= R2;i++){
// if(in[i] == pre[L1]){
// index = i;
// break;
// }
// }
// 左右部分长度
int len = index - L2;
process(pre,L1+1,L1+len,in,L2,index-1,post,L3,L3+len-1,map);
process(pre,L1+len+1,R1,in,index+1,R2,post,L3+len,R3-1,map);
}
public static void main(String[] args) {
int[] pre = { 1, 2, 4, 5, 3, 6, 7 };
int[] in = { 4, 2, 5, 1, 6, 3, 7 };
int[] post = post(pre, in);
for (int i :post){
System.out.print(i+" ");
}
}
}
/**
* 最长递增子序列问题的O(N*logN)的解法,严格递增
*/
public class MaxIncreasingSubSeq {
// O(N^2)解法
public static int maxIncreasingSubSeq(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
int n = arr.length;
int[] temp = new int[n];
// 以第一个元素结尾的最长递增子序列一定是自己1
temp[0] = 1;
// 预处理数组的有效区域
int r = 0;
int res = 0;
for (int i = 1; i < n; i++) {
int max = 0;
for (int j = r; j >=0; j--) {
if(arr[i] > arr[j]){
max = Math.max(max,temp[j]);
}
}
temp[i] = max+1;
r++;
res = Math.max(res,temp[i]);
}
return res;
}
// O(logn),
// 定义dp数组记录每个位置结尾时,最大递增子序列
// 辅助数组temp,第一个位置时dp[0] = 1,temp[0] = arr[0],后面依次遍历,每遍历到一个数
// ends[i]的最左边的位置,把它更新成arr[i],i位置结尾的最大递增子序列就是
// 此时0到此时找到的ends位置之间的元素个数,如果没有,扩充有效区ends,如此重复。
// ends[i] 长度为i+1的最长递增子序列的最小结尾。
public static int maxIncreasingSubSeq2(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
int n = arr.length;
int[] dp = new int[n];
int[] ends = new int[n];
dp[0] = 1;
ends[0] = arr[0];
// ends数组有效区
int right = 0;
int l = 0;
int r = right;
int mid = 0;
// 遍历数组,每遍历到一个数时,在ends中通过二分找到大于等于这个数的最左的位置更新,
// 起点到此时位置的元素个数之差就是i位置的最大递增子序列
int max = 0;
for (int i = 1; i < n; i++) {
l = 0;
r = right;
// 二分找大于等于当前数最左边的值
while (l <= r){
mid = l + ((r - l) >> 1);
if(ends[mid] >= arr[i]){
r = mid - 1;
}else {
l = mid + 1;
}
}
// 如果没有找到l会来打right+1的位子,更新right
// 找到了right 不变
right = Math.max(right,l);
ends[l] = arr[i];
dp[i] = l + 1;
max = Math.max(max,dp[i]);
}
return max;
}
public static void main(String[] args) {
int[] arr = new int[]{2,1,4,3,5,8,7,9};
int[] arr2 = new int[]{2,1,4,3,5,8,7,9};
System.out.println(maxIncreasingSubSeq(arr));
System.out.println(maxIncreasingSubSeq2(arr2));
//System.out.println(5+((9-5)>>1));
}
}
- 每个信封都有长和宽两个维度的数据,A信封如果想套在B信封里面,A信封必须在长和宽上都小于B信封才行。如果给你一批信封,返回最大的嵌套层数。
题解,利用最长递增子序列求解。
按照长从小到大排序,长一样按照宽从大到小排序。然后把排好序的信封的第二维数据拎出来,求他的最大递增子序列就是解。假设现在排好序中的i位置的宽是V ,那么以V结尾的最长递增子序列其实就是宽也比V小长也比位置长小的信封。
/**
* 每个信封都有长和宽两个维度的数据,A信封
* 如果想套在B信封里面,A信封必须在长和宽上都小于B信封才行。
* 如果给你一批信封,返回最大的嵌套层数
*/
public class Envelope {
public static int envelope(EnvelopeNode[] arr){
if(arr == null || arr.length == 0){
return 0;
}
Arrays.sort(arr,new MyComparator());
int[] dArr = new int[arr.length];
int index = 0;
for (EnvelopeNode item : arr){
dArr[index++] = item.d;
}
int i = maxIncreasingSubSeq2(dArr);
return i;
}
public static int maxIncreasingSubSeq2(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
int n = arr.length;
int[] dp = new int[n];
int[] ends = new int[n];
dp[0] = 1;
ends[0] = arr[0];
// ends数组有效区
int right = 0;
int l = 0;
int r = right;
int mid = 0;
// 遍历数组,每遍历到一个数时,在ends中通过二分找到大于等于这个数的最左的位置更新,
// 起点到此时位置的元素个数之差就是i位置的最大递增子序列
int max = 0;
for (int i = 1; i < n; i++) {
l = 0;
r = right;
// 二分找大于等于当前数最左边的值
while (l <= r){
mid = l + ((r - l) >> 1);
if(ends[mid] >= arr[i]){
r = mid - 1;
}else {
l = mid + 1;
}
}
// 如果没有找到l会来打right+1的位子,更新right
// 找到了right 不变
right = Math.max(right,l);
ends[l] = arr[i];
dp[i] = l + 1;
max = Math.max(max,dp[i]);
}
return max;
}
static class MyComparator implements Comparator<EnvelopeNode> {
@Override
public int compare(EnvelopeNode o1, EnvelopeNode o2) {
return o1.l != o2.l ? o1.l - o2.l : o2.d - o1.d;
}
}
public static void main(String[] args) {
EnvelopeNode[] arr = new EnvelopeNode[]{
new EnvelopeNode(3,2),
new EnvelopeNode(4,3),
new EnvelopeNode(5,6),
new EnvelopeNode(7,2),
new EnvelopeNode(6,3),
new EnvelopeNode(8,7),
new EnvelopeNode(3,2)
};
System.out.println(envelope(arr));
}
}
/**
* 给定一个数组arr,返回子数组的最大累加和。
*/
public class MaxArraySum {
public static int maxArraySum(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
// 定义变量cur如果当前累加和大于0那么就一直累加,累加过程中记录最大值,
// 当cur小于0时,把cur重置为0
int max = arr[0];
int cur = arr[0];
for (int i = 1; i < arr.length; i++) {
cur = cur < 0 ? 0 : cur;
cur += arr[i];
max = Math.max(max,cur);
}
return max;
}
public static void main(String[] args) {
int[] arr = new int[]{1,2,-3,4,2,-2,1,1,5,-9};
System.out.println(maxArraySum(arr));
}
}
- 给定一个整型矩阵,返回子矩阵的最大累计和。
流程:假设是一个n*m的矩阵,算00,01,02,......,0n-1,11,12,13...1n-1,.....n-1~n-1各自的累加和,求最大值,每一次求和时,可以吧多行压缩成一行让后转化为求一个数组的最大累加和问题。各个数组求最大值。
/**
* 给定一个整型矩阵,返回子矩阵的最大累计和。
*/
public class MatrixMaxSum {
public static int matrixMaxSum(int[][] matirx){
if(matirx == null || matirx[0].length == 0){
return 0;
}
int row = matirx.length;
int col = matirx[0].length;
int max = Integer.MIN_VALUE;
for (int i = 0; i < row; i++) {
int[] temp = new int[col];
for (int j = i; j < row; j++) {
int h = 0;
for (int k = 0; k < col; k++) {
temp[k] += matirx[j][k];
h += temp[k];
max = Math.max(max,h);
h = h < 0 ? 0:h;
}
}
}
return max;
}
public static void main(String[] args) {
int[][] matrix = new int[][]{ { -90, 48, 78 }, { 64, -40, 64 }, { -81, -7, 66 } };
System.out.println(matrixMaxSum(matrix));
}
}