zhedahht / codinginterviewchinese2 Goto Github PK

这道题目有问题，题目说的是:给你一根长度为n的绳子，请把绳子剪成m段，求最大值，而解法却是剪任意段求最大值，并没有限制剪的段数。

比如一段绳子长度为 7，要求剪成 7段，那么答案就不是12 了，12是绳子能剪成的最大长度，但只有剪成2段或者3段才能得到12，剪成7段长度不可能为12。

代码的解法是不限制绳子的段数的，或许是我没有理解清楚代码，还请解惑

// 多个重复的数字
void test1()
{
int numbers[] = { 2, 2, 3, 3, 5, 5, 6, 6 };
int duplications[] = { 2, 3 };
test("test1", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int));
}
这种情况，一个重复的数字都找不出来

代码仓库没有给出，书上给出了

//copy operator
CMyString& CMyString::operator=(const CMyString& str)
{
	if(m_pData != &str)
	{
		CMyString tmpData(str);
		
		char *ptmp = tmpData.m_pData;
		tmpData.m_pData = m_pData;
		m_pData = ptmp;
	}
	return *this;
}

m_pData是private的，书上写的有点问题

在PrintTreeNode(const TreeNode* pNode)函数中，遗漏了一句++i;，如下：

void PrintTreeNode(const TreeNode* pNode)
{
	if (pNode != nullptr)
	{
		printf("value of this node is: %d.\n", pNode->m_nValue);

		printf("its children is as the following:\n");
		std::vector<TreeNode*>::const_iterator i = pNode->m_vChildren.begin();
		while (i < pNode->m_vChildren.end())
		{
			if (*i != nullptr)
			{
				printf("%d\t", (*i)->m_nValue);
				++i;       //此句不加会导致程序进入死循环
			}
			printf("%d\t", (*i)->m_nValue);
		}

		printf("\n");
	}
	else
	{
		printf("this node is nullptr.\n");
	}

	printf("\n");
}

如题

现在给出的实现如下：

/*length 为字符数组str的总容量，大于或等于字符串str的实际长度*/
void ReplaceBlank(char str[], int length)
{
    if(str == nullptr && length <= 0)
        return;

    /*originalLength 为字符串str的实际长度*/
    int originalLength = 0;
    int numberOfBlank = 0;
    int i = 0;
    while(str[i] != '\0')
    {
        ++ originalLength;

        if(str[i] == ' ')
            ++ numberOfBlank;

        ++ i;
    }

    /*newLength 为把空格替换成'%20'之后的长度*/
    int newLength = originalLength + numberOfBlank * 2;
    if(newLength > length)
        return;

    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
    {
        if(str[indexOfOriginal] == ' ')
        {
            str[indexOfNew --] = '0';
            str[indexOfNew --] = '2';
            str[indexOfNew --] = '%';
        }
        else
        {
            str[indexOfNew --] = str[indexOfOriginal];
        }

        -- indexOfOriginal;
    }
}

我的考虑是 originalLength 的计算，在 strlen(string) 时，确实像上面的计算长度是没有错的，不用考虑字符数组最后的空字符 \0，在这里的话，考虑边界条件，个人觉得应该添加如下改动：

1. 在计算 newLength 之前，将 originalLength 给多计算一个字符，算上最后的空字符 \0，其他的保持不变即可；
2. 如果考虑和 strlen(string) 一样的语义，在计算 originalLength 时就用如上的代码计算长度即可，但在判断得到的 newLength 是否超出 length 时，需要

    if(newLength +１ > length)
        return;

这样保证替换之后的字符串的最后一位空字符是字符数组提供的，在测试时，传入的字符数组是 char str[100] = "We are happy."，其13-99索引号均填充为 \0

以上 1 和 2 两种方案选择一种即可。

PrintMinNumber函数中
char** strNumbers = (char**)(new int[length])
我在mac上编译运行的时候当数组个数大于4时会结果会出现乱码，我将其改成
char** strNumbers = new char*[length]
后代码输出结果正确。
求解释。

我神圣！伟大！优秀！不容侵犯，永远第一！

运行结果：

linux 4.15.0-36-generic
gcc 5.4.0

我有点疑惑为什么要用两层while循环，第二层的while改为if会不会更好一点，因为第二层只是一个判断并不会进入循环

是否需要先删除 visited

                delete[] visited;
                return true;

作者在面试题43有这样的分析，存在错误——“可以再把1346-21345分成两段：[1346, 11345]和[11346, 21345].每一段剩下的4位数字中，选择其中一位是1，其余三位可以在0~9这10个数字任意选择，因此根据排列组合原则，总共出现的次数是2x4x10^3 = 8000次”

按作者说的，剩下的4位数字中，如果前3位选0，最后一位选1，数字1应当包含在8000次里面，但是数字1并不在 [1346, 11345]和[11346, 21345] 任一区间内，很明显上述分析并不对

编译有问题：
1>------ 已启动生成: 项目: test3, 配置: Debug Win32 ------
1>生成启动时间为 2018/5/25 16:18:47。
1>InitializeBuildStatus:
1> 正在对“Debug\test3.unsuccessfulbuild”执行 Touch 任务。
1>ClCompile:
1> 所有输出均为最新。
1>PrintListInReversedOrder.obj : error LNK2019: 无法解析的外部符号 "void __cdecl PrintList(struct ListNode *)" (?PrintList@@YAXPAUListNode@@@z)，该符号在函数 "void __cdecl Test(struct ListNode *)" (?Test@@YAXPAUListNode@@@z) 中被引用
1>PrintListInReversedOrder.obj : error LNK2019: 无法解析的外部符号 "void __cdecl DestroyList(struct ListNode *)" (?DestroyList@@YAXPAUListNode@@@z)，该符号在函数 "void __cdecl Test1(void)" (?Test1@@yaxxz) 中被引用
1>PrintListInReversedOrder.obj : error LNK2019: 无法解析的外部符号 "void __cdecl ConnectListNodes(struct ListNode *,struct ListNode *)" (?ConnectListNodes@@YAXPAUListNode@@0@Z)，该符号在函数 "void __cdecl Test1(void)" (?Test1@@yaxxz) 中被引用
1>PrintListInReversedOrder.obj : error LNK2019: 无法解析的外部符号 "struct ListNode * __cdecl CreateListNode(int)" (?CreateListNode@@YAPAUListNode@@h@Z)，该符号在函数 "void __cdecl Test1(void)" (?Test1@@yaxxz) 中被引用
1>G:\visual studio 2010\Projects\test3\Debug\test3.exe : fatal error LNK1120: 4 个无法解析的外部命令
1>
1>生成失败。
1>
1>已用时间 00:00:00.55
========== 生成: 成功 0 个，失败 1 个，最新 0 个，跳过 0 个 ==========

我咋一个都运行不成功

try
{
    BinaryTreeNode* root = Construct(preorder,inorder,length);
    PrintTree(root);

    DestroyTree(root);
}
catch(std::exception& exception)
{
    printf("Invalid Input.\n");
}

其中返回值root的结构类型是BinaryTreeNode:
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};

而下一步传入PrintTree的函数参数类型应该是TreeNode,结构如下：
struct TreeNode
{
int m_nValue;
std::vector<TreeNode*> m_vChildren;
};

二者不吻合导致无法成功测试

while(rootInorder <= endInorder && *rootInorder != rootValue)
    ++ rootInorder;

这里应为
while(rootInorder < endInorder && *rootInorder != rootValue)
++ rootInorder;

假如前四个数字数字刚刚好，那是不是要把middle换一下？
if(count > (middle - start + 1))
end = middle;
else
start = middle + 1;
应该改为
if(count > (middle - start + 1))
end = middle;
else
start = middle + 1;
middle= end ；

每遇到一个*，就会产生一个分支，，指数级别的复杂度。
用编译原理里面的方法进行优化也好，用动态规划来做也行。如此暴力的解决方式会给人误导的。

第三种解法，作者声称的即全面又高效的解法，PowerWithUnsignedExponent(double base, unsigned int exponent)，当 exponent < 0时，答案错误

66-67行代码
if(rootInorder == endInorder && *rootInorder != rootValue)
throw std::exception("Invalid input.");
这句没有用吧！

常规解法中设置一个flag，每次讲flag右移1位并与原来的数字做与运算。书中给的判断条件是 if（n&flag），这个判断是错的。正确的判别式应该是if（（n&flag）==flag）。很容易理解，flag从1，2，4，....不断右移，此时按位与得到的结果应该是只有这一位是1，其余全是零，即是flag。作者也帮忙看一下这个想法对嘛

1.第二版书中，面试12的hasPath函数的形参表matrix和str书中为char *，但应该都为const char *应该才能保证字符串数组和矩阵不被修改，并且github中代码是定义成const char *的；
2.存在内存泄漏，在查找通路成功后没有释放visited的内存。

bool increment(char* number)
{
int len = strlen(number);
for (int index = len - 1; index >= 0; index--)
{
if ('9' == number[index])
{
if (0 == index)
{
return false;
}
number[index] = '0';
}
else
{
number[index] += 1;
break;
}
}
return true;
}

只检测出了第一个重复数字，请问怎么判定第二个重复数字4呢？

该题目已经说明了长度为 n+1 的数组所有数字都在 1~n 范围，那么这个 n 至少应该是 1，否则就没有意义了，所以代码里面有一处判断

if (numbers == nullptr || length <=0)
    return -1;

应该是

if (numbers == nullptr || length <= 1)
    return -1;

请问用什么编译器编译啊？DEV报错collect.exe的错误

如题

书中写到：

当n>=5的时候，我们可以证明2（n-2）>n并且3（n-3）>n。也就是说，当绳子剩下的长度大于或者等于5的时候，我们就把它剪成长度为3或长度为2的绳子段

这个“也就是说”结论是怎么得出的？这个结论不是应该证明了3（n-3）>2（n-2）>.....>i（n-i）才能得出吗？

if(length < 2)  return 0;
if(length == 2) return 1;
if(length == 3)  return 2;

。。。。。。。。。。。。。
products[1] = 1;
products[2] = 2;
products[3] = 3;
你上面写的跟下面写的矛盾呀。。。。。

In the funciton "hasPath" is limited row from 0 to rows and col from 0 to cols (line 43 and 45), but why in function "hasPathCore" still judge "row >= 0 && row < rows && col >= 0 && col < cols" (line 67)?

看解法发现并没有用到题干所要求的剪成m段啊? 这道题是不是解读有点错误

按我的理解，这五行代码意思是，此时定位错误，退回到上一个定位。但是，上一个定位处的情况，都已经有递归代码进行检测了，这个回退貌似是多次一举。或者我理解有误，还望指教。

何老师，这段代码是不是有异常安全问题呀？

CMyString& CMyString::operator = (const CMyString& str)
   {
       if(this == &str)
       return *this;
    
       delete []m_pData;
       m_pData = nullptr;
    
       m_pData = new char[strlen(str.m_pData) + 1];
       strcpy(m_pData, str.m_pData);
    
       return *this;
   }

书中写到

动态规划解法，因为1*2>1*1*1所以f(3)=2。

但是题目并没有说绳子长度不可以为小数，所以1.5*1.5>1*2，f(3)=1.5*1.5不是吗？

这个是要去哪里下载么

执行时发生段错误：segmentation fault (core dumped)

求数字序列中某一位的数字，可以遍历建立哈希表，key为下标，value为数列中对应的值，直接查表就好了啊

当n为奇数时，应该是：
a^{(n-1)/2} × a^{(n+1)/2}

请问能用int数组处理吗？为什么要选用char字符数组处理？

第二版书中41页提到，"虽然有两个循环，但每个数字最多只要交换两次就能找到属于它自己的位置，所以总时间复杂度是O(n)"

这里不太明白，书中给的例子第一个下标就交换了三次，这个O(n)是怎样得出的呢？

page 185 求路径和，返回上一层的时候，currentSum忘记减去pop出的那个节点的值

我看了一下，代码是没有问题，但我觉得思路有一点问题，书中的代码是这样的
private int maxProductAfterCounter1(int length){
int max=0;
if(length<2)return 0;
if(length==2)return 1;
if(length==3)return 2;
int[] product =new int[length+1];
product[0]=0;
product[1]=1;
product[2]=2;
product[3]=3;
for(int i=1;i<=length;i++){
max=product[i];
for(int j=1;j<=i/2;j++){
int temp=product[j]*product[i-j];
if(temp>max)max=temp;
}
product[i]=max;
}
max=product[length];
return max;
}
这里面没有解释为什么从4开始，为什么长度为4的就必须要剪开，当然我们可以推算出4以后，它每次剪开的乘积都会大于本身，但是没有数学推算，自己写了一个，先假设每一个product最大值是自己本身，由于1，不能剪是自己，2剪了之后没有本身大
private static int maxProductAfterCounter(int length){
int max=0;
if(length<2)return 0;
if(length==2)return 1;
if(length==3)return 2;
int[] product =new int[length+1];
for(int i=1;i<=length;i++)
product[i]=i;
for(int i=1;i<=length;i++){
max=product[i];
for(int j=1;j<=i/2;j++){
int temp=product[j]*product[i-j];
if(temp>max)max=temp;
}
product[i]=max;
}
max=product[length];
return max;
}

f(1)=1,f(2)=1,f(3)=2
所以不用考虑length=4，直接 int timsOf3 = length/3就行了
return (int)(pow(3,timsOf3));

如题，明明还有剪成m段的要求，但解法中没有考虑到。比如长度为8的绳子，要求剪成2段最大就是4*4=16，要求剪成3段最大就是3*3*2=18，要求剪成4段最大就是2*2*2*2=16。但参考解法中只要输入8输出一定就是18，很疑惑。

不应该最小堆应该是从小到大排列，最大堆应该从大到小排列。这样才能保证最小堆的数大于最大堆的数 吗？ 为什么原文代码，最小堆从大到小排列，最大堆从小到大排列。谢谢解答