通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

算法题中常用的java数据结构

9215人浏览 / 0人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  leetcode  | 

作者:因情语写

链接:https://www.proprogrammar.com/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<Eiterator()

    int lastIndexOf(Object o)

    ListIterator<ElistIterator()

    ListIterator<ElistIterator(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<Espliterator()

    List<EsubList(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<Eiterator()

    boolean remove(Object o)

    boolean removeAll(Collection<?> c)

    boolean retainAll(Collection<?> c)

    int size()

    default Spliterator<Espliterator()

     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<KkeySet()

    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<Vvalues()

    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<EdescendingIterator()

    E element()

    E getFirst()

    E getLast() 

    Iterator<Eiterator()

    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. 长度最小的子数组

给定一个含有 个正整数的数组和一个正整数 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的最小长度


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

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告