本文共 3863 字，大约阅读时间需要 12 分钟。
大家好，我是烤鸭，不得不承认，这是水了一篇博客，贴几道最近刷的简单的算法题。
给定一个整数n，按字典顺序返回1 - n。
例如，给出13，返回：[1,10,11,12,13,2,3,4,5,6,7,8,9]。
请优化您的算法以节省时间和空间。输入大小可能高达5,000,000。
public static ListlexicalOrder(int n) { List ans = new ArrayList<>(n); for (int i = 1, curr = 1; i <= n; ++i) { ans.add(curr); if (curr * 10 <= n) { curr *= 10; } else { while (curr % 10 == 9 || curr == n) curr /= 10; curr++; } } return ans; } public static void main(String[] args) { System.out.println(lexicalOrder(13)); }
2. Longest Absolute File Path
假设我们按照以下方式通过字符串来抽象我们的文件系统： 该字符串"dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"表示： dir subdir1 subdir2
file.ext
该目录dir包含一个空的子目录subdir1和一个subdir2包含文件的子目录file.ext。 该字符串"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"表示： dir subdir1 file1.ext subsubdir1 subdir2 subsubdir2file2.ext
该目录dir包含两个子目录subdir1和subdir2。subdir1包含一个文件file1.ext和一个空的二级子目录subsubdir1。subdir2包含一个subsubdir2包含文件的二级子目录file2.ext。 我们感兴趣的是找到文件系统中文件的最长（字符数）绝对路径。例如，在上面的第二个例子中，最长的绝对路径是"dir/subdir2/subsubdir2/file2.ext"，其长度是32（不包括双引号）。 给定一个以上述格式表示文件系统的字符串，将最长的绝对路径的长度返回到抽象文件系统中的文件。如果系统中没有文件，则返回0。 注意： 文件的名称至少包含一个.和一个扩展名。 目录或子目录的名称将不包含.。 所需时间复杂度：O(n)这里n是输入字符串的大小。
a/aa/aaa/file1.txt如果还有其他路径，请注意这不是最长的文件路径aaaaaaaaaaaaaaaaaaaaa/sth.png。
public static int lengthLongestPath(String input) { Deque stack = new ArrayDeque<>(); stack.push(0); // "dummy" length int maxLen = 0; for(String s:input.split("\n")){ int lev = s.lastIndexOf("\t")+1; // number of "\t" int pop = 0; while(lev+1 以上是对着discuss的高票答案改了改。
3. Robot sequence of its moves
最初，位置（0,0）处有一个机器人。给出它的一系列动作，判断这个机器人是否有一个圆圈，这意味着它移回到原来的位置。
移动顺序由一个字符串表示。而每一个动作都是由一个人物来表现的。有效的机器人移动是R（右），L（左），U（上）和D（下）。输出应该是真或假，表示机器人是否做出圆圈。 例1： 输入： “UD” 输出： true 例2： 输入： “LL”输出：false
这题太简单了。。。。高票答案是用的switch,我用的if else。
public static boolean judgeCircle(String moves) { Boolean flag = false; int up =0,down =0,left =0,right =0; for (char move:moves.toCharArray()) { if(move == 'U') up++; if(move == 'D') down++; if(move == 'L') left++; if(move == 'R') right++; } if(left == right && up == down) flag = true; return flag; } public static void main(String[] args) { System.out.println(judgeCircle("LL")); } 4. Find All Anagram sina String
给定一个字符串小号和非空字符串p，找到的所有开始指数p中的字谜小号。 字符串只包含小写英文字母，字符串s和p的长度不会超过20,100。 输出的顺序并不重要。 例1： 输入： s：“cbaebabacd”p：“abc” 输出：[ 0，6 ]
说明：
起始索引= 0的子字符串是“cba”，它是“abc”的一个字母组合。 起始索引= 6的子字符串是“bac”，它是“abc”的一个字母组合。 例2：输入： s：“abab”p：“ab” 输出： [0，1，2]
说明：
起始索引= 0的子字符串是ab，它是ab的一个字母组合。 开始索引= 1的子字符串是“ba”，它是“ab”的一个字母组合。起始索引= 2的子字符串是“ab”，它是“ab”的一个字母组合。
自己写的答案，效率没有高票的快。
public static ListfindAnagrams(String s, String p) { //cbaebabacd ArrayList list = new ArrayList<>(); char[] array = s.toCharArray(); for (int sir = 0; sir < array.length - p.length() + 1; sir++) { String sirs = s.substring(sir, sir + p.length()); char[] arraySirs = sirs.toCharArray(); char[] arrayP = p.toCharArray(); int sirRes = 0, pRes = 0; for (int l = 0; l < (arraySirs.length>arrayP.length?arraySirs.length:arrayP.length); l++) { sirRes += arraySirs[l] - 'a'; pRes += arrayP[l] - 'a'; } if (sirRes == pRes) list.add(sir); } return list; } public static void main(String[] args) { long first = System.nanoTime(); System.out.println(first); String s = "cbaebabacd"; String p = "abc"; System.out.println(findAnagrams(s, p)); System.out.println(System.nanoTime() - first); }
转载地址：http://qbmlf.baihongyu.com/