你正在使用的浏览器版本过低，将不能正常浏览和使用知乎。leetcode（46）
作者：努力的摩羯
链接：/question//answer/
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
【题意】给定一个数，求其最少能表示成几个完全平方数的和表示。
【思路】用动归解决。
【别人家的小孩】
解答里面说，有个定理说了，任何自然数都能表示成4哥完全平方数的和。
【题意】正则表达式匹配，'?'匹配任意一个字符，'*'匹配任意字符
【思路】用动归解决。
【别人家的小孩】
&img src=&/d6eb2f776c5_b.png& data-rawwidth=&723& data-rawheight=&568& class=&origin_image zh-lightbox-thumb& width=&723& data-original=&/d6eb2f776c5_r.png&&（我忘记答案从哪里看来的了）（我忘记答案从哪里看来的了）
我理解的他这种解法思路是，『把p字符串按照*分开，如果每一部分都在s中能找到，则匹配』，和很多解答中提到的KMP解法的思想是一样的。
----------------------------------------------竟然破了10-------------------------------------------------
【题意】求数组中乘积最大的子数组
【思路】想不清楚
【别人家的小孩】
&img src=&/b176d174b8cc23b2f0e073bd36584f29_b.png& data-rawwidth=&451& data-rawheight=&324& class=&origin_image zh-lightbox-thumb& width=&451& data-original=&/b176d174b8cc23b2f0e073bd36584f29_r.png&&记录当前乘积的最大和最小，遍历的时候每个最大来自于当前数、当前数乘以最大值、当前数乘以最小值中产生，最小同样。记录当前乘积的最大和最小，遍历的时候每个最大来自于当前数、当前数乘以最大值、当前数乘以最小值中产生，最小同样。
【题意】在行列递增矩阵中查找target，返回是否存在。
【思路】二分查找
【别人家的小孩】
&img src=&/62bad4d8bc90c05b39079_b.png& data-rawwidth=&619& data-rawheight=&272& class=&origin_image zh-lightbox-thumb& width=&619& data-original=&/62bad4d8bc90c05b39079_r.png&&基本思路就是从矩阵右上角开始查找，当前值比target大往左走，比target小的话往下走。基本思路就是从矩阵右上角开始查找，当前值比target大往左走，比target小的话往下走。
这个题目其实很经典，但我第一次遇到是在某次电面中，打死没有想到如此巧妙的方法。
【题意】给定一个字符串，是否是合法的数字表示
【思路】#￥%……&*（
【别人家的小孩】自动机
&img src=&/2f1e581cadc_b.png& data-rawwidth=&604& data-rawheight=&577& class=&origin_image zh-lightbox-thumb& width=&604& data-original=&/2f1e581cadc_r.png&&状态1356是合法的结束状态。（此图是我自己画的）状态1356是合法的结束状态。（此图是我自己画的）
【题意】给定一个字符串，问在字符串头部增加最短的字符串使其变成回文
【思路】！#￥%……&*（）
【别人家的小孩】Manacher和KMP
其实Manacher算法是求最长回文子串中非常漂亮的算法了。
本题目可以转换为求给定字符串从首字母开始的最长回文子串（然后将余下的reverse，insert到头部就可以），而求从首字母开始的最长回文子串，可以用Manacher算法，也可以将str反转以后频道str尾部，使用KMP的求next数组，这样next数组最后一个值就是从首字母出发的最长回文子串长度。
----------------------------------------------------------又补充了三个题----------------------------------------------------
【题意】实现LRU Cache
【思路】不会
【别人家的小孩】unordered_map和单链表实现
第一次看解答记住的是用c++ stl的list的实现方法，可以省去很多操作细节，某次面试面试官说你要自己写链表，我思考了挺久感觉单链表实现不了就写的双链表。后来室友找到一个单链表实现，看完以后真的是太佩服了。
思路是，最近使用的value放在队尾，map中存放的是key对应value的pre结点指针。
8. 253 Meeting Rooms II
【题意】输入[[0, 30],[5, 10],[15, 20]]表示每个会议的开始结束时间，求最少需要多少会议室能够安排所有的会议。
【思路】按照开始时间排序，然后用最小堆保存当前所有会议室的结束时间。
【别人家的小孩】把开始、结束时间当作两个时间点，结束时间乘以-1，然后按照时间点的绝对值排序，这样就得到了一个时间轴上2n个时间点，正的表示开始时间，负的表示结束时间。设变量count，遍历2n个时间点，遇正+1，遇负-1，count的最大值就是最少需要的会议室数量。
&img src=&/241b0ea2126bcc5081d9fdc098f9f92d_b.png& data-rawwidth=&483& data-rawheight=&526& class=&origin_image zh-lightbox-thumb& width=&483& data-original=&/241b0ea2126bcc5081d9fdc098f9f92d_r.png&&9.
287 9. 287
【题意】n+1个数，取值范围是[1,n]，所以至少有1个数重复出现，假设只有一个数重复出现了，找到她。要求不能修改输入，常数空间，O(n)时间复杂度。
【思路】看完要求之后直接怀疑题目写错了吧。
【别人家的小孩】
我的理解，设数组大小为n，取值范围是1- n-1(变为 0- n-2)
构建一个链表A, a-&next= nums[a]，因为有两个num相等，那么此链表肯定有环，环的第一个数就是我们找的答案。（这个解法真是太厉害了）
作者：Zack
链接：/question//answer/
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1）求二叉树的高度（Maximum Depth of Binary Tree）
// LeetCode, Maximum Depth of Binary Tree
// 时间复杂度O(n)，空间复杂度O(logn)
class Solution {
int maxDepth(TreeNode *root) {
if (root == nullptr) return 0;
return max(maxDepth(root-&left), maxDepth(root-&right)) + 1;
2）判断二叉树是否对称（Symmetric Tree）
// LeetCode, Symmetric Tree
// 递归版，时间复杂度O(n)，空间复杂度O(logn)
class Solution {
bool isSymmetric(TreeNode *root) {
return root ? isSymmetric(root-&left, root-&right) :
bool isSymmetric(TreeNode *left, TreeNode *right) {
if (!left && !right) // 终止条件
if (!left || !right) // 终止条件
return left-&val == right-&val // 三方合并
&& isSymmetric(left-&left, right-&right)
&& isSymmetric(left-&right, right-&left);
3）二叉树-& 链表（Flatten Binary Tree to Linked List）
// LeetCode, Flatten Binary Tree to Linked List
// 递归版2
// @author 王顺达(/u/)
// 时间复杂度O(n)，空间复杂度O(logn)
class Solution {
void flatten(TreeNode *root) {
flatten(root, NULL);
// 把root 所代表树变成链表后，tail 跟在该链表后面
TreeNode *flatten(TreeNode *root, TreeNode *tail) {
if (NULL == root)
root-&right = flatten(root-&left, flatten(root-&right, tail));
root-&left = NULL;
二. 字符串
1）最长无重复字符子串（Longest Substring Without Repeating Characters）
class Solution {
int lengthOfLongestSubstring(string s) {
int ans = 0;
int dic[256];
memset(dic,-1,sizeof(dic));
int len = s.size();
int idx = -1;
for (int i=0;i&i++)
char c = s[i];
if (dic[c]&idx)
idx = dic[c];
ans = max(ans,i-idx);
1）数组中所有数字出现两次，只有一个出现一次，求出它（Single Number）
// LeetCode, Single Number
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
int singleNumber(int A[], int n) {
int x = 0;
for (size_t i = 0; i & ++i)
x ^= A[i];
2）顺时针旋转二维数组90度（Rotate Image）
// LeetCode, Rotate Image
// 思路1，时间复杂度O(n^2)，空间复杂度O(1)
class Solution {
void rotate(vector&vector&int&&& matrix) {
const int n = matrix.size();
for (int i = 0; i & ++i) // 沿着副对角线反转
for (int j = 0; j & n - ++j)
swap(matrix[i][j], matrix[n - 1 - j][n - 1 - i]);
for (int i = 0; i & n / 2; ++i) // 沿着水平中线反转
for (int j = 0; j & ++j)
swap(matrix[i][j], matrix[n - 1 - i][j]);
3）排序数组去重（Remove Duplicates from Sorted Array）
// LeetCode, Remove Duplicates from Sorted Array
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
int removeDuplicates(int A[], int n) {
if (n == 0) return 0;
int index = 0;
for (int i = 1; i & i++) {
if (A[index] != A[i])
A[++index] = A[i];
return index + 1;
4）两个排序数组，求中位数（Median of Two Sorted Arrays）
// LeetCode, Median of Two Sorted Arrays
// 时间复杂度O(log(m+n))，空间复杂度O(log(m+n))
class Solution {
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total = m +
if (total & 0x1)
return find_kth(A, m, B, n, total / 2 + 1);
return (find_kth(A, m, B, n, total / 2)
+ find_kth(A, m, B, n, total / 2 + 1)) / 2.0;
static int find_kth(int A[], int m, int B[], int n, int k) {
//always assume that m is equal or smaller than n
if (m & n) return find_kth(B, n, A, m, k);
if (m == 0) return B[k - 1];
if (k == 1) return min(A[0], B[0]);
//divide k into two parts
int ia = min(k / 2, m), ib = k -
if (A[ia - 1] & B[ib - 1])
return find_kth(A + ia, m - ia, B, n, k - ia);
else if (A[ia - 1] & B[ib - 1])
return find_kth(A, m, B + ib, n - ib, k - ib);
return A[ia - 1];
KMP 解 Shortest Palindrome，当时看到这个解答也是被帅哭了。。
string shortestPalindrome(string s) {
string re=s;
reverse(re.begin(), re.end());
string t = s + &#& + re;
vector&int& next(t.size(), 0);
for (int i = 1; i & t.size(); ++i) {
int j = next[i - 1];
while (j & 0 && t[i] != t[j])
j = next[j - 1];
j += (t[i] == t[j]);
next[i] = j;
return re.substr(0, s.size() - next[t.size() - 1]) + s;
作者：sliver native
链接：/question//answer/
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
等等，不一而足，有空就要多上leetcode上看看。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3578次
积分：1700
积分：1700
排名：千里之外
原创：171篇