Monthly Archives: May 2017

LeetCode House Robber III

LeetCode House Robber III
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:

     3
    / \
   2   3
    \   \
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:

     3
    / \
   4   5
  / \   \
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.
Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.


这次要偷的房子分布在一棵二叉树上。。。
规则是有边相连的两个节点不能同时被偷,问最多能偷到多少钱。
我开始想的和LeetCode House Robber类似,一个节点要么偷,要么不偷。不偷得到的钱是上一个节点偷或不偷的最大值;偷得到的钱是上一个节点不偷加上该节点的钱数。使用递归的方法求解。
代码如下:

class Solution {
private:
	void dfs(TreeNode* root, int& norobsum, int& robsum) {
		int nrs = max(norobsum, robsum);
		int rs = norobsum + root->val;
		norobsum = nrs;
		robsum = rs;
		if (root->left)dfs(root->left, norobsum, robsum);
		if (root->right)dfs(root->right, norobsum, robsum);
	}
public:
	int rob(TreeNode* root) {
		if (!root)return 0;
		int norobsum = 0, robsum = 0;
		dfs(root, norobsum, robsum);
		return max(norobsum, robsum);
	}
};

本代码提交WA,错误样例如下:

     1
    / \
   2   3

令m[i]=(u,v)表示截至目前偷i节点得到u钱,不偷得到v钱。则m[1]=(1,0),递归进入左孩子,m[2]=(2+0,max(1,0))=(2,1),递归进入右孩子,m[3]=(3+1,max(2,1))=(4,2)。导致算出来的结果是4。这是因为3号节点偷的时候,其实不是3+1,1号节点的状态不能简单等价于2号节点的状态。
正确的做法应该是这样的,对于节点i,先算到左右节点偷或者不偷的钱数,即m[l]=(lrs,lnrs)和m[r]=(rrs,rnrs)。那么i偷的话,则左右节点都不能偷了=lnrs+rnrs+i.val;如果i不偷的话,则左右节点都可以偷或者不偷=max(lnrs,lrs)+max(rnrs,rrs),所以m[i]=(lnrs+rnrs+i.val, max(lnrs,lrs)+max(rnrs,rrs))。
代码如下:

class Solution {
private:
	void dfs(TreeNode* root, int& norobsum, int& robsum) {
		int lnrs = 0, lrs = 0, rnrs = 0, rrs = 0;
		if (root->left)dfs(root->left, lnrs, lrs);
		if (root->right)dfs(root->right, rnrs, rrs);
		norobsum = max(lnrs, lrs) + max(rnrs, rrs);
		robsum = lnrs + rnrs + root->val;
	}
public:
	int rob(TreeNode* root) {
		if (!root)return 0;
		int norobsum = 0, robsum = 0;
		dfs(root, norobsum, robsum);
		return max(norobsum, robsum);
	}
};

本代码提交AC,用时16MS。

LeetCode House Robber II

LeetCode House Robber II
Note: This is an extension of House Robber.
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.


本题是LeetCode House Robber的扩展版,当首尾相连时,怎样偷到最多的钱。
因为首尾相连,所以如果偷了第一家,就不能偷最后一家;或者如果偷了最后一家,就不能偷第一家。所以我们可以把数组分成两个部分,一部分是去掉最后一家,求一个最大值;另一部分是去掉第一家,求一个最大值。最优结果就是这两个最大值的最大值。
代码如下:

class Solution {
public:
	int rob(vector<int>& nums) {
		if (nums.size() == 0)return 0;
		if (nums.size() == 1)return nums[0];
		int ans1 = 0, ans2 = 0;
		vector<vector<int>> dp1(nums.size() + 1, vector<int>(2, 0)), dp2(nums.size() + 1, vector<int>(2, 0));
		for (int i = 1; i < nums.size(); ++i) { // 不偷最后一家
			dp1[i][0] = max(dp1[i - 1][0], dp1[i - 1][1]);
			dp1[i][1] = dp1[i - 1][0] + nums[i - 1];
			ans1 = max(ans1, max(dp1[i][0], dp1[i][1]));
		}
		for (int i = 2; i <= nums.size(); ++i) { // 不偷第一家
			dp2[i][0] = max(dp2[i - 1][0], dp2[i - 1][1]);
			dp2[i][1] = dp2[i - 1][0] + nums[i - 1];
			ans2 = max(ans2, max(dp2[i][0], dp2[i][1]));
		}
		return max(ans1, ans2);
	}
};

本代码提交AC,用时3MS。
更漂亮的代码是:

class Solution {
private:
	int subrob(const vector<int>& nums, int left, int right) {
		int robsum = 0, norobsum = 0;
		for (int i = left; i <= right; ++i) {
			int nrs = max(robsum, norobsum);
			int rs = norobsum + nums[i];
			norobsum = nrs;
			robsum = rs;
		}
		return max(robsum, norobsum);
	}
public:
	int rob(vector<int>& nums) {
		int n = nums.size();
		if (n == 0)return 0;
		if (n == 1)return nums[0];
		return max(subrob(nums, 0, n - 2), subrob(nums, 1, n - 1));
	}
};

本代码提交AC,用时3MS。

LeetCode Different Ways to Add Parentheses

LeetCode Different Ways to Add Parentheses
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]
Example 2
Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.


给定一个包含+-*的运算字符串,求所有加括号的方案计算到的值。
采用分治法的思路,尝试在每个操作符分成两个部分,这就相当于分别把操作符左右两边括起来单独计算。然后left和right分开进行递归,最后merge。递归的终止条件是当字符串中不包含操作符时,直接返回这个字符串对应的数值。
分治法很经典的例子。
代码如下:

class Solution {
private:
	int operate(int a, int b, char c) {
		switch (c) {
			case '+':return a + b;
			case '-':return a - b;
			case '*':return a*b;
		}
	}
public:
	vector<int> diffWaysToCompute(string input) {
		int n = input.size();
		vector<int> ans;
		bool found = false;
		for (int i = 0; i < n; ++i) {
			if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
				found = true;
				vector<int> lefts = diffWaysToCompute(input.substr(0, i));
				vector<int> rights = diffWaysToCompute(input.substr(i + 1));
				for (int j = 0; j < lefts.size(); ++j) {
					for (int k = 0; k < rights.size(); ++k) {
						ans.push_back(operate(lefts[j], rights[k], input[i]));
					}
				}
			}
		}
		if (!found)return{ atoi(input.c_str()) };
		return ans;
	}
};

本代码提交AC,用时3MS。

LeetCode Fraction Addition and Subtraction

LeetCode Fraction Addition and Subtraction
Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator 1. So in this case, 2 should be converted to 2/1.
Example 1:

Input:"-1/2+1/2"
Output: "0/1"

Example 2:

Input:"-1/2+1/2+1/3"
Output: "1/3"

Example 3:

Input:"1/3-1/2"
Output: "-1/6"

Example 4:

Input:"5/3+1/3"
Output: "2/1"

Note:

  1. The input string only contains '0' to '9', '/', '+' and '-'. So does the output.
  2. Each fraction (input and output) has format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.
  3. The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
  4. The number of given fractions will be in the range [1,10].
  5. The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.

给定一个只包含+-/的运算字符串,要求求出这个字符串的值,并且用最简分数的形式表示。
参考这篇博客,没什么技巧,就是用代码模拟手算的过程。首先求出所有分母的最小公倍数,然后通分,使得所有数的分母都相同,最后把所有通分过的分子加起来,得到结果。最最后一步就是把分子和分母约分。
这些步骤中涉及到求最小公倍数和最大公约数。最大公约数的求法gcd是必须掌握的,另外再根据gcd(x,y)*lcm(x,y)=x*y的性质,可以求到最小公倍数lcm(x,y)
代码如下:

class Solution {
private:
	int gcd(int x, int y) {
		while (y) {
			int tmp = x % y;
			x = y;
			y = tmp;
		}
		return x;
	}
	int lcm(int x, int y) {
		return x * y / gcd(x, y);
	}
public:
	string fractionAddition(string expression) {
		vector<int> num, denom; // 分子,分母
		expression += "+"; // 哨兵
		int i = 0, j = 0;
		bool isnum = true;
		for (j = 0; j < expression.size(); ++j) {
			if (j != 0 && (expression[j] == '/' || expression[j] == '-' || expression[j] == '+')) {
				int one = atoi(expression.substr(i, j - i).c_str());
				if (isnum)num.push_back(one);
				else denom.push_back(one);
				isnum = !isnum;
				if (expression[j] == '/') i = j + 1;
				else i = j;
			}
		}
		int fm = 1;
		for (int i = 0; i < denom.size(); ++i)fm = lcm(fm, denom[i]);
		int fz = 0;
		for (int i = 0; i < num.size(); ++i)fz += num[i] * (fm / denom[i]);
		int g = 0;
		if (fz < 0)
			g = gcd(-fz, fm);
		else
			g = gcd(fz, fm);
		return to_string(fz / g) + "/" + to_string(fm / g);
	}
};

本代码提交AC,用时3MS。

LeetCode Delete Operation for Two Strings

LeetCode Delete Operation for Two Strings
Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.
Example 1:

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Note:

  1. The length of given words won't exceed 500.
  2. Characters in given words can only be lower-case letters.

给定两个字符串,求最少的删除次数,使得两个字符串相等。
这其实就是求两个字符串的最长公共子序列,因为最少的删除次数之后,两个字符串都变成了lcs,则每个字符串删除的次数就是原始长度减去lcs的长度。
代码如下:

class Solution {
private:
	int lcs(const string& s1, const string& s2) {
		int n1 = s1.size(), n2 = s2.size();
		vector<int> dp1(n2 + 1, 0), dp2(n2 + 1, 0);
		int ans = 0;
		for (int i = 1; i <= n1; ++i) {
			for (int j = 1; j <= n2; ++j) {
				if (s1[i - 1] == s2[j - 1])dp2[j] = dp1[j - 1] + 1;
				else dp2[j] = max(dp1[j], dp2[j - 1]);
				ans = max(ans, dp2[j]);
			}
			dp1.swap(dp2);
		}
		return ans;
	}
public:
	int minDistance(string word1, string word2) {
		int l = lcs(word1, word2);
		return word1.size() - l + word2.size() - l;
	}
};

本代码提交AC,用时52MS。

LeetCode Combination Sum III

LeetCode Combination Sum III

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.
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]]

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.


从1~9中取k个数,使得这k个数的和等于n,求出所有取数方案。
简单的递归题,为了不重复,每次从上次取数的下一个取,代码如下:

class Solution {
private:
	void dfs(vector<vector<int>>& ans, vector<int>& cand, int step, const int& k,int sum) {
		if (cand.size() == k&&sum == 0) {
			ans.push_back(cand);
			return;
		}
		for (int i = step; i <= 9; ++i) {
			if (i > sum)break;
			cand.push_back(i);
			dfs(ans, cand, i + 1, k, sum - i);
			cand.pop_back();
		}
	}
public:
	vector<vector<int>> combinationSum3(int k, int n) {
		vector<vector<int>> ans;
		vector<int> cand;
		dfs(ans, cand, 1, k, n);
		return ans;
	}
};

本代码提交AC,用时3MS。

LeetCode Kth Smallest Element in a Sorted Matrix

LeetCode Kth Smallest Element in a Sorted Matrix
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n2.


给定一个矩阵,该矩阵每行和每列都是有序的,要找出第k小的数。
如果只利用每行或者每列是有序的,则可以使用堆解决。我们以行为例,那么每行都是有序的,则相当于把所有行进行n路归并,然后找到第k小的数。所以我们构建一个最小堆,首先把所有行的首元素放到堆中,然后n路归并k次,每次弹出堆顶元素(即当前最小值),然后把原堆顶元素所在行的下一个元素放入堆中。k次归并结束之后,堆顶元素即为第k小的元素。
代码如下:

class Solution {
private:
	struct Node {
		int val, row, col;
		Node(int v = 0, int r = 0, int c = 0) :val(v), row(r), col(c) {};
		friend bool operator<(const Node& n1, const Node& n2) {
			return n1.val > n2.val;
		}
	};
public:
	int kthSmallest(vector<vector<int>>& matrix, int k) {
		int n = matrix.size();
		priority_queue<Node> pn;
		for (int i = 0; i < n; ++i)pn.push(Node(matrix[i][0], i, 0));
		Node t;
		while (k--) {
			t = pn.top();
			pn.pop();
			if (t.col < n - 1)pn.push(Node(matrix[t.row][t.col + 1], t.row, t.col + 1));
		}
		return t.val;
	}
};

本代码提交AC,用时45MS。时间复杂度是O(klgn),堆的大小为n,每次归并调整堆需要lgn时间,一共需要归并k次,所以总的时间复杂度是O(klgn)。
另外用二分的方法可以同时利用行有序和列有序的特点。这种矩阵可以看成一个曲面,曲面的最低点为左上角元素left,最高点为右下角元素right,所以曲面就是从左上角向上延伸到右下角(想象一下MATLAB画的图)。那么第k小的数肯定在[left,right]范围内,我们可以二分查找这个区间。假设中点是mid,则我们在每一行找找比mid小的数有多少个,加起来如果等于cnt,则说明mid这个数排在第cnt位。因为每一行也是有序的,所以可以直接用upper_bound查找第一个比mid大的数。
代码如下:

class Solution {
public:
	int kthSmallest(vector<vector<int>>& matrix, int k) {
		int n = matrix.size(), left = matrix[0][0], right = matrix[n - 1][n - 1];
		while (left <= right) {
			int mid = left + (right - left) / 2;
			int cnt = 0;
			for (int i = 0; i < n; ++i) {
				cnt += upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
			}
			if (cnt < k)left = mid + 1;
			else right = mid - 1;
		}
		return left;
	}
};

本代码提交AC,用时43MS。时间复杂度是O(lgX nlgn),X为[left,right]的区间大小,ngln是对于每个mid,都需要在每一行二分查找比mid小的数的个数。
还可以将上述复杂度降为O(lgX n)。就是在找cnt,不需要每一行都二分查找,我们可以从矩阵的左下角往右上角阶梯查找,如果要查找的数更大,则往右移,否则往上移,每次查询只需要O(n)的时间,所以总时间是O(lgX n)。
代码如下:

class Solution {
private:
	int count_less_equal(vector<vector<int>>& matrix, int num) {
		int n = matrix.size(), i = n - 1, j = 0, cnt = 0;
		while (i >= 0 && j < n) {
			if (matrix[i][j] <= num) {
				cnt += i + 1;
				++j;
			}
			else --i;
		}
		return cnt;
	}
public:
	int kthSmallest(vector<vector<int>>& matrix, int k) {
		int n = matrix.size(), left = matrix[0][0], right = matrix[n - 1][n - 1];
		while (left <= right) {
			int mid = left + (right - left) / 2;
			int cnt = count_less_equal(matrix, mid);
			if (cnt < k)left = mid + 1;
			else right = mid - 1;
		}
		return left;
	}
};

本代码提交AC,用时39MS。

LeetCode Kill Process

LeetCode Kill Process
Given n processes, each process has a unique PID (process id) and its PPID (parent process id).
Each process only has one parent process, but may have one or more children processes. This is just like a tree structure. Only one process has PPID that is 0, which means this process has no parent process. All the PIDs will be distinct positive integers.
We use two list of integers to represent a list of processes, where the first list contains PID for each process and the second list contains the corresponding PPID.
Now given the two lists, and a PID representing a process you want to kill, return a list of PIDs of processes that will be killed in the end. You should assume that when a process is killed, all its children processes will be killed. No order is required for the final answer.
Example 1:

Input:
pid =  [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
Output: [5,10]
Explanation:
           3
         /   \
        1     5
             /
            10
Kill 5 will also kill 10.

Note:

  1. The given kill id is guaranteed to be one of the given PIDs.
  2. n >= 1.

给定一个父子进程的对应关系,现在要kill掉某个进程id,那么id的子进程,孙进程也会被kill掉,问最终被kill掉的进程有哪些。
简单题。先使用map把父子进程的对应关系存起来,因为是一个父亲可能有多个孩子进程,所以要用multimap。然后用bfs类似于树的层次遍历,把所有孩子进程遍历一遍并存到结果数组中。
代码如下,刚好看了C++ primer的unordered_multimap的范围查找,用equal_range很方便。

class Solution {
public:
	vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
		unordered_multimap<int, int> umm;
		for (int i = 0; i < pid.size(); ++i) {
			umm.insert(pair<int, int>(ppid[i], pid[i]));
		}
		vector<int> ans;
		queue<int> q;
		q.push(kill);
		while (!q.empty()) {
			int id = q.front();
			q.pop();
			ans.push_back(id);
			auto r = umm.equal_range(id);
			for (auto i = r.first; i != r.second; ++i)q.push(i->second);
		}
		return ans;
	}
};

本代码提交AC,用时166MS。

LeetCode Heaters

LeetCode Heaters
Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.
Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.
So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.
Note:

  1. Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
  2. Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
  3. As long as a house is in the heaters' warm radius range, it can be warmed.
  4. All the heaters follow your radius standard and the warm radius will the same.

Example 1:

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

给定房子和加热器的位置,问加热器的最小半径是所少才能使所有房子都在加热的范围之内。一个加热器的加热范围是一个圆,所有加热器的加热半径都是一样的。
要保证每个房子都在加热范围之内,且加热器的半径最小,则房子i肯定被紧邻i前后的两个加热器之一覆盖,其他加热器距离i的距离肯定比紧邻i前后的两个加热器远。比如x, i, y,i表示房子坐标,x和y分别表示紧邻i的两个加热器坐标,则覆盖i的最小半径应该是min(i-x,y-i)。
所以问题就转换为对每个房子坐标i,去加热器坐标数组中找到紧邻i前后的两个加热器坐标x和y,然后根据上述公式更新结果。为了便于查找,先对加热器坐标排序,然后直接二分查找就好了。
代码如下:

class Solution {
public:
	int findRadius(vector<int>& houses, vector<int>& heaters) {
		sort(heaters.begin(), heaters.end());
		int ans = 0;
		for (int i = 0; i < houses.size(); ++i) {
			int &pos = houses[i];
			int r = INT_MAX;
			auto lb = lower_bound(heaters.begin(), heaters.end(), pos);
			if (lb > heaters.begin())r = min(r, pos - *(lb - 1));
			auto ub = lower_bound(heaters.begin(), heaters.end(), pos);
			if (ub < heaters.end())r = min(r, *ub - pos);
			ans = max(ans, r);
		}
		return ans;
	}
};

本代码提交AC,用时89MS。
还可以自己写二分查找代码,如下:

class Solution {
private:
	int my_lower_bound(vector<int>& v, int target) {
		int l = 0, r = v.size() - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (target > v[m])l = m + 1;
			else r = m - 1;
		}
		return l;
	}
public:
	int findRadius(vector<int>& houses, vector<int>& heaters) {
		sort(heaters.begin(), heaters.end());
		int ans = 0, n = houses.size(), m = heaters.size();
		for (int i = 0; i < n; ++i) {
			int &pos = houses[i];
			int r = INT_MAX;
			int lb = my_lower_bound(heaters, pos);
			if (lb > 0)r = min(r, pos - heaters[lb - 1]);
			if (lb < m)r = min(r, heaters[lb] - pos);
			ans = max(ans, r);
		}
		return ans;
	}
};

本代码提交AC,用时76MS。

LeetCode Permutation in String

LeetCode Permutation in String
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.
Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

  1. The input strings only contain lower case letters.
  2. The length of both given strings is in range [1, 10,000].

给定两个字符串s1和s2,问s1的排列是否是s2的子串。
暴力方法是枚举s2的每个字符,如果在s1中,则在s2中取等长的子串,hash判断s2的子串和s1是否是同一个串的不同排列。
代码如下:

class Solution {
public:
	bool checkInclusion(string s1, string s2) {
		int n = s1.size(), m = s2.size();
		if (n > m)return false;
		unordered_map<char, int> hash1;
		for (int i = 0; i < n; ++i)++hash1[s1[i]];
		for (int i = 0; i < m; ++i) {
			if (hash1.find(s2[i]) != hash1.end()) {
				if (i + n <= m) {
					unordered_map<char, int> hash2;
					for (int j = i; j < i + n; ++j)++hash2[s2[j]];
					if (hash1 == hash2)return true;
				}
			}
		}
		return false;
	}
};

本代码提交AC,用时1365MS。
优化方法是使用滑动窗口方法,假设s1的长度为n。先hash s1,再在s2中开长度为n的窗口,判断窗口内的子串hash是否和s1的hash相等,相等则返回tru,否则窗口向右滑动一格,即增加右边一个字符频率,同时减掉左边一个字符频率,如此循环。
代码如下:

class Solution {
public:
	bool checkInclusion(string s1, string s2) {
		int n = s1.size(), m = s2.size();
		if (n > m)return false;
		vector<int> hash1(26, 0), hash2(26, 0);
		for (int i = 0; i < n; ++i) {
			++hash1[s1[i] - 'a'];
			++hash2[s2[i] - 'a'];
		}
		if (hash1 == hash2)return true;
		for (int i = n; i < m; ++i) {
			++hash2[s2[i] - 'a'];
			--hash2[s2[i - n] - 'a'];
			if (hash1 == hash2)return true;
		}
		return false;
	}
};

本代码提交AC,用时13MS。