LeetCode 刷题
LeetCode 刷题
（以前刷的）
1.链表反转
- 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000
解法一 暴力：
遍历链表的每个节点，每遍历个节点就用头插法插入一个新的链表里
时间复杂度为 T(n^2) 空间复杂度为O(n)
解法二： 迭代
不生成新的链表，把链表的指向的方向反过来
假设链表为 1 ->2 -> 3 ->∅ 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
在遍历链表时，将当前节点的指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while (cur)
{
ListNode* T = cur->next;
cur->next =pre;
pre =cur;
cur = T;
} //画图解决
return pre;
}
};
2.删除倒数第k个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
!img
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
解法一 ： 遍历整个链表后，算出结点数，反推正序第几个 O(N) N 为链表的长度 ，T（N)
解法二 ：双指针，一个前指针一个指针，前指针先走n步，然后 后指针和前指针一起走，前指针走到尾后，后指针指向待删除节点的前一部分
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* pre = new ListNode(1); //设置一个虚拟的前置结点
pre->next = head;
ListNode* h1 = pre; //前指针
ListNode* h2 = pre; //后指针
ListNode* temp = nullptr;
for (int i = 0; i < n+1; ++i)
h1 = h1->next;
while (h1)
{
h1 = h1->next;
h2 = h2->next;
}
temp = h2->next;
h2->next = h2->next->next;
delete temp;
head = pre->next;
delete pre;
return head;
}
};
3.盛最多水的容器（双指针） 3. 盛最多水的容器（双指针）
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
!img
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
解法一：暴力求解
遍历每一个容器， 时间复杂度O（n^2)
解法二： 双指针
- 一个指针在头，一个指针在后，分别向中间靠拢，如何移动呢（移动的条件）？
- 那个指针指向的值比较小就先移动那个.
- 容器的大小
min（头，尾） \* （头到尾直接的距离）
为啥移动小的呢？
容器的大小取决于最小的那个板，移动最大的那个板子，容器只会变得最小或者不变（板子可能变大，容器大小不变，板子变小若是比原来较小的那个板子还小，容器则会变得更小）移动较大的那个板子则是可能变大，会不会错过同个长度的其他搭配呢？其实我也没琢磨透…
- 代码
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1;//减一是要换成逻辑地址下标
int ans = 0;
while (l<r)
{
int area = min(height[l], height[r]) * (r - l);
ans = max(ans, area);
if (height[l] < height[r])
l++;
else
r--;
}
return ans;
}
4.冒泡排序
今天去面试，笔试要写个冒泡排序，这题应该信手拈来的，可我还推了那么久！！不行啊！
vector<int> maopao(vector<int> x)
{
int i, y;
for (i = 0; i < x.size() - 1; i++)
{
for ( y = 0; y < x.size()-1 - i; y++)
{
if (x[y] > x[y + 1])
{
swap(x[y], x[y + 1]);
}
}
}
return x;
}
时间复杂度为O( n^2） 两遍循环
5数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
解法1 : 用set容器（该容器没有重复的数字），遍历vector ，遍历一个插入一个，插入失败则是重复的
int findRepeatNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int x = 0; x < nums.size(); x++)
if (nums[x] == nums[x + 1])
return nums[x + 1];
return 0;
};
解法2： 原地交换，有0- n-1个数字， 每个数都对应一个下标 i，当然 下标 i 不一定等于 nums\[i\],
若是等于的话，则有可能一个下标对应很多个数，
遍历每一个数，将其数值作为下标，即
nums[nums[i]] = nums[i];
这样一来就做到 数值就是其索引值
继续遍历 ，若是发现 交换时 索引值对应的数值已经存在了，则说明有重复的了
if (nums[nums[i]]== nums[i])
return nums[i];
看代码
int findRepeatNumber(vector<int>& nums) {
int i = 0;
while (i<nums.size()) //遍历
{
if (nums[i] == i) //判断索引值和当前的值是否对应
{
i++; //是，则继续遍历下一个
continue;
}
if (nums[nums[i]] == nums[i]) //核心： 判断是否有重复
//判断当前的值 和以当前值为索引的所对应的值是否相等
return nums[i];
swap(nums[i], nums[nums[i]]); //不相等，则交换
i++;
}
return -1;
}
6.二叉树的三种遍历
递归 和迭代的方法 递归 和迭代的方法
前序 （根左右） 前序 （根左右）
递归：先往左边一直遍历，遍历一个抽一个，，
int forn_tree(TreeNode* root,vector<int>& res) {
if (root = NULL) //递归出口 该节点不存在
return ; //遍历每一个元素都是根节点
res.push_back(root->val); //遍历每一个元素都是根节点
forn_tree(root->left, res);
forn_tree(root->right, res);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
forn_tree(root, res); //递归函数
return res;
}
利用栈来完成递归
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
while (!s.empty() || root)
{
if (root)
{
res.push_back(root->val);
s.push(root);
root = root->left;
}
else
{
root = s.top();
s.pop();
root = root->right;
}
}
return res;
}
中序 （左根右） 中序 （左根右）
同上，递归遍历，问题是何时打印出来该节点 总结：跟在哪里就先打印哪里，如中序 根在左右节点中间
所以， 先遍历左边，一直往左遍历，到最左边的时候打印节点，然后往右遍历
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorderTraversal_tree(root, res);
return res;
}
void inorderTraversal_tree(TreeNode* root, vector<int> &res) {
if (root == nullptr)
return ;
inorderTraversal_tree(root->left, res);
res.push_back(root->val);
inorderTraversal_tree(root->right, res);
}
使用栈来递归：
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
while (!s.empty() || root)
{
if (root)
{
s.push(root);
root = root->left;
}
else
{
root = s.top();
s.pop();
res.push_back(root->val);
root = root->right;
}
}
}
后续 （左右根）
原理同上
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
inorderTraversal_tree(root, res);
return res;
}
void postorderTraversal_tree(TreeNode* root, vector<int> &res) {
if (root == nullptr)
return ;
postorderTraversal_tree(root->left, res);
postorderTraversal_tree(root->right, res);
res.push_back(root->val);
}
使用栈来递归：
vector<int> postorderTraversal(TreeNode* root)
{
vector<int> res;
inorderTraversal_tree(root, res);
return res;
}
7. 合并两个有序链表 7\. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路：
两个链表，建立一个新的头结点，每次比较两个链表当x较大小，那个小则头结点指向那个（尾插法），当前节点值小的链表则指向下一个节点，空间复杂度为O（1），没有用到额外的空间
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* preHead = new ListNode(-1);
ListNode* prev = preHead;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next; //尾插法
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev->next = (l1 == nullptr ? l2 : l1);
return preHead->next;
}
8.合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
多个链表升序，也才用合并两个链表的思路来，用一个临时链表ans来保存两个链表合并后的结果，然后遍历每一个有序链表
没有用到额外的空间，
ListNode* twoLists1(ListNode* l1, ListNode* l2) {
ListNode* preHead = new ListNode(-1);
ListNode* prev = preHead;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
prev->next = l1;
l1 = l1->next;
}
else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next; //尾插法
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev->next = l1 == nullptr ? l2 : l1; //三则表达式 如果l1为空了，则l2还有
return preHead->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode *ans = nullptr;
int len = lists.size();
for (int i = 0; i < len; i++){
ans = twoLists1(ans, lists[i]); //遍历每一个链表
}
return ans;
}
9.有效的括号 9. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
思路：
利用堆栈的特性（FIFO） ，遍历字符串每一个元素时，逐个入栈，一定是左括号的先入栈
遍历到右括号则检查栈的顶部是否匹配，匹配则出栈，为了方便建立对应 哈希表 方便判断出 左右括号是否匹配，
class Solution {
public:
bool isValid(string s) {
int x = 0, z = 0, d = 0;
int n = s.size();
if (s.size() % 2 != 0) //括号肯定为偶数
return false;
//建立无序表 逐一做匹配
unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
stack<char> stk;
for (auto ch : s) //遍历字符串元素
{
if (pairs.count(ch)) //判断改字符是否为右括号
{
if (stk.empty() || stk.top() != pairs[ch]) //若果栈空了或者栈顶的右括号和刚遍历的左括号不匹配则返回false
return false;
stk.pop(); //匹配成功则把出栈，把栈顶匹配完成的元素去掉
}
else {
stk.push(ch);//没有遍历到右括号则出栈
}
}
return stk.empty();
}
};
10. 斐波那契数列 10\. 斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
递归的接法：
将大问题分解成若干个小问题
F(5)= F(4)+F(3);
F(4)=F(3)+F(2)…..
以此类推
int fib(int n) {
if (n <= 0)
return 0;
if (n == 1)
return 1;
return fib(n - 1) + fib(n - 2);
}
非递归的接法（从下往上，求出每个数 ,时间复杂度 O(n)）
int fib_1(int n) {
int arr[2] = { 0,1 };
int pre = 0;
int now = 1;
int next = 0;
for (int i =2; i <= n; ++i)
{
next = pre + now; //用next 保留两个数相加的和
pre = now; //pre 和 now 变量向前推进
now = next;
}
return next;
}
也可以用以下的方法（和上面的思路一样，只是采用了数组的形式，很妙！）
int fib(int n) {
arr[2] = {0, 1};
for(int i = 2; i <= n; ++i) {
arr[i & 1] = (arr[0] + arr[1]) % (int)(1e9 + 7);
}
return arr[n & 1]; //n &1 的用意是： 定位到数组的小标 ， n&1 的值只能为 0 或 1
}
11.青蛙跳台阶（和斐波那契数列一样）
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
青蛙可以跳一步或者两步 顶一个函数 f（n） n表示台阶
跳第一个台阶的时候，有一种选择 f(1)，跳第二台阶的时候 f(2) ，有两种选择，跳第三个的时候，第二台阶到第三个台阶只有一种选择–跳一个；第一个台阶到第三台阶跳两个，需要考虑的是当前阶梯数 n 和 n -2 和n与n-2之间的的数目 f（n） = f（n-1） +f ( n -2 )
f(3) = f(2)+f(1) 这样就是斐波那契数列啦，可以用递归，但重复计算很多
int numWays(int n) {
if(n ==0)
return 1;
else if(n ==1)
return 1;
else if(n ==2)
return 2;
int pre = 1;
int now = 2;
int next = 0;
for (int i =3; i <= n; ++i)
{
next = (pre + now)%(int(1e9+7)); //用next 保留两个数相加的和
pre = now%(int(1e9+7)); //pre 和 now 变量向前推进
now = next%(int(1e9+7));
}
return next;
}
11.二分查找
二分查找是针对 有序数列 的，对无序数列是无效的，在有序序列中使用二分查找能大大提高查找效率，通常能将时间按复杂度从 O(n)降至O(logn)
eg:
在一个有序数组中查找某个元素的位置
- 递归
int find_gui(vector<int>& nums, int target, int l, int r)
{
int right = r;
int left = l;
int mid = left + (right - left) / 2;
if (right < left)
return -1;
if (nums[mid] < target)
se_gui(nums, target,mid + 1,r);
else if (nums[mid] > target)
se_gui(nums, target, l, mid- 1);
else if(nums[mid] == target)
return mid;
}
- 非递归
-
int search1(vector<int>& nums, int target) {
int len = nums.size() - 1;
int left = 0, right = len;
int mid;
while (left < right)
{
mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
else
return mid;
}
return -1;
}
相关题目：
在升序的序列中找到指定数字出现的次数
12.查找两个链表的相同节点（）
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
ListNode* At = headA;
ListNode* Bt = headB;
while (At!=Bt)
{
if (At != nullptr)
At = At->next;
else
At =headB;
if (Bt == nullptr)
Bt = Bt->next;
else
Bt = headA;
}
return Bt;
}
13.排序大总结
快排（被问了好几次…）
复杂度是O（nlogn）
思路是：
每一次的遍历把首元素放到他应该在的位置
如
5，1 ，4，3
5 的位置应该是 在四位的，第一轮目标就时要包5 放在第四位，其他的不用管
其它的数字 经过一轮的排序后，会以选定数字的为轴，大的右边，小的在左边；
以定位好的数字为轴，对左边的数字在重复一次以上的操作，对右边的也是，这就是用到递归了;
递归的层数越多是时间复杂度也越大， 平均的时间复杂度是 nO(logn)
n 代表层数， logn带边每层遍历的次数
vector<int> sortArray_1(vector<int>& nums) {
int high = nums.size() - 1;
QSort(nums, 0, high);
return nums;
}
void QSort(vector<int> &nums,int low,int high)
{
int mid;
if (low < high)
{
mid = Partition(nums, low, high);
QSort(nums, low, mid - 1); //递归左边的
QSort(nums, mid + 1,high); //递归右边的
}
}
int Partition(vector<int>& nums,int low,int high)
{
int r = high;
int l = low;
int std = nums[l]; //选定需要定位的目标数
while (l < r) //首尾各自开始向中心靠齐
{
//要从后面开始，判断数字是否大于目标数，知道遇到大于的
while (l < r && nums[r] >= std)
{
r--;
}
//然后交换数字
swap(nums[l], nums[r]);
//然后在来左边
while (l < r && nums[l] <= std)
{
l++;
}//同理
swap(nums[l], nums[r]);
}
return l;
}
14. 2n+1个数字，找出一个不对的数字 14\. 2n+1个数字，找出一个不对的数字
15.1000瓶药水有一瓶毒药，怎么快速检测出来（可用小白鼠）
讲一千瓶药水用二进制排序，2的10次方 为1024 故需要10位
00000 00000 1
00000 00001 2
00000 00010 3
…..
1111101000 1000
有10 位，我们用10只老鼠（每个老鼠都有编号 0-9）来检测， 瓶子序号中，第n位为1（n的取值为（0~9）） ，就用给对应编号为 n 的老鼠喝 如：
00001 00001 第0 位和第5位为1 ，则用调 编号 为 0 和 5的老去和药水
最后看是那些老鼠死了，死老鼠的序号，对应二进制的第几位，如 编号 二 和 三老鼠死了， 则二进制 为 0110 ，该编号对应的药水的编号，就是有毒的了
16.接雨水
给定 _n_ 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
思路：
- 暴力解法
判断每个柱子能否装水，得看柱子左右两边的柱子 ，水的高度取决于最短的
并且中间的柱子也有高度，所以也要减去当前柱子（即中间的柱子）的高度
每一个柱子 装水量为
s = min（left，right） - mid
总结： 遍历每一个柱子，取柱子左边最高的柱子，柱子右边最高的柱子，然后以左右两边最低的为标准来计算
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int ans = 0;
//遍历每一个柱子
for (int i = 1; i < n - 1; i++) {
int l_max = 0, r_max = 0;
// 找右边最高的柱子
for (int j = i; j < n; j++)
r_max = max(r_max, height[j]);
// 找左边最高的柱子
for (int j = i; j >= 0; j--)
l_max = max(l_max, height[j]);
// 如果自己就是最高的话，
// l_max == r_max == height[i]
ans += min(l_max, r_max) - height[i];
}
return ans;
}
};