//1.最大子序和：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
#include <iostream>
#include <vector>
using namespace std;

int maxSubArray(vector<int>& nums) {
	//此时不确定数组的长度
	int MaxSum = 0;
	int PreSum = 0;
	for (int i = 0; i < nums.size(); i++) {
		PreSum += nums[i];
		if (PreSum > MaxSum) {
			MaxSum = PreSum;
		}
		if (PreSum <= 0) PreSum = 0;
	}
	return MaxSum;
}
int main() {
	int n;
	//cout << "请输入元素总个数：";
	cin >> n;
	vector<int> nums;
	//cout << "清输入各元素：";
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		nums.push_back(num);
	}
	cout << maxSubArray(nums);
	return 0;
}
//2.股票：给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。
#include <iostream>
#include <vector>
using namespace std;

int maxProfit(vector<int>& prices)
{
	int MaxProfit = 0;
	for (int i = 0; i < prices.size(); i++)
	{
		for (int j = i + 1; j < prices.size(); j++)
		{
			int temp = prices[j] - prices[i];
			if (temp > MaxProfit)
			{
				MaxProfit = temp;
			}
		}
	}
	return MaxProfit;
}

int main() {
	int n;
	cout << "请输入总天数：";
	cin >> n;
	vector<int> prices;
	cout << "清输入每天的股票价格：";
	for (int i = 0; i < n; i++) {
		int price;
		cin >> price;
		prices.push_back(price);
	}
	cout << maxProfit(prices);
	return 0;
}
//3.The missing integer：现在有 9个整数，这 9个整数都在 1到 10 之间（含 1 和 10），而且每个整数只出现了一次。因此，肯定会有一个整数缺失。现在把这个艰难的任务交给你，让你找到缺失的整数。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int findInteger(vector<int>& nums) {
    sort(nums.begin(), nums.end());//升序
    int i;
    for (i = 1; i <= nums.size(); i++) {
        if (nums[i - 1] != i)
            break;
    }
    return i;
}
int main()
{
    int n = 9;
    vector<int> nums;
    //cout << "输入这些整数：";
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        nums.push_back(temp);
    }
    cout << "The missing integer is:" << findInteger(nums);
}
//4.协助工作：现在需要把若干块已知边长的黑板（厚度忽略不计）搬进教室，请设计程序判断黑板能否穿过教室的门。
#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 door = sqrt(h * h + w * w);
		double shortEdge = (a < b) ? a : b;
		if (shortEdge <= door) {
			cout << "Just do it.";
		}
		else {
			cout << "We have a problem.";
		}
		cout << endl;
	}
}
//5.分发饼干：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int findContentChildren(vector<int>& g, vector<int>& s) {
	sort(g.begin(), g.end());
	sort(s.begin(), s.end());
	int KidSum = 0;
	int i = 0;
	int j = 0;
	while (i < s.size() && j < g.size()) {
		if ( g[j] <= s[i]  ) {
			j++;
			i++;
			KidSum++;
		}
		else {
			i++;
		}
	}
	return KidSum;
}
int main() {
	vector<int> vec1{ 1,2 }, vec2{ 1,2,3 };
	cout << findContentChildren(vec1, vec2);
	system("PAUSE");
	return 0;
}
//6.排列的数目：	给定一个由不同正整数组成的数组 nums，和一个目标整数target。请从 nums 中找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。
#include<iostream>
#include<vector>
using namespace std;

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];
}
int main() {
    int n;
    int target;
    vector<int> nums;
    cout << "请输入数组元素个数：";
    cin >> n;
    cout << "请输入元素：";
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        nums.push_back(temp);
    }
    cout << "请输入目标整数：";
    cin >> target;
    cout <<"组合个数："<< combinationSum4(nums, target)<<endl;
    system("PAUSE");
    return 0;
}
//7.不同路径：一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start”）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？
#include<iostream>
using namespace std;

int uniquePaths(int m, int n) {
    if (m <= 0 || n <= 0) return 0;
    if (m == 1 && n == 1) return 1;
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}
int main() {
    int m, n;
    cout << "m = ";
    cin >> m;
    cout << "n = ";
    cin >> n;
    cout << uniquePaths(m, n)<<endl;
    system("PAUSE");
    return 0;
}
//8.Torry的困惑：Torry从小喜爱数学。一天，老师告诉他，像2、3、5、7……这样的数叫做质数。
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
    int n, i, j, count = 0;
    long long sum = 1;
    cin >> n;
    for (i = 2; i <= sqrt(10000); i++)
    {
        for (j = 2; j < i; j++)
        {
            if (i % j == 0)
                break;
        }
        if (j >= i)
        {
            count++;
            sum = (sum * i) % 50000;
            if (count == n)
                break;
        }
    }
    cout << sum << endl;
    return 0;
}
// 9.第k个数:有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 3，5，7，9，15，21，25，27，35.
#include <iostream>
#include <stdio.h>
using namespace std;

int min(int a, int b, int c){
	int minNum = a < b ? a : b;
	minNum = minNum < c ? minNum : c;
	return minNum;
}
int findUglyNumber(int k){
	int* pArray = new int[k + 1];
	pArray[0] = 1;
	int* p3, * p5, * p7;
	p3 = p5 = p7 = pArray;
	int count = 0;
	int minNum;
	while (count < k){
		count++;
		minNum = min(*p3 * 3, *p5 * 5, *p7 * 7);
		pArray[count] = minNum;
		//注意等号不能取，while中循环条件如果改成 *p3 * 3 < minNum 是错误的，这样会陷入死循环，使得minNum候选的几个候选值不再变化 
		while (*p3 * 3 <= minNum){
			p3++;
		}
		while (*p5 * 5 <= minNum){
			p5++;
		}
		while (*p7 * 7 <= minNum){
			p7++;
		}
	}
	int result = pArray[k];
	delete[] pArray;
	return result;
}
int main(){
	int k;
	cin >> k;
	cout << findUglyNumber(k);
	return 0;
}
// 10.删除有序数组中的重复项：给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。
#include<iostream>
#include<vector>
using namespace std;

int DeleteDuplicate(vector<int>& nums) {
	if (nums.empty())
		return 0;
	int low = 0;
	for (int fast = 1; fast < nums.size(); fast++) {
		if (nums[fast] != nums[low]) {
			low++;
			nums[low] = nums[fast];
		}
	}
	return low+1;
}
int main() {
	int n;
	cout << "输入数组元素个数：";
	cin >> n;
	vector<int> nums;
	cout << "输入元素：";
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		nums.push_back(temp);
	}
	int size = DeleteDuplicate(nums);
	cout << "去除重复项后的数组长度：" << size << endl;
	cout << "nums = ";
	for (int i = 0; i < size; i++) {
		cout << nums[i] << " ";
	}
	return 0;
}
// 11.无重叠区间:给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if (intervals.empty()) {
        return 0;
    }

    sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
        return u[1] < v[1];
        });

    int n = intervals.size();
    int right = intervals[0][1];
    int ans = 1;
    for (int i = 1; i < n; ++i) {
        if (intervals[i][0] >= right) {
            ++ans;
            right = intervals[i][1];
        }
    }
    return n - ans;
}
int main() {
    int n;
    cout << "输入区间个数：";
    cin >> n;
    vector<vector<int>> out(n, vector<int>(2));
    for (int i = 0; i < n; i++) {
        cout << "输入第" << i + 1 << "个区间的起始点：";
        cin >> out[i][0] >> out[i][1];
    }
    cout<<"移除数量："<<eraseOverlapIntervals(out);
    return 0;
}
// 12.周期串：如果一个字符串可以被某个长度为k的字符串重复一次或多次得到，则称这个字符串的周期为k。
#include<iostream> 
#include<string> 
using namespace std;
int main()
{
	int t;
	char str[80]; 
	cin >> t; 
	while (t--) {
		cin >> 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) {
					cout << i << endl;
					break;
				}
			}
		}
	}
	return 0;
}
// 13.拼车：假设你是一位顺风车司机。
#include <iostream>
#include<vector>
#include<map>
using namespace std;

bool carPooling(vector<vector<int>>& trips, int capacity)
{
    map<int, int> tmp;
    for (auto it : trips)
    {
        for (int i = it[1]; i < it[2]; i++)
        {
            tmp[i] += it[0];
        }
    }
    for (auto it : tmp)
    {
        if (it.second > capacity)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int n;
    int cap;
    cout << "行程数：";
    cin >> n;
    cout << "空位数：";
    cin >> cap;
    vector<vector<int>> trips(n, vector<int>(3));
    for (int i = 0; i < n; i++) {
        cout << "输入第" << i + 1 << "个行程的信息：";
        cin >> trips[i][0] >> trips[i][1] >> trips[i][2];
    }
    if (carPooling(trips, cap)) {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }
    return 0;
}

// 14.最小操作次数使数组元素相等：给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。
#include <iostream>
#include<vector>
using namespace std;
int minMoves(vector<int>& nums) {
    int n = nums.size();
    if (n == 0 || n == 1)return 0;
    int s = 0;
    int min = nums[0];
    for (int i = 0; i < n; i++) {
        if (nums[i] < min)min = nums[i]; //不用sort函数，o(n)找到最小值
    }
    for (int i = 0; i < n; i++) {
        s = s + nums[i] - min; //让n-1个数每次加一，相当于让一个数每次减1，只要每次都让最大的数减小到和最小的数相等即可
    }
    return s;
}
int main()
{
    vector<int> nums;
    while (true)
    {
        int temp;
        cin >> temp;
        nums.push_back(temp);
        if (cin.get() == '\n')   break;
    }
    cout << minMoves(nums)<<endl;
    system("PAUSE");
    return 0;
}
// 15.炒股:小明很喜欢炒股,他记录了一段时间内一支股票股价的变化。
#include <iostream>
#include<vector>
using namespace std;
int CountUp(vector<int>& days) {
    int sum = 0;
    int max = 0;
    for (int i = 0; i + 1 < days.size(); i++) {
        int begin = i;
        if (days[begin] < days[begin + 1]) {
            sum++;
            max = max > sum ? max : sum;
        }
        else
        {
            sum = 1;
        }
    }
    return max;
}
int main()
{
    vector<int> nums;
    while (true)
    {
        int temp;
        cin >> temp;
        nums.push_back(temp);
        if (cin.get() == '\n')   break;
    }
    cout << CountUp(nums) << endl;
    system("PAUSE");
    return 0;
}
// 16.替换空格：请实现一个函数，把字符串s 中的每个空格替换"%20"。 
#include <iostream>
#include<string>
using namespace std; 

string replaceSpace(string s) {
	int og_len = s.size();
	int count_blank = 0;
	for (int i = 0; i < og_len; i++) {
		if (s[i] == ' ') count_blank++;
	}
	s.resize(og_len + count_blank * 2);
	int new_len = s.size();
	for (int i = og_len - 1, j = new_len - 1; i < j; i--, j--) {
		if (s[i] != ' ') s[j] = s[i];
		else {
			s[j - 2] = '%';
			s[j - 1] = '2';
			s[j] = '  0';
			j -= 2;
		}
	}
	return s;
}
int main() {
	string s;
	getline(cin, s);
	cout << replaceSpace(s) << endl;
}
// 17.两数之和
#include <iostream>
#include<vector>
using namespace std;
void twoSum(vector<int>& nums, int target) {
    int n = nums.size();
    int a, b;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (nums[i] + nums[j] == target) {
                a = i;
                b = j;
            }
        }
    }
    cout << "[" << a << "," << b << "]" << endl;
}
int main()
{
    int tar;
    vector<int> nums;
    cout << "目标：";
    cin >> tar;
    cout << "数组：";
    do
    {
        int temp;
        cin >> temp;
        nums.push_back(temp);
    } while (cin.get() != '\n');
    twoSum(nums,tar);
    system("PAUSE");
    return 0;
}
// 18.种花问题:假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。
#include <iostream>
#include<vector>
using namespace std;
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
	int sum = flowerbed.size();
	/*if(flowerbed.empty() || n > (sum+1)/2){ return false; }*/
	if (n == 0) return true;
	if (sum == 1) {
		if (flowerbed[0] == 0) {
			return true;
		}
		else {
			if (n == 0) {
				return true;
			}
			return false;
		}
	}
	if (flowerbed[0] == 0 && sum >= 2) {
		if (flowerbed[1] == 0) {
			n--;
			flowerbed[0] = 1;
		}
	}
	int i = 1;
	while (i < (sum - 1) && n != 0) {
		if (flowerbed[i] == 0 && flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
			flowerbed[i] = 1;
			n--;
		}
		i++;
	}
	if (flowerbed[sum - 1] == 0 && sum >= 2 && n != 0) {
		if (flowerbed[sum - 2] == 0) {
			n--;
		}
	}
	if (n == 0) {
		return true;
	}
	return false;
}
int main()
{
	int n;
	vector<int> flowers;
	cout << "n=";
	cin >> n;
	do
	{
		int t;
		cin >> t;
		flowers.push_back(t);
	} while (cin.get()!='\n');
	if (canPlaceFlowers(flowers, n)) {
		cout << "true";
	}
	else
	{
		cout << "false";
	}
}

// 19.三角形中最小路径之和
#include <iostream>
#include<vector>
using namespace std;
int minimumTotal(vector<vector<int>>& triangle) {
    for (int i = triangle.size() - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            triangle[i - 1][j] += min(triangle[i][j], triangle[i][j + 1]);
        }
    }
    return triangle[0][0];
}
int main()
{
    vector<vector<int>> triangle;
    vector<int> t;
    bool flag = true;
    int temp;
    while (flag){
        do
        {
            cin >> temp;
            if (!cin) {
                flag = false;
                break;
            }
            t.push_back(temp);
        } while (cin.get()!='\n');
        if (flag) {
            triangle.push_back(t);
            t.clear();
        }
    }
    cout << minimumTotal(triangle) << endl;
    return 0;
}