7道easy+5道medium。
今天想休息下，所以就先做部分位运算的了(
(medium)34. 在排序数组中查找元素的第一个和最后一个位置
只不过就是每次找到的时候向前再继续找或者向后再继续找罢了。代码如下：
class Solution {
public:
int find(int l , int r , vector<int>& nums)
{
if(l >= r)
{
if(nums[r] != num)
return -1;
return r;
}
int mid = (l + r) >> 1;
if(nums[mid] == num)
{
int tmp = find(l , mid , nums);
return tmp == -1 ? mid : tmp;
}
if(nums[mid] > num)
return find(l , mid , nums);
else
return find(mid + 1 , r , nums);
}
int findr(int l , int r , vector<int>& nums)
{
if(l >= r)
{
if(nums[r] != num)
return -1;
return r;
}
int mid = (l + r) >> 1;
if(nums[mid] == num)
{
int tmp = findr(mid + 1 , r , nums);
return tmp == -1 ? mid : tmp;
}
if(nums[mid] > num)
return findr(l , mid , nums);
else
return findr(mid + 1 , r , nums);
}
vector<int> searchRange(vector<int>& nums, int target) {
num = target;
int n = nums.size();
vector<int> ans;
if(n)
{
int k = find(0 , n - 1 , nums);
ans.push_back(k);
ans.push_back(findr(max(k , 0) , n - 1 , nums));
}
else
{
ans.push_back(-1);
ans.push_back(-1);
}
return ans;
}
private:
int num;
};(medium)153. 寻找旋转排序数组中的最小值
由于是旋转获得的新数组，所以最小值右边的最大值肯定是小于左边部分的最小值的，即nums[r]>nums[l]；而当nums[mid] > nums[r]时，说明mid位于最小值左边的链上，要往右边找；反之则往左边找。代码如下：
class Solution {
public:
int find(int l , int r , vector<int>& nums)
{
if(l == r)
return nums[l];
int mid = (l + r) >> 1;
if(nums[mid] < nums[r])
return find(l , mid , nums);
else
return find(mid + 1 , r , nums);
}
int findMin(vector<int>& nums) {
n = nums.size();
return find(0 , n - 1 , nums);
}
private:
int n;
};(easy)67. 二进制求和
思路很多，但我还是不想操作太多，所以用i表示当前到了第几位，n-i表示a中的，m-i表示b中的，这样就能在同步操作的同时减少更多操作。代码如下：
class Solution {
public:
string addBinary(string a, string b) {
int n = a.length();
int m = b.length();
int i = 1;
bool flag = 0;
int tmp;
string s = "";
while(i <= m || i <= n || flag)
{
tmp = flag;
if(i <= n)
tmp += a[n - i] - '0';
if(i <= m)
tmp += b[m - i] - '0';
if(tmp >= 2)
{
flag = 1;
//tmp %= 2;
tmp = tmp & 1;
}
else
{
flag = 0;
}
s += tmp + '0';
i++;
}
reverse(s.begin() , s.end());
return s;
}
};(easy)190. 颠倒二进制位
这更没啥好说的，肉眼上的第i位直接左移32-i位加在sum上即可(代码中用31-i是因为i是从0开始)。
如果多次调用，我就会把1<<i位的值记录下来，这样就不需要每次都计算一遍1<<i的值了。
代码如下：
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t sum = 0;
for(int i = 0 ; i < 32 ; i++)
{
sum = sum | ((n & 1) << (31 - i));
n = n >> 1;
}
return sum;
}
};(easy)191. 位1的个数
按照上题相同做法就没意思了，换成记录1<<i的情况。代码如下：
class Solution {
public:
void init()
{
p[0] = 1;
for(int i = 1 ; i < 32 ; i++)
{
p[i] = p[i - 1] << 1;
}
return ;
}
int hammingWeight(uint32_t n) {
init();
int ans = 0;
for(int i = 0 ; i < 32 ; i++)
{
if(n&p[i])
ans++;
}
return ans;
}
private:
uint32_t p[32];
};(easy)136. 只出现一次的数字
好像是第一道自己没有思路的easy题？确实第一下真想不到线性时间+常量空间的想法，倒是想到每个相加，遇到相同的就+当前位*-1，但依然需要O(n)的额外空间; 唯一想法就是排序(但是效率是nlogn不算线性)。后面看题解才想起来还有异或这东西。
异或运算有以下三个性质。
任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
任何数和其自身做异或运算，结果是 0，即 a⊕a=0
异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b代码如下：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int n = nums.size();
int ans = 0;
for(int i = 0 ; i < n ; i++)
ans = ans ^ nums[i];
return ans;
}
};(medium)137. 只出现一次的数字 II
什么牛魔题，直接上电路了可还行😄。当然，思路很好，即若需要只出现一次的数字，其他数字都出现t次，我们只需要把每个数其二进制中第i位(0=<i<=31)的值加至p[i]，最后p[i]的值必定为t的倍数，不为t的倍数的i则为只出现一次的数字的第i位。更进阶的数字电路的思路我是不想解释了。代码如下：
class Solution {
public:
void init()
{
p[0] = 1;
for(int i = 1 ; i < 32 ; i++)
p[i] = p[i - 1] << 1;
return ;
}
void get(int x)
{
for(int i = 0 ; i < 32 ; i++)
{
num[i] += (bool)(p[i] & x);
}
return ;
}
int singleNumber(vector<int>& nums) {
int n = nums.size();
init();
for(int i = 0 ; i < n ; i++)
{
get(nums[i]);
}
int ans = 0;
for(int i = 0 ; i < 32 ; i++)
{
int tmp = num[i] % 3;
if(tmp)
ans += tmp << i;
}
return ans;
}
private:
int p[32];
int num[32];
};(medium)201. 数字范围按位与
只能说位运算确实牛逼好吧，只想到了二进制中若某一位有0的出现则该位必定为0，但不知道怎么继续了。看题解才明白，若right-left=1，则最后一位肯定有0的存在，这样可以继续递推，直到right=left，右移的次数num则为0在二进制中出现的次数，即后num位都为0，num位前的部分则为当前的right，即结果为当前的right<<num。代码如下：
class Solution {
public:
int rangeBitwiseAnd(int left, int right) {
int zero_num = 0;
while(right > left)
{
zero_num++;
right >>= 1;
left >>= 1;
}
return right << zero_num;
}
};(easy)9. 回文数
不用转换为字符串，其实就是一个很简单的问题：数字x有n位，则第一位为x/10^(n-1)，最后一位为x%10，每次递归就x = x % 10^(n-1) , x /= 10 , n = n - 2。代码如下：
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0)
return 0;
int tmp = x;
int num = 0;
while(tmp)
{
num++;
tmp = tmp / 10;
}
tmp = x;
while(tmp)
{
int m = pow(10 , num - 1);
if(tmp / m != tmp % 10)
return 0;
tmp %= m;
tmp /= 10;
num -= 2;
}
return 1;
}
};(easy)66. 加一
单纯只是考虑进位的问题的一道题，代码如下：
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int n = digits.size();
int i = 1;
bool flag = 1;
int tmp;
vector<int> ans;
while(i <= n)
{
tmp = flag + digits[n - i];
flag = 0;
if(tmp >= 10)
{
flag = 1;
tmp = tmp % 10;
}
ans.push_back(tmp);
i++;
}
if(flag)
ans.push_back(flag);
reverse(ans.begin() , ans.end());
return ans;
}
};(medium)172. 阶乘后的零
算是一道找规律的题？其实本质是质因数拆解，可以发现，2是每两个就出现一次，而5则是每5个出现一次，而当遇到一次5时就表示肯定有一个0，就转变成了求阶乘其中有5的因子的个数。继续优化；我们发现，假设我们n/5之后，表示每5个出现1次的5已经处理完了，但由于25 125这种有多个5的我们只求了一个，所以还需要加上n/(5^t) t=2,3....(因为每次到k*5^t的时候，已经加了t-1次它的5的个数了，此时针对该数只需要加1即可)，因而就变成了求n/(5^t) t=1,2,3..的和。代码如下：
class Solution {
public:
int trailingZeroes(int n) {
int ans = 0;
while(n)
{
ans += n / 5;
n /= 5;
}
return ans;
}
};(easy)69. x 的平方根
纯数学题，完全不会就用的暴力枚举sqrt(x)，由于x<=2^31-1，那么sqrt(x)<2^16=65536，很小的一个范围，枚举问题不大；本质是牛顿迭代法，具体见下：
关于x-(x^2-a)/2x的个人理解:这个是由切线方程转换过来的。 确定一个切线方程在于它的斜率和对于x轴的位移， 可以这样写每个点的切线方程 y=(2x)(x-b)。 (2x)表示斜率，b代表对于x轴向正方向的位移。 这个切线方程和f(x)的交点这样就可以求了： (2x)(x-b)=x^2-a， 可得b=(x+a/x)/2。 这个b就是切线方程和x轴的交点的x坐标， 由答主提供的图像可以直观看出交点坐标比x更接近平方根，不断重新赋值，逐渐趋近。
具体代码如下：
class Solution {
public:
int mySqrt(int x) {
long long tmp = x;
while(tmp * tmp > x)
{
tmp = (tmp + x / tmp) >> 1;
}
return tmp;
}
};这个是暴力的代码：
class Solution {
public:
int mySqrt(int x) {
long long k = 0;
for(int i = 0 ; i <= tmp ; i++)
{
k = (long long)i * (long long)i;
if(k > x)
return (i - 1);
}
return 0;
}
private:
int tmp = 1 << 16;
};