leetcode 318. 最大单词长度乘积
给定一个字符串数组$words$,找到$length(word[i]) * length(word[j])$的最大值,并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词,返回 0。
1 | 示例 1: |
1 | 示例 2: |
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/maximum-product-of-word-lengths
思路:思路:简单水题,用一个int统计从下标0开始到当前字符出现的字符,例如abc对应的二进制位为0,1,2即$2^0+2^1+2^2$,这样就可以用与运算判断两个字符串是否有相同的字符,如果有相同字符则按位与的结果不为0,否则为0,后面根据这个条件找出最大字符串长度乘积即可。
- 时间复杂度:$O(n^2)$
- 空间复杂度:$O(n^2)$
1 | class Solution { |
leetcode-712. 两个字符串的最小ASCII删除和
给定两个字符串s1, s2,找到使两个字符串相等所需删除字符的ASCII值的最小和。
1 | 示例 1: |
1 | 示例 2: |
注意:
- 0 < s1.length, s2.length <= 1000。
- 所有字符串中的字符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 | class Solution { |
leetcode 24. 两两交换链表中的节点
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
1 | 示例 1: |
1 | 示例 2: |
提示:
- 链表中节点的数目在范围 [0, 100] 内
- 0 <= Node.val <= 100
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs
思路:简单模拟即可,将原链表拆成两部分,下标为奇数的为一部分,偶数为一部分,交叉拼接即可。
- 时间复杂度:$O(n)$
- 空间复杂度:$O(1)$
1 | class Solution { |
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 | 示例 1: |
1 | 示例 2: |
提示:
- $1 <= n <= 16$
- $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
16class 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 | 示例: |
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/arithmetic-slices
思路:双指针,简单数学题。思考过程如下:
对于一个长度大于等于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
18class 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 | 示例 1: |
1 | 示例 2: |
提示:
- 1 <= days.length <= 365
- 1 <= days[i] <= 365
- days 按顺序严格递增
- costs.length == 3
- 1 <= costs[i] <= 1000
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/minimum-cost-for-tickets
思路:状态表示: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
17class 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];
}
};