1694. 重新格式化电话号码

难度简单65

给你一个字符串形式的电话号码 number 。number 由数字、空格 ' '、和破折号 '-' 组成。

请你按下述方式重新格式化电话号码。

  • 首先，删除 所有的空格和破折号。
  • 其次，将数组从左到右每 3 个一组分块，直到 剩下 4 个或更少数字。剩下的数字将按下述规定再分块：
    • 2 个数字：单个含 2 个数字的块。
    • 3 个数字：单个含 3 个数字的块。
    • 4 个数字：两个分别含 2 个数字的块。

最后用破折号将这些块连接起来。注意，重新格式化过程中 不应该 生成仅含 1 个数字的块，并且 最多 生成两个含 2 个数字的块。

返回格式化后的电话号码。

题目解读

其实就是每三个字符添加一个分隔符,

处理最后剩的那一批字符, 如果是4个那么就 加成 - 2 - 2

如果是三个就继续 -3

如果是两个字符就是 -2

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public String reformatNumber(String number) {
    StringBuilder res = new StringBuilder("");
    number=number.replace(" ","").replace("-","");// 删除- 以及空格
    char[]chars=number.toCharArray();
    for(int i=0;i<chars.length;i+=3){
        if(res.length()!=0){
            res.append("-");
        }
        if(i+4>=chars.length){
            if(i+3>=chars.length){
                res.append(number.substring(i));
            }else{
                res.append(number.substring(i,i+2)).append("-").append(number.substring(i+2));
            }
            break;
        }
        String tmp=number.substring(i,i+3);
      res.append(tmp);
    }
    return res.toString();
    }
}

String replace()

语法

1
public String replace(char searchChar, char newChar)

参数

  • searchChar – 原字符。
  • newChar – 新字符。

返回值

替换后生成的新字符串。

实例

以下实例对字符串 Runoob 中的字符进行替换：

1
2
3
4
5
6
7
8
9
10
11
public class Main {
    public static void main(String args[]) {
        String Str = new String("Runoob");

        System.out.print("返回值 :" );
        System.out.println(Str.replace('o', 'T'));

        System.out.print("返回值 :" );
        System.out.println(Str.replace('u', 'D'));
    }
}

以上程序执行结果为：

1
2
返回值 :RunTTb
返回值 :RDnoob

777. 在LR字符串中交换相邻字符

难度中等217

在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。

题目给定的规则是:

  • L 只能向右移动
  • R 只能向左移动
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public boolean canTransform(String start, String end) {
        /*
        替换操作可以实际上是将 L 往左移动（L 左边为 X 时才能移动），R 往右移动（R 右边是 X 时才能移动），
        但 L 无法穿过 R，R 也无法穿过L。所以，如果去掉 start 和 end 中的所有 X，剩下的字符应该是相同的，否则返回 false。
        如果当前字符为L 且 i<j，那么这个 L 无法向右移动，返回 false；如果当前字符为 R 且 i>j，那么这个 RR 无法向左移动，返回 false。
        * */
        int i=0,j=0,n=end.length();
        char[]s=start.toCharArray();
        char[]e=end.toCharArray();
        // 从左往右遍历, 直到遇到 L or R
        while(true){
            while(i<n&&s[i]=='X'){ //右移
                i++;
            }
            while(j<n&&e[j]=='X'){ //同样的操作复刻一遍
                j++;
            }
            if(i==n&&n==j){ // 符合的 截止条件
                return true;
            }
            if(i==n||j==n||s[i]!=e[j]){// 遍历到两个不相同 , 由于 R  如果前面是R, 那么L 是无法移动到前面的, 因此这种情况直接return false;
                // 加上 只有一个到达了终点的情况
                return false;
            }
            if(s[i]=='L'&&i<j || s[i]=='R'&&i>j){
                // 由于 L 只能往右走 ,  但是此时两者的 下标不同, 比如 L  XL , 此时第二个字符串是无法变成第一种的, 因为L不能左移
                // 对于 R 同理
                return false;
            }
            // 当前两个相同, 继续遍历
            i++;
            j++;
        }
    }
}

1784. 检查二进制字符串字段

难度简单68

给你一个二进制字符串 s ，该字符串 不含前导零 。

如果 s 包含 零个或一个由连续的 '1' 组成的字段 ，返回 true 。否则，返回 false 。

如果 s 中 由连续若干个 '1' 组成的字段 数量不超过 1，返回 true 。否则，返回 false 。

题意解读

一个或多个1是一个连续字段 如果字符串s含有的连续字段数目≤1，则返回true，否则为false。

代码如下

1
2
3
4
5
class Solution {
    public boolean checkOnesSegment(String s) {
        return s.split("0").length<=1;
    }
}

811. 子域名访问计数

难度中等173

网站域名 "discuss.leetcode.com" 由多个子域名组成。顶级域名为 "com" ，二级域名为 "leetcode.com" ，最低一级为 "discuss.leetcode.com" 。当访问域名 "discuss.leetcode.com" 时，同时也会隐式访问其父域名 "leetcode.com" 以及 "com" 。

计数配对域名 是遵循 "rep d1.d2.d3" 或 "rep d1.d2" 格式的一个域名表示，其中 rep 表示访问域名的次数，d1.d2.d3 为域名本身。

  • 例如，"9001 discuss.leetcode.com" 就是一个 计数配对域名 ，表示 discuss.leetcode.com 被访问了 9001 次。

给你一个 计数配对域名 组成的数组 cpdomains ，解析得到输入中每个子域名对应的 计数配对域名 ，并以数组形式返回。可以按 任意顺序 返回答案。

HashMap统计

通过两个函数将域名的访问次数以及各级域名解析出来, 然后通过hashmap统计, 最后在整合成List返回即可

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public List<String> subdomainVisits(String[] strs) {
        LinkedList<String> res=new LinkedList<>();
        Map<String,Integer> map=new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            int cnt=getTime(strs[i]);
            String[]ss=divideString(strs[i]);
            for (int j = 0; j < ss.length; j++) {
                map.put(ss[j],map.getOrDefault(ss[j],0)+cnt);
            }
        }
        for (Map.Entry<String, Integer> kv : map.entrySet()) {
            res.add(kv.getValue() +" "+ kv.getKey());
        }
        return res;
    }
    int getTime(String s){
        int idx=0;
        while(s.charAt(idx)!=' '){
            idx++;
        }
        return Integer.parseInt(s.substring(0,idx));
    }
    String[] divideString(String s){
        int idx=0;
        while(s.charAt(idx)!=' '){
            idx++;
        }
        s=s.substring(idx+1);
        String[]res=s.split("\\.");
        for (int i = 0; i < res.length; i++) {
            String tmp=res[i];
            for (int j = i+1; j <res.length; j++) {
                tmp+="."+res[j];
            }
            res[i]=tmp;
        }
        return res;
    }
}

921. 使括号有效的最少添加

labuladong 题解思路

难度中等232

只有满足下面几点之一，括号字符串才是有效的：

  • 它是一个空字符串，或者
  • 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
  • 它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串 s ，移动N次，你就可以在字符串的任何位置插入一个括号。

  • 例如，如果 s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))" 。

返回 为使结果字符串 s 有效而必须添加的最少括号数。

题意解读

​ // /给定一个括号字符串 s ，在每次操作中，你可以在字符串的任何位置插入一个括号。

​ // 例如，如果 s = “()))” ，你可以插入一个左括号变成 “(()))”，或者插入一个右括号变成 “())))” 。

​ // 返回 为使结果字符串 s 有效而必须添加的最少括号数。

我们使用res记录插入的次数, 使用need记录需要右括号的次数

如果遍历到了左括号, 那么就是

  • need++

如果是右括号, 那么就是

  • need--

    如果此时 need==-1 , 也就是右括号多了一个, 那么需要插入一个左括号, 此时需要 res++ ,同时need 变为0

最后返回需要插入的左括号的数量res以及遍历完仍然需要的右括号的数量之和need即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minAddToMakeValid(String s) {
        // /给定一个括号字符串 s ，在每次操作中，你可以在字符串的任何位置插入一个括号。
        // 例如，如果 s = "()))" ，你可以插入一个左括号变成 "(()))"，或者插入一个右括号变成 "())))" 。
        // 返回 为使结果字符串 s 有效而必须添加的最少括号数。
        //"()))(("
        int res=0,need=0; // res记录插入的次数, need记录需要的右括号的数量
        char[]chars=s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if(chars[i]=='('){
                need++;
            }else{
                need--;
                if(need==-1){
                    res++;
                    need=0;
                }
            }
        }
        return res+need;
    }
}

134. 加油站

难度中等1053

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

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

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

感觉有点像那个**55. 跳跃游戏 - 力扣（LeetCode）**

是否能跳到终点

1
2
3
4
5
6
7
8
9
public boolean canJump(int[] nums) {
    int max_dis=nums[0]; // max_dis表示可以跳到的最大的下标
    for (int i = 1; i < nums.length; i++) {
        if(max_dis>=i){
            max_dis=Math.max(i+nums[i],max_dis);
        }
    }
    return max_dis>=nums.length-1;
}

题目确定可以跳到终点, 求最小的步数45. 跳跃游戏 II

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int jump(int[] nums) {
    if(nums.length==1) return 0; // 特殊情况
    // 题目确定可以跳到终点, 求最小的步数
    int res=1, end=nums[0] , max_dis=nums[0];
    // 需要确定当前这一步是否要跳? 如果不跳, 那么end 不变, 如果跳了, 那么end=i+num[i], res++
    // 如果当前为第i次跳跃(使用end记录第i次的距离) , 那么我们可以统计可以跳到的最大长度
    // max_dis=Math.max(max_dis, i+nums[i]);
    // 当前仅当 end==i的时候, 我们更换 end 为第i+1 次跳跃的最远距离, 并且res++(进行了一次跳跃)
    for (int i = 1; i < nums.length-1; i++) {
        max_dis=Math.max(max_dis,i+nums[i]);
        if(end==i){
            end=max_dis;
            res++;
        }
    }
    return res;
}

那么我们回到本题

写完发现这几道题似乎没有什么关联 🤽‍♂️

那么本题的解题思路

汽车进入站点 i 可以加 gas[i] 的油（图中绿色数字），离开站点会损耗 cost[i] 的油（图中红色数字），那么可以把站点和与其相连的路看做一个整体，将 gas[i] - cost[i] 作为经过站点 i 的油量变化值（图中橙色数字）：

示意图

这样，题目描述的场景就被抽象成了一个环形数组，数组中的第 i 个元素就是 gas[i] - cost[i]。

有了这个环形数组，我们需要判断这个环形数组中是否能够找到一个起点 start，使得从这个起点开始的累加和一直大于等于 0。

关键在于找到这么一个加油站, 使累加的过程中, 剩余的油量始终不小于0 , 那么根据题意, 可以得知这个解是唯一的

那么我们为什么不在遍历的过程中遇到剩余油量小于0的加油站直接返回呢?

  • 因为题目给的数据可能是无解的

    可能走到最后剩余的油量也是0 ,

    例如

    • gas[0,0,0,0]
    • cost[1,1,1,1]

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    /*给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，
    则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是 唯一 的。*/
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int rest=0,run=0,start=0;
        for (int i = 0; i < gas.length; i++) {
            rest+=(gas[i]-cost[i]);
            run+=(gas[i]-cost[i]); // run表示走的路程, 如果走的路程为负数, 说明当前位置耗油量大于加油量,
            if(run<0){
                start=i+1; // 题目需要返回的是 需要, 需要时数组对应的下标+1
                run=0; // 重置为0,
            }
        }
        return rest<0?-1:start; // rest<0表示 无法走完全程 (表示剩余的油量)
    }
    // 我们需要找到一个节点, 然后使得汽车行走(可以视作为一个累加的过程, ), 我们找到可以使得汽车行走过程中始终不会油量<0 的点,作为起始点
}

135. 分发糖果

难度困难1013

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

采用两次贪心的策略

  • 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
  • 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

这样从局部最优推出了全局最优，

即：相邻的孩子中，评分高的孩子获得更多的糖果

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int candy(int[] ratings) {
        int[]candy = new int[ratings.length];
        Arrays.fill(candy,1);//每个孩子最少发一个糖果
        for (int i = 1; i < ratings.length; i++) {
            if(ratings[i]>ratings[i-1]){
                candy[i]= candy[i-1]+1; // 局部最优
            }
        }
        for (int i = ratings.length - 2; i >= 0; i--) {
            if(ratings[i]>ratings[i+1]){
                candy[i]=Math.max(candy[i+1]+1, candy[i]); // 局部最优
            }
        }
        int ans=0;
        for (int i = 0; i < candy.length; i++) {
            // System.out.println(candy[i]);
            ans+= candy[i];
        }
        return ans;
    }
}

300. 最长递增子序列

难度中等2825

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

动态规划

不再赘述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    //最长递增子序列
    public int lengthOfLIS(int[] nums) {
        if(nums.length==1) return 1;
        int res=0;
        int[]dp=new int[nums.length]; //dp[i] 表示0~i 的最长递增子序列
        Arrays.fill(dp,1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[i]>nums[j])
                    dp[i]=Math.max(dp[i],dp[j]+1);
            }
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}

DP+ 二分

再新建一个数组，然后第一个数先放进去，然后第二个数和第一个数比较，

如果说大于第一个数，那么就接在他后面，如果小于第一个数，那么就替换，

一般的，如果有i个数，那么每进来一个新的数，都要用二分查找法来得知要替换在哪个位置的数。

因为有个for循环，所以是O(N),在加上循环里有个二分查找，所以最后是*O(NlogN)*的时间复杂度。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length==1) return 1;
        int[]tails=new int[nums.length]; // tails[i] 的值代表 长度为 i+1 的尾部元素值
        int res=0; //res为tails 的当前的长度 => tails 严格递增
        for (int i = 0; i < nums.length; i++) {
            // tails严格递增, 插入 nums[i] , 如果
            int l=0, r=res;
            while(l<r){//二分查找
                int m=l+r>>1;
                if(tails[m]<nums[i]) l=m+1;
                else r=m;
            }
            tails[r]=nums[i]; 
            // 保守起见一般使用  r ,避免翻车 => 此时 nums[i] 大于前面所有的元素, 因此放在最后 (r 此时==res , 刚好为tails的长度)
            if(res==r) res++;
        }
        return res;
    }
}

1894. 找到需要补充粉笔的学生编号

难度中等96

一个班级里有 n 个学生，编号为 0 到 n - 1 。每个学生会依次回答问题，编号为 0 的学生先回答，然后是编号为 1 的学生，以此类推，直到编号为 n - 1 的学生，然后老师会重复这个过程，重新从编号为 0 的学生开始回答问题。

给你一个长度为 n 且下标从 0 开始的整数数组 chalk 和一个整数 k 。一开始粉笔盒里总共有 k 支粉笔。当编号为 i 的学生回答问题时，他会消耗 chalk[i] 支粉笔。如果剩余粉笔数量 严格小于 chalk[i] ，那么学生 i 需要 补充 粉笔。

请你返回需要 补充 粉笔的学生 编号 。

遍历一遍, 求一轮消耗的总粉笔数

取模再模拟一遍即可

注意边界条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int idx=0;
        long sum=0l;
        for (int i : chalk) {
            sum+=i;
        }
        k%=sum;
        while(k>0){
            if(k>=chalk[idx]){
                k-=chalk[idx];
                idx++;
                if(idx==chalk.length){
                    idx=0;
                }
            }else{
                return idx;
            }

        }
        return idx;
    }
}

875. 爱吃香蕉的珂珂

难度中等440

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

看到本题 , 我们可以思考

t = f(k) f(x) 表示的是速度为k 的时候, 吃完香蕉需要的最短的时间

k表示速度, t表示吃完香蕉需要的时间 , 我们需要求的就是 t<=h 的时候, k的最小值

这种题目一般会有类似于下图的关系, 而我们需要求的就是左临界点 => 最小速度

值得注意的是本题的数据范围

第一次使用的r=1000 0000由于过小

导致遇到下面的样例是无法通过的, 因为 k 被限制在了 [l,r] , 因此 r应取到题目的 piles[i]的最大值

1
2
[10 0000 0000]
2

r=1000000000+1 更加保险 , 但是实际上r= 1000000000 也可以通过,

  • 只要二分的过程中可以让 m 取到1000000000就行了

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        //  t = f(k)   k表示速度, h表示吃完香蕉需要的时间  , 我们需要求的就是 t<=h 的时候, k的最小值
        int l=1,r=1000000000;
        int m;
        while(l<r){
            m=l+(r-l)/2;
            if(f(piles,m)<=h) r=m;
            else l=m+1;
        }
        return l;
    }
    int f(int[]piles,int k){
        int t=0;
        for (int i : piles) {
            t+= (i%k==0? i/k : i/k+1);
        }
        return t;
    }
}