文章目录
LeetCode刷题记录：
67. 二进制求和
题目描述：
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
题解：
字符串模拟
两个二进制字符串按位相加
class Solution {
public:
string addBinary(string a, string b) {
//2022年3月19日15:34:31
string ans;
//从低位开始相加
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int n = max(a.size(), b.size()), carry = 0;
for (size_t i = 0; i < n; ++i) {
//a.at(i) 下标为i的字符 获得指定字符
carry += i < a.size() ? (a.at(i) == '1') : 0;
carry += i < b.size() ? (b.at(i) == '1') : 0;
ans.push_back((carry % 2) ? '1' : '0');
carry /= 2;
}
if (carry) {
//如果还有一位
ans.push_back('1');
}
reverse(ans.begin(), ans.end());
return ans;
}
};
tip:
用substr的指定子串（给定起始位置和长度）替换从指定位置上的字符串
string& replace (size_t pos, size_t len, const string& str, size_t subpos, size_t sublen);
string& replace(被替换的开始位置,替换的长度,替换件的名字,替换件的开始位置,替换件中替换的长度);
int main() {
string line = "this@ is@ a test string!";
string substr = "12345";
line = line.replace(0, 2, substr, substr.find("1"), 3);
//用substr的指定子串（从1位置数共3个字符）替换从0到5位置上的line
cout << line << endl;
return 0;
}
输出：
123is@ is@ a test string!
69. x 的平方根
题目描述：
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 < = x < = 2 31 − 1 0 <= x <= 2^{31} - 1 0<=x<=231−1
题解：
（1）二分答案
class Solution {
public:
int mySqrt(int x) {
//二分
int l = 0, r = x, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long long)mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
};
（2）数学方法：「袖珍计算器算法」
是一种用指数函数 exp \exp exp 和对数函数 ln \ln ln 代替平方根函数的方法。我们通过有限的可以使用的数学函数，得到我们想要计算的结果。
我们将 x \sqrt{x} x 写成幂的形式 x 1 / 2 x^{1/2} x1/2 ，再使用自然对数 e e e 进行换底，即可得到：
注意： 由于计算机无法存储浮点数的精确值，而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。例如当 x = 2147395600 x = 2147395600 x=2147395600 时， e 1 2 ln x e^{\frac{1}{2} \ln x} e21lnx的计算结果与正确值 4634046340 4634046340 4634046340 相差 1 0 − 11 10^{-11} 10−11 ，这样在对结果取整数部分时，会得到 4633946339 4633946339 4633946339 这个错误的结果。
因此在得到结果的整数部分 ans \textit{ans} ans 后，我们应当找出 ans \textit{ans} ans 与 ans + 1 \textit{ans} + 1 ans+1 中哪一个是真正的答案。
class Solution {
public:
int mySqrt(int x) {
if (x == 0) {
return 0;
}
int ans = exp(0.5 * log(x));
return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
}
};
（3）数学方法：「牛顿迭代法」
（大佬解法，拓展思维）
下面这种方法可以很有效地求出根号 aa 的近似值：首先随便猜一个近似值 x，然后不断令 x 等于 x 和 a/x 的平均数，迭代个六七次后 x 的值就已经相当精确了。
例如，我想求根号 2 等于多少。假如我猜测的结果为 4，虽然错的离谱，但你可以看到使用牛顿迭代法后这个值很快就趋近于根号 2 了：
( 4 + 2/ 4 ) / 2 = 2.25
( 2.25 + 2/ 2.25 ) / 2 = 1.56944..
( 1.56944..+ 2/1.56944..) / 2 = 1.42189..
( 1.42189..+ 2/1.42189..) / 2 = 1.41423..
…
这种算法的原理很简单，我们仅仅是不断用 ( x , f ( x ) ) (x, f(x)) (x,f(x)) 的切线来逼近方程 x 2 − a = 0 x^2-a=0 x2−a=0 的根。
a \sqrt{a} a 实际上就是 x 2 − a = 0 x^2-a=0 x2−a=0 的一个正实根，这个函数的导数是 2 x 2x 2x。
也就是说，函数上任一点 ( x , f ( x ) ) (x,f(x)) (x,f(x)) 处的切线斜率是 2 x 2x 2x。
那么， x − f ( x ) 2 x x-\frac{f(x)}{2x} x−2xf(x) 就是一个比 x x x 更接近的近似值。
代入 f ( x ) = x 2 − a f(x)=x^2-a f(x)=x2−a 得到 x − x 2 − a 2 x x-\frac{x^2-a}{2x} x−2xx2−a，也就是 x + a x 2 \frac{x+\frac{a}{x}}{2} 2x+xa。
class Solution {
int s;
public:
int mySqrt(int x) {
s=x;
if(x==0)
return 0;
return ((int)(sqrts(x)));
}
double sqrts(double x){
double res = (x + s / x) / 2;
if (res == x) {
return x;
} else {
return sqrts(res);
}
}
};
70. 爬楼梯
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
提示：
1 <= n <= 45
题解：
动态规划
本问题其实常规解法可以分成多个子问题，爬第n阶楼梯的方法数量，等于 2 部分之和
（1）递归：
//超时啦！！！（呜呜呜）
class Solution {
public:
int climbStairs(int n) {
if(n==1||n==0)return 1;
return climbStairs(n-1)+climbStairs(n-2);
}
};
（2）改个递推：（顺利过关！！！）
class Solution {
public:
int climbStairs(int n) {
int p = 0, q = 0, r = 1;
for (int i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
};
（3）还可以dp嘛：
class Solution {
public:
int climbStairs(int n) {
int dp[50]={
0};
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
看了LeetCode官方题解的我（os:我是什么垃圾 ）
（4）矩阵快速幂：
时间复杂度：同快速幂， O ( log n ) O(\log n) O(logn)。
空间复杂度： O ( 1 ) O(1) O(1)。
class Solution {
public:
vector<vector<long long>> multiply(vector<vector<long long>> &a, vector<vector<long long>> &b) {
vector<vector<long long>> c(2, vector<long long>(2));
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
}
vector<vector<long long>> matrixPow(vector<vector<long long>> a, int n) {
vector<vector<long long>> ret = {
{
1, 0}, {
0, 1}};
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, a);
}
n >>= 1;
a = multiply(a, a);
}
return ret;
}
int climbStairs(int n) {
vector<vector<long long>> ret = {
{
1, 1}, {
1, 0}};
vector<vector<long long>> res = matrixPow(ret, n);
return res[0][0];
}
};
（5）斐波拉契数列的通项公式：
class Solution {
public:
int climbStairs(int n) {
double sqrt5 = sqrt(5);
double fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1);
return (int)round(fibn / sqrt5);
}
};
看到这里，我只能高呼：“数学万岁！！！”
83. 删除排序链表中的重复元素
题目描述：
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表。
题解：
单链表的删除操作
（1） 递推：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) {
return head;
}
ListNode* p=head;
while(p->next){
if(p->next->val == p->val)
p->next=p->next->next;
else
p=p->next;
}
return head;
}
};
（2）递归：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head||!head->next){
return head;
}
head->next = deleteDuplicates(head->next);
return head->val == head->next->val ? head->next : head;
}
};
（3）双指针
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL || head->next == NULL)
return head;
ListNode* cur = head;
ListNode* next = head->next;
while (next != NULL) {
if (next->val != cur->val) {
cur = cur->next;
} else {
cur->next = next->next;
}
next = next->next;
}
return head;
}
};
（4）题解新方法(哑结点：这样就不用判空了
在头节点前面增加虚拟头节点，这样对头节点的处理就跟普通节点一样。
不过，需要注意的是：设置虚拟头节点的值时，需要设置大一点，因为链表是排序链表，如果设置比较小，可能跟原头节点的值相等，如果原头节点后面恰好没有其它节点的值等于其值，这样原头节点也被删除，从而导致出错。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
/* 创建虚拟头节点，并给其节点值赋值 */
ListNode* dummyHead = new ListNode(1000);
/* 将虚拟头节点指向原链表头节点 */
dummyHead->next = head;
ListNode* cur = dummyHead;
while (cur->next != nullptr) {
/* 当前节点值等于其下一节点值 */
if (cur->val == cur->next->val) {
/* 将当前节点指向其下下一个节点 */
cur->next = cur->next->next;
/* 当前节点值不等于其下一节点值，让当前节点右移，继续遍历 */
} else {
cur = cur->next;
}
}
/* 释放虚拟头节点的空间，防止内存泄漏 */
ListNode* retNode = dummyHead->next;
delete dummyHead;
return retNode;
}
};
82. 删除排序链表中的重复元素 II
题目描述：
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表 。
题解：
其实像这种要删除节点的题，头节点之前开一个节点，从那个点向后遍历模拟，问题会简单很多，不需要考虑很多奇奇怪怪的条件
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head)
return head;
ListNode* dummyHead = new ListNode(-1000, head);
ListNode* cur = dummyHead;
while (cur->next && cur->next->next) {
if (cur->next->val == cur->next->next->val) {
int x = cur->next->val;
while (cur->next && cur->next->val == x) {
cur->next = cur->next->next;
}
}
else {
cur = cur->next;
}
}
return dummyHead->next;
}
};
京公网安备 11010502036488号