zhedahht / codinginterviewchinese2 Goto Github PK
View Code? Open in Web Editor NEW《剑指Offer:名企面试官精讲典型编程面试题》第二版源代码
License: Other
《剑指Offer:名企面试官精讲典型编程面试题》第二版源代码
License: Other
66-67行代码
if(rootInorder == endInorder && *rootInorder != rootValue)
throw std::exception("Invalid input.");
这句没有用吧!
现在给出的实现如下:
/*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
,在这里的话,考虑边界条件,个人觉得应该添加如下改动:
newLength
之前,将 originalLength
给多计算一个字符,算上最后的空字符 \0
,其他的保持不变即可;strlen(string)
一样的语义,在计算 originalLength
时就用如上的代码计算长度即可,但在判断得到的 newLength
是否超出 length
时,需要 if(newLength +1 > length)
return;
这样保证替换之后的字符串的最后一位空字符是字符数组提供的,在测试时,传入的字符数组是 char str[100] = "We are happy."
,其13-99索引号均填充为 \0
以上 1 和 2 两种方案选择一种即可。
void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{
if(!pListHead || !pToBeDeleted)
return;
// 要删除的结点不是尾结点
if(pToBeDeleted->m_pNext != nullptr)
{
ListNode* pNext = pToBeDeleted->m_pNext;
pToBeDeleted->m_nValue = pNext->m_nValue;
pToBeDeleted->m_pNext = pNext->m_pNext;
delete pNext;
pNext = nullptr;
}
// 链表只有一个结点,删除头结点(也是尾结点)
else if(*pListHead == pToBeDeleted)
{
delete pToBeDeleted;
pToBeDeleted = nullptr;
*pListHead = nullptr;
}
// 链表中有多个结点,删除尾结点
else
{
ListNode* pNode = *pListHead;
// 加强边界检查,防止意外输入造成core dump
while(pNode->m_pNext != nullptr && pNode->m_pNext != pToBeDeleted)
{
pNode = pNode->m_pNext;
}
if (pNode->m_pNext == pToBeDeleted)
{
pNode->m_pNext = nullptr;
delete pToBeDeleted;
pToBeDeleted = nullptr;
}
}
}
第二版书中41页提到,"虽然有两个循环,但每个数字最多只要交换两次就能找到属于它自己的位置,所以总时间复杂度是O(n)"
这里不太明白,书中给的例子第一个下标就交换了三次,这个O(n)是怎样得出的呢?
我神圣!伟大!优秀!不容侵犯,永远第一!
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;
};
二者不吻合导致无法成功测试
书中写到
动态规划解法,因为1*2>1*1*1所以f(3)=2。
但是题目并没有说绳子长度不可以为小数,所以1.5*1.5>1*2,f(3)=1.5*1.5不是吗?
while(rootInorder <= endInorder && *rootInorder != rootValue)
++ rootInorder;
这里应为
while(rootInorder < endInorder && *rootInorder != rootValue)
++ rootInorder;
PrintMinNumber函数中
char** strNumbers = (char**)(new int[length])
我在mac上编译运行的时候当数组个数大于4时会结果会出现乱码,我将其改成
char** strNumbers = new char*[length]
后代码输出结果正确。
求解释。
如题
当n为奇数时,应该是:
a^{(n-1)/2} × a^{(n+1)/2}
代码仓库没有给出,书上给出了
//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的,书上写的有点问题
if(length < 2) return 0;
if(length == 2) return 1;
if(length == 3) return 2;
。。。。。。。。。。。。。
products[1] = 1;
products[2] = 2;
products[3] = 3;
你上面写的跟下面写的矛盾呀。。。。。
bool hasSubtree(TreeNode *T1, TreeNode *T2)
{
if(T2==nullptr && T1==nullptr)
return true;
if (T1 != nullptr && T2!=nullptr && T1->val == T2->val)
{
return hasSubtree(T1->left,T2->left) && hasSubtree(T1->right,T2->right);
}
return false;
}
只检测出了第一个重复数字,请问怎么判定第二个重复数字4呢?
如题
// 多个重复的数字
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));
}
这种情况,一个重复的数字都找不出来
在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");
}
书中写到:
当n>=5的时候,我们可以证明2(n-2)>n并且3(n-3)>n。也就是说,当绳子剩下的长度大于或者等于5的时候,我们就把它剪成长度为3或长度为2的绳子段
这个“也就是说”结论是怎么得出的?这个结论不是应该证明了3(n-3)>2(n-2)>.....>i(n-i)才能得出吗?
f(1)=1,f(2)=1,f(3)=2
所以不用考虑length=4,直接 int timsOf3 = length/3就行了
return (int)(pow(3,timsOf3));
请问能用int数组处理吗?为什么要选用char字符数组处理?
求数字序列中某一位的数字,可以遍历建立哈希表,key为下标,value为数列中对应的值,直接查表就好了啊
page 185 求路径和,返回上一层的时候,currentSum忘记减去pop出的那个节点的值
是否需要先删除 visited
delete[] visited;
return true;
该题目已经说明了长度为 n+1 的数组所有数字都在 1~n 范围,那么这个 n 至少应该是 1,否则就没有意义了,所以代码里面有一处判断
if (numbers == nullptr || length <=0)
return -1;
应该是
if (numbers == nullptr || length <= 1)
return -1;
我咋一个都运行不成功
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;
}
我有点疑惑为什么要用两层while循环,第二层的while改为if会不会更好一点,因为第二层只是一个判断并不会进入循环
请问用什么编译器编译啊?DEV报错collect.exe的错误
假如前四个数字数字刚刚好,那是不是要把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 ;
/**
* 题目:输入一个整型数组,数组里有正数也有负数。数组中的一个或
* 连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复
* 杂度为 O(n)。
*
* @author flying
*/
public class Q42_MaxSubSequence {
/**
* 1. 把数组的变化,看作是连绵起伏的山谷。连续的非负数序列是一段山,连续的负数序列是一段谷,山谷交错。
* 2. 山和谷都以自己最右侧的坐标命名,记作 n
* 2. 如果只有一段山 n,那么最大值就是这段山的面积 sum(n)。
* 3. 在一段山的基础上添加谷 n,那么最大值是 sun(山n) 的面积, 然后把这段山谷整合起来成为一段山,整合后的山的面积是:
* sum(山-谷) > 0 ? sum(山-谷) : 0;, 这个记作 sum'(n), sum'(n) 不等于 sum(n), sum(n)
* 4. 这样的话,长度为 n 的山谷序列中,最大值连续序列 max_n = max(max(n-1), sum(n) + sum'(n -1))。
* 5. 从第一段开始求,一直递推到 第 n 段,可以在 o(n) 的时间内搞定。
* 为了让代码看上去行数更少,我合并了一些连续的赋值运算,以及省略掉了大括号。
*/
private int maxSubSequence(int[] array) {
if (array == null)
throw new IllegalArgumentException("param is invalid");
int max = 0, sumMount = 0;
for (int i : array)
max = Math.max(max, sumMount = Math.max(0, sumMount + i));
return max;
}
public void test() {
System.out.println(maxSubSequence(new int[] {1}));
System.out.println(maxSubSequence(new int[] {0}));
System.out.println(maxSubSequence(new int[] {-1, -2, -3, -4, -5}));
System.out.println(maxSubSequence(new int[] {1, -2, 3, 10, -4, 7, 2, -5}));
}
}
常规解法中设置一个flag,每次讲flag右移1位并与原来的数字做与运算。书中给的判断条件是 if(n&flag),这个判断是错的。正确的判别式应该是if((n&flag)==flag)。很容易理解,flag从1,2,4,....不断右移,此时按位与得到的结果应该是只有这一位是1,其余全是零,即是flag。作者也帮忙看一下这个想法对嘛
每遇到一个*,就会产生一个分支,,指数级别的复杂度。
用编译原理里面的方法进行优化也好,用动态规划来做也行。如此暴力的解决方式会给人误导的。
作者在面试题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.第二版书中,面试12的hasPath函数的形参表matrix和str书中为char *,但应该都为const char *应该才能保证字符串数组和矩阵不被修改,并且github中代码是定义成const char *的;
2.存在内存泄漏,在查找通路成功后没有释放visited的内存。
执行时发生段错误:segmentation fault (core dumped)
按我的理解,这五行代码意思是,此时定位错误,退回到上一个定位。但是,上一个定位处的情况,都已经有递归代码进行检测了,这个回退貌似是多次一举。或者我理解有误,还望指教。
第三种解法,作者声称的即全面又高效的解法,PowerWithUnsignedExponent(double base, unsigned int exponent),当 exponent < 0时,答案错误
如题,明明还有剪成m段的要求,但解法中没有考虑到。比如长度为8的绳子,要求剪成2段最大就是4*4=16,要求剪成3段最大就是3*3*2=18,要求剪成4段最大就是2*2*2*2=16。但参考解法中只要输入8输出一定就是18,很疑惑。
看解法发现并没有用到题干所要求的剪成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;
}
我看了一下,代码是没有问题,但我觉得思路有一点问题,书中的代码是这样的
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;
}
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)?
编译有问题:
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 个 ==========
这道题目有问题,题目说的是:给你一根长度为n的绳子,请把绳子剪成m段,求最大值,而解法却是剪任意段求最大值,并没有限制剪的段数。
比如一段绳子长度为 7,要求剪成 7段,那么答案就不是12 了,12是绳子能剪成的最大长度,但只有剪成2段或者3段才能得到12,剪成7段长度不可能为12。
代码的解法是不限制绳子的段数的,或许是我没有理解清楚代码,还请解惑
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.