**一. 题目描述** Implement wildcard pattern matching with support for ‘?’ and ‘*’. ‘?’ Matches any single character. ‘*’ Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). The function prototype should be:  bool isMatch(const char *s, const char *p) Some examples: ~~~ isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "*") → true isMatch("aa", "a*") → true isMatch("ab", "?*") → true isMatch("aab", "c*a*b") → false ~~~ **二. 题目分析** 题目的大意是，给出两串字符串`s`和`p`，规定符号`?`能匹配任意单个字符，`*`能匹配任意字符序列（包括空字符序列）。如果两串字符串完全匹配则返回`true`。 该题的难点主要在于出现`*`时的匹配操作。和网上大多数做法相似，一开始使用递归完成，结果总是超时。后来使用几个变量用于记录遇到`p`中的`*`时的下标，每次遇到一个`*`，就保留住当前字符串`s`和`p`的下标，然后s从当前下标往后扫描，如果不匹配，则s的下标加一，重复扫描。 **三. 示例代码** ~~~ #include #include using namespace std; class Solution { public: bool isMatch(string s, string p) { int s_size = s.size(); int p_size = p.size(); int s_index = 0, p_index = 0; int temp_s_index = -1, temp_p_index = -1; while (s_index < s_size) { if (p[p_index] == '?' || p[p_index] == s[s_index]) { ++p_index; ++s_index; continue; } if (p[p_index] == '*') { temp_p_index = p_index; temp_s_index = s_index; ++p_index; continue; } if (temp_p_index >= 0) { // 字符串p可能有多个*，因此只要出现过*，则需要更新当前匹配的下标 p_index = temp_p_index + 1; s_index = temp_s_index + 1; // 当前坐标s与p不匹配，则s的坐标在原基础上加一，继续循环 ++temp_s_index; continue; } return false; } while (p[p_index] == '*') ++p_index; return p_index == p_size; } }; ~~~ **四. 小结** 这种题目一般递归的思路还是首选，但递归的最大缺点就是耗时。该题若使用动态规划也可以解决，但是未必能达到以上方法的

**一. 题目描述** Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples. ~~~ [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0 ~~~ **二. 题目分析** 题目的大意是，给定一个已排序的数组和一个目标值`target`，如果在数组中找到该目标值，就返回这个目标值的元素下标。如果没有找到，就返回`target`应该插入到该数组中的位置下标。这个过程中，假设该数组中没有重复元素。 和[Search for a Range](http://blog.csdn.net/liyuefeilong/article/details/50403616) 的解法类似，二分查找即可，可能出问题的地方是对边界条件的处理。 **三. 示例代码** ~~~ #include #include using namespace std; class Solution { public: int searchInsert(vector& nums, int target) { int n = nums.size(), low = 0, high = n - 1, midIndex = 0; while (low <= high) { midIndex = (low + high) / 2; if (nums[midIndex] == target) return midIndex; else if (nums[midIndex] > target) high = midIndex - 1; else low = midIndex + 1; } // 边界 if (low > n) return n; if (high < 0) return 0; } }; ~~~ 解题结果：  **四. 小结** 二分查找的经典题目，对边界的情况需要额外考虑。该题实际上是实现：`std::lower_bound()` 的功能。

**一. 题目描述** You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions `[1, 2, ..., n]` and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API `bool isBadVersion(version)` which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API. **二. 题目分析** 题目说了一堆，一开始并不知道是想让干什么。后来去网上查了题意，引用如下： 你是一名产品经理，并领导团队开发一个新产品。不幸的是，产品的最终版本没有通过质量检测。由于每一个版本都是基于上一个版本开发的，因此某一个损坏的版本之后的所有版本全都是坏的。 假设有n个版本[1, 2, …, n]，现在你需要找出第一个损坏的版本，它导致所有后面的版本都坏掉了。 提供给你一个API `bool isBadVersion(version)`，其功能是返回某一个版本是否损坏。实现一个函数找出第一个损坏的版本。你应该最小化调用API的次数。 原来只需实现类似于[Search for a Range](http://blog.csdn.net/liyuefeilong/article/details/50403616) 的功能，判断坏版本的函数`bool isBadVersion(version)`题目已经提供，无需纠结如何操作，这里还是使用二分查找来解决问题。 **三. 示例代码** 期初使用如下代码一直提示：Time Limit Exceeded ~~~ // Forward declaration of isBadVersion API. bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int low = 1, high = n; int midIndex = 0; while (low <= high) { midIndex = (low + high) / 2; if (isBadVersion(midIndex)) high = midIndex - 1; else low = midIndex + 1; } return low; } }; ~~~ 检查了一段时间，发现当n取很大的数时出现问题，原来是语句`midIndex = (low + high) / 2;` 直接相加时溢出，导致循环超时，该用以下代码Accept。 ~~~ // Forward declaration of isBadVersion API. bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int low = 1, high = n; int midIndex = 0; while (low <= high) { midIndex = low + (high - low) / 2; if (isBadVersion(midIndex)) high = midIndex - 1; else low = midIndex + 1; } return low; } }; ~~~ **四. 小结** 该题的难度在[Search for a Range](http://blog.csdn.net/liyuefeilong/article/details/50403616) 之下，但出现了数据溢出的问题，因此对于简单一些的题也时刻不能掉以轻心啊。

**一. 题目描述** Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of `O(logn)`. If the target is not found in the array, return `[-1, -1]`. For example, Given `[5, 7, 7, 8, 8, 10]` and target value `8`, return `[3, 4]`. **二. 题目分析** 题目大意是，给定一个已排序的序列和一个目标数字`target`，在这个序列中寻找等于`target`的**元素的下标范围**。由于序列已经排好序，直接用二分查找，分别求等于`target`的最靠左的元素下标`left`和最靠右的元素下标`right`即可。 **三. 示例代码** ~~~ #include #include using namespace std; class Solution { public: vector searchRange(vector& nums, int target) { int n = nums.size(); int left = searchRangeIndex(nums, target, 0, n - 1, true); int right = searchRangeIndex(nums, target, 0, n - 1, false); vector result; result.push_back(left); result.push_back(right); return result; } private: int searchRangeIndex(vector& nums, int target, int low, int high, bool isLeft) { while (low <= high) { int midIndex = (low + high) >> 1; if (nums[midIndex] == target) { int temp = -1; if (isLeft) { if (nums[midIndex] == nums[midIndex - 1] && low < midIndex) temp = searchRangeIndex(nums, target, low, midIndex - 1, true); } else { if (nums[midIndex] == nums[midIndex + 1] && high > midIndex) temp = searchRangeIndex(nums, target, midIndex + 1, high, false); } return temp == -1 ? midIndex : temp; // temp == -1时表示只有中间一个值等于target } else if (nums[midIndex] > target) high = midIndex - 1; else low = midIndex + 1; } return -1; // 找不到target，输出-1 } }; ~~~  **四. 小结** 注意题目要求`O(logn)`的时间复杂度，算法写的不好可能会超时。

**一. 题目描述** Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library’s sort function for this problem. Follow up:  A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s,  then 1’s and followed by 2’s. Could you come up with an one-pass algorithm using only constant space? **二. 题目分析** 题目一开始说到一组对象，包含红白蓝三种颜色，然后要对他们进行排序，说白了就是对一个只含有`0, 1, 2`三个数字的数组从小到大排序。 题目要求：come up with an one-pass algorithm using only constant space，因此只能扫描一次。这里采取的方法是，统计`0, 1, 2`三个数字分别出现的次数，再将数组nums重新构建为从0到2排列的数组，这种方法没有使用数组元素间的交换，只需扫描一次nums。 **三. 示例代码** ~~~ #include #include using namespace std; class Solution { public: void sortColors(vector& nums) { int SIZE = nums.size(); int count[3] = {0, 0, 0}; for (int i = 0; i < SIZE; ++i) ++count[nums[i]]; for (int i = 0, index = 0; i < 3; ++i) for (int j = 0; j < count[i]; ++j) nums[index++] = i; } }; ~~~ 一个测试结果：  **四. 小结** 本题的解法还是挺多的，可多参考网上的其他解法。

**一. 题目描述** Given an unsorted integer array, find the first missing positive integer. For example,  Given `[1,2,0]` return `3`,  and `[3,4,-1,1]` return `2`. Your algorithm should run in O(n) time and uses constant space. **二. 题目分析** 该题的大意是给定一个未排序的数组，该数组可能包含零或正负数，要求找出第一个未出现的正数。例如`[1, 2, 0]`，由于第一个未出现的正整数是`3`，则返回`3`；`[3, 4, -1, 1]`第一个未出现的正整数是`2`，则返回`2`。算法要求在`O(n)`的时间复杂度及常数空间复杂度内完成。 一种方法是，先把数组里每个正整数从`i`位放到第`i-1`位上，这样就形成了有序的序列，然后检查每一下标`index`与当前元素值，就能知道当前下标所对应的正整数是否缺失，若缺失则返回下标`index + 1`即可。 **三. 示例代码** ~~~ #include #include using namespace std; class Solution { public: int firstMissingPositive(vector& nums) { int n = nums.size(); for (int i = 0; i < n; ++i) { int temp = 0; while (i + 1 != nums[i] && nums[i] != nums[nums[i] - 1] && nums[i] > 0) { temp = nums[i]; nums[i] = nums[temp - 1]; nums[temp - 1] = temp; } } for (int i = 0; i < n; ++i) { if (i + 1 != nums[i]) return i + 1; } return n + 1; } }; ~~~

**一. 题目描述** Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3\. For “bbbbb” the longest substring is “b”, with the length of 1. **二. 题目分析** 题目的大意是，给出一串字符串，找出无重复字符的最长子串，输出其长度。可以使用两个指针，一个指向当前子串的头，一个指向尾，尾指针不断往后扫描，当有字符前面出现过，记录当前子串长度和最优解的比较结果。然后头指针不断往后扫描，直到扫描到一个字符和尾指针相同，则尾指针继续扫描，当尾指针到达字符串结尾时算法结束。算法复杂度O(n) + O(n) = O(n)。 **三. 示例代码** ~~~ class Solution { private: bool canUse[256]; public: int lengthOfLongestSubstring(string s) { // Start typing your C/C++ solution below // DO NOT write int main() function memset(canUse, true, sizeof(canUse)); int count = 0; int start = 0; int ret = 0; for(int i = 0; i < s.size(); i++) { if (canUse[s[i]]) { canUse[s[i]] = false; count++; } else { ret = max(ret, count); while(true) { canUse[s[start]] = true; count--; if (s[start] == s[i]) break; start++; } start++; canUse[s[i]] = false; count++; } } ret = max(ret, count); return ret; } }; ~~~ **四. 小结** 参考：[http://www.cnblogs.com/remlostime/archive/2012/11/12/2766530.html](http://www.cnblogs.com/remlostime/archive/2012/11/12/2766530.html)

**一. 题目描述** Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example:  Given array `A = [2,3,1,1,4]` The minimum number of jumps to reach the last index is 2\. (Jump 1 step from index 0 to 1, then 3 steps to the last index.) **二. 题目分析** 该题的大意是，给定一个数组，每个元素代表从该位置可以往后跳的距离，问从第一个位置跳到最后一个位置至少需要跳多少次。 与 Jump Game 有所不同的是，Jump Game 询问该数组能否跳到最后一格，这道题要求算出跳的次数。解决的思路依旧是贪心，只需设置一个数组用来记录跳的路径即可。 **三. 示例代码** ~~~ class Solution { public: int jump(int A[], int n) { int result = 0; // 当前已跳跃的次数 int last = 0; // 上一跳可达到的最远距离 int curr = 0; // 当前一跳可达到的最远距离 for (int i = 0; i < n; ++i) { // 无法向前继跳直接返回 if(i > curr) return -1; // 需要进行下次跳跃，则更新last和当前已执行的跳数result if (i > last) { last = curr; ++result; } // 更新当前可跳达的最远处 curr = max(curr, i+A[i]); } return result; } }; ~~~ **四. 小结** 类似的解题思路还有BFS，后期可以验证验证。

**一. 题目描述** Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example:  `A = [2,3,1,1,4]`, return true.  `A = [3,2,1,0,4]`, return false. **二. 题目分析** 该题的大意是，给定一个数组，从第一个元素开始，元素的值表示能够往后跳的最大距离，问按照这种规则，该数组是否能跳到最后一个元素。 解题的基本思路是贪心算法。当然，使用动态规划也是完全可以解决的，也贴出网上一种动规代码。 **三. 示例代码** ~~~ // greedy algorithm class Solution { public: bool canJump(int A[], int n) { if(n == 0 || n == 1){ return true; } int maxStep = A[0]; for(int index = 1 ; index < n ; ++index) { if(maxStep == 0) return false; --maxStep; if(maxStep < A[index]) maxStep = A[index]; if(maxStep + index >= n - 1) // 满足条件 return true; } } }; ~~~ ~~~ // DP algorithm class Solution { public: bool canJump(int A[], int n) { vector f(n, 0); f[0] = 0; for (int i = 1; i < n; i++) { f[i] = max(f[i - 1], A[i - 1]) - 1; if (f[i] < 0) return false; } return f[n - 1] >= 0; } }; ~~~ **四. 小结** 该题的思路是，使maxStep一直保持最大的能移动步数。

**一. 题目描述** Given a matrix ofmn elements (mrows, n columns), return all elements of the matrix in spiral order.  For example, Given the following matrix: ~~~ [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] ~~~ You should return `[1,2,3,6,9,8,7,4,5]`. **二. 题目分析** 题意：给定一个m*n的矩阵，从外围一层一层的打印出矩阵中的元素内容。解题的方法有多种，以下采用的方法是，使用四个数字分别记录上下左右四个边界的位置（beginX，endX，beginY，endY），不断循环以收窄这些边界，最终当两个边界重叠时，结束循环。 同时，当循环完成后，即得到所求数组。 **三. 示例代码** ~~~ class Solution { public: vector spiralOrder(vector >& matrix) { vector result; if (matrix.empty()) return result; int beginX = 0, endX = matrix[0].size() - 1; int beginY = 0, endY = matrix.size() - 1; while (1) { // 从左到右 for (int i = beginX; i <= endX; ++i) result.push_back(matrix[beginY][i]); if (++beginY > endY) break; // 从上到下 for (int i = beginY; i <= endY; ++i) result.push_back(matrix[i][endX]); if (beginX > --endX) break; // 从右到左 for (int i = endX; i >= beginX; --i) result.push_back(matrix[endY][i]); if (beginY > --endY) break; // 从下到上 for (int i = endY; i >= beginY; --i) result.push_back(matrix[i][beginX]); if (++beginX > endX) break; } return result; } }; ~~~

**一. 题目描述** Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that: • Only one letter can be changed at a time  • Each intermediate word must exist in the dictionary For example, Given: start = “hit”  end = “cog”  dict = [“hot”,”dot”,”dog”,”lot”,”log”] As one shortest transformation is ”hit” -> ”hot” -> ”dot” -> ”dog” -> ”cog”, return its length 5. Note: • Return 0 if there is no such transformation sequence.  • All words have the same length.  • All words contain only lowercase alphabetic characters. **二. 题目分析** 参考链接：[http://www.mamicode.com/info-detail-448603.html](http://www.mamicode.com/info-detail-448603.html) 可以将这道题看成是一个图的问题。我们将题目映射到图中，顶点是每个字符串，然后两个字符串如果相差一个字符则进行连边。我们的字符集只有小写字母，而且字符串的长度固定，假设是L。那么可以注意到每一个字符可以对应的边有25个（26个小写字母去掉自己），那么一个字符串可能存在的边是25*L条。接下来就是检查这些对应的字符串是否在字典内，就可以得到一个完整的图的结构。根据题目要求，等价于求这个图中一个顶点到另一个顶点的最短路径，我们一般用BFS广度优先。 这道题，我们只能用最简单的办法去做，每次改变单词的一个字母，然后逐渐搜索，这种求最短路径，树最小深度问题用BFS最合适。 和当前单词相邻的单词，就是和顶点共边的另一个顶点，是对当前单词改变一个字母且在字典内存在的单词。 找到一个单词的相邻单词，加入BFS队列后，我们要从字典内删除，因为不删除会造成类似hog->hot->hog这样的死循环。而且删除对求最短路径没有影响，因为我们第一次找到的单词肯定是最短路径，我们是层序遍历去搜索的，最早找到的一定是最短路径，即使后面的其他单词也能转换成它，路径肯定不会比当前的路径短。这道题仅要求求出最短路径长度，不需要求输出最短路径，所以可以删除这个单词。 BFS队列之间用空串”“来标示层与层的间隔，每次碰到层的结尾，遍历深度+1，进入下一层。 **三. 示例代码** ~~~ class Solution { public: int ladderLength(string start, string end, unordered_set &dict) { if(start.size() == 0 || end.size() == 0) return 0; queue wordQ; wordQ.push(start); wordQ.push(""); int path = 1; while(!wordQ.empty()) { string str = wordQ.front(); wordQ.pop(); if(str != "") { int len = str.size(); for(int i = 0; i < len; i++) { char tmp = str[i]; for(char c = 'a'; c <= 'z'; c++) { if(c == tmp) continue; str[i] = c; if(str == end) return path + 1; //如果改变后的单词等于end 返回path+1 if(dict.find(str) != dict.end()) { wordQ.push(str); dict.erase(str); //字典内删除这个词 防止反复走 } } str[i] = tmp; //重置回原来的单词 } } else if(!wordQ.empty()) { //到达当前层的结尾，并且不是最后一层的结尾 path++; wordQ.push(""); } } return 0; } }; ~~~

**一. 题目描述** Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. For example,  Given words = `["oath","pea","eat","rain"]` and board = ~~~ [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] ~~~ Return `["eat","oath"]`. Note:  You may assume that all inputs are consist of lowercase letters `a-z`. **二. 题目分析** 若沿用Word Search的方法，必定超时。 一种被广为使用的方法是使用字典树，网上的相关介绍不少，简单沿用一种说法，就是一种单词查找树，Trie树，属于树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。 其具体性质、查找方法等可参照：[http://baike.baidu.com/link?url=BR1qdZ2oa8BIRbgtD6_oVsaBhzRecDJ0MMFntUvPGNjpG3XgJZihyUdFAlw1Pa30-OFUsNJRWPSanHng65l-Ja](http://baike.baidu.com/link?url=BR1qdZ2oa8BIRbgtD6_oVsaBhzRecDJ0MMFntUvPGNjpG3XgJZihyUdFAlw1Pa30-OFUsNJRWPSanHng65l-Ja) 而具体的解题思路是： 1. 将待查找的单词储存在字典树Trie中，使用DFS在board中查找，利用字典树进行剪枝。 2. 每当找到一个单词时，将该单词从字典树中删去。 3. 返回结果按照字典序递增排列。 **三. 示例代码** 以下代码虽然使用字典树来改进dfs，但AC后发现算法还是比较耗时： ~~~ #include #include #include #include using namespace std; class TrieNode { public: TrieNode() // 构造函数 { for (int i = 0; i < 26; ++i) next[i] = NULL; end = false; } void insert(string s) { if (s.empty()) { end = true; return; } if (next[s[0] - 'a'] == NULL) next[s[0] - 'a'] = new TrieNode(); next[s[0] - 'a']->insert(s.substr(1)); // 右移一位截取字符串s，继续递归插入 } bool search(string key) { if (key.empty()) return end; if (next[key[0] - 'a'] == NULL) return false; return next[key[0] - 'a']->search(key.substr(1)); } bool startsWith(string prefix) { if (prefix.empty()) return true; if (next[prefix[0] - 'a'] == NULL) return false; return next[prefix[0] - 'a']->startsWith(prefix.substr(1)); } private: TrieNode *next[26]; bool end; }; class Tri { public: Tri(){ root = new TrieNode(); } void insert(string s) { root->insert(s); // 调用TrieNode类的方法 } bool search(string k) { return root->search(k); } bool startsWith(string p) { return root->startsWith(p); } private: TrieNode *root; }; class Solution { public: vector findWords(vector>& board, vector& words) { const int x = board.size(); const int y = board[0].size(); for (auto ptr : words) tree.insert(ptr); // 将候选单词插入字典树中 vector result; for (int i = 0; i < x; ++i) { for (int j = 0; j < y; ++j) { // 用于记录走过的路径 vector > way(x, vector(y, false)); dfs(board, way, "", i, j, result); } } // 以下操作排除重复出现的单词 sort(result.begin(), result.end()); result.erase(unique(result.begin(), result.end()), result.end()); return result; } private: Tri tree; void dfs(vector > &board, vector > way, string word, int x, int y, vector &result) { if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) // 超出边界 return; if (way[x][y]) return; word.push_back(board[x][y]); if (tree.search(word)) result.push_back(word); if (tree.startsWith(word)) { way[x][y] = true; dfs(board, way, word, x + 1, y, result); dfs(board, way, word, x - 1, y, result); dfs(board, way, word, x, y + 1, result); dfs(board, way, word, x, y - 1, result); way[x][y] = false; } word.pop_back(); } }; ~~~ 以下是网上一种使用字典树的算法，耗时48ms - 56ms： ~~~ class Trie { public: Trie *next[26]; bool exist; Trie() { fill_n(next, 26, nullptr); exist = false; } ~Trie() { for (int i = 0; i < 26; ++i) delete next[i]; } void insert(const string &t) { Trie *iter = this; for (int i = 0; i < t.size(); ++i) { if (iter->next[t[i] - 'a'] == nullptr) iter->next[t[i] - 'a'] = new Trie(); iter = iter->next[t[i] - 'a']; } iter->exist = true; } }; class Solution { public: int m, n; vector findWords(vector>& board, vector& words) { Trie *trie = new Trie(); for (auto &s : words) trie->insert(s); m = board.size(); n = board[0].size(); vector ret; string sofar; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { bc(board, ret, sofar, trie, i, j); } } return ret; } void bc(vector> &board, vector &ret, string &sofar, Trie *root, int x, int y) { if (x < 0 || y < 0 || x >= m || y >= n || board[x][y] == '\0' || root == nullptr) return ; if (root->next[board[x][y] - 'a'] == nullptr) return ; root = root->next[board[x][y] - 'a']; char t = '\0'; swap(t, board[x][y]); sofar.push_back(t); if (root->exist) { root->exist = false; ret.push_back(sofar); } bc(board, ret, sofar, root, x, y + 1); bc(board, ret, sofar, root, x + 1, y); bc(board, ret, sofar, root, x - 1, y); bc(board, ret, sofar, root, x, y - 1); swap(t, board[x][y]); sofar.pop_back(); } }; ~~~ **四. 小结** 学习并初次使用了字典树，并不是十分熟悉，写出的代码计算比较耗时。

**一. 题目描述** Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighbouring. The same letter cell may not be used more than once. For example, Given board = ~~~ [ ["ABCE"], ["SFCS"], ["ADEE"] ] ~~~ word = “ABCCED”, -> returns true,  word = “SEE”, -> returns true,  word = “ABCB”, -> returns false. **二. 题目分析** 题目的大意是，给定一个board字符矩阵和一个word字符串，可以从矩阵中任意一点开始经过上下左右的方式走，每个点只能走一次，若存在一条连续的路径，路径上的字符等于给定的word字符串的组合，则返回true，否则返回false。 解决的方法类似于走迷宫，使用递归回溯即可。由于走过的路径需要排除，因此构造一个辅助数组记录走过的位置，防止同一个位置被使用多次。 **三. 示例代码** ~~~ #include #include #include using namespace std; class Solution { public: bool exist(vector > &board, string word) { const int x = board.size(); const int y = board[0].size(); // 用于记录走过的路径 vector > way(x, vector(y, false)); for (int i = 0; i < x; ++i) { for (int j = 0; j < y; ++j) { if (dfs(board, way, word, 0, i, j)) return true; } } return false; } private: bool dfs(vector > &board, vector > way, string word, int index, int x, int y) { if (index == word.size()) // 单词完成匹配 return true; if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) // 超出边界 return false; if (word[index] != board[x][y]) // 遇到不匹配 return false; if (way[x][y]) // 该格已经走过，返回false return false; // 若该格未曾走过，可进行递归 way[x][y] = true; bool result = dfs(board, way, word, index + 1, x + 1, y) || // 往上扫描 dfs(board, way, word, index + 1, x - 1, y) || // 往下扫描 dfs(board, way, word, index + 1, x, y + 1) || // 往右扫描 dfs(board, way, word, index + 1, x, y - 1); // 往左扫描 way[x][y] = false; return result; } }; ~~~ 

**一. 题目描述** Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example,  Given [100, 4, 200, 1, 3, 2],  The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4. Your algorithm should run in O(n) complexity. **二. 题目分析** 这道题有两个技巧： 1. 哈希表插入和查找一个数的时间复杂度为`O(1)`；因此，可以使用哈希表来保存数组，以保障对于数组中的元素的查找是常量时间； 2. 一个数与它相邻的数都在同一个连续子序列中，因此，可以在某个数开始进行最长连续子序列判断的时候，可以将与它在同一连续子序列中的元素标记为不作为判断的开始，因为该元素所在的连续子序列处理过了，这样就可以大大较少比较次数，降低计算复杂度； 由于C++实现中的哈希表是一个无序字典类型，因此，可以将数组元素的值作为关键字，技巧2中每个元素的标记位作为每一个关键字的值。 对于数组中的每一个元素，先判断其所在连续子序列是否已经处理过了，如果已经处理过了，则直接处理下一个元素；如果还没处理过，则以其为中心，向左向右查找是否有相邻的数存在数组中，如果存在，就将长度加1，并将该元素的标记位置位，表示该元素所在的连续子序列已经处理过了，一直查找下去，直到相邻的数字不存在数组中为止，记录序列的长度，然后处理下一个元素。按照这个方法，在进行最长连续子序列查找的过程中，每个元素只被访问一次，因此计算复杂度为`O(n)`。 在创建哈希表的过程中，计算复杂度也为`O(n)`，因此，整个算法的时间复杂度为`O(n)+O(n)=O(n)`。 **三. 示例代码** ~~~ class Solution { public: int longestConsecutive(vector &num) { // get the size of the num int Size = num.size(); // build the hash_table unordered_map HashTable; for (int Index = 0; Index < Size; Index++) { int Tmp = num[Index]; HashTable[Tmp] = false; } // find the longest consecutive sequence int LongestNumber = 1; for (int Index = 0; Index < Size; Index++) { int Tmp = num[Index]; if (HashTable[Tmp]) { continue; } int TmpSequence = 1; while (HashTable.find(++Tmp) != HashTable.end()) { HashTable[Tmp] = true; TmpSequence++; } Tmp = num[Index]; while (HashTable.find(--Tmp) != HashTable.end()) { HashTable[Tmp] = true; TmpSequence++; } if (LongestNumber < TmpSequence) { LongestNumber = TmpSequence; } } return LongestNumber; } }; ~~~ **四. 小结** 该题可以在进行一次最大连续子序列查找的过程中将所有在该连续子序列中的元素进行标记，从而减少寻找最长连续子序列的这个过程，降低计算复杂度，使得这个寻找过程的计算复杂度为O(n)。

**一. 题目描述** Given preorder and inorder traversal of a tree, construct the binary tree.  Note: You may assume that duplicates do not exist in the tree. **二. 题目分析** 这道题考察了先序和中序遍历，先序是先访问根节点，然后访问左子树，最后访问右子树；中序遍历是先遍历左子树，然后访问根节点，最后访问右子树。 做法都是先根据先序遍历的概念，找到先序遍历的第一个值，即为根节点的值，然后根据根节点将中序遍历的结果分成左子树和右子树，然后就可以递归的实现了。 按照上述做法，时间复杂度为`O(n^2)`，空间复杂度为`O(1)` **三. 示例代码** ~~~ #include #include #include using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { private: TreeNode* buildTree(vector::iterator PreBegin, vector::iterator PreEnd, vector::iterator InBegin, vector::iterator InEnd) { if (PreBegin == PreEnd) { return NULL; } int HeadValue = *PreBegin; TreeNode *HeadNode = new TreeNode(HeadValue); vector::iterator LeftEnd = find(InBegin, InEnd, HeadValue); if (LeftEnd != InEnd) { HeadNode->left = buildTree(PreBegin + 1, PreBegin + (LeftEnd - InBegin) + 1, InBegin, LeftEnd); } HeadNode->right = buildTree(PreBegin + (LeftEnd - InBegin) + 1, PreEnd, LeftEnd + 1, InEnd); return HeadNode; } public: TreeNode* buildTree(vector& preorder, vector& inorder) { if (preorder.empty()) { return NULL; } return buildTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end()); } }; ~~~ **四. 小结** 该题考察了基础概念，并不涉及过多的算法问题。

**一. 题目描述** Given inorder and postorder traversal of a tree, construct the binary tree.  Note: You may assume that duplicates do not exist in the tree. **二. 题目分析** 这道题和Construct Binary Tree from Preorder and Inorder Traversal类似，都是考察基本概念的，后序遍历是先遍历左子树，然后遍历右子树，最后遍历根节点。 做法都是先根据后序遍历的概念，找到后序遍历最后的一个值，即为根节点的值，然后根据根节点将中序遍历的结果分成左子树和右子树，然后就可以递归的实现了。 上述做法的时间复杂度为`O(n^2)`，空间复杂度为`O(1)`。 **三. 示例代码** ~~~ #include #include #include using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { private: TreeNode* buildTree(vector::iterator PostBegin, vector::iterator PostEnd, vector::iterator InBegin, vector::iterator InEnd) { if (InBegin == InEnd) { return NULL; } if (PostBegin == PostEnd) { return NULL; } int HeadValue = *(--PostEnd); TreeNode *HeadNode = new TreeNode(HeadValue); vector::iterator LeftEnd = find(InBegin, InEnd, HeadValue); if (LeftEnd != InEnd) { HeadNode->left = buildTree(PostBegin, PostBegin + (LeftEnd - InBegin), InBegin, LeftEnd); } HeadNode->right = buildTree(PostBegin + (LeftEnd - InBegin), PostEnd, LeftEnd + 1, InEnd); return HeadNode; } public: TreeNode* buildTree(vector& inorder, vector& postorder) { if (inorder.empty()) { return NULL; } return buildTree(postorder.begin(), postorder.end(), inorder.begin(), inorder.end()); } }; ~~~ **四. 小结** 与前面一题一样，该题考察了基础概念，并不涉及过多的算法问题。

**一. 题目描述** Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Ensure that numbers within the set are sorted in ascending order. Example 1:  Input: k = 3, n = 7  Output: ~~~ [[1,2,4]] ~~~ Example 2:  Input: k = 3, n = 9  Output: ~~~ [[1,2,6], [1,3,5], [2,3,4]] ~~~ **二. 题目分析** 这道题题是组合之和系列的第三道题，跟之前两道Combination Sum 组合之和，前面两道题的联系比较紧密，变化不大，而这道跟它们最显著的不同就是这道题要求一个解中元素的个数为k。 实际上这道题是Combination Sum和Combination Sum II的综合体，两者杂糅到一起就是这道题的解法了。n是k个数字之和，如果n<0，则直接返回，如果n == 0，而且此时临时组合temp中的数字个数正好为k，说明此时是一个合适的组合解，将其存入结果result中。 **三. 示例代码** ~~~ #include #include using namespace std; class Solution { public: vector > combinationSum3(int k, int n) { vector > result; vector temp; combinationSum3DFS(k, n, 1, temp, result); return result; } private: void combinationSum3DFS(int k, int n, int level, vector &temp, vector > &result) { if (n < 0) return; if (n == 0 && temp.size() == k) result.push_back(temp); for (int i = level; i <= 9; ++i) { temp.push_back(i); combinationSum3DFS(k, n - i, i + 1, temp, result); temp.pop_back(); } } }; ~~~ **四. 小结** Combination Sum系列是经典的DFS题目，还需要深入研究。

**一. 题目描述** Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C once number of times. Note:  • All numbers (including target) will be positive integers.  • Elements in a combination (a1, a2, …, ak) must be in non-descending order. (ie, a1 > a2 > … > ak).  • The solution set must not contain duplicate combinations.  For example, given candidate set 10,1,2,7,6,1,5 and target 8, A solution set is: ~~~ [1, 7] [1, 2, 5] [2, 6] [1, 1, 6] ~~~ **二. 题目分析** 该题与之前的Combination Sum的解法类似，均可使用深度优先搜索来解。不同的是该题需要注意如何避免组合重复，因为不能重复，所以要跳过一样的数字。 例如：一个整数集合：[2 2 3]，当我们要使用第二个2时，我们要检查他的前面一个2是否使用了，当未被使用时第二个2就不能使用；。 **三. 示例代码** ~~~ #include #include #include using namespace std; class Solution { public: vector > combinationSum2(vector &candidates, int target) { vector temp; // 用于存放临时组合 sort(candidates.begin(), candidates.end()); combinationDFS(candidates, temp, 0, target); return result; } private: vector > result; void combinationDFS(vector &candidates, vector &temp, size_t index, int target) { if (target == 0) { result.push_back(temp); return; } else { int prev = -1; for (size_t i = index; i < candidates.size(); ++i) { // 由于candidates中元素可能有重复，以下操作的意义是判断上轮循 // 环是否选择了candidates[i]，是则跳过选择下一个candidates元素 // 直到下标到达比prev大的元素，选择该元素进行下一轮递归 if (prev == candidates[i]) continue; if (candidates[i] > target) return; prev = candidates[i]; temp.push_back(candidates[i]); combinationDFS(candidates, temp, i + 1, target - candidates[i]); temp.pop_back(); } } } }; ~~~  四. 小结 相关题目参照：

**一. 题目描述** Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. Note:  • All numbers (including target) will be positive integers.  • Elements in a combination (a1; a2; … ; ak) must be in non-descending order. (a1<=a2<=…<= ak).  • The solution set must not contain duplicate combinations. For example, given candidate set 2,3,6,7 and target 7, A solution set is: ~~~ [7] [2, 2, 3] ~~~ **二. 题目分析** 题目大意是：有一个正整数集合C和一个正整数目标T。现从C中选出一些数，使其累加和恰好等于T（C中的每个数都可以取若干次），求所有不同的取数方案，是一道典型的深度优先搜索题。 题目的一个细节是，正整数集合C可能存在**重复的数**，而这些数用于组合时，会产生重复的排列组合，如下图所示，而题目要求：The solution set must not contain duplicate combinations.  我的解决方法是对正整数集合C先进行从小到大排序，然后使用vector的erase方法去除集合C的重复元素，然后再进行DFS的相关运算。 **三. 示例代码** ~~~ #include #include #include using namespace std; class Solution { public: vector > combinationSum(vector &candidates, int target) { vector temp; // 用于存放临时组合 sort(candidates.begin(), candidates.end()); // 结果要求输出的组合不能重复，需要去除candidates中的重复元素 candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end()); combinationDFS(candidates, temp, 0, target); return result; } private: vector > result; void combinationDFS(vector &candidates, vector &temp, size_t index, int target) { if (target == 0) // 得到满足目标的一组解 { result.push_back(temp); return; } else { for (size_t i = index; i < candidates.size(); ++i) { if (candidates[i] > target) return; temp.push_back(candidates[i]); combinationDFS(candidates, temp, i, target - candidates[i]); temp.pop_back(); } } } }; ~~~  **四. 小结** 该题是一道经典的DFS题目，后续还有Combination Sum II和Combination Sum III，需要深入研究。

**一. 题目描述** Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example: Given ”25525511135”, return [”255.255.11.135”, ”255.255.111.35”]. (Order does not matter) **二. 题目分析** 题目的大意是，输入一个仅含整数的字符串，找出所有合法的ip地址，并输出所有的可能性。 很显然这道题需要遍历到最后一个字符才能判断一个解是否合法，因此需使用dfs。本题的难点在于存在各种各样的限制条件，如每段中不能出现以0开头的数字。需反复尝试方可AC，由于时间有限，给出一个参考的代码链接，后续需深入研究。 **三. 示例代码** ~~~ class Solution { public: vector restore(string s, int n, bool &flag) { vector res; if(s.length() < n) {flag = false; return res;} if(n==1) { if(s.length()>3){flag=false;return res;}//maybe larger than int int ip = stoi(s); if(ip==0 && s.length() >1) flag = false; else if(ip>0 && s[0] == '0') flag = false; else if((ip >= 0) && (ip < 256)) { res.push_back(s); flag = true; }else flag = false; return res; } int loop = s.length() - n +1;//garuntee every ip address is no less than one bit loop = min(loop,3); for(int i = 1; i <= loop; i++) { string ipstr = s.substr(0,i); int ip = stoi(ipstr); if(ip==0 && ipstr.length() >1)break; if(ip>0 && ipstr[0] == '0')break; if((ip>=0) && (ip < 256)) { string suffix = s.substr(i); bool f = false; vector tmp = restore(suffix,n-1,f); if(f) { flag = true; for(int k = 0; k < tmp.size(); k++) res.push_back(ipstr + '.' + tmp[k]); } } } return res; } vector restoreIpAddresses(string s) { // Start typing your C/C++ solution below // DO NOT write int main() function vector res; bool flag = false; res = restore(s,4,flag); return res; } } ~~~ **四. 小结** 递归到最后一个数并进行判断，最后输出结果。