【每日编程-452期】Leetcode.522.最长特殊序列II
样例：
输入: "aba", "cdc", "eae"
输出: 3
提示：
所有给定的字符串长度不会超过 10 。
给定字符串列表的长度将在 [2, 50 ] 之间。
解决方法：
（1）算法的基本思想：
算法一：
两两比较字符串
i串和j串进行比较，如果 i 和 j 相等，则跳过
判断 i 串是否为 j 串的子串，如果是的话，则不用进行接下来的比较了，因为总有另一个串比它要长。
如果不是则继续比较，直到和所有其它串比较完，更新res。
（2）代码实现：
class Solution
{
public:
int findLUSlength(vector<string> &strs)
{
int res = -1, j = 0, n = strs.size();
//两两比较字符串
for (int i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
//遇到自己，跳过
if (i == j)
continue;
//判断i串是否为j串的子串，若是，则返回true执行break，不再进行比较，跳出j循环，否则继续进行比较。
if (checkSubs(strs[i], strs[j]))
break;
}
//i串与strs中所有其它串进行比较
//若j = n 则i串不是所有其它串的子串，对res进行更新
//若j ≠ n 则i串是某个串的子串，不对res进行更新，因为总有一个串比它要长
if (j == n)
res = max(res, (int)strs[i].size());
}
return res;
}
//判断subs是否为str的子串
int checkSubs(string subs, string str)
{
int i = 0;
//让subs站好别动，用str的每个元素按顺序去匹配subs串
for (char c : str)
{
//从某个相同的元素开始计数，若i的值与subs串的长度相等，则subs串为str串的子串，返回true
if (c == subs[i])
++i;
if (i == subs.size())
break;
}
return i == subs.size();
}
};
class Solution
{
public:
//如果a串是b串的子串
bool isCommon(string a, string b)
{
int i = 0, j = 0;
while (i < a.size() && j < b.size())
{
if (a[i] == b[j])
{
i++;
j++;
}
else
j++;
}
return i == a.size();
}
int findLUSlength(vector<string> &strs)
{
int ans = -1;
for (int i = 0; i < strs.size(); ++i)
{
bool flag = true;
for (int j = 0; j < strs.size(); ++j)
{
//不是自己并且i串是j串的子串，则令flag=false，不用更新ans，break内层for
if (i != j && isCommon(strs[i], strs[j]))
{
flag = false;
break;
}
}
if (flag)
ans = max(ans, int(strs[i].size()));
}
return ans;
}
};
样例一：
输入: L = 6, R = 10输入: 4解释:6 -> 110 (2 个计算置位，2 是质数)
7 -> 111 (3 个计算置位，3 是质数)
9 -> 1001 (2 个计算置位，2 是质数)
10-> 1010 (2 个计算置位，2 是质数)
输出样例：
输入: L = 10, R = 15
输入: 5
解释:
10-> 1010 (2 个计算置位，2 是质数)
11 -> 1011 (3 个计算置位, 3 是质数)
12 -> 1100 (2 个计算置位, 2 是质数)
13 -> 1101 (3 个计算置位, 3 是质数)
14 -> 1110 (3 个计算置位, 3 是质数)
15 -> 1111 (4 个计算置位, 4 不是质数)
注意:
L, R是L <= R且在[1, 10^6]中的整数。R - L的最大值为 10000。
class Solution {
public:
int countPrimeSetBits(int L, int R) {
}
};