Posted on | In , |
Words count in article: 638 | Reading time ≈ 3

Problem Description

As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem.

There are two machines A and B. Machine A has n kinds of working modes, which is called mode_0, mode_1, …, mode_n-1, likewise machine B has m kinds of working modes, mode_0, mode_1, … , mode_m-1. At the beginning they are both work at mode_0.

For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode_3 or in machine B at mode_4, job 1 can either be processed in machine A at mode_2 or in machine B at mode_4, and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y), which means it can be processed either in machine A at mode_x, or in machine B at mode_y.

Obviously, to accomplish all the jobs, we need to change the machine’s working mode from time to time, but unfortunately, the machine’s working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.

Input

The input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n, m (n, m < 100) and k (k < 1000). The following k lines give the constrains of the k jobs, each line is a triple: i, x, y.

The input will be terminated by a line containing a single zero.

Output

The output should be one integer per line, which means the minimal times of restarting machine.

Sample Input

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0
``` 

# Sample Output
3

# 思路： 
这很明显是有张二分图。              
点：A模式，B模式；                  
边：job_k可由机器A的模式i转化成机器B的模式j（可以理解是任务）                   
那么问题就转化成是否存在一个最小点集，使得所有的边都至少和该点集的一个点相联系。                    
这就是最小顶点覆盖数                

最小点覆盖=最大匹配

匈牙利算法

```cpp
#include<stdio.h>  
#include<string.h>  
#include<vector>  
#include<algorithm>  
using namespace std;  
vector<int>map[1010];  
int used[1010],pipei[1010];  
int find(int x)  
{  
    for(int i=0;i<map[x].size();i++)  
    {  
        int y=map[x][i];  
        if(!used[y])  
        {  
            used[y]=1;  
            if(!pipei[y]||find(pipei[y]))  
            {  
                pipei[y]=x;  
                return 1;  
            }  
        }  
    }  
    return 0;  
}  
int main()  
{  
    int n;  
    while(scanf("%d",&n),n)  
    {  
        int a,b,c;  
        int m,k;  
        memset(pipei,0,sizeof(pipei));  
        scanf("%d%d",&m,&k);  
        for(int i=0;i<=n;i++)  
        map[i].clear();  
        while(k--)  
        {  
            scanf("%d%d%d",&a,&b,&c);  
            if(b&&c)  
            map[b].push_back(c);  
        }  
        int sum=0;  
        for(int i=0;i<n;i++)  
        {  
            memset(used,0,sizeof(used));  
            sum+=find(i);  
        }  
        printf("%d\n",sum);  
    }  
    return 0;  
}

Posted on | In , |
Words count in article: 816 | Reading time ≈ 4

Problem Description

The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.

The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.

Input

The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:

‘X’: a block of wall, which the doggie cannot enter;
‘S’: the start point of the doggie;
‘D’: the Door; or
‘.’: an empty block.

The input is terminated with three 0’s. This test case is not to be processed.

Output

For each test case, print in one line “YES” if the doggie can survive, or “NO” otherwise.

Sample Input

1
2
3
4
5
6
7
8
9
10
4 4 5 
S.X. 
..X. 
..XD 
.... 
3 4 5 
S.X. 
..X. 
...D 
0 0 0

Sample Output

1
2
NO 
YES

奇偶性剪枝

我们可以把map看成是下图中的样子：

1
2
3
4
5
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1

从0走一步必然走到1，从1走一步必然走到0

即：

  • 0->1或1->0 必然为奇数步
  • 0->0或 1->1必然为偶数步

所以： 当遇到从0走向0而要求时间为奇数的，或者0走向1要求时间为偶数的情况，可直接判断NO

此外

由距离公式以及上述推断，当前位置与所剩时间的奇偶性也要相同。

即剩余的时间t的奇偶性必定与abs(xi - x0) + abs(yi - y0)的奇偶性相同。不然就无法到达

最后就是DFS加上奇偶性剪枝

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<stdio.h>
#include<stdlib.h>
bool flag;
int n,m,t,i,j,x1,y1,x2,y2,num;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};  //设置四个方向，分别是左、右、下、上
char str[8][8];
void dfs(int k,int l,int tc)
{
    int i;
    if(tc==t && k==x2 &&l==y2)
       flag=true;
    if(flag) 
	   return;  
    if((abs(x2-k)+abs(y2-l))%2!=(t-tc)%2) 
	   return;   //奇偶性剪枝的判断条件
    for(i=0;i<4;i++)
    {
        int xx=k+dx[i];
        int yy=l+dy[i];
        if(xx>=0 && xx<n && yy>=0 && yy<m && str[xx][yy]!='X')
        {
            str[xx][yy]='X';
            dfs(xx,yy,tc+1);
            str[xx][yy]='.';    //此方向如果不行的话就回溯
        }
    }
}
int main()
{
    while (scanf("%d%d%d",&n,&m,&t))
    {
        if(n==0 && m==0 && t==0)
            break;
        num=0;
        flag=false;
        for(i=0;i<n;i++)
        {
        	scanf("%s",str[i]);
            for(j=0;j<m;j++)
            {
                if(str[i][j]=='S')
                {
                    x1=i;y1=j;
                }
                else if(str[i][j]=='D')
                {
                    x2=i;y2=j;
                    num++;
                }
                else if(str[i][j]=='.')
                {
                    num++;
                }
            }
        }
        str[x1][y1]='X';
        if(num>=t)
          dfs(x1,y1,0);
        if(flag) 
            printf("YES\n");
        else 
            printf("NO\n");
    }
    return 0;
}

Posted on | In , |
Words count in article: 313 | Reading time ≈ 1

Problem Description

You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.

Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string.

Output

There should be one line per test case containing the length of the largest string found.

Sample Input

2
3
ABCD
BCDFF
BRCD
2
rose
orchid

Sample Output

2
2

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int MAXN = 0x3f3f3f3f;
const int MINN = 0xc0c0c0c0;
const int maxn = 1e2 + 5;
string s[maxn];

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int i, j, k;
        int sub;
        int len = MAXN;
        for (i = 0; i < n; i++)
        {
            cin >> s[i];
            if (s[i].size() < len)
            {
                len = s[i].size();
                sub = i;
            }
        }
        int ans = 0;
        for (i = s[sub].size(); i > 0; i--)
        {
            for (j = 0; j < s[sub].size() - i + 1; j++)
            {
                string s1, s2;
                s1 = s[sub].substr(j, i);
                s2 = s1;
                reverse(s2.begin(), s2.end());
                for (k = 0; k < n; k++)
                {
                    if (s[k].find(s1, 0) == -1 && s[k].find(s2, 0) == -1)
                        break;
                }
                if (k == n && s1.size() > ans)
                    ans = s1.size();
            }
        }
        cout << ans << endl;
    }
}

Posted on | In , |
Words count in article: 338 | Reading time ≈ 2

Implement a trie with insert, search, and startsWith methods.

1
2
3
4
5
6
7
8
9
10
Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

  • You may assume that all inputs are consist of lowercase letters a-z.
  • All inputs are guaranteed to be non-empty strings.
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class TrieNode {
public:
    TrieNode(bool b = false){
        is_word = b;
        memset(next, 0, sizeof(next));
    }
    TrieNode  *next[26];
    bool is_word;
};

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode;
    }
    
    ~Trie(){
        clear(root);
    }
    /** Inserts a word into the trie. */
    void insert(string word) {
        auto temp = root;
        for(int i = 0; i < word.size(); i++){
            if(temp->next[word[i] - 'a'] == nullptr)
                temp->next[word[i] - 'a'] = new TrieNode;
            temp = temp->next[word[i]-'a'];
        }
        temp->is_word = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        auto temp = find_string(word);
        if(temp != nullptr && (temp->is_word))
            return true;
        else
            return false;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        auto temp = find_string(prefix);
        if(temp != nullptr)
            return true;
        else
            return false;
    }

private:
    TrieNode *root;
    TrieNode *find_string(std::string word){
        auto temp = root;
        for(int i = 0; i < word.size(); i++){
            if(temp->next[word[i] - 'a'] != nullptr)
                temp = temp -> next[word[i] - 'a'];
            else {
                temp = nullptr;
                break;
            }
        }
        return temp;
    }
    void clear(TrieNode *root){
        for(int i = 0; i < 26; i++){
            if(root->next[i] != nullptr){
                clear(root->next[i]);
            }
        }
        delete root;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * bool param_2 = obj.search(word);
 * bool param_3 = obj.startsWith(prefix);
 */

Posted on | In , |
Words count in article: 183 | Reading time ≈ 1

Given a collection of intervals, merge all overlapping intervals.

1
2
3
4
5
6
7
8
9
10
Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
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
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    bool static compare(const Interval &a,const Interval &b){
        return a.start<b.start;
    }
    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(),intervals.end(),compare);
        int i,size = intervals.size();
        for(i=1;i<size;){
            if(intervals[i].start <= intervals[i-1].end){
                intervals[i-1].end = max(intervals[i].end,intervals[i-1].end);
                intervals.erase(intervals.begin() + i);
                size--;
            }
            else{
                i++;
            }
        }
        return intervals;
    }
};

Posted on | In , |
Words count in article: 167 | Reading time ≈ 1

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:

  • You may assume that duplicates do not exist in the tree.

For example, given

1
2
3
4
5
6
7
8
9
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    TreeNode* buildTree(const vector<int>& preorder, int p_l, int p_h, const vector<int>& inorder, int i_l, int i_h)
    {
        if(i_l > i_h) return NULL;
        int val = preorder[p_l];
        TreeNode *root = new TreeNode(val);
        int i = i_l;
        for(; i <= i_h; i++)
            if(inorder[i] == val) break;
        root->left = buildTree(preorder, p_l+1, p_l+i-i_l, inorder, i_l, i-1);
        root->right = buildTree(preorder, p_l+i-i_l+1, p_h, inorder, i+1, i_h);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTree(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
};

Posted on | In , |
Words count in article: 211 | Reading time ≈ 1

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

1
2
3
4
5
6
7
8
9
Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1

Note:

  • You may assume that you have an infinite number of each kind of coin.
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
class Solution {
public:
    int min(int a,int b){
        return a<b?a:b;
    }
    int calculate(vector<int>& coins, int amount,int count[]){
        int coinsCount=coins.size(),i;
        for(i=0;i<coinsCount;i++){
            int j;
            for(j=0;j<=amount;j++){
                if(j-coins[i]>=0)
                    count[j] = min(count[j],1+count[j-coins[i]]);
            }
        }
        if(count[amount]==INT_MAX-1)
            return -1;
        return count[amount];
    }
    int coinChange(vector<int>& coins, int amount) {
        int count[amount+1]={0};
        int i;
        for(i=1;i<=amount;i++)
            count[i]=INT_MAX-1;
        int index[amount+1];
        return calculate(coins,amount,count);
    }
};

Posted on | In , |
Words count in article: 237 | Reading time ≈ 1

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.
Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool wordBreak(string s, unordered_set<string> &dict) {
    if(dict.size()==0) return false;
    
    vector<bool> dp(s.size()+1,false);
    dp[0]=true;
    
    for(int i=1;i<=s.size();i++)
    {
        for(int j=i-1;j>=0;j--)
        {
            if(dp[j])
            {
                string word = s.substr(j,i-j);
                if(dict.find(word)!= dict.end())
                {
                    dp[i]=true;
                    break; //next i
                }
            }
        }
    }
    
    return dp[s.size()];
}

Posted on | In , |
Words count in article: 227 | Reading time ≈ 1

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

  • Each of the array element will not exceed 100.
  • The array size will not exceed 200.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
 

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

DFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool backtrack(vector<int>& nums, int start, int target) {
        if (target <= 0) return target == 0;
        for (int i = start; i < nums.size(); i++) 
            if (backtrack(nums, i + 1, target - nums[i])) return true;
        return false;
    }
    
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        return !(sum & 1) && backtrack(nums, 0, sum >> 1);
    }
};

DP:

1
2
3
4
5
6
7
8
9
10
bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0), target = sum >> 1;
    if (sum & 1) return false;
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    for(auto num : nums) 
        for(int i = target; i >= num; i--)
            dp[i] = dp[i] || dp[i - num];
    return dp[target];
}

Posted on | In , |
Words count in article: 624 | Reading time ≈ 3

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

1
2
3
4
5
6
7
8
9
10
11
12
13
Example 1:

Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.
Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Note:

  • The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  • You may assume that there are no duplicate edges in the input prerequisites.

BFS

BFS uses the indegrees of each node. We will first try to find a node with 0 indegree. If we fail to do so, there must be a cycle in the graph and we return false. Otherwise we set its indegree to be -1 to prevent from visiting it again and reduce the indegrees of its neighbors by 1. This process will be repeated for n (number of nodes) times.

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
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        graph g = buildGraph(numCourses, prerequisites);
        vector<int> degrees = computeIndegrees(g);
        for (int i = 0; i < numCourses; i++) {
            int j = 0;
            for (; j < numCourses; j++) {
                if (!degrees[j]) {
                    break;
                }
            }
            if (j == numCourses) {
                return false;
            }
            degrees[j]--;
            for (int v : g[j]) {
                degrees[v]--;
            }
        }
        return true;
    }
private:
    typedef vector<vector<int>> graph;
    
    graph buildGraph(int numCourses, vector<pair<int, int>>& prerequisites) {
        graph g(numCourses);
        for (auto p : prerequisites) {
            g[p.second].push_back(p.first);
        }
        return g;
    }
    
    vector<int> computeIndegrees(graph& g) {
        vector<int> degrees(g.size(), 0);
        for (auto adj : g) {
            for (int v : adj) {
                degrees[v]++;
            }
        }
        return degrees;
    }
};

DFS

For DFS, in each visit, we start from a node and keep visiting its neighbors, if at a time we return to a visited node, there is a cycle. Otherwise, start again from another unvisited node and repeat this process. We use todo and done for nodes to visit and visited nodes.

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
34
35
36
37
38
39
40
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        graph g = buildGraph(numCourses, prerequisites);
        vector<bool> todo(numCourses, false), done(numCourses, false);
        for (int i = 0; i < numCourses; i++) {
            if (!done[i] && !acyclic(g, todo, done, i)) {
                return false;
            }
        }
        return true;
    }
private:
    typedef vector<vector<int>> graph;
    
    graph buildGraph(int numCourses, vector<pair<int, int>>& prerequisites) {
        graph g(numCourses);
        for (auto p : prerequisites) {
            g[p.second].push_back(p.first);
        }
        return g;
    }
    
    bool acyclic(graph& g, vector<bool>& todo, vector<bool>& done, int node) {
        if (todo[node]) {
            return false;
        }
        if (done[node]) {
            return true;
        }
        todo[node] = done[node] = true;
        for (int v : g[node]) {
            if (!acyclic(g, todo, done, v)) {
                return false;
            }
        }
        todo[node] = false;
        return true;
    }
};