T1 5780. 删除一个元素使数组严格递增

题目

给你一个下标从 0 开始的整数数组 nums ，如果 恰好 删除 一个 元素后，数组 严格递增 ，那么请你返回 true ，否则返回 false 。如果数组本身已经是严格递增的，请你也返回 true 。

数组 nums 是 严格递增 的定义为：对于任意下标的 1 <= i < nums.length 都满足 nums[i - 1] < nums[i] 。

示例 1：
输入：nums = [1,2,10,5,7]
输出：true
解释：从 nums 中删除下标 2 处的 10 ，得到 [1,2,5,7] 。
[1,2,5,7] 是严格递增的，所以返回 true 。

示例 2：
输入：nums = [2,3,1,2]
输出：false
解释：
[3,1,2] 是删除下标 0 处元素后得到的结果。
[2,1,2] 是删除下标 1 处元素后得到的结果。
[2,3,2] 是删除下标 2 处元素后得到的结果。
[2,3,1] 是删除下标 3 处元素后得到的结果。
没有任何结果数组是严格递增的，所以返回 false 。

示例 3：
输入：nums = [1,1,1]
输出：false
解释：删除任意元素后的结果都是 [1,1] 。
[1,1] 不是严格递增的，所以返回 false 。

示例 4：
输入：nums = [1,2,3]
输出：true
解释：[1,2,3] 已经是严格递增的，所以返回 true 。

提示：
2 <= nums.length <= 1000
1 <= nums[i] <= 1000

题解

这复杂度操作空间太大了，leetcode周赛第一题经典有手就行，别多想（
每次去掉一个数，强行遍历即可

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 boolean canBeIncreasing(int[] nums) {
        int len = nums.length;
        for(int i = 0; i < len; i++){
            Integer prev = null;
            boolean flag = true;
            for(int j = 0; j < len; j++){
                if(j == i) continue;
                if(prev == null){
                    prev = nums[j];
                    continue;
                }
                if(prev >= nums[j]) {
                    flag = false;
                    break;
                }
                else prev = nums[j];
            }
            if(flag) return true;
        }
        return false;
    }
}

T2 5781. 删除一个字符串中所有出现的给定子字符串

题目

给你两个字符串 s 和 part ，请你对 s 反复执行以下操作直到 所有 子字符串 part 都被删除：

  • 找到 s 中 最左边 的子字符串 part ，并将它从 s 中删除。
    请你返回从 s 中删除所有 part 子字符串以后得到的剩余字符串。
    一个 子字符串 是一个字符串中连续的字符序列。

示例 1：
输入：s = “daabcbaabcbc”, part = “abc”
输出：“dab”
解释：以下操作按顺序执行：
s = “daabcbaabcbc” ，删除下标从 2 开始的 “abc” ，得到 s = “dabaabcbc” 。
s = “dabaabcbc” ，删除下标从 4 开始的 “abc” ，得到 s = “dababc” 。
s = “dababc” ，删除下标从 3 开始的 “abc” ，得到 s = “dab” 。
此时 s 中不再含有子字符串 “abc” 。

示例 2：
输入：s = “axxxxyyyyb”, part = “xy”
输出：“ab”
解释：以下操作按顺序执行：
s = “axxxxyyyyb” ，删除下标从 4 开始的 “xy” ，得到 s = “axxxyyyb” 。
s = “axxxyyyb” ，删除下标从 3 开始的 “xy” ，得到 s = “axxyyb” 。
s = “axxyyb” ，删除下标从 2 开始的 “xy” ，得到 s = “axyb” 。
s = “axyb” ，删除下标从 1 开始的 “xy” ，得到 s = “ab” 。
此时 s 中不再含有子字符串 “xy” 。
 
提示：
1 <= s.length <= 1000
1 <= part.length <= 1000
s​​​​​​ 和 part 只包小写英文字母。

题解

indexOf()方法好啊，虽然indexOf也是通过自左向右遍历暴力实现的（但是可以提升手速

1
2
3
4
5
6
7
8
9
10
class Solution {
    public String removeOccurrences(String s, String part) {
        int len = part.length();
        while(s.indexOf(part) != -1){
            int cur = s.indexOf(part);
            s = s.substring(0, cur) + s.substring(cur + len, s.length());
        }
        return s;
    }
}

T3 5782. 最大子序列交替和

题目

一个下标从 0 开始的数组的 交替和 定义为 偶数 下标处元素之 和 减去 奇数 下标处元素之 和 。

比方说，数组 [4,2,5,3] 的交替和为 (4 + 5) - (2 + 3) = 4 。
给你一个数组 nums ，请你返回 nums 中任意子序列的 最大交替和 （子序列的下标 重新 从 0 开始编号）。

一个数组的 子序列 是从原数组中删除一些元素后（也可能一个也不删除）剩余元素不改变顺序组成的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的一个子序列（加粗元素），但是 [2,4,2] 不是。

示例 1：
输入：nums = [4,2,5,3]
输出：7
解释：最优子序列为 [4,2,5] ，交替和为 (4 + 5) - 2 = 7 。

示例 2：
输入：nums = [5,6,7,8]
输出：8
解释：最优子序列为 [8] ，交替和为 8 。

示例 3：
输入：nums = [6,2,1,2,4,5]
输出：10
解释：最优子序列为 [6,1,5] ，交替和为 (6 + 5) - 1 = 10 。
 
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

题解

数据量大小10510^5首先O(n2)O(n^2)暴力必然会导致TLE
这道题是比较典型的状态转换dp题，我们发现计算交替和的时候，长度为奇数的子数组状态 可以和 长度为偶数的子数组状态 可以互相转换
我们定义：

  • 创建dp1数组，其中dp1[i]表示nums数组0 ~ i中可以生成的奇数长度子数组的最大交替和
  • 同理，dp2[i]表示nums数组0 ~ i中可以生成的偶数长度子数组的最大交替和
    不难发现，有如下关系，动态规划方程如下：
  • dp1[i]=Math.max(dp1[i−1],dp2[i−1]+nums[i])dp1[i] = Math.max(dp1[i - 1], dp2[i - 1] + nums[i])
  • dp2[i]=Math.max(dp2[i−1],dp1[i−1]−nums[i])dp2[i] = Math.max(dp2[i - 1], dp1[i - 1] - nums[i])
    注意到，nums.length和nums[i]在最差情况下都可以到达10510^5的大小，对于int来说存在溢出的风险，可以暂时使用long进行替代存储

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public long maxAlternatingSum(int[] nums) {
        int len = nums.length;
        long[] dp1 = new long[len];
        long[] dp2 = new long[len];
        dp1[0] = (long)nums[0];
        for(int i = 1; i < len; i++){
            dp1[i] = Math.max((long)dp1[i - 1], (long)dp2[i - 1] + (long)nums[i]);
            dp2[i] = Math.max((long)dp2[i - 1], (long)dp1[i - 1] - (long)nums[i]);
        }
        return dp1[len - 1] > dp2[len - 1] ? dp1[len - 1]: dp2[len - 1];
    }
}

T4 5783. 设计电影租借系统

题目

你有一个电影租借公司和 n 个电影商店。你想要实现一个电影租借系统，它支持查询、预订和返还电影的操作。同时系统还能生成一份当前被借出电影的报告。

所有电影用二维整数数组 entries 表示，其中 entries[i] = [shopi, moviei, pricei] 表示商店 shopi 有一份电影 moviei 的拷贝，租借价格为 pricei 。每个商店有 至多一份 编号为 moviei 的电影拷贝。

系统需要支持以下操作：

  • Search 找到拥有指定电影且 未借出 的商店中 最便宜的 5 个 。商店需要按照 价格 升序排序，如果价格相同，则 shopi 较小 的商店排在前面。如果查询结果少于 5 个商店，则将它们全部返回。如果查询结果没有任何商店，则返回空列表。
  • Rent 从指定商店借出指定电影，题目保证指定电影在指定商店 未借出 。
  • Drop 在指定商店返还 之前已借出 的指定电影。
  • Report 返回 最便宜的 5 部已借出电影 （可能有重复的电影 ID），将结果用二维列表 res 返回，其中 res[j] = [shopj, moviej] 表示第 j 便宜的已借出电影是从商店 shopj 借出的电影 moviej 。res 中的电影需要按 价格 升序排序；如果价格相同，则 shopj 较小 的排在前面；如果仍然相同，则 moviej 较小 的排在前面。如果当前借出的电影小于 5 部，则将它们全部返回。如果当前没有借出电影，则返回一个空的列表。

请你实现 MovieRentingSystem 类：

  • MovieRentingSystem(int n, int[][] entries) 将 MovieRentingSystem 对象用 n 个商店和 entries 表示的电影列表初始化。
  • List<Integer> search(int movie) 如上所述，返回 未借出 指定 movie 的商店列表。
  • void rent(int shop, int movie) 从指定商店 shop 借出指定电影 movie 。
  • void drop(int shop, int movie) 在指定商店 shop 返还之前借出的电影 movie 。
  • List<List<Integer>> report() 如上所述，返回最便宜的 **已借出 **电影列表。
    注意 测试数据保证 rent 操作中指定商店拥有 未借出 的指定电影，且 drop 操作指定的商店 之前已借出 指定电影。

示例 1：
输入：
["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]
[[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]]
输出：
[null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]
解释：
MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);
movieRentingSystem.search(1); // 返回 [1, 0, 2] ，商店 1，0 和 2 有未借出的 ID 为 1 的电影。商店 1 最便宜，商店 0 和 2 价格相同，所以按商店编号排序。
movieRentingSystem.rent(0, 1); // 从商店 0 借出电影 1 。现在商店 0 未借出电影编号为 [2,3] 。
movieRentingSystem.rent(1, 2); // 从商店 1 借出电影 2 。现在商店 1 未借出的电影编号为 [1] 。
movieRentingSystem.report(); // 返回 [[0, 1], [1, 2]] 。商店 0 借出的电影 1 最便宜，然后是商店 1 借出的电影 2 。
movieRentingSystem.drop(1, 2); // 在商店 1 返还电影 2 。现在商店 1 未借出的电影编号为 [1,2] 。
movieRentingSystem.search(2); // 返回 [0, 1] 。商店 0 和 1 有未借出的 ID 为 2 的电影。商店 0 最便宜，然后是商店 1 。

提示：
1 <= n <= 3 * 10^5
1 <= entries.length <= 10^5
0 <= shopi < n
1 <= moviei, pricei <= 10^4
每个商店 至多 有一份电影 moviei 的拷贝。
search，rent，drop 和 report 的调用 总共 不超过 10^5 次。

题解

大型阅读理解现场，读得死去活来，题目不难，关键是自己犯了点错误
代码如下：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class MovieRentingSystem {
    Map<Integer,PriorityQueue<int[]>>movies=new HashMap<>();
    Set<int[]>set=new HashSet<>();
    PriorityQueue<int[]>jie=new PriorityQueue<>(new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            if(o1[2]!=o2[2])return o1[2]-o2[2];
            else if(o1[1]!=o2[1])return o1[1]-o2[1];
            else return o1[0]-o2[0];
        }
    });
    Map<Integer,int[]>[]shops;
    public MovieRentingSystem(int n, int[][] entries) {
        shops=new Map[n];
        for(int i=0;i<n;i++)
            shops[i]=new HashMap();
        for(int i=0;i<entries.length;i++)
        {
            int[]tem=entries[i];
            if(movies.get(tem[1])==null)movies.put(tem[1],new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if(o1[2]!=o2[2])
                        return o1[2]-o2[2];
                    else return o1[0]-o2[0];
                }
            }));
            movies.get(tem[1]).add(tem);
            shops[tem[0]].put(tem[1],tem);
        }
    }
    public List<Integer> search(int movie) {
        int num=5;
        List<Integer>list=new ArrayList<>();
        if(movies.get(movie)==null)return list;
        PriorityQueue<int[]>tem=(movies.get(movie));
        Stack<int[]>stack=new Stack<>();
        while (!tem.isEmpty()&&num>0)
        {
            int[]arr=tem.poll();
            stack.add(arr);
            if(!set.contains(arr)) {
                list.add(arr[0]);
                num--;
            }
        }

        while (!stack.isEmpty())
            tem.add(stack.pop());
        return list;
    }

    public void rent(int shop, int movie) {
        int[]tem=shops[shop].get(movie);
        set.add(tem);
        jie.add(tem);
    }

    public void drop(int shop, int movie) {
        int[]tem=shops[shop].get(movie);
        set.remove(tem);
        jie.remove(tem);
    }

    public List<List<Integer>> report() {
        int num=5;
        PriorityQueue<int[]>tem=jie;
        List<List<Integer>>list=new ArrayList<>();
        Stack<int[]>stack=new Stack<>();
        while (!tem.isEmpty()&&num>0)
        {
            int[]arr=tem.poll();
            stack.add(arr);
                List<Integer> ll = new ArrayList<>();
                ll.add(arr[0]);
                ll.add(arr[1]);
                list.add(ll);
                num--;
        }
        while (!stack.isEmpty())
            jie.add(stack.pop());
        return list;
    }
}

我们都知道Java有一个常量池，例如Integer整型常量池，有一个特殊的范围-128 ~ 127，当我们创建在范围内的Integer对象时，Java会自动将指针指向常量池已有对象，这时如果我们用==或者!=判断时是没有问题的，但是当我们创建的对象超出了范围，就会自行创建相应的新对象，该对象拥有不同的指针地址，即使他们的对象值相同，==运算时也不会相等，因为地址不同，不是同一个对象，必须使用equals()方法来解决问题
这道题目中，Map<Integer, Integer>取出的value是Integer类型的，直接写入lambda表达式时应当注意，不能使用==