面试题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 ",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 ",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 != '