文章目录
- 1.两数之和(hash)
- 2. 两数相加(链表)
- 3. 无重复字符的最长子串(滑动窗口双指针)
- 中间空缺的因为未保存丢失了,包括容器的知识,如二维数组,string、char等
- 6.Z 字形变换
- 7.整数反转
- 9.回文数
- 13.罗马数字转换
- 14.最长公共前缀
- 15. 三数之和(双指针)
- 16. 最接近的三数之和
- 17. 电话号码的字母组合
- 18. 四数之和
- 19. 删除链表的倒数第N个节点
- 20.有效的括号(堆栈的运用)
- 21.合并链表
- 22. 括号生成
- 23. 合并K个排序链表
- 26. 删除排序数组中的重复项
- 27. 移除元素
- 31. 下一个排列
- 33. 搜索旋转排序数组
- 34. 在排序数组中查找元素的第一个和最后一个位置
- 35. 搜索插入位置(二分法***************)
- 36. 有效的数独
- 36. 有效的数独
- 39. 组合总和
- 41. 缺失的第一个正数
- 42. 接雨水
- 43. 字符串相乘
- 44. 通配符匹配
- 45. 跳跃游戏 II
- 46. 全排列
- 48. 旋转图像
- 49. 字母异位词分组
- 50. Pow(x, n)
- 51. N皇后(回溯dfs)
- 53. 最大子序和(贪心)
- 55. 跳跃游戏
- 56. 合并区间(贪心)
- 57. 插入区间
- 62. 不一样路径(dp)
- 64. 最小路径和(dp)
- 69. x 的平方根(二分法)
- 70. 爬楼梯(dp)
- 72. 编辑距离
- 73. 矩阵置零
- 75. 颜色分类(三数快排)
- 74. 搜索二维矩阵
- 77. 组合
- 78. 子集
- 79. 单词搜索
- 80. 删除排序数组中的重复项 II
- 81. 搜索旋转排序数组 II
- 88. 合并两个有序数组
- 91.
- 94. 二叉树的中序遍历
- 95. 不一样的二叉搜索树 II
- 97. 交错字符串
- 98. 验证二叉搜索树(dfs)
- 100. 相同的树
- 101. 对称二叉树
- 102. 二叉树的层序遍历
- 103. 二叉树的锯齿形层次遍历
- 104. 二叉树的最大深度(***********)
- 105. 从前序与中序遍历序列构造二叉树
- 106. 从中序与后序遍历序列构造二叉树
- 107. 二叉树的层次遍历 II
- 108. 将有序数组转换为二叉搜索树(****)
- 109. 有序链表转换二叉搜索树
- 110. 平衡二叉树
- 111. 二叉树的最小深度
- 112. 路径总和
- 113. 路径总和 II
- 114. 二叉树展开为链表
- 115. 不一样的子序列
- 116. 填充每一个节点的下一个右侧节点指针(bfs)
- 117. 填充每一个节点的下一个右侧节点指针 II(bfs)
- 118. 杨辉三角
- 119. 杨辉三角 II
- 121. 买卖股票的最佳时机(dp)
- 122. 买卖股票的最佳时机 II
- 123. 买卖股票的最佳时机 III
- 124. 二叉树中的最大路径和(dfs,不懂)
- 128. 最长连续序列
- 129. 求根到叶子节点数字之和
- 130. 被围绕的区域
- 144. 二叉树的前序遍历
- 146. LRU缓存机制
- 150. 逆波兰表达式求值
- 152. 乘积最大子数组(dp)
- 153. 寻找旋转排序数组中的最小值
- 155. 最小栈
- 162. 寻找峰值
- 169. 多数元素
- 179. 最大数
- 189. 旋转数组
- 198. 打家劫舍(dp)
- 199. 二叉树的右视图
- 200. 岛屿数量
- 205. 同构字符串(哈希表)
- 209. 长度最小的子数组(滑动窗口)
- 213. 打家劫舍 II
- 217. 存在重复元素
- 226. 翻转二叉树(dfs)
- 232. 用栈实现队列
- 238. 除自身之外数组的乘积
- 239. 滑动窗口最大值
- 257. 二叉树的全部路径
- 268. 缺失数字
- 275. H指数 II
- 278. 第一个错误的版本(二分法)
- 283. 移动零
- 287. 寻找重复数
- 290. 单词规律
- 300. 最长上升子序列
- 303. 区域和检索 - 数组不可变
- 322. 零钱兑换
- 324. 摆动排序 II
- 343. 整数拆分
- 344. 反转字符串
- 347. 前 K 个高频元素(sort排序)
- 349. 两个数组的交集
- 350. 两个数组的交集 II
- 354. 俄罗斯套娃信封问题(最大递增子序列)
- 373. 查找和最小的K对数字(堆排序(优先队列)****************)
- 374. 猜数字大小(二分法)
- 377. 组合总和 Ⅳ(dfs,dp)
- 383. 赎金信
- 392. 判断子序列
- 401. 二进制手表
- 413. 等差数列划分(dp)
- 416. 分割等和子集(背包问题)
- 417. 太平洋大西洋水流问题
- 442. 数组中重复的数据
- 435. 无重叠区间(贪心)
- 448. 找到全部数组中消失的数字
- 451. 根据字符出现频率排序(sort重写****************)
- 452. 用最少数量的箭引爆气球
- 454. 四数相加 II(哈希取数**********)
- 474. 一和零(背包)
- 494. 目标和
C++版的leetcode,从头再来!java
1.两数之和(hash)
下面这个代码在return的时候一直遇到问题:node
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int length = sizeof(nums)/sizeof(nums[0]);
for(int i = 0;i < length;++i)
for(int j = 0; j<length;++i)
if (nums[i] + nums[j] == target)
{
return {nums[i],nums[j]};
}
}
};
后来改正的:python
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int length = nums.size();
vector<int> ans;
for(int i = 0;i < length;i++)
for(int j = i + 1; j<length;j++)
if (nums[i] + nums[j] == target)
{
ans.push_back(i);
ans.push_back(j);
return ans;
}
return ans;
}
};
几点说明:
1.一个函数是必须有返回值的,若是只有if里加了return,当出现else的 状况这个函数就没有了,因此要加else,要么最后加return也行;
2.返回一个列表时,能够定义一个容器来装
3.计算数组长度用size()函数;
用暴力法就没有意义了,测试用例必定后面的过不了
一开始想对数组进行排序,这样能够极大程度的进行剪枝,可是排序以后丢失了原有的下标,若是返回的是元素不是下标的话这样就是可行的,可是下标不能用这种方法
哈希表的方法:ios
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> m;
for(int i=0;i<nums.size();i++)
m[nums[i]] = i; //向map中添加元素
for(int i=0;i<nums.size();i++)
{
if(m.find(target-nums[i]) != m.end() && m[target-nums[i]] != i) //若是m中存在对应的键值,而且不为i,后面这个条件很重要,由于会有重复的元素
return {i , m[target-nums[i]]};
}
return {};
}
};
做者:zrita
连接:https://leetcode-cn.com/problems/two-sum/solution/c-san-chong-fang-fa-jian-dan-yi-dong-ji-bai-100-z-/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
2. 两数相加(链表)
能够说有思路,先补齐不齐的,而后再添加到新的链表中,最后考虑进位,可是代码过长既浪费时间又容易出错git
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* temp1 = l1;
int len1 = 0;
while(temp1)
{
temp1 = temp1->next;
len1++;
}
ListNode* temp2 = l2;
int len2 = 0;
while(temp2)
{
temp2 = temp2->next;
len2++;
}
temp1 =l1;
while(temp1->next)
{
temp1 = temp1->next;
}
temp2=l2;
while(temp2->next)
{
temp2=temp2->next;
}
while(len1 <len2)
{
ListNode* zero = new ListNode(0);
temp1->next=zero;
temp1 = zero;
len1++;
}
while(len2<len1)
{
ListNode* zero = new ListNode(0);
temp2->next = zero;
temp2 = zero ;
len2++;
}
ListNode* head = new ListNode(l1->val+l2->val);
ListNode* temp = head;
temp1=l1;
temp1 = temp1->next;
temp2=l2;
temp2 = temp2->next;
while(len1-1)
{
ListNode* cur = new ListNode(temp1->val+temp2->val);
temp1=temp1->next;
temp2=temp2->next;
temp->next = cur;
temp = cur;
len1--;
}
temp = head;
while(temp->next)
{
if(temp->val>=10)
{
temp->val -=10;
temp->next->val +=1;
}
temp =temp->next;
}
if(temp->val>=10)
{
ListNode* zero = new ListNode(1);
temp->val -=10;
temp->next = zero;
}
return head;
}
};
相同的思路更简洁的代码
里面值得学习的地方是新建一个头节点,可是不许备放在终链表中,这样不用再把中间过渡的一些代码写出来
还有就是新建节点的时候直接new就能够的web
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int len1=1;//记录l1的长度
int len2=1;//记录l2的长度
ListNode* p=l1;
ListNode* q=l2;
while(p->next!=NULL)//获取l1的长度
{
len1++;
p=p->next;
}
while(q->next!=NULL)//获取l2的长度
{
len2++;
q=q->next;
}
if(len1>len2)//l1较长,在l2末尾补零
{
for(int i=1;i<=len1-len2;i++)
{
q->next=new ListNode(0);
q=q->next;
}
}
else//l2较长,在l1末尾补零
{
for(int i=1;i<=len2-len1;i++)
{
p->next=new ListNode(0);
p=p->next;
}
}
p=l1;
q=l2;
bool count=false;//记录进位
ListNode* l3=new ListNode(-1);//存放结果的链表
ListNode* w=l3;//l3的移动指针
int i=0;//记录相加结果
while(p!=NULL&&q!=NULL)
{
i=count+p->val+q->val;
w->next=new ListNode(i%10);
count=i>=10?true:false;
w=w->next;
p=p->next;
q=q->next;
}
if(count)//若最后还有进位
{
w->next=new ListNode(1);
w=w->next;
}
return l3->next;
}
};
做者:chenlele
连接:https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-gpe3dbjds1/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
3. 无重复字符的最长子串(滑动窗口双指针)
用了带剪枝的暴力法,每次维护一个set,可是最后仍是超时了算法
class Solution {
public:
int lengthOfLongestSubstring(string s) {
//遍历确定不行,子串表示要连续
//尝试双指针遍历加剪枝
if(s.empty())return 0;
if(s.size()==1)return 1;
int len = s.size();
int max = 1;
for(int i= 0 ; i<len ; i++)
{
set<int> st;
st.insert(s[i]);
for(int j = i+1; j<len ;j++)
{
int k = st.size();
st.insert(s[j]);
if(st.size()==k) break;
if(st.size()>max)max=st.size();
}
}
return max;
}
};
对于字符串的题,最容易出现的就是超时,而这是更好的办法每每是哈希表法docker
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
//s[start,end) 前面包含 后面不包含
int start(0), end(0), length(0), result(0);
int sSize = int(s.size());
unordered_map<char, int> hash;
while (end < sSize)
{
char tmpChar = s[end];
//仅当s[start,end) 中存在s[end]时更新start
if (hash.find(tmpChar) != hash.end() && hash[tmpChar] >= start)
{
start = hash[tmpChar] + 1;
length = end - start;
}
hash[tmpChar] = end;
end++;
length++;
result = max(result, length);
}
return result;
}
};
做者:pinku-2
连接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-cshi-xian-/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
双指针法可使用滑动窗口法,每次要找到是哪里多出来了,再从这个地方开始数组
class Solution
{
public:
// 在左闭右开[left,right)的字符串s中,找字符target对应的下标位置,若未找到,则返回-1
int getThePosOfSame(int left, int right, const string& s, char target) const
{
for (int i = left; i < right; i++)
{
if (s[i] == target)
{
return i;
}
}
return -1;
}
int lengthOfLongestSubstring(string s)
{
const int len = s.length();
int max_len = 0;
int i = 0;
int j = 0;
while (j < len)
{
int pos = getThePosOfSame(i, j, s, s[j]);
if (pos == -1)
{
j++;
}
else
{
max_len = (j - i) > max_len ? (j - i) : max_len;
i = pos + 1;
}
}
max_len = (j - i) > max_len ? (j - i) : max_len;
return max_len;
}
};
做者:hui-mao-zi-2
连接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-dong-chuang-kou-by-hui-mao-zi-2/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
本身的写的滑动窗口,要特别注意对数组的维护和每次更替时i和j的值缓存
class Solution {
public:
int lengthOfLongestSubstring(string s) {
//遍历确定不行,子串表示要连续
//尝试双指针遍历加剪枝
if(s.empty())return 0;
if(s.size()==1)return 1;
int len = s.size();
int max = 1;
int i = 0;
int j = 1;
vector<char> temp;
temp.push_back(s[0]);
while(i<len && j<len)
{
if( find(temp.begin(),temp.end(),s[j])==temp.end() )
{
temp.push_back(s[j]);
j++;
if(temp.size()>max)max =temp.size();
}
else
{
int k = find(temp.begin(),temp.end(),s[j])-temp.begin();
i = i+k+1;
j=i+1;
temp.clear();
temp.push_back(s[i]);
}
}
return max;
}
};
中间空缺的因为未保存丢失了,包括容器的知识,如二维数组,string、char等
6.Z 字形变换
拿到题目以后的思路:
1.每行须要创建一个容器存放值
2.可是因为行数是题目给定的,并非常量,因此只能先创建一个二维矩阵,行数就是题目的行数
3.设置在到达边界是当即返回,这个地方还想的不是很清楚
4.可想而知会很是复杂
官方解答:
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
vector<string> rows(min(numRows, int(s.size())));
int curRow = 0;
bool goingDown = false;
for (char c : s) {
rows[curRow] += c;
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}
string ret;
for (string row : rows) ret += row;
return ret;
}
};
做者:LeetCode
连接:https://leetcode-cn.com/problems/zigzag-conversion/solution/z-zi-xing-bian-huan-by-leetcode/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
首先因为是字符串型,没必要设置char型的二维矩阵而是直接设置一维而后进行拼接就好了,其次,对于到终点就返回的一个要求,就简单定义一个变量,从上到下时每次变量加1,从下到上每次变量键1,能够设置一个bool开关,做为加一和减一的标志,以前想的堆栈什么都太复杂了,虽然容器好用,可是能用一维的就不用二维,能用一两个指针或者变量的就不用堆栈
7.整数反转
class Solution {
public:
int reverse(int x) {
int p = 10;
int n;
long result = 0;
if(x == INT_MIN)
{
return 0;
}
if (x >= 0)
{
while(x > 0)
{
n = x % p;
x = x / p;
result = result*10 + n;
}
if(result > INT_MAX)
{
return 0;
}
return result;
}
else
{
int y = -x;
while(y > 0)
{
n = y % p;
y = y / p;
result = result*10 + n;
}
if(result > INT_MAX)
{
return 0;
}
return -result;
}
}
};
几点说明:
1.INT_MIN ,INT_MAX第一次见
INT_MAX = 2^31-1
INT_MIN= -2^31
另外为了防止result直接溢出了先试用long类型(8字节)进行定义!
2.反转后不用放到容器里而是分离的时候能够直接构成反转数;
3.遇到正反两种状况时不须要分两大类,而是在开头转换就能够,使用一次递归,以下所示
class Solution
{
public:
int reverse(int x)
{
long result(0); //利用long避免溢出
if (x == INT_MIN)
{
return 0;
}
if (x < 0)
{
return -reverse(-x);//当x小于0,再次调用该函数解出x大于0的状况,结果加负号返回
}
int digit(0);
while (x > 0)
{
digit = x % 10;
x /= 10;
result = result * 10 + digit;//这里能够直接返回
}
if (result > INT_MAX)
{
return 0;
}
return int(result);
}
};
做者:pinku-2
连接:https://leetcode-cn.com/problems/reverse-integer/solution/zheng-shu-fan-zhuan-cshi-xian-liang-chong-jie-fa-z/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
class Solution {
public:
int reverse(int x) {
int rev = 0;
while (x != 0) {
int pop = x % 10;
x /= 10;
if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
rev = rev * 10 + pop;
}
return rev;
}
};
做者:LeetCode
连接:https://leetcode-cn.com/problems/reverse-integer/solution/zheng-shu-fan-zhuan-by-leetcode/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
9.回文数
这里使用了整数反转的思路,直接比对反转后是否相等就知道是不是回文数;
另外,为了防止超范围,result可使用类型long;
另外,数字和字符串转换不如算法方式好;
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0){return false;}
else
{
long result = 0;
int y = x;
int n = 0;
while(x > 0)
{
n = x % 10;
x = x / 10;
result = result*10 + n;
}
if (result == y){return true;}
else{return false;}
}
}
};
看到一种新写法
return (x==n) ? true : false;
可代替原来的代码为
return (result == y) ? true: false;
13.罗马数字转换
这则代码在map的使用上花费了较多时间,s是string字符串,s[0]能够去除字符串的第一个元素,可是必定不能使用luoma[“s[0]”]去提取值,由于s[0]这里不会进行编译的!因此要提取的话要找自己就是string类型的,而s.substr(n,m)能够作到这一点,n表明起始位置,m表明提取的个数,将其放入luoma[]中能够提取到想要的value。
#include <map>
#include <iostream>
using namespace std;
class Solution {
public:
int romanToInt(string s) {
int length = s.size();
std::map<string,int> luoma;
luoma.insert(pair<string,int>("I",1));
luoma.insert(pair<string,int>("V",5));
luoma.insert(pair<string,int>("X",10));
luoma.insert(pair<string,int>("L",50));
luoma.insert(pair<string,int>("C",100));
luoma.insert(pair<string,int>("D",500));
luoma.insert(pair<string,int>("M",1000));
long result = 0;
if (length >1)
{
for (int i = 0;i < length-1; i++ )
{
if(luoma[s.substr(i,1)] >= luoma[s.substr(i+1,1)])
{
result = result + luoma[s.substr(i,1)];
}
else
{
result = result - luoma[s.substr(i,1)];
}
}
result = result + luoma[s.substr(length-1,1)];
}
else{
result = luoma[s.substr(0)];
}
return result;
}
};
官方的
class Solution {
public:
int romanToInt(string s) {
unordered_map<string, int> m = {{"I", 1}, {"IV", 3}, {"IX", 8}, {"V", 5}, {"X", 10}, {"XL", 30}, {"XC", 80}, {"L", 50}, {"C", 100}, {"CD", 300}, {"CM", 800}, {"D", 500}, {"M", 1000}};
int r = m[s.substr(0, 1)];
for(int i=1; i<s.size(); ++i){
string two = s.substr(i-1, 2);
string one = s.substr(i, 1);
r += m[two] ? m[two] : m[one];
}
return r;
}
};
做者:QQqun902025048
连接:https://leetcode-cn.com/problems/roman-to-integer/solution/2-xing-python-on-by-knifezhu/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
map:
优势:
有序性,这是map结构最大的优势,其元素的有序性在不少应用中都会简化不少的操做
红黑树,内部实现一个红黑书使得map的不少操做在lgn的时间复杂度下就能够实现,所以效率很是的高
缺点: 空间占用率高,由于map内部实现了红黑树,虽然提升了运行效率,可是由于每个节点都须要额外保存父节点、孩子节点和红/黑性质,使得每个节点都占用大量的空间
适用处:对于那些有顺序要求的问题,用map会更高效一些
unordered_map:
优势: 由于内部实现了哈希表,所以其查找速度很是的快
缺点: 哈希表的创建比较耗费时间
适用处:对于查找问题,unordered_map会更加高效一些,所以遇到查找问题,常会考虑一下用unordered_map
14.最长公共前缀
整体来讲思路难度不大,
1.要注意函数可能没有返回值的状况
2.要求一个公共最小长度,不必定非要建出容器而后求最小值,能够直接在求每一个值的时候顺带求出最小值
3.substr函数仍是很好用的,主要是还能指定输出的个数
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int a = strs.size();
if (a == 0)
{
return "";
}
else if (a == 1)
{
return strs[0];
}
else
{
int aamin = strs[0].size();
for(int i = 1; i <a ; i++)
{
if(aamin > strs[i].size()){aamin = strs[i].size();}
}
for (int i = 0; i < aamin; i++ )
{
for (int j = 0; j< a; j++)
{
if (strs[0].substr(i,1) != strs[j].substr(i,1))
{
return strs[0].substr(0,i);
}
}
}
return strs[0].substr(0,aamin);
}
}
};
基本同样,不过其并无使用substr函数
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.size()==0)
return "";
string str="";
int min_lenth=strs[0].size();
for(int i=1;i<strs.size();i++)
{
if(min_lenth>=strs[i].size())
min_lenth=strs[i].size();
}
for(int k=0;k<min_lenth;k++)
{
char s=strs[0][k];
for(int j=1;j<strs.size();j++)
{
if(s!=strs[j][k])
return str;
}
str+=s;
}
return str;
}
};
15. 三数之和(双指针)
直接暴力法,必定是不可取的
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//没有好的办法,双指针不行,矩阵不行,贪心不行
//二维数组
int len = nums.size();
//vector<vector<int> > myvec(len, vector<int>(nums,0));
set<multiset<int> > res;
for (int i = 0; i<len; i++)
{
for(int j= i+1; j<len ; j++)
{
for (int c=j+1 ;c<len; c++)
{
//if (c==i || c==j){continue;}
if ((nums[i]+nums[j]+nums[c])==0)
{
multiset<int> x;
x.insert(nums[i]);
x.insert(nums[j]);
x.insert(nums[c]);
res.insert(x);
}
}
}
}
vector<vector<int> > re;
for(auto i:res)
{
vector<int> x;
for(auto j:i)
{
x.push_back(j);
}
re.push_back(x);
}
//vector<vector<int> > re = res;
return re;
}
};
再暴力法上加了剪枝,可是仍是超时了,说明这种方法是不行的
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int len = nums.size();
if(len<3)return {};
sort(nums.begin(),nums.end());
int i = 0 ;
int j = 1 ;
int l = 2;
set<vector<int>> res;
for(int i = 0 ; i<len ;i++)
{
if(nums[i]>0) break;//直接中止循环
if(nums[i]+nums[len-2]+nums[len-1]<0)continue;//直接跳过这次循环
for(int j = i+1;j<len ;j++)
{
if(nums[i]+nums[j]+nums[len-1]<0)continue;//跳过这次循环
for(int k = j+1 ; k<len ;k++)
{
if(nums[i]+nums[j]+nums[k]==0)
{
vector<int> temp = {nums[i],nums[j],nums[k]};
res.insert(temp);
//为了防止又相同值这里不能中止
}
if(nums[i]+nums[j]+nums[k]>0) break;//后面的k也都不行了
}
}
}
vector<vector<int>> r(res.begin(),res.end());
return r;
}
};
正确的作法,双指针法,一个在前一个在后,寻找0-nums[i]的两个值,特别适用于已经排序的数组,要记住排序以后数组常用 一前一后的双指针法
class Solution
{
public:
vector<vector<int>> threeSum(vector<int> &nums)
{
vector<vector<int>> result;
int vecSize = int(nums.size());
if (vecSize <= 2)
{
return result;
}
int possibleSize = vecSize - 2;
sort(nums.begin(), nums.end());
for (int index = 0; index < possibleSize; index++)
{
int intNow = nums[index];
if(intNow > 0){
break;
}
int negativeNow = 0 - intNow;
int lo = index + 1;
int hi = vecSize - 1;
while (lo < hi)
{
int intLo = nums[lo];
int intHi = nums[hi];
if (intLo + intHi == negativeNow)
{
vector<int> tmpVec{intNow, intLo, intHi};
result.push_back(tmpVec);
//去重
while (lo < hi && nums[lo] == intLo)
{
lo++;
}
while (lo < hi && nums[hi] == intHi)
{
hi--;
}
}
else if (intLo + intHi < negativeNow)
{
lo++;
}
else if (intLo + intHi > negativeNow)
{
hi--;
}
}
//去重
while (index + 1 < possibleSize && nums[index] == nums[index + 1])
{
index++;
}
}
return result;
}
};
做者:pinku-2
连接:https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-cshi-xian-shuang-zhi-zhen-fa-tu-shi/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
本身写的,勉强不超时,考虑多是去重那里费了比较多功夫
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int len = nums.size();
int k=0, i=1,j = len-1;
sort(nums.begin(),nums.end());
vector<vector<int>> res;
while(k<=len-3)
{
if(nums[k]+nums[k+1]+nums[k+2]>0)break;
if(nums[k]+nums[k+1]+nums[k+2]==0)
{ vector<int> temp={nums[k],nums[k+1],nums[k+2]};
res.push_back(temp);break;};
//if(nums[k]+nums[i]+nums[j]>0){k++;i=k+1;j=len-1;continue;}
if(nums[k]+nums[j-1]+nums[j]<0){k++;i=k+1;j=len-1;continue;}
while(i<j)
{
if(nums[i]+nums[j]==-nums[k])
{
vector<int> temp={nums[k],nums[i],nums[j]};
res.push_back(temp);
i++;j--;
}
else if(nums[i]+nums[j]>-nums[k])
{
j--;
}
else
{
i++;
}
}
k++;
i=k+1;
j=len-1;
}
set<vector<int>> r(res.begin(),res.end());
res.assign(r.begin(),r.end());
return res;
}
};
16. 最接近的三数之和
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int len = nums.size();
int k=0,i=1,j=len-1;
sort(nums.begin(),nums.end());
int res = 1e6;
if(nums[0]+nums[1]+nums[2]>target) return nums[0]+nums[1]+nums[2];
if(nums[len-3]+nums[len-2]+nums[len-1]<target) return nums[len-3]+nums[len-2]+nums[len-1];
while(k<=len-3)
{
if(nums[k]+nums[k+1]+nums[k+2]>target)
return abs(res-target)<abs(nums[k]+nums[k+1]+nums[k+2]-target)?res:nums[k]+nums[k+1]+nums[k+2];
while(i<j)
{
if(nums[k]+nums[i]+nums[j]==target)return target;
else if(nums[k]+nums[i]+nums[j]>target)
{
res = abs(res-target)<abs(nums[k]+nums[i]+nums[j]-target)?res:nums[k]+nums[i]+nums[j];j--;
}
else
{
res =abs(res-target)<abs(nums[k]+nums[i]+nums[j]-target)?res:nums[k]+nums[i]+nums[j];i++;
}
}
k++;
i=k+1;
j=len-1;
}
return res;
}
};
17. 电话号码的字母组合
怎么排列出全部的状况,时最难的地方
string str;
str = str + 'm' + "m" + to_string(m)+char(m) + char(m+'0') ;
字符串拼接,加号也行,单双引号都能拼,整型用to_string
这题能使用递归,可是很差理解,这个队列的思想很是实用,很是像二叉树层序遍历的过程!先遍历第一曾(单个的),每个生成一个组合再放到队列末尾,而这个弹出,像极了把子节点放入队列后面,而后将此节点弹出的过程
队列是有效的一种遍历手段
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> res;//用于输出向量
map<char, string> m = { {'2',"abc" },{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"} };//映射map哈希表
int size = digits.size();//输入字符串产长度
queue<string> que;//新建队列
//先将第一个元素对应的码表入队
for (int j = 0; j < m[digits[0]].size(); j++)
{
string str;
str.push_back(m[digits[0]][j]);//char转string
que.push(str);//string入队,分别将'a','b','c'入队列
}
string s;//用于存储队头元素
for (int i = 1; i < size; i++)//对剩下的第二个开始进行遍历,每一都会组成新的字符串放入队列,而后将此弹出
{
int length = que.size();//当前队列长度,这时的队列存放的是上一层全部的字符串,以前的都弹掉了,对于里面的每一个,都须要新的组合进入队尾,再弹出这个
while (length--)//
{
for (int j = 0; j < m[digits[i]].size(); j++)
{
s = que.front();
s = s + m[digits[i]][j];//队头元素加上新元素
que.push(s);//入队
}
que.pop();//队头出队
}
}
while (!que.empty())
{
res.push_back(que.front());//队头元素存储至res
que.pop();//队头出队
}
return res;//返回
}
};
做者:su-ge
连接:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/c-dui-lie-jian-dan-shi-xian-yi-dong-by-su-ge/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
套用递归模板能够写出递归
class Solution {
private:
vector<string> res;
string path;
int len;
public:
void dfs(unordered_map<char,string> mymap, int pos, string digits)
{
if(pos == len)
{
res.push_back(path);
}
for(auto i:mymap[digits[pos]])
{
path = path+ i;
dfs(mymap,pos+1,digits);
path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.empty())return res;
len = digits.size();
unordered_map<char,string> mymap{{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
dfs(mymap,0,digits);
return res;
}
};
18. 四数之和
借鉴以前三数之和的双指针法,能作可是计算量大
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
int len = nums.size();
int i = 0, j = 1, k1= 2,k2= len-1;
set<vector<int> > res;
while(i< len-3 )
{
while(j<len-2)
{
while( k1<k2)
{
int temp = nums[i]+nums[j]+nums[k1]+nums[k2];
if (temp == target)
{
vector<int> vec ={nums[i], nums[j], nums[k1],nums[k2]};
res.insert(vec);
k1++;
}
else if (temp > target){k2--;}
else {k1++;}
}
j++;
k1 = j+1;
k2 = len-1;
}
i++;
j=i+1;
k1=j+1;
k2=len-1;
}
vector<vector<int> > re;
for (auto i :res)
{
re.push_back(i);
}
return re;
}
};
这样的方法可行,在这个方法上能够有更优化的办法,以前有特殊状况0,因此即判断第一个指针值的大小和0的关系就好了,可是当target不为0时不能这样简单的判断,由于0如下的值越加越小,0以上的值越加越大,因此能够换个稍微复杂的验证方式,假设头节点是p,若是p和右边的三个的和都大于target,就不必了,能够中止循环,由于还会大于target,若是p和最后三位的加和还小于target的话,那么就说明这个p不可能组成,直接计算p+1的状况
指针依次是 p,k,i,j,若是 nums[p] + 3 * nums[p + 1] > target,由于 nums 按升序排列,因此以后的数确定都大于 target ,直接 break;
若是 nums[p] + 3 * nums[-1] < target,那么当前的 nums[p] 加其他三个数必定小于 target,故 p 直接下一位便可,continue;
做者:z1m
连接:https://leetcode-cn.com/problems/4sum/solution/shuang-zhi-zhen-gao-su-jie-fa-by-ml-zimingmeng/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
第二次写的加入剪枝的操做
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int len = nums.size();
int k=0,l=1,i=2,j=len-1;
sort(nums.begin(),nums.end());
set<vector<int>> res;
while(k<=len-4)
{
if(nums[k]+nums[k+1]+nums[k+2]+nums[k+3]>target)break;
if(nums[k]+nums[j-2]+nums[j-1]+nums[j]<target){k++;l=k+1;i=k+2;j=len-1;continue;}
while(l<=len-3)
{
if(nums[k]+nums[l]+nums[l+1]+nums[l+2]>target)break;
if(nums[k]+nums[l]+nums[j-1]+nums[j]<target){l++;i=l+1;j=len-1;continue;}
while(i<j)
{
if(nums[k]+nums[l]+nums[i]+nums[j]==target)
{
vector<int> temp={nums[k],nums[l],nums[i],nums[j]};
res.insert(temp);i++;j--;
}
else if(nums[k]+nums[l]+nums[i]+nums[j]>target)
{
j--;
}
else
{
i++;
}
}
l++;i=l+1;j=len-1;
}
k++;
l=k+1;
i=l+1;
j=len-1;
}
vector<vector<int>> r(res.begin(),res.end());
return r;
}
};
19. 删除链表的倒数第N个节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
int len=0;
ListNode* temp = head;
while(temp!=nullptr)
{
len++;
temp = temp->next;
}
if(len==1){return NULL;}
else if (len==n){head = head->next;}
else
{
temp =head;
for(int i= 0;i<len-n-1;i++)
{
temp=temp->next;
}
temp ->next = temp ->next->next;
}
return head;
}
};
思想是找到该节点的前一个节点,可是要注意特殊状况,即删除的是第一个节点的状况,这种状况下会没有前一个节点
双指针,当快的前进n时,慢的开始;当快的到结尾时,慢的正好到能够删除的那个节点前一个,对于一维方向上的问题,双指针能够解决绝大数
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(NULL);
dummy->next = head; //添加头节点,便于操做
ListNode* slow=dummy,* fast=dummy;
int distance=0;
while(fast->next){
if(distance<n){
fast=fast->next;
distance++;
}else{
fast=fast->next;
slow=slow->next;
}
}
slow->next=slow->next->next;
return dummy->next;
}
};
做者:zgdgod
连接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/c-by-zgdgod-4/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
20.有效的括号(堆栈的运用)
有效运用了break和continue:一个是当即退出当前循环,一个是结束本次循环;
class Solution {
public:
bool isValid(string s) {
int length = s.size();
if (length % 2 == 1)
{
return false;
}
else
{
map <string ,int> fuhao = {{"(",1}, {")",-1}, {"[",2}, {"]",-2}, {"{",3}, {"}",-3}};
while((s.size()) > 0)
{
length = s.size();
for(int i = 0; i < s.size()-1; i++)
{
if ( fuhao[s.substr(i,1)] == - fuhao[s.substr(i+1,1)])
{
s.erase(i,2);
break;
}
}
if(length == 0)
{
return true;
}
else if (length == s.size())
{
return false;
}
else
{
continue;
}
}
return (s.size() == 0) ? (true) : (false);
}
}
};
思路:对于字符串s
若下一个字符是左括号:则任务数量task+1,且将须要匹配的右括号数字添加至key容器;
若下一个字符是右括号:
一、如果key容器中最后一个数字对应的右括号,则任务数量task-1,移除容器最后一项;
二、若不是key容器中最后一个数字对应的右括号,则直接结束,返回False。
知识点:
1.for(auto i : s)遍历s中的全部字符、元素,甚至可使用自动类型推断,一个冒号就解决了,实用性很大!
2.vector.empty()与
if (vector.size() == 0 ){return true}
else {return false} 的效果更简洁,若是要反着来能够在前面加一个!
3.对于s中的每个符号,若是是左半边,就把这个推动容器;若是是右半边,此时若容器为空则说明以前没有左半边入栈,则false,若是容器不为空继续,把容器最后一个左半括号提取出来,若是此右半边和这个括号不匹配,则false,若是匹配则弹出此左半括号,继续下去,所有走完后,直接用空就表明是否所有匹配,一语双关!
class Solution {
public:
bool isValid(string s) {
if(s.size() % 2) return false;
vector<char> vecStack;//字符型的容器
char c;
//对于s中的每个符号,若是是左半边,就把这个推动容器;若是是右半边,此时若容器为空则说明以前没有左半边入栈,则false,若是容器不为空继续,把容器最后一个左半括号提取出来,若是此右半边和这个括号不匹配,则false,若是匹配则弹出此左半括号,继续下去,所有走完后,直接用空就表明是否所有匹配,一语双关!
for(auto i : s) {
if(i == '}' || i == ')' || i== ']') {
if (!vecStack.empty()) c = vecStack[vecStack.size()-1];
else return false;
if(i == '}' && c != '{') return false;
if(i == ')' && c != '(') return false;
if(i == ']' && c != '[') return false;
vecStack.pop_back();
}
else vecStack.push_back(i);
}
return vecStack.empty();
}
};
做者:wallcwr
连接:https://leetcode-cn.com/problems/valid-parentheses/solution/jing-dian-jian-dan-de-zhan-wen-ti-by-wallcwr/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
本身又写了一遍,发现一个问题:必须是单引号才行,双引号就不行——单引号字符,双引号字符串
class Solution {
public:
bool isValid(string s) {
vector <char> kuohao;
if (s.size() % 2 == 1) return false;
for (auto str : s)
{
if ((str == '{') || (str == '[') || (str == '('))
{
kuohao.push_back(str);
}
else
{
if(kuohao.size() == 0) return false;
if (str == '}' && kuohao[kuohao.size()-1] == '{')
{
kuohao.pop_back();
continue;
}
else if (str == ']' && kuohao[kuohao.size()-1] == '[')
{
kuohao.pop_back();
continue;
}
else if (str == ')' && kuohao[kuohao.size()-1] == '(' )
{
kuohao.pop_back();
continue;
}
else
{
return false;
}
}
}
return kuohao.empty();
}
};
在C++中单引号表示字符,双引号表示字符串。
例如 :在定义一个数组的时候string a [5]={“nihao”,“henhao”,“good”,“en”,“h”};
定义的是一个字符串数组,这是字符串元素要用双引号。
char b[5]={‘a’,‘b’,‘c’,‘d’,‘e’};
定义的是一个字符数组,元素要用单引号。
要注意元素的输出不一样:
int a=10;
cout<<“a”;输出为 字符a;这就是上次“s[0]”中不能再编译s[0]的缘由,可是若是是单引号没准能编译
cout<<a;输出为10;
cout<<‘a’ ;输出为65;
21.合并链表
思路正确,但就是代码有些复杂
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode(0);
ListNode* res = head;
ListNode* temp1 = l1;
ListNode* temp2 = l2;
while(temp1!= nullptr && temp2!= nullptr)
{
while (temp1 != nullptr && temp1->val <= temp2->val)
{
ListNode* temp = new ListNode(temp1->val);
res->next = temp;
res = temp;
temp1 = temp1->next;
}
while (temp1 != nullptr&&temp2 != nullptr && temp1->val > temp2->val)
{
ListNode* temp = new ListNode(temp2->val);
res->next = temp;
res = temp;
temp2 = temp2->next;
}
}
while (temp1!=nullptr)
{
ListNode* temp = new ListNode(temp1->val);
res->next = temp;
res= temp;
temp1=temp1->next;
}
while(temp2!=nullptr)
{
ListNode* temp = new ListNode(temp2->val);
res->next =temp;
res= temp;
temp2=temp2->next;
}
return head->next;
}
};
#include <vector>
using namespace std;
/**
* Definition for singly-linked list.
*/
struct ListNode//链表的结构体
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
ListNode *result = new ListNode(-1); //哑节点简化代码
ListNode *workNode = result;
while (l1 != nullptr && l2 != nullptr) //直到有一个为空指针为止
{
if (l1->val <= l2->val) //若是1的值小于2的值,就考察1的下一个值
{
workNode->next = l1;
l1 = l1->next;
}
else//考察2的下一个值
{
workNode->next = l2;
l2 = l2->next;
}
workNode = workNode->next;
}
workNode->next = (l1 != nullptr) ? l1 : l2;//谁不为空就把谁剩下的加进去
return result->next;
}
};
连接:https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-
22. 括号生成
借鉴了以前电话号码题的思路,经过一个队列作到了层序遍历,可是因为产生的括号的有效性不能保证,因此又写了一个判断有效性的函数,过程十分复杂
class Solution {
public:
bool isright(string s)
{
stack<char> st;
for (auto i : s)
{
if (i == '(') { st.push('('); }
else
{
if (!st.empty() && st.top() == '(') { st.pop(); }
else { return false; }
}
}
if (st.empty()) { return true; }
else { return false; }
}
vector<string> generateParenthesis(int n) {
if (n == 0)
{
vector<string> s = { "" };
return s;
}
else
{
string s = "(";
queue<string> res;
res.push(s);
for (int i = 0; i < 2 * (n-1); i++)
{
int j = res.size();
while (j)
{
string s1 = res.front() + "(";
res.push(s1);
string s2 = res.front() + ")";
res.push(s2);
res.pop();
j--;
}
}
vector<string> re;
while (!res.empty())
{
string s3 = res.front() + ")";
if (isright(s3))
{
re.push_back(s3);
res.pop();
}
else { res.pop(); }
}
return re;
}
}
};
有一种能大大提升效率的方法(多用于树形问题)是剪枝算法,及时判断是否可行,不可行就舍去这一树枝
递归作法(代码简单可是情景必需要知足递归条件):
class Solution {
public:
vector<string> generateParenthesis(int n) {
if (n == 0) return{ "" };
if (n == 1) return{ "()" };
vector<string> ans;
generateParenthesisIter("(", n-1, n, ans);
return ans;
}
void generateParenthesisIter(string valid, int left_num, int right_num, vector<string>& ans){
if (left_num == 0){ //递归终止条件
valid.append(right_num, ')');
ans.push_back(valid);
return;
}
for (int n = left_num; n >= 0; n--){ //本层使用的左括号数量
string str = valid;
if (left_num - n > right_num - 1)//剪枝: 无效的分支
return; //剩余括号中左括号数量大于右括号数量,说明已用的右括号数量大于左括号数量
str.append(n, '(');
str.append(1, ')');
generateParenthesisIter(str, left_num - n, right_num - 1, ans);
}
return;
}
};
做者:lcl-17
连接:https://leetcode-cn.com/problems/generate-parentheses/solution/c-shen-du-you-xian-bian-li-0ms-by-lcl-17/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
找到全部括号的组合方式看起来比较复杂。
因此咱们能够尝试换个思路:若是“(”对应数字1,“)”对应数字-1呢?
经过观察咱们能够发现这样一个规律:
凡有效的括号组合,转化成数字,任意前n项和都不小于0!
好比:“()()()”
前1位:1>=0;前2位:1+(-1)=0>=0;前3位:1+(-1)+1=1>=0;
…以此类推,前n位数字和均大于等于0.
又好比:“((()))”
前3位:1+1+1=3>=0;前4位:1+1+1+(-1)=2>=0;前5位:1+1+1+(-1)+(-1)=1>=0;
…依然知足规律。
至此,咱们就能想到这样一个思路:
1.目标为n时,能够转化为n个-1和n个1
2.求这串数字的全部排列
3.知足以上规律的就是有效的括号组合
4.最后一步再将数字组合转化成括号组合
整个过程须要一些小的工具:
1.求全排列的函数:next_permutation
2.数字转化成括号:容器map
class Solution {
public:
vector<string> generateParenthesis(int n)
{
vector<string> result;
if(n == 0){return result;}
vector<vector<int>> mid;
vector<int> temp;
for(int i = 0 ; i < n ; i ++)
{
temp.push_back(-1); //先放全部的-1
}
for(int i = 0 ; i < n ; i ++)
{
temp.push_back(1); //再放全部的+1(这样的缘由是由于全排列须要从小到大的顺序)
}
while(next_permutation(temp.begin(),temp.end())) //求全排列
{
int target = 0;
int judg = 1;
for(auto i:temp)
{
target+=i;
if(target < 0)
{
judg = 0;break; //是否知足前n项之和不小于0
}
}
if(judg == 1){mid.push_back(temp);}//若是不用剪枝,则能够将数组放入mid
}
map<int,string> invert;
invert.insert(map<int,string>::value_type(1,"(")); //1对应左括号
invert.insert(map<int,string>::value_type(-1,")")); //-1对应右括号
for(auto i:mid)
{
string s;
for(auto j:i)
{
s += invert[j]; //数字组合转化成字符串
}
result.push_back(s);
}
return result;
}
};
做者:da-lian-mao-ai-chi-yu
连接:https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-tai-fu-za-shu-zi-zhuan-hua-ta-by-da-lian-m/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
全排列函数next_permutation
用这个函数一会儿就省去了找全部可能的排列,在排列以后再转成括号就好了,因为只有一种括号,就用1和-1来代替并使用剪枝算法
while(next_permutation(temp.begin(),temp.end()))
{}
next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列,同时并改变num数组的值。
另外,须要强调的是,next_permutation()在使用前须要对欲排列数组按升序排序,不然只能找出该序列以后的全排列数。
23. 合并K个排序链表
这种思路太好了,放到一块儿再重构,只要掌握好新建链表的方法就能够了,必须用new
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<int> v;
for(auto head:lists)
{
while(head)
{
v.push_back(head->val);
head=head->next;
}
}
sort(v.begin(),v.end());
ListNode* head = new ListNode(0);
ListNode* res = head;
//int i = v.size();
for(int i = 0 ; i<v.size(); i++)
{
ListNode* temp =new ListNode(v[i]);
res->next = temp;
res = temp;
}
return head->next;
}
};
26. 删除排序数组中的重复项
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int i =1;
int j = 0;
int len = nums.size();
if(len==0)return 0;
for(i=1; i<len;i++)
{
if(nums[i]==nums[j])continue;
else
{
nums[++j] = nums[i];
}
}
return j+1;
}
};
27. 移除元素
循环这里必须加等号
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int i = 0 ;
int j = nums.size()-1;
while(i<=j)
{
while(i<=j && nums[i]!=val) i++;
while(i<=j && nums[j]==val)j--;
if(i<=j) swap(nums[i],nums[j]);
}
return i;
}
};
31. 下一个排列
class Solution {
public:
void nextPermutation(vector<int>& nums) {
if(next_permutation(nums.begin(),nums.end()))
{
return ;
}
else
{
sort(nums.begin(),nums.end());
return ;
}
}
};
采用的是遍历判断法,可以剪枝的地方很是有限,因此超时了
class Solution {
public:
bool is(string s1)
{
if(s1[0]==')')return false;
int len = s1.size();
if(len%2!=0)return false;
stack<char> st;
for(auto i:s1)
{
if(i=='(')
{
st.push(i);
}
else
{
if(!st.empty() && st.top()=='(')
{
st.pop();
}
else
{
return false;
}
}
}
return st.empty();
}
int longestValidParentheses(string s) {
//两种办法,第一种双指针窗口法,当遇到破坏结构时,从中间的地方开始起,可是可能会有一点复杂
//遍历判断法,专门呢写一个函数,第一种的复杂度确定是最低的
if(s.empty())return 0;
int max = 0;
int len = s.size();
if(len==1)return 0;
for(int i = 0 ; i<len ;i++)
{
for(int j = i+1;j<len;j++)
{
string s1=s.substr(i,j-i+1);
if(is(s1) && j-i+1>max)max = j-i+1;
}
}
return max;
}
};
33. 搜索旋转排序数组
class Solution {
public:
int search(vector<int>& nums, int target) {
int right = nums.size();
int left = 0;
while(left<right)
{
int mid = left + (right-left)/2;
if(nums[mid]==target){return mid;}
else if (nums[mid]>target)
{
if(target>=nums[0] || nums[mid]<nums[0]){right = mid;}
else{left=mid+1;}
}
else
{
if(nums[mid]>=nums[0] ||target<nums[0]){left=mid+1;}
else{right=mid;}
}
}
return -1;
}
};
class Solution {
public:
int search(vector<int>& nums, int target) {
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
lo = mid + 1;
else
hi = mid;
}
return lo == hi && nums[lo] == target ? lo : -1;
}
};
做者:LukeLee
连接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/ji-jian-solution-by-lukelee/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while(left<right)
{
int mid = left + (right-left)/2;
if(nums[mid]==target)
{
int t1 =mid-1, t2 = mid+1;
while(t1>=0 && nums[t1]==target)t1--;
while(t2<(int)nums.size() && nums[t2]==target)t2++;
return {t1+1,t2-1};
}
else if(nums[mid]<target)
{
left = mid +1;
}
else{right = mid;}
}
return {-1,-1};
}
};
35. 搜索插入位置(二分法***************)
二分法的边界仍是比较难处理,这道题中当存在相等时就直接返回mid,当不相等的时候须要进行两值夹逼并返回有值,并且两个边界都不能舍去,可是这样又会可能无限循环,最后还要加个if判断是否夹逼了
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int len = nums.size();
int left=0,right = len-1;
if(target<=nums[0])return 0;
if(target>nums[len-1])return len;
if(target==nums[len-1])return len-1;
while(left<right)
{
int mid = (left+right)/2;
if(nums[mid]==target)return mid;
else if(nums[mid]>target)
{
right = mid;
}
else
{
left = mid;
}
if(left==right-1 && nums[left]<target && nums[right]>target )return right;
}
return right;
}
};
简单的写法
能够不用夹逼,由于找的时刚刚大于等于这个值的,因此每次让左边界加1
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int low = 0, high = nums.size() - 1, mid = 0;
while(low <= high){
mid = low + (high - low) / 2;
if(nums[mid] < target) low = mid + 1;
else if(nums[mid] > target) high = mid - 1;
else return mid;
}
return low;
}
};
比较使用的模板
用来求刚刚大于等于target的第一个值
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int len = nums.size();
int left=0,right = len;
while(left<right)
{
int mid = (left+right)/2;
if(nums[mid]==target)return mid;
else if(nums[mid]<target)
{
left = mid+1;
}
else
{
right = mid;
}
}
return left;
}
};
36. 有效的数独
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
//主要考察二维数组用法
//每一列
for(int i= 0 ; i<9 ;i++)
{
set<char> st;
int num = 0;
for(int j = 0 ; j < 9; j++)
{
if(board[i][j]=='.'){continue;}
else{st.insert(board[i][j]);num++;}
}
if(st.size()!=num){return false;}
}
//每行
for(int i= 0 ; i<9 ;i++)
{
set<char> st;
int num = 0;
for(int j = 0 ; j < 9; j++)
{
if(board[j][i]=='.'){continue;}
else{st.insert(board[j][i]);num++;}
}
if(st.size()!=num){return false;}
}
for(int c1 = 0 ; c1<9; c1=c1+3)
{
for(int c2 =0 ; c2<9 ;c2=c2+3)
{
set<char>st;
int num=0;
for(int i=0 ; i<3 ;i++)
{
for(int j = 0; j<3; j++)
{
if(board[c1+i][c2+j]=='.'){continue;}
else{st.insert(board[c1+i][c2+j]);num++;}
}
}
if(st.size()!=num){return false;}
}
}
return true;
}
};
36. 有效的数独
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<int> wow(9,0);
int mux1;
int mux2;
int mux3;
int box_index;
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j] == '.'){
continue;
}
mux1 = 0x01 << (board[i][j] - '1');
mux2 = 0x01 << 9 << (board[i][j] - '1');
mux3 = 0x01 << 9 << 9 << (board[i][j] - '1');
box_index = (i/3) * 3 + j/3;
if((wow[i]&mux1) != mux1 && (wow[j]&mux2) != mux2 && (wow[box_index]&mux3) != mux3){
wow[i] = wow[i]|mux1;
wow[j] = wow[j]|mux2;
wow[box_index] = wow[box_index]|mux3;
}
else{
return false;
}
}
}
return true;
}
};
这个遍历三次太复杂了,并且使用set时间也比较长
下面这个方法灵活运用了三个哈希表(二维数组实现)的,单次遍历,用目的区域(行、列、快)来表示行,用1-9来9个数字出现次数做为列,列为10由于直接对应,0不算,给9加一行
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int row[9][10] = {0};// 哈希表存储每一行的每一个数是否出现过,默认初始状况下,每一行每个数都没有出现过
// 整个board有9行,第二维的维数10是为了让下标有9,和数独中的数字9对应。
int col[9][10] = {0};// 存储每一列的每一个数是否出现过,默认初始状况下,每一列的每个数都没有出现过
int box[9][10] = {0};// 存储每个box的每一个数是否出现过,默认初始状况下,在每一个box中,每一个数都没有出现过。整个board有9个box。
for(int i=0; i<9; i++){
for(int j = 0; j<9; j++){
// 遍历到第i行第j列的那个数,咱们要判断这个数在其所在的行有没有出现过,
// 同时判断这个数在其所在的列有没有出现过
// 同时判断这个数在其所在的box中有没有出现过
if(board[i][j] == '.') continue;
int curNumber = board[i][j]-'0';
if(row[i][curNumber]) return false;
if(col[j][curNumber]) return false;
if(box[j/3 + (i/3)*3][curNumber]) return false;
row[i][curNumber] = 1;// 以前都没出现过,如今出现了,就给它置为1,下次再碰见就可以直接返回false了。
col[j][curNumber] = 1;
box[j/3 + (i/3)*3][curNumber] = 1;
}
}
return true;
}
};
做者:liujin-4
连接:https://leetcode-cn.com/problems/valid-sudoku/solution/36-jiu-an-zhao-cong-zuo-wang-you-cong-shang-wang-x/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
写了一套很是复杂的算法,原理是依次判断每一个控制区域,若是有个地方能用三个条件判断出来则填上,而后再解决其余的,结果发现代码在无限循环,缘由是不存在这样的直接能够判断出来的位置,这样原理上就出错了
class Solution {
public:
int num(vector<vector<char>>& board, int k1, int k2)
{
map<char, int> m = { {'1',0},{'2',0},{'3',0},{'4',0},{'5',0},{'6',0},{'7',0},{'8',0},{'9',0} };
for (int i = 0; i < 9; i++)
{
if (board[k1][i] != '.') { m[board[k1][i]] = 1; }
if (board[i][k2] != '.') { m[board[i][k2]] = 1; }
}
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (board[k1 / 3 + i][k2 / 3 + j] != '.') { m[board[k1 / 3 + i][k2 / 3 + j]] = 1; }
}
}
map<char, int>::iterator iter;
int num = 0;
int res = 0;
for (auto iter = m.begin(); iter != m.end(); iter++)
{
//int num = 0;
if (iter->second == 0) { res = iter->second; num++; }
}
if (num == 1) { return res; }
else { return 0; }
}
bool is(vector<vector<char>>& board)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (board[i][j] == '.') { return false; }
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
//想法使用递归,终止条件是填满了,方法是对空着的位置进行遍历,每个都设置一个哈希,当行列块又出现的设为1,当剩最后一个 了时就返回这个表
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (board[i][j] == '.')
{
if (num(board, i, j)) { board[i][j] = char(num(board, i, j)+'0' ); }
else { continue; }
}
}
}
while (!is(board)) { solveSudoku(board); }
return;
}
};
39. 组合总和
要特别注意将i放入下次dfs的写法,目的就是为了下次再也不查找以前的元素,值得学习
class Solution {
private:
vector<vector<int>> res;
vector<int> path;
int sum = 0;
public:
void dfs(vector<vector<int>>& res,vector<int>& candidates,vector<int>& path, int sum,int target ,int j)
{
if(sum == target)
{
res.push_back(path);return;
}
if(sum>target)return;
for(int i = j; i<(int)candidates.size() ;i++)
{
path.push_back(candidates[i]);
sum +=candidates[i];
dfs(res, candidates, path, sum, target,i);
path.pop_back();
sum -=candidates[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
dfs(res,candidates,path,0,target,0);
return res;
}
};
dfs深度优先搜索***
回溯算法:当给定终点时,能够进行回退
再加上递归和剪枝算法
(二叉树经常使用算法:回溯、队列、递归、剪枝)
负递归算法:
// author:rmokerone
#include <iostream>
#include <vector>
using namespace std;
class Solution {
private://成员变量
vector<int> candidates;
vector<vector<int>> res;
vector<int> path;
public:
void DFS(int start, int target) {
if (target == 0) { //递归终止条件
res.push_back(path);
return;
}
for (int i = start; i < candidates.size() && target - candidates[i] >= 0; i++) {
path.push_back(candidates[i]);
DFS(i, target - candidates[i]);
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
std::sort(candidates.begin(), candidates.end());
this->candidates = candidates;
DFS(0, target);
return res;
}
};
做者:liweiwei1419
连接:https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
正递归加剪枝算法:
要特别注意几点:
1.是用了剪枝是为了提速
2.除此以外,在深度优先搜索的时候能够设置从当前元素开始,由于以前的元素在以前的节点已经用过了,因此加了一个start变量用来记录在can容器中的位置
3.像sum这种的不用每次都计算,直接加个参数就好了,注意全局变量的定义位置,由于递归函数要用,因此定义在全局的地方,还能够在外面定义可是在函数中进行计算,好比siz这个变量,更严格点能够定义在private中
class Solution {
public:
vector<int> tmp;
vector<vector<int>> ans;
int siz;
void dfs(int now, int sum, int tar, vector<int>& num)
{
if(sum > tar) return;
if(sum == tar)
{
ans.push_back(tmp);
return;
}
for(int i = now; i < siz; i ++)
{
tmp.push_back(num[i]); //一层一层往下走
dfs(i, sum + num[i], tar, num); //当大于或者等于时都会返回
tmp.pop_back();//回到上一个分叉节点,从整个树的最左边一条开始试
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
siz = candidates.size();
dfs(0, 0, target, candidates);
return ans;
}
};
做者:iswJXkYVv3
连接:https://leetcode-cn.com/problems/combination-sum/solution/c-di-gui-shen-sou-by-iswjxkyvv3/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
41. 缺失的第一个正数
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
//sort(nums.begin(),nums.end());
for(int i = 1;true;i++)
{
auto temp = find(nums.begin(),nums.end(),i);
if (temp==nums.end()){return i;}
}
}
};
还可使用哈希表作,创建一个1到n的哈希表,遍历过数组后找第一个哈希值为0的
42. 接雨水
这是一个创建在一维数组上的问题,理论上这类的全部问题均可以用双指针来解决,这道题的难点在于找到最大值以后的后半部分怎么处理,怎么去找到剩下的部分,这时候须要求最大值,使用max_element函数,可是注意返回的是一个迭代器,用法以下
#include <algorithm>
//返回迭代器
auto max = max_element(v.begin(), v.end());
//获得最大值对应下标
int kk = max-v.begin();
当开始使用这个函数的时候想把里面全部的索引换成迭代器指针,可是发如今执行起来十分有困难,就是由于迭代器之间不传递,好比i和j都是v的迭代器,i++被容许,可是j=i+1就不被容许,因此能不使用迭代器就不使用,当要使用那些返回迭代器的方法时,能够用他减去v.begin()天然就返回的是下标位置
class Solution {
public:
int trap(vector<int>& height) {
if(height.size()<=2){return 0;}
int i = 0;
int j = 1;
int sum = 0;
while (i < height.size() - 2)
{
while (j<height.size() && height[i] > height[j]) { j++; }
if (j == height.size())
{
auto m = max_element(height.begin()+i+1, height.end());
j=m-height.begin();
}
sum = sum + (j - i - 1)*min(height[i], height[j]);
for (int c = i + 1; c < j; c++)
{
sum = sum - height[c];
}
i = j;
j = i + 1;
}
return sum;
}
};
堆栈的方法,不是很好理解
直观想法
咱们能够不用像方法 2 那样存储最大高度,而是用栈来跟踪可能储水的最长的条形块。使用栈就能够在一次遍历内完成计算。
咱们在遍历数组时维护一个栈。若是当前的条形块小于或等于栈顶的条形块,咱们将条形块的索引入栈,意思是当前的条形块被栈中的前一个条形块界定。若是咱们发现一个条形块长于栈顶,咱们能够肯定栈顶的条形块被当前条形块和栈的前一个条形块界定,所以咱们能够弹出栈顶元素而且累加答案到
\text{ans}ans 。算法
使用栈来存储条形块的索引下标。 遍历数组: 当栈非空且
\text{height}[current]>\text{height}[st.top()]height[current]>height[st.top()]
意味着栈中元素能够被弹出。弹出栈顶元素 \text{top}top。 计算当前元素和栈顶元素的距离,准备进行填充操做
\text{distance} = \text{current} - \text{st.top}() -
1distance=current−st.top()−1 找出界定高度 \text{bounded_height} =
\min(\text{height[current]}, \text{height[st.top()]}) -
\text{height[top]}bounded_height=min(height[current],height[st.top()])−height[top]
往答案中累加积水量\text{ans} \mathrel{+}= \text{distance} \times
\text{bounded_height}ans+=distance×bounded_height 将当前索引下标入栈 将
\text{current}current 移动到下个位置
做者:LeetCode
连接:https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
int trap(vector<int>& height)
{
int ans = 0, current = 0;
stack<int> st;
while (current < height.size()) {
while (!st.empty() && height[current] > height[st.top()]) {
int top = st.top();
st.pop();
if (st.empty())
break;
int distance = current - st.top() - 1;
int bounded_height = min(height[current], height[st.top()]) - height[top];
ans += distance * bounded_height;
}
st.push(current++);
}
return ans;
}
做者:LeetCode
连接:https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
43. 字符串相乘
没有思路,原来是利用乘法的计算方式来的
class Solution {
public:
string multiply(string num1, string num2) {
int n1=num1.size();
int n2=num2.size();
string res(n1+n2,'0');
for(int i=n2-1;i>=0;i--){
for(int j=n1-1;j>=0;j--){
int temp=(res[i+j+1]-'0')+(num1[j]-'0')*(num2[i]-'0');
res[i+j+1]=temp%10+'0';//当前位
res[i+j]+=temp/10; //前一位加上进位,res[i+j]已经初始化为'0',加上int类型自动转化为char,因此此处不加'0'
}
}
//去除首位'0'
for(int i=0;i<n1+n2;i++){
if(res[i]!='0')
return res.substr(i);
}
return "0";
}
};
做者:carryzz
连接:https://leetcode-cn.com/problems/multiply-strings/solution/c-shu-shi-cheng-fa-dai-ma-jian-ji-you-ya-yi-dong-b/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
44. 通配符匹配
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
vector< vector<bool> > dp(n+1, vector<bool>(m+1, false)); dp[0][0] = true;
// initialize
for (int i = 1; i <= m; ++ i){
if(p[i - 1] == '*' && dp[0][i - 1]) dp[0][i] = dp[0][i - 1];
}
for (int i = 1; i <= n; ++ i){
for (int j = 1; j <= m; ++ j){
if (s[i - 1] == p[j - 1] || p[j - 1] == '?'){
dp[i][j] = dp[i - 1][j - 1];// ismatch, move on
}else if (p[j - 1] == '*'){
bool zero, mul;// '*' act as zero, '*' act as multiple characters
zero = (j < m && s[i - 1] == p[j] && dp[i - 1][j - 1]) || dp[i][j - 1];
mul = dp[i -1][j];
dp[i][j] = zero || mul;
}
}
}
return dp[n][m];
}
};
做者:wen-mu-yang
连接:https://leetcode-cn.com/problems/wildcard-matching/solution/c-dong-tai-gui-hua-yu-shuang-zhi-zhen-tan-xin-by-w/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
45. 跳跃游戏 II
使用了递归算法,不断更新起点,每更新一次跳到能跳到的最远的地方,记录到达终点时的步数,但在过程当中关于什么时候记录步数的问题很难。终于调成功后发现这样是错误的,由于有时不须要全跳,尤为是最后几个值为0的状况,要是早早跳到这里反而会到不了终点!
class Solution {
public:
int ans=0;
int summm(int start, vector<int> nums)
{
int temp = max_element(nums.begin() + start +1, nums.begin() + start + nums[start]+1) - nums.begin();
if (start + nums[start] >= temp + nums[temp]) { ans++; return start + nums[start]; }
else { ans++; return temp ; }
}
int jump(vector<int>& nums) {
int len = nums.size();
//int ans = 0;
if (len == 1) { return 0; }
else
{
int start = 0;
//if (start + nums[start] >= len) { return 1; }
while (start<len )
{
if (start + nums[start] >= len-1) { return ans + 1; }
start = summm(start, nums);
}
return ans;
}
}
};
贪心算法
看了解答,发现这种思路总体是对的,就是追求每一次能走的最大,然而以前的错误在于,并非比较start+nums[start]和max[start,start+len(start)]之间的最大值,应该比较的是和区间里每个值和其值的和即i+len(i),这才是走的最远的方法,按照这种方法不断更新,就能够找到最后了
即便意思相近可是别人的表达也十分简介
int jump(vector<int> &nums)
{
int ans = 0;
int start = 0;
int end = 1;
while (end < nums.size())
{
int maxPos = 0;
for (int i = start; i < end; i++)
{
// 能跳到最远的距离
maxPos = max(maxPos, i + nums[i]); //在遍历的过程当中不断更新这个最大值
}
start = end; // 下一次起跳点范围开始的格子
end = maxPos + 1; // 下一次起跳点范围结束的格子,加一是由于上面的遍历时左闭右开的
ans++; // 跳跃次数
}
return ans;
}
做者:ikaruga
连接:https://leetcode-cn.com/problems/jump-game-ii/solution/45-by-ikaruga/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
46. 全排列
关于全排列next_permumation有几点须要说明
1.之气那要排序
2.只要开始全排列,第一个结果是已经改变以后的数组,而不是原来的
3。参数是首末迭代器
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
sort(nums.begin(), nums.end());
res.push_back(nums);
while(next_permutation(nums.begin(),nums.end()))
{
res.push_back(nums);
}
return res;
}
};
这是使用队列层序遍历的方法写的,可是因为不容许重复,每次要使用find判断,十分复杂
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
if (nums.size()==0 || nums.size()==1)
{
res.push_back(nums);
return res;
}
sort(nums.begin(), nums.end());
queue<vector<int>> q;
for(auto i:nums)
{
vector<int> temp;
temp.push_back(i);
q.push(temp);
}
//int i=nums.size()-1;
while(q.front().size()!=nums.size())
{
for (auto i:nums)
{
vector<int> temp = q.front();
if(find(temp.begin(),temp.end(),i)==temp.end())
{
temp.push_back(i);
q.push(temp);
}
}
q.pop();
}
while(!q.empty())
{
res.push_back(q.front());
q.pop();
}
return res;
}
};
回溯问题+决策树
算法模板
递归{
递归出口;
for(int i = 1;i<=n;i++){
add(i);
进入递归;
remove(i);
}
}
做者:windliang
连接:https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-2-7/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
void backtrack(路径,选择列表)
{
if(终止条件)
{
传出路径结果
return;
}
for i in 选择列表
{
进入该选择
back(路径,选择列表)
退出该选择
}
}
这是根据该思想写的代码,代码结构简单,清晰,可是优化的很差
class Solution {
private:
vector<vector<int> > res;
int len;
vector<int> path;
public:
void backtrack(vector<int> &path, vector<int>& nums)
{
set<int> s(path.begin(),path.end());
if(path.size()==len)
{
if (s.size()==len)
{
res.push_back(path);
return;
}
else
{
return;
}
}
for(auto i : nums)
{
path.push_back(i);
backtrack(path,nums);
path.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
len = nums.size();
if (nums.size()==0 || nums.size()==1)
{
res.push_back(nums);
return res;
}
sort(nums.begin(), nums.end());
backtrack(path,nums);
return res;
}
};
48. 旋转图像
将图片沿正对角线和竖轴翻转一下就能够了
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
// 对于正对角线对称翻转
for (int i = 0; i < n; i++) {
for (int j = i; j < m; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
// 竖轴镜像操做
for (int i = 0; i < n; i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
}
};
做者:happy_yuxuan
连接:https://leetcode-cn.com/problems/rotate-image/solution/leetcode48-fan-zhuan-gui-lu-by-happy_yuxuan/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
49. 字母异位词分组
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
vector<pair<multiset<char>,vector<string>>> st;
for(auto str:strs)
{
multiset<char> temp(str.begin(),str.end());
bool b = false;
for(int i = 0 ;i<(int)st.size() ;i++)
{
if(st[i].first==temp)
{
st[i].second.push_back(str);
b = true;
break;
}
}
if(!b)
{
st.push_back(pair<multiset<char>,vector<string>>(temp,{str}));
}
}
for(auto i:st)
{
vector<string> temp;
for(auto j:i.second)
{
temp.push_back(j);
}
res.push_back(temp);
}
return res;
}
};
更好的办法:哈希表和数组联系,只要引入一个hash表,索引是排序后的单词,值为结果vector的下标,循环一遍就行了
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
int sub=0; //结果vector的下标值
string tmp; //临时string
unordered_map<string,int> work; //判断排序后单词是否存在,即字母组成是否一致
for(auto str:strs)
{
tmp=str;
sort(tmp.begin(),tmp.end());
if(work.count(tmp))
{
res[work[tmp]].push_back(str);
}
else
{
vector<string> vec(1,str);
res.push_back(vec);
work[tmp]=sub++;
}
}
return res;
}
};
做者:rjs
连接:https://leetcode-cn.com/problems/group-anagrams/solution/c-yin-ru-hashbiao-shi-jian-32ms-ji-bai-9948-nei-cu/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
50. Pow(x, n)
暴力法
class Solution {
public:
double myPow(double x, int n) {
if(x==0)return 0;
if(x==1 || n==0) return 1;
double res=1;
while(n>0)
{
res=res*x;
n--;
}
while(n<0)
{
res = res/x;
n++;
}
return res;
}
};
递归法,将指数幂进行二分,十分巧妙
class Solution {
public:
double myPow(double x, int n) {
if (n == 0) { return 1; }
if (n == 1) { return x; }
if (n == -1) { return 1 / x; }
double half = myPow(x, n / 2);
double rest = myPow(x, n % 2);
return rest * half * half;
}
};
做者:frank588
连接:https://leetcode-cn.com/problems/powx-n/solution/qing-xi-jian-dan-de-dan-han-shu-di-gui-wu-lei-xing/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
51. N皇后(回溯dfs)
思路很是清晰,典型的n皇后的问题,稍微麻烦的问题是判断是否额可以知足条件,并且注意不用在最后才检查条件。应该在中间进行判断,只要可以知足条件才继续下去,这样到最后也就知足条件了,放一个知足一个,最后就必定知足,这里一行一行创建的会稍微简单一点
class Solution {
vector<vector<string>> res;//存结果
vector<string> tmp;//存棋盘
public:
vector<vector<string>> solveNQueens(int n) {
string line(n,'.');//既然一行一行试,那就一行一行存
solveNQueens(line, 0, n);//从第0行开始
return res;
}
private:
//试某一行
void solveNQueens(string& line, int row, int n)
{
if(tmp.size() == n)//棋盘绘制够n行存进结果,不用继续试了
{
res.push_back(tmp);
return;
}
for(int i = 0; i < n; ++i)//一格一格,每格都要试
{
if(checkAll(row, i, n)) //符合条件了
{
line[i] = 'Q'; //就把当前试的这一格放皇后
tmp.push_back(line); //而后把这一行绘制进棋盘
line[i] = '.'; //棋盘的下一行应该是没有皇后的
solveNQueens(line, row + 1, n);//去试下一行
tmp.pop_back(); //接下来要去试下一格,刚才绘制进去的那一行删掉
}
}
}
//暴力检查条件
bool checkAll(int row, int col, int n)
{
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i,--j)//左上方
{
if(tmp[i][j] == 'Q')
return false;
}
for(int i = row - 1; i >= 0; --i)//正上方
{
if(tmp[i][col] == 'Q')
return false;
}
for(int i = row -1, j = col + 1; i >= 0 && j < n; --i, ++j)//右上方
{
if(tmp[i][j] == 'Q')
return false;
}
return true;
}
};
做者:zynflicker
连接:https://leetcode-cn.com/problems/n-queens/solution/4ms89mhui-su-fa-jian-dan-yi-dong-by-zynflicker/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
53. 最大子序和(贪心)
很典型的使用贪心算法的例题
class Solution
{
public:
int maxSubArray(vector<int> &nums)
{
//相似寻找最大最小值的题目,初始值必定要定义成理论上的最小最大值
int result = INT_MIN;
int numsSize = int(nums.size());
int sum = 0;
for (int i = 0; i < numsSize; i++)
{
sum += nums[i];
result = max(result, sum);
//若是sum < 0,从新开始找子序串
if (sum < 0)
{
sum = 0;
}
}
return result;
}
};
做者:pinku-2
连接:https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-cshi-xian-si-chong-jie-fa-bao-li-f/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
55. 跳跃游戏
每次跟新一次位置,当最远达到的地方是0,说明false,代码用vs会出现莫名其妙的问题,可是作法应该是对的
另外因为可能出现的请状况太多了,在边界的设置上出错的地方太多了
class Solution {
public:
bool canJump(vector<int>& nums) {
int left = 0;
int len = nums.size();
while(1)
{
if(left>=len-1 || left+nums[left]>=len-1)return true;
int max = 0;
int temp = 0;
for(int i = left ; i<=len-1 &&i<=left+nums[left] ;i++)
{
if(i+nums[i]>max){max = i+nums[i];temp=i;}
}
if(max<len-1&& nums[max]==0)return false;
left = temp;
}
return false;
}
};
一样意思但更简洁的代码
解题思路:
1.若是某一个做为 起跳点 的格子能够跳跃的距离是 3,那么表示后面 3 个格子均可以做为 起跳点。
2.能够对每个能做为 起跳点 的格子都尝试跳一次,把 能跳到最远的距离 不断更新。
3.若是能够一直跳到最后,就成功了。
做者:ikaruga
连接:https://leetcode-cn.com/problems/jump-game/solution/55-by-ikaruga/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
bool canJump(vector<int>& nums)
{
int k = 0;
for (int i = 0; i < nums.size(); i++)
{
if (i > k) return false;//k表示到i的时候,以前全部位置能到达的最大距离,每个都走一下,可是不用考虑怎么走的,当走到一个位置不能再更新了,就会小于下一个i
k = max(k, i + nums[i]);
}
return true;
}
做者:ikaruga
连接:https://leetcode-cn.com/problems/jump-game/solution/55-by-ikaruga/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
56. 合并区间(贪心)
一样的格式,可是改为max了,并且维护的不是一个树,而是先放到二维向量中的末尾
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> res;
if(intervals.empty())return res;
sort(intervals.begin(),intervals.end());
res.push_back(intervals[0]);
for(int i = 1 ;i< (int)intervals.size() ;i++)
{
if(intervals[i][0]<= res.back()[1])
{
res.back()[1] = max(res.back()[1],intervals[i][1]);
}
else
{
res.push_back(intervals[i]);
}
}
return res;
}
};
使用长度为1的滑动窗口在滑动,可是没想到题目仍是会出现后面区间包含前面的状况,这样就要从新设计了
看到答案说sort函数排序能够默认按照第一个第二个这样排序,能够排序以后在作,排序以后后面的值确定是大于等于前面的,可是还要考虑后面包含前面的状况
考点:排序+数组
思路:先对二维数组表示的全部区间的左端点进行升序排序,而后从第二个区间(下标为1)开始遍历判断是否能够作合并操做:只要前一个区间的右端点大于等于当前区间的左端点,那说明这两个区间能够合并,合并后的区间左端点是前一个区间的左端点,只须要更新右端点为两个区间右端点的最大值便可。
不然,说明两个区间没有重叠,直接更新表示不重复区间的pos值
做者:xing2fan
连接:https://leetcode-cn.com/problems/merge-intervals/solution/qu-jian-he-bing-de-pai-xu-fa-by-xing2fan/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (!intervals.size()) return {};
//先把区间集合按照左端点从小到大进行排序
sort(intervals.begin(), intervals.end(), less<vector<int>>());
int pos = 0;//pos的值是每一个不重叠的区间
//直接在原区间上作就能够
//从第二个区间开始去比较
for (int i = 1; i < intervals.size(); ++i)
{
//两个区间若能合并,则第一个区间的右端点必定大于等于第二个区间的左端点
//好比[1,3] [2,6]
if (intervals[pos][1] >= intervals[i][0])
{
//第一个区间的尾部须要更新为:两个区间的最大值即[1,6]
intervals[pos][1] = max(intervals[pos][1], intervals[i][1]);
}
else//没有重叠时
{
//[1,6] [2,8]====>区间1就是目前的这个区间
intervals[++pos] = intervals[i];
}
}
intervals.resize(pos + 1);//把最后的不用的弹出
return intervals;
}
};
做者:xing2fan
连接:https://leetcode-cn.com/problems/merge-intervals/solution/qu-jian-he-bing-de-pai-xu-fa-by-xing2fan/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return intervals;
}
sort(intervals.begin(), intervals.end());
vector<vector<int>> result{ intervals.front() };
for (auto&& interval : intervals) {
if (interval.front() > result.back().back()) {
result.emplace_back(move(interval));
} else {
result.back().back() = max(interval.back(), result.back().back());
}
}
return result;
}
};
做者:klaxxi
连接:https://leetcode-cn.com/problems/merge-intervals/solution/c-pai-xu-tan-xin-by-klaxxi/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
57. 插入区间
和上题同样,先插入再作
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> res;
if(newInterval.empty())return intervals;
intervals.push_back(newInterval);
sort(intervals.begin(),intervals.end());
res.push_back(intervals[0]);
for(int i =1; i< (int)intervals.size() ;i++)
{
if(intervals[i][0]<= res.back()[1])
{
res.back()[1] = max(res.back()[1], intervals[i][1]);
}
else
{
res.push_back(intervals[i]);
}
}
return res;
}
};
62. 不一样路径(dp)
在多种题解法中,动态规划每每是最简单的一种,而递归每每是麻烦也很差写的一种,因此最好仍是先考虑dp,这道理可想而知dp较为简单,以前作的dp都是在一维上,这回是二维上的dp
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> board(m,vector<int>(n,0));
for(int i = 0 ; i <m ;i++)
{
board[i][0]=1;
}
for(int j = 0; j<n ;j++)
{
board[0][j]=1;
}
for(int i = 1; i<m ;i++)
{
for(int j = 1 ; j<n ;j++)
{
board[i][j] = board[i-1][j] + board[i][j-1];
}
}
return board[m-1][n-1];
}
};
64. 最小路径和(dp)
很典型的动态规划题目,和上题同样
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.empty())return 0;
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> board(m,vector<int>(n,0));
board[0][0]=grid[0][0];
for(int i = 1 ; i< n ;i++)
{
board[0][i] = grid[0][i]+board[0][i-1];
}
for(int i = 1 ; i< m ; i++)
{
board[i][0] = grid[i][0]+board[i-1][0];
}
for(int i = 1 ; i < m ;i++)
{
for(int j = 1 ; j< n; j++)
{
board[i][j] = grid[i][j] + min( board[i-1][j],board[i][j-1]);
}
}
return board[m-1][n-1];
}
};
69. x 的平方根(二分法)
虽然就是典型的二分法,可是有不少值得讲究的地方:
1.mid最好设置为两个的和除以2再加1,扩大范围更好,否则可能会chucuo
2.初始值能够设置的更小点
3.最后是left和right的变化问题,最后两个都变化或者至少一个变化,而后返回left就能够,没必要要返回mid
class Solution {
public:
int mySqrt(int x) {
if(x==0)return 0;
long left = 1;
long right = x;
while(left<right)
{
long mid = (left+right)/2+1;
if(mid==x/mid)return mid;
else if(mid>x/mid)
{right = mid-1;}
else
{left = mid;}
}
return left;
}
};
70. 爬楼梯(dp)
动态规划
class Solution {
public:
int climbStairs(int n) {
if(n==0)return 0;
if(n==1)return 1;
if(n==2) return 2;
vector<int> dp(n+1,0);
dp[0]=0;
dp[1]=1;
dp[2]=2;
for(int i = 3 ; i<n+1; i++)
{
dp[i] = dp[i-1]+ dp[i-2];
}
return dp[n];
}
};
72. 编辑距离
class Solution {
public:
int minDistance(string word1, string word2) {
int len1 = word1.size();
int len2 = word2.size();
vector<vector<int>> dp(len1+1, vector<int>(len2+1,0));
for(int i = 0 ;i<=len1; i++)
{
dp[i][0] = i;
}
for(int j = 0 ; j<=len2 ;j++)
{
dp[0][j] = j;
}
for(int i=1 ;i<=len1 ;i++)
{
for(int j=1; j<=len2 ;j++)
{
if(word1[i-1]==word2[j-1])
{
dp[i][j] = dp[i-1][j-1] ;
}
else
{
dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
}
}
}
return dp[len1][len2];
}
};
73. 矩阵置零
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if(matrix.size()==0)return;
vector<int> row;
vector<int> col;
int len1 = matrix.size();
int len2 = matrix[0].size();
for(int i= 0 ;i<len1 ; i++)
{
for(int j = 0 ; j <len2 ;j++)
{
if(matrix[i][j]==0)
{
row.push_back(i);
col.push_back(j);
}
}
}
for(auto i :row)
{
for(int j = 0 ; j<len2 ;j++)
{
matrix[i][j]=0;
}
}
for(auto j:col)
{
for(int i = 0 ; i<len1 ; i++)
{
matrix[i][j] = 0;
}
}
return;
}
};
75. 颜色分类(三数快排)
只有三个数的时候排序能够如此简单
class Solution {
public:
void sortColors(vector<int>& nums) {
int left = 0 , right = nums.size()-1;
for(int i = left ;i<=right ;i++)
{
if(nums[i]==0)swap(nums[left++],nums[i]);
if(nums[i]==2)swap(nums[right--],nums[i--]);
}
return;
}
};
快速排序
巩固一下快速排序,要特注意的是先循环j再循环i
class Solution {
public:
void quicksort(int left,int right, vector<int>& nums)
{
if(left>=right)return;
int i = left;
int j = right;
while(i<j)
{
while(i<j && nums[j]>=nums[left])j--;
while(i<j && nums[i]<=nums[left])i++;
if(i<j)
{
swap(nums[i],nums[j]);
}
}
swap(nums[left],nums[i]);
quicksort(left,i-1,nums);
quicksort(i+1,right,nums);
}
void sortColors(vector<int>& nums) {
int len = nums.size();
if(len==0 || len==1)return;
quicksort(0,len-1,nums);
return;
}
};
74. 搜索二维矩阵
采用了两个二分法模板作的,注意衔接的时候,要考虑小于第一个个值的状况
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty())return false;
if(matrix[0].empty())return false;
int len = matrix.size();
int left = 0,right = len;
while(left<right)
{
int mid = (left+right)/2;
if(matrix[mid][0]==target)return true;
else if(matrix[mid][0]<target)
{
left = mid+1;
}
else
{
right = mid;
}
}
int temp = left-1;
if(temp<0)return false;
len = matrix[0].size();
left = 0;right=len;
while(left<right)
{
int mid = (left+right)/2;
if(matrix[temp][mid]==target) return true;
else if(matrix[temp][mid]<target)
{
left=mid+1;
}
else
{
right=mid;
}
}
return false;
}
};
77. 组合
因为这个pos表明的是初始位置,当进行过一次遍历后,这个值也要加1才行
class Solution {
private:
vector<vector<int> > res;
vector<int> path;
public:
void dfs(int n,int pos, int k)
{
if (path.size()==k)
{
res.push_back(path);
}
for(int i = pos; i<= n; i++)
{
path.push_back(i);
dfs(n,pos+1,k);
path.pop_back();
pos++;
}
}
vector<vector<int>> combine(int n, int k) {
if(n==0||k==0) return res;
dfs(n,1,k);
return res;
}
};
其余解答,道理是同样的
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> list;
vector<int> result;
dfs(list,result,n,k,0,-1);
return list;
}
void dfs(vector<vector<int>>& list, vector<int>& result, int n, int k, int pos,int pre){
if(pos == k){
list.push_back(result);
return;
}
if((pos + (n-pre)) <= k)return;//剪枝,添加以后用时节省了2/3
//在当前对不合理的取值进行判断,结束下一层的递归操做。
//若是当前剩余可操做数字的个数即(n-pre)< k-pos+1(即组合中有待赋值的位置个数),(+1是由于当前pos尚未进行操做),则能够判断该条路径不可能获得正确的解,再也不向下探寻。
for(int i=pre+1; i<n ; i++){
result.push_back(i+1);
pre = i;
dfs(list,result,n,k,pos+1,pre);
result.pop_back();//回溯
}
return;
}
};
做者:rouzi
连接:https://leetcode-cn.com/problems/combinations/solution/dfsjian-zhi-by-rouzi/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
78. 子集
适合用递归作,可是递归并很差写
下面这个递归式return,是在最后(至关于没有),这个结构比较少见,主要是由于没有肯定的返回条件,进行一个遍历,而后在遍历的过程当中不断的放入大的容器
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int> > res;
vector<int> tmp;
helper(res,tmp,nums,0);
return res;
}
void helper(vector<vector<int> >& res,vector<int> tmp,vector<int>& nums,int level){
if(tmp.size()<=nums.size()){
res.push_back(tmp);
}
for(int i=level;i<nums.size();i++){
tmp.push_back(nums[i]);
helper(res,tmp,nums,i+1);
tmp.pop_back();
}
return;
}
};
做者:Tangzixia
连接:https://leetcode-cn.com/problems/subsets/solution/liang-chong-fang-fa-qiu-jie-zi-ji-by-tangzixia/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
class Solution {
public:
vector<vector<int>> ans;
vector<int> tmp;
void find(int dep, vector<int>& nums)
{
// 已经处理完最后一位,将目前存储的集合存入 ans ,并回溯
if(dep <= 0)
{
ans.push_back(tmp);
return;
}
// 状况一:集合中有该元素
tmp.push_back(nums[dep - 1]);
find(dep - 1, nums);
tmp.pop_back();
// 状况二:集合中无该元素
find(dep - 1, nums);
}
vector<vector<int>> subsets(vector<int>& nums) {
find(nums.size(), nums);
return ans;
}
};
做者:iswJXkYVv3
连接:https://leetcode-cn.com/problems/subsets/solution/c-0ms-132mb-shen-sou-yong-shi-ji-bai-100mark-by-is/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
79. 单词搜索
因为代码太复杂没有全写完,可是道理应该是对的,遍历每一个word中的字符,当找到该字符时就将下一个字符、找到的坐标、board输入到判断函数中,当全部字符都判断成功时才算含有此字符串,道理时对的,但不算是dfs或者回溯方法
class Solution {
private:
string s1;
int h=0;
int l = 0;
public:
//位置必须传递,才能和上次有关联
bool dfs(char s1, string& s, int a , int b , vector<vector<char>>& board)
{
if(a==0)
{
if(b==0)
{
if(board[a+1][b]==s1 || board[a][b+1]==s2){return true;}}
}
if(b==l-1 )
{
if(board[a+1][b]==s1 || board[a][b-1]==s2){return true;}}
}
else
{
if(board[a+1][b]==s1 || board[a][b+1]==s2 || board[a][b-1]==s2){return true;}}
}
for(int j = 0 ; j <b ; j++ )
{
if(board[a+1][j]==s1){return true;}
}
if(a==h-1)
{
for(int j = 0 ; j <b ; j++ )
{
if(board[a-1][j]==s1){return true;}
}
}
if(b==l-1)
{
for(int i = 0 ; i<a; i++)
{
if(board[i][])
}
}
for(auto i :s)
{
dfs(i,s,)
}
}
bool exist(vector<vector<char>>& board, string word) {
h = board.size();
l = board[0].size();
//如何获取第一次的正确位置,或者进行遍历寻找
for(int i = 0 ; i< h;i++ )
{
for(int j = 0; j<l ; j++)
{
if (board[i][j]==word[0])//这里不用判断
{
if(dfs(word[1],word,i,j,board)){return true;}
}
}
}
return false;
}
};
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if(board.size() == 0) return false;
for (int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
if (dfs(board,word,i,j,0)){
return true;
}
}
}
return false;
}
bool dfs(vector<vector<char>>& board, string& word, int i,int j,int length){
if(i>=board.size()||j>=board[0].size()||i<0||j<0||length>=word.size()||word[length]!=board[i][j]){
return false; //出界或者最后一位不相等
}
if(length==word.size()-1&&word[length]==board[i][j]){//word不为空且最后一位和当前位置相等
return true;
}
char temp=board[i][j];
board[i][j]='0';//这个位置
bool flag=dfs(board,word,i,j+1,length+1)||dfs(board,word,i,j-1,length+1)||dfs(board,word,i+1,j,length+1)||dfs(board,word,i-1,j,length+1); //找四边的每个点,若是点
board[i][j]=temp; // 标记过的点恢复原状,以便进行下一次搜索
return flag;
}
};
做者:z1m
连接:https://leetcode-cn.com/problems/word-search/solution/tu-jie-di-gui-shen-du-you-xian-sou-suo-by-z1m/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
伪代码
dfs(i,j,word, board,len)
{
if(i,j已经出界 || 这个位置和wordlen元素不相等)
{返回false}
if(这个位置和word最后一维相等)
{返回true}
}
exist()
{
遍历board,并对每个位置执行一次判断//当每一个位置都输入进去,直接进入dfs,判断和第一位是否相等,若是不相等则到下一个位置,若是相等则进入函数主体,判断四周的四个位置都和下一位相等,true的终止条件是到了最后一位并且与此位置相等。里面有一点要注意为了防止出现AEA这种又回去的状况,在这次搜索中已经相等过的要设置为‘0’防止回去
}
1.总结:dfs也能够设置为有类型的,当设置为bool型这种特殊的类型时,要写两个终止条件,一个是true的,一个是false,false能够是每次的回退条件,可是true必定是最终的判断条件,剩下的函数主题就是默认的经过这次验证
80. 删除排序数组中的重复项 II
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int len = nums.size();
int i = 0, j = 0;
while(i<len)
{
int temp = i;
while(i<len && nums[i]==nums[temp])i++;
if(i-temp==1){nums[j++]=nums[temp];}
else if(i-temp>=2){nums[j++]=nums[temp];nums[j++]=nums[temp];}
}
return j;
}
};
81. 搜索旋转排序数组 II
先去重
class Solution {
public:
bool search(vector<int>& nums, int target) {
if(nums.empty())return false;
int j = 0;
for(int i =1 ;i<(int)nums.size() ;i++)
{if(nums[i]!=nums[j])nums[++j]=nums[i];}
vector<int> num;
num.assign(nums.begin(),nums.begin()+j+1);
if((int)num.size()>1 && num[j]==num[0]){num.pop_back();}
int right = num.size();
int left = 0;
while(left<right)
{
int mid = left + (right-left)/2;
if(num[mid]==target){return true;}
else if (num[mid]>target)
{
if(target>=num[0] || num[mid]<num[0]){right = mid;}
else{left=mid+1;}
}
else
{
if(num[mid]>=num[0] ||target<num[0]){left=mid+1;}
else{right=mid;}
}
}
return false;
}
};
88. 合并两个有序数组
class Solution {
public:
void merge(vector<int>& arr1, int m, vector<int>& arr2, int n) {
//int len1 = arr1.size();
//int len2 = arr2.size();
if(m==0)
{
arr1.assign(arr2.begin(),arr2.end());
return;
}
if(n==0) return;
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (i>= 0 && j>= 0)
{
while (i>= 0 && j>=0 && arr1[i] >= arr2[j])
{
arr1[k--] = arr1[i--];
}
while (i >= 0 && j >= 0 && arr1[i] <= arr2[j])
{
arr1[k--] = arr2[j--];
}
}
while (i>=0 )
{
arr1[k--] = arr1[i--];
}
while (j>=0)
{
arr1[k--] = arr2[j--];
}
return ;
}
};
91.
字符串转数字
atoi(str.c_str());
字符转数字
int(char-'0')
94. 二叉树的中序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
vector<int> res;
public:
void dfs(TreeNode* root)
{
if(!root) return;
dfs(root->left);
res.push_back(root->val);
dfs(root->right);
}
vector<int> inorderTraversal(TreeNode* root) {
if(!root) return res;
dfs(root);
return res;
}
};
95. 不一样的二叉搜索树 II
看不懂为何这么作
解法一彻底没有用到查找二叉树的性质,暴力尝试了全部可能从而形成了重复。咱们能够利用一下查找二叉树的性质。左子树的全部值小于根节点,右子树的全部值大于根节点。
因此若是求 1…n 的全部可能。
咱们只须要把 1 做为根节点,[ ] 空做为左子树,[ 2 … n ] 的全部可能做为右子树。
2 做为根节点,[ 1 ] 做为左子树,[ 3…n ] 的全部可能做为右子树。
3 做为根节点,[ 1 2 ] 的全部可能做为左子树,[ 4 … n ] 的全部可能做为右子树,而后左子树和右子树两两组合。
4 做为根节点,[ 1 2 3 ] 的全部可能做为左子树,[ 5 … n ] 的全部可能做为右子树,而后左子树和右子树两两组合。
…
n 做为根节点,[ 1… n ] 的全部可能做为左子树,[ ] 做为右子树。
至于,[ 2 … n ] 的全部可能以及 [ 4 … n ] 以及其余状况的全部可能,能够利用上边的方法,把每一个数字做为根节点,而后把全部可能的左子树和右子树组合起来便可。
若是只有一个数字,那么全部可能就是一种状况,把该数字做为一棵树。而若是是 [ ],那就返回 null。
做者:windliang
连接:https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-2-7/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
class Solution {
public:
vector<TreeNode*> helper(int start,int end){
vector<TreeNode*> ret;
if(start > end)
ret.push_back(nullptr);
for(int i=start;i<=end;i++){
vector<TreeNode*> left = helper(start,i-1);
vector<TreeNode*> right = helper(i+1,end);
for(auto l : left){
for(auto r : right){
TreeNode* root = new TreeNode(i);
root -> left = l;
root -> right = r;
ret.push_back(root);
}
}
}
return ret;
}
vector<TreeNode*> generateTrees(int n) {
vector<TreeNode*> ret;
if(n == 0)
return ret;
ret = helper(1,n);
return ret;
}
};
做者:black-hole
连接:https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/c-30xing-dai-ma-di-gui-by-black-hole/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
97. 交错字符串
能正确判断,可是超时了,由于递归的效率比较低;
对于字符串的题,使用递归都比较耗时
class Solution {
private:
int len1;
int len2;
int len3;
public:
bool dfs(int i, int j, int k, string& s1, string &s2, string &s3)
{
if(i==len1 && j==len2 && k==len3) return true;
if(i<len1 && j<len2)
{
if(s2[j]!=s3[k]&&s1[i]==s3[k])
{
return dfs(i+1,j,k+1,s1,s2,s3);
}
if(s1[i]!=s3[k]&&s2[j]==s3[k])
{
return dfs(i,j+1,k+1,s1,s2,s3);
}
if(s1[i]==s3[k]&&s2[j]==s3[k])
{
return dfs(i+1,j,k+1,s1,s2,s3)||dfs(i,j+1,k+1,s1,s2,s3);
}
if(s1[i]!=s3[k]&&s2[j]!=s3[k])
{
return false;
}
}
if(i==len1 && j<len2)
{
if(s2[j]==s3[k]) return dfs(i,j+1,k+1,s1,s2,s3);
else{return false;}
}
if(i<len1 && j==len2)
{
if(s1[i]==s3[k]) return dfs(i+1,j,k+1,s1,s2,s3);
else{return false;}
}
}
bool isInterleave(string s1, string s2, string s3) {
len1 = s1.size();
len2 = s2.size();
len3 = s3.size();
if(len1+len2 != len3) return false;
if(s1.empty()&&s2.empty()&&s3.empty()) return true;
return dfs(0,0,0,s1,s2,s3);
}
};
98. 验证二叉搜索树(dfs)
写了一堆不正确的代码,四层递归
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//用来遍历,得到全部节点下的值
void dfs1(TreeNode* root, vector<int>& res)
{
if(!root) return;
res.push_back(root->val);
dfs1(root->left,res);
dfs1(root->right,res);
}
//用来判断每一个节点做为根节点时候是否符合标准
bool dfs2(TreeNode* root, vector<int> r1, vector<int> r2)
{
if(r1.empty() && r2.empty()) return true;
if(!r1.empty() && r2.empty())
{
for(auto i:r1)
{
if(i>=root->val)return false;
}
}
if(r1.empty() && !r2.empty())
{
for(auto i:r2)
{
if(i<=root->val)return false;
}
}
for(auto i:r1)
{
if(i>=root->val)return false;
}
for(auto i:r2)
{
if(i<=root->val)return false;
}
return true;
}
//对每个进行判断
bool df3(TreeNode* root)
{
vector<int> left;
dfs1(root->left,left);
vector<int> right;
dfs1(root->right,right);
return dfs2(root,left,right);
}
//遍历并返回判断结果
void df4(TreeNode* root, bool& flag)
{
if(!root) return;
if(!df3(root)) flag = false;
isValidBST(root->left);
isValidBST(root->right);
}
bool isValidBST(TreeNode* root) {
if(!root) return true;
bool flag=true;
df4(root,flag);
if(flag==true)return true;
return false;
}
};
以前的思路是判断两百边的数组,可是得到数组就须要进行遍历,十分麻烦,下面的解法目的不是求节点是否在左右节点数组的中间,而是每一个节点和一个区间进行比较,这个区间一开始是无限大,每通过一个节点就将区间范围缩小,往左节点走时父节点做为有边界,往右边界走时父节点做为左边界,这样能够不断的将父节点的区间范围传递下去,十分巧妙
思路:引入上下边界
对于树的每一个节点 val ,设其上下边界 low , high。(用 long 防止 INT_MAX 溢出 )
判断根结点时,须知足 low < val < high ,不然返回 false
判断左节点时,仅 上界 变化 ( 新上界为 high 与 val 较小值。又因 val 必小于 high,故新上界为 val )
判断右节点时,仅 下界 变化 ( 同理,新下界为 val )
做者:penn-10
连接:https://leetcode-cn.com/problems/validate-binary-search-tree/solution/cyu-yan-yan-zheng-er-cha-sou-suo-shu-by-penn-10/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
bool fun(struct TreeNode* root, long low, long high) {
if (root == NULL) return true;
long num = root->val;
if (num <= low || num >= high) return false;
return fun(root->left, low, num) && fun(root->right, num, high);
}
bool isValidBST(struct TreeNode* root){
return fun(root, LONG_MIN, LONG_MAX);
}
做者:penn-10
连接:https://leetcode-cn.com/problems/validate-binary-search-tree/solution/cyu-yan-yan-zheng-er-cha-sou-suo-shu-by-penn-10/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
100. 相同的树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
//一种适用性很强的办法,都通过层序遍历,比较最后的结果,但这确定不是最优解法
if(p==NULL && q==NULL)return true;
if(p==NULL && q!= NULL)return false;
if(p!=NULL && q==NULL)return false;
if(p->val != q->val)return false;
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
};
101. 对称二叉树
易错点时三个条件不能少,并且注意对称时左节点的左孩子和右节点的右孩子相比
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool dfs(TreeNode* root1, TreeNode* root2)
{
if(root1==NULL && root2==NULL){return true;}
if(root1==NULL && root2!=NULL){return false;}
if(root1!=NULL && root2==NULL){return false;}
if(root1->val!=root2->val){return false;}
return dfs(root1->left,root2->right) && dfs(root1->right,root2->left);
}
bool isSymmetric(TreeNode* root) {
if(root==NULL){return true;}
return dfs(root->left,root->right);
}
};
102. 二叉树的层序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
vector<vector<int> > res;
public:
void dfs(vector<TreeNode*> cur)
{
if(cur.size()==0){return;}
vector<int> temp;
vector<TreeNode*> next;
for(auto i:cur)
{
temp.push_back(i->val);
if(i->left!=NULL){next.push_back(i->left);}
if(i->right!=NULL){next.push_back(i->right);}
}
res.push_back(temp);
dfs(next);
}
vector<vector<int>> levelOrder(TreeNode* root) {
if(root==NULL){return res;}
vector<TreeNode*> cur;
cur.push_back(root);
dfs(cur);
return res;
}
};
使用队列的方法
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
vector<int> level;
if(root == nullptr) return res;
queue<TreeNode*> que;
que.push(root);
que.push(nullptr);
TreeNode *cur = nullptr;
while(que.size()){
cur = que.front();
que.pop();
if(cur){
level.push_back(cur->val);
if(cur->left) que.push(cur->left);
if(cur->right) que.push(cur->right);
}else{
res.push_back(level);
level.resize(0);
if(que.size() > 0) que.push(nullptr);
}
}
return res;
}
};
103. 二叉树的锯齿形层次遍历
印象中是使用堆栈的,可是直接用一个bool量来标记也很方便
还能够正常层序遍历,而后隔一个倒叙一下就能够,和1007同样,都是遍历以后对数组作处理
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
vector<vector<int> > res;
bool flag;
public:
void dfs(vector<TreeNode*> cur)
{
if(cur.size()==0){return;}
vector<TreeNode*> next;
vector<int> temp;
for(auto i:cur)
{
if(i->left!=NULL){next.push_back(i->left);}
if(i->right!=NULL){next.push_back(i->right);}
temp.push_back(i->val);
}
if(!flag){reverse(temp.begin(),temp.end());}
flag = !flag;
res.push_back(temp);
dfs(next);
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if(root==NULL){return res;}
vector<TreeNode*> temp;
temp.push_back(root);
flag = 1;
dfs(temp);
return res;
}
};
104. 二叉树的最大深度(***********)
有一种很简单的写法,不少处会用到
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==NULL)return 0;
return max( maxDepth( root->left) , maxDepth( root->right) )+1;
}
};
通常最终值放到private处定义,中间每次须要用到的参量放入递归的参数列表
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
int max;
public:
void dfs(TreeNode* root, int num)
{
if(root->left==NULL&&root->right==NULL){return;}
if(root->left!=NULL)
{
num++;
if(max<num){max=num;}
dfs(root->left,num);
num--;
}
if(root->right!=NULL)
{
num++;
if(max<num){max=num;}
dfs(root->right,num);
num--;
}
}
int maxDepth(TreeNode* root) {
max=0;
if(root==NULL){return max;}
max=1;
dfs(root,1);
return max;
}
};
105. 从前序与中序遍历序列构造二叉树
主要问题是代码写的太复杂了,可是思路是正确的,这里的递归函数须要设置成返回节点型,注意这种的最后仍是要吧头节点返回来,否则第一个递归函数就没有返回值了
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
public:
TreeNode* dfs(vector<int>& preorder, vector<int>& inorder)
{
if(preorder.size()==0){return NULL;}
if(preorder.size()==1)
{
TreeNode* temp = new TreeNode(preorder[0]);
return temp;
}
int mid = find(inorder.begin(),inorder.end(),preorder[0])-inorder.begin();
TreeNode* root= new TreeNode(preorder[0]);
vector<int> p1(preorder.begin()+1,preorder.begin()+ mid+1);
vector<int> q1(inorder.begin() ,inorder.begin()+ mid);
root->left = dfs(p1,q1);
vector<int> p2(preorder.begin()+mid+1, preorder.end());
vector<int> q2(inorder.begin()+mid+1 ,inorder.end());
root->right =dfs(p2,q2);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size()==0){return NULL;}
TreeNode* root = dfs(preorder,inorder);
return root;
}
};
在递归的过程当中传递了不少参数,代码量减小
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int pos = 0;
return buildTree(preorder, pos, inorder, 0, inorder.size()-1);
}
TreeNode* buildTree(vector<int>& preorder, int& pos, vector<int>& inorder, int left, int right) {
if (pos >= preorder.size()) return 0;
int i = left;
for (i = left; i <= right; ++i) {
if (inorder[i] == preorder[pos]) break;
}
TreeNode* node = new TreeNode(preorder[pos]);
if (left <= i-1) node->left = buildTree(preorder, ++pos, inorder, left, i-1); // 左子树
if (i+1 <= right) node->right = buildTree(preorder, ++pos, inorder, i + 1, right); // 右子树
return node;
}
};
做者:yuexiwen
连接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/c-fen-zhi-by-yuexiwen/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
106. 从中序与后序遍历序列构造二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* dfs(vector<int>& inorder,vector<int>& postorder)
{
if(inorder.size()==0){return NULL;}
if(inorder.size()==1)
{
TreeNode* temp = new TreeNode(inorder[0]);
return temp;
}
int mid = find(inorder.begin(), inorder.end(), postorder[postorder.size()-1] )- inorder.begin();
TreeNode* root = new TreeNode(inorder[mid]);
vector<int> l1(inorder.begin(), inorder.begin()+mid);
vector<int> l2(postorder.begin(), postorder.begin()+mid);
root->left = dfs(l1, l2);
vector<int> r1(inorder.begin()+mid+1, inorder.end());
vector<int> r2(postorder.begin()+mid, postorder.end()-1);
root->right = dfs(r1,r2);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(postorder.size()==0){return NULL;}
TreeNode* root = dfs(inorder,postorder);
return root;
}
};
107. 二叉树的层次遍历 II
彻底能够从上到下遍历,而后拿一个堆栈存放,或者直接返回reverse的结果?!不是更简单,看来在使用堆栈的倒叙功能时,用reverse可能更方便
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
stack<vector<int>> res;
public:
void dfs(vector<TreeNode*> cur)
{
if(cur.size()==0){return;}
vector<int> temp;
vector<TreeNode*> next;
for(auto i:cur)
{
if(i->left!=NULL){next.push_back(i->left);}
if(i->right!=NULL){next.push_back(i->right);}
temp.push_back(i->val);
}
res.push(temp);
dfs(next);
}
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<TreeNode*> temp;
temp.push_back(root);
vector<vector<int>> r;
if(root==NULL){return r;}
dfs(temp);
while(!res.empty())
{
r.push_back(res.top());
res.pop();
}
return r;
}
};
108. 将有序数组转换为二叉搜索树(****)
dfs方法
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return bst(nums,0,nums.size()-1);
}
TreeNode* bst(vector<int>& a,int l,int r){
if(l>r) return NULL;
int mid=(r-l)/2+l;
TreeNode* root=new TreeNode(a[mid]);
root->left=bst(a,l,mid-1);
root->right=bst(a,mid+1,r);
return root;
}
};
做者:dai-52
连接:https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/cdi-gui-jie-fa-by-dai-52-2/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
109. 有序链表转换二叉搜索树
转成数组是一种方法,另一种是使用快慢指针,把中间的找出来,这部分放到dfs最开始的地方
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* dfs(vector<int>& nums, int left, int right)
{
if(left>right) return NULL;
int mid = left+(right-left)/2;
auto root = new TreeNode(nums[mid]);
root->left = dfs(nums,left,mid-1);
root->right = dfs(nums,mid+1,right);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
//其实跟上一题区别不大,只是数组换成了链表,能够把链表转换成数组,而后和上题同样
vector<int> v;
while(head){v.push_back(head->val);head=head->next;}
int len = v.size();
return dfs(v,0,len-1);
}
};
110. 平衡二叉树
有考虑的方法是写一个这个节点下面深度的函数,而后递归每个节点的左右节点进行判断,可是以前求最大深度的代码就写的很复杂
下面这个求深度的代码十分简单,不用进行num的维护每次返回值加1就能够了,代笔层数,这道题双递归函数十分巧妙
三个条件放再一块儿判断会更简便,不过传入单个节点会稍微比较难理解,为何到了叶节点就返回true了
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(!root) return true;
int d = abs(depth(root->left)-depth(root->right)); //当前节点的左右子树的高度差
return (d<=1) && (isBalanced(root->left)) && (isBalanced(root->right));
}
// 求解二叉树深度(104题)
int depth(TreeNode* node)
{
if(node ==NULL) return 0;
return max( depth(node->left), depth(node->right) )+1;
}
};
做者:fly_sky
连接:https://leetcode-cn.com/problems/balanced-binary-tree/solution/c-ban-ben-dai-ma-jian-ji-by-fly_sky/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
111. 二叉树的最小深度
形式基本上是仿照最大深度来的,可是有一点不同,要注意对最小深度的定义,不是出现null就行,而是必须出现叶节点,即自己存在可是左右孩子不存在的,这是惟一的状况,因为root可能会存在左右孩子为null的状况,因此不能将左右孩子直接输入,而是将根节点输入。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minnn(TreeNode* root)
{
if(!root->left && !root->right){return 0;}
if(root->left && !root->right){return minnn(root->left)+1;}
if(!root->left && root->right){return minnn(root->right)+1;}
return min(minnn(root->left),minnn(root->right))+1;
}
int minDepth(TreeNode* root) {
if(!root){return 0;}
return minnn(root)+1;
}
};
112. 路径总和
要注意几点:
1.当根节点为空,其路径和不存在而不是为空,0和空在这里是不同的,以前这个地方就错过
2.这题的终止条件是到叶节点,因此终结条件(正+负)必须是关于叶节点的
3.不管是最大最小仍是其余,逻辑关系都体如今dfs的返回方式的逻辑关系上
4.sum这种变化的值能够做为参数
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool dfs(TreeNode* root, int sum)
{
if(!root->left && !root->right)
{
if(root->val==sum)return true;
return false;
}
if(!root->left && root->right)return dfs(root->right,sum-root->val);
if(!root->right && root->left)return dfs(root->left,sum-root->val);
return dfs(root->left,sum-root->val) || dfs(root->right,sum-root->val);
}
bool hasPathSum(TreeNode* root, int sum) {
if(!root)return false;
return dfs(root,sum);
}
};
113. 路径总和 II
难点是如何应对何时存节点,何时放节点的问题,这个能够根据例子倒推一下
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
vector<vector<int>> res;
vector<int> path;
public:
void dfs(TreeNode* root,int sum)
{
if(!root->left && !root->right)
{
path.push_back(root->val);
if(root->val==sum) res.push_back(path);
path.pop_back();
return;
}
if(root->left)
{
path.push_back(root->val);
dfs(root->left,sum-root->val);
path.pop_back();
}
if(root->right)
{
path.push_back(root->val);
dfs(root->right,sum-root->val);
path.pop_back();
}
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if(!root)return res;
dfs(root,sum);
return res;
}
};
114. 二叉树展开为链表
先先序遍历展开为一列,而后变成链表,先序遍历的代码时固定的,就像求最大深度那样要记住
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
vector<int> list;
public:
//先序遍历
void dfs(TreeNode* root)
{
if(!root ) return ;
list.push_back(root->val);
dfs(root->left);
dfs(root->right);
}
void dfs2(TreeNode* root,int pos, vector<int> list)
{
if(pos==list.size()) return;
TreeNode* temp = new TreeNode(list[pos]);
root->left = NULL;
root->right = temp;
dfs2(temp,pos+1,list);
}
void flatten(TreeNode* root) {
//作一下层序遍历,求出数组,而后都放到右孩子上
if(!root)return;
dfs(root);
dfs2(root,1,list);
return;
}
};
115. 不一样的子序列
关于字符串的题使用递归由超时了,可是思路应该时对的:把t中的每一个字符在s中的位置求出来并组成一个二维数组,里面存放每一个t中字符的位置,而后对这个dfs递归计数,在值小于前一个个时须要进行剪枝,这个递归和求全部根节点到子节点时的模板很是像
class Solution {
public:
void dfs(int& num,vector<int>& path, int pos, vector<vector<int>>& board)
{
if(path.size()==board.size())
{
num++;
return;
}
for(int i:board[pos])
{
if( pos==0 || (pos>0 && i>path[path.size()-1]) )
{
path.push_back(i);
dfs(num,path,pos+1,board);
path.pop_back();
}
}
}
int numDistinct(string s, string t) {
if(s.empty())return 0;
int lens = s.size();
int lent = t.size();
vector<vector<int>> board;
for(int i = 0 ; i<lent ; i++)
{
vector<int> temp;
for(int j = 0; j<lens ; j++)
{
if(s[j]==t[i])
{
temp.push_back(j);
}
}
board.push_back(temp);
}
int num = 0;
vector<int> path;
int pos = 0;
dfs(num,path,pos,board);
return num;
}
};
116. 填充每一个节点的下一个右侧节点指针(bfs)
dfs是深度优先遍历,有前序中序后序,参数为根节点;bfs是广度优先遍历,没有什么序之说,在遍历是后习惯用一个数组存放每一层的全部节点或者节点值,参数为数组
一般bfs用非递归队列比较多,可是用递归也能够较好的解决一些问题,自由的对结果进行调整,可是队列很差拿出来
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
vector<vector<Node*>> res;
public:
void bfs(vector<Node*> cur)
{
if(cur.empty())return;
vector<Node*> temp;
for(auto i:cur)
{
if(i->left)temp.push_back(i->left);
if(i->right)temp.push_back(i->right);
}
bfs(temp);
res.push_back(temp);
}
Node* connect(Node* root) {
if(!root) return NULL;
vector<Node*> cur;
cur.push_back(root);
res.push_back(cur);
bfs(cur);
for(auto i : res)
{
if(i.size()==1){continue;}
int m = i.size();
for(int j = 0 ; j< m-1; j++)
{
i[j]->next=i[j+1];
}
}
return root;
}
};
117. 填充每一个节点的下一个右侧节点指针 II(bfs)
和116的代码一摸同样
118. 杨辉三角
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res;
if(numRows==0) return res;
vector<int> t = {1};
res.push_back(t);
if(numRows==1) return res;
t.push_back(1);
res.push_back(t);
if(numRows==2) return res;
numRows -=2;
vector<int> cur = {1,1};
while(numRows--)
{
vector<int> temp;
temp.push_back(1);
int len = cur.size();
for(int i = 0 ; i<len-1 ; i++)
{
temp.push_back(cur[i]+cur[i+1]);
}
temp.push_back(1);
cur.assign(temp.begin(),temp.end());
res.push_back(cur);
}
return res;
}
};
119. 杨辉三角 II
class Solution {
public:
vector<int> getRow(int numRows) {
vector<int> t = {1};
if(numRows==0) return t;
t.push_back(1);
if(numRows==1) return t;
numRows -=1;
vector<int> cur = {1,1};
while(numRows--)
{
vector<int> temp;
temp.push_back(1);
int len = cur.size();
for(int i = 0 ; i<len-1 ; i++)
{
temp.push_back(cur[i]+cur[i+1]);
}
temp.push_back(1);
cur.assign(temp.begin(),temp.end());
}
return cur;
}
};
额外的空间也能够不使用,可是要修改原数据,不太好,因此就用了额外的 n*sizeof(int)的空间。
line用于记录n层到n-1层最短的路径长度,其初始值为triangle的第n行。其递归公式为:
line[j] = triangle[i][j] + min(line[j], line[j + 1]),i 表示当前自下向上到达第 i 层。
line[j]=triangle[i][j]+min(line[j],line[j+1]),i表示当前自下向上到达第i层。
做者:liushang-leecode
连接:https://leetcode-cn.com/problems/triangle/solution/dong-tai-gui-hua-zi-di-xiang-shang-ke-yi-shi-yong-/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<int> line(triangle[n - 1]);
for (int i = n - 2; i >= 0; i--)
for (int j = 0; j <= i; j++)
line[j] = triangle[i][j] + min(line[j], line[j + 1]);
return line[0];
}
};
做者:liushang-leecode
连接:https://leetcode-cn.com/problems/triangle/solution/dong-tai-gui-hua-zi-di-xiang-shang-ke-yi-shi-yong-/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
121. 买卖股票的最佳时机(dp)
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty())return 0;
int dp=prices[0],res = 0;
for(int i = 1; i< (int)prices.size() ;i++)
{
dp = min(dp,prices[i]);
res = max(res, prices[i]-dp);
}
return res;
}
};
一次遍历法,不是特别好理解
class Solution {
public:
int maxProfit(vector<int>& prices) {
int inf = 1e9; //很大的值
int minprice = inf, maxprofit = 0;
for (int price: prices) {
maxprofit = max(maxprofit, price - minprice);
minprice = min(price, minprice);
}
return maxprofit;
}
};
做者:LeetCode-Solution
连接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if(len==0 || len==1)return 0;
int minvalue = prices[0];
int maxvalue = INT_MIN;
for(int i = 1 ; i<len ; i++)
{
minvalue = min(minvalue,prices[i-1]);
maxvalue = max(maxvalue,prices[i]-minvalue);
}
if(maxvalue<0)return 0;
return maxvalue;
}
};
动态规划法
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n == 0) return 0; // 边界条件
int minprice = prices[0];
vector<int> dp (n, 0); //新建一个数组
//在动态变化中维护了最小值,老是能得到这个点以前的最小值
//最后原本不用再和本身比较了,可是题目有一个特殊要求,就是不能小于0,因此再生成这个动态数组的时候,每次都要和0比较,若是小于0就不要了
for (int i = 1; i < n; i++){
minprice = min(minprice, prices[i]);
dp[i] = max(dp[i - 1], prices[i] - minprice);
}
return dp[n - 1];
}
};
做者:z1m
连接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/gu-piao-wen-ti-python3-c-by-z1m/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
122. 买卖股票的最佳时机 II
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
for(int i=1; i< (int)prices.size() ;i++)
{
res += (prices[i]>prices[i-1])?(prices[i]-prices[i-1]):0;
}
return res;
}
};
这道题不适合动态规划,能够用贪心结合双指针作
不用非等到上升到最高点才买,只要上升一次就买一次,低了就不动
class Solution {
public:
int maxProfit(vector<int>& prices) {
//快慢指针标记
int i=0,j=1,sum=0;
//判断vector大小
if(prices.size()<=1)
return 0;
//两个指针一直紧挨在一块儿,只有j的值大于i的值时,就把差值加入sum中
while(j<prices.size()){
if(prices[j]-prices[i]>0)
sum+=(prices[j]-prices[i]);
i++;
j++;
}
return sum;
}
};
做者:zhong-zhong-ban-da-dui-chang
连接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/ctan-xin-suan-fa-by-zhong-zhong-ban-da-dui-chang/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
123. 买卖股票的最佳时机 III
是在上一题的基础上作的,可是次数再多就不行了,并且这种双循环方式也超时了,可是思路是对的
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty())return 0;
int res1 = 0, dp1 = prices[0], res = 0;
for(int i =1 ; i< (int)prices.size() ;i++)
{
dp1 = min(dp1, prices[i]);
res1 = max(res1, prices[i]-dp1);
int dp2 = prices[i];
int res2 = 0;
for(int j = i+1 ; j<(int)prices.size() ;j++)
{
dp2 = min(dp2, prices[j]);
res2 = max(res2, prices[j]-dp2);
}
res = max(res, res1+res2);
}
return res;
}
};
124. 二叉树中的最大路径和(dfs,不懂)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//一个 根,左,右 的路径状况有(根,左+根,根+右,左+根+右)
//可是该根做为其父亲的孩子时,其max 应该为 max(根,左+根,根+右).若是包含左+根+右,则加上其父亲就构不成路径了
int maxPathSum(TreeNode* root) {
long long gMax = LLONG_MIN;
maxPathSumCore(root, gMax);
return gMax;
}
int maxPathSumCore(TreeNode* root, long long& gMax){
if(root==nullptr) return 0;
int curVal = root->val;
int leftMax = maxPathSumCore(root->left, gMax);
int rightMax = maxPathSumCore(root->right, gMax);
long long curMax = max(curVal, max(curVal+leftMax, max(curVal+rightMax, curVal+leftMax+rightMax)));
if(curMax>gMax) gMax = curMax;
return max(curVal, max(curVal+leftMax, curVal+rightMax));
}
};
做者:lou-ding-_shai-tai-yang
连接:https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/di-gui-dang-qian-jie-dian-de-zui-da-lu-jing-he-dan/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
128. 最长连续序列
很简便的作法,稍难理解
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.empty()){
return 0;
}
unordered_set<int> myset(nums.begin(), nums.end());
int res = 0;
for(auto num : nums){
if(myset.count(num-1)==0){
int x = num + 1;
while(myset.count(x)){
x ++;
}
res = max(res, x-num);
}
}
return res;
}
};
做者:anyaleung
连接:https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/cdai-ma-li-yong-unordered_set-by-anyaleung/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
129. 求根到叶子节点数字之和
字符串转数字
int num = 0 ;
string s = "sdfsf";
num = std::atoi(s.c_str());
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
vector<string> res;
string s;
public:
void dfs(TreeNode* root)
{
if(!root->left && !root->right)
{
s = s + to_string(root->val);
res.push_back(s);
s.pop_back();
}
if(root->left)
{
s = s + to_string(root->val);
dfs(root->left);
s.pop_back();
}
if(root->right)
{
s = s + to_string(root->val);
dfs(root->right);
s.pop_back();
}
}
int sumNumbers(TreeNode* root) {
if(!root)return 0;
dfs(root);
int sum = 0;
for(auto i:res)
{
sum += atoi(i.c_str());
}
return sum;
}
};
130. 被围绕的区域
本身写的递归十分的复杂,主要问题在于,在判断的过程当中就把不是本位置的元素给改了,致使路径上发生变化,看了解答,发现是思路错了,或者说这道题逆向思惟一下很是好作,就像数学选择题里面的举反例同样
被围绕的区间不会存在于边界上,换句话说,任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上,或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。若是两个元素在水平或垂直方向相邻,则称它们是“相连”的。
做者:ZZYuting
连接:https://leetcode-cn.com/problems/surrounded-regions/solution/cbeats-9465easy-to-understand-by-zzyuting/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
/*
First, check the four border of the matrix. If there is a element is
'O', alter it and all its nei***or 'O' elements to '1'.
Then ,alter all the 'O' to 'X'
At last,alter all the '1' to 'O'
For example:
X X X X X X X X X X X X
X X O X -> X X O X -> X X X X
X O X X X 1 X X X O X X
X O X X X 1 X X X O X X
*/
class Solution {
public:
void solve(vector<vector<char>>& board) {
if(board.size()==0){
return;
}
int rows=board.size(),cols=board[0].size();
//对边界上的进行dfs
for(int i=0;i<rows;i++){
dfs(board,i,0);
dfs(board,i,cols-1);
}
for(int j=1;j<cols-1;j++){
dfs(board,0,j);
dfs(board,rows-1,j);
}
//遍历所有的,1变0,其余为X,很巧妙的先把这些量都标出来来了
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(board[i][j]=='1'){
board[i][j]='O';
}
else{
board[i][j]='X';
}
}
}
}
private:
void dfs(vector<vector<char>>& board,int i,int j){
//若是既不在边界上并且又为X的直接跳过,当此边界上的点为0时才有动做
//若是在边界上为O,就直接改为1
if(i>=0&&i<board.size()&&j>=0&&j<board[0].size()&&board[i][j]=='O'){
board[i][j]='1';
dfs(board,i-1,j);
dfs(board,i+1,j);
dfs(board,i,j-1);
dfs(board,i,j+1);
}
}
};
做者:ZZYuting
连接:https://leetcode-cn.com/problems/surrounded-regions/solution/cbeats-9465easy-to-understand-by-zzyuting/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
在这里插入代码片
144. 二叉树的前序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
vector<int> res;
public:
void dfs(TreeNode* root)
{
if(root==NULL)return;
res.push_back(root->val);
dfs(root->left);
dfs(root->right);
}
vector<int> preorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
};
146. LRU缓存机制
使用哈希map和双链表:
逻辑
// key 映射到 Node(key, val)
HashMap<Integer, Node> map;
// Node(k1, v1) <-> Node(k2, v2)...
DoubleList cache;
int get(int key) {
if (key 不存在) {
return -1;
} else {
将数据 (key, val) 提到开头;
return val;
}
}
void put(int key, int val) {
Node x = new Node(key, val);
if (key 已存在) {
把旧的数据删除;
将新节点 x 插入到开头;
} else {
if (cache 已满) {
删除链表的最后一个数据腾位置;
删除 map 中映射到该数据的键;
}
将新节点 x 插入到开头;
map 中新建 key 对新节点 x 的映射;
}
}
较简化的版本
class LRUCache {
public:
//删除、查找、插入的复杂度都O(1)
LRUCache(int capacity) {
cap=capacity;
}
int get(int key) {
if(hashtable.count(key)==0) return -1;
else//更新到表头
{
auto iter = hashtable[key];//找到对应结点地址
cache.splice(cache.begin(),cache,iter);//移动到链表头
return cache.begin()->second;//返回value
}
}
void put(int key, int value) {
if(hashtable.count(key)==0) {
//若是容量到了,删除尾部元素,再加上新结点
if(cache.size()==cap) {
hashtable.erase(cache.back().first);
cache.pop_back();
}//直接添加
cache.push_front(make_pair(key,value));
hashtable[key]=cache.begin();
}
else {//若是插入相同key的元素,除了要移动,value也须要更新
auto iter = hashtable[key];
iter->second=value;//更新地址value
cache.splice(cache.begin(),cache,iter);//移动到链表头
hashtable[key]=cache.begin(); //更新hashtable的value
}
}
unordered_map<int,list<pair<int,int>>::iterator> hashtable;
list<pair<int,int>> cache;//key value
int cap=0;
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
做者:tong-guai
连接:https://leetcode-cn.com/problems/lru-cache/solution/ha-xi-shuang-xiang-lian-biao-you-hua-ban-ben-by-to/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
class LRUCache {
public:
LRUCache(int capacity) {
_capacity = capacity;
}
int get(int key) {
if(_map.count(key) != 0)
{
int ret = (*_map[key]).second;
_list.erase(_map[key]);
_list.push_front({key, ret});
_map[key] = _list.begin();
return ret;
}
else return -1;
}
void put(int key, int value) {
if(_map.count(key) == 0)
{
if(_list.size() == _capacity)
{
int k = _list.back().first;
_map.erase(_map.find(k));
_list.pop_back();
}
}
else{
_list.erase(_map[key]);
_map.erase(_map.find(key));
}
_list.push_front({key, value});
_map[key] = _list.begin();
}
private:
unordered_map<int, list<pair<int, int>>::iterator> _map;
list<pair<int, int>> _list;
int _capacity;
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
做者:ma-te-zai-wei-ma
连接:https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-ma-te-zai-wei-ma/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
150. 逆波兰表达式求值
用bool判断第一个符号而且用一个值储存结果是很麻烦的事,不如就一直将结果放在堆栈中
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<string> st;
//bool flag = true;第一次遇到的符号须要特殊处理,用flag来表示是不是第一个
for(auto token:tokens)
{
if(token=="+")
{
int t1 =atoi(st.top().c_str());
st.pop();
int t2 = atoi(st.top().c_str());
st.pop();
st.push(to_string(t1+t2));
}
else if(token=="-")
{
int t1 =atoi(st.top().c_str());
st.pop();
int t2 = atoi(st.top().c_str());
st.pop();
st.push(to_string(t2-t1));
}
else if(token=="*")
{
int t1 =atoi(st.top().c_str());
st.pop();
int t2 = atoi(st.top().c_str());
st.pop();
st.push(to_string(t1*t2));
}
else if(token=="/")
{
int t1 =atoi(st.top().c_str());
st.pop();
int t2 = atoi(st.top().c_str());
st.pop();
st.push(to_string(t2/t1));
}
else
{
st.push(token);
}
}
return atoi(st.top().c_str());
}
};
152. 乘积最大子数组(dp)
解题思路
这题是求数组中子区间的最大乘积,对于乘法,咱们须要注意,负数乘以负数,会变成正数,因此解这题的时候咱们须要维护两个变量,当前的最大值,以及最小值,最小值可能为负数,但没准下一步乘以一个负数,当前的最大值就变成最小值,而最小值则变成最大值了。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = INT_MIN , imax = 1, imin =1;
for(int i = 0 ; i< (int)nums.size() ;i++)
{
if(nums[i]<0)swap(imax,imin);
imax = max(nums[i],imax*nums[i]);
imin = min (nums[i],imin*nums[i]);
res = max(res,imax);
}
return res;
}
};
153. 寻找旋转排序数组中的最小值
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums[0]<=nums.back())return nums[0];
int left = 0 , right = nums.size();
while(left<right)
{
int mid = left+(right-left)/2;
if(nums[mid]>=nums[0])
{left=mid+1;}
else
{right=mid;}
}
return nums[left];
}
};
155. 最小栈
使用两个队列,可是会超时
class MinStack {
private:
queue<int> q1;
queue<int> q2;
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
if(q1.empty()&&q2.empty())q1.push(x);
else if(q1.empty())q2.push(x);
else if(q2.empty())q1.push(x);
}
void pop() {
if(q1.empty())
{
while(q2.size()>1)
{
q1.push(q2.front());
q2.pop();
}
q2.pop();
}
else
{
while(q1.size()>1)
{
q2.push(q1.front());
q1.pop();
}
q1.pop();
}
}
int top() {
int res;
if(q1.empty())
{
while(q2.size()>1)
{
q1.push(q2.front());
q2.pop();
}
res = q2.front();
q1.push(q2.front());
q2.pop();
}
else
{
while(q1.size()>1)
{
q2.push(q1.front());
q1.pop();
}
res = q1.front();
q2.push(q1.front());
q1.pop();
}
return res;
}
int getMin() {
int res = INT_MAX;
if(q1.empty())
{
while(!q2.empty())
{
res = min(res, q2.front());
q1.push(q2.front());
q2.pop();
}
}
else
{
while(!q1.empty())
{
res = min(res,q1.front());
q2.push(q1.front());
q1.pop();
}
}
return res;
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
一个栈s存放数据,另外一个栈min存放前栈中最小的数据
class MinStack {
public:
stack<int> s;//数据栈
stack<int> min;//辅助栈
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
s.push(x);
if(min.empty()||x<=min.top())
{
min.push(x);
}
}
void pop() {
if(s.top()==min.top())
min.pop();
s.pop();
}
int top() {
return s.top();
}
int getMin() {
return min.top();
}
};
做者:chenlele
连接:https://leetcode-cn.com/problems/min-stack/solution/zui-xiao-zhan-by-gpe3dbjds1/
来源:力扣(LeetCode)
著做权归做者全部。商业转载请联系做者得到受权,非商业转载请注明出处。
162. 寻找峰值
直接作是不符合要求的,看到logN应该直接想到使用二分法
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int len =nums.size();
if(len==0 || len ==1) return 0;
if(len==2)
{
int i = nums[0]>nums[1]? 0:1;
return i;
}
for(int i = 1 ; i<len-1 ;i++)
{
if(nums[i]>nums[i-1] && nums[i]>nums[i+1]) return i;
}
if(nums[0]>nums[1])return 0;
if(nums[len-1]>nums[len-2])return len-1;
return INT_MIN;
}
};
以前作过一道两数之和的,因此 在这里面使用了查找法,凡是查找须要遍历,因此这样作会超时,更好的办法是双指针一个在前一个在后,这里双指针法更好的缘由是数组已经排序好了,,能够有规律的缩小双指针的范围
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int len = numbers.size();
for(int i = 0 ;i<len ;i++)
{
auto iter = find(numbers.begin()+i+1,numbers.end(), target- numbers[i]);
if( iter!=numbers.end())
{
int temp = iter-numbers.begin();
vector<int> res={i+1,temp+1};
return res;
}
}
return {};
}
};
169. 多数元素
class Solution {
public:
int majorityElement(vector<int>& nums) {
int len = nums.size();
if(len==1) return nums[0];
sort(nums.begin(),nums.end());
return nums[len/2];
}
};
179. 最大数
一开始想的是把全部数字都变成数组的形式,而后使用sort进行排序,可是会有一个问题,30和3进行比较的话确定会认为30大而且在前,可是最后303显然没有330大,因此这种方法是有问题的
题目解析:根据题目中给的例子来看,主要就是要给给定数组进行排序,可是排序方法不是普通的升序或者降序,由于9要排在最前面,而9既不是数组中最大的也不是最小的,因此咱们要自定义排序方法。对于两个数字a和b来讲,若是将其都转为字符串,若是ab > ba,则a排在前面,好比9和34,因为934>349,因此9排在前面,再好比说30和3,因为303<330,因此3排在30的前面。按照这种规则对原数组进行排序后,将每一个数字转化为字符串再链接起来就是最终结果。
————————————————
版权声明:本文为CSDN博主「pushup8」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处连接及本声明。
原文连接:https://blog.csdn.net/pushup8/article/details/85196465
class Solution {
public:
string largestNumber(vector<int>& nums) {
string res = "";
sort(nums.begin(), nums.end(), [](int a, int b){
return to_string(a) + to_string(b) > to_string(b) + to_string(a);
});
for(auto num : nums){
res += to_string(num);
}
return res[0] == '0' ? "0" : res;
}
};
本身写的
注意sort函数重写的四个要素1.static2.inline3.const4.&
class Solution {
public:
static inline bool func(const string& a, const string& b)
{
return a+b>b+a;
}
string largestNumber(vector<int>& nums) {
vector<string> st;
//st.assign(nums.begin(),nums.end());
for(auto i:nums)st.push_back(to_string(i));
sort(st.begin(),st.end(),func);
string res;
for(auto i:st)res += i;
while( (int)res.size()>1 && res[0]=='0')res = res.substr(1,(int)res.size()-1);
return res;
}
};
189. 旋转数组
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int len = nums.size();
reverse(nums.begin(),nums.end