aquawj

class Solution {
    //1. write
    //操作次数: nums.length
    //适用：很多非零数。此法为写入次数最优！
    public void moveZeroes(int[] nums) {
        if(nums == null || nums.length == 0){
            return;
        }
        int index = 0;
        for(int i = 0; i < nums.length; i++){

aquawj

//方法1．sort + two pointer
//O(n^2) time, O(1) space if not consider sorting's stack usage
    public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
            if(i==0||(i>0&&nums[i]!=nums[i-1])){
                int lo=i+1,hi=nums.length-1,sum=0-nums[i];

aquawj

// 1. DFS
public class Solution {
    String[] mapping = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; //比直接用map省空间，表示也简单
    //注意将mapping设为全局变量，两个函数都要用
    public List<String> letterCombinations(String digits) {
       List<String> res = new ArrayList<>();
        if(digits == null || digits.length() == 0){
            return res;
        }
        StringBuilder sb = new StringBuilder();

aquawj

//string做的时间复杂度︽n+(n-1)+...+1 = O(n^2)
//O(n)
public class Solution {
    public String addBinary(String a, String b) {
        if (a == null || b == null) { //不用检查length == 0，已包含在后续程序中
            return "";
        }
        StringBuilder res = new StringBuilder(); //也可以不用sb, String res = "";
        int i = a.length() - 1;
        int j = b.length() - 1;

aquawj

//正则表达式regex + String操作
public class Solution {
   public static boolean isPalindrome(String s){
		if(s.length()<2) return true;
		String str=s.toLowerCase().replaceAll("[^a-z0-9]","");// 关键句：全小写，replace所有不是0-9和a-z的
		for(int i=0,j=str.length()-1; i<=j; i++,j--){
			if(str.charAt(i)!=str.charAt(j))  return false;
		  }
		return true;
   }

aquawj

/*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".*/

//方法1：使用2个Hash
//targetHash来表示目标值字典；sourceHash表示当前window中的字符统计
//（1）九章做法——使用isValid()函数，循环i（左指针）
    public String minWindow(String s, String t) {

aquawj

/*Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, 
determine if s can be segmented into a space-separated sequence of one or more dictionary words. 
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.*/

aquawj

//你是个产品经理，发现product的最近版本fail了。目前已经开发到第n版（1,2，……，n）。找出在最早是哪个version开始坏的（其后的所有version都是坏的）
//给好API来判断是不是bad version: boolean isBadVersion(int n)
//二分 O(logn)
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if(n < 1) return n;
        int start = 1, end = n;
        while(start + 1 < end){
            int mid = start + (end - start)/2 ;
            if(!isBadVersion(mid)){

aquawj

//正常是4种情况：1.先判断mid在左边还是右边（与A[start]比较）
// 2. 下一维度又分两种情况：单一趋势（极左or极右） vs 不定趋势
//（写的不好就变成6种情况了）
//二分法复杂度都是 O(logn)

public int search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return -1;
        }

aquawj

//此题注意要同时操作doublyLinkedList和map，插入删除都需要同时
//通过key来联系map和list node
public class LRUCache {
    private class Node{ //双向链表节点：4个变量
        Node prev;
        Node next;
        int key;
        int value;

        public Node(int key, int value) {