【剑指Offer】俯视50题之31 - 40题
2024-09-30 14:56:51
面试题31连续子数组的最大和
面试题32从1到n整数中1出现的次数
面试题33把数组排成最小的数
面试题34丑数
面试题35第一个仅仅出现一次的字符
面试题36数组中的逆序对
面试题37两个链表的第一个公共结点
面试题38数字在排序数组中出现的次数
面试题39二叉树的深度
面试题40数组中仅仅出现一次的数字
/*******************************************************/
面试题31连续子数组的最大和 ，输入一个数组。数组里面有正数，也有负数。
求连续数的最大值
实现例如以下：
int MaxSum(int num[], int length)
{
int CurrentSum = 0;
int iResult = 0x80000000; if (num == NULL || length < 0)
{
return 0;/* invalid */
} for (int i = 0; i < length; i++)
{ if (CurrentSum <= 0)
{
CurrentSum = num[i];
}
else
{
CurrentSum += num[i];
} if (CurrentSum > iResult)
iResult = CurrentSum;
}
return iResult;
}
面试题32从1到n整数中1出现的次数 ，输入一个N，求1到N全部的整数中1出现的次数
实现例如以下：
#include <iostream> int CountNum(int n)
{
int iCurrentNum = 0;/* 当前位的数 */
int iNTemp = n;
int iResult = 0;
int iBase = 1; /* 个位 */
int iRemain = 0; if (n <= 0)
{
return 0;
} while (iNTemp > 0)
{
iCurrentNum = iNTemp % 10;
iNTemp = iNTemp/10; if (iCurrentNum > 1)
{
iResult+= (iNTemp + 1)*iBase;
}
else if (iCurrentNum == 1)
{
iResult+= (iNTemp)*iBase + iRemain + 1;
}
else if (iCurrentNum == 0)
{ iResult+= (iNTemp)*iBase;
} iRemain += iCurrentNum*iBase; /* 先计算剩余数大小*/
iBase = iBase*10; /**然后计算下次base位*/
} return iResult;
} int main()
{
printf("%d\n",CountNum(11));
}
面试题33把数组排成最小的数
实现例如以下：
#include <iostream>
#define MAX_NUM_LENGTH 10 int compare(const void *str1, const void *str2)
{
char str1Temp[MAX_NUM_LENGTH*2 +1];
char str2Temp[MAX_NUM_LENGTH*2 +1]; strcpy(str1Temp, (const char*)str1);
strcat(str1Temp, (const char*)str2); strcpy(str2Temp, (const char*)str2);
strcat(str2Temp, (const char*)str1); return strcmp(str1Temp,str2Temp); }
void GetMinNum(int num[], int length)
{
char **numStr = (char **)malloc(length + 1);
for (int i = 0; i < length; i++)
{
numStr[i] = (char *)malloc(MAX_NUM_LENGTH +1);
sprintf(numStr[i],"%d",num[i]);
}
qsort(numStr,length,sizeof(char *),compare); for (int i = 0; i < length; i++)
{
printf("%s",numStr[i]);
} /* 释放内存 */
for (int i = 0; i < length; i++)
{
free(numStr[i]);
}
free(numStr); } int main()
{
int num[] = {1,234,341};
GetMinNum(num, 3);
}
面试题34丑数
实现例如以下：
#include <iostream>
#define MAX_NUM_LENGTH 10 int min(int a, int b, int c)
{
int min = (a>b)?b:a;
min = (min > c)? c:min; return min;
}
/* 仅仅能被2、3、5整除的 */
int GetUglyNum(int n)
{
/* 创建一个n个元素的数组 */
int UglyNum[n];
int p2 = 0;
int p3 = 0;
int p5 = 0;
int NextIndex = 1;
UglyNum[0] = 1; while(NextIndex < n)
{
UglyNum[NextIndex] = min(UglyNum[p2]*2, UglyNum[p3]*3 ,UglyNum[p5]*5); while(UglyNum[p2]*2 <= UglyNum[NextIndex])
{
p2++;
}
while(UglyNum[p3]*3 <= UglyNum[NextIndex])
{
p3++;
}
while(UglyNum[p5]*5 <= UglyNum[NextIndex])
{
p5++;
} NextIndex++;
} return UglyNum[NextIndex - 1];
} int main()
{
printf("%d\n",GetUglyNum(3)); }
面试题35第一个仅仅出现一次的字符
实现例如以下：
#include <iostream>
#define VOS_OK 0
#define VOS_ERR 1 /* 仅仅能被2、3、5整除的 */
int GetFirstChar(char *str, char *result)
{
unsigned int hashNum[256] = {0};
char *p; if (str == NULL)
{
return VOS_ERR;
} p = str;
while(*p != '\0')
{
hashNum[*p]++;
p++;
} p = str;
while(*p!= '\0')
{
if (hashNum[*p] == 1)
{
*result = *p;
return VOS_OK;
}
p++;
}
return VOS_ERR; } int main()
{
char iChar;
if (VOS_OK == GetFirstChar("aabcddb", &iChar))
{
printf("%c\n",iChar);
}
else
{
printf("Error!");
}
}
面试题36数组中的逆序对
实现例如以下：
/* 求数组中的逆序对 */
#include <iostream>
#define VOS_OK 0
#define VOS_ERR 1
int Merge(int *numA, int begin,int mid, int end)
{
int startA = begin;
int startB = mid + 1;
int *numB = (int *)malloc(sizeof(int)*(end + 1));
int currentIndex = 0;
long long result = 0; if (numA == NULL || begin > mid || mid > end)/* 其余异常函数调用处保证 */
{
return 0;
} while (startA <=mid && startB <= end)
{
if (numA[startA] <= numA[startB])
{
numB[currentIndex] = numA[startA++];
}
else
{
numB[currentIndex] = numA[startB++];
/* 前面的大于后面的，则前数组之后的元素也大于该元素 */
result += mid - startA + 1;
} currentIndex++;
} while (startA <= mid)
{
numB[currentIndex++] = numA[startA++];
} while (startB <= end)
{
numB[currentIndex++] = numA[startB++];
} for (int i = begin; i <= end; i++)
{
numA[i] = numB[i];
}
free(numB); return result; } int MergeSort(int *num, int start, int end)
{
int result = 0;
int mid;
if (num == NULL || start >= end) /* 注意start == end 的时候*/
{
return 0;
} mid = (start + end)>>1;
result = MergeSort(num, start, mid) + MergeSort(num, mid +1, end);
result += Merge(num,start,mid,end); return result; } int main()
{
int num[]={2,1,3,5,6}; printf("%d\n",MergeSort(num, 0, 4));
}
面试题37两个链表的第一个公共结点
实现例如以下：
1）暴力法
每次遍历链表A,然后将链表A中当前结点在链表B中查找。假设找到则停止查找，返回。
2）空间换取时间
将两个链表都入栈，然后从最后一个结点開始比較。直到不相等为止。
3）同一时候向后查找
先遍历链表A得长度lengthA。再遍历链表B得长度lengthB
假如A比B长n。则A先走n步，假如B比A长n，则B先走n步。
然后同一时候向后走，直到第一个相等的结点
面试题38数字在排序数组中出现的次数
有两种思路：利用二分查找法，找到该数中间出现的位置，然后分别向前后遍历同样数，可得到该数出现的次数
利用二分查找法，找打该数最左边及最右边出现的位置。然后就能够求得该数出现的次数
左右查询实现例如以下：
#include <iostream>
int MaxSum(int num[], int length, int value)
{
int iResult = 0;
int i = 0;
int j = length - 1;
int mid;
int k; while(i <= j )
{
mid = (i + j)>>1;
if (num[mid] > value)
{
j= mid - 1;
}
else if (num[mid] < value)
{
i = mid + 1;
}
else
{
/* 向左查询*/
k = mid-1;
while (k >= i &&(num[k] == value))
{
k--;
iResult++;
}
/* 向右查询*/
k = mid+1;
while (k <= j &&(num[k] == value))
{
k++;
iResult++;
}
printf("================");
return iResult + 1;
}
} return iResult;
} int main()
{
int num[]={2,2,2,2,5,5,6,6}; printf("%d\n",MaxSum(num, 8, 2) );
getchar();
}
第二种实现方法：
#include <iostream>
int GetFirstK(int num[], int length, int value)
{
int mid;
int i = 0;
int j = length - 1; if (num == NULL)
{
return 0;
} while (i <= j)
{
mid = (i + j)>>1; if (num[mid] > value)
{
j = mid - 1;
}
else if (num[mid] < value)
{
i = mid + 1;
}
else
{
if (mid -1 >= 0 && (num[mid - 1] == value))
{
j = mid - 1;
}
else
{
return mid;
}
}
} return 0;
} int GetLastK(int num[], int length, int value)
{
int mid;
int i = 0;
int j = length - 1; if (num == NULL)
{
return 0;
} while (i <= j)
{
mid = (i + j)>>1; if (num[mid] > value)
{
j = mid - 1;
}
else if (num[mid] < value)
{
i = mid + 1;
}
else
{
if (mid + 1 <= j && (num[mid + 1] == value))
{
i = mid + 1;
}
else
{
return mid;
}
}
} return 0;
} int main()
{
int num[]={2,2,2,2,5,5,6,6}; printf("%d\n",GetLastK(num, 8, 2) - GetFirstK(num, 8, 2) + 1);
getchar();
}
面试题39二叉树的深度
实现例如以下：
int DepthTree(BinaryNode *root)
{
int leftDepth = 0;
int rightDepth = 0; if (root == NULL)
{
return 0;
} leftDepth = DepthTree(root->lchild);
rightDepth = DepthTree(root->rchild); retrun (leftDepth > rightDepth)? (leftDepth + 1):(rightDepth + 1);
}
扩展题目：推断一个树是否是平衡二叉树
实现例如以下：
bool IsBlanceTree(BinaryNode *root, int *depth)
{
int leftDepth = 0;
int rightDepth = 0;
int diff; if (root == NULL)
{
return true;
} leftDepth = DepthTree(root->lchild);
rightDepth = DepthTree(root->rchild); if (IsBlanceTree(root->lchild, &leftDepth)
&&IsBlanceTree(root->rchild, &rightDepth))
{
diff = leftDepth - rightDepth;
if (diff < 1 && diff > -1)
{
*depth = (leftDepth > rightDepth)? (leftDepth + 1):(rightDepth + 1);
return true;
}
} retrun false;
}
面试题40数组中仅仅出现一次的数字 ：给一个数组，数组中有两个数仅仅出现一次。其余数出现两次，求这两个数
思路：将数组分成两组，分别异或去重。怎样分组呢？分组依据异或之后。最后一位二进制值为1的位分组。对数组一进行异或最后得一个数。对数组二异或。最后得还有一个数。
则最后得到的两个数是所求的数。
实现例如以下：
int FindFirstBitIsOne(int resultOR)
{
for (int i = 0; i < 32; i++)
{
if (resultOR & (1 << i))
{
return i;
}
}
return 0; } int IsBitOne(int data, int indexOfOne)
{
return data & (1<<indexOfOne); }
void FindNumsAppearOnce(int data[],int length,int *num1,int num2)
{
if (data == NULL || length < 2)
{
return;
}
int resultOR = 0;
for (int i = 0; i < length; i++)
{
resultOR ^=data[i];
} int indexOfOne = FindFirstBitIsOne(resultOR); for (int j = 0; j < length; j++)
{
if (IsBitOne(data[j], indexOfOne))
{
*num1 ^=data[j];
}
else
{
*num2^=data[j];
}
} }
最新文章
- Warning C4819
- 【真的是随笔】如何利用htaccess把网站流量引到一个页面上（站点维护页效果）
- MRBS, meeting room manager system,会议预定管理系统
- java中的接口回调
- 使用dev http client调试restful API开发
- Light oj 1005 - Rooks (找规律)
- Android 官方文档：（二）应用清单 —— 2.2 &lt;action&gt;标签
- ceph启动脚本
- js中点击空白区域时文本框与隐藏层的问题
- 遇过的坑(2)—MyISAM表类型不支持事务操作
- C++ primer 练习 12.7
- [图形学] 结束 [Unity Shader] 开始
- 【head first python】1.初识python 人人都爱列表
- workqueue --最清晰的讲解
- cf1076d 贪心最短路
- linux中环境变量PATH设置错误，导致ls cd 等命令不能使用，提示：没有那个文件或目录
- MYSQL的基本函数 （加密函数）
- intellj idea show "run dashboard" panel
- lnmp手动新建虚拟机
- Vim 手记：语法高亮