#yyds干货盘点# LeetCode刷题集131 - 140

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

博主私藏的LeetCode刷题集合
有些较难的问题都有思路和注释node

131. 分割回文串

给定一个字符串 s,将 s 分割成一些子串,使每一个子串都是回文串。算法

返回 s 全部可能的分割方案。数组

示例:markdown

输入: "aab"
输出:app

[
  ["aa","b"],
  ["a","a","b"]
]
class Solution {
     int len;
    ArrayList<List<String>> res = new ArrayList<>();
    String s;
    boolean[][] dp;

    public List<List<String>> partition(String s) {
        this.s = s;
        len = s.length();

        if (len < 1)
            return res;

        // dp[i][j] 表示某一子串,s.substring(i, j + 1)
        // 例如 s="babad",dp[0][0] = "b",dp[0][4] = "babad"
        dp = new boolean[len][len];
        // one character
        // 斜着遍历 [0,0] -> [1,1] -> ...
        // 单个字符均为回文
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        // two character
        // 斜着遍历 [0,1] -> [1,2] -> ...
        // 两个字符均相同才是回文
        for (int i = 0; i < len - 1; i++) {
            dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }
        // others
        // 开始dp,  此子串 = 字符 + 左下角的子串 + 字符
        // 只有左下角是回文,同时两端添加的字符相同时,才是回文
        for (int i = 2; i < len; i++) {
            for (int j = 0; j < len - i; j++) {
                dp[j][j + i] = dp[j + 1][j + i - 1] && s.charAt(j) == s.charAt(j + i);
            }
        }
        //回溯法,穿串串
        foo(new LinkedList<>(),0);

        return res;
    }

    void foo(LinkedList<String> path, int level) {
        if (level >= len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = level; i < len; i++) {
            if (dp[level][i]) {
                path.add(s.substring(level, i + 1));
                foo(path, i + 1);
                path.removeLast();
            }
        }
    }

}

132. 分割回文串 II

给定一个字符串 s,将 s 分割成一些子串,使每一个子串都是回文串。dom

返回符合要求的最少分割次数。ide

示例:测试

输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。ui

class Solution {
   public int minCut(String s) {
        if(s == null || s.length() <= 1)
            return 0;
        int len = s.length();
        int dp[] = new int[len];
        Arrays.fill(dp, len-1);
        for(int i = 0; i < len; i++){
            // 注意偶数长度与奇数长度回文串的特色
            mincutHelper(s , i , i , dp);  // 奇数回文串以1个字符为中心
            mincutHelper(s, i , i+1 , dp); // 偶数回文串以2个字符为中心
        }
        return dp[len-1];
    }
    private void mincutHelper(String s, int i, int j, int[] dp){
        int len = s.length();
        while(i >= 0 && j < len && s.charAt(i) == s.charAt(j)){
            dp[j] = Math.min(dp[j] , (i==0?-1:dp[i-1])+1);
            i--;
            j++;
        }
    }
}

133. 克隆图

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。this

图中的每一个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。

class Node {
    public int val;
    public List<Node> neighbors;
}

测试用例格式:

简单起见,每一个节点的值都和它的索引相同。例如,第一个节点值为 1,第二个节点值为 2,以此类推。该图在测试用例中使用邻接列表表示。

邻接列表是用于表示有限图的无序列表的集合。每一个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点(值为 1)。你必须将 给定节点的拷贝 做为对克隆图的引用返回。

示例 1:
在这里插入图片描述

输入:adjList = [[2,4],[1,3],[2,4],[1,3]]
输出:[[2,4],[1,3],[2,4],[1,3]]
解释:
图中有 4 个节点。
节点 1 的值是 1,它有两个邻居:节点 2 和 4 。
节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
节点 4 的值是 4,它有两个邻居:节点 1 和 3 。
示例 2:

在这里插入图片描述

输入:adjList = [[]]
输出:[[]]
解释:输入包含一个空列表。该图仅仅只有一个值为 1 的节点,它没有任何邻居。
示例 3:

输入:adjList = []
输出:[]
解释:这个图是空的,它不含任何节点。
示例 4:

在这里插入图片描述

输入:adjList = [[2],[1]]
输出:[[2],[1]]

提示:

节点数介于 1 到 100 之间。
每一个节点值都是惟一的。
无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
因为图是无向的,若是节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
图是连通图,你能够从给定节点访问到全部节点。

PS:
克隆图

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/
class Solution {
      Map<Node, Node> map = new HashMap<>();
    public Node cloneGraph(Node node) {
        if(node == null) return null;
        Node copy = new Node(node.val, new ArrayList<>());
        map.put(node, copy);
        for(Node neighbor : node.neighbors){
            if(map.containsKey(neighbor)){
                copy.neighbors.add(map.get(neighbor));
            }else{
                copy.neighbors.add(cloneGraph(neighbor));
            }
        }
        return copy;
    }
}

134. 加油站

在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站须要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。

若是你能够绕环路行驶一周,则返回出发时加油站的编号,不然返回 -1。

说明:

若是题目有解,该答案即为惟一答案。
输入数组均为非空数组,且长度相同。
输入数组中的元素均为非负数。
示例 1:

输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3

解释:
从 3 号加油站(索引为 3 处)出发,可得到 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站,你须要消耗 5 升汽油,正好足够你返回到 3 号加油站。
所以,3 可为起始索引。
示例 2:

输入:
gas = [2,3,4]
cost = [3,4,3]

输出: -1

解释:
你不能从 0 号或 1 号加油站出发,由于没有足够的汽油可让你行驶到下一个加油站。
咱们从 2 号加油站出发,能够得到 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油
你没法返回 2 号加油站,由于返程须要消耗 4 升汽油,可是你的油箱只有 3 升汽油。
所以,不管怎样,你都不可能绕环路行驶一周。

class Solution {
      public int canCompleteCircuit(int[] gas, int[] cost) {
        int g = 0, res = 0, start = 0;  // 记录车子当前总油量,一路的开销,当前起始的位置
        for(int i=0;i<gas.length;i++) {
            g += gas[i] - cost[i];      // 加的油扣掉花费的油
            res += gas[i] - cost[i];    // 计算一路的开销
            if(g < 0) {
                g = 0;                  // 不能到达下一个加油站,清零,从下一个开始
                start = i + 1;          // 记录下一个起点
            }
        }
        return res < 0 ? -1: start;
    }
}

135. 分发糖果

老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每一个孩子的表现,预先给他们评分。

你须要按照如下要求,帮助老师给这些孩子分发糖果:

每一个孩子至少分配到 1 个糖果。
相邻的孩子中,评分高的孩子必须得到更多的糖果。
那么这样下来,老师至少须要准备多少颗糖果呢?

示例 1:

输入: [1,0,2]
输出: 5
解释: 你能够分别给这三个孩子分发 二、一、2 颗糖果。
示例 2:

输入: [1,2,2]
输出: 4
解释: 你能够分别给这三个孩子分发 一、二、1 颗糖果。
第三个孩子只获得 1 颗糖果,这已知足上述两个条件。

class Solution {
       public int candy(int[] ratings) {
        if(ratings == null || ratings.length == 0){
            return 0;
        }
        int[] nums = new int[ratings.length];//记录每一位孩子获得的糖果数
        nums[0] = 1;
        //先正序遍历,若是后一位比前一位高分,就给比前一位多1的糖果,不然给1
        for(int i = 1; i < ratings.length; i++){
            if(ratings[i] > ratings[i-1]){
                nums[i] = nums[i-1] + 1;        
            }else {
                nums[i] = 1;
            }
        }
        //在倒叙遍历,若是前一位比后一位高分而且获得的糖果小于或等于后一位,就给前一位孩子比后一位孩子多一个糖果
        for(int i = ratings.length -2 ; i >= 0; i--){
            if(ratings[i] > ratings[i+1] && nums[i] <= nums[i+1]){
                nums[i] = nums[i+1] +1;
            }
        }
        int count = 0;
        for(int i : nums){
            count +=i;
        }
        return count;
    }
}

136. 只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次之外,其他每一个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具备线性时间复杂度。 你能够不使用额外空间来实现吗?

示例 1:

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

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

PS:

异或:5^5=0,5^0=5,相同的数异或获得0,与0异或获得自己,因此把数组全部的数异或一遍,一对对情侣都消掉,就剩那个单身狗了。

线性时间复杂度

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result = result^nums[i];
        }
        return result;
    }
}

137. 只出现一次的数字 II

给定一个非空整数数组,除了某个元素只出现一次之外,其他每一个元素均出现了三次。找出那个只出现了一次的元素。

说明:

你的算法应该具备线性时间复杂度。 你能够不使用额外空间来实现吗?

示例 1:

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

输入: [0,1,0,1,0,1,99]
输出: 99

PS:
对每一位单独统计出现1的次数, 若是出现的次数不能整除3说明惟一存在的数在这一位上为1, 时间复杂度O(32N)

class Solution {
  public int singleNumber(int[] nums) {

        int ret = 0;
        for(int i = 0; i < 32; ++i) {
            int bitnums = 0;
            //二进制向左走一位
            int bit = 1 << i;
            for(int num : nums) {
            //每一个数这一位是否是1若是是1就++
                if((num&bit) != 0)
                    bitnums++;
            }
            //若是不能%3的话,证实那个出现过一次的数在这一位是1;
            if(bitnums % 3 != 0)
                ret |= bit;
        }
        return ret;
    }
}

138. 复制带随机指针的链表

给定一个链表,每一个节点包含一个额外增长的随机指针,该指针能够指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。

咱们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每一个节点用一个 [val, random_index] 表示:

val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);若是不指向任何节点,则为 null 。

示例 1:
在这里插入图片描述

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2:

在这里插入图片描述

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

在这里插入图片描述

输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]
示例 4:

输入:head = []
输出:[]
解释:给定的链表为空(空指针),所以返回 null。

提示:

-10000 <= Node.val <= 10000
Node.random 为空(null)或指向链表中的节点。
节点数目不超过 1000 。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
     public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
        // 空间复杂度O(1),将克隆结点放在原结点后面
        Node node = head;
        // 1->2->3  ==>  1->1'->2->2'->3->3'
        while(node != null){
            Node clone = new Node(node.val,node.next,null);
            Node temp = node.next;
            node.next = clone;
            node = temp;
        }
        // 处理random指针
        node = head;
        while(node != null){
            // !!
            node.next.random = node.random == null ? null : node.random.next;
            node = node.next.next;
        }
        // 还原原始链表,即分离原链表和克隆链表
        node = head;
        Node cloneHead = head.next;
        while(node.next != null){
            Node temp = node.next;
            node.next = node.next.next;
            node = temp;
        }
        return cloneHead;
    }
}

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,断定 s 是否能够被空格拆分为一个或多个在字典中出现的单词。

说明:

拆分时能够重复使用字典中的单词。
你能够假设字典中没有重复的单词。
示例 1:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 由于 "leetcode" 能够被拆分红 "leet code"。
示例 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 由于 "applepenapple" 能够被拆分红 "apple pen apple"。
注意你能够重复使用字典中的单词。
示例 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
        Map hasCompute = new HashMap<Integer,Boolean>();
        return wordBreak(s,wordDict,0,hasCompute);
    }
    public boolean wordBreak(String s,List<String> wordDict,int index,Map hasCompute){
        //找到全部可能性
        boolean result = false;
        for(String word:wordDict){
           if(s.startsWith(word,index)){               
               index+=word.length();
               //先判断以前是否已经计算过
               if(hasCompute.containsKey(index)) return false;//若是已经计算过,说明是失败的
               if(index == s.length()) return true;//递归结束条件
               if(wordBreak(s,wordDict,index,hasCompute)) return true;//若是找到了,直接返回
               else{
                   //记录已经计算的字符串
                   if(!hasCompute.containsKey(index)){
                       hasCompute.put(index,false);
                   }
                   //把index还原
                   index-=word.length();  
                } 
            }
        }
        return result;
    }
}

140. 单词拆分 II

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增长空格来构建一个句子,使得句子中全部的单词都在词典中。返回全部这些可能的句子。

说明:

分隔时能够重复使用字典中的单词。
你能够假设字典中没有重复的单词。
示例 1:

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
"cats and dog",
"cat sand dog"
]
示例 2:

输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解释: 注意你能够重复使用字典中的单词。
示例 3:

输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

class Solution {
      private Map<String, List<String>> cache = new HashMap<>();

    public List<String> wordBreak(String s, List<String> wordDict) {
        return dfs(s, wordDict,0);
    }

    private List<String> dfs(String s, List<String> wordDict, int offset){

        if (offset == s.length()){
            List<String> res = new ArrayList<>();
            res.add("");
            return res;
        }

        if (cache.containsKey(s.substring(offset))){
           return cache.get(s.substring(offset));
        }

        List<String> res = new ArrayList<>();
        for (String word : wordDict){
            if (word.equals(s.substring(offset, Math.min(s.length(),offset + word.length())))){
                List<String> next = dfs(s, wordDict, offset + word.length());
                for (String str: next){
                    res.add((word + " "+ str).trim());
                }
            }
        }

        cache.put(s.substring(offset),res);
        return res;
    }
}