题目：最长子串
Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC".
Note: If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
双指针法
复杂度
时间 O(N) 空间 O(1)
思路
用一个哈希表记录目标字符串每个字母的个数，一个哈希表记录窗口中每个字母的个数。先找到第一个有效的窗口，用两个指针标出它的上界和下界。然后每次窗口右界向右移时，将左边尽可能的右缩，右缩的条件是窗口中字母的个数不小于目标字符串中字母的个数。
注意
-
用一个数组来保存每个字符出现的次数，比哈希表容易
-
保存结果子串的起始点初值为-1，方便最后判断是否有正确结果
代码
public class Solution { public String minWindow(String S, String T) { int[] srcHash = new int[255]; // 记录目标字符串每个字母出现次数 for(int i = 0; i < T.length(); i++){ srcHash[T.charAt(i)]++; } int start = 0,i= 0; // 用于记录窗口内每个字母出现次数 int[] destHash = new int[255]; int found = 0; int begin = -1, end = S.length(), minLength = S.length(); for(start = i = 0; i < S.length(); i++){ // 每来一个字符给它的出现次数加1 destHash[S.charAt(i)]++; // 如果加1后这个字符的数量不超过目标串中该字符的数量，则找到了一个匹配字符 if(destHash[S.charAt(i)] <= srcHash[S.charAt(i)]) found++; // 如果找到的匹配字符数等于目标串长度，说明找到了一个符合要求的子串 if(found == T.length()){ // 将开头没用的都跳过，没用是指该字符出现次数超过了目标串中出现的次数，并把它们出现次数都减1 while(start < i && destHash[S.charAt(start)] > srcHash[S.charAt(start)]){ destHash[S.charAt(start)]--; start++; } // 这时候start指向该子串开头的字母，判断该子串长度 if(i - start < minLength){ minLength = i - start; begin = start; end = i; } // 把开头的这个匹配字符跳过，并将匹配字符数减1 destHash[S.charAt(start)]--; found--; // 子串起始位置加1，我们开始看下一个子串了 start++; } } // 如果begin没有修改过，返回空 return begin == -1 ? "" : S.substring(begin,end + 1); } }
最长回文子串
回文字符串，指的是形式如同"abcba"或是"abccba“形式的字符串。
那么如何在一串给定的字符串中寻找其中最长的回文子串呢？
①动态规划
package uestc; public class Main { public static void main(String[] args) { String s = "xccxbdc"; String solu = longestPalindrome1(s); System.out.println(solu); } public static String longestPalindrome(String s) { int len = s.length(); int maxLen = 0; String res = null; boolean[][] dp = new boolean[len][len]; for(int i = len - 1;i >= 0;i--){ for(int j = i;j < len;j++){ dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i+1][j-1] == true); //（1）当前遍历到的子串i~j是否是回文子串取决于i+1~j-1，也就是i~j中间的子串是否是回文并且s[i]是否等于s[j]； //（2）dp[i][j]是为true则意味着i~j是回文子串，则在下面判断后对res进行更新；如果为false，则该子串不是回文子串，开始遍历下一个子串。 if(dp[i][j] == true && (res == null || j - i + 1 > maxLen)){ //如果该子串长度更长，则更新res res = s.substring(i, j+1); maxLen = res.length(); } } } return res; } }
②可以用延伸的思想来寻找，即先找最短的字符串如"a"、"bb"等，在这些字符串基础上进行延伸扩展，若是找到的符合要求的子串长度大于已找到的回文子串的最大长度，则取而代之，同时记录该子串的第一个字符的下标。
通过这种思想将字符串遍历执行即可找到最大回文子串。
public class PalindromicSubstring { private static int start; private static int maxLength; public static String longestPalindrome1(String s) { if(s.length()<2) return s; for(int i=0;i<s.length()-1;i++) { //遍历整个数组，寻找回文子串最中间的字符，如果回文子串是奇数长度，那么最中间有一个字符；否则有两个字符 extendPali(s,i,i); extendPali(s,i,i+1); } return s.substring(start,start+maxLength); } public static void extendPali(String s,int i,int j) { while(i>=0&&j<s.length()&&s.charAt(i)==s.charAt(j)) { i--; //如果满足括号里的条件，则继续向两边扩展 j++; } if(maxLength<j-i-1){ //更新最大长度的值 start=i+1; maxLength=j-i-1; } } }
两个栈实现一个队列
思路:所有元素进stack1，然后全部出stack1并进入stack2.实现队列的先进先出即：若stack2非空，我们需要的恰好再栈顶，出栈;若要给队列添加元素，即先进sack1,要出队时，若stack2不为空就出栈，为空时就把stack1全部进栈到stack2
package uestc; import java.util.Stack; public class StackToQueue { Stack<Integer> stack1=new Stack<Integer>() ; Stack<Integer> stack2=new Stack<Integer>(); public void addToTail(int x)//添加元素到队尾 --进队--- { stack1.push(x); } public int deleteHead()//删除对首 --出队--- 不需是队不为空才能删除呀~~~~ { if( pSize()!=0)//队列不为空 { if(stack2.isEmpty())//若stack2为空，则把stack1全部加入stack2 stack1ToStack2(); return stack2.pop(); } else { System.out.println("队列已经为空，不能执行从队头出队"); return -1; } } public int poll() { if( pSize()!=0)//队列不为空 { if(stack2.isEmpty())//若stack2为空，则把stack1全部加入stack2 stack1ToStack2(); return stack2.pop(); } else { System.out.println("队列已经为空"); return -1; } } public void stack1ToStack2()//把stack1全部放入stack2 { while(!stack1.isEmpty()) { stack2.push(stack1.pop()); } } public int pSize() { return stack1.size()+stack2.size();//两个都为空队列才是空 } public static void main(String[] args) { StackToQueue q=new StackToQueue (); q.addToTail(1); q.addToTail(2); q.addToTail(3); q.addToTail(4); System.out.println(q.deleteHead()); q.addToTail(5); System.out.println(q.deleteHead()); System.out.println(q.deleteHead()); System.out.println(q.deleteHead()); System.out.println(q.deleteHead()); System.out.println(q.poll()); }}
两个队列实现一个栈
思路：所有元素进入q1，因为我们的目的是栈，也就是最先出c,儿队是从队头开始出，所有先把ab出q1并入q2,此时目标c跑到了队头，出q1。此时q1已经为空，下一个要出的是b,把a从q2出队并进q1,此时目标b在q2队头,出队........
即：把非空队列的n-1个压人空对列，剩的第n个出队...即总有一个队列为空。
二叉树的层序遍历算法实现
实现二叉树的层序遍历--从根开始，依次向下，对于每一层从左向右遍历。
层序遍历与先序、中序、后序遍历不同。层序遍历用到了队列，而先、中、后序需要用到栈。
因此，先、中、后序遍历 可以 采用递归方式来实现，而层序遍历则没有递归方式。
算法步骤：
初始时，根结点入队列
然后，while循环判断队列不空时，弹出一个结点，访问它，并把它的所有孩子结点入队列。
public void levelTraverse(BinarySearchTree<T> tree){ levelTraverse(tree.root); } private void levelTraverse(BinaryNode<T> root){ if(root == null) return; Queue<BinaryNode<T>> queue = new LinkedList<>();//层序遍历时保存结点的队列 queue.offer(root);//初始化 while(!queue.isEmpty()){ BinaryNode<T> node = queue.poll(); System.out.print(node.element + " ");//访问节点 if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } }