The string APPAPT contains two PAT's as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.

Now given any string, you are supposed to tell the number of PAT's contained in the string.

Input Specification:
Each input file contains one test case. For each case, there is only one line giving a string of no more than 10
5
characters containing only P, A, or T.

Output Specification:
For each test case, print in one line the number of PAT's contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.

Sample Input:
APPAPT
Sample Output:
2

方法DP

dp0 表示i之前有多少个P
dp1 表示i之前有多少个组成的PA
dp2 表示i之前有多少个组成的PAT

初始状态:
如果s[0] == 'P' 则 dp0 = 1 否则 dp0 = 0
dp1 = 0
dp2 = 0

转移方程:
如果s[i] == 'P' 则 dp0 = dp0 + 1 否则 dp0 = dp0
如果s[i] == 'A' 则 dp1 = dp0 + dp1 否则 dp1 = dp1
如果s[i] == 'T' 则 dp2 = dp1 + dp2 否则 dp2 = dp2

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    if(s.length() == 0) {
        cout << 0 << endl;
        return 0;
    }

    long long dp[3][s.length()];
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < s.length(); j++){
            dp[i][j] = 0;
        }
    }

    if(s[0] == 'P'){
        dp[0][0] = 1;
    }

    for(int i = 1; i < s.length(); i++){
        dp[0][i] = dp[0][i-1];
        dp[1][i] = dp[1][i-1];
        dp[2][i] = dp[2][i-1];
        if(s[i] == 'P'){
            dp[0][i] += 1;
        } else if(s[i] == 'A') {
            dp[1][i] += dp[0][i];
        } else if(s[i] == 'T'){
            dp[2][i] += dp[1][i];
        }
        dp[0][i] = dp[0][i] % 1000000007;
        dp[1][i] = dp[1][i] % 1000000007;
        dp[2][i] = dp[2][i] % 1000000007;
    }
    cout << dp[2][s.length()-1];
    return 0;
}

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

 

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
示例 2:

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

输入:nums = [0]
输出:[]
 

提示:

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

双指针法

我们可以通过排序将无序数组转为有序数组之后外层循环for表示三数之和的第三个元素nums[k],而剩下的两个数在0~k-1中找显然就变成了两数之和的问题。
两数之和可以用双指针,哈希,二分法都可以者利用的是双指针,而双指针必须将数组进行排序。

另外因为我们取的元素k是三数之和的第三个元素,可能会存在nums[k]的下一个和当前的值是相同的,此时的结果有可能是相等的,所以我们只能保留一个结果,显然若nums[k] == nums[k+1],而三数之和nums[i], nums[j], nums[k] 与 nums[i], nums[j], nums[k+1]是相同的,但是题目要求是只保留不同的,所以我们要判断若nums[k] == nums[k+1]则要让k++,直到nums[k] != nums[k+1]
证明:nums = [0, 0, 0, 0]
此时若k = 2,i = 0, j = 1,此时nums[i]+nums[j]+nums[k] = 0
而k=3,i=0,j = 1 nums[i]+nums[j]+nums[k] = 0 也为0,此时存在重复结果集应只保留一个,问题就在于当nums[k] = a时,若nums[k+1] = nums[k] = a,则存在nums[i], nums[j], nums[k] 与 nums[i], nums[j], nums[k+1]这两个结果集,因此当nums[k] == nums[k+1]时则k++直到nums[k] != nums[k+1] 只保留一个相同的nums[k]值。

为什么是nums[k] == nums[k+1]而不是nums[k-1] == nums[k],前者是让k为相同值中的最后一个,而后者是保证k为相同值的第一个,比如[-2, 0, 1, 1, 2] 前者算法这回取到k = 3, 后者取的是k = 2,而显然k = 3 时有 i = 0, j = 2 存在nums[i]+nums[j]+nums[k] == 0,而k = 2时无解,问题就在于我们的k取的是三数之和的第三个元素,所以当nums[k]存在同值时我们要让k的下标尽可能大这样子可以保证0~k-1 中允许有重值nums[k],而若nums[k]取下标尽可能小的话则会出现0~k-1中无重值nums[k]在某些特例下会有问题如上文中的[-2, 0, 1, 1, 2]

而在二数之和中若nums[i], nums[j], nums[k]为其中一个解,则要继续往下遍历时要进行i++,j-- 直到nums[i] != nums[i-1] 和 nums[j] != nums[j+1] 因为若nums[i] == nums[i-1],则nums[i], nums[j], nums[k] 与 nums[i-1], nums[j], nums[k] 是相同的解,会出现重复解,所以i++,j--必须循环到其不为相同值的情况下。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        set<int> sets;
        if(nums.size() <= 2){
            return res;
        }
        sort(nums.begin(), nums.end());
        for(int k = 2; k < nums.size(); k++){
        if(k < nums.size() - 1 && nums[k] == nums[k+1]){
            continue;
        }
        int i = 0, j = k-1;
        while(i < j){
            int v = nums[i] + nums[k] + nums[j];
            if(v < 0){
                i++;
            } else if(v > 0){
                j--;
            } else {
                vector<int> tmp = {nums[i], nums[k], nums[j]};
                res.push_back(tmp);
                do {
                    i++;
                } while(i < j && nums[i] == nums[i-1]);
                do {
                    j--;
                } while(i < j && nums[j] == nums[j+1]);
            }
        }
    }
        return res;
    }
};

整数数组 nums 按升序排列,数组中的值 互不相同 。

在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。

 

示例 1:

输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
示例 2:

输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:

输入:nums = [1], target = 0
输出:-1
 

提示:

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
 

进阶:你可以设计一个时间复杂度为 O(log n) 的解决方案吗?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

方法1 单次二分

每一次二分得到的mid,start ~ mid, 以及 mid+1~end 肯定有一个是有序数组,一个是无序数组,则我们只需要对有序数组的区间进行判断target是否落在此区间,若落在此区间则进入继续二分,否则肯定落在另一个半区以此类推。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size() - 1;
        while(start <= end) {
            int mid = (start + end) / 2;
            if(nums[mid] == target){
                return mid;
            }
            // 前半段顺序
            if(nums[mid] >= nums[start]){
                if(nums[mid] > target && target >= nums[start]){
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if(target > nums[mid] && target <= nums[end]){
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
};

方法2 二次二分

第一次先二分找到翻转的下标k,然后把数组划分为0~k, k+1~nums.size()-1,只需要判断数组落在哪个区间用二分即可。
这里要注意findK的判断条件
不能用start=mid+1, end = mid-1 因为有可能mid就是边界,若+1,-1则会把正确结果给丢失了,我们的目的是逼近正确答案,
其次if(nums[start] < nums[mid]) 这里要用 < 不能用 <= 因为若end-start=1,mid = (start+end)/2=start+(end-start)/2;因为end-start=1,而1/2因为向下取整所以永远为0,所以mid=start。
因为start == mid,所以若用 <= 的话则会出现nums[start] <= nums[mid]为真则start = mid=0,陷入死循环。
若采用<,则nums[start] < nums[mid] 为假则end=mid=start,此时start < end 为假,所以退出循环。
这两种情况下start均为正确的下标。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int k = findK(nums);
        if(target >= nums[0] && target <= nums[k]){
            return find(nums, 0, k, target);
        } else {
            return find(nums, k+1, nums.size()-1, target);
        }
    }

    int find(vector<int>& nums, int start, int end, int target){
        while(start <= end){
            int mid = (start + end) / 2;
            if(target < nums[mid]){
                end = mid - 1;
            } else if(target > nums[mid]) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    int findK(vector<int>& nums){
        int start = 0, end = nums.size() - 1;
        while(start < end){
            int mid = (start + end) / 2;
            if(nums[start] < nums[mid]){
                start = mid;
            } else {
                end = mid;
            }
        }
        return start;
    }
};

给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器。

 

示例 1:

输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:

输入:height = [1,1]
输出:1
示例 3:

输入:height = [4,3,2,1,4]
输出:16
示例 4:

输入:height = [1,2,1]
输出:2
 

提示:

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法1 宽度优先贪心

容易想到:面积=高*宽
而在限定高度的情况下越宽越好,因此我们可以对数组的高度进行枚举判断在每一个高度下,取能支持此高度最宽的边界l,r 对于每一个h,计算 area = (r-l) * min(arr[l], arr[h]),要求min(arr[l], arr[h])>=h
其中l是满足高度大于h的最左边的下标l,r是满足高度大于h的最右边的下标r。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector<int> height = {1, 2, 1};
    vector<int> height_b(height);
    sort(height_b.begin(), height_b.end());
    int mmax = 0;
    for(int i = 0; i < height_b.size(); i++){
        if(i != 0 && height_b[i] == height_b[i-1]){
            continue;
        }
        int h = height_b[i];
        int l = 0, r = 0;
        for(int j = 0; j < height.size(); j++){
            if(height[j] >= h) {
                l = j;
                break;
            }
        }
        for(int j = height.size() - 1; j > l; j--){
            if(height[j] >= h) {
                r = j;
                break;
            }
        }
        if(r == l){
            continue;
        }
        mmax = max(mmax, (r-l)*h);
    }
    cout << mmax;
    return 0;
}

解法2 双指针法

令l=0, r=height.size()-1;
可得area = (r-l) * min(height[l], height[r]);
若 height[l] < height[r] 则l++,否则r--
证明:

若height[l] < height[r], area = (r-l) * height[l],设r-l=t
设移动后的r=r0, r0-l=t0
若height[r0] < height[l] 则: area0 = t0 * height[r0] < area = t * height[l]
若height[r0] >= height[l] 则: area0 = t0 * height[l] < area = t * height[l]
也就是说当height[l] < height[r]时,无论什么情况r--的areax均<=area。

那移动l呢?
设移动后的l=l0, r-l0=t0
若height[l0] < height[l] 则:area0 = t0 * height[l0] < area
若height[l0] >= height[l] 则: area0 = t0 * height[r] 有可能>=area, 也有可能 <= area
因此证得height[l] < height[r]时需l++,因为area最值只可能出现在l++部分,同理可证height[l] >= height[r]时,r--。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int mmax = 0;
        int l = 0, r = height.size()-1;
        while(l < r){
            mmax = max(mmax, (r - l) * min(height[l], height[r]));
            if(height[l] < height[r]){
                l++;
            } else {
                r--;
            }
        }
        return mmax;
    }
};

题干

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。
 

示例 1:

输入:x = 123
输出:321
示例 2:

输入:x = -123
输出:-321
示例 3:

输入:x = 120
输出:21
示例 4:

输入:x = 0
输出:0
 

提示:

-231 <= x <= 231 - 1

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-integer
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

数学推导

class Solution {
public:
    int reverse(int x) {
        int a = x;
        int s = 0;
        while(a){
            int digit = a%10;
            s += digit;
            a = a/10;
            if(a){
                if(x > 0){
                    if(s > (INT_MAX - 1 - digit) / 10){
                        return 0;
                    }
                } else {
                    if(s < (INT_MIN-digit)/10){
                        return 0;
                    }
                }
                s = s*10;
            }
        }
        return s;
    }
};

$$-2^{31} \le rev*10+digit \le 2^{31}-1$$

$$\left \lfloor \frac{-2^{31}-digit}{10} \right \rfloor \le rev \le \left \lfloor \frac{2^{31}-1-digit}{10} \right \rfloor $$