6. ZigZag Conversion
68. Text Justification
71. Simplify Path
214. Shortest Palindrome
String Comparison
String Compression
6. ZigZag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string text, int nRows); convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
代码（特殊题目）：
/** * 找规律的题目，可以看出，第一行和最后一行的字符之间是没有字符的，而相互之间的关系是str.charAt(i + j); j = 0; j + i < n; j += 2 *(row - 1); * 而中间的行中，字符之间的字符的坐标是str.charAt(j + 2*(row - 1) - i) */ public class Solution { public String convert(String s, int numRows) { if (s == null || s.length() <= 1 || numRows <= 1) { return s; } int strLength = s.length(); StringBuilder tmpStr = new StringBuilder(); for (int i = 0; i < numRows; i++) { for (int j = 0; j + i < strLength; j += 2 * (numRows - 1)) { tmpStr.append(s.charAt(i + j)); if (i == 0 || i == numRows - 1) { continue; } int index = j + 2 * (numRows - 1) - i; if (index < strLength) { tmpStr.append(s.charAt(index)); } } } return new String(tmpStr); } } 68. Text Justification
Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters. Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right. For the last line of text, it should be left justified and no extra space is inserted between words. For example, words: ["This", "is", "an", "example", "of", "text", "justification."] L: 16. Return the formatted lines as: [ "This is an", "example of text", "justification. " ] Note: Each word is guaranteed not to exceed L in length.
思路：循环体内，每次构造一行。每次构造就用j来试试最大能插入几个单词到该行。average代表该行正常的相隔多少个空间。extra是求余得到的余数，也就是多出来没分配的空格优先分配在左边的相隔区间。因为要保证除了只有一个单词的和最后一行外，都是贴着左右两边的。利用字符数组来构造空格。最后的代码是针对最后一行或者只有一个单词的情况。因为一般的其它行tmpStr.length() - maxLength == 0了。
public class Solution { public List<String> fullJustify(String[] words, int maxWidth) { List<String> ans = new ArrayList<>(); if (words == null || words.length == 0) { return ans; } int wordNum = words.length; int i = 0; while (i < wordNum) { // see how many words this line can contain int curLength = 0; int j = i; while (j < wordNum && curLength + words[j].length() + (j - i) <= maxWidth) {// 错误1等于号 curLength += words[j].length(); j = j + 1; } // confirm the average spaces and extra spaces // 这里有两种情况，如果不是最后一行，词与词之间的空格由除法决定，还可能有extra space，因为要 // left justified 和 right justified. // 如果是最后一行，average = 1，然后extra为0 // 最后还有可能用到average和extra的是one word的时候 boolean lastLine = (j == wordNum); boolean oneWord = (j == i + 1); int average = (lastLine || oneWord) ? 1 : ((maxWidth - curLength) / (j - i - 1));//错误2：注意这里j已经是提前走了一部步，所以要减1 int extra = (lastLine || oneWord) ? 0 : ((maxWidth - curLength) % (j - i - 1)); // Build the string of this line. StringBuilder tmpStr = new StringBuilder(words[i]); for (int k = i + 1; k < j; k++) { char[] tmp = new char[extra > 0 ? average + 1 : average]; Arrays.fill(tmp, ' '); tmpStr.append(tmp); tmpStr.append(words[k]); extra = extra - 1; } // in case of one word or last line. char[] tmp = new char[maxWidth - tmpStr.length()]; Arrays.fill(tmp, ' '); tmpStr.append(tmp); ans.add(new String(tmpStr)); i = j; } return ans; } } 71. Simplify Path Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" click to show corner cases. Corner Cases: Did you consider the case where path = "/../"? In this case, you should return "/". Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/". In this case, you should ignore redundant slashes and return "/home/foo".
思路：一旦遇到”..“，就把已经存起来的路径的最新一个删掉。（如果存起来的数据结构里面有元素的话）。接着，就算存储的结构里面没有元素的话，也会返回一个”/“。但是，最后一个”/”需要去掉。最后需要注意的是如果有"//"的话，需要使用"/+"的正则表达式。
public class Solution { public String simplifyPath(String path) { if (path == null || path.length() == 0) { return path; } //用一个ArrayList记录需要用的路径字符串，注意不考虑"."和""。 //如果遇到..的话就删除最近的一个字符串（在arraylist有内容的时候） //注意最后一个slash要去掉 List<String> res = new ArrayList<>(); String[] analysis = path.split("/+"); for (String tmp : analysis) { if (tmp.equals("..")) { if (res.size() > 0) { res.remove(res.size() - 1); } } else if (!tmp.equals("") && !tmp.equals(".")) { res.add(tmp); } } StringBuilder ans = new StringBuilder("/"); for (String str : res) { ans.append(str); ans.append("/"); } String result = new String(ans); if (res.size() > 0) { result = result.substring(0, result.length() - 1); } return result; } }
214. Shortest Palindrome
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation. For example: Given "aacecaaa", return "aaacecaaa". Given "abcd", return "dcbabcd".
思路：如前，回文有两种情况。1）以一个字母为中轴；2）以一对字母为中轴。注意这两种情况并不是互斥的，因为存在（aaaaa这种情况，两边都符合了）。所以，优先检查以一对字母为中轴的。因为如果是"aaaaa"的时候，一对的先检测就是走不到头。这得益于，length - 1/ 2，如果是奇数的话，刚好指到中间的那个数。如果是偶数的话，刚好指到一对中轴数左边的数。接下来就会直接，检测成一个字母为中轴。即可直接返回。无论哪种情况，在这道题目上，都是从中轴出发往两边走。一旦遇到不是相等的，就停下来。或者其中一边走到底了停下来。如果左边的指针不是停在起点，那么就不能往前加字符串构成回文。否则，可以返回“”，不能构成回文。
public class Solution { public String shortestPalindrome(String s) { if (s == null || s.length() < 2) { return s; } int mid = (s.length() - 1) / 2; char[] array = s.toCharArray(); String res = ""; for (int index = mid; index >= 0; index--) { if (array[index] == array[index + 1]) { if (!(res = helper(array, index, index + 1)).equals("")) { return res; } } // 排除"aaaaa" if (!(res = helper(array, index, index)).equals("")) { return res; } } return res; } private String helper(char[] array, int l, int r) { int i = 1; for (; l - i >= 0 && r + i < array.length; i++) { if (array[l - i] != array[r + i]) { break; } } if (l - i >= 0) { return ""; } String tmpStr = new String(array); StringBuilder tmp = new StringBuilder(tmpStr.substring(r + i)); tmp.reverse(); return (new String(tmp) + tmpStr); } }
String Comparison Compare two strings A and B, determine whether A contains all of the characters in B. The characters in string A and B are all Upper Case letters.
public class Solution { /** * @param A : A string includes Upper Case letters * @param B : A string includes Upper Case letter * @return : if string A contains all of the characters in B return true else return false */ //注意理解题目意思，如果A不能包含所有B的字符的话，A的字典中某个字符的出现的次数，不够抵扣B的出现次数。这时候 //就应该直接返回false。其余情况就返回true。不需要抵扣至0，大于0也算包含。 public boolean compareStrings(String A, String B) { if (B.equals("")) { return true; } if (A.equals("")) { return false; } // write your code here int[] dict = new int[26]; char[] strArray = A.toCharArray(); for (char tmp : strArray) { dict[tmp - 'A'] += 1; } char[] targetArray = B.toCharArray(); for (char tmp : targetArray) { dict[tmp - 'A'] -= 1; if (dict[tmp - 'A'] < 0) { return false; } } return true; } } String Compress（伪压缩）
Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the compressed string would not become smaller than the original string, your method should return the original string. You can assum the string has only uppercase and lowercase letters(a-z)
思路：for 循环的每一次都需要第一时间count++，count初始化为0。接着，count置零的条件是i + 1为长度，或者charAt(i) != charAt(i + 1)。置零之前，需要在StringBuilder当中加上这个字母和出现次数。最后比较长度，如果长度小的话，输出压缩后的字符串。
public static String compressString(String str){ StringBuilder compressed = new StringBuilder(str.length()); int count = 0; for (int i = 0; i < str.length(); i++){ count++; if (i+1 == str.length() || str.charAt(i) != str.charAt(i+1)){ compressed.append(str.charAt(i)); compressed.append(count); count = 0; } } if (compressed.toString().length() >= str.length()){ return str; } return compressed.toString(); }
