剑指offer.C++.code51-55 剑指offer.C++.code51-55

51. 数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

// Solution:(1)哈希表——时间复杂度O(n)，空间复杂度O(n) class Solution { public: // Parameters: //numbers:an array of integers //length:the length of array numbers //duplication: (Output) the duplicated number in the array number // Return value:true if the input is valid, and there are some duplications in the array number //otherwise false bool duplicate(int numbers[], int length, int* duplication) { if(numbers==NULL || length==0) return 0; vector duplication_flag(length, false); for (int i = 0; i < length; i ++) { if (duplication_flag[numbers[i]] == true) { duplication[0] = numbers[i]; return true; } duplication_flag[numbers[i]] = true; } return false; } };

// Solution:(2)利用哈希表性质 // 利用了哈希的特性，但不需要额外的存储空间。因此时间复杂度为O(n)，不需要额外空间！ // 把当前序列当成是一个下标和下标对应值是相同的数组； // 遍历数组，判断当前位的值和下标是否相等： 2.1. 若相等，则遍历下一位； // 2.2. 若不等，则将当前位置i上的元素和a[i]位置上的元素比较：若它们相等，则找到第一个重复元素！ // 若不等，则将它们两交换。换完之后a[i]位置上的值和它的下标是对应的，但i位置上的元素和下标并不一定对应； // 重复2.2的操作，直到当前位置i的值也为i，将i向后移一位，再重复2. class Solution { public: // Parameters: //numbers:an array of integers //length:the length of array numbers //duplication: (Output) the duplicated number in the array number // Return value:true if the input is valid, and there are some duplications in the array number //otherwise false bool duplicate(int numbers[], int length, int* duplication) { if(numbers==NULL || length==0) return 0; for (int i = 0; i < length; i ++) { if (numbers[i] != i) { if (numbers[i] == numbers[numbers[i]]) { // 找到重复元素 duplication[0] = numbers[i]; return true; } else { int tmp = numbers[i]; numbers[i] = numbers[tmp]; numbers[tmp] = tmp; } } } return false; } };

52. 构建乘积数组【分解为前后两部分，分别累积乘】

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0] * A[1] * ... * A[i-1] * A[i+1] * ... * A[n-1]。不能使用除法。

【剑指offer.C++.code51-55】B[i]的值可以看作下图的矩阵中每行的乘积。
下三角用连乘可以很容求得，上三角，从下向上也是连乘。
因此，先算下三角中的连乘，即我们先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。

上下三角

class Solution { public: vector multiply(const vector& A) { vector B; if (A.size() == 0) return B; int tmp = 1; B.push_back(tmp); for (int i = 1; i < A.size(); i ++) { tmp *= A[i-1]; B.push_back(tmp); } tmp = 1; for (int i = B.size()-2; i >= 0; i --) { tmp *= A[i+1]; B[i] *= tmp; } return B; } };

53. 正则表达式匹配【根据下一位是否*，分类讨论】

请实现一个函数用来匹配包括'.'和' * '的正则表达式。模式中的字符'.'表示任意一个字符，而' * '表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab * ac * a"匹配，但是与"aa.a"和"ab * a"均不匹配。

// Solution: // 当模式中的第二个字符不是“*”时： // 1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。 // 2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。 // 而当模式中的第二个字符是“*”时： // 如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式： // 1、模式后移2字符，相当于x*被忽略； // 2、字符串后移1字符，模式后移2字符； // 3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位； class Solution { public: bool match(char* str, char* pattern) { if (str == NULL || pattern == NULL) return false; return matchCore(str, pattern); } bool matchCore(char* str, char* pattern) { if (*pattern == '\0' && *str == '\0') return true; if (*pattern == '\0' && *str != '\0') return false; if (*(pattern + 1) != '*') { if (*str == *pattern || (*pattern == '.' && *str != '\0')) return matchCore(str + 1, pattern + 1); } else if (*(pattern + 1) == '*') { if (*str == *pattern || (*pattern == '.' && *str != '\0')) // 第一个字符不匹配 return (matchCore(str, pattern + 2) || matchCore(str + 1, pattern + 2) || matchCore(str + 1, pattern)); else// 第一个字符不匹配 return matchCore(str, pattern + 2); } return false; } };

54. 表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

// Solution: // 1>整数：首位+或-，其余都是0~9； // 2>小数：首位+或-，跟随0~9，仅一位小数点，后续有两种情况，一是仅有0~9，二是有可能有0~9并且有科学表示法结尾 // 3>科学表示法结尾：首位e/E，可能有+/-，随后都跟随整数 class Solution { public: bool isNumeric(char* string) { if (string == NULL) return false; if (*string == '+' || *string == '-') string ++; if (*string == '\0') return false; bool numFlag = true; scanDigits(&string); // 整数(或前半部分) if (*string != '\0') { if (*string == '.') { // 小数点 string ++; scanDigits(&string); if (*string == 'e' || *string == 'E') //科学表示法的结尾 numFlag = isExponential(&string); } else if (*string == 'e' || *string == 'E') { //科学表示法的结尾 numFlag = isExponential(&string); } else { numFlag = false; } } return numFlag && *string == '\0'; }void scanDigits(char** string) { while (**string != '\0' && **string <= '9' && **string >= '0') (*string) ++; }bool isExponential(char** string) { if (**string != 'e' && **string != 'E') return false; (*string) ++; if (**string == '+' || **string == '-') (*string) ++; if (**string == '\0') return false; scanDigits(string); return (**string == '\0') ? true: false; }};

55. 字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
输出描述：如果当前字符流没有存在出现一次的字符，返回#字符。

// Solution:使用哈希表存ch首次出现的位置index，或者标记未出现(-1)、出现多次(-2)。最后扫描其中最小的index class Solution { private: int occurrence[256]; //ASCII仅有256个 int index; public: Solution() {// 注意初始化 index = 0; for (int i = 0; i < 256; i ++) occurrence[i] = -1; } //Insert one char from stringstream void Insert(char ch) { if (occurrence[ch] == -1)// ch首次出现 occurrence[ch] = index; else if (occurrence[ch] >= 0) // ch重复出现 occurrence[ch] = -2; index ++; } //return the first appearence once char in current stringstream char FirstAppearingOnce() { char ch = '#'; int minIndex = numeric_limits::max(); for (int i = 0; i < 256; i ++) { if (occurrence[i] >= 0 && occurrence[i] < minIndex) { ch = (char)i; minIndex = occurrence[i]; } } return ch; }};