继续整理《Cracking the Coding Interview》。
17.4无判断max
请编写一个方法，找出两个数字中最大的那个。条件是不得使用if-else等比较和判断运算符。
给定两个int a和b，请返回较大的一个数。若两数相同则返回任意一个。
通过判断a-b的符号来返回结果，考虑a-b溢出的情况。溢出的话一定异号，各种情形考虑到。
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
| class Max {
public:
int flag(int x)
{
return (x >> 31) & 1;
}
int getMax(int a, int b)
{
int fa = flag(a);
int fb = flag(b);
int fc = flag(a - b);
int k = fa^fb;
int ans = 0;
if (k == 0)
{
ans = 1 ^ fc;
}
else
{
ans = 1 ^ fa;
}
return ans*a + (1 ^ ans)*b;
}
}wc;
|
17.5珠玑妙算
我们现在有四个槽，每个槽放一个球，颜色可能是红色(R)、黄色(Y)、绿色(G)或蓝色(B)。例如，可能的情况为RGGB(槽1为红色，槽2、3为绿色，槽4为蓝色)，作为玩家，你需要试图猜出颜色的组合。比如，你可能猜YRGB。要是你猜对了某个槽的颜色，则算一次“猜中”。要是只是猜对了颜色但槽位猜错了，则算一次“伪猜中”。注意，“猜中”不能算入“伪猜中”。
给定两个string A和guess。分别表示颜色组合，和一个猜测。请返回一个int数组，第一个元素为猜中的次数，第二个元素为伪猜中的次数。
Leetcode上面的题。首先计算猜中的个数，然后没猜中的记录个数。注意考虑一些情况。
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
| class Result {
public:
vector<int> calcResult(string A, string guess)
{
int A_len = A.length();
int g_len = guess.length();
vector<int>res;
if (A_len != g_len)return res;
int ans1 = 0, ans2 = 0;
map<char, int>hax;
for (int i = 0; i < A_len; i++)
{
if (A[i] == guess[i])ans1++;
else
{
hax[A[i]]++;
}
}
for (int i = 0; i < g_len; i++)
{
if (A[i] == guess[i])continue;
else
{
if (hax[guess[i]])
{
ans2++;
hax[guess[i]]--;
}
}
}
res.push_back(ans1);
res.push_back(ans2);
return res;
}
};
|
17.6最小调整有序
有一个整数数组，请编写一个函数，找出索引m和n，只要将m和n之间的元素排好序，整个数组就是有序的。注意：n-m应该越小越好，也就是说，找出符合条件的最短序列。
给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的起点和终点。(原序列位置从0开始标号,若原序列有序，返回[0,0])。保证A中元素均为正整数。
首先找中间不符合排序的区间，然后记录这段区间下的最小值与最大值，往外面扩。
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
| class Rearrange
{
public:
int find_left(vector<int>&A)
{
int sz = A.size();
for (int i = 0; i+1 < sz; i++)
{
if (A[i] > A[i + 1])return i;
}
return sz - 1;
}
int find_right(vector<int>&A)
{
int sz = A.size();
for (int i = sz - 1; i - 1 >= 0; i--)
{
if (A[i] < A[i - 1])return i;
}
return 0;
}
vector<int> findSegment(vector<int> A, int n)
{
int left = find_left(A);
int right = find_right(A);
if (left >= right)
{
vector<int>ans = { 0,0 };
return ans;
}
int minn = A[left], maxx = A[right];
for (int i = left; i <= right; i++)
{
minn = min(minn, A[i]);
maxx = max(maxx, A[i]);
}
while (left >= 0)
{
if (A[left] <= minn)
{
break;
}
left--;
}
left++;
while (right < A.size())
{
if (A[right] >= maxx)
{
break;
}
right++;
}
right--;
vector<int>res;
res.push_back(left);
res.push_back(right);
return res;
}
};
|
17.7数字发音
有一个非负整数，请编写一个算法，打印该整数的英文描述。
给定一个int x，请返回一个string，为该整数的英文描述。
这个也是Leetcode的原题，很麻烦，主要在于空格要考虑各种情况。
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
| class ToString
{
public:
vector<string> bigs = { "","Thousand","Million" };
vector<string>digits = { "One","Two","Three","Four","Five","Six","Seven","Eight","Nine" };
vector<string>teens = { "Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen" };
vector<string>tens = { "Ten","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety" };
string toString(int x)
{
if (x == 0)
{
return "Zero";
}
else if (x < 0)
{
return "Negative " + toString(-1 * x);
}
string res = "";
int cnt = 0;
while (x > 0)
{
if (x % 1000 != 0)
{
if(res.length())
res = num_to_string(x % 1000) + " " + bigs[cnt] + "," + res;
else
res = num_to_string(x % 1000) + " " + bigs[cnt];
}
x /= 1000;
cnt++;
}
while (*res.begin() == ' ')res.erase(res.begin());
while (*(res.end() - 1) == ' ')res.erase(res.end() - 1);
return res;
}
string num_to_string(int x)
{
string res = "";
if (x >= 100)
{
res = digits[x / 100 - 1] + " Hundred";
x = x % 100;
}
if (x >= 11 && x <= 19)
{
if(res.length())
res = res + " " + teens[x % 10 - 1];
else
res = teens[x % 10 - 1];
return res;
}
else if (x == 10 || x >= 20)
{
int num = x / 10;
x %= 10;
if(res.length())
res = res + " " + tens[num - 1];
else
res = tens[num - 1];
}
if (x)
{
if(res.length())
res = res + " " + digits[x - 1];
else
res = digits[x - 1];
}
return res;
}
};
|
17.13树转链表
有一个类似结点的数据结构TreeNode，包含了val属性和指向其它结点的指针。其可以用来表示二叉查找树(其中left指针表示左儿子，right指针表示右儿子)。请编写一个方法，将二叉查找树转换为一个链表，其中二叉查找树的数据结构用TreeNode实现，链表的数据结构用ListNode实现。
给定二叉查找树的根结点指针root，请返回转换成的链表的头指针。
中序递归遍历。
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
|
class Converter
{
public:
ListNode *head = new ListNode(-1);
ListNode *pre = head;
ListNode* treeToList(TreeNode* root)
{
if (root)
{
treeToList(root->left);
pre->next = new ListNode(root->val);
pre = pre->next;
treeToList(root->right);
}
return head->next;
}
};
|