指针练习(下)

76.最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。

如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。

注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
示例 2:

输入:s = "a", t = "a"
输出:"a"
示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。
思路:

第一次做困难的题目,首先我们可以将示例2和示例3的两种情况做处理:

if (s.size() < t.size())
return "";
if ((s.size() == t.size()) && (s == t))
return s;

示例1应该是考察滑动窗口概念,但是貌似没看懂题意,后面你这道题目在补。

LeetCode See: ​​https://leetcode.cn/problems/linked-list-cycle-ii/​

633.平方数之和

给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a2 + b2 = c

示例 1:

输入:c = 5
输出:true
解释:1 * 1 + 2 * 2 = 5
示例 2:

输入:c = 3
输出:false
思路:

输入一个数,拆分成两个数的乘机,如果不用数据库函数真的不好搞,一开始想的11 + xx = input,但这样显然不合理也不对

x*x = input - (1*1)

如果看作x && y ,总要先假设一个有数据的

for(int x = 0 ; x <= input; ++ x)
{
int y = input - (x*x);
平方根(y);
判断是否满足;
}

求平方根的函数应该需要包含math.c/cmath,具体我也忘了百度了一下,sqrt()函数,返回是浮点数(很多位),那么我们需要判断返回的是不是整数。

bool judgeSquareSum(int c) {
for (float x = 0; x <= c; ++x)
{
float y = c - (x * x);
auto y_ = sqrt(y);
if (y_ == (int)y_)
return true;
}
return false;
}

提交以后缺报错,输入3:但是本地的vs没有错误

Line 8: Char 18: runtime error: -nan is outside the range of representable values of type 'int' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:17:18

用了官方答案:

bool judgeSquareSum(int c) {
for (long a = 0; a * a <= c; a++) {
double b = sqrt(c - a * a);
if (b == (int)b) {
return true;
}
}
return false;
}

不纠结了

LeetCode See: ​​https://leetcode.cn/problems/sum-of-square-numbers/​

680.验证回文字符串 Ⅱ

给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。

示例 1:
输入: s = "aba"
输出: true

示例 2:
输入: s = "abca"
输出: true
解释: 你可以删除c字符。

示例 3:
输入: s = "abc"
输出: false

特意百度了一下: "回文串"是一个正读和反读都一样的字符串,比如"level"或者"noon"等等就是回文串。 根据题意,正反读aba成立,删除其中一个还能保证一致即可。

思路:

定义两个指针分别从指向头尾,首尾字母(ascii码)比较,end指向字符串最后一个字母来做移动,start来右移动。

// 首先如果<=2那一定是真,因为允许删除一个,怎么都是正确的。
const int lens = strlen(s.c_str());
if (lens <= 2)
return true;
const char* pstr = s.c_str(); const char* phead = s.c_str();
const char* pend = pstr + lens - 1;
int idx = 1;
while (pstr <= pend)
{
if (*pstr != *pend)
{
if (0 == idx--)
return false;
// 处理: "xccccccccccc" "eccer" "aydmda"
if (*pstr != *(pend - 1))
pend++;
else
pstr--;
}
pstr++; pend--;
}
return true;

测试用例报错了"ebcbbececabbacecbbcbe",会发现上面逻辑还是有欠缺。

笨办法, 添加一个check_tr函数,分别传入pstar+1和pend-1,如果pstar+1匹配后为真直接返回,否则在传入pend-1重新遍历一次,可以保证剩下的字符串是否一致.

可以在Check_tr加一个判断if_else来区分到底用那种比较好可能会提高进一步优化,我这里么有优化。

class Solution {
public:
bool check_tr(const char* pstr, const char* pend)
{
while (pstr <= pend)
{
if (*pstr != *pend)
return false;
pstr++; pend--;
}
return true;
}

bool validPalindrome(std::string s) {
const int lens = strlen(s.c_str());
if (lens <= 2)
return true;
const char* pstr = s.c_str();
const char* pend = pstr + lens - 1;
while (pstr <= pend)
{
if (*pstr != *pend)
{
bool nret = false;
check_tr(pstr+1, pend) ? nret = true : nret = check_tr(pstr, pend-1);
return nret;
}
pstr++; pend--;
}
return true;
}
};

虽然通过了测试用力,但是会发现问题,如果运气不好则会调用两次check_tr()。

从内到外查询也会有缺陷,从内到外查询的意思:计算star - end中间还剩多少字符串,end - start = ;llens / 2,余数不需要管。

const int lens = (pend - pstr) / 2;

如果对很大的字符串"bbaaaaa...... bacb ......aaaaaacb",指针从外围会很耗时间,从内围直接可以返回,但是如果遇到外围很大的字符串反之。

524.通过删除字母匹配到字典里最长单词

给你一个字符串 s 和一个字符串数组 dictionary ,找出并返回 dictionary 中最长的字符串,该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个,返回长度最长且字母序最小的字符串。如果答案不存在,则返回空字符串。

示例 1:

输入:s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出:"apple"
示例 2:

输入:s = "abpcplea", dictionary = ["a","b","c"]
输出:"a"
思路:

这道题目比较有意思,看到题目首选以dictionary遍历拿到字符串 首先s绝对是双指针遍历。

1)定义pstart 和 pend. s的pstart和"apple"_f_pstart匹配。

2)pend和"apple"_f_pend的尾匹配。

3)如果if (0 < (f_pstart - f_pend))代表匹配成功

4)匹配成功要存储到数组,因为还要返回长度最长且字母序最小的字符串。

std::string findLongestWord(std::string s, std::vector<std::string>& dictionary) {

std::vector<std::string> hitdict;
const int ilens = s.size();
for (auto const iter : dictionary)
{
const char* pstart = s.c_str();
const char* pend = pstart + ilens - 1;

const int f_ilens = iter.size();
const char* f_pstart = iter.c_str();
const char* f_pend = f_ilens + f_pstart - 1;

if (ilens < f_ilens)
continue;

while (pstart <= pend)
{
if (*pstart == *f_pstart)
f_pstart++;
if (*pend == *f_pend)
f_pend--;
if (0 < (f_pstart - f_pend))
{
hitdict.push_back(iter);
break;
}
pstart++; pend--;
}
}
if (hitdict.size() == 1)
return hitdict[0];
std::string max_string;
int maxlens = 0;
for (auto iter : hitdict)
{
if (maxlens == 0)
{
maxlens = iter.size();
max_string = iter;
continue;
}
if (maxlens > iter.size())
continue;
else if (maxlens == iter.size())
{
// 字母序最小的字符串
for (SIZE_T idx = 0; idx < iter.size(); ++idx)
{
if (iter[idx] != max_string[idx])
{
if (iter[idx] < max_string[idx])
{
maxlens = iter.size();
max_string = iter;
}
break;
}
}
}
else
{
maxlens = iter.size();
max_string = iter;
}
}
return max_string;
}

一把梭完成测试用例。

LeetCode See: ​​https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/​

发表评论

相关文章