198. House Robber I/II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

思路:
复杂度: Time O(n), Space O(n)

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] money = new int[nums.length + 1];
        money[0] = 0; // 第0次抢了0
        money[1] = nums[0]; // 第一次抢的nums[0]
        for (int i = 2; i < nums.length + 1; i++) {
            money[i] = Math.max(money[i - 1], money[i - 2] + nums[i - 1]);
        }
        return money[nums.length];
    }
}

房子成环。
思路: 抢第一个就不能抢最后一个,不抢第一个抢不抢最后一个随意
两种情况:
1.抢第一间(第二间必须不抢,第三间随意),不抢最后一间(倒数第二间随意)
2.不抢第一间(第二间随意),最后一间抢不抢随意(倒数第二间也随意)

public class Solution {
    // 1 2 4 6 4
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int n = nums.length;
        int[] robFirst = new int[n+1];
        int[] notRobFirst = new int[n+1];
        // init 
        robFirst[1] = nums[0];
        robFirst[2] = robFirst[1];
        notRobFirst[1] = 0;
        notRobFirst[2] = nums[1];

        for (int i = 3; i <= n - 1; i++) { // 第三次抢到n-1次
            robFirst[i] = Math.max(nums[i - 1] + robFirst[i - 2], robFirst[i - 1]);
        }
        for (int i = 3; i <= n; i++) { // 第三次抢到第n次
            notRobFirst[i] = Math.max(nums[i - 1] + notRobFirst[i - 2], notRobFirst[i-1]);
        }

        return Math.max(robFirst[n - 1], notRobFirst[n]);

    }
}

212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = [“oath”,”pea”,”eat”,”rain”] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return [“eat”,”oath”].

思路: 如果用BFS来做的话,

复杂度: time 是MN26^L, space: 26^L, 用Trie来做, 先建立Trie树,把words添加到trie中,然后用BFS 去遍历board,找满足的点。 找的时候需要剪枝。

public class Solution {
    public int[] xDir = new int[]{-1, 0, 1, 0};
    public int[] yDir = new int[]{0, 1, 0, -1};
    public class TrieNode {
        HashMap<Character, TrieNode> children;
        boolean hasWord;
        public TrieNode() {
            this.children = new HashMap<Character, TrieNode>();
            this.hasWord = false;
        }
    }

    public class Trie {
        TrieNode root;
        public Trie() {
            root = new TrieNode();
        }
        public void insert(String word) {
            if (word == null || word.length() == 0) return;
            TrieNode current = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!current.children.containsKey(c)) {
                    current.children.put(c, new TrieNode());
                }
                current = current.children.get(c);
            }
            current.hasWord = true;
        }

        public boolean search(String word) {
            if (word == null || word.length() == 0) return false;
            TrieNode current = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!current.children.containsKey(c)) {
                    return false;
                }
                current = current.children.get(c);
            }
            return current.hasWord;
        }
    }


    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        if (board == null || board.length == 0 || board[0] == null || 
            board[0].length == 0 || words.length == 0 || words == null)
            return res;
        // build Trie tree
        Trie trie = new Trie();
        for (String word: words) {
            trie.insert(word);
        }
        StringBuilder sb = new StringBuilder();
        // search words in board
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                search(board, trie.root, i, j, res, sb);
            }
        }  
        return res;
    }

    public void search(char[][] board, TrieNode root, int x, int y, List<String> res, StringBuilder sb) {
        if (!isValid(board, x, y)) return;
        char c = board[x][y];
        TrieNode current = root.children.get(c);
        // check edge case
        if (c == '#' || current == null) return;
        sb.append(c);
        if (root.hasWord) { // check has a word
            res.add(sb.toString());
            root.hasWord = false;
        }

        board[x][y] = '#'; // pruning
        for (int k = 0; k < 4; k++) { // explore 4 directions
            int newX = x + xDir[k];
            int newY = y + yDir[k];
            search(board, current, newX, newY, res, sb);
        }
        sb.setLength(sb.length() - 1);
        board[x][y] = c;
    } 

    public boolean isValid(char[][] board, int x, int y) {
        if (x < 0 || x >= board.length || y < 0 || y>= board[0].length) return false;
        return true;
    }
}

127. Word LadderI/II

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

Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,

Given:
beginWord = “hit”
endWord = “cog”
wordList = [“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来解这道题目。 用一个hashmap来记录每个单词跟对应的距离. 用一个queue用来做bfs遍历。
BFS遍历过程: 1. 对queue进行poll操作拿到currentWord 2. 遍历currentWord的每个字符位置i, 同时对currentWord的每个位置上的字符进行’a’->’z’的替换,得到nextWord. 3. 先用endWord跟nextWord比较,如果相同,则找到,返回currentWord的长度+1. 如果不是endWord,如果满足wordList包含nextWord,同时hashMap中不存在这个nextWord,那么就将对应的nextWord存入hashMap,并放入queue。

复杂度: time O(n), space O(n)

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if (beginWord == null || beginWord.length() == 0 || 
            endWord == null || endWord.length() == 0 || wordList.size() == 0) return 0;
        HashMap<String, Integer> dictMap = new HashMap<>();
        ArrayDeque<String> queue = new ArrayDeque<>();
        dictMap.put(beginWord, 1);
        queue.offer(beginWord);
        while(!queue.isEmpty()) {
            String currentWord = queue.poll();
            for (int i = 0; i < currentWord.length(); i++) {
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    StringBuilder sb = new StringBuilder(currentWord);
                    sb.setCharAt(i, ch);
                    String nextWord = sb.toString();
                    if (endWord.equals(nextWord)) {
                        return dictMap.get(currentWord) + 1;
                    }
                    if (wordList.contains(nextWord) && !dictMap.containsKey(nextWord)) {
                        dictMap.put(nextWord, dictMap.get(currentWord) + 1);
                        queue.offer(nextWord);
                    }
                }
            }
        }
        return 0;
    }
}

438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: “cbaebabacd” p: “abc”

Output:
[0, 6]

Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Example 2:

Input:
s: “abab” p: “ab”

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

思路: 这个题目是求给定的pattern的anagram,在给定的字符串中出现的位置; 需要借助两个数组, 一个是给定的pattern数组,用来存pattern中各个字符的出现次数。 另一个长度等同于pattern的滑动窗口,当前window下的各个字符的出现次数。当window遍历给定的字符s的时候,做一下几件事情: 1. window中前一个坐标对应的字符的次数-1; window中新加进来的字符的次数+1. 然后比较当前window下的anagram跟pattern 是否相同。

复杂度: 比较anagram O(1), 遍历O(n).

public class Solution {
    public List&lt;Integer&gt; findAnagrams(String s, String p) {
        List&lt;Integer&gt; res = new ArrayList&lt;&gt;();
        if (s == null || s.length() == 0 || p == null || p.length() == 0) return res;
        if (s.length() &lt; p.length()) return res;
        int[] pattern = new int[26];
        int[] window = new int[26];
        int pLen = p.length();

        for (int i = 0; i &lt; pLen; i++) {
            int pIdx = p.charAt(i) - 'a';
            int sIdx = s.charAt(i) - 'a';
            pattern[pIdx]++;
            window[sIdx]++;
        }
        if (isAnagram(window, pattern)) res.add(0);
        for (int i = pLen; i &lt; s.length(); i++) {
            int preIdx = i - pLen;
            window[s.charAt(preIdx) - 'a']--;
            window[s.charAt(i) - 'a']++;
            if (isAnagram(window, pattern)) res.add(i - pLen + 1);
        }
        return res;
    }
    public boolean isAnagram(int[] window, int[] pattern) {
        for (int i = 0; i &lt; pattern.length; i++) {
            if(window[i] != pattern[i]) return false;
        }
        return true;
    }
}

20. Valid Parentheses

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来做.
1. 遍历给定的字符串,针对每个字符char, 当char等于'(‘,”{“,'[‘的时候,把char压入stack.
2. 当char等于’)’,’}’,’]’的时候,把stack栈顶元素pop出来,跟char比较看是否是一对。这里要注意几个情况的判断: 1. stack.isEmpty(), 为空的话,返回false. 2. sc == ‘)’ && stack.pop() != ‘(‘, 返回false.同理其他的几个括号.
3.最后还要判断下最后stack是否为空. 不为空,返回false。

public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) return true;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            Character sc = s.charAt(i);
            if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
                stack.push(sc);
            }
            if (s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) == ']') {
                if (stack.isEmpty()) return false;
                if (sc == ')' && stack.pop() != '(') return false;
                if (sc == '}' && stack.pop() != '{') return false;
                if (sc == ']' && stack.pop() != '[') return false;
            }
        }
        return stack.isEmpty();

    }
}

139. Word Break

Given a string s and a dictionary of words dict, 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”.

思路:如果给定单词可以被分解,那么在字典中都可以找到对应的每一块, 我们需要找到这样的分割点。这里有一个条件那就是这个单词的最后一个分割点到单词末尾组成的substring肯定会出现在字典中,从这个分割点开始往前也是可以分解在字典中找到对应的单词。 我们可以用DP的思想来做这个题目, 从后往前来验证。 外层循环可以从后往前来挨个遍历单词每个字符,内层循环来找这样的分割点到单词末尾之间组成的所有substring是否有存在在字典当中。我们用一个boolean 数组来表示,某个点i到单词末尾组成的所有的可能的substring的集合是否有在Dict中出现过。依次从后往前找,直到最后返回数组第一个值即可。

复杂度: Time: O(n^2), Space: O(n)

public class Solution {
    public boolean wordBreak(String s, Set&lt;String&gt; wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        Arrays.fill(dp, false);
        dp[s.length()] = true;
        for (int i = s.length() - 1; i &gt;= 0; i--) {
            for(int j = i; j &lt; s.length(); j++) {
                String sub = s.substring(i, j + 1);
                if (wordDict.contains(sub) &amp;&amp; dp[j + 1]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
}

239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Max
————— —–
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?
思考: 用maxHeap来做,每个window内都用maxheap来取得最大值。
复杂度: Time(nlogk) Space: O(k)

public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int n = nums.length;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        int res[] = new int[n - k + 1];
        for (int i = 0; i < n; i++) {
            // 窗口最左边数从pq中取出
            if (i >= k) pq.remove(nums[i - k]);
            // 把新加的数放到pq
            pq.offer(nums[i]);
            // 放到结果array
            if (i + 1 >= k) res[i - k + 1] = pq.peek();

        }
        return res;
    }

复杂度:Time O(n),
思考: 不会做,参考的几个blog解答。 发现有几个总结不错的解法,受益良多。
大致上这个题目是给定一个数组num跟长度为k的window, 求window从左往右滑动过程中,在滑动窗口所见的范围k内,出现的最大值的集合。
结果集合总共有nums.length – k + 1个元素, 所以我们的数组下标对应的也就是i-k+1;
我们用一个双向队列queue在O(n)时间内解决这个问题,保持窗口内的最大值在窗口边界(队列头),实现这个方法就是不停的删除掉窗口中比新进来元素小的元素。 数组中存的是元素的坐标,而不是每个元素对应的值, 每当有新的元素进入window时候,从队队尾开始,删掉比新元素小的元素,然后将新加进来的元素放到队列末尾。这样就保证了队首元素始终是窗口(队列)最大元素.

我们对这个数组进行遍历大概有以下几个步骤:
1. 对于新加进来的元素i,我们要判断是否k-i的值等于queue中的头部的坐标, 如果等于则需要将queue中头部元素扔掉。
2. 如果queue中队尾元素对应的值小于新加的元素i对应的值,那么持续扔掉队尾元素,保证queue中元素对应的值是降序的。
3. 把i加入queue中。
4. 判断如果i+i >=k,表示至少比较了k次,则需要记录一次最大值放到最终结果里面,我们直接取queue中头部元素对应的值。

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length < k || k <= 0 || nums == null) return nums;
        Deque<Integer> queue = ArrayDeque<Integer>();
        int[] res = nums.length - k + 1;
        for (int i = 0; i < nums.length; i++) {
            // window 是往右滑动的,每当往右滑动一个数,最左边的数要拿出来,我们要检查queue中的头部的下标是否等于i-k. 
            if (!queue.isEmpty() && queue.peek() == i - k) queue.poll();
            // queue中队尾所有比新数小的都扔掉,保证queue中是降序的
            while(!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) queue.pollLast();
            queue.offer(i);
            // 检查如果是比较了至少k次,那就把i-l+1这个点的坐标对应结果放到最终结果里面。
            if (i + 1 >= k) res[i-k+1] = queue.peek();
        }
        return res;
    }
}

Reference: [Leetcode] Sliding Window Maximum 滑动窗口最大值
239. Sliding Window Maximum
https://segmentfault.com/a/1190000003834593