0%

每日leetcode 318. 最大单词长度乘积 712. 两个字符串的最小ACSCII删除和 24. 两两交换链表中的节点 1238. 循环码排列 413. 等差数列划分 983. 最低票价

leetcode 318. 最大单词长度乘积

给定一个字符串数组$words$,找到$length(word[i]) * length(word[j])$的最大值,并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词,返回 0。

1
2
3
4
5
示例 1:

输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "xtfn"
1
2
3
4
5
6
7
8
9
10
示例 2:

输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4
解释: 这两个单词为 "ab", "cd"
示例 3:

输入: ["a","aa","aaa","aaaa"]
输出: 0
解释: 不存在这样的两个单词。

思路:思路:简单水题,用一个int统计从下标0开始到当前字符出现的字符,例如abc对应的二进制位为0,1,2即$2^0+2^1+2^2$,这样就可以用与运算判断两个字符串是否有相同的字符,如果有相同字符则按位与的结果不为0,否则为0,后面根据这个条件找出最大字符串长度乘积即可。

  • 时间复杂度:$O(n^2)$
  • 空间复杂度:$O(n^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:
int maxProduct(vector<string>& words) {
int n = words.size();
vector<vector<int>> nums;
for(auto &c:words){
int v=0,t = c.size();
for(auto &w:c){
int a = w-'a';
v|=1<<a;
}
nums.push_back({v,t});
}
int res = 0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if((nums[i][0] & nums[j][0]) == 0){
res = max(res,nums[i][1] * nums[j][1]);
}
}
}
return res;
}
};

leetcode-712. 两个字符串的最小ASCII删除和

给定两个字符串s1, s2,找到使两个字符串相等所需删除字符的ASCII值的最小和。

1
2
3
4
5
6
7
示例 1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
"eat" 中删除 "t" 并将 116 加入总和。
结束时,两个字符串相等,115 + 116 = 231 就是符合条件的最小和。
1
2
3
4
5
6
7
8
示例 2:

输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"
100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e"101[e] 加入总和。
结束时,两个字符串都等于 "let",结果即为 100+101+101+101 = 403
如果改为将两个字符串转换为 "lee""eet",我们会得到 433417 的结果,比答案更大。

注意:

  1. 0 < s1.length, s2.length <= 1000。
  2. 所有字符串中的字符ASCII值在[97, 122]之间。
  • 来源:力扣(LeetCode)

  • 链接:https://leetcode-cn.com/problems/minimum-ascii-delete-sum-for-two-strings
    思路: 这题与编辑距离差不多,状态表示:$f[i][j]$表示使s的前i个字符和t的前j个字符相等所需删除字符的ASCII值最小和,显然
    如果$s[i]==t[j]$
    则$f[i][j]=f[i-1][j-1]$
    否则,
    $f[i][j] = min(f[i-1][j] + s[i-1] - ‘a’, f[i][j-1] + t[j-1] - ‘a’) + 97$,
    即,使s的前i-1个字符和t的前j个字符相等所需删除字符的ASCII值最小和与使s的前i个字符和t的前j-1个字符相等所需删除字符的ASCII值最小和的最小值,前者需要删除s[i],后者删除t[j]。
    初始状态为$f[i][0]$和$f[0][j]$。

  • 时间复杂度:$O(n*m)$

  • 空间复杂度:$O(n*m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int minimumDeleteSum(string s, string t) {
int n = s.size(), m = t.size(), f[n+1][m+1];
memset(f,0,sizeof f);
for(int i=1;i<=n;i++) f[i][0] += f[i-1][0] + s[i-1] - 'a' + 97;
for(int i=1;i<=m;i++) f[0][i] += f[0][i-1] + t[i-1] - 'a' + 97;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i-1] == t[j-1]) f[i][j] = f[i-1][j-1];
else f[i][j] = min(f[i-1][j] + s[i-1] - 'a', f[i][j-1] + t[j-1] - 'a') + 97;
}
}
return f[n][m];
}
};

leetcode 24. 两两交换链表中的节点

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

1
2
3
4
5
示例 1


输入:head = [1,2,3,4]
输出:[2,1,4,3]
1
2
3
4
5
6
7
8
示例 2

输入:head = []
输出:[]
示例 3

输入:head = [1]
输出:[1]

提示:

  1. 链表中节点的数目在范围 [0, 100] 内
  2. 0 <= Node.val <= 100

思路:简单模拟即可,将原链表拆成两部分,下标为奇数的为一部分,偶数为一部分,交叉拼接即可。

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(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
25
26
27
28
29
30
31
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *oddhead=new ListNode(-1), *evenhead=new ListNode(-1);
ListNode *r=head, *s=oddhead, *t=evenhead;
int cnt = 1;
auto p = head,sr = p, tr = p;
while(p){
r = p->next;
p->next = nullptr;
if(cnt & 1) s->next = p, s = s->next;
else t->next = p, t = t->next;
p = r;
cnt++;
}
s = oddhead->next, t = evenhead->next;
ListNode *res= new ListNode(-1);
p = res;
while(s && t){
sr = s->next, tr = t->next;
s->next = nullptr, t->next = nullptr;
p->next = t;
p = p->next;
p->next = s;
p = p->next;
s = sr, t = tr;
}
p->next = s;
return res->next;
}
};

leetcode 1238. 循环码排列

给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,…,2^n-1) 的排列 p,并且满足:

$p[0] = start$
$p[i] 和 p[i+1]$的二进制表示形式只有一位不同
$p[0] 和 p[2^n -1]$的二进制表示形式也只有一位不同

1
2
3
4
5
6
示例 1

输入:n = 2, start = 3
输出:[3,2,0,1]
解释:这个排列的二进制表示是 (11,10,00,01)
所有的相邻元素都有一位是不同的,另一个有效的排列是 [3,1,0,2]
1
2
3
4
5
示例 2

输出:n = 3, start = 2
输出:[2,6,7,5,4,0,1,3]
解释:这个排列的二进制表示是 (010,110,111,101,100,000,001,011)

提示:

  1. $1 <= n <= 16$
  2. $0 <= start < 2^n$

思路:格雷码变种,将0开头的格雷码编码平移到start开头即可。

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
    vector<int> circularPermutation(int n, int s) {
    vector<int> res;
    res.push_back(0);
    int start=0,k=0;
    for(int i=1;i<(1<<n);i++){
    if(i & 1) res.push_back(res[i-1] ^ 1);
    else res.push_back(res[i-1] ^ 2*(res[i-1] & -res[i-1]));
    if(res[i] == s) start = i;
    }
    vector<int> ans;
    while(k<(1<<n)) ans.push_back(res[start++ % (1<<n)]),k++;
    return ans;
    }
    };

leetcode 413. 等差数列划分

如果一个数列至少有三个元素,并且任意两个相邻元素之差相同,则称该数列为等差数列。
例如,以下数列为等差数列:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。

1, 1, 2, 5, 7

数组 A 包含 N 个数,且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q),P 与 Q 是整数且满足 0<=P<Q<N 。

如果满足以下条件,则称子数组(P, Q)为等差数组:

元素 A[P], A[p + 1], …, A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

函数要返回数组 A 中所有为等差数组的子数组个数。

1
2
3
4
5
示例:

A = [1, 2, 3, 4]

返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

思路:双指针,简单数学题。思考过程如下:
对于一个长度大于等于3的等差数列,有多少个子数组(长度大于等于3)也是等差数列呢?以1,2,3,4,5举例:
对于1开头有3个,分别是1,2,3; 1,2,3,4; 1,2,3,4,5;
对于2开头有2个,分别是2,3,4; 2,3,4,5;
对于3开头有1个,分别是3,4,5;
所以一个长度为n(n>=3)的等差数列的长度大于等于3的子数组有(n-1)*(n-2)/2个。

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
    public:
    int numberOfArithmeticSlices(vector<int>& A) {
    int n = A.size(), i = 0;
    int res = 0;
    while(i<n){
    int j = i+1;
    if(j >= n) break;
    int diff = A[j] - A[i];
    while(j<n && A[j] - A[j-1] == diff) j++;
    if(j-i>=3){
    res+=(j-i-1)*(j-i-2)/2;
    }
    i = j-1;
    }
    return res;
    }
    };

leetcode 983. 最低票价

在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有三种不同的销售方式:

一张为期一天的通行证售价为 costs[0] 美元;
一张为期七天的通行证售价为 costs[1] 美元;
一张为期三十天的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。 例如,如果我们在第 2 天获得一张为期 7 天的通行证,那么我们可以连着旅行 7 天:第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

1
2
3
4
5
6
7
8
9
10
示例 1

输入:days = [1,4,6,7,8,20], costs = [2,7,15]
输出:11
解释:
例如,这里有一种购买通行证的方法,可以让你完成你的旅行计划:
在第 1 天,你花了 costs[0] = $2 买了一张为期 1 天的通行证,它将在第 1 天生效。
在第 3 天,你花了 costs[1] = $7 买了一张为期 7 天的通行证,它将在第 3, 4, ..., 9 天生效。
在第 20 天,你花了 costs[0] = $2 买了一张为期 1 天的通行证,它将在第 20 天生效。
你总共花了 $11,并完成了你计划的每一天旅行。
1
2
3
4
5
6
7
8
9
示例 2

输入:days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出:17
解释:
例如,这里有一种购买通行证的方法,可以让你完成你的旅行计划:
在第 1 天,你花了 costs[2] = $15 买了一张为期 30 天的通行证,它将在第 1, 2, ..., 30 天生效。
在第 31 天,你花了 costs[0] = $2 买了一张为期 1 天的通行证,它将在第 31 天生效。
你总共花了 $17,并完成了你计划的每一天旅行。

提示:

  1. 1 <= days.length <= 365
  2. 1 <= days[i] <= 365
  3. days 按顺序严格递增
  4. costs.length == 3
  5. 1 <= costs[i] <= 1000

思路:状态表示:f[i]表示完成前i个旅程所需要的最低票价,为了方便,下标从1开始。状态很好想,对于第i个旅程,可由前面与他间隔不超过30天的旅途买票过来。即$f[i] = min(f[i],f[j-1] + cost)$,cost根据间隔的天数确定。

  • 时间复杂度:$O(30*n)$
  • 空间复杂度:$O(n)$
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
    int n = days.size(), mincost = min(costs[0],min(costs[1],costs[2]));
    int f[n+1];
    f[0] = 0;
    for(int i=1;i<=n;i++){
    f[i] = f[i-1] + mincost;
    for(int j=i-1;j>=1;j--){
    if(days[i-1] - days[j-1] < 7) f[i] = min(f[i],f[j-1] + costs[1]);
    if(days[i-1] - days[j-1] < 30) f[i] = min(f[i],f[j-1] + costs[2]);
    if(days[i-1] - days[j-1] >= 30) break;
    }
    }
    return f[n];
    }
    };