月份：2016年2月

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数组求取完毕。

初步代码如下：

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;
	}
}

优化后的代码如下：

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;
}

思路：

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!

class Solution {
public:
	int trap(vector<int>& height) {
		int left = 0; int right = height.size() - 1;
		int maxL = 0, maxR = 0;
		int result = 0;
		while (left<right)
		{
			if (height[left]<height[right])             {
				if (height[left]>maxL)
					maxL = height[left];//遇到新的高度，则无法填充雨水
				else//height[left]<=maxL                     
					result+=maxL-height[left];                 
				left++;             
			}            
			else             
			{                 
				if(height[right]>maxR)
					maxR = height[right];//遇到新的高度，无法填充雨水
			else
				result += maxR - height[right];
				right--;
			}
		}

		return result;
	}
};

题目描述

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

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

AC代码如下：

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

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代码：

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;

	}
};

题目描述

AC代码如下：

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;
    }
};

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

	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;
	}

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

题目描述

"aeiou"

返回：True

"BarackObama"

返回：False

AC代码：

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;
    }
};

#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;
}

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

#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;
}