46. 圆圈中最后剩下的数【约瑟夫环问题】
- 有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
// Solution:(1)使用环形链表模拟，时间复杂度O(mn)，空间复杂度O(n);
// (2)直接找出最后一个数字规律
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if (n < 1 || m < 1)
return -1;
list<int> numbers;
for (int i = 0; i < n; i ++)
numbers.push_back(i);
list<int>::iterator cur = numbers.begin();
while (numbers.size() > 1) {
for (int i = 1; i < m; i ++) {
cur ++;
if (cur == numbers.end()) // 模拟环尾
cur = numbers.begin();
}
list<int>::iterator deleteIt = cur;
cur ++;
if (cur == numbers.end())
cur = numbers.begin();
numbers.erase(deleteIt);
}
return *(cur);
}
};
// Solution:(1)使用环形链表模拟，时间复杂度O(mn)，空间复杂度O(n);
// (2)直接找出最后一个数字规律，f(n,m) = 0, n=1，时间O(n)，空间O(1)
// f(n,m) = [f(n-1, m)+m]%n, n>1
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if (n < 1 || m < 1)
return -1;
int last = 0;
for (int i = 2; i <= n; i ++)
last = (last + m) % i;
return last;
}
};
47. 求1+2+...+n【发散思维】
- 求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
// Solution:(1)利用构造函数求解
class Temp {
public:
Temp() { N ++; Sum += N;}
static void Reset() { N = 0; Sum = 0;}
static unsigned int GetSum() { return Sum;}
private:
static unsigned int N;
static unsigned int Sum;
};
unsigned int Temp::N = 0;
unsigned int Temp::Sum = 0;
class Solution {
public:
int Sum_Solution(int n) {
Temp::Reset();
Temp *a = new Temp[n];
delete []a;
a = NULL;
return Temp::GetSum();
}
};
// Solution:(2)利用虚函数求解，一个函数递归，一个函数判断终止条件
class A;
A* Array[2];
class A {
public:
virtual unsigned int Sum(unsigned int n) {
return 0;
}
};
class B: public A {
public:
virtual unsigned int Sum(unsigned int n) {
return Array[!!n]->Sum(n-1) + n;
}
};
class Solution {
public:
int Sum_Solution(int n) {
A a;
B b;
Array[0] = &a;
Array[1] = &b;
int value = Array[1]->Sum(n);
return value;
}
};
// Solution:(3)利用函数指针求解
typedef int (*fun) (int);
class Solution {
public:
static int Sum_terminator(int n) {
return 0;
}
static int Sum_Solution(int n) {
static fun f[2] = {Sum_terminator, Sum_Solution};
return n + f[!!n](n-1);
}
};
48. 不用加减乘除做加法
- 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
// Solution：位运算
class Solution {
public:
int Add(int num1, int num2)
{
int sum, carry;
do {
sum = num1 ^ num2;
carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
} while (num2 != 0);
return num1;
}
};
49. 把字符串转换成整数
- 将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
输入描述:
输入一个字符串,包括数字字母符号,可以为空
输出描述:
如果是合法的数值表达则返回该数字，否则返回0
示例1
输入
+2147483647
1a33
输出
2147483647
0
// 考虑：(1)输入""; (2)输入非0-9; (3)输入"+/-"等; (4)溢出
class Solution {
public:
int StrToInt(string str) {
int gFlag = -1;
int len = str.size();
if (len == 0) {
gFlag = 1;
return 0;
}
int minus = 1;
long long num = 0;
int i = 0;
if (str[i] == '+') {
i ++;
} else if (str[i] == '-') {
i ++;
minus = -1;
}
while (str[i] != '\0') {
if (str[i] >= '0' && str[i] <= '9') {
num = num*10 + str[i]-'0';
i ++;
if (((minus > 0) && (num > 0x7FFFFFFF)) ||
((minus < 0) && (num > 0x80000000))) {
num = 0;
gFlag = 2;
break;
}
} else {
num = 0;
gFlag = 3;
break;
}
}
return (int)minus*num;
}
};
50. 树中两个结点的最低公共祖先
- 输入两个结点，求他们的最低公共祖先
- 二叉树：判断两个结点与当前结点的大小关系，第一个在两节点之间的值即最低公共祖先。
solution
- 非二叉树，有指向父节点的指针：（转换为求两个链表第一个公共结点）
solution
- 非二叉树，没有指向父节点的指针： 判断子树中同时包含两个结点，并判断该节点的子节点子树不同时包含两个结点，该结点就是最低公共祖先。使用数组保存两个结点所在的路径，以减少重复计算子树情况。
solution1
solution2
soluntion3
bool GetNodePath(TreeNode * pRoot, TreeNode * pNode, list<TreeNode *> &path) {
if (pRoot == pNode)
return true;
path.push_back(pRoot);
bool found = false;
vector<TreeNode *>::iterator i = pRoot->children.begin();
while (! found && i < pRoot->children.end()) {
found = GetNodePath(*i, pNode, path);
i ++;
}
if (! found)
path.pop_back();
return found;
}
TreeNode * GetLastCommonNode(const list<TreeNode*> &path1, const list<TreeNode*> &path2) {
list<TreeNode*>::const_iterator iterator1 = path1.begin();
list<TreeNode*>::const_iterator iterator2 = path2.begin();
TreeNode* pLast = NULL;
while (iterator1 != path1.end() && iterator2 != path2.end()) {
if (*iterator1 == *iterator2)
pLast = *iterator1;
iterator1 ++;
iterator2 ++;
}
return pLast;
}
TreeNode * GetLastCommonParent(TreeNode * pRoot, TreeNode * pNode1， TreeNode * pNode2) {
if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
List<TreeNode *> path1;
GetNodePath(pRoot, pNode1, path1);
List<TreeNode *> path2;
GetNodePath(pRoot, pNode2, path2);
return GetLastCommonNode(path1, path2);
}
网友评论