一、ranko的手表

ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。
ranko 在 t1时刻看了下时间，过了一段时间在 t2时刻看了下时间。她想知道， t1 和 t2这两个时刻之间相距的时间的最大值和最小值是多少？
保证 t1在 t2之前（且 t1和 t2等）。t1和 t2在同一天的 00:00 到 23:59 之间。
输入描述：
两行输入两个时间，为 xx:xx 的形式。其中 xx 为数字或者字符 ‘?’ ，问号代表这个数字没有显示。
保证输入是合法的。
输出描述：
一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。
输入：
18:0?
2?:1?
复制
输出：
121 319
复制
说明：
相距最小的时间为 18:09 到 20:10 ，相距121分钟。
相距最大的时间为 18:00 到 23:19 ，相距319分钟。

解法:

将一天的时间进行以分钟为单位进行转换，并进行从0到24 * 60分钟进行遍历，若分钟用i表示，那么将i进行24小时制进行转换，当至少满足所提供的两个时间其一时，将该时间存入各自的容器中，最后进行遍历两个容器，分别求得最大值与最小值。

#include
#include
#include
using namespace std;
int main()
{
	string a, b;
	cin >> a >> b;
	int total_minute = 24 * 60,mint = 1e+6,maxt = 0;
	vector<int> vec1, vec2;
	for (int i = 0; i < total_minute; ++i) {
		int hour = i / 60, minute = i % 60;
		if ((a[0] == '?' || a[0] - '0' == hour / 10) && (a[1] == '?' || a[1] - '0' == hour % 10) && (a[3] == '?' || a[3] - '0' == minute / 10)
			&& (a[4] == '?' || a[4] - '0' == minute % 10))
			vec1.push_back(i);
		if ((b[0] == '?' || b[0] - '0' == hour / 10) && (b[1] == '?' || b[1] - '0' == hour % 10) && (b[3] == '?' || b[3] - '0' == minute / 10)
			&& (b[4] == '?' || b[4] - '0' == minute % 10))
			vec2.push_back(i);
	}
	for (int i = 0; i < vec1.size(); ++i) {
		for (int j = 0; j < vec2.size(); ++j) {
			if (vec1[i] < vec2[j]) {
				mint = min(vec2[j] - vec1[i], mint);
				maxt = max(vec2[j] - vec1[i], maxt);
			}
		}
	}
	cout << mint << " " << maxt;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

二、和为S的连续正数序列

解法一:

我们可以从数字1开始枚举连续的数字，将其累加判断其是否等于目标，如果小于目标数则继续往后累加，如果大于目标数说明会超过，跳出，继续枚举下一个数字开始的情况（比如2，比如3），这样每次都取连续的序列，只有刚好累加和等于目标数才可以记录从开始到结束这一串数字，代表是一个符合的序列。

//枚举左区间
for(int i = 1; i <= up; i++){ 
    //从左区间往后依次连续累加
    for(int j = i; ;j++){
        ... 

1
2
3
4
5
6

而因为序列至少两个数，每次枚举区间的起始数字最多到目标数的一半向下取整即可，因为两个大于目标数一半的数相加一定大于目标数。

• 从1到目标值一半向下取整作为枚举的左区间，即每次序列开始的位置。
• 从每个区间首部开始，依次往后累加，如果大于目标值说明这一串序列找不到，换下一个起点。
• 如果加到某个数字刚好等于目标值，则记录从区间首到区间尾的数字。

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > res;
        vector<int> temp;
        int sum1 = 0;
        //因为序列至少两个数，因此枚举最多到该数字的一半向下取整
        int up = (sum - 1) / 2; 
        //枚举左区间
        for(int i = 1; i <= up; i++){ 
            //从左区间往后依次连续累加
            for(int j = i; ;j++){ 
                sum1 += j;
                //大于目标和则跳出该左区间
                if(sum1 > sum){ 
                    sum1 = 0;
                    break;
                //等于则找到
                }else if(sum1 == sum){ 
                    sum1 = 0;
                    temp.clear();
                    //记录线序的数字
                    for(int k = i; k <= j; k++) 
                        temp.push_back(k);
                    res.push_back(temp);
                    break;
                }
            }
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

解法二:

从某一个数字开始的连续序列和等于目标数如果有，只能有一个，于是我们可以用这个性质来使区间滑动。

两个指针l、r指向区间首和区间尾，公式(l+r)∗(r−l+1)/2计算区间内部的序列和，如果这个和刚好等于目标数，说明以该区间首开始的序列找到了，记录下区间内的序列，同时以左边开始的起点就没有序列了，于是左区间收缩；如果区间和大于目标数，说明该区间过长需要收缩，只能收缩左边；如果该区间和小于目标数，说明该区间过短需要扩大，只能向右扩大，移动区间尾。

• 从区间[1,2开始找连续子序列。
• 每次用公式计算区间内的和，若是等于目标数，则记录下该区间的所有数字，为一种序列，同时左区间指针向右。
• 若是区间内的序列和小于目标数，只能右区间扩展，若是区间内的序列和大于目标数，只能左区间收缩。
  

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > res;
        vector<int> temp;
        //从1到2的区间开始
        for(int l = 1, r = 2; l < r;){ 
            //计算区间内的连续和
            int sum1 = (l + r) * (r - l + 1) / 2; 
            //如果区间内和等于目标数
            if(sum1 == sum){ 
                temp.clear();
                //记录区间序列
                for(int i = l; i <= r; i++) 
                    temp.push_back(i);
                res.push_back(temp);
                //左区间向右
                l++; 
            //如果区间内的序列和小于目标数，右区间扩展
            }else if(sum1 < sum) 
                r++;
            //如果区间内的序列和大于目标数，左区间收缩
            else 
                l++;
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29