2022年1月

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format $$N=p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_m^{k_m} $$
Input Specification:
Each input file contains one test case which gives a positive integer N in the range of long int.

Output Specification:
Factor N in the format N=p1^k1p2^k2...pm^km

Sample Input:
97532468
Sample Output:
97532468=2^211171011291

思路:
先求素数表,然后对于每一个素数尝试去分解题目所提供的值,分解至无法整除为止记录下来,这里记录用了一个结构体 factor 表示一次分解的结果 x表示底,cnt表示次方。这里要注意特判1的情况否则1不会输出。

#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 100010;
int prime[maxn], pNum = 0;
bool p[maxn] = {0}; // p[i] == false 为质数

void findPrime(){
    for(long int i = 2; i < maxn; i++){
        if(p[i]){
            continue;
        }
        prime[pNum++] = i;
        for(long int j = i + i; j <= maxn; j += i){
            p[j] = true;
        }
    }
}

struct factor {
    long int x;
    int cnt;
} fac[10];

int main() {
    long int value;
    cin >> value;
    if(value == 1){
        printf("1=1");
        return 0;
    }
    long int bValue = value;
    findPrime();
    int fNum = 0;
    for(int i = 0; i < pNum; i++){
        long int j = prime[i];
        if(bValue % j != 0){
            continue;
        }
        factor f = factor{};
        f.x = j;
        int cnt = 0;
        while(bValue % j == 0){
            bValue /= j;
            cnt++;
        }
        f.cnt = cnt;
        fac[fNum++] = f;
        if(bValue == 0){
           break;
        }
    }
    printf("%ld=", value);
    for(long int i = 0; i < fNum; i++){
        printf("%ld", fac[i].x);
        if(fac[i].cnt > 1){
            printf("^%d", fac[i].cnt);
        }
        if(i != fNum - 1){
            printf("*");
        }
    }
    return 0;
}

For any 4-digit integer except the ones with all the digits being the same, if we sort the digits in non-increasing order first, and then in non-decreasing order, a new number can be obtained by taking the second number from the first one. Repeat in this manner we will soon end up at the number 6174 -- the black hole of 4-digit numbers. This number is named Kaprekar Constant.

For example, start from 6767, we'll get:

7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
... ...
Given any 4-digit number, you are supposed to illustrate the way it gets into the black hole.

Input Specification:
Each input file contains one test case which gives a positive integer N in the range (0,10
4
).

Output Specification:
If all the 4 digits of N are the same, print in one line the equation N - N = 0000. Else print each step of calculation in a line until 6174 comes out as the difference. All the numbers must be printed as 4-digit numbers.

Sample Input 1:
6767
Sample Output 1:
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
Sample Input 2:
2222
Sample Output 2:
2222 - 2222 = 0000

这里要注意6174的情况如果先while(value != 6174) 再执行代码则可能出现6174没有打印结果所以应该要用do{} while()

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


int getNums(int value, bool isDecrease){
    int nums[10];
    memset(nums, 0, sizeof(nums));
    int count = 0;
    while(value != 0){
        nums[value%10]++;
        value /= 10;
        count++;
    }
    for(int i = count; i < 4; i++){
        nums[0]++;
    }
    int result = 0;
    if(!isDecrease){
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < nums[i]; j++){
                result = result*10 + i;
            }
        }
    } else {
        for(int i = 9; i >= 0; i--){
            for(int j = 0; j < nums[i]; j++){
                result = result*10 + i;
            }
        }
    }
    return result;
}

int main() {
    int value;
    cin >> value;
    do{
        int a = getNums(value, true);
        int b = getNums(value, false);
        value = a-b;
        printf("%04d - %04d = %04d\n", a, b, value);
        if(value == 0){
            break;
        }
    }while(value != 6174);
    return 0;
}

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