# 539. Minimum Time Difference

## Description

Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list.

Example 1:

Input: ["23:59","00:00"]
Output: 1


Note:

The number of time points in the given list is at least 2 and won’t exceed 20000.

The input time is legal and ranges from 00:00 to 23:59.

1. 先将所有的时间点转化为分钟的形式，对新列表进行遍历，之后，如果在第i分钟时，时间点存在，则将其设置为true，否则保持false 在标记过程中，若发现某元素已经存在，直接返回0即可，因为相同时间点如果出现两次及以上，说明最小时间差就是0

2. 加入辅助变量last,first,min,prev,分别用于标记循环的左右边界和最小值以及上一次遍历过的元素。

3. 之后再次遍历boolean数组，如果first不等于初始值，则说明被更新过，那么首先计算新的min值，之后更新其他辅助变量即可。

4.返回最终结果

public class Solution {
public int parseTime(List<String> timePoints){
boolean [] array=new boolean[24*60];
int min=Integer.MAX_VALUE;
int first=Integer.MAX_VALUE;
int last=Integer.MIN_VALUE;
int prev=0;
for(int i=0;i<timePoints.size();++i){
String firHour=timePoints.get(i).split(":")[0];
String firMin=timePoints.get(i).split(":")[1];
int fir_Min=Integer.parseInt(firMin);
int fir_Hour=Integer.parseInt(firHour);
if(array[fir_Hour*60+fir_Min]==true)  return 0;
array[fir_Hour*60+fir_Min]=true;
}

for(int i=0;i<24*60;++i){
if(array[i]){
if(first!=Integer.MAX_VALUE){
min=Math.min(min,i-prev);
}
first=Math.min(first,i);
last=Math.max(last,i);
prev=i;
}
}
return Math.min(min,24*60-last+first);
}

public int findMinDifference(List<String> timePoints) {
return parseTime(timePoints);
}
}


["23:56","09:03","10:01"]

第543次迭代所得的first为543, last为543



# 357. Count Numbers with Unique Digits

## Description

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10 n.

Example: Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Hint:

1. A direct way is to use the backtracking approach.
2. Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
3. This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
4. Let f(k) = count of numbers with unique digits with length equals k.
5. f(1) = 10, …, f(k) = 9 * 9 * 8 * … (9 - k + 2) [The first factor is 9 because a number cannot start with 0].

## Analysis

9*9=81


n==3及之后的情况请自行考虑，我们已经找出了解决此题的一种方法，代码如下:

## Code

class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if(n==0)
return 1;
n=min(n,10);
vector<int> dp(n+1,9);
int sum=0;
dp[1]=10;
for(int i=2;i<=n;++i)
for(int j=9;j>=9-i+2;--j)
dp[i]*=j;
for(int i=1;i<dp.size();++i){
sum+=dp[i];
}
return sum;
}
};


# 131. Palindrome Partitioning

## Description

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab", Return

[
["aa","b"],
["a","a","b"]
]


## code

class Solution {
private:
bool isPalindrome(const string & s,int start,int end){
while(start<end){
if(s[start++]!=s[end--])
return false;
}
return true;
}
void  backtracking(vector<vector<string>> & res,vector<string> & temp,string & s,int start){
if(start==s.size()){
res.push_back(temp);
return;
}
for(int i=start;i<s.size();++i){
if(isPalindrome(s,start,i)){
temp.push_back(s.substr(start,i-start+1));
backtracking(res,temp,s,i+1);
temp.pop_back();
}
}
}
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> temp;
backtracking(res,temp,s,0);
return res;
}
};


# 77. Combinations

## Description

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example, If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]


## code

class Solution {
private:
void backtracking(vector<vector<int>> & res,vector<int> & temp,int * num,int start,int k,int n){
if(temp.size()==k){
res.push_back(temp);
return;
}
for(int i=start;i<n;++i){
temp.push_back(num[i]);
backtracking(res,temp,num,i+1,k,n);
temp.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> temp;
int * array=new int[n];
for(int i=1;i<=n;++i)
array[i-1]=i;
backtracking(res,temp,array,0,k,n);
delete array;
return res;
}
};


class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
int i = 0;
vector<int> p(k, 0);
while (i >= 0) {
p[i]++;
if (p[i] > n) --i;
else if (i == k - 1) result.push_back(p);
else {
++i;
p[i] = p[i - 1];
}
}
return result;
}
};


For example, the (4, 2) test case yields:

Incremented element at index 0
[1, 0]
Moved index to the right, and copied the value from the left
[1, 1]
Incremented element at index 1
[1, 2]
Combination found!
Incremented element at index 1
[1, 3]
Combination found!
Incremented element at index 1
[1, 4]
Combination found!
Incremented element at index 1
[1, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[2, 5]
Moved index to the right, and copied the value from the left
[2, 2]
Incremented element at index 1
[2, 3]
Combination found!
Incremented element at index 1
[2, 4]
Combination found!
Incremented element at index 1
[2, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[3, 5]
Moved index to the right, and copied the value from the left
[3, 3]
Incremented element at index 1
[3, 4]
Combination found!
Incremented element at index 1
[3, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[4, 5]
Moved index to the right, and copied the value from the left
[4, 4]
Incremented element at index 1
[4, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[5, 5]
n exceeded at 0, moving index to the left
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]


# 60. Permutation Sequence

## Description

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"


Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

## Analysis

n=4


4*3*2*1=24


k=17


3*2*1*2=12


17-12=5


## code

class Solution {
private:
int fact(int n){
int res=1;
for(int i=2;i<=n;i++)
res=res*i;
return res;
}
char helper(string & s, int & k){
int temp=fact(s.size()-1),i=(k-1)/temp;
char res=s[i];
s.erase(i,1);
k=k-i*temp;
return res;
}
public:
string getPermutation(int n, int k) {
string s=string("123456789").substr(0,n);
string res(n,' ');
for(int i=0;i<n;i++)
res[i]=helper(s,k);
return res;
}
};