作者：whisper

链接：http://proprogrammar.com:443/article/387

声明：请尊重原作者的劳动，如需转载请注明出处

---

    忙着考研，但还是三心二意，leetcode题还是照刷不误，下面是目前为止刷的题目。

    已刷400题，开始刷题时很难，到后面就开始顺手起来了，不会的题目就看解答，主要还是因为学了基础的数据结构，掌握了常用算法，刷题过程中用到了一些数据结构（不涉及多线程中使用的数据结构），下面就具体的说说，给后来者一些方便。

    常用的数据结构

    List: ArrayList, LinkedList

    Set: HashSet, TreeSet, LinkedHashSet

    Map: HashMap, TreeMap, LinkedHashMap

    Stack: Stack, Deque(LinkedList, ArrayDeque)(双端队列也可以做为栈使用)

    Queue(Deque): PriorityQueue, ArrayDeque, LinkedList

    Array: 一维, 二维, 三维...

    大致常用的就是上面这些，下面说说每种的特性并给出算法例子

    List

    列表相比数组来说，长度可变，可以看成是对数组的增强，而且列表可以存储任意类型的数据元素，也可以通过指定泛型存储某一特定类型的数据元素，常用到的是ArrayList, LinkedList，ArrayList底层是用数组实现的，所以查询的效率较高，而LinkedList的底层是链表实现的，所以修改的效率较高，这也是它们不同的使用场合，在长度不是事先确定的情况下，可以使用列表。

    ArrayList构造方法：

    ArrayList()

    ArrayList(Collection<? extends E> c)

    ArrayList(int initialCapacity)

    LinkedList构造方法：

    LinkedList()

    LinkedList(Collection<? extends E> c)

    List常用方法：

    boolean add(E e)

    void add(int index, E element)

    boolean addAll(Collection<? extends E> c)

    boolean addAll(int index, Collection<? extends E> c)

    void clear()

    boolean contains(Object o)

    boolean containsAll(Collection<?> c)

    boolean equals(Object o)

    E get(int index)

    int hashCode()

    int indexOf(Object o)

    boolean isEmpty()

    Iterator<E> iterator()

    int lastIndexOf(Object o)

    ListIterator<E> listIterator()

    ListIterator<E> listIterator(int index)

    E remove(int index)

    boolean remove(Object o)

    boolean removeAll(Collection<?> c)

    default void replaceAll(UnaryOperator<E> operator)

    boolean retainAll(Collection<?> c)

    E set(int index, E element)

    int size()

    default void sort(Comparator<? super E> c)

    default Spliterator<E> spliterator()

    List<E> subList(int fromIndex, int toIndex)

    Object[] toArray()

    <T> T[] toArray(T[] a)

    下面给出使用ArrayList和LinkedList例子

    直接使用LinkedList作为列表使用的例子我没找到，下面只给出ArrayList的例子吧。

    830. 较大分组的位置

在一个由小写字母构成的字符串 S 中，包含由一些连续的相同字符所构成的分组。

例如，在字符串 S = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。

我们称所有包含大于或等于三个连续字符的分组为较大分组。找到每一个较大分组的起始和终止位置。

最终结果按照字典顺序输出。

示例 1:

输入: "abbxxxxzzy"
输出: [[3,6]]
解释: "xxxx" 是一个起始于 3 且终止于 6 的较大分组。

示例 2:

输入: "abc"
输出: []
解释: "a","b" 和 "c" 均不是符合要求的较大分组。

示例 3:

输入: "abcdddeeeeaabbbcd"
输出: [[3,5],[6,9],[12,14]]

说明:  1 <= S.length <= 1000

 

    // 想法：直接算连续数量，大于2的记录一下
    public List<List<Integer>> largeGroupPositions(String S) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list;
        int start = 0, cur = 1;

        while(cur < S.length()){
            if(S.charAt(start) == S.charAt(cur)){
                cur++;
            }else{
                if(cur - start >= 3){
                    list = new ArrayList<>();
                    list.add(start);
                    list.add(cur - 1);
                    res.add(list);
                }
                start = cur;
                cur++;
            }
        }

        // 小技巧：一些题目开始需要处理一下，一些题目结尾需要处理一下
        if(cur - start >= 3){
            list = new ArrayList<>();
            list.add(start);
            list.add(cur - 1);
            res.add(list);
        }

        return res;
    }

    这里还用到了列表的列表。因为返回值的元素数量不确定，所以要用列表，具体算法就不展开了，是道简单题，容易理解

    Set

    Set与List最大的不同是Set中的元素不会重复，当向Set中添加已有元素时，本次的添加会失效，所以Set可以用来去重或者判断是否出现重复，Set的实现有TreeSet和HashSet，HashSet是我们正常使用的一种，而TreeSet是有序（这里的有序是排序，即逻辑的顺序是按一定规则排序的）的，LinkedHashSet也是有序的（这里的有序是顺序，即逻辑的顺序是插入的顺序），同时要注意的是Set接口是没有get方法的，所以当我们想获取Set中的元素时，要用迭代的方式进行遍历。

    HashSet构造方法：

    HashSet()

    HashSet(Collection<? extends E> c)

    HashSet(int initialCapacity)

    HashSet(int initialCapacity, float loadFactor)

    TreeSet构造方法：

    TreeSet()

    TreeSet(Collection<? extends E> c)

    TreeSet(Comparator<? super E> comparator)

    TreeSet(SortedSet<E> s)

    LinkedHashSet构造方法

    LinkedHashSet()

    LinkedHashSet(Collection<? extends E> c)

    LinkedHashSet(int initialCapacity)

    LinkedHashSet(int initialCapacity, float loadFactor)

    Set常用方法：

    boolean add(E e)

    boolean addAll(Collection<? extends E> c)

    void clear()

    boolean contains(Object o)

    boolean containsAll(Collection<?> c)

    boolean equals(Object o)

    int hashCode()

    boolean isEmpty()

    Iterator<E> iterator()

    boolean remove(Object o)

    boolean removeAll(Collection<?> c)

    boolean retainAll(Collection<?> c)

    int size()

    default Spliterator<E> spliterator()

     Object[] toArray()

    <T> T[] toArray(T[] a)

    LinkedHashSet我没有用过，下面给出使用HashSet和TreeSet的例子吧

    290. 单词规律

给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = "abba", str = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", str = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false

示例 4:

输入: pattern = "abba", str = "dog dog dog dog"
输出: false

说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。 

 

    // 想法：找到字符与字符串的对应关系，当出现不对应时，返回false
    public boolean wordPattern(String pattern, String str) {
        Map<String, String> map = new HashMap<>();
        Set<String> set = new HashSet<>();
        String[] ps = pattern.split(""), ss = str.split(" ");
        String temp;
        int size;

        if(ps.length != ss.length){
            return false;
        }

        for(int i = 0; i < ps.length; i++){
            if("".equals(ps[i])){
                return false;
            }
            
            temp = map.get(ps[i]);
            // 不同字符对应的字符串应不同
            if(null == temp){
                map.put(ps[i], ss[i]);
                // 利用set判重复
                size = set.size();
                set.add(ss[i]);
                if(size == set.size()){
                    return false;
                }
            }else if(!temp.equals(ss[i])){
                return false;
            }
        }

        return true;
    }

    这里通过比较set添加新元素之前与之后size是否变化（是否添加了重复元素）来确定是否返回，具体算法就不再说了

    821. 字符的最短距离

给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。

示例 1:

输入: S = "loveleetcode", C = 'e'
输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

说明:

1. 字符串 S 的长度范围为 [1, 10000]。
2. C 是一个单字符，且保证是字符串 S 里的字符。
3. S 和 C 中的所有字母均为小写字母。

 

    // 想法：两次遍历，第一次找C，第二次找与C的最近距离
    public int[] shortestToChar(String S, char C) {
        char[] cs = S.toCharArray();
        // 耗时
        Set<Integer> cset = new TreeSet<>();
        int min;
        List<Integer> res = new ArrayList<>();

        for(int i = 0;i < cs.length; i++){
            if(cs[i] == C){
                cset.add(i);
            }
        }

        loop:
        for(int i = 0; i < cs.length; i++){
            min = Integer.MAX_VALUE;
            if(cs[i] == C){
                res.add(0);
                continue;
            }

            for(int j: cset){
                if(min > Math.abs(i - j)){
                    min = Math.abs(i - j);
                }else{
                    res.add(min);
                    continue loop;
                }
            }
            res.add(min);
        }

        // 耗时
        return res.stream().mapToInt(i -> i).toArray();
    }

    这里用到了TreeSet，找到距离C的最小距离，算法很简单，不多说

    Map

    Map即Hash表，以键值对的方式存储数据，主要有三种HashMap，LinkedHashMap，TreeMap，常规是即是HashMap，但遍历的顺序不一定是添加的顺序，LinkedHashMap是有序的，遍历的顺序即插入的顺序，TreeMap的key是按一定规则排序的，LinkedHashMap和TreeMap类似于LinkedHashSet与TreeSet，Map元素是(key-value)键值对，用于表示相互关联的两个数据，如果把value换成复杂结构如List和Set或者对象，那么使用范围就可以进一步扩大。

    HashMap构造方法：

    HashMap()

    HashMap(int initialCapacity)

    HashMap(int initialCapacity, float loadFactor)

    HashMap(Map<? extends K,? extends V> m)

    LinkedHashMap构造方法：

    LinkedHashMap()

    LinkedHashMap(int initialCapacity)

    LinkedHashMap(int initialCapacity, float loadFactor)

    LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

    注：accessOrder为false时，遍历顺序为添加顺序，当accessOrder为true时，每次访问一个元素后会把该元素移动到map的尾部

    LinkedHashMap(Map<? extends K,? extends V> m)

    TreeMap构造方法：

    TreeMap()

    TreeMap(Comparator<? super K> comparator)

    TreeMap(Map<? extends K,? extends V> m)

    TreeMap(SortedMap<K,? extends V> m)

    Map的内部静态接口

    static interface Map.Entry<K,V>

    Map常用方法：

    void clear()

    default V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)

    default V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction)

    default V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)

    boolean containsKey(Object key)

    boolean containsValue(Object value)

    Set<Map.Entry<K,V>> entrySet()

    boolean equals(Object o)

    default void forEach(BiConsumer<? super K,? super V> action)

    V get(Object key)

    default V getOrDefault(Object key, V defaultValue)

    int hashCode()

    boolean isEmpty()

    Set<K> keySet()

    default V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction)

    V put(K key, V value)

    void putAll(Map<? extends K,? extends V> m)

    default V putIfAbsent(K key, V value)

    V remove(Object key)

    default boolean remove(Object key, Object value)

    default V replace(K key, V value)

    default boolean replace(K key, V oldValue, V newValue)

    default void replaceAll(BiFunction<? super K,? super V,? extends V> function)

    int size()

    Collection<V> values()

    java8中map加了好多好用的方法啊^-^

    LinkedHashMap在写算法时还没有用到，下面给出使用HashMap和TreeMap的例子。

    884. 两句话中的不常见单词

给定两个句子 A 和 B 。 （句子是一串由空格分隔的单词。每个单词仅由小写字母组成。）

如果一个单词在其中一个句子中只出现一次，在另一个句子中却没有出现，那么这个单词就是不常见的。

返回所有不常用单词的列表。

您可以按任何顺序返回列表。

示例 1：

输入：A = "this apple is sweet", B = "this apple is sour"
输出：["sweet","sour"]

示例 2：

输入：A = "apple apple", B = "banana"
输出：["banana"]

提示：

1. 0 <= A.length <= 200
2. 0 <= B.length <= 200
3. A 和 B 都只包含空格和小写字母。

import java.util.Map.Entry;

class Solution {
    // 想法：基础题，两个map
    public String[] uncommonFromSentences(String A, String B) {
        Map<String, Integer> mapa = new HashMap<>(), mapb = new HashMap<>();
        List<String> res = new ArrayList<>();

        for(String s: A.split(" ")){
            mapa.put(s, mapa.getOrDefault(s, 0) + 1);
        }

        for(String s: B.split(" ")){
            mapb.put(s, mapb.getOrDefault(s, 0) + 1);
        }

        for(Entry<String, Integer> entry: mapa.entrySet()){
            if(entry.getValue() == 1 && null == mapb.get(entry.getKey())){
                res.add(entry.getKey());
            }
        }

        for(Entry<String, Integer> entry: mapb.entrySet()){
            if(entry.getValue() == 1 && null == mapa.get(entry.getKey())){
                res.add(entry.getKey());
            }
        }

        return res.toArray(new String[0]);
    }
}

     两个map存出现的字符串和出现的次数，算法不多解释了

594. 最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。

示例 1:

输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是：[3,2,2,2,3].

说明: 输入的数组长度最大不超过20,000.

    // 想法：treeMap，找相邻
    public int findLHS(int[] nums) {
        Map<Integer, Integer> treeMap = new TreeMap<>();
        for(int n: nums){
            treeMap.put(n, treeMap.getOrDefault(n, 0) + 1);
        }

        // 找出相邻且出现次数最多的两数
        int pre = Integer.MAX_VALUE, after = Integer.MIN_VALUE, count = 0, acount = 0, max = Integer.MIN_VALUE;
        for(int k: treeMap.keySet()){
            if(pre == Integer.MAX_VALUE){
                pre = k;
                count = treeMap.get(k);
            }else{
                if(k - pre == 1){
                    acount = treeMap.get(k);
                    after = k;
                    count += acount;
                    if(max < count){
                        max = count; 
                    }
                }else{
                    if(k - after == 1){
                        pre = after;
                        count = acount + treeMap.get(k);
                        after = k;
                        acount = treeMap.get(k);
                        if(max < count){
                            max = count;
                        }
                    }else{
                        pre = k;
                        after = Integer.MIN_VALUE;
                        count = treeMap.get(k);
                        acount = 0;
                    }
                }
            }
        }

        return max == Integer.MIN_VALUE ? 0 : max;
    }

    将数组中的元素存TreeMap，因为有序，所以大小相邻的元素在TreeMap中节点的也是相邻的，利用这一特性可以求出所要的结果

    Stack

    栈是一种先进后出的数据结构，可以用来代替递归，常用的场合如数制转换，括号匹配的检验，行编辑程序问题，表达式求值等，在java中可以用Stack和LinkedList, ArrayDeque实现栈的功能，其中Stack是比较老的一个类了，继承了Vector，是线程安全的，一般单线程问题中用LinkedList, ArrayDeque就可以了

    Stack构造及常用方法

    Stack()

    boolean empty()

    E peek()

    E pop()

    E push(E item)

    int search(Object o)

    LinkedList构造及常用方法：

    LinkedList()

    LinkedList(Collection<? extends E> c)

    E peek()

    E pop()

    void push(E e)

    int size()

    boolean isEmpty()

    ArrayDeque构造及常用方法：

    ArrayDeque()

    ArrayDeque(Collection<? extends E> c)

    ArrayDeque(int numElements)

    E peek()

    E pop()

    void push(E e)

    int size()

    boolean isEmpty()

    LinkedList和ArrayDeque做为栈使用的例子

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

    // 想法：数据结构基本题，遇左括号入栈，遇右括号出栈，看是否匹配，字符串结束时栈要为空
    public boolean isValid(String s) {
        if(s.length() == 0){
            return true;
        }
        
        char[] arr = s.toCharArray();
        Deque<Character> stack = new ArrayDeque<>();
        char temp;
        
        for(char c: arr){
            if(c == '}' || c == ']' || c == ')'){
                if(stack.isEmpty()){
                    return false;
                }else{
                    temp = stack.pop();
                    if(temp + 1 != c && temp + 2 != c){
                        return false;
                    }
                }
            }else{
                stack.push(c);
            }
        }
        
        return stack.isEmpty();
    }

    使用ArrayDeque做栈，左括号入栈，遇右括号出栈，看是否匹配，字符串结束时栈要为空

682. 棒球比赛

你现在是棒球比赛记录员。
给定一个字符串列表，每个字符串可以是以下四种类型之一：
1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
2. "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
3. "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
4. "C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。

每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。

示例 1:

输入: ["5","2","C","D","+"]
输出: 30
解释: 
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到2分。总和是：7。
操作1：第2轮的数据无效。总和是：5。
第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
第4轮：你可以得到5 + 10 = 15分。总数是：30。

示例 2:

输入: ["5","-2","4","C","D","9","+","+"]
输出: 27
解释: 
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到-2分。总数是：3。
第3轮：你可以得到4分。总和是：7。
操作1：第3轮的数据无效。总数是：3。
第4轮：你可以得到-4分（第三轮的数据已被删除）。总和是：-1。
第5轮：你可以得到9分。总数是：8。
第6轮：你可以得到-4 + 9 = 5分。总数是13。
第7轮：你可以得到9 + 5 = 14分。总数是27。

注意：

输入列表的大小将介于1和1000之间。
列表中的每个整数都将介于-30000和30000之间。

    // 当前得分最多与前两次有关，所以只要通过前两次就能算出当前，
    // 但由于有C操作的存在，所以所有的得分都要记录，用栈
    public int calPoints(String[] ops) {
        LinkedList<Integer> stack = new LinkedList<>();
        int res = 0;
        
        for(String s: ops){
            if("C".equals(s)){ 
                stack.pop();
            }else if("D".equals(s)){
                stack.push(stack.peek() * 2);
            }else if("+".equals(s)){
                // 小技巧，当把LinkedList当栈用时，栈顶在LinkedList的开头（列表0索引的位置）
                stack.push(stack.peek() + stack.get(1));
            }else{
                stack.push(Integer.parseInt(s));
            } 
        }
        
        while(!stack.isEmpty()){
            res += stack.pop();
        }
        
        return res;
    }

     LinkedList做栈，值得一题的一点是，LinkedList不光是栈，还是列表，所以还可以当列表用，即混用栈和列表的方法以提高效率

    Queue(Deque双端队列)

    队列包括一端进一端出的普通队列和双端队列，普通队列有PrioirtyQueue，但其实PrioirtyQueue是按一定规则排序的，所以要想使用普通队列还得使用双端队列LinkedList或ArrayDeque，双端队列即可端都可以进可以出的队列，队列常用于广度优先搜索，PrioirtyQueue默认是一个小顶堆

    PrioirtyQueue的构造方法：

    PriorityQueue()

    PriorityQueue(Collection<? extends E> c)

    PriorityQueue(Comparator<? super E> comparator)

    PriorityQueue(int initialCapacity)

    PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

    PriorityQueue(PriorityQueue<? extends E> c)

    PriorityQueue(SortedSet<? extends E> c)

    Queue常用方法：

    boolean add(E e)

    E element()

    E remove()

    boolean offer(E e)

    E peek() 

    E poll()

    LinkedList构造方法（见上）

    ArrayDeque构造方法

    ArrayDeque()

    ArrayDeque(Collection<? extends E> c)

    ArrayDeque(int numElements)

    Deque常用方法

    boolean add(E e)

    void addFirst(E e)

    void addLast(E e)

    boolean contains(Object o)

    Iterator<E> descendingIterator()

    E element()

    E getFirst()

    E getLast() 

    Iterator<E> iterator()

    boolean offer(E e)

    boolean offerFirst(E e)

    boolean offerLast(E e)

    E peek()

    E peekFirst()

    E peekLast()

    E poll()

    E pollFirst()

    E pollLast()

    E pop()

    void push(E e)

    E remove()

    boolean remove(Object o)

    E removeFirst()

    boolean removeFirstOccurrence(Object o)

    E removeLast()

    boolean removeLastOccurrence(Object o)

    int size()

    下面给出PriorityQueue，LinkedList和ArrarDeque做队列使用的例子

378. 有序矩阵中第K小的元素

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第k小元素，而不是第k个元素。

示例:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13。

说明:

你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n^2 。

    // 想法:小顶堆，出k次，第k次出来的即为所求
    public int kthSmallest(int[][] matrix, int k) {
        Element ele;
        PriorityQueue<Element> queue = new PriorityQueue<>((e1, e2) -> ((Element)e1).val - ((Element)e2).val);
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        ele = new Element(0, 0, matrix[0][0]);
        queue.offer(ele);
        
        while(k > 0){
            ele = queue.poll();
            if(ele.i < matrix.length - 1 && !visited[ele.i+1][ele.j]){
            	Element e1 = new Element(ele.i+1, ele.j, matrix[ele.i+1][ele.j]);
                queue.offer(e1);
                visited[ele.i+1][ele.j] = true;
            }
            
            if(ele.j < matrix[0].length - 1 && !visited[ele.i][ele.j+1]){
                Element e2 = new Element(ele.i, ele.j+1, matrix[ele.i][ele.j+1]);
                queue.offer(e2);
                visited[ele.i][ele.j+1] = true;
            }
            
            k--;
        }
        
        return ele.val;
    }
    
    private class Element{
        int i;
        int j;
        int val;
        public Element(int i, int j, int val){
            this.i = i;
            this.j = j;
            this.val = val;
        }
    }

    使用PriorityQueue的典型场合，求第K小，用小顶堆，堆中第K个元素即为第K小

841. 钥匙和房间

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初，除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true，否则返回 false。

示例 1：

输入: [[1],[2],[3],[]]
输出: true
解释:  
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例 2：

输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

提示：

1. 1 <= rooms.length <= 1000
2. 0 <= rooms[i].length <= 1000
3. 所有房间中的钥匙数量总计不超过 3000。

    // 想法：对0号房间能到的房间，这些房间能到的房间也是符合题意的
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Set<Integer> handledRooms = new HashSet<>();
        Queue<Integer> enterRooms = new LinkedList<>();
        int room;
        List<Integer> keys;
        
        enterRooms.add(0);
        
        while(!enterRooms.isEmpty()){
            room = enterRooms.poll();
            keys = rooms.get(room);
            handledRooms.add(room);
            
            for(Integer k: keys){
                while(!handledRooms.contains(k)){
                    enterRooms.offer(k);
                    handledRooms.add(k);
                }
            }
            
        }
        
        return handledRooms.size() == rooms.size();
    }

    使用LinkedList作为队列，将能进入的房间入队列待处理，求这些房间能进入的房间，入队，直到队列空（没有能进入的房间）

200. 岛屿数量

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1

示例 2:

输入:
11000
11000
00100
00011

输出: 3

    public int numIslands(char[][] grid) {
         if(null==grid||grid.length==0){
            return 0;
        }
         boolean[][] used=new boolean[grid.length][grid[0].length];//该岛屿是否已经遍历
        ArrayDeque<Index> queue=new ArrayDeque<Index>();
        int count=0;//岛屿数
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'&&used[i][j]==false){
                    Index tmp=new Index(i,j);
                    count++;
                    queue.add(tmp);
                    while (!queue.isEmpty()){
                        Index index=queue.removeFirst();
                        if(index.x<grid.length-1){//判断右边是否是岛屿
                            if(grid[index.x+1][index.y]=='1'&&used[index.x+1][index.y]==false){
                                queue.add(new Index(index.x+1,index.y));
                                used[index.x+1][index.y]=true;
                            }
                        }
                        if(index.y<grid[0].length-1){//判断下边是否有岛屿
                            if(grid[index.x][index.y+1]=='1'&&used[index.x][index.y+1]==false){
                                queue.add(new Index(index.x,index.y+1));
                                used[index.x][index.y+1]=true;
                            }
                        }
                         if(index.y>0){//判断左边是否有岛屿
                            if(grid[index.x][index.y-1]=='1'&&used[index.x][index.y-1]==false){
                                queue.add(new Index(index.x,index.y-1));
                                used[index.x][index.y-1]=true;
                            }
                        }
                         if(index.x>0){//判断上边是否有岛屿
                            if(grid[index.x-1][index.y]=='1'&&used[index.x-1][index.y]==false){
                                queue.add(new Index(index.x-1,index.y));
                                used[index.x-1][index.y]=true;
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
    
     public  class Index{
        int x;//行索引
        int y;//列索引
 
        public Index(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    使用ArrayDeque，使用广度优先，当出现陆地时，将相邻陆地也处理作为一块岛屿

    Array

    数组应该是使用的最广泛的数据结构了，最简单，效率最高，在一般场合下使用是很合适的，缺点是长度必须是事先确定的，数组有一维，多维（二维，三维。。。），使用数组作为基础可以实现很多高级算法，如树状数组，并查集等，或者用于动态规划等，可以说是无处不在，数组常用的技巧有双索引技巧（对撞指针，滑动窗口）

    下面给出对撞指针和滑动窗口的例子

167. 两数之和 II - 输入有序数组

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

• 返回的下标值（index1 和 index2）不是从零开始的。
• 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2

    // 想法：因为有序，所以从两端开始，如果两端和大于目标，大端减小，如果两端和小于目标，小端增加，直到找到结果
    public int[] twoSum(int[] numbers, int target) {
        int little = 1;
        int large = numbers.length;
        
        while(numbers[little-1] + numbers[large-1] != target)
        {
            if(numbers[little-1] + numbers[large-1] > target)
            {
                large--;
            }
            else
            {
                little++;
            }
        }
        
        return new int[]{little, large};
    }

    因为有序，所以从两端开始，如果两端和大于目标，大端减小，如果两端和小于目标，小端增加，直到找到结果

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例: 

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

    public int minSubArrayLen(int s, int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;

        int len = nums.length;
        int start = 0, end = 0;
        int sum = 0;
        int minLen = len + 1;
        while(start < len) {
            while(end < len && sum < s) {
                sum += nums[end ++];
            }
            if(sum < s)
                break;
            if(end - start < minLen) {
                minLen = end - start;
            }
            sum -= nums[start];
            ++ start;
        }
        return (minLen > len) ? 0 : minLen;
    }

    算法还是比较巧妙的，使用滑动窗口，高端不断增加，舍弃低端，找出高低端之间大于S的最小长度

---

亲爱的读者：有时间可以点赞评论一下