Count and Say leetcode

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

 n = 1，输出一个1。

 n = 2，看n=1那一行，1个1，输出11。

 n = 3，看n=2那一行，2个1，输出：21。

 n = 4，看n=3那一行，一个2一个1，输出：1211。

以此类推。(注意这里n是从1开始的）
int i--> string : str + ""+i
char c -- > string str + "" + c

public class Solution {
    /**
     * @param n the nth
     * @return the nth sequence
     */
    public String countAndSay(int n) {
        if (n < 0) {
            return "";
        }
        String cur = "1";
        int count = 1;
        for (int j = 1; j < n; j++) {//因为第0位是1 所以从第一位开始
            StringBuilder res = new StringBuilder();
            for (int i = 0; i < cur.length(); i++ ) {
                if (i < cur.length() - 1 && cur.charAt(i) == cur.charAt(i + 1)) {
                    count++;
                } else {
                    res.append(count + "" + cur.charAt(i));
                    count = 1;
                }
                
            }
            cur =  res.toString();
        }
        return cur;
    }
}

Valid Parentheses leetcode

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

用stack实现, 左括号都push到stack中 注意返回时候是要确保stack为空才能true

时间O(n)

 
public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(' ||s.charAt(i) == '[' || s.charAt(i) == '{') {
                stack.push(s.charAt(i));
            } else if (s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}') {
                if (stack.size() == 0) {
                    return false;
                }
                char c = stack.pop();
                if (s.charAt(i) == ')') {
                    if (c != '(') {
                        return false;
                    }
                } else if (s.charAt(i) == ']') {
                    if (c != '[') {
                        return false;
                    }
                } else {
                    if (c != '{') {
                        return false;
                    }
                }
            }
        }
        return stack.size() == 0; //防止有stack没清空
    }
}
//
public class Solution {
    public boolean isValid(String s) {
        HashMap<Character, Character> map = new HashMap<Character, Character>();
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                stack.push(s.charAt(i));
            } else {
                if (stack.isEmpty() || map.get(stack.pop()) != s.charAt(i)) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

Longest Common Prefix leetcode

Write a function to find the longest common prefix string amongst an array of strings.
暴力解法, 先找到所有字符里面最小长度(最长的前缀肯定小于等于这个长度).之后循环, 每个以第零个为参照逐位扫描, 如果不相同则返回当前记录的前缀

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0 || strs == null) {
            return "";
        }
        int min = Integer.MAX_VALUE;
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < strs.length; i++) {
            min = Math.min(min, strs[i].length());
        }
        for (int i = 0; i < min; i++) {
            for (int j = 0; j < strs.length; j++) {
                if (strs[j].charAt(i) != strs[0].charAt(i)) {
                    return res.toString();
                }
            }
            res.append(strs[0].charAt(i));
        }
        return res.toString();
    }
}

Roman to Integer leetcode

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

从后往前扫罗马字符, 由于罗马字符的形成标准 如果之前的字符小于之后的 则对于之前字符用减法 大于等于则加法.

所以把罗马字符和对应数字放入一个hashmap里 方便查找

public class Solution {
    public int romanToInt(String s) {
        if (s.length() == 0 || s == null) {
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('M', 1000);
        map.put('D', 500);
        map.put('C', 100);
        map.put('L', 50);
        map.put('X', 10);
        map.put('V', 5);
        map.put('I', 1);
        int res = map.get(s.charAt(s.length() - 1));
        for (int i = s.length()-2; i >= 0; i--) {
            if (map.get(s.charAt(i + 1)) > map.get(s.charAt(i))) {
                res -= map.get(s.charAt(i));
            } else {
                res += map.get(s.charAt(i));
            }
        }
        return res;
    }
}

Integer to Roman leetcode

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

羅馬數字共有7個，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）。按照下述的規則可以表示任意正整數。需要注意的是罗马数字中没有“0”，與進位制無關。一般認為羅馬數字只用來記數，而不作演算。

• 重複數次：一個羅馬數字重複幾次，就表示這個數的幾倍。

• 右加左減：
  • 在較大的羅馬數字的右邊記上較小的羅馬數字，表示大數字加小數字。
  • 在較大的羅馬數字的左邊記上較小的羅馬數字，表示大數字减小數字。
  • 左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV
  • 但是，左減時不可跨越一個位數。比如，99不可以用IC（）表示，而是用XCIX（）表示。（等同於阿拉伯數字每位數字分別表示。）
  • 左減數字必須為一位，比如8寫成VIII，而非IIX。
  • 右加數字不可連續超過三位，比如14寫成XIV，而非XIIII。（見下方“數碼限制”一項。）

• 加線乘千：
  • 在羅馬數字的上方加上一條橫線或者加上下標的Ⅿ，表示將這個數乘以1000，即是原數的1000倍。
  • 同理，如果上方有兩條橫線，即是原數的1000000（）倍。

• 數碼限制：
• 同一數碼最多只能出現三次，如40不可表示為XXXX，而要表示為XL。
• 例外：由於IV是古羅馬神話主神朱庇特（即IVPITER，古羅馬字母裡沒有J和U）的首字，因此有時用IIII代替IV。

每次寻找小于所给数字的最大值相减, 直到num的值为0

public class Solution {
    public String intToRoman(int num) {
        if (num < 0) {
            return "";
        }
        int[] intset = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] strset = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder res = new StringBuilder();
        for (int i = 0; num != 0; i++) {
            while (num >= intset[i]) {
                num -= intset[i];
                res.append(strset[i]);
            }
        }
        return res.toString();
    }
}

String to Integer (atoi) leetcode

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

这道题要考虑 1. 越界问题. 2. 正负号问题 3. 空格问题(用string.trim()) 4.异常符号出现(符号前面保留 后面全删除)

public class Solution {
    public int myAtoi(String str) {
        if(str == null) {
            return 0;
        }
        str = str.trim();
        if (str.length() == 0) {
            return 0;
        }
        int index = 0;
        int tem = 1;
        long result = 0;//因为result可能大于 int的范围
        if (str.charAt(index) == '-') {
            tem = -1;
            index++;
        } else if (str.charAt(index) == '+') {
            index++;
        }
        for (; index < str.length(); index++) {
            if (str.charAt(index) < '0' || str.charAt(index) > '9') {
                break;
            }
            int mid = str.charAt(index) - '0';
            result = result * 10 + mid;
            if (result > Integer.MAX_VALUE) {
                break;
            }
        }
        if (result * tem >  Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        if (result * tem < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        return (int)result * tem;//因为result为long 但是最后要返回int
    }
}

ZigZag Conversion leetcode

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

题解：

 n=2时，字符串坐标变成zigzag的走法就是：

 0 2 4 6

 1 3 5 7

 n=3时的走法是：

 0     4     8

 1  3 5  7 9

 2     6    10 

 n=4时的走法是：

 0      6        12

 1   5 7    11 13 (j = 1 5 = 1+ 2n-2 - 2*1, j = 5 11 = 5 + 2n-2 - 2*1)

 2 4   8 10    14

 3      9         15 

 可以发现规律，每个zigzag包含2n-2个字符  第一行和最后一行，就是按照2n-2的顺序一点点加的。

对于除了第一行最后一行的行数值为 j+(2n-2)-2i(i是行的index）。
所有字符走一遍 时间O(n)

public class Solution {
    public String convert(String s, int numRows) {
        if (s == null || s.length() == 0) {
            return s;
        }
        if (numRows == 1) {
            return s;
        }
        StringBuilder res = new StringBuilder();
        int size = 2*numRows - 2;
        for (int i = 0; i < numRows; i++) {
            for (int j = i; j < s.length(); j += size ) {
                res.append(s.charAt(j));
                if (i != 0 && i != numRows - 1 && j + size - (i * 2) < s.length()) {
                    res.append(s.charAt(j + size - (i * 2)));
                }
            }
        }
        return res.toString();
    }
}

Longest Palindromic Substring leetcode

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
这道题可以以串心为中心 往字符串两边扫 找到最长的回文串
对于每个子串的中心（可以是一个字符，或者是两个字符的间隙，比如串abc,中心可以是a,b,c,或者是ab的间隙，bc的间隙，例如aba是回文，abba也是回文，这两种情况要分情况考虑）往两边同时进 行扫描，直到不是回文串为止。假设字符串的长度为n,那么中心的个数为2*n-1(字符作为中心有n个，间隙有n-1个）。对于每个中心往两边扫描的复杂 度为O(n),所以时间复杂度为O((2*n-1)*n)=O(n^2),空间复杂度为O(1)。”引自http://codeganker.blogspot.com/2014/02/longest-palindromic-substring-leetcode.html）

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            String tem = helper(s, i, i);
            if (tem.length() > res.length()) {
                res = tem;
            }
            tem = helper(s, i, i + 1);
            if (tem.length() > res.length()) {
                res = tem;
            }
        }
        return res;
    }
    public String helper(String s, int start, int end) {
        while (start>= 0 && end < s.length() ) {
            if (s.charAt(start) == s.charAt(end)) {
                start--;
                end++;
            } else {
                break;
            }
        }
        return s.substring(start + 1, end);//此时start位和end位的不相等
    }
}

Palindrome Number leetcode

Determine whether an integer is a palindrome. Do this without extra space.
首先确定 负数不是回文串
然后判断数字的第一项和最后一项是否相同 不同就返回false. 相同再继续遍历

public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int div = 1;
        while (x/10 >= div) {
            div *= 10; 
        }
        while (x != 0) {
            int left = x/div;
            int right = x%10;
            if (left != right) {
                return false;
            }
            x = (x%div) / 10;// x变为去掉left & right 的数字 12321--> 232
            div /= 100;//因为去掉了left和right 缩小100倍 div也要缩小
        }
        return true;
    }
}

Valid Palindrome leetcode

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

从两边出发往中间走看是否匹配, 遇到不是字母或者数字的就跳过;

character 变为小写的格式为 c1 = (char) (c1 - 'A' + 'a'); 或者也可以直接 Character.toLowerCase(char)
时间复杂度是O(n)，空间上是O(1)

public class Solution {
    public boolean isPalindrome(String s) {
        if (s.length() == 0|| s == null) {
            return true;
        }
        int start = 0;
        int end = s.length() - 1;
        while (start <= end) {
            if (!isValid(s.charAt(start))) {//这里用了if循环 因为如果是while left会溢出
                start++;
                continue;
            }
            if (!isValid(s.charAt(end))) {
                end--;
                continue;
            }
            if (isSame(s.charAt(start), s.charAt(end))) {
                start++;
                end--;
            } else {
                return false;
            }
        }
        return true;
    }
    public boolean isValid(char k) {
        if ((k >= 'a' && k <= 'z') || (k >= 'A' && k <= 'Z') || (k >= '0' && k <= '9')) {
            return true;
        }
        return false;
    }
    public boolean isSame(char c1, char c2) {
        if (c1 >= 'A' && c1 <= 'Z') {
            c1 = (char) (c1 - 'A' + 'a');
        }
        if (c2 >= 'A' && c2 <= 'Z') {
            c2 = (char) (c2 - 'A' + 'a');
        }
        return c1 == c2;
    }
}

Minimum Window Substring leetcode

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.

这道题是字符串处理的题目，和Substring with Concatenation of All Words思路非常类似，同样是建立一个字典，然后维护一个窗口。区别是在这道题目中，因为可以跳过没在字典里面的字符（也就是这个串不需要包含且仅仅包含字典里面的字符，有一些不在字典的仍然可以满足要求），所以遇到没在字典里面的字符可以继续移动窗口右端，而移动窗口左端的条件是当找到满足条件的串之后，一直移动窗口左端直到有字典里的字符不再在窗口里。在实现中就是维护一个HashMap，一开始key包含字典中所有字符，value就是该字符的数量，然后遇到字典中字符时就将对应字符的数量减一。算法的时间复杂度是O(n),其中n是字符串的长度，因为每个字符再维护窗口的过程中不会被访问多于两次。空间复杂度则是O(字典的大小)，也就是代码中T的长度。

public class Solution {
    public String minWindow(String s, String t) {
        int m = s.length();
        int n = t.length();
        if (m == 0 || n == 0 || s == null || t == null) {
            return "";
        }
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < n; i++) {
            if (!map.containsKey(t.charAt(i))) {
                map.put(t.charAt(i), 1);
            } else {
                map.put(t.charAt(i), map.get(t.charAt(i)) + 1);
            }
        }
        int minL = m+1;
        int count = 0;
        int minstart = 0;
        int left = 0;
        for (int i = 0; i < m; i++) {
           if (map.containsKey(s.charAt(i))) {
               map.put(s.charAt(i), map.get(s.charAt(i)) - 1);
               if (map.get(s.charAt(i)) >= 0) {
                   count++;
               }
               while (count == n) {
                   if (i - left + 1 < minL) {
                       minL = i - left + 1;
                       minstart = left;
                   }
                   if (map.containsKey(s.charAt(left))) {
                       map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
                       if (map.get(s.charAt(left)) > 0) {
                           count--;
                       }
                   }
                   left++;
               }
           } 
        }
        if (minL > m) {
            return "";
        }
        return s.substring(minstart, minstart + minL);
    }
}

Substring with Concatenation of All Words (hard) leetcode

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in wordsexactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].

题意：给定一个字符串S和一个字符串数组L，L中的字符串长度都相等，找出S中所有的子串恰好包含L中所有字符各一次，返回子串的起始位置。

用一个hashmap把words里面所有单词放入, 出现次数为单词的value 作为字典

再用另一个hashmap 记录当前单词

因为每个单词长度一样，外层循序只许循环wordLen次，每次指针挪一次，每一次循环遍历整个字符串。

内层循环每次遍历一个单词，把整个S字符串遍历检查。

需要在每次大循环维护一个count，看是不是达到了给的字典字符串数量，同时维护一个index，是每个符合条件的字符串的起始index，需要存到返回结果中。

为了能够检查是不是合格字符串，在这里维护一个curDict的HashMap。



首先检查一个单词是不是在原始字典中出现，没出现的话说明这个单词肯定不符合标准，index指针指向下一个单词的起始点，计数器和curDict都要清零。


如果这个单词在原始字典里出现过，用更新原始字典的方法更新curDict，如果这个单词出现的次数没有超过原始字典里记录的次数，那么count++，如果超过了，就需要挪动指针，并把超过的从curDict删掉。


最后，如果count达到了L的length，说明找到了一个合格的字符串，那么将index存入返回结果res中，再把index挪到下一个单词处，更新curDict即可。

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int m = words.length;
        int n = words[0].length();
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return result;
        }
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for (int i = 0; i < m; i++) {//把words所有单词放入map里
            if (map.containsKey(words[i])) {
                map.put(words[i], map.get(words[i]) + 1);
            } else {
                map.put(words[i], 1);
            }
        }
        for (int i = 0; i < n; i++) {
            int count = 0;
            int left = i;
            HashMap<String, Integer> curmap = new HashMap<String, Integer>();
            for (int j = i; j <= s.length() - n; j += n) {
                String str = s.substring(j, j + n);
                if (!map.containsKey(str)) {
                    left = j + n;
                    curmap.clear();
                    count = 0;
                } else {
                    if (!curmap.containsKey(str)) {
                        curmap.put(str, 1);
                    } else {
                        curmap.put(str, curmap.get(str) + 1); 
                    }
                    if (curmap.get(str) <= map.get(str)) {//如果当前和map中都有这个单词 count++
                        count++;
                    } else {//如果这个单词出现次数>map中出现的次数
                        while (curmap.get(str) > map.get(str)) {
                            String tem = s.substring(left, left + n);

                            curmap.put(tem, curmap.get(tem) - 1);
                            if(curmap.get(tem)<map.get(tem)) {//如果是= 说明tem就是str 对于str并没有在count中+
                                count--;
                            } 
                            
                            left = left + n;
                        }
                    }
                    if (count == m) {
                        result.add(left);
                        String tem = s.substring(left, left + n);
                        curmap.put(tem, curmap.get(tem) - 1);
                        count--;
                        left += n;
                    }
                }
            }
        }
        return result;
    }
}

Longest Substring Without Repeating Characters leetcode

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

基本思路是维护一个窗口，每次关注窗口中的字符串，在每次判断中，左窗口和右窗口选择其一向前移动。同样是维护一个HashSet, 正常情况下移动右窗口，如果没有出现重复则继续移动右窗口，如果发现重复字符，则说明当前窗口中的串已经不满足要求，继续移动有窗口不可能得到更好的结果，此时移动左窗口，直到不再有重复字符为止，中间跳过的这些串中不会有更好的结果，因为他们不是重复就是更短。因为左窗口和右窗口都只向前，所以两个窗口都对每个元素访问不超过一遍，因此时间复杂度为O(2*n)=O(n),是线性算法。空间复杂度为HashSet的size,也是O(n).

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int walker = 0;
        int runner = 0;
        int max = 0;
        HashSet<Character> set = new HashSet<Character>();
        while (runner < s.length()) {
            if (set.contains(s.charAt(runner))) {
                max = Math.max(max, runner - walker);
                while (s.charAt(walker) != s.charAt(runner)) {
                    set.remove(s.charAt(walker));
                    walker++;
                }
                set.remove(s.charAt(walker));
                walker++;
            } else {
                set.add(s.charAt(runner));
                runner++;
            }
        }
        return Math.max(max, runner - walker);
    }
}

String and Array

1. ASCII字符 string.charAt(i) 返回的事int值
String last = "Kennedy";
int key = last.charAt(2);
System.out.println(key);
==>
110 返回ASCII码数值

2. 若果想返回int数值

str1="2345";
int x=str1.charAt(2)-'0';
==> x=4;

3. string.trim() 除去string前后的空格

4. StringBuilder
4.1 append()可以使char和int
4.2 toString()

Longest Consecutive Sequence leetcode

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

最简单的方法是先排序再一次遍历 时间复杂度O(nlogn) + O(n) = O(nlogn)
用hashset存储所有的数 这样查找时间为O(1),
对于数组中每个数我们要找大于和小于他的数 例如当前数组是2 我们就要查找有没有1 和3, 如果有了3了, 那么继续找4.
所以我们对于数组中的每个数都在hashset中找他的上下边界 找到后就在set中删除然后继续查找, 维护一个max 最后返回最长的连续
我们对于数组中每个数都进行一次查找, 查找的时间复杂度是O(1) 所以最后复杂度是O(n)

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                int count = 1;
                set.remove(nums[i]);
                int low = nums[i] - 1;
                int high = nums[i] + 1;
                while (set.contains(low)) {//找下边界
                    set.remove(low);
                    count++;
                    low--;
                }
                while (set.contains(high)) {//找上边界
                    set.remove(high);
                    count++;
                    high++;
                }
                max = Math.max(max, count);
            }
        }
        return max;
    }
}

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

这道题可以用链表来实现 但是复杂度是O(n^2)

题解：

解决这道题的方法是：双向链表+HashMap。

“为了能够快速删除最久没有访问的数据项和插入最新的数据项，我们将双向链表连接Cache中的数据项，并且保证链表维持数据项从最近访问到最旧访问的顺序。 每次数据项被查询到时，都将此数据项移动到链表头部（O(1)的时间复杂度）。这样，在进行过多次查找操作后，最近被使用过的内容就向链表的头移动，而没 有被使用的内容就向链表的后面移动。当需要替换时，链表最后的位置就是最近最少被使用的数据项，我们只需要将最新的数据项放在链表头部，当Cache满 时，淘汰链表最后的位置就是了。 ”

解决了LRU的特性，现在考虑下算法的时间复杂度。为了能减少整个数据结构的时间复杂度，就要减少查找的时间复杂度，所以这里利用HashMap来做，这样时间苏咋读就是O(1)。

 所以对于本题来说：

get(key): 如果cache中不存在要get的值，返回-1；如果cache中存在要找的值，返回其值并将其在原链表中删除，然后将其作为头结点。

set(key,value)：当要set的key值已经存在，就更新其value， 将其在原链表中删除，然后将其作为头结点；当药set的key值不存在，就新建一个node，如果当前len<capacity,就将其加入hashmap中，并将其作为头结点，更新len长度，否则，删除链表最后一个node，再将其放入hashmap并作为头结点，但len不更新。

原则就是：对链表有访问，就要更新链表顺序。 

数据结构

LRU的典型实现是hash map + doubly linked list， 双向链表用于存储数据结点，并且它是按照结点最近被使用的时间来存储的。 如果一个结点被访问了， 我们有理由相信它在接下来的一段时间被访问的概率要大于其它结点。于是， 我们把它放到双向链表的头部。当我们往双向链表里插入一个结点， 我们也有可能很快就会使用到它，同样把它插入到头部。 我们使用这种方式不断地调整着双向链表，链表尾部的结点自然也就是最近一段时间， 最久没有使用到的结点。那么，当我们的Cache满了， 需要替换掉的就是双向链表中最后的那个结点(不是尾结点，头尾结点不存储实际内容)。

如下是双向链表示意图，注意头尾结点不存储实际内容：

头 --> 结 --> 结 --> 结 --> 尾
结     点     点     点     结
点 <-- 1  <-- 2 <-- 3  <-- 点

假如上图Cache已满了，我们要替换的就是结点3。

哈希表的作用是什么呢？如果没有哈希表，我们要访问某个结点，就需要顺序地一个个找， 时间复杂度是O(n)。使用哈希表可以让我们在O(1)的时间找到想要访问的结点， 或者返回未找到。
时间 Get O(1) Set O(1) 空间 O(N)

public class LRUCache {//
    public class ListNode {
        int key;
        int val;
        ListNode prev;
        ListNode next;
        public ListNode(int k, int v) {
            this.key = k;
            this.val = v;
        }
    }
    int size;
    int capacity;
    HashMap<Integer, ListNode> map;
    ListNode head;
    ListNode tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.map = new HashMap<Integer, ListNode>();
        this.head = new ListNode(0, 0);
        this.tail = new ListNode(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        ListNode n = map.get(key);
        if(n != null){
            movehead(n);
            return n.val;
        } else {
            return -1;
        }
    }
    
    public void set(int key, int value) {
        ListNode node = map.get(key);
        if (node == null) {
            node = new ListNode(key, value);
            puthead(node);
            size++;
        } else {
            node.val = value;
            movehead(node);
        }
        if (size > capacity) {
            removelast();
            size--;
        }
        map.put(key, node);
    }
    public void movehead(ListNode n) {
        n.next.prev = n.prev;
        n.prev.next = n.next;
        puthead(n);
    }
    public void puthead(ListNode n) {
        n.next = head.next;
        n.next.prev = n;
        head.next = n;
        n.prev = head;
    }
    public void removelast() {
        ListNode last = tail.prev;
        last.prev.next = tail;
        tail.prev = last.prev;
        map.remove(last.key);
    }
}

Largest Rectangle in Histogram leetcode

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

维护一个栈, 这个栈从低向上的高度是依次递增的，如果遇到当前bar高度比栈顶元素低，那么就出栈直到满足条件，过程中检测前面满足条件的矩阵。

1.当栈空或者当前高度大于栈顶下标所指示的高度时，当前下标入栈。否则，2：当前栈顶出栈，并且用这个下标所指示的高度计算面积。然后大于当前高度的栈顶依次出栈并计算高度.如果栈已经为空，说明到目前为止所有元素（当前下标元素除外）都比出栈元素高度要大（否则栈中肯定还有元素），所以矩阵面积就是高度乘以当前下标i。如果栈不为空，那么就是从当前栈顶元素的下一个到当前下标的元素之前都比出栈元素高度大（因为栈顶元素第一个比当前出栈元素小的）
3. fake一个最后一个直方高度为0 (这样面积也为0)
4. 因为每次入栈计算的面积都是出栈元素的面积 所以最后添加一个高度为0的元素让所有的元素都出栈计算面积

首先，如果栈是空的，那么索引i入栈。那么第一个i=0就进去吧。注意栈内保存的是索引，不是高度。然后i++。

然后继续，当i=1的时候，发现h[i]小于了栈内的元素，于是出栈。（由此可以想到，哦，看来stack里面只存放单调递增的索引）

这时候stack为空，所以面积的计算是h[t] * i.t是刚刚弹出的stack顶元素。也就是蓝色部分的面积。

继续。这时候stack为空了，继续入栈。注意到只要是连续递增的序列，我们都要keep pushing，直到我们遇到了i=4，h[i]=2小于了栈顶的元素。

这时候开始计算矩形面积。首先弹出栈顶元素，t=3。即下图绿色部分。

接下来注意到栈顶的（索引指向的）元素还是大于当前i指向的元素，于是出栈，并继续计算面积，桃红色部分。

最后，栈顶的（索引指向的）元素大于了当前i指向的元素，循环继续，入栈并推动i前进。直到我们再次遇到下降的元素，也就是我们最后人为添加的dummy元素0.

同理，我们计算栈内的面积。由于当前i是最小元素，所以所有的栈内元素都要被弹出并参与面积计算。

注意我们在计算面积的时候已经更新过了maxArea。

总结下，我们可以看到，stack中总是保持递增的元素的索引，然后当遇到较小的元素后，依次出栈并计算栈中bar能围成的面积，直到栈中元素小于当前元素。

public class Solution {
    public int largestRectangleArea(int[] height) {
        Stack<Integer> stack = new Stack<Integer>();
        int[] tem = Arrays.copyOf(height, height.length + 1);
        int max = 0;
        int i = 0;
        while (i < tem.length) {
            if (stack.isEmpty() || tem[i] >= tem[stack.peek()]) {
                stack.push(i);
                i++;
            } else {
                int t = stack.pop();
                if (!stack.isEmpty()) {
                    max = Math.max(max, tem[t] * (i - stack.peek() - 1));
                } else {
                    max = Math.max(max, tem[t] * i);
                }
            }
        }
        return max;
    }
}

public class Solution {
    public int largestRectangleArea(int[] height) {
        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        for (int i = 0; i <= height.length; i++) {
            int h;
            if (i == height.length) {
                h = 0;
            } else {
                h = height[i];
            }
            if (stack.isEmpty() || h >= height[stack.peek()]) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && h < height[stack.peek()]) {
                    int k = stack.pop();
                    if (stack.isEmpty()) {
                        max = Math.max(i * height[k], max);
                    } else {
                        max = Math.max(max, (i - stack.peek() - 1)*height[k]);
                    }
                }
                stack.push(i);
            }
        }
        return max;
    }
}

Implement Queue by Two Stacks

As the title described, you should only use two stacks to implement a queue's actions.

The queue should support push(element), pop() and top() where pop is pop the first(a.k.a front) element in the queue.

Both pop and top methods should return the value of first element.

Example

For push(1), pop(), push(2), push(3), top(), pop(), you should return 1, 2 and 2

Challenge

implement it by two stacks, do not use any other data structure and push, pop and top should be O(1) by AVERAGE

用两个stack来实现queue 第一个stack正向装入数字 然后pop出来 push到第二个stack中

每次判定stack2是否为empty(这样做可以防止后来加入的数字push到stack2中 这样顺序就乱了 所以要等stack2 是空的时候才再次网stack2里面push数字) 如果为empty继续push入stack1 pop出来的数 

public class Solution {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public Solution() {
       stack1 = new Stack<Integer>();
       stack2 = new Stack<Integer>();
    }
    public void push(int element) {
        stack1.push(element);
    }

    public int pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int top() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
}

Min Stack leetcode

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

在维护stack同时维护一个minstack, 记录stack内最小值 当stack push新值的时候 minstack 将新值与它最上面的值比较 哪个小就新push哪个 这样ministack最顶层都是当前stack的最小值

class MinStack {
    private Stack<Integer> stack = new Stack<Integer>();
    private Stack<Integer> ministack = new Stack<Integer>();
    public void push(int x) {
       stack.push(x);
        if (ministack.empty()) {
            ministack.push(x);
        } else if (ministack.peek() < x) {
            ministack.push(ministack.peek());
        } else {
            ministack.push(x);
        } 
    }

    public void pop() {
        ministack.pop();
        stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return ministack.peek();
    }
}

Word Ladder I leetcode

Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

题解：

 这道题是套用BFS同时也利用BFS能寻找最短路径的特性来解决问题。

 把每个单词作为一个node进行BFS。当取得当前字符串时，对他的每一位字符进行从a~z的替换，如果在字典里面，就入队，并将下层count++，并且为了避免环路，需把在字典里检测到的单词从字典里删除。这样对于当前字符串的每一位字符安装a~z替换后，在queue中的单词就作为下一层需要遍历的单词了。

 正因为BFS能够把一层所有可能性都遍历了，所以就保证了一旦找到一个单词equals（end），那么return的路径肯定是最短的。

 reference:http://www.cnblogs.com/springfor/p/3893499.html
时间复杂度 O(string.length() * 26)

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        if (beginWord == null || endWord == null) {
            return 0;
        }
        Queue<String> queue = new LinkedList<String>();
        queue.offer(beginWord);
        int res = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                String str = queue.poll();
                for (int i = 0; i < str.length(); i++) {
                    char[] tem = str.toCharArray();
                    for (char j = 'a'; j <= 'z'; j++) {
                        tem[i] = j;
                        String cur = new String(tem);
                        if (cur.equals(endWord)) {
                            return res + 1;
                        }
                        else if (wordDict.contains(cur)) {
                            queue.offer(cur);
                            wordDict.remove(cur);
                        }
                    }
                }
            }
            res++;
        }
        return 0;
    }
    
}

N-Queens I leetcode

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

条件：任意两个皇后都不能处于同一行、同一列或同一斜线上 

典的DFS递归回溯解法，大体思路就是对每一行，按每一列挨个去试，试到了就保存结果没试到就回溯。
难点大概就是用1个一维数组存皇后所在的坐标值。对于一个棋盘来说，每个点都有横纵坐标，用横纵坐标可以表示一个点。
而这道题巧就巧在，每一行只能有一个皇后，也就是说，对于一行只能有一个纵坐标值，所以用1维数组能提前帮助解决皇后不能在同一行的问题。
那么用一维数组表示的话，方法是：一维数组的下标表示横坐标（哪一行），而数组的值表示纵坐标（哪一列）。

例如：对于一个4皇后问题，声明一个长度为4的数组（因为行数为4）。
     A[] = [1,0,2,3]表达含义是：
     当前4个皇后所在坐标点为：[[0,1],[1,0],[2,2],[3,3]]（被我标蓝的正好是数组的下标，标粉的正好是数组的值）
     相当于：A[0] = 1, A[1] = 0, A[2] = 2, A[3] = 3 

这样以来，皇后所在的坐标值就能用一维数组表示了。
而正是这个一维数组，在回溯找结果的时候不需要进行remove重置操作了，因为回溯的话正好就回到上一行了，就可以再重新找下一个合法列坐标了。

因为是按照每一行去搜索的，当行坐标值等于行数时，说明棋盘上所有行都放好皇后了，这时就把有皇后的位置标为Q，没有的地方标为0。
按照上面讲的那个一维数组，我们就可以遍历整个棋盘，当坐标为（row，columnVal[row]）的时候，就说明这是皇后的位置，标Q就行了。  

reference:http://www.cnblogs.com/springfor/p/3870944.html
代码一共有三个部分 验证摆放 dfs 和输出结果
验证时候要确定queen不在同一行或者对角线 如果在对角线 那么queen的位置差和行数差是相等的

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<List<String>>();
        if (n <= 0) {
            return res;
        }
        int[] column = new int[n];
        helper(res, column, n, 0);
        return res;
    }
    public void helper(List<List<String>> res, int[] column, int n, int pos) {
        if (pos == n) {
            List<String> tem = new ArrayList<String>();
            for (int i = 0; i < n; i++) {
                StringBuilder str = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (column[i] == j) {
                        str.append("Q");
                    } else {
                        str.append(".");
                    }
                }
                tem.add(str.toString());
            }
            
            res.add(tem);
            return;
        } else {
            for (int i = 0; i < n; i++) {
                column[pos] = i;
                if (isValid(column, pos)) {
                    helper(res,column, n, pos + 1);
                }
            }
        }
    }
    public boolean isValid(int[] column, int pos) {
        for (int i = 0; i < pos; i++) {
            if (column[i] == column[pos] || Math.abs(column[i] - column[pos]) == pos - i) {
                return false;
            }
        }
        return true;
    } 
}