LeetCode 681. Next Closest Time

You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9” are all invalid.

Example 1:

Input: “19:34”

Output: “19:39”

Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39,
which occurs 5 minutes later.

It is not 19:33, because this occurs 23 hours and 59 minutes later.

Example 2:

Input: “23:59”

Output: “22:22”

Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22.
It may be assumed that the returned time is next day’s time since it is smaller
than the input time numerically.

法一暴力法

#include<iostream>
#include<algorithm>
#include<string>
#include<set>
using namespace std;
string nextCloseTime(string time)
{
	//!!
	set<char> t(time.begin(),time.end());
	int hour=stoi(time.substr(0,2));
	int min=stoi(time.substr(3,2));
	char str[5];
	while(1){
		min++;
		if(min==60){
			min=0;
			hour=(hour+1)%24;
		}
		sprintf(str,"%02d:%02d",hour,min);
		set<char> s(str,str+sizeof(str));
		//比较是排好序的两个序列 
		if(includes(t.begin(),t.end(),s.begin(),s.end())) break;
		
	}
	string ans=(string)str;
	return ans;
}
int main(void)
{
string p="19:34";
string ans=nextCloseTime(p);
cout<<ans;
}

法二 dfs

用best表示与当前时间相差的分钟数维护best

#include<iostream>
#include<algorithm>
#include<string>
#include<set>
#define INT_MAX 0xffff
using namespace std;

void dfs(int depth,int &best,int curr[],int digits[],int &ans){

	if(depth==4){
		if(curr[0]*10+curr[1]>24) return;
		if(curr[2]*10+curr[3]>59) return;
		int curtime=(curr[0]*10+curr[1])*60+curr[2]*10+curr[3];
		int pastime=(digits[0]*10+digits[1])*60+digits[2]*10+digits[3];
		int tt=(curtime-pastime+24*60)%(24*60);
		if(curtime==pastime) tt=24*60;
		if(tt<best) 
		{
			best=tt;			
		    ans=curtime;		  
		}	
	  return;
	}
    else{
	for(int i=0;i<4;i++){
	curr[depth]=digits[i];
	dfs(depth+1,best,curr,digits,ans); 
	}
	
}
}
string nextCloseTime(string time)
{

int hour=(int)stoi(time.substr(0,2));
int min=(int)stoi(time.substr(3,2));
int digits[4]={hour/10,hour%10,min/10,min%10};
int best=INT_MAX;
int curr[5];
int dep=0;
int ans;
dfs(dep,best,curr,digits,ans);
char buff[5];
sprintf(buff, "%02d:%02d", ans/60, ans%60);
return (string)buff;
}
int main(void)
{
string p="23:59";
string ans=nextCloseTime(p);
cout<<ans;
}

参考链接

https://zxi.mytechroad.com/blog/?s=681

法一 暴力法

法二 dfs

法一暴力法