#yyds干货盘点# LeetCode刷题集211 - 220

2021年11月24日 阅读数:3
这篇文章主要向大家介绍#yyds干货盘点# LeetCode刷题集211 - 220,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

博主私藏的LeetCode刷题集合
有些较难的问题都有思路和注释正则表达式

211. 添加与搜索单词 - 数据结构设计

设计一个支持如下两种操做的数据结构:算法

void addWord(word)
bool search(word)

search(word) 能够搜索文字或正则表达式字符串,字符串只包含字母 . 或 a-z 。 . 能够表示任何一个字母。数组

示例:markdown

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

说明:数据结构

你能够假设全部单词都是由小写字母 a-z 组成的。app

class WordDictionary {

    Map<Integer,Set<String>> map = new HashMap<>();//根据字符串长度分开存放
    public WordDictionary() {

    }
    public void addWord(String word) {
        int length = word.length();
        if(map.get(length)!=null){
            map.get(length).add(word);
        }else{
            Set<String> set = new HashSet<>();
            set.add(word);
            map.put(length, set);
        }
    }
    public boolean search(String word) {
        Set<String> set = map.get(word.length());
        if(set==null){  //不存在该长度的字符串,直接返回false;
            return false;
        }
        if(set.contains(word)) return true;
        char[] chars = word.toCharArray();
        P:for(String s : set){
            if(word.length()!=s.length()){
                continue;
            }
            char[] cs = s.toCharArray();
            for(int i = 0; i< cs.length; i++){//逐个字符对比
                if(chars[i] != '.' && chars[i] != cs[i]){
                    continue P;
                }
            }
            set.add(word);
            return true;
        }
        return false;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

212. 单词搜索 II

给定一个二维网格 board 和一个字典中的单词列表 words,找出全部同时在二维网格和字典中出现的单词。ide

单词必须按照字母顺序,经过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不容许被重复使用。函数

示例:学习

输入: 测试

words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

输出: ["eat","oath"]
说明:
你能够假设全部输入都由小写字母 a-z 组成。

提示:

你须要优化回溯算法以经过更大数据量的测试。你可否早点中止回溯?
若是当前单词不存在于全部单词的前缀中,则能够当即中止回溯。什么样的数据结构能够有效地执行这样的操做?散列表是否可行?为何? 前缀树如何?若是你想学习如何实现一个基本的前缀树,请先查看这个问题: 实现Trie(前缀树)。

PS:
首先构建一个字典树,而后在dfs的时候加入字典树,以某个字符串结尾的能够减小搜索次数
这里为何不用开头用结尾呢, (●ˇ∀ˇ●)
结尾在这里就是我搜索完一个,我能够直接比较,若是没有的话,我再返回上一个,

class TrieNode {
    private static final int ALPHABET_SIZE = 26;

    TrieNode[] children = new TrieNode[ALPHABET_SIZE];
    // 判断这个前缀是否是某个字符串的结尾
    boolean isEndOfWord = false;
    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < ALPHABET_SIZE; i++)
            children[i] = null;
    }
}

class Trie {
    public TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode curNode = root;
        int index;
        for (int i = 0; i < word.length(); i++) {
            index = word.charAt(i) - 'a';
            if (curNode.children[index] == null) {
                curNode.children[index] = new TrieNode();
            }
            curNode = curNode.children[index];
        }
        curNode.isEndOfWord = true;
    }
}
class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        if (words == null || words.length == 0 || board == null || board.length == 0 || board[0].length == 0)
            return result;

        Trie trie = new Trie();
        for (String temp : words)
            trie.insert(temp);

        TrieNode root = trie.root;
        boolean[][] visited = new boolean[board.length][board[0].length];
        Set<String> tempResult = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (root.children[board[i][j] - 'a'] != null ) {
                    dfs(board, visited, i, j, root.children[board[i][j] - 'a'], tempResult, sb);
                }
            }
        }

        // 须要把tempResult这个set拷贝到真正的result List中进行返回
        Iterator<String> iterator = tempResult.iterator();
        while (iterator.hasNext()) {
            result.add(iterator.next());
        }
        return result;
    }

    private void dfs(char[][] board, boolean[][] visited, int startIInBoard, int startJInBoard
            , TrieNode curNode, Set<String> resultSet, StringBuilder curStrBuilder) {
        curStrBuilder.append(board[startIInBoard][startJInBoard]);
        visited[startIInBoard][startJInBoard] = true;
        if (curNode.isEndOfWord) {
            resultSet.add(curStrBuilder.toString());
        }
        // 向上搜索, 若是上面的格子没有被搜索过的话
        if (startIInBoard > 0 && !visited[startIInBoard - 1][startJInBoard]
                && curNode.children[board[startIInBoard - 1][startJInBoard] - 'a'] != null) {
            dfs(board, visited,startIInBoard - 1, startJInBoard
                    , curNode.children[board[startIInBoard - 1][startJInBoard] - 'a'], resultSet, curStrBuilder);
        }
        // 向下搜索
        if (startIInBoard < board.length - 1 && !visited[startIInBoard + 1][startJInBoard]
                && curNode.children[board[startIInBoard + 1][startJInBoard] - 'a'] != null) {
            dfs(board, visited,startIInBoard + 1, startJInBoard
                    , curNode.children[board[startIInBoard + 1][startJInBoard] - 'a'], resultSet, curStrBuilder);
        }
        // 向左搜索
        if (startJInBoard > 0 && !visited[startIInBoard][startJInBoard - 1]
                && curNode.children[board[startIInBoard][startJInBoard - 1] - 'a'] != null) {
            dfs(board, visited, startIInBoard, startJInBoard - 1
                    , curNode.children[board[startIInBoard][startJInBoard - 1] - 'a'], resultSet, curStrBuilder);
        }
        // 向右搜索
        if (startJInBoard < board[0].length - 1 && !visited[startIInBoard][startJInBoard + 1]
                && curNode.children[board[startIInBoard][startJInBoard + 1] - 'a'] != null) {
            dfs(board, visited, startIInBoard, startJInBoard + 1
                    , curNode.children[board[startIInBoard][startJInBoard + 1] - 'a'], resultSet, curStrBuilder);
        }
        // 恢复现场
        curStrBuilder.setLength(curStrBuilder.length() - 1);
        visited[startIInBoard][startJInBoard] = false;
    }
}

214. 最短回文串

给定一个字符串 s,你能够经过在字符串前面添加字符将其转换为回文串。找到并返回能够用这种方式转换的最短回文串。

示例 1:

输入: "aacecaaa"
输出: "aaacecaaa"
示例 2:

输入: "abcd"
输出: "dcbabcd"

class Solution {
    public static String shortestPalindrome(String s) {
        StringBuilder r = new StringBuilder(s).reverse();
        String str = s + "#" + r;
        int[] next = next(str);
          //若是是回文串  1234321     #       1234321
            //next[str.length]=7,r.substring(0,0)=""输出原字符串
            //若是  123432    #   234321  next[str.length]=5  
            //r.substring(0,6-5),只须要第一位
        String prefix = r.substring(0, r.length() - next[str.length()]);
        return prefix + s;
    }

    // next数组
      //KMP的next[j]=x就是0~x-1与 j-x~j-1 的元素是相同的
      //大概是这样
    private static int[] next(String P) {
        int[] next = new int[P.length() + 1];
        next[0] = -1;
        int k = -1;
        int i = 1;
        //next【k】保存的是我上次相等的时候
                //不相等的时候我就从我上一次相等的时候就行匹配
                //i是快指针,k是慢指针
        while (i < next.length) {
            if (k == -1 || P.charAt(k) == P.charAt(i - 1)) {
                next[i++] = ++k;
            } else {
                k = next[k];
            }
        }
        return next;
    }
}

215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意,你须要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不一样的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你能够假设 k 老是有效的,且 1 ≤ k ≤ 数组的长度。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums.length < 2){
            return nums.length == 1 ? nums[0] : -1;
        }
        return countingSort(nums, k);
    }

    private int countingSort(int[] nums, int k){
        int max = 0;
        int min = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > max){
                max = nums[i];
            }

            if(nums[i] < min){
                min = nums[i];
            }
        }

        int length = (max - min) + 1;
        int[] newArray = new int[length];
        //这个数组记录的是与最小的值相差的某位的数量
        for(int i = 0; i < nums.length; i++){
            newArray[nums[i] - min]++;
        }

        int j = 0;
        for(int i = newArray.length - 1; i >= 0; i--){
            //这样最大值就出来了,先从最大值开始
            if(newArray[i] > 0){
                j = newArray[i] + j;
                if(j >= k){
                    return i + min;
                }
            }
        }
        return -1;
    }
}

216. 组合总和 III

找出全部相加之和为 n 的 k 个数的组合。组合中只容许含有 1 - 9 的正整数,而且每种组合中不存在重复的数字。

说明:

全部数字都是正整数。
解集不能包含重复的组合。
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

class Solution {
    //结果集
    public List<List<Integer>> lists = new ArrayList<>();
    //临时集
    public List<Integer> list = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        //回溯入口
        backTracking(list, 0, 1, k, n, 0);
        return lists;
    }
    public void backTracking(List<Integer> list, int index, int c, int k, int n, int sum){
        //回溯出口
        //保证是k个数字的累加,且,和为指定值
        if(index == k && sum == n){
            //知足添加入集合
            List<Integer> currentList = new ArrayList<>();
            currentList.addAll(list);
            lists.add(currentList);
            return;
        }
        //剪枝操做
        if(sum > n){
            return;
        }
        //回溯条件
        for(int i = c; i <= 9; ++i){
            list.add(i);
            sum += i;
            backTracking(list, index + 1, i + 1, k, n, sum);
            list.remove(list.size() - 1);
            sum -= i;
        }
    }
}

217. 存在重复元素

给定一个整数数组,判断是否存在重复元素。

若是任何值在数组中出现至少两次,函数返回 true。若是数组中每一个元素都不相同,则返回 false。

示例 1:

输入: [1,2,3,1]
输出: true
示例 2:

输入: [1,2,3,4]
输出: false
示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

class Solution {
    public boolean containsDuplicate(int[] nums) {
          Set<Integer> res = new HashSet<Integer>();
        for(int i:nums)
            res.add(i);
        return res.size()<nums.length?true:false;
    }
}

218. 天际线问题

城市的天际线是从远处观看该城市中全部建筑物造成的轮廓的外部轮廓。如今,假设您得到了城市风光照片(图A)上显示的全部建筑物的位置和高度,请编写一个程序以输出由这些建筑物造成的天际线(图B)。
在这里插入图片描述
在这里插入图片描述

Buildings Skyline Contour

每一个建筑物的几何信息用三元组 [Li,Ri,Hi] 表示,其中 Li 和 Ri 分别是第 i 座建筑物左右边缘的 x 坐标,Hi 是其高度。能够保证 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX 和 Ri - Li > 0。您能够假设全部建筑物都是在绝对平坦且高度为 0 的表面上的完美矩形。

例如,图A中全部建筑物的尺寸记录为:[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] 。

输出是以 [ [x1,y1], [x2, y2], [x3, y3], ... ] 格式的“关键点”(图B中的红点)的列表,它们惟一地定义了天际线。关键点是水平线段的左端点。请注意,最右侧建筑物的最后一个关键点仅用于标记天际线的终点,并始终为零高度。此外,任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

例如,图B中的天际线应该表示为:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]。

说明:

任何输入列表中的建筑物数量保证在 [0, 10000] 范围内。
输入列表已经按左 x 坐标 Li 进行升序排列。
输出列表必须按 x 位排序。
输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案;三条高度为 5 的线应该在最终输出中合并为一个:[...[2 3], [4 5], [12 7], ...]

class Solution {
   // 线段树 
    public List<List<Integer>> getSkyline(int[][] buildings) {
        int len = buildings.length;
        if (len == 0) return new ArrayList<>();
        return segment(buildings, 0, len - 1);
    }

    private List<List<Integer>> segment(int[][] buildings, int l, int r) {
        // 建立返回值
        List<List<Integer>> res = new ArrayList<>();

        // 找到树底下的结束条件 -> 一个建筑物
        if (l == r) {
            res.add(Arrays.asList(buildings[l][0], buildings[l][2])); // 左上端坐标
            res.add(Arrays.asList(buildings[l][1], 0)); // 右下端坐标
            return res;
        }

        int mid = l + (r - l) / 2; // 取中间值

        // 左边递归
        List<List<Integer>> left = segment(buildings, l, mid);

        // 右边递归
        List<List<Integer>> right = segment(buildings, mid + 1, r);

        // 左右合并

        // 建立left 和 right 的索引位置
        int m = 0, n = 0;
        // 建立left 和 right 目前的高度
        int lpreH = 0, rpreH = 0;
        // 两个坐标
        int leftX, leftY, rightX, rightY;
        while (m < left.size() || n < right.size()) {

            // 当有一边彻底加入到res时,则加入剩余的那部分
            if (m >= left.size()) res.add(right.get(n++));
            else if (n >= right.size()) res.add(left.get(m++));

            else { // 开始判断left 和 right
                leftX = left.get(m).get(0); // 不会出现null,能够直接用int类型
                leftY = left.get(m).get(1);
                rightX = right.get(n).get(0);
                rightY = right.get(n).get(1);
                //看我这两个矩形谁靠左
                if (leftX < rightX) {
                    //左面还比之前高,就加左面
                   if (leftY > rpreH) res.add(left.get(m));
                   //左面比右面高,我要加入左面点的以及之前右面的的高度,由于我立刻就有新高度了2,10
                   else if (lpreH > rpreH) res.add(Arrays.asList(leftX, rpreH));
                 //  用我左面的高替换我之前右面的高
                    lpreH = leftY;
                    m++;
                } else if (leftX > rightX) {
                   if (rightY > lpreH) res.add(right.get(n));
                   else if (rpreH > lpreH) res.add(Arrays.asList(rightX, lpreH));
                    rpreH = rightY;
                    n++;
                } else { // left 和 right 的横坐标相等
                  if (leftY >= rightY && leftY != (lpreH > rpreH ? lpreH : rpreH)) res.add(left.get(m));
                    else if (leftY <= rightY && rightY != (lpreH > rpreH ? lpreH : rpreH)) res.add(right.get(n));
                    lpreH = leftY;
                    rpreH = rightY;
                    m++;
                    n++;
                }
            }
        }
        return res;
    }

}

219. 存在重复元素 II

给定一个整数数组和一个整数 k,判断数组中是否存在两个不一样的索引 i 和 j,使得 nums [i] = nums [j],而且 i 和 j 的差的绝对值最大为 k。

示例 1:

输入: nums = [1,2,3,1], k = 3
输出: true
示例 2:

输入: nums = [1,0,1,1], k = 1
输出: true
示例 3:

输入: nums = [1,2,3,1,2,3], k = 2
输出: false
PS:
滑动窗口

class Solution {
       public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])){
                return true;
            }
            set.add(nums[i]);
            if(set.size() == k+1){
                set.remove(nums[i - k]);
            }

        }

        return false;
    }
}

220. 存在重复元素 III

给定一个整数数组,判断数组中是否有两个不一样的索引 i 和 j,使得 nums [i] 和 nums [j] 的差的绝对值最大为 t,而且 i 和 j 之间的差的绝对值最大为 ķ。

示例 1:

输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
示例 2:

输入: nums = [1,0,1,1], k = 1, t = 2
输出: true
示例 3:

输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
   // 滑动窗口结合查找表,此时滑动窗口即为查找表自己(控制查找表的大小便可控制窗口大小)
    TreeSet<Long> set = new TreeSet<>();
    for (int i = 0; i < nums.length; i++) {
        // 边添加边查找
        // 查找表中是否有大于等于 nums[i] - t 且小于等于 nums[i] + t 的值
        Long ceiling = set.ceiling((long) nums[i] - (long) t);
        if (ceiling != null && ceiling <= ((long) nums[i] + (long) t)) {
            return true;
        }
        // 添加后,控制查找表(窗口)大小,移除窗口最左边元素
        set.add((long) nums[i]);
        if (set.size() == k + 1) {
            set.remove((long) nums[i - k]);
        }
    }
    return false;
    }
}