尝试制作一个仅检查string s1中是否存在string s2排列的程序。
在下面的程序中创建，并且适用于下面的测试用例。
输入：
s1 = "ab"
s2 = "eidballl"
输出：
True
说明：s2包含s1的一个排列（即ba）。
但是，当输入s2="sdfdadddbd"，s1="ab"预期为false但得到true时，此操作将失败。
我正在尝试找出这里缺少的东西。使用滑动窗口方法。在我的c#中的代码下面：
public bool CheckInclusion(string s1, string s2) {
var intCharArray = new int[256];
foreach(char c in s1)
{
intCharArray[c]++;
}
int start=0,end=0;
int count=s1.Length;
bool found=false;
while(end<s2.Length)
{
if (intCharArray[s2[end]]>0) { count--;}
intCharArray[s2[end]]--;
Console.WriteLine("end:" + end + " start:"+ start);
if(end-start==s1.Length) {
if (count==0) {return true;}
if (intCharArray[s2[start]]>=0)
{
count++;
}
intCharArray[s2[start]]++;
start++;
}
end++;
}
return false;
}
c#参考方案
我想这个问题与LeetCode 567类似。这些是简单，高效，低复杂度的公认解决方案：
C＃
class Solution {
public bool CheckInclusion(string s1, string s2) {
int lengthS1 = s1.Length;
int lengthS2 = s2.Length;
if (lengthS1 > lengthS2)
return false;
int[] countmap = new int[26];
for (int i = 0; i < lengthS1; i++)
countmap[s1[i] - 97]++;
int[] bCount = new int[26];
for (int i = 0; i < lengthS2; i++) {
bCount[s2[i] - 97]++;
if (i >= (lengthS1 - 1)) {
if (allZero(countmap, bCount))
return true;
bCount[s2[i - (lengthS1 - 1)] - 97]--;
}
}
return false;
}
private bool allZero(int[] s1, int[] s2) {
for (int i = 0; i < 26; i++) {
if (s1[i] != s2[i])
return false;
}
return true;
}
}
爪哇
class Solution {
public boolean checkInclusion(String s1, String s2) {
int lengthS1 = s1.length();
int lengthS2 = s2.length();
if (lengthS1 > lengthS2)
return false;
int[] countmap = new int[26];
for (int i = 0; i < lengthS1; i++) {
countmap[s1.charAt(i) - 97]++;
countmap[s2.charAt(i) - 97]--;
}
if (allZero(countmap))
return true;
for (int i = lengthS1; i < lengthS2; i++) {
countmap[s2.charAt(i) - 97]--;
countmap[s2.charAt(i - lengthS1) - 97]++;
if (allZero(countmap))
return true;
}
return false;
}
private boolean allZero(int[] count) {
for (int i = 0; i < 26; i++)
if (count[i] != 0)
return false;
return true;
}
}
蟒蛇
class Solution:
def checkInclusion(self, s1, s2):
count_map_s1 = collections.Counter(s1)
count_map_s2 = collections.Counter(s2[:len(s1)])
for i in range(len(s1), len(s2)):
if count_map_s1 == count_map_s2:
return True
count_map_s2[s2[i]] += 1
count_map_s2[s2[i - len(s1)]] -= 1
if count_map_s2[s2[i - len(s1)]] == 0:
del(count_map_s2[s2[i - len(s1)]])
return count_map_s2 == count_map_a
参考
在以下链接中解释了代码：
LeetCode 567 Solution
LeetCode 567 Discussion Board
这两个答案对于研究以下内容也很有用：
Link 1
Link 2
可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制
LeetCode题解统计城市的所有灯泡这个是我刚毕业的时候，一个真实的面试题，这是一个开放题。题目描述：想办法，将一个城市的所有灯泡数量统计出来。题解：费米估算法1、如果某个城市常驻人口有1000万2、假设每5人居住在一套房里，每套房有灯泡5只，那么住宅灯泡共有1000万只3、假设公众场所每10人共享一只灯泡，那么共有100万只4、主要的这两者相加就得出了1100万只当然实际上这是估算的，具体应…
LeetCode题解黑白圆盘一个圆盘被涂上了黑白二色，两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?题解：可以用一个相机即可
LeetCode题解圆上任取三点构成锐角三角形的概率来自字节跳动的一道几何题题解：1/4
LeetCode题解多人运动已知小猪每晚都要约好几个女生到酒店房间。每个女生 i 与小猪约好的时间由 [si , ei］表示，其中 si 表示女生进入房间的时间， ei 表示女生离开房间的时间。由于小猪心胸开阔，思想开明，不同女生可以同时存在于小猪的房间。请计算出小猪最多同时在做几人的「多人运动」。例子： Input ： [[ 0 , 30] ,[ 5 , 10 ] ， [15 , 2…