-
第 61 楼 / webdriver
- 时间: 2014-9-23 14:02Now comes the solution (in C++) ...
Solution 1 uses constant extra space.
代码: /**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
return copyRandomList_1(head);
}
RandomListNode *copyRandomList_1(RandomListNode *head) {
for (RandomListNode *cur = head; cur; cur = cur->next->next) {
RandomListNode *newNode = new RandomListNode(cur->label);
newNode->next = cur->next;
cur->next = newNode;
}
for (RandomListNode *cur = head; cur; cur = cur->next->next)
if (cur->random)
cur->next->random = cur->random->next;
RandomListNode dummy(0), *curNew = &dummy;
for (RandomListNode *cur = head; cur; cur = cur->next) {
curNew->next = cur->next;
curNew = curNew->next;
cur->next = cur->next->next;
}
return dummy.next;
}
RandomListNode *copyRandomList_2(RandomListNode *head) {
if (!head) return NULL;
unordered_map<RandomListNode *, RandomListNode *> map;
RandomListNode dummy(0), *curNew = &dummy, *cur = head;
while (cur)
{
if (map.find(cur) == map.end())
map[cur] = new RandomListNode(cur->label);
if (cur->random && map.find(cur->random) == map.end())
map[cur->random] = new RandomListNode(cur->random->label);
curNew->next = map[cur];
curNew = curNew->next;
curNew->random = map[cur->random];
cur = cur->next;
}
return dummy.next;
}
}; -
-
- 时间: 2014-9-23 14:05Problem Name: Count and Say
Description:
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string. -
-
- 时间: 2014-9-23 14:05Now comes the solution (in C++) ...
...
代码: class Solution {
public:
string countAndSay(int n) {
string res = "1";
for (int i = 2; i <= n; ++i)
{
stringstream ss;
int j = 0, N = res.size();
while (j < N) {
int k = j + 1;
while (k < N && res[k] == res[j])
k++;
ss << (k - j) << res[j];
j = k;
}
ss >> res;
}
return res;
}
};
-
- 时间: 2014-9-23 14:05Problem Name: Decode Ways
Description:
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2. -
- 时间: 2014-9-23 14:06Now comes the solution (in C++) ...
dp. Note that '0' must be decoded in together with the number in front of it.
代码: class Solution {
public:
int numDecodings(string s) {
if (s.empty() || s[0] == '0')
return 0;
int N = s.size();
int dp[N+1];
dp[0] = 1;
dp[1] = 1;
for (int i = 1; i < N; ++i)
{
if (s[i] == '0')
{
if (s[i-1] != '1' && s[i-1] != '2')
return 0;
dp[i+1] = dp[i-1];
}
else
{
int num = s[i] - '0' + (s[i-1] - '0') * 10;
if (num >= 11 && num <= 26)
dp[i+1] = dp[i] + dp[i-1];
else
dp[i+1] = dp[i];
}
}
return dp[N];
}
}; -
- 时间: 2014-9-23 14:07Problem Name: Distinct Subsequences
Description:
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting
some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3. -
- 时间: 2014-9-23 14:07Now comes the solution (in C++) ...
dp.
代码: class Solution {
public:
int numDistinct(string S, string T) {
int N = S.size(), M = T.size();
int dp[M+1][N+1];
dp[0][0] = 1;
for (int j = 1; j <= N; ++j)
dp[0][j] = 1;
for (int i = 1; i <= M; ++i)
dp[i][0] = 0;
for (int i = 1; i <= M; ++i)
for (int j = 1; j <= N; ++j)
if (S[j-1] == T[i-1])
dp[i][j] = dp[i][j-1] + dp[i-1][j-1];
else
dp[i][j] = dp[i][j-1];
return dp[M][N];
}
}; -
- 时间: 2014-9-23 14:09
-
- 时间: 2014-9-23 14:10Now comes the solution (in C++) ...
Use << operator.
代码: class Solution {
public:
int divide(int dividend, int divisor) {
assert(divisor != 0);
bool flag = dividend > 0 && divisor < 0 ||
dividend < 0 && divisor > 0;
long long dividendll = abs((long long)dividend);
long long divisorll = abs((long long)divisor);
int res = 0;
while (dividendll >= divisorll)
{
long long div = divisorll;
int quot = 1;
while ((div << 1) <= dividendll) {
div <<= 1;
quot <<= 1;
}
dividendll -= div;
res += quot;
}
return flag ? -res : res;
}
};
-
- 时间: 2014-9-23 14:12Problem Name: Edit Distance
Description:
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
Leetcode Hacking Practice -- Solution in C++ Part 1
