1: int singleNumber(int A[], int n) {
2: int left = A[0];
3: for(int i =1; i< n; i++)
4: {
5: left = left ^ A[i];
6: }
7: return left;
8: }
1: int candy(vector<int> &ratings) {
2: vector<int> candy(ratings.size());
3: candy[0] = 1;
4: int i =1;
5: for (; i < ratings.size(); ++i)
6: {
7: if (ratings[i] > ratings[i-1]) //递增
8: {
9: candy[i] = candy[i - 1] + 1;
10: }
11: if (ratings[i] == ratings[i-1]) //平行
12: {
13: candy[i] = 1;
14: }
15: if (ratings[i] < ratings[i - 1]) //递减
16: {
17: candy[i] = candy[i - 1] - 1;
18: }
19: if (i<ratings.size()-1 && ratings[i] < ratings[i-1] && ratings[i] <=ratings[i+1])
20: ReAdjustCandy(ratings, candy, i);
21: }
22: if (ratings[i-1] < ratings[i-2])
23: ReAdjustCandy(ratings, candy, ratings.size() - 1);
24: int total = 0;
25: std::for_each(candy.begin(), candy.end(), [&](int n){
26: total += n;
27: });
28: return total;
29: }
30: void ReAdjustCandy(vector<int>& ratings, vector<int>& candy, int startIndex)
31: {
32: int k = startIndex;
33: int diff = 1 - candy[k];
34: while (k > 0 && ratings[k - 1] > ratings[k])
35: {
36: candy[k] = candy[k] + diff;
37: k--;
38: }
39: if (diff > 0) candy[k] += diff;
40: }
gas[i].cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. 1: class Solution {
2: public:
3: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
4: vector<int> diff(gas.size());
5: for(int i =0; i< gas.size(); ++i)
6: {
7: diff[i] = gas[i] - cost[i];
8: }
9:
10: int leftGas=0, sum =0, startnode=0;
11: for(int i =0; i<gas.size(); ++i)
12: {
13: leftGas += diff[i];
14: sum += diff[i];
15: if(sum <0) //只要小于0就不可能是解
16: {
17: startnode = i+1;
18: sum=0;
19: }
20: }
21: if(leftGas <0)
22: return -1;
23: else
24: return startnode;
25: }
26: };
1: void ListPermutation(string sample, int depth, string& result)2: {3: if(depth == sample.size())4: {5: prinf("%s\r\n", result.c_str());6: return;7: }8:9: // process low-case char10: result.push_back(sample[depth]);11: ListPermutation(sample, depth+1, result);12: result.pop_back();13:14: //process up-case char15: result.push_back(sample[depth]-32);16: ListPermutation(sample, depth+1, result);17: result.pop_back();18: }
1: void ListPermutation(string sample)2: {3: int L = sample.size();4: long end = pow(2, L) -1;5: for(int i =0; i< end; i++)6: {7: // Convert Dec to Binary,8: // return a string to represent binary data with size L9: string binaryRep = ConvertDecToBinany(i, L);10:11: string output;12: for(int j=0; j<L; j++)13: {14: if(binaryRep[j] == '0') //low case15: {16: output.push_back(sample[j]);17: }18: else19: {20: output.push_back(sample[j]-32);21: }22: }23: printf("%s\r\n", output.c_str());24: }25: }
|
Problem Statement
|
|||||||||||||
|
|
 F is a function that is defined on all real numbers from
the closed interval [1,N]. You are given a vector <int> Y with N
elements. For each i (1 <= i <= N) we have F(i) = Y[i-1]. Additionally,
you know that F is piecewise linear: for each i, on the interval [i,i+1] F is
a linear function. The function F is uniquely determined by this information.
For example, if F(4)=1 and F(5)=6 then we must have F(4.7)=4.5.As another example, this is the plot of the function F for Y = {1, 4, -1, 2}. You are also given a vector <int> query. For each i, compute the number of solutions to the equation F(x) = query[i]. Note that sometimes this number of solutions can be infinite. Return a vector <int> of the same length as query. For each i, element i of the return value should be -1 if the equation F(x) = query[i] has an infinite number of solutions. Otherwise, element i of the return value should be the actual number of solutions this equation has. |
||||||||||||
|
Definition
|
|||||||||||||
|
|
|
||||||||||||
|
|
|||||||||||||
|
Constraints
|
|||||||||||||
|
-
|
Y will contain between 2 and 50 elements,
inclusive.
|
||||||||||||
|
-
|
Each element of Y will be between -1,000,000,000
and 1,000,000,000, inclusive.
|
||||||||||||
|
-
|
query will contain between 1 and 50 elements,
inclusive.
|
||||||||||||
|
-
|
Each element of query will be between
-1,000,000,000 and 1,000,000,000, inclusive.
|
||||||||||||
|
Examples
|
|||||||||||||
|
0)
|
|||||||||||||
|
|
|
||||||||||||
|
1)
|
|||||||||||||
|
|
|
||||||||||||
|
2)
|
|||||||||||||
|
|
|
||||||||||||
|
3)
|
|||||||||||||
|
|
|
||||||||||||
1: #include<vector>
2: using namespace std;
3: class PiecewiseLinearFunctionDiv2
4: {
5: public:
6: vector <int> countSolutions(vector <int> Y, vector <int> query)
7: {
8: vector<int> result;
9: for(int i =0; i< query.size(); i++)
10: {
11: int searchNum = query[i];
12: int start = 0;
13: int solution=0;
14: if(searchNum == Y[start]) solution++;
15: for(int j =1; j< Y.size(); j++)
16: {
17: if(max(Y[start], Y[j]) > searchNum && min( Y[start], Y[j]) < searchNum)
18: {
19: solution++;
20: }
21: if(searchNum == Y[j])
22: {
23: if(searchNum == Y[start])
24: {
25: solution =-1;
26: break;
27: }
28: solution++;
29: //j++;
30: }
31: start = j;
32: }
33: result.push_back(solution);
34: }
35: return result;
36: }
37: };
Problem Statement 1000P |
|||||||||||||
| In this problem, all strings consist of uppercase English letters
only. That is, there are 26 distinct letters. The weight of a string S can be computed as follows: for each letter that occurs at least once in S, its leftmost and rightmost occurrences L and R are found and the weight is increased by R-L. For example, if S="ABCACAZ", the weight of S is (5-0) + (1-1) + (4-2) + (6-6) = 7. (The leftmost occurrence of 'A' is at the index L=0, the rightmost one is at R=5, so 'A' contributes 5-0 = 5 to the weight of S. The only 'B' contributes 0, the pair of 'C's adds 2, and the only 'Z' adds 0.) You are given a int L. Consider all strings of length L. Compute the weight of each of these strings. The strings with the minimum weight among all of them are called light. Your task is to count the number of light strings of length L. Since this count may be very large, return it modulo 1,000,000,009. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
| - | L will be between 1 and 1000, inclusive. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
1: int mod = 1000000009;
2: class StringWeightDiv2
3: {
4: public:
5: long Permutation(int n, int m)
6: {
7: long result=1;
8: for(int i =0; i< m; i++)
9: {
10: result*=n;
11: result%=mod;
12: n--;
13: }
14: return result;
15: }
16: int countMinimums(int L)
17: {
18: if(L<=26) return Permutation(26, L);
19: else
20: return Permutation(L-1, 25)*26%mod;
21: }
22: };
Problem Statement 250P |
|||||||||||||
| You are given two strings: init and goal. Both init
and goal contain lowercase letters only. Additionally, init
does not contain the character 'z'.
Your goal is to transform init into goal. The only operation you are allowed to do is to insert the character 'z' anywhere into init. You can repeat the operation as many times as you want, and each time you can choose any position where to insert the 'z'. For example, if init="fox", you can transform it to "fzox" in one operation. Alternately, you can transform "fox" into "zzzfoxzzz" in six operations. It is not possible to transform "fox" into any of the strings "fx", "foz", "fxo", "foxy". Return "Yes" (quotes for clarity) if it is possible to transform init into goal. Otherwise, return "No". |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Notes |
|||||||||||||
| - | Note that the return value is case sensitive. | ||||||||||||
Constraints |
|||||||||||||
| - | init and goal will each contain between 1 and 50 characters, inclusive. | ||||||||||||
| - | Each character of init and goal will be a lowercase letter ('a'-'z'). | ||||||||||||
| - | init will not contain the letter 'z'. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
| 4) | |||||||||||||
|
|||||||||||||
| 5) | |||||||||||||
|
|||||||||||||
| 6) | |||||||||||||
|
|||||||||||||
1: #include <string>
2: #include <cstring>
3: using namespace std;
4: class InsertZ
5: {
6: public:
7: string canTransform(string init, string goal)
8: {
9: int i =0, j=0;
10: while(i<init.size() && j<goal.size())
11: {
12: if(goal[j] == 'z')
13: {
14: j++;
15: continue;
16: }
17: if(init[i]!=goal[j])
18: {
19: return "No";
20: }
21: i++;
22: j++;
23: }
24: if(i<init.size())
25: return "No";
26: while(j<goal.size())
27: {
28: if(goal[j] != 'z')
29: return "No";
30: j++;
31: }
32: return "Yes";
33: }
34: };
Problem Statement 500P |
|||||||||||||
| Little Fox Jiro is standing at the bottom of a long flight of
stairs. The bottom of the stairs has number 0, the bottommost step
has number 1, the next step has number 2, and so on. The staircase
is so long that Jiro is guaranteed not to reach its top.
Jiro will now perform N consecutive actions. The actions are numbered 1 through N, in order. When performing action X, Jiro chooses between two options: either he does nothing, or he jumps exactly X steps up the stairs. In other words, if Jiro starts performing action X standing on step Y, he will end it either on step Y, or on step Y+X. For example, if N=3, Jiro will make three consecutive choices: whether or not to jump 1 step upwards, 2 steps upwards, and then 3 steps upwards. One of the steps is broken. The number of this step is badStep. Jiro cannot jump onto this step. You are given the ints N and badStep. Compute and return the number of the topmost step that can be reached by Jiro. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
| - | N will be between 1 and 2,000, inclusive. | ||||||||||||
| - | badStep will be between 1 and 4,000,000, inclusive. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
| 4) | |||||||||||||
|
|||||||||||||
1: class JumpFurther
2: {
3: public:
4: int furthest(int N, int badStep)
5: {
6: int k=1;
7: for(; k<=N; k++)
8: {
9: int start=0, end = N-1;
10: int index=-1;
11: while(start<=end) //这里二分查找m
12: {
13: int mid = (start+end)/2;
14: int result = (2*k + mid)*(mid+1);
15: if( result == 2*badStep)
16: {
17: index = mid;
18: break;
19: }
20: else if(result < 2*badStep)
21: {
22: start = mid+1;
23: }
24: else
25: {
26: end = mid-1;
27: }
28: }
29: if(index == -1)
30: {
31: break;
32: }
33: }
34: return (k+N)*(N-k+1)/2;
35: }
36: };
Problem Statement 1000P |
|||||||||||||
| There is a H times W rectangle divided into unit cells. The rows
of cells are numbered 0 to H-1 from top to bottom, and the columns
are numbered 0 to W-1 from left to right. The corners of cells are
called lattice points. By definition, there are (H+1)*(W+1)
lattice points in our rectangle.
Each of the four edges of each cell is painted white. Additionally, in each cell exactly one of the two diagonals is painted white. Two lattice points are called adjacent if they are connected by a white line segment. (In other words, consecutive corners of a cell are always adjacent, opposite corners of a cell are adjacent if and only if they are connected by a painted diagonal, and no other pairs of lattice points are adjacent.) We now want to color each of the lattice points using one of three available colors: red, green, or blue. There is only one constraint: adjacent lattice points are not allowed to share the same color. You are given a String[] cells with H elements, each consisting of W characters. If cells[i][j] is 'N', there is a diagonal line from the top left to the bottom right corner in the cell in row i, column j. If cells[i][j] is 'Z', there is a diagonal line from the top right to the bottom left corner in the cell in row i, column j. If there is at least one valid way to color all lattice points, return "Yes" (quotes for clarity). Otherwise, return "No". |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
| - | cells will contain between 1 and 50 elements, inclusive. | ||||||||||||
| - | Each element of cells will contain between 1 and 50 characters, inclusive. | ||||||||||||
| - | All elements of cells will contain the same number of characters. | ||||||||||||
| - | Each character of cells will be either 'N' or 'Z'. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
| 4) | |||||||||||||
|
|||||||||||||
1: #include <string>
2: #include <vector>
3: using namespace std;
4: class ThreeColorabilityEasy
5: {
6: public:
7: string isColorable(vector <string> cells)
8: {
9: int row = cells.size();
10: int col = cells[0].size();
11: if(row == 1 || col ==1) return "Yes";
12: for(int i =0; i<row-1; i++)
13: {
14: for(int j=0; j<col-1; j++)
15: {
16: int count=0;
17: if(cells[i][j] == 'N') count++;
18: if(cells[i][j+1] == 'N') count++;
19: if(cells[i+1][j] == 'N') count++;
20: if(cells[i+1][j+1] == 'N') count++;
21: if(count ==1 || count ==3) return "No";
22: }
23: }
24: return "Yes";
25: }
26: };
250PProblem Statement |
|||||||||||||
| Manao has N cards arranged in a sequence. He numbered them from left
to right with numbers from 0 to N-1. Each card is colored black on
one side and white on the other. Initially, each of the cards may
lie on a different side. That is, some of the cards (possibly none
or all of them) will be black side up and others will be white side
up. Manao wants to flip some cards over to obtain an alternating
configuration: every pair of successive cards must be of different
colors. You are given a string cardFront consisting of N characters. For each i, character i of cardFront is 'B' if card i lies black side up, and 'W' otherwise. Count and return the minimum number of cards which must be flipped to obtain an alternating configuration. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
| - | cardFront will be between 3 and 50 characters long, inclusive. | ||||||||||||
| - | Each character in cardFront will be either 'B' or 'W'. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
1: #include <string>
2: using namespace std;
3: class BlackAndWhiteSolitaire
4: {
5: public:
6: int minimumTurns(string cardFront);
7: };
8: int BlackAndWhiteSolitaire::minimumTurns(string cardFront)
9: {
10: int len = cardFront.size();
11: int turn1 =0, turn2 =0;
12: string sample1 = "BW";
13: string sample2 = "WB";
14: for(int i =0; i< len; i++)
15: {
16: if(sample1[i%2] != cardFront[i])
17: turn1++;
18: if(sample2[i%2] != cardFront[i])
19: turn2++;
20: }
21: return min(turn1, turn2);
22: }
Problem Statement |
|||||||||||||
| There is a long narrow storehouse. The storehouse is divided into a
sequence of N identical sectors, labeled 0 through N-1. Each sector
is large enough to contain a single container. Currently, some
sectors are empty and some sectors are filled by containers. The
storehouse also contains a surveillance system that is described
below. We are going to break into the storehouse. As a part of preparation for the heist, we already found out some information about the warehouse. In particular, we know exactly how the containers are currently placed in the warehouse. You are given a String containers consisting of N characters. For each i, character i of containers is 'X' if sector i contains a container, and it is '-' if sector i is empty. We also discovered some information about the surveillance system. The system consists of several hidden cameras. You are given a int L with the following meaning: Each of the cameras monitors exactly L consecutive sectors. The segments of sectors monitored by different cameras might overlap, but no two cameras watch exactly the same segment. (In other words, each sector may be monitored by multiple cameras, but each camera monitors a different set of consecutive sectors.) Finally, we know something about what the cameras currently see. You are given a int[] reports. Each element of reports corresponds to one of the cameras (in no particular order). More precisely, reports[i] is the number of containers stored in the sectors monitored by the corresponding camera. It is guaranteed that all our information is correct and consistent. Your task is to use the provided information to deduce which sectors are monitored by at least one surveillance camera. Return a String containing N characters. For each i, character i of the return value should be one of '+', '?', and '-'. Character '+' represents that sector i is certainly monitored by at least one camera. Character '-' represents that sector i is certainly not monitored by any of the cameras. Character '?' represents the remaining case: given the information we have, it is possible that sector i is monitored, but it is also possible that it is not monitored. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
| - | containers will contain N elements, where N is between 1 and 50, inclusive. | ||||||||||||
| - | Each character in containers will be either 'X' or '-'. | ||||||||||||
| - | L will be between 1 and N, inclusive. | ||||||||||||
| - | reports will contain between 1 and N-L+1 elements, inclusive. | ||||||||||||
| - | Each element of reports will be between 0 and L, inclusive. | ||||||||||||
| - | The given information will be consistent. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
| 4) | |||||||||||||
|
|||||||||||||
1: #include <vector>
2: #include <string>
3: #include <map>
4: #include <bitset>
5: using namespace std;
6: class SurveillanceSystem
7: {
8: public:
9: string getContainerInfo(string containers, vector <int> reports, int L)
10: {
11: sort(reports.begin(), reports.end());
12: string target(containers.size(), '-');
13: map<int, vector<int> > lengthDir;
14: int pre=0, cur = 0, count=0; //two-pointer scan
15: for(int i =0; i<L; i++)
16: {
17: if(containers[i] =='X')
18: count++;
19: pre++;
20: }
21: vector<int>* dir = &lengthDir[count];
22: dir->push_back(cur);
23: while(pre< containers.size())
24: {
25: if(containers[pre] == 'X')
26: count++;
27: if(containers[cur] == 'X')
28: count--;
29: pre++;
30: cur++;
31: vector<int>* dir = &lengthDir[count];
32: dir->push_back(cur);
33: }
34: bitset<51> doubtless, doubt;
35: int expectCount;
36: int report;
37: for(int length =0; length<reports.size(); length++)
38: {
39: expectCount=1;
40: report = reports[length];
41: while(length<reports.size()-1 && reports[length] == reports[length+1])
42: {
43: expectCount++;
44: length++;
45: }
46: if(expectCount < lengthDir[report].size())// for exmple, expect 1 camera watching 3 storages, but there are muiltiple choice
47: {
48: int counter[51];
49: memset(counter, 0, sizeof(counter));
50: for(int k =0; k< lengthDir[report].size(); k++ )
51: {
52: for(int j =0; j<L; j++)
53: {
54: counter[lengthDir[report][k] +j] ++;
55: }
56: }
57: for(int k =0; k< target.size(); k++)
58: {
59: if(counter[k] ==0) continue;
60: if(expectCount > lengthDir[report].size() - counter[k])
61: doubtless.set(k,1);
62: else
63: doubt.set(k,1);
64: }
65: }
66: else
67: {
68: for(int k =0; k< lengthDir[report].size(); k++ )
69: {
70: for(int j =0; j<L; j++)
71: {
72: doubtless.set(lengthDir[report][k]+j,1);
73: }
74: }
75: }
76: }
77: for(int i =0; i< target.size();i++)
78: {
79: if(doubtless[i] ==1)
80: target[i] ='+';
81: else if(doubt[i] ==1)
82: target[i] ='?';
83: }
84: return target;
85: }
86: };
Problem Statement |
|||||||||||||
|
This problem statement contains superscripts and/or subscripts.
These may not display properly outside the applet. Manao is studying graph theory and simple cycles in particular. A simple cycle of length L ≥ 3 in graph G is a sequence of vertices (v0, v1, ..., vL-1) such that all v0, v1, ..., vL-1 are pairwise distinct and for each i=0..L-1, an edge between vi and v(i+1) mod L exists in G. Manao is interested in graphs formed by connecting two trees. The connection process is as follows. Manao takes two trees composed of N vertices each. The vertices in each tree are labeled from 0 to N - 1. Then, he generates some permutation P of numbers from 0 to N - 1. Finally, the graph is formed by connecting vertex i of the first tree to vertex P[i] of the second tree, for each i from 0 to N - 1. To remove ambiguity, the vertices of the first tree within the graph are referred to as A0, A1, ..., AN-1 and the vertices of the second graph are referred to as B0, B1, ..., BN-1. Manao wants to know the maximum number of simple cycles of length K which the resulting graph could contain if he chooses P optimally. You are given two String[]s, tree1 and tree2. Both contain N elements, each of them N characters long. The j-th character in the i-th element of tree1 is 'X' if vertices i and j in the first tree are connected and '-' otherwise. tree2 describes the second tree in the same fashion. Compute and return the maximum possible number of simple cycles of length K in the graph formed by connecting the two given trees as described above. Two simple cycles are equal if one of them can be cyclically shifted, or reversed and cyclically shifted, to coincide with the second. According to this definition, (1, 2, 3, 4), (2, 3, 4, 1) and (3, 2, 1, 4) are all equal. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
| - | tree1 and tree2 will each contain N elements, where N is between 1 and 9, inclusive. | ||||||||||||
| - | Each element of tree1 and tree2 will be N characters long. | ||||||||||||
| - | Each element of tree1 and tree2 will consist of 'X' and '-' characters only. | ||||||||||||
| - | tree1[i][i] and tree2[i][i] will be '-' for each i between 0 and N-1. | ||||||||||||
| - | tree1[i][j] will be equal to tree1[j][i] for each i, j between 0 and N-1. | ||||||||||||
| - | tree2[i][j] will be equal to tree2[j][i] for each i, j between 0 and N-1. | ||||||||||||
| - | Both tree1 and tree2 will describe a graph which is a tree. | ||||||||||||
| - | K will be between 3 and 7, inclusive. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
| 4) | |||||||||||||
|
|||||||||||||
