刷TMD LeetCode - 2019年

刷TMD LeetCode - 2019年


【820】单词的压缩编码

题目描述

首先要读懂题意:words[]中有metime,由于metime的后缀,所以me可以用time进行索引,那么索引中就不需要记录me了。
那么题目就转化为:找到字符串数组中所有不是其他字符串的后缀的字符串,由于初始字符串可能有相同的,所以我们需要一个去重机制Set,首先把原始字符串都加入集合,然后遍历所有字符串,判断它的所有后缀是否在Set中 —— 如果在,则说明Set中存在字符串是其他字符串的后缀,删除它。最后再计算所有Set中剩余的字符串的总长度即可。

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 minimumLengthEncoding(String[] words) {
//创建Set用于去重,并将原始字符串加入
Set<String> indexItems = new HashSet<>(Arrays.asList(words) );
for (String word : words) {
//1 <= words[i].length <= 7,也就是说后缀最多7个,可以遍历
for (int i = 1; i < word.length(); i++) {
//如果后缀存在于Set,说明有字符串是当前字符串的后缀,可以去除
String comp = word.substring(i);
if (indexItems.contains(comp) ) {
indexItems.remove(comp);
}
}
}
//最后遍历整个Set,求所有字符串(加#)的长度
int rst = 0;
for (String item : indexItems) {
rst += item.length() + 1;
}
return rst;
}
}


【1109】航班预订统计

题目描述

题意有点费解,我们可以将题目中的(i,j,k)转化为在第i站上飞机k人,在第j + 1站下飞机k
为什么是j + 1站下车呢?因为[i,j]是一个左闭右闭区间,应该理解为乘客从i站坐到了j站。

暴力法O(N^2):在一个区间内,记录每个子区间的总量,比如(1,3,10),那么我们在1 ~ 3的每个位置都记录10这样每次区间内有更改,都需要遍历整个区间,时间复杂度高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//执行用时 :1223 ms, 在所有 Java 提交中击败了17.25%的用户
//内存消耗 :65.8 MB, 在所有 Java 提交中击败了100.00%的用户
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] rst = new int[n];
for (int i = 0; i < bookings.length; i++) {
//(i,j,k):从i到j的航班每个订k张票
//航班从1到n编号
for (int j = bookings[i][0]; j <= bookings[i][1]; j++) {
rst[j - 1] += bookings[i][2];
}
}
return rst;
}
}


【对于区间问题,使用差分法求前缀和】

十分感谢LeetCode大佬的题解,茅塞顿开。

那么有没有办法不记录这么多的值、每次改变不去遍历区间呢?我们可以采用差分法 —— 每次不记录整个区间的总量,而是只记录左右端点的变化量。比如(1,3,10),那么我们就在1位置+ 10,在4位置- 10

只记录变化量,如何计算区间内的总量呢?我们可以采用计算前缀和的办法 —— i位置之前的总量,即为i位置之前所有变化量的和。我们只需要一次遍历,根据rst[i] += rst[i - 1]进行求和,就可以计算出所有子区间的总量了:

如果我们有多个区间,只需要叠加即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//执行用时 :3 ms, 在所有 Java 提交中击败了100.00%的用户
//内存消耗 :66.2 MB, 在所有 Java 提交中击败了26.26%的用户
class Solution {
//差分法
public int[] corpFlightBookings(int[][] bookings, int n) {
//由于公交下标从1开始,所以cntChanges[i]表示第i + 1站的人数变化,即差分
int[] cntChanged = new int[n];
for(int[] booking : bookings) {
//(i,j,k): i站上车k人,j + 1站下车k人
//cntChanges[i]表示第i + 1站的人数变化,(i,j,k)第i站上车k人,所以需要booking[0] - 1
cntChanged[booking[0] - 1] += booking[2];
//根据题意,坐到了最后一站的乘客不会下车,需要考虑边界条件,否则越界
if(booking[1] < n) {
cntChanged[booking[1]] -= booking[2];
}
}

//从第2站开始计算前缀和
for(int i = 1; i < n; i++) {
cntChanged[i] += cntChanged[i - 1];
}
return cntChanged;
}
}


链表

1.倒数第k结点问题——先后指针

输入一个链表,输出该链表中倒数第k个结点。

  1. 首先应该想到的应该是遍历两次链表的方法。第一次遍历求出链表的长度len,第二次遍历到倒数第k个结点,即下标为len - k的节点。
  2. 有没有只遍历一次的方法呢?答案是先后指针法——先指针先遍历,先走了k步后,后指针开始从头遍历,这样先后指针就始终保持间隔为k,当先指针到达尾部时,后指针所在位置就是倒数第k个结点。
  3. 注意考虑边界条件:①如果链表为空或者查找倒数第0个数,直接返回null;②如果链表长度小于k,也直接返回null

List

0代表头结点。

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
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/

public class Solution {

//先后指针法
public ListNode findKthToTail(ListNode head, int k) {
//链表为空,或k=0,无解
if(head == null || k == 0) {
return null;
}

ListNode ahead = head; //先指针
ListNode behind = head; //后指针

//0是头结点head,所以先指针从1开始走k-1步,先后指针相隔则为k
for(int i = 1; i < k; i++) {
if(ahead.next != null) {
ahead = ahead.next;
}else{
//如果链表长度小于k,无解
return null;
}
}

//后指针加入,先后指针保持k的间隔
while(ahead.next != null) {
ahead = ahead.next; //记得往后移动
behind = behind.next;
}

return behind;
}
}


2.反转单链表(三指针法)

输入一个无头链表,反转链表后,输出新链表的表头。

  1. 我们需要3个指针,head指针记录当前待处理的结点,next指针记录当前结点的下一个结点,pre指针记录当前结点的上一个结点。
  2. 有了3个指针后,我们可以进行反转操作。原链表为pre -> head -> next -> ...,我们如果直接反转链表成pre <- head next -> ...,那么链表就会断开,所以我们需要一个指针next来记录当前结点的下一个结点,然后才能让当前结点和上一个结点之间的链条进行反转。
  3. 反转完成后,prehead依次后移,重复步骤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
25
26
27
28
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if (head == null)
return null;
ListNode pre = null;
ListNode next = null;
while(head != null){
//记录下一个结点的位置,防止断链
next = head.next;
//反转当前结点和上一个结点
head.next = pre;
//pre、head依次后移
pre = head;
head = next;
}
return pre;

}
}


字符串匹配 —— KMP算法

题目

使用KMP算法,求字符串text中子字符串pattern出现的位置。

思路

  • 如果要求一个字符串中是否含有子字符串,首先想到的肯定是“暴力”。分别用两个指针ij指向字符串textpattern的当前位置,从头开始遍历,如果匹配则ij后移;如果不匹配那么i回溯,然后从下一个位置继续匹配pattern这种方法会存在大量的回溯,效率不高,时间复杂度是O(mn),其中mtext长度,npattern长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int bf(String text, String pattern) {
if (pattern == null || text == null) return -1;
int i = 0, j = 0; //i -> text, j -> pattern
while (i < text.length() && j < pattern.length()) {
if (text.charAt(i) == pattern.charAt(j)) { //相等(匹配)则后移
i++;
j++;
}else{ //不相等(匹配)则回溯
i = i - j + 1; //text回溯,然后后移一位
j = 0;
}
}
//如果text没有被匹配完,那么一定是中途找到了字串pattern
if (i < text.length()) return i - j;
//text被匹配完,那就没有找到
return -1;
}

  • 一个改进的方法就是**KMP算法:它的核心思想是每次如果不匹配,text字符串指针不动,只有pattern指针回溯**。

  • 那么它是怎么做到的呢?首先KMP算法计算一个next数组,记录pattern匹配串的每一个子串中,前缀等于后缀时的最长长度(不包括自身)。比如说子字符串abcabc,它的前缀等于后缀的情况中(不包括自身),最长的是abcxxxxxxabc,即3;而子字符串abc,由于不包括自身,所以它不存在前缀等于后缀的情况,即0。

  • 那么如何用代码实现呢?我们使用双指针来计算next数组 —— 初始化先指针ahead = 0、后指针behind = -1 next0

  • behind == -1,即pattern数组刚开始遍历,或是已被回溯;或是pattern[ahead] == pattern[behind],就将behindahead都后移一位,同时将next[ahead]置为匹配长度,即behind —— 由于behind == -1,所以ahead++; behind++; next[ahead] = behind; next1

  • pattern[ahead] != pattern[behind],就将behind置为next[behind] —— 由于(pattern[ahead] == pattern[1] == b) != (pattern[behind] == pattern[0] == a),所以behind == next[behind] == next[0] = -1 next2

  • 依次类推,即可求出整个next数组,时间复杂度是O(n),其中n为pattern长度

  • 接下来遍历text,如果不匹配只回溯p,即p = next[p],不再回溯t,这一步是时间复杂度是O(m),其中mtext长度 —— 所以KMP的时间复杂度是O(m + n)

代码

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
public static int kmp(String text, String pattern) {
if (text == null || pattern == null) return -1;
//计算next数组 O(n)
int[] next = new int[pattern.length()];
int behind = -1, ahead = 0;
next[0] = -1;
while (ahead < pattern.length() - 1) {
if (behind == -1
|| pattern.charAt(ahead) == pattern.charAt(behind)) {
behind++;
ahead++;
next[ahead] = behind;
}else {
behind = next[behind];
}
}
//遍历text O(m)
int t = 0, p = 0;
while (t < text.length() && p < pattern.length()) {
if (p == -1 || text.charAt(t) == pattern.charAt(p)){
t++;
p++;
}else {
p = next[p];
}
}
if (t < text.length()) return t -p;
return -1;
}


排序三元素数组:双指针法

题目

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

  • 注意:
    不能使用代码库中的排序函数来解决这道题。

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

  • 进阶:
    你能想出一个仅使用常数空间的遍历一次算法吗?

思路

  1. 数组排序,库函数有Arrays.sort()Arrays.parallelSort(),但是本题不允许使用库函数

  2. 对于数组,已经排好序找某两个元素或是按照某种逻辑排序,都可以使用双指针法

  3. 采用双指针,p0指针前面的元素是0,p2指针后面的元素是2,p0~p2中间的元素是1;此外,还要引入一个curr指针,指向的是当前的元素,p0~curr是元素1,curr~p2是尚未遍历元素

  4. 进行遍历,跳出循环的条件是p2 < curr

  5. nums[curr]=0时:nums[curr]nums[p0]交换位置,p0++;curr++;nums[curr]=1时:curr++;即可(元素0移到p0前,元素2移到p2后,剩下的自然就是1,所以元素1不处理,只将当前指针后移);nums[curr]=2时:nums[curr]nums[p2]交换位置,p2--;当前元素指针不能后移,因为换过来的p2位置元素可能是0/1,需要进行判断

  6. 交换两个元素,不引入额外空间,容易想到:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    a = a + b;
    b = a - b;
    a = a - b;
    //或
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    //但是要注意的是,a和b不能是同一对象
    //在此题中,nums[curr]和nums[p2]可能会指向同一对象,所以不能用这种方法,只能引入额外内存

  7. 所以交换两个元素,可以考虑引入临时变量,或是直接使用Collections.swap(List list, int i, int j)——注意需要配合Arrays.asList()Collection.toArray()使用。

代码

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
class Solution {
public void sortColors(int[] nums) {
// Arrays.sort(nums); 1ms 36mb
// Arrays.parallelSort(nums); 1ms 35.6mb

//双(三)指针法,p0前面的都是0,p2后面的都是2
//中间的(p0到curr)自然就是1
// 1ms 35.3mb
int p0 = 0, curr = 0; //curr是当前元素,curr到p2是待定元素
int p2 = nums.length - 1;
while (curr <= p2) { //结束条件,p2 < curr
if (nums[curr] == 0) {
//p0和curr交换位置
int temp = nums[p0];
nums[p0] = nums[curr];
nums[curr] = temp;
curr++;
p0++;
}else if (nums[curr] == 1) {
curr++; // (p0,curr)是元素1
}else{
//p2与curr交换位置
int temp = nums[p2];
nums[p2] = nums[curr];
nums[curr] = temp;
p2--;
//注意curr不能++,因为无法确定p2换过来的元素是0还是1
}
}
}
}


求无重复字符的最长子串:滑动窗口法

题目

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

  • 示例1:
    输入:"pwwkew"
    输出:3
    解释:wke,3

  • 示例2:
    输入:"dvdf"
    输出:3
    解释:vdf,3

思路

  1. 首先是暴力法,首先找出所有字符串中可能出现的子串(O(N^2)),然后判断子串中是否存在重复字符(O(N),所以总时间复杂度是O(N^3),不可取:

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
public int lengthOfLongestSubstring(String s){
int len = s.length();
int max = 0; //默认0
//求所有子字符串,只需要确定一个区间 [i,j] 即可
for(int i = 0; i < len; i++){
for(int j = i + 1; j < len; j++){
//判断子串是否存在重复字符,存在则过滤
//否则更新最大值
if(allUnique(s, i, j)) max = Math.max(max, j - i);
}
}
}

//@param: String s,字符串
//@param: int start, 子串开始处
//@param: int end, 子串结束处
//@return: boolean,子串是否无重复字符
public boolean allUnique(String s, int start, int end){
Set<Character> set = new HashSet<>(); //查找:O(1)
for(int i = start; i < end; i++){
Character c = s.charAt(i);
if(set.contains(c)) return false;
set.add(c);
}
return true;
}

  1. 因此我们要进行优化 —— 想一下暴力法中对于所有子串都会判断是否存在重复字符,其实是有很多重复的情况的,比如:如果已知范围为[i,j]的子串中无重复字符,那么判断范围为[i,j+1]的子串时,只需要判断j+1位置的字符在不在[i,j]子串中即可
  2. 如果是直接遍历子串判断字符存不存在,那么最终时间复杂度会到达O(N^2),我们可以引入HashSet,以空间换时间,将字符的查找控制在O(1),从而获得O(N)的算法

滑动窗口

  • 滑动窗口是数组/字符串问题中常用的抽象概念,窗口是索引范围为[i, j)的元素集合
  • 滑动窗口则是可以将两个边界向某个方向“滑动”的窗口

比如我们将[i, j)向右滑动一个元素,则窗口变为[i + 1, j + 1)

  • 此题中,我们采用一个[i, j)的滑动窗口(刚开始i == j,同为0),窗口大小j - i就是当前最大的无重复字符子串长度
  • 采用一个HashSet存储窗口[i,j)之间的元素,即子串中存在的字符,可以保证不重复,而且查找为O(1)
  • 每次j索引位置的元素如果不在HashSet中则加入,然后j向右滑动
  • 如果j索引位置元素在HashSet中,那么则移除i位置的元素,同时i右移

重复这一步可以保证j位置的元素最终肯定会被移出HashSet中,这时候j就又能够向右滑动了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//时间复杂度:O(N)
public int lengthOfLongestSubstring(String s){
Set<Character> set = new HashSet<>();
int i = 0, j = 0, max = 0;
int len = s.length();
//窗口未到底,就一直循环
while(i < n && j < n) {
if(!set.contains(s.charAt(j))){ //[i, j - 1)不包含j元素
set.add(s.charAt(j++));
//等价于:
//set.add(s.charAt(j));
//j = j + 1;
max = Math.max(max, j - i);
}else{ //[i, j - 1)包含j元素
set.remove(s.charAt(i++));
//等价于:
//set.remove(s.charAt(i));
//i = i + 1;
}
}
return max;
}


二分查找中的小技巧

  1. 如果leftright很大的话,mid = (left + right) / 2可能会越界
  2. mid = left + (right - left) / 2越界的可能性会大大降低
-------------本文结束感谢您的阅读-------------

本文标题:刷TMD LeetCode - 2019年

文章作者:DragonBaby308

发布时间:2020年01月18日 - 00:49

最后更新:2020年02月01日 - 14:55

原始链接:http://www.dragonbaby308.com/fxxk-leetcode-1/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

急事可以使用右下角的DaoVoice,我绑定了微信会立即回复,否则还是推荐Valine留言喔( ఠൠఠ )ノ
0%