leetcode 318. 最大单词长度乘积

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

示例 1:

输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "xtfn"。

示例 2:

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

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

来源：力扣（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)$

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:

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

示例 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"，我们会得到 433 或 417 的结果，比答案更大。

注意:

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)$

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：


输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

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

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs

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

时间复杂度：$O(n)$
空间复杂度：$O(1)$

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：

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

示例 2：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/circular-permutation-in-binary-representation

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

时间复杂度：$O(n)$

空间复杂度：$O(n)$

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 中所有为等差数组的子数组个数。

示例:

A = [1, 2, 3, 4]

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

来源：力扣（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)$

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：

输入：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，并完成了你计划的每一天旅行。

示例 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 <= 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)$

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];
    }
};