[633] 平方数之和
https://leetcode-cn.com/problems/sum-of-square-numbers/description/
- algorithms
- Medium (34.98%)
- Likes: 169
- Dislikes: -
- Total Accepted: 40.4K
- Total Submissions: 114.8K
- Testcase Example: ‘5’
- Source Code: 633.sum-of-square-numbers.cpp
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
示例 1：
输入：c = 5 输出：true 解释：1 * 1 + 2 * 2 = 5
示例 2：
输入：c = 3 输出：false
示例 3：
输入：c = 4 输出：true
示例 4：
输入：c = 2 输出：true
示例 5：
输入：c = 1 输出：true
提示：
0 <= c <= 231 - 1
方法1: 双指针
本题可以使用双指针快速找到答案, 思想还是等同于遇到有序数组, 只不过数组范围为 0, sqrt(c)
唯一需要注意的是 c 的取值范围 , 最好用 long 来创建双指针
class Solution {
public:
bool judgeSquareSum(int c) {
if(c<=2){
return true;
}
long a = 0, b = sqrt(c);
while(a<=b){
if(b*b == c - a*a){
return true;
}else if(b*b < c - a*a){
++a;
}else{
--b;
}
}
return false;
}
};
复杂度分析:
- 时间复杂度:
O(sqrt(n)) - 空间复杂度:
O(1)
方法2: 二分查找
待完善
[680] 验证回文字符串 Ⅱ
https://leetcode-cn.com/problems/valid-palindrome-ii/description/
- algorithms
- Easy (39.95%)
- Likes: 336
- Dislikes: -
- Total Accepted: 67.2K
- Total Submissions: 167.6K
- Testcase Example: ‘“aba”‘
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: "aba" 输出: True
示例 2:
输入: "abca" 输出: True 解释: 你可以删除c字符。
注意:
- 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
方法1: 双指针
在数组首尾分别设置左右指针, 两指针朝中间靠拢, 两指针对应元素相等则继续靠拢, 需要注意的是, 当元素不等, 只要 区间为 [left+1, right) 或 [left, right-1) 的子数组满足回文即可
class Solution {
public:
bool validPalindrome(string s) {
int count=1, left = 0, right = s.size() - 1;
while(left < right){
if(s[left] == s[right]){
++left;
--right;
} else return (isvailed(s, left + 1, right) || isvailed(s, left, right - 1));
}
return true;
}
bool isvailed(string s, int left, int right){
while(left < right){
if(s[left] == s[right]){
++left;
--right;
}else return false;
return true;
}
}
};
复杂度分析:
- 时间复杂度:
O(n), 判断s与判断s的子字符都是O(n) - 空间复杂度:
O(1), 常量空间
