29.日常算法

1. 验证回文串 II

题目来源
给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

示例 1：
输入: s = “aba”
输出: true

示例 2：
输入: s = “abca”
输出: true
解释: 可以删除 “c” 字符 或者 “b” 字符

class Solution {
public:bool validPalindrome(string s) {int left = 0, right = s.size() - 1;int count = 0;;int idxl = 0;int idxr = 0;while (left < right){if (s[left] != s[right]){++count;if (count == 3) return false;if (count == 2){// 第二次进来说明去掉左边的不正确回到原来的地方去掉右边的left = idxl;right = idxr;--right;}else{//第一次进来记录原来的坐标先去掉左边的idxl = left;idxr = right;++left;}}else{++left;--right;}}return true;}
};

2.x 的平方根

题目来源
给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。正数的平方根有两个，只输出其中的正数平方根。如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

示例 1：
输入: x = 4
输出: 2

示例 2：
输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842…，由于小数部分将被舍去，所以返回 2

class Solution {
public:int mySqrt(int x) {if (x == 0) return 0;int left = 1, right = x;while (left < right){long long mid = (right - left + 1) / 2 + left;if (mid * mid > x) right = mid - 1;else left = mid;}return left;}
};