题目
- 给定 n 对括号，请写一个函数以将其生成新的括号组合，并返回所有组合结果。
- 寻找目录的最大长度： https://www.lintcode.com/problem/longest-absolute-file-path/description
- 给定一个整数n，返回n!（n的阶乘）的尾随零的个数
实现代码
- 第一个实现思路比较清晰
- 直接进行递归调用函数即可
- 注意表达式有效仅仅在左括号出现比较多的情况
public class Solution {
/*** @param n: n pairs* @return: All combinations of well-formed parentheses*/public List<String> generateParenthesis(int n) {// write your code hereList<String> results = new ArrayList<>();getParent(n,n,results,"");return results;}public void getParent(int left,int right,List<String> results,String index){if (left == 0 && right == 0){results.add(index);return;}if (left > 0){String tempLeft = index + "(";getParent(left-1,right,results,tempLeft);}if (right > left){String tempRight = index + ")";getParent(left,right-1,results,tempRight);}}
}
- 因为可能存在文件名很长的文件，因此必须统计到每一个节点
- 开始想的是通过多路树，进行一个
BFS或者DFS进行一次遍历 - 或者使用二叉树，使用左孩子右兄弟的方式进行遍历
- 然后想到将文件名加入到树里面的过程就已经完成了遍历
- 问题就变成了怎么将文件名分开：
- 首先使用
split("\n")分成不同的行，对于每一行判断相对于根目录是第几层目录，这样每一次到后续没有目录，实现一个DFS遍历 - 使用一个数组记录所有遍历时上一层目录的长度即可
public class Solution {
/*** @param input: an abstract file system* @return: return the length of the longest absolute path to file*/public int lengthLongestPath(String input) {// write your code hereif (input == null || input.length() == 0) return 0;int[] lengths = new int[input.length() + 1];int ans = 0;for (String line : input.split("\n")) {int level = getLevel(line);int len = line.length() - level + 1;// 如果没有扩展文件if (line.contains(".")){ans = Math.max(ans,lengths[level - 1] + len);} else {lengths[level] = lengths[level - 1] + len + 1;}}return ans;}public int getLevel(String line){int index = 1;for(int i = 0; i < line.length(); i ++){if (line.charAt(i) != '\t'){return index;}index ++;}return index;}
}
- 满足成0的最基本的要求就是要有一个2和5
- 每5个在一起提取出系数以后会有一个0
trailingZeroes(n/5)表示系数中含有的0，n/5表示有多少组
public class Solution {
/*** @param n: a integer* @return: return a integer*/public int trailingZeroes(int n) {// write your code herereturn n < 5 ? 0 :trailingZeroes(n/5) + n/5;}
}
git 地址： https://github.com/Outliwer/LintCode_Result