a*******y
发帖数: 1040 | 1 贴youtubevideo的那哥们的coding太长了，估计不是interviewer要的，有没有
recursion可以做这个的？ | p********s
发帖数: 37 | 2 写了个超级傻的，各种没效率，您别笑话囧
int pl(int a, int b) { return a + b; }
int mi(int a, int b) { return a - b; }
int ti(int a, int b) { return a * b; }
int di(int a, int b) { return (b && !(a % b)) ? (a / b) : -12345 ; }
int (*op[4])(int a, int b) = {&pl, &mi, &ti, &di};
const char *name[4] = {"+", "-", "*", "/"};
char result[128] = {0};
bool tryit(int nums[], char* res)
{
char result[128];
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
for(int k = 0; k < 4; k++)
if ((*op[k])((*op[j])((*op[i])(nums[0], nums[1]), nums[2]), nums[3]) == 24)
{
sprintf(res, "(((%d %s %d) %s %d) %s %d)\0", nums[0], name[i], nums[1],
name[j], nums[2], name[k], nums[3]);
return true;
}
else if ((*op[j])((*op[i])(nums[0], nums[1]), (*op[k])(nums[2], nums[3])) =
= 24) {
sprintf(res, "((%d %s %d) %s (%d %s %d)\0", nums[0], name[i], nums[1],
name[j], nums[2], name[k], nums[3]);
return true;
}
return false;
}
bool twentyFour(int nums[], char* res) {
sort(nums, nums + 4);
do {
if (tryit(nums, res))
return true;
}while(next_permutation(nums, nums + 4));
return false;
} | a*******y
发帖数: 1040 | 3 你这个主要是那个permutation函数把， 而且你没写出来，要是有permutation，还不
如弄成postfix来做 | p********s
发帖数: 37 | | Z*****Z
发帖数: 723 | 5 贴个python版的
def expressable0(numList, target, curr, index):
N = len(numList)
if(index == N):
return curr == target
if(expressable0(numList, target, curr + numList[index], index + 1)):
return True
elif(expressable0(numList, target, curr - numList[index], index + 1)):
return True
elif(expressable0(numList, target, curr * numList[index], index + 1)):
return True
elif(expressable0(numList, target, curr // numList[index], index + 1)):
return True
return False
def expressable(numList, target):
return expressable0(numList, target, numList[0], 1)
if __name__ == '__main__':
numList = [2, 2, 3, 2]
target = 24
print(expressable(numList, target))
【在 p********s 的大作中提到】
: 那个是stl的alrorithm库里的函数，http://www.cplusplus.com/reference/algorithm/next_permutation/，面试真不让stl用咱也没办法呀
| a*******y
发帖数: 1040 | 6 我知道那个是STL的，关键这个是这道题的关键，你用STL来实现了
【在 p********s 的大作中提到】
: 那个是stl的alrorithm库里的函数，http://www.cplusplus.com/reference/algorithm/next_permutation/，面试真不让stl用咱也没办法呀
| a*******y
发帖数: 1040 | 7 贴youtubevideo的那哥们的coding太长了，估计不是interviewer要的，有没有
recursion可以做这个的？ | p********s
发帖数: 37 | 8 写了个超级傻的，各种没效率，您别笑话囧
int pl(int a, int b) { return a + b; }
int mi(int a, int b) { return a - b; }
int ti(int a, int b) { return a * b; }
int di(int a, int b) { return (b && !(a % b)) ? (a / b) : -12345 ; }
int (*op[4])(int a, int b) = {&pl, &mi, &ti, &di};
const char *name[4] = {"+", "-", "*", "/"};
char result[128] = {0};
bool tryit(int nums[], char* res)
{
char result[128];
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
for(int k = 0; k < 4; k++)
if ((*op[k])((*op[j])((*op[i])(nums[0], nums[1]), nums[2]), nums[3]) == 24)
{
sprintf(res, "(((%d %s %d) %s %d) %s %d)\0", nums[0], name[i], nums[1],
name[j], nums[2], name[k], nums[3]);
return true;
}
else if ((*op[j])((*op[i])(nums[0], nums[1]), (*op[k])(nums[2], nums[3])) =
= 24) {
sprintf(res, "((%d %s %d) %s (%d %s %d)\0", nums[0], name[i], nums[1],
name[j], nums[2], name[k], nums[3]);
return true;
}
return false;
}
bool twentyFour(int nums[], char* res) {
sort(nums, nums + 4);
do {
if (tryit(nums, res))
return true;
}while(next_permutation(nums, nums + 4));
return false;
} | a*******y
发帖数: 1040 | 9 你这个主要是那个permutation函数把， 而且你没写出来，要是有permutation，还不
如弄成postfix来做 | p********s
发帖数: 37 | | Z*****Z
发帖数: 723 | 11 贴个python版的
def expressable0(numList, target, curr, index):
N = len(numList)
if(index == N):
return curr == target
if(expressable0(numList, target, curr + numList[index], index + 1)):
return True
elif(expressable0(numList, target, curr - numList[index], index + 1)):
return True
elif(expressable0(numList, target, curr * numList[index], index + 1)):
return True
elif(expressable0(numList, target, curr // numList[index], index + 1)):
return True
return False
def expressable(numList, target):
return expressable0(numList, target, numList[0], 1)
if __name__ == '__main__':
numList = [2, 2, 3, 2]
target = 24
print(expressable(numList, target))
【在 p********s 的大作中提到】
: 那个是stl的alrorithm库里的函数，http://www.cplusplus.com/reference/algorithm/next_permutation/，面试真不让stl用咱也没办法呀
| a*******y
发帖数: 1040 | 12 我知道那个是STL的，关键这个是这道题的关键，你用STL来实现了
【在 p********s 的大作中提到】
: 那个是stl的alrorithm库里的函数，http://www.cplusplus.com/reference/algorithm/next_permutation/，面试真不让stl用咱也没办法呀
| a**********e
发帖数: 157 | 13 是不是没考虑 (a+b+c)/d ?
【在 p********s 的大作中提到】
: 写了个超级傻的，各种没效率，您别笑话囧
: int pl(int a, int b) { return a + b; }
: int mi(int a, int b) { return a - b; }
: int ti(int a, int b) { return a * b; }
: int di(int a, int b) { return (b && !(a % b)) ? (a / b) : -12345 ; }
: int (*op[4])(int a, int b) = {&pl, &mi, &ti, &di};
: const char *name[4] = {"+", "-", "*", "/"};
: char result[128] = {0};
: bool tryit(int nums[], char* res)
: {
| a**********e
发帖数: 157 | 14 a few cases like a/(b+c+d) seem missing, e.g. {72,1,1,1}
【在 p********s 的大作中提到】
: 写了个超级傻的，各种没效率，您别笑话囧
: int pl(int a, int b) { return a + b; }
: int mi(int a, int b) { return a - b; }
: int ti(int a, int b) { return a * b; }
: int di(int a, int b) { return (b && !(a % b)) ? (a / b) : -12345 ; }
: int (*op[4])(int a, int b) = {&pl, &mi, &ti, &di};
: const char *name[4] = {"+", "-", "*", "/"};
: char result[128] = {0};
: bool tryit(int nums[], char* res)
: {
|
|
