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.

此题的要求是,需要我们在一个代表若干时间点的字符串列表中,找到相差最小的两个时间点的差值。

最直接的方式就是计算所有时间点距离零点所过去的分钟数,并进行排序,再计算两两之差。取最小即可,此种方式在时间和空间上的消耗都是比较大的,而且没有利用题目中的条件进行进一步的分析。

而比较好的做法是:

因为24个小时所对应的时间点只有24*60种,也就是1440种。所以完全可以建立一个boolean数组,用来标记状态。

  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
第543次迭代所得的prev为543
第601次迭代所得的最小值为58
第601次迭代所得的first为543, last为601
第601次迭代所得的prev为601
第1436次迭代所得的最小值为58
第1436次迭代所得的first为543, last为1436
第1436次迭代所得的prev为1436
所得的最小值为58

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

此题其实是一道非常容易理解的排列组合题,但由于题目描述过于庞大,往往会给人一种此题很难的感觉,下面用归纳推理的方式对此题进行解决:

当n==1时,由0~10之间的数字所组成的数字均符合题目要求,所以返回10

当n==2时,第一个位置上的数不能为0,所以有9种情况,对于第二个数,可以取0,所以也是9种情况,故有

9*9=81

种情况,再加上n==1时的10种情况,所以返回91

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"]
]

Analysis

思路比较简单,只需要先检查(start,i)区间内是否为回文串,如果是,则令start自增1后,进行递归即可,代码如下:

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],
]

Analysis

实质上此题就是求subsets的变形,只需要控制好子集中的元素个数即可,代码如下:

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!
Added [1, 2] as an answer!
Incremented element at index 1
[1, 3]
Combination found!
Added [1, 3] as an answer!
Incremented element at index 1
[1, 4]
Combination found!
Added [1, 4] as an answer!
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!
Added [2, 3] as an answer!
Incremented element at index 1
[2, 4]
Combination found!
Added [2, 4] as an answer!
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!
Added [3, 4] as an answer!
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

此题虽然在分类上属于backtracking,但如果直接利用回溯法求全排列又会造成在n较大的情况下超时,所以不能直接利用回溯法,而是需要分析其中的规律,从而直接构造出排列。

假设

n=4

则全排列有

4*3*2*1=24

种可能性,设此时

k=17

因为以1,2开头的排列只有

3*2*1*2=12

恰好小于17,所以可以确定所求排列的开头必然是3在确定开头为3之后,将其从原字符串中删除,还剩下

17-12=5

种排列,字符串中还剩下124,以上述方法确定第二个元素为4,重复上述过程,直到得出所求排列即可。

代码如下:

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;
    }
};