1、两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i,j;
        for(i=0;i<nums.size()-1;i++)
        {
            for(j=i+1;j<nums.size();j++)
            {
                if(nums[i]+nums[j]==target)
                {
                   return {i,j};
                }
            }
        }
        return {i,j};
    }
};

2、三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for (int first = 0; first < n; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = n - 1;
            for (int second = first + 1; second < n; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while (second < third && nums[first] + nums[second] + nums[third] > 0) {
                    --third;
                }
                if (second == third) {
                    break;
                }
                if (nums[first] + nums[second] + nums[third] == 0) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};

3、合并两个有序链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr){
            return l2;
        }else if(l2 == nullptr)
        {
            return l1;
        }
        else if(l1->val < l2->val)
        {
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }
        else
        {
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
    }
};

4、删除有序数组的重复项

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int numsSize = nums.size();
        if(numsSize<2)
            return numsSize;
        int slow = 0;
        for(int fast=1;fast<numsSize;fast++){
            if(nums[fast] != nums[slow]){
                nums[++slow] = nums[fast];
            }
        }
        return ++slow;
    }
};

5、在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int first = -1;
        int end = -1;
        for(int i=0;i<nums.size();i++){
            if(nums[i] == target){
                first = i;
                break;
            }
        }
        for(int j=nums.size()-1;j>=0;j--){
            if(nums[j] == target){
                end = j;
                break;
            }
        }
        return {first,end};
    }
};

6、最大子数组和

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        int result = INT_MIN;
        int numsSize = int(nums.size());
        int sum = 0;
        for (int i = 0; i < numsSize; i++)
        {
            sum += nums[i];
            result = max(result,sum);
            if(sum<0){
                sum=0;
            }
        }
        return result;
    }
};

7、不同路径

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return ans;
    }
};

8、买卖股票的最佳时机

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int pricesSize = prices.size();
        int result = 0;
        int minPrice=INT_MAX;
        for(int i=0;i<pricesSize;i++){
            if(result < prices[i]-minPrice){
                result=prices[i]-minPrice;
            }
            if(minPrice>prices[i]){
                minPrice=prices[i];
            }
        }
        return result;
    }
};

9、二维区域和检索-矩阵不可变

class NumMatrix {
public:
    vector<vector<int>> sums;
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m > 0) {
            int n = matrix[0].size();
            sums.resize(m + 1, vector<int>(n + 1));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                }
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */

10、无重叠区间

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        //按照右边界排序
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });

        if(intervals.empty())
            return 0;
        int count = 0;
        int pre = intervals[0][1];
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0]<pre){
                count++;
            }else{
                pre = intervals[i][1];
            }
        }
        return count;
    }
};

11、用最少数量的箭引爆气球

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        //按照右边界排序
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        if(points.empty())
            return 0;
        
        int pos = points[0][1];
        int count = 1;
        for(int i=1;i<points.size();i++){
            if(points[i][0]>pos){
                count++;
                pos=points[i][1];
            }
        }
        return count;
    }
};

12、分发饼干

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int n = 0;
        int i = 0;
        int j = 0;
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        while(i<g.size() && j<s.size()){
            if(s[j]>=g[i]){
                i++;
                j++;
                n++;
            }else{
                j++;
            }
        }
        return n;
    }
};

13、种花问题

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        for(int i=0;i<flowerbed.size();i++){
            if(flowerbed[i]==0 && (i==0||flowerbed[i-1]==0) &&(i==flowerbed.size()-1 ||flowerbed[i+1]==0))
            {
                flowerbed[i]=1;
                n--;
            }
        }
        return n<=0;
    }
};

14、拼车

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        //判断每一个站点是否超载
        int allTrip[1000]={0};
        for (int i = 0; i < trips.size(); i++) {
            for (int j = trips[i][1]; j < trips[i][2]; j++) {
                allTrip[j] += trips[i][0];
                if (allTrip[j] > capacity) {
                    return false;
                }
            }
        }
        return true;
    }
};

15、第K个数

class Solution {
public:
    int getKthMagicNumber(int k) {
        int ans[k];
        ans[0]=1;
        int p3=0;
        int p5=0;
        int p7=0;
        for(int i=1;i<k;i++){
            int t3=ans[p3]*3;
            int t5=ans[p5]*5;
            int t7=ans[p7]*7;
            ans[i]=min(min(t3,t5),t7);
            if(ans[i]==t3) p3++;
            if(ans[i]==t5) p5++;
            if(ans[i]==t7) p7++;
        }
        return ans[k-1];
    }
};

16、三角形中最小的路径之和

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> f(n, vector<int>(n));
        f[0][0] = triangle[0][0];
        for (int i = 1; i < n; i++) {
            f[i][0] = f[i - 1][0] + triangle[i][0];  //j=0
            for (int j = 1; j < i; j++) {
                f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];  //other
            }
            f[i][i] = f[i - 1][i - 1] + triangle[i][i];    //i=j
        }
        return *min_element(f[n - 1].begin(), f[n - 1].end());
    }
};

17、排列的数目

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for(int& num : nums){
                if(num<=i && dp[i-num]<INT_MAX-dp[i])
                    dp[i] += dp[i-num];
            }
        }
        return dp[target];
    }
};

1042 协作工作

#include <stdio.h>
#include<iostream>
#include<cmath>
using namespace std;
int main(){
	double h,w,a,b;
	while(scanf("%lf %lf %lf %lf", &h, &w, &a, &b) != EOF){
	double maxlen = sqrt(h*h + w*w);
	double minbian = (a < b) ? a : b;
	if(minbian <= maxlen){
		cout << "Just do it.";
	}else{
		cout << "We have a problem.";
	}
	cout << endl;
} }

相对分子质量

#include<stdio.h>
#include<string.h>
int main(){
	double molecularWeight(char ch);//函数声明
	int n, tempn;//暂存数字
	double temp, ans;//temp-暂存分子量
	char str[90];//字符串
	int flag = -1;//当前位是字母，flag = 1， 当前位是数字，flag = 0，初始化为-1（既不是数字也不是字母) 
	scanf("%d", &n);
	while(n--){
		tempn = 0;
		temp = 0;
		ans = 0;
		scanf("%s", str);
		int i;
		for(i = 0;i < strlen(str);i++){
			if(str[i] >= 'A' && str[i] <='Z'){
			if(flag == 1){//当前是字母并且前一位是字母
				ans = ans + temp; 
			}else{//当前是字母并且前面是数字
				temp = temp * tempn;
				ans = ans + temp;
				tempn = 0; 
		}
	temp = molecularWeight(str[i]);//求分子量
	flag = 1;//当前位是字母，flag = 1
	}else{
tempn = tempn * 10 + str[i] - '0';//求数字
flag = 0;//当前位是数字，flag = 0
}}
if(flag == 1){//最后一位是字母的话，加上当前位的分子量
temp = molecularWeight(str[i - 1]);
ans = ans + temp; }else{//最后面是数字
ans = ans + temp * tempn; }
printf("%.3lf\n", ans);
}}
double molecularWeight(char ch){
double temp;
if(ch == 'C'){
temp = 12.01; }else if(ch == 'H'){
temp = 1.008; }else if(ch == 'O'){
temp = 16;
}else if(ch == 'N'){
temp = 14.01; }
return temp; }

1068 周期串

#include<stdio.h>
#include<string.h>
int main()
{
int t;
char str[80];
scanf("%d", &t);
while(t--){
scanf("%s", &str);
int len = strlen(str);
for(int i = 1;i <= len;i++){//假设 i 是周期
int flag = 1;//i 是周期的话，flag = 1，不是的话 flag 为 0 
if(len % i ==0){//假设 i 是周期，肯定可以被长度整除
for(int j = i;j < len;j++){
if(str[j] != str[j % i]){
flag = 0;
break; }}
if(flag == 1){
printf("%d\n", i);
printf("\n");
break; }}}}
return 0; }

将正整数分解相加

#include <iostream> using namespace std;
int a[31], n, sum = 0, count = 1, top = 0;
void Dfs(int i)
{if (sum == n)
{
cout << n << "=";
for (int j = 0; j < top - 1; j++)
{
cout << a[j] << "+";
}
cout << a[top - 1];
if (count % 4 == 0 || a[top - 1] == n) cout << endl; else cout << ";";
count++;
}
else if (sum < n)
{
for (int j = i; j <= n; j++)
{
a[top++] = j; sum += j; Dfs(j);
sum -= j; top--;
}
}
}
int main()
{
cin >> n; Dfs(1);
return 0;
}

N项物品装箱

#include <iostream> #include <cstring>
using namespace std; int main()
{
int n, m = 0; cin >> n;
int s[n][2], b[n];
for (int i = 0; i < n; i++)
{
cin >> s[i][0]; b[i] = 100;
}
for (int i = 0; i < n; i++)
{
int flag = 1, j = 0; while (flag)
{
if (b[j] >= s[i][0])
{
flag = 0;
b[j] -= s[i][0];
s[i][1] = j + 1;;
}
else
{
j++;
if (j > m) m = j;
}
}
}
for (int i = 0; i < n; i++)
{
cout << s[i][0] << " " << s[i][1] << endl;
}
cout << m + 1 << endl; return 0;
}

质数模50000

#include <stdio.h> #include <math.h>
#define epsilon 1e-8 int IsPrime(int n)
{
int ok = n > 1;
int m = (int)sqrt(n + epsilon), k = 2; while (ok && k <= m)
{
ok = n % k != 0;
++k;
}
return ok;
}
int main()
{
int n, i = 0, j, sum = 1; scanf("%d", &n);
for (j = 2; i < n; j++)
{
if (IsPrime(j))
{
sum *= j; sum %= 50000; i++;
}
}
printf("%d\n", sum);
 
return 0;
}