Month: February 2016

1.在KMP字符串匹配算法中，我们需要先求出next数组，由于过程比较抽象，现在一步一步来讲解。

2.next数组的求法：首先next[0]=0，next[1]=1，这个是基础。假设字符串为str，当前位为i，则判断str[i-1]是否等于i-1上对应的next值对应的内容，即str[next[i-1]-1]，为什么还需要把next的值减1？因为next数组的计算，是把字符串按照1，2，3，4。。。。从1开始的规则来计算的。

如果str[i-1]==str[next[i-1]-1]，那么next[i]=next[i-1]+1；

如果不等，我们令j=next[i-1]，判断str[i-1]是否等于str[next[j-1]-1]，如果不等于，我们令j=next[j-1]，继续判断str[i-1]是否等于str[next[j-1]-1]，一直循环判断，直到相等，则next[i]=next[j-1]+1。

我们来看看数组

KMP序号:   1  2  3  4  5  6  7  8  9  10  11  12
string：      a  b  a  b  a  a  a  b  a    b     a    a
next数组：0  1  1  2  3  4  2  2  3    4     5    6
数组idx：   0  1  2  3  4  5  6  7  8    9    10  11

我们从第三位开始分析，

注意下面涉及到的str[i]，是按照正常的string获取位置，不是按照KMP序号，即str为str[0,1,2,3…..10,11]，next为next[0,1,2,3…..10,11]。

第三位i=2：前一位str[1]=’b’，next[1]=1，str[next[1]-1]=’a’，’b’!=’a’，所以再往前一步已经无字符，所以next[2]=1;

第四位i=3：前一位str[2]=’a’，next[2]=1，str[next[2]-1]=’a’，相等，所以next[3]=next[2]+1=2;

第五位i=4：前一位str[3]=’b’，next[3]=2，str[next[3]-1]=str[1]=’b’，相等，所以next[4]=next[3]+1=3;

第六位i=5：前一位str[4]=’a’，next[4]=3，str[next[4]-1]=str[2]=’a’，相等，所以

next[5]=next[4]+1=4;

第七位i=6：前一位str[5]=’a’，next[5]=4，str[next[5]-1]=str[3]=’b’，与str[5]不相等，所以继续看前一个next，即next[next[5]-1]=next[3]，str[next[3]-1]=str[1]=’b’，依然不相等，继续往前看next[next[3]-1]=next[1]，str[next[1]-1]=str[0]=’a’，相等，则next[6]=next[1]+1=2;

第八位i=7：前一位str[6]=’a’，next[6]=2，str[next[6]-1]=str[1]=’b’，与str[6]不相等，所以继续看前一个next，即next[next[6]-1]=next[1]，str[next[1]-1]=’a’，与str[6]相等，所以next[7]=next[1]+1=2;

第九位i=8：前一位str[7]=’b’，next[7]=2，str[next[7]-1]=str[1]=’b’，与str[7]相等，所以next[8]=next[7]+1=3;

第十位i=9：前一位str[8]=’a’，next[8]=3，str[next[8]-1]=str[2]=’a’，与str[8]相等，所以next[9]=next[8]+1=4;

第十一位i=10：前一位str[9]=’b’，next[9]=4，str[next[9]-1]=str[3]=’b’，与str[9]相等，所以next[10]=next[9]+1=5;

第十二位i=11：前一位str[10]=’a’，next[10]=5，str[next[10]-1]=str[4]=’a’，与str[10]相等，所以next[11]=next[10]+1=6;

至此，next数组求取完毕。

初步代码如下：

[c language=”++”]
next[0] = 0;
next[1] = 1;
for (int i = 2; i < str.size(); ++i)
{
if (str[i – 1] == str[next[i – 1] – 1])
next[i] = next[i – 1] + 1;
else
{
int j = next[i – 1];
while (j>0 && str[i – 1] != str[j – 1])
{
j = next[j – 1];
}
next[i] = next[j] + 1;
}
}
[/c]

优化后的代码如下：
[c language=”++”]
next[0] = 0;
next[1] = 1;
for (int i = 2; i < str.size(); ++i)
{
int j = i;
while (j>1 && str[i – 1] != str[next[j – 1] – 1])
j = next[j – 1];
next[i] = next[j – 1] + 1;
}
[/c]
 

思路：

1.使用两个指针，从两端往内遍历。

2.如果左边的高度小于右边的高度，那么左边的高度则可以填充雨水，但是填充为多少呢？这个时候，需要看左边的左边的最大高度maxL（简称为左边的最大高度），我们可以把雨水填充为左边的最大高度maxL。为什么能够填充为左边的最大高度maxL？

因为在遍历过程中，我们需要左边的高度小于右边的高度才会进行更新最大高度的操作，在这个过程中，我们可以保证存在一个height[right]在maxL的右边，且height[right]>maxL，因此，我们可以填充为左边的最大高度maxL。

3.右边同理。

4.时间复杂度为O(n)，空间复杂度为O(1)。

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

题目描述

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

1.这道题目比较有意思，不能使用循环，判断语句。
2.从方法上进行判断，那么有循环和递归，而题目要求不能使用循环，那么可以从递归方面入手。
3.递归需要一个终止条件，而这个终止条件使用了if判断语句，那么我们有没有别的方式不适用if语句判断呢？
4.当然是有的，我们可以使用利用&&符号，如果左边为假，那么右边就不再进行判断。

AC代码如下：

[c language=”++”]
class Solution {
public:
int Sum_Solution(int n) {
int sum = n;
//当sum为0时，不会执行后半个处理
sum && (sum += Sum_Solution(n – 1));
return sum;
}
};
[/c]

1.分析题目后，我们发现需要找出一条路径，而这条路径的限制是每次只改变一个字母。因此，这也可以理解为求单元最短路径。

2.我们可以考虑采用DFS或者BFS进行搜索。先看看DFS，DFS每次找出一条到达目标点的路径，但是不确定这条路径是否为最短，所以需要遍历完所有的节点才确定到最终解。

3.而BFS相当于一层一层地往外搜索，所以一旦遇到目标点，那么其记录的路径长度就是最短长度，经过上面的分析，我们可以初步使用BFS进行求解。

4.最初的思路是构建好各个单词的邻居，要构建邻居关系，需要对每个单词遍历一次单词表，时间复杂度为O(n*n)，而BFS的复杂度为O(n)，实际我刚开始也是这么做的，结果超时了。单词量能上到2000以上。

5.为了解决构建邻居超时的问题，我换了一种方法，就是事先不构建邻居，而是在BFS中，通过原来的单词进行字母变换，构建出一个新单词，再去判断这个单词是否在wordList中，假设单词长度为k，每个字母替换26次，BFS的复杂度为O(n)，则总的复杂度为（26*k*n）。这样编写程序能够顺利通过测试，耗时460ms。

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["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.

AC代码：
[c language=”++”]
class Solution {
public:

int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
map<string, bool> visited;
int wordSize = beginWord.size();

int length = 1;
queue<string> q;
q.push(beginWord);
visited[beginWord] = true;
int count1 = 1;
int count2 = 0;

while (!q.empty())
{
length++;
for (int i = 0; i < count1; ++i)
{
string head = q.front();
q.pop();
string tmp = head;

//替换每个单词的每个字母，看看是否能够在wordList中找到
for (int j = 0; j < wordSize; ++j)
{
tmp = head;
for (int k = 0; k < 26; k++)
{
tmp[j] = ‘a’ + k;
if (wordList.find(tmp) != wordList.end()&&!visited[tmp])
{//找到邻居
visited[tmp] = true;
q.push(tmp);
count2++;
}
if (tmp == endWord)
return length;
}
}
}
count1 = count2;
count2 = 0;
}
return 0;

}
};
[/c]
 

题目描述

AC代码如下：

[c language=”++”]
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> result(0);
if(A.size()==0)
return result;

result=vector<int>(A.size(),1);

int tmp=1;

//前向乘积数组
for(int i=1;i<A.size();++i)
{
tmp*=A[i-1];
result[i]*=tmp;
}

tmp=1;
//后向乘积数组
for(int i=A.size()-2;i>=0;–i)
{
tmp*=A[i+1];
result[i]*=tmp;
}
return result;
}
};
[/c]

最近再次复习编写堆排，于是重新梳理了一下。之前也写过堆排的代码：堆排Heap Sort

[c language=”++”]
vector<int> heap;
int size;

void push(int x)
{
int i = size++;
int p = (i – 1) / 2;
while (x>heap[p])
{
heap[i] = heap[p];
if (i == 0) break;
i = p;
p = (i – 1) / 2;
}
heap[i] = x;
}

void pop()
{
int bottom = heap[size – 1];
int i = 0;
int a = 2 * i + 1, b = 2 * i + 2;
size–;
while (a<size)
{
if (b<size&&heap[a]<heap[b]) a = b;
if (bottom<heap[a])
heap[i] = heap[a];
else break;
i = a;
a = 2 * i + 1;
b = 2 * i + 2;
}
heap[i] = bottom;
}
[/c]

1.题目要求不能使用额外的结构，这道题目和判断一个数组里面是否各数唯一一样。
2.我们先把数组进行排序，时间复杂度为O(nlogn)，排序后，相同的字符必然相邻，于是遍历一遍，检查相邻是否相同即可。
3.总的时间复杂度为O(nlogn)，空间复杂度为O(1)。

题目描述

"aeiou"

返回：True

"BarackObama"

返回：False

AC代码：
[c language=”++”]
class Different {
public:
bool checkDifferent(string iniString) {
// write code here
sort(iniString.begin(),iniString.end());
for(int i=0;i<iniString.size()-1;++i)
{
if(iniString[i]==iniString[i+1])
return false;
}
return true;
}
};
[/c]

[c language=”++”]
#include <stdio.h>
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
using namespace std;

int partition(vector<int>&arr, int l, int r)
{
int pivot = arr[r];
int k = l;
for (int i = l; i < r; ++i)
{
if (arr[i] < pivot)
swap(arr[i], arr[k++]);
}
swap(arr[k], arr[r]);
return k;
}
void quickSort(vector<int>&arr, int l, int r)
{
if (l >= r) return;
int k = partition(arr, l, r);
quickSort(arr, l, k – 1);
quickSort(arr, k + 1, r);
}
int main()
{
vector<int> input = { 4, 5, 1, 6, 2, 7, 3, 8 };

quickSort(input, 0,input.size() – 1);

return 0;
}
[/c]

需要借助一个数组，时间复杂度为O(nlogn)，空间复杂度为O(n)

[c language=”++”]
#include <stdio.h>
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
using namespace std;

void Merge(vector<int>&arr, vector<int>&tmp, int l, int k, int r)
{
int i = l;
int j = k + 1;
int p = l;

while (i <= k&&j <= r)
{
if (arr[i] < arr[j])
tmp[p++] = arr[i++];
else
tmp[p++] = arr[j++];
}

while (i <= k)
tmp[p++] = arr[i++];

while (j <= r)
tmp[p++] = arr[j++];

for (i = l; i <= r; ++i)
arr[i] = tmp[i];
}

void MSort(vector<int>&arr, vector<int>&tmp, int l, int r)
{
if (l >= r) return;
int k = (l + r) / 2;
MSort(arr, tmp, l, k);
MSort(arr, tmp, k + 1, r);
Merge(arr, tmp, l, k, r);
}

void MergeSort(vector<int>&arr)
{
vector<int> tmp(arr.size());
MSort(arr, tmp, 0, arr.size() – 1);
}
int main()
{
vector<int> arr = { 12,1 , 123, 1, 4, 2, 54, 3, 52, 3, 12, 4, 123,55 , 135 };
MergeSort(arr);

return 0;
}

[/c]