一。字符串循环移位问题；
给定一个字符串S[0...N-1]，要求把S的前k个字符移动到S的尾部，如把字符串“abcdef”向左移动2位得到“cdefab”。
/** * 该算法实现将字符串循环左移k位 * @param s * @param k * @return */ public static String leftShifting(String s, int k) { char[] ch = s.toCharArray(); k %= s.length(); leftShiftingHelper(ch, 0, k-1); leftShiftingHelper(ch, k, ch.length-1); leftShiftingHelper(ch, 0, ch.length-1); return new String(ch, 0, ch.length); } /** * 将字符数组的m-n位逆置 * @param ch * @param m * @param n */ private static char[] leftShiftingHelper(char[] ch, int m, int n) { int i = m, j = n; while(i < j) { char c = ch[i]; ch[i++] = ch[j]; ch[j--] = c; } return ch; }
二。压缩空格问题。将给定字符串中所有的空格去掉；
给定某字符串S，该字符串中有若干空格，删除这些空格，并返回修改后的字符串，要求时间复杂度为：O(N),空间复杂度为O(1).
/** * *算法描述： * 删除给定字符串中所有的空格 * @param s * @return */ public static String deleteSpaceSpaces(String s) { if(s == null || s.length() == 0) return s; int i = 0, j = 0; char[] ch = s.toCharArray(); while(j < ch.length && i < ch.length) { if(ch[j] != ‘ ‘) { if( i != j) { ch[i] = ch[j]; } i++; } j++; } return new String(ch, 0, i); }
三。求一个数组中最大的2个数。（TopN问题）
给定一个数组，求该数组中最大的两个数。可以假设数组的长度大于2. O(N) and O(1).
/** * 该算法寻找一个数组中前2大的数，假设数组长度大于2 * @param nums * @return */ public static int[] topTwo(int[] nums) { int[] res = new int[2]; res[0] = nums[0]; res[1] = nums[0]; for(int i=0; i<nums.length; i++) { if(nums[i] > res[0]) { res[1] = res[0]; res[0] = nums[i]; } else if(nums[i] > res[1]) res[1] = nums[i]; } return res; }
四。Huffman编码问题（字符串的最优无损压缩）
import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Map.Entry; class Huffman { Huffman parent; Huffman left; Huffman right; int weight; } public class HuffmanCoding { public static ArrayList<String> Huff(String s) { ArrayList<String> list = new ArrayList<String>(); HashMap<Character, Integer> map = computWordFrequency(s); Huffman[] huffTree = new Huffman[2 * map.size() - 1]; //用数组模拟霍夫曼树 for(int i=0; i<huffTree.length; i++) huffTree[i] = new Huffman(); Iterator<Entry<Character, Integer>> it = map.entrySet().iterator(); int i=0; while(it.hasNext()) { Map.Entry entry = (Entry) it.next(); huffTree[i].weight = (int) entry.getValue(); System.out.println(i + " " + huffTree[i].weight); i++; } //建树 int len = map.size(); for(int j=map.size(); j<huffTree.length; j++) { int[] mins = topTwoMin(huffTree, 0, len); System.out.println(Arrays.toString(mins)); huffTree[j].weight = huffTree[mins[0]].weight + huffTree[mins[1]].weight; huffTree[j].left = huffTree[mins[0]]; huffTree[j].right = huffTree[mins[1]]; huffTree[mins[0]].parent = huffTree[j]; huffTree[mins[1]].parent = huffTree[j]; len++; } //编码 for(int j=0; j<map.size(); j++) { Huffman temp = huffTree[j]; StringBuffer sb = new StringBuffer(); while(temp.parent != null) { if(temp.parent.left == temp) sb.append("0"); else sb.append("1"); temp = temp.parent; } list.add(sb.toString()); } return list; } /** * 该算法寻找一个数组中最小的2数，假设数组长度大于2 * @param nums * @return */ public static int[] topTwoMin(Huffman[] huffTree, int start, int end) { int[] res = new int[2]; res[0] = Integer.MAX_VALUE; res[1] = Integer.MAX_VALUE; int[] index = new int[2]; for(int i=start; i<end; i++) { if(huffTree[i].parent == null && huffTree[i].weight < res[0]) { res[1] = res[0]; res[0] = huffTree[i].weight; index[1] = index[0]; index[0] = i; } else if(huffTree[i].parent == null && huffTree[i].weight < res[1]) { res[1] = huffTree[i].weight; index[1] = i; } } return index; } /** * 该函数返回每个字符出现的词频数 * @param s * @return */ public static HashMap<Character, Integer> computWordFrequency(String s) { HashMap<Character, Integer> map = new HashMap<Character, Integer>(); char[] ch = s.toCharArray(); for(int i=0; i<ch.length; i++) { if(!map.containsKey(ch[i])) map.put(ch[i], 1); else map.put(ch[i], map.get(ch[i]) + 1); } return map; } public static void main(String[] args) { // TODO Auto-generated method stub String s = "aadabcbacdaebdebcdbebdacaedaacaebcaaaaa"; System.out.println(Huff(s)); } }
五。字符串的全排列枚举
六。KMP算法
原文：http://www.cnblogs.com/little-YTMM/p/5421079.html
