1. 两数之和(easy)
2023/1/8
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
我的答案
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int a, b;
int* res;
int i, j;
for( i = 0; i < numsSize - 1; i++ ){
for( j = i + 1; j < numsSize; j++ ){
if( nums[i] + nums[j] == target ){
*returnSize = 2;
res = (int*)malloc(sizeof(int) * 2);
res[0] = i;
res[1] = j;
return res;
}
}
}
*returnSize = 0;
return NULL;
}
- 基本是暴力枚举,更好的做法是使用哈希表来降低时间复杂度,但相应地会增加空间复杂度.
参考答案
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i;
}
return {};
}
};
感想
第一次接触C++里的unordered_map,可以很方便地使用哈希表.
2. 两数相加(medium)
2023/3/5
题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围
[1, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
我的答案
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
#include <stdlib.h>
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode* head, *tail, * temp;
int carry = 0, res = 0, val1, val2;
head = NULL;
tail = NULL;
while(l1 != NULL || l2 != NULL || carry ){
temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->val = 0;
temp->next = NULL;
if(l1 == NULL){
val1 = 0;
}else{
val1 = l1->val;
l1 = l1->next;
}
if(l2 == NULL){
val2 = 0;
}else{
val2 = l2->val;
l2 = l2->next;
}
res = val1 + val2;
if(res + carry > 9){
res = res - 10 + carry;
carry = 0;
temp->val = res;
carry = 1;
}else{
res = res + carry;
carry = 0;
temp->val = res;
}
if(head == NULL){
head = temp;
tail = head;
}else{
tail->next = temp;
tail = tail->next;
}
}
return head;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = nullptr, *tail = nullptr;
int carry = 0;
while(l1 || l2 || carry){
int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;
int sum = n1 + n2 + carry;
if(!head){
head = tail = new ListNode(sum % 10);
}else{
tail->next = new ListNode(sum % 10);
tail = tail->next;
}
carry = sum / 10;
if(l1){
l1 = l1->next;
}
if(l2){
l2 = l2->next;
}
}
return head;
}
};
- 先用C写的,AC了之后看了题解,思路基本是一样的,细节有所出入,跟着题解写了一遍C++的版本,思路很简单,就是借鉴加法的原理,只不过要用链表实现.
参考答案
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = nullptr, *tail = nullptr;
int carry = 0;
while (l1 || l2) {
int n1 = l1 ? l1->val: 0;
int n2 = l2 ? l2->val: 0;
int sum = n1 + n2 + carry;
if (!head) {
head = tail = new ListNode(sum % 10);
} else {
tail->next = new ListNode(sum % 10);
tail = tail->next;
}
carry = sum / 10;
if (l1) {
l1 = l1->next;
}
if (l2) {
l2 = l2->next;
}
}
if (carry > 0) {
tail->next = new ListNode(carry);
}
return head;
}
};
感想
最近这段时间一直在学C++的语法,后面的题都打算用C++来写了,边写边学
3. 无重复字符的最长子串(medium)
2023/3/6
题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
我的答案
class Solution {
public:
int lengthOfLongestSubstring(string s) {
string sub;
int len = 0, max = 0;
for(int i = 0; i < s.length(); i++){
int pos = sub.find(s[i]);
sub += s[i];
if(pos != string::npos){
len = sub.length()-1;
max = (len > max) ? len : max;
sub.erase(0,pos+1);
}
}
len = sub.length();
return (len > max) ? len : max;
}
};
- 还有可以优化的空间,当max已经大于剩余子串的长度时,可以直接return
参考答案
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 哈希集合，记录每个字符是否出现过
unordered_set<char> occ;
int n = s.size();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
// 枚举左指针的位置，初始值隐性地表示为 -1
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.erase(s[i - 1]);
}
while (rk + 1 < n && !occ.count(s[rk + 1])) {
// 不断地移动右指针
occ.insert(s[rk + 1]);
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1);
}
return ans;
}
};
感想
第一次接触滑动窗口,边写边优化,自己摸爬滚打写出了这个代码,值得鼓励的是自己想出来的滑动窗口,并且时间和内存都比官方题解给的代码低!
同时也是第一次独立使用C++写出来的程序
4. 寻找两个正序数组的中位数(hard)
2023/3/8
题目描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
我的答案
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len = nums1.size() + nums2.size();
int pos1 = 0, pos2 = 0;
double res = 0;
if(len%2){
for(int i = 0; i <= len/2; i++){
if(pos1 >= nums1.size()){
res = nums2[pos2++];
continue;
}else if(pos2 >= nums2.size()){
res = nums1[pos1++];
continue;
}
if(nums1[pos1] >= nums2[pos2]){
res = nums2[pos2++];
}else{
res = nums1[pos1++];
}
}
return res;
}else{
for(int i = 0; i < len/2; i++){
if(pos1 >= nums1.size()){
res = nums2[pos2++];
continue;
}else if(pos2 >= nums2.size()){
res = nums1[pos1++];
continue;
}
if(nums1[pos1] >= nums2[pos2]){
res = nums2[pos2++];
}else{
res = nums1[pos1++];
}
}
double res2;
if(pos1 >= nums1.size()){
res2 = nums2[pos2++];
return (res + res2)/2.0;
}else if(pos2 >= nums2.size()){
res2 = nums1[pos1++];
return (res + res2)/2.0;
}
if(nums1[pos1] >= nums2[pos2]){
res2 = nums2[pos2++];
}else{
res2 = nums1[pos1++];
}
return (res + res2)/2.0;
}
}
};
- 是一种较容易想到的方法,双指针,具体细节还有优化空间,但总体的时间复杂度是O(m+n),空间复杂度是O(1)
参考答案
class Solution {
public:
int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
/* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
* 这里的 "/" 表示整除
* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
* 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
* 这样 pivot 本身最大也只能是第 k-1 小的元素
* 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
* 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
* 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
*/
int m = nums1.size();
int n = nums2.size();
int index1 = 0, index2 = 0;
while (true) {
// 边界情况
if (index1 == m) {
return nums2[index2 + k - 1];
}
if (index2 == n) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return min(nums1[index1], nums2[index2]);
}
// 正常情况
int newIndex1 = min(index1 + k / 2 - 1, m - 1);
int newIndex2 = min(index2 + k / 2 - 1, n - 1);
int pivot1 = nums1[newIndex1];
int pivot2 = nums2[newIndex2];
if (pivot1 <= pivot2) {
k -= newIndex1 - index1 + 1;
index1 = newIndex1 + 1;
}
else {
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int totalLength = nums1.size() + nums2.size();
if (totalLength % 2 == 1) {
return getKthElement(nums1, nums2, (totalLength + 1) / 2);
}
else {
return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
}
}
};
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.size();
int n = nums2.size();
int left = 0, right = m;
// median1：前一部分的最大值
// median2：后一部分的最小值
int median1 = 0, median2 = 0;
while (left <= right) {
// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
int i = (left + right) / 2;
int j = (m + n + 1) / 2 - i;
// nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
int nums_im1 = (i == 0 ? INT_MIN : nums1[i - 1]);
int nums_i = (i == m ? INT_MAX : nums1[i]);
int nums_jm1 = (j == 0 ? INT_MIN : nums2[j - 1]);
int nums_j = (j == n ? INT_MAX : nums2[j]);
if (nums_im1 <= nums_j) {
median1 = max(nums_im1, nums_jm1);
median2 = min(nums_i, nums_j);
left = i + 1;
} else {
right = i - 1;
}
}
return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
}
};
- 第一种优化方式,利用二分查找,每次将\(\frac{k}{2}\)之前的都可以跳过遍历,时间复杂度降为O(log(m+n))
- 方法二划分数组,暂时还没有理解,等以后再看看
感想
第一次写hard难度,这道题不是很难,整个过程不超过半个小时,算法比较普通,想到了更好的解法(answer1),由于懒(bushi),没有付出行动
5. 最长回文子串(medium)
2023/3/8
题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
我的答案
class Solution {
public:
string longestPalindrome(string s) {
int size = s.size(), pos, max = 0, len = 0;
if(size == 0 || size == 1){
return s;
}
for(int i = 0; i < size - max; i++){
int j = i;
int k = s.find(s[i], j + 1);
while(k != string::npos){
if(k - i + 1 < max){
j = k;
k = s.find(s[i], j + 1);
continue;
}else if(IsPalindrome(s.substr(i, k - i + 1))){
max = k - i + 1;
pos = i;
}
j = k;
k = s.find(s[i], j + 1);
}
}
if(max == 0){
return {s[0]};
}
return s.substr(pos, max);
}
bool IsPalindrome(string s) {
int pl = 0, pr = s.size() - 1;
while(pl < pr){
if(s[pl++] != s[pr--]){
return false;
}
}
return true;
}
};
class Solution {
public:
string longestPalindrome(string s) {
int size = s.size();
bool **dp = new bool*[size] ();
for(int i = 0; i < size; i++){
dp[i] = new bool[size] ();
}
for(int i = 0; i < size; i++){
dp[i][i] = true;
}
int maxLen = 1, begin = 0;
for(int L = 2; L <= size; L++){
for(int i = 0; i < size; i++){
int j = i + L - 1;
if(j >= size){
break;
}
if(s[i] != s[j]){
dp[i][j] = false;
}else{
if(i == j - 1){
dp[i][j] = true;
}else{
dp[i][j] = dp[i + 1][j - 1];
}
if(dp[i][j] && L > maxLen){
maxLen = L;
begin = i;
}
}
}
}
return s.substr(begin, maxLen);
}
};
2023/3/25刷夜时耐心研究了动态规划的算法题，本题是第一道AC的动态规划
参考答案
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
vector<vector<int>> dp(n, vector<int>(n));
// 初始化：所有长度为 1 的子串都是回文串
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= n; L++) {
// 枚举左边界，左边界的上限设置可以宽松一些
for (int i = 0; i < n; i++) {
// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界，就可以退出当前循环
if (j >= n) {
break;
}
if (s[i] != s[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substr(begin, maxLen);
}
};
class Solution {
public:
pair<int, int> expandAroundCenter(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
--left;
++right;
}
return {left + 1, right - 1};
}
string longestPalindrome(string s) {
int start = 0, end = 0;
for (int i = 0; i < s.size(); ++i) {
auto [left1, right1] = expandAroundCenter(s, i, i);
auto [left2, right2] = expandAroundCenter(s, i, i + 1);
if (right1 - left1 > end - start) {
start = left1;
end = right1;
}
if (right2 - left2 > end - start) {
start = left2;
end = right2;
}
}
return s.substr(start, end - start + 1);
}
};
- 第一个参考答案是动态规划,第二个是"中心扩展算法"
感想
写了两个半小时才AC,全部删了重新改了两遍,前两遍都想用"聪明"的办法解决,失败后无奈只能暴力破解,但时间复杂度是\(O(n^3)\),太高了,超出时间限制,通过一些局部的小改变优化了一点,硬生生地AC了,代码并不美观.时间和空间复杂度都很高.
本来想着把动态规划的解法放一放，没想到下一题（第10题）又是动态规划，于是回来重新写了一遍这道题，仅用20分钟AC
10. 正则表达式匹配(hard)
2023/3/26
题目描述
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
提示：
1 <= s.length <= 201 <= p.length <= 20s只包含从a-z的小写字母。p只包含从a-z的小写字母，以及字符.和*。- 保证每次出现字符
*时，前面都匹配到有效的字符
我的答案
class Solution {
public:
bool isMatch(string s, string p) {
int s_size = s.size();
int p_size = p.size();
bool ** dp = new bool*[s_size + 1]();
for(int i = 0; i < s_size + 1; i++){
dp[i] = new bool[p_size + 1]();
}
dp[0][0] = true;
for(int j = 2; j < p_size + 1; j++){
if(p[j - 1] == '*'){
dp[0][j] = dp[0][j - 2];
}else{
dp[0][j] = false;
}
}
//遍历开始
for(int j = 1; j < p_size + 1; j++){
for(int i = 1; i < s_size + 1; i++){
if(s[i - 1] == p[j - 1] || p[j - 1] == '.'){
dp[i][j] = dp[i - 1][j - 1];
// if(dp[i][j])
// break;
}else if(p[j - 1] != '*'){
dp[i][j] = false;
}else if(p[j - 1] == '*'){
if(s[i - 1] == p[j - 2] || p[j - 2] == '.'){
// if(i == 1){
// dp[i][j] = dp[i][j - 2];
// }
dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
}else{
dp[i][j] = dp[i][j - 2];
}
}
}
}
return dp[s_size][p_size];
}
};
参考答案
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
auto matches = [&](int i, int j) {
if (i == 0) {
return false;
}
if (p[j - 1] == '.') {
return true;
}
return s[i - 1] == p[j - 1];
};
vector<vector<int>> f(m + 1, vector<int>(n + 1));
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
f[i][j] |= f[i][j - 2];
if (matches(i, j - 1)) {
f[i][j] |= f[i - 1][j];
}
}
else {
if (matches(i, j)) {
f[i][j] |= f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
};
感想
- 第一次写这道题是在2023/3/13,当时还不会动态规划,用双指针写了很久没有写出来,最多只通过了三分之二的测试点,无奈放弃,看了题解才知道这题最好要使用动态规划,想到第5题也是动态规划还搁置在那,于是停了一段时间的刷题(还有一部分原因是这段时间很迷茫,不知道努力的方向...)
- 第二次写正则表达式的时候已是2023/3/26凌晨,刚写完第五题最长回文子串,趁对动态规划题型的手感还在,赶紧来写这道题,顺利地完成了coding...
- 然而,应了那句老话,程序员有百分之八十的时间都在debug,在我长达一个小时的debug之后,终于发现原来问题出在递推公式某一个情况的分析不够全面(line 33),果然,动态规划的难点就在递推公式上.
11. 盛最多水的容器(medium)
2023/4/4
题目描述
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
提示：
n == height.length2 <= n <= 1050 <= height[i] <= 104
我的答案
class Solution {
public:
int maxArea(vector<int>& height) {
int n = height.size();
int p1 = 0, p2 = n - 1;
int max = (n - 1) * ((height[p1] < height[p2]) ? height[p1] : height[p2]);
while(p1 < p2){
if(height[p1] >= height[p2]){
int height_temp = height[p2];
while(height_temp >= height[p2] && p1 < p2){
--p2;
}
}else{
int height_temp = height[p1];
while(height_temp >= height[p1] && p1 < p2){
++p1;
}
}
int temp = ( (height[p1] < height[p2]) ? height[p1] : height[p2] ) * (p2 - p1);
max = (max > temp) ? max : temp;
}
return max;
}
};
参考答案
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1;
int ans = 0;
while (l < r) {
int area = min(height[l], height[r]) * (r - l);
ans = max(ans, area);
if (height[l] <= height[r]) {
++l;
}
else {
--r;
}
}
return ans;
}
};
感想
- 经典的双指针,暴力求解时间会超
- 找到移动指针的情况是双指针题型求解的关键
15. 三数之和(medium)
2023/4/5
题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
我的答案
#include <algorithm>
#include <vector>
class Solution {
public:
bool MyFind(vector<int>& nums, int& temp, int p1, int p2) {
if(temp < nums[p1] || temp > nums[p2]){
return false;
}
if(p2 - p1 == 2){
if(nums[p1 + 1] == temp){
return true;
}else{
return false;
}
}else if(p2 - p1 < 2){
return false;
}
int index = (p1 + p2) / 2;
if(temp > nums[index]){
return MyFind(nums, temp, index, p2);
}else if(temp < nums[index]){
return MyFind(nums, temp, p1, index);
}else{
return true;
}
}
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int p1 = 0, size = nums.size();
int tmp_p2 = size - 1;
while(nums[p1] <= 0){
int p2 = tmp_p2;
while(nums[p2] > -2 * nums[p1] && p2 > p1 + 1){
--p2;
}
tmp_p2 = p2;
while(nums[p2] >= 0 && p2 > p1 + 1){
int temp = -1 * (nums[p1] + nums[p2]);
if(MyFind(nums, temp, p1, p2)){
res.push_back({nums[p1], nums[p2], temp});
}
while(nums[p2] == nums[--p2] && p2 > p1);
}
while(nums[p1] == nums[++p1] && p1 < size - 2);
if(p1 == size - 2) break;
}
return res;
}
};
参考答案
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
ans.push_back({nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
};
感想
- 仔细分析不难看出来这题的思路是排序+双指针,但本题我在双指针的选择上未做到最好,我的算法是将一个指针从小到大移动,另一个指针从大到小移动,由于指针并不是同时移动,时间复杂度为\(O(N^2)\),然后对每一种情况进行一个find操作寻找第三个数,这里一开始使用的是遍历的方法,那样总时间复杂度将会达到\(O(N^3)\),超出时间限制,将find函数优化为二分查找,总的时间复杂度降低为\(O(N^2logN)\),通过
- 比较好的算法是:
- 设\(a+b+c = 0\)其中a,b,c为升序
- 遍历a,对任意一个a,取b指向a的下一个位置,c指向数组末尾,由于b增加时c必然会减小,此时双指针是同时移动的,均摊下来的时间复杂度为\(O(N)\),考虑到外层对a的遍历,总的时间复杂度为\(O(N^2)\)
- 尽量不要使用STL的函数(效率低)
17. 电话号码的字母组合(medium)
2023/7/13
题目描述
- 给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
我的答案
class Solution {
public:
vector<string> letterCombinations(string digits) {
int n = digits.size();
vector<string> map, res;
for (int i = 0; i < n; ++i)
{
switch(digits[i])
{
case '2' : map.push_back("abc"); break;
case '3' : map.push_back("def"); break;
case '4' : map.push_back("ghi"); break;
case '5' : map.push_back("jkl"); break;
case '6' : map.push_back("mno"); break;
case '7' : map.push_back("pqrs"); break;
case '8' : map.push_back("tuv"); break;
case '9' : map.push_back("wxyz"); break;
}
}
string tmp = "";
dfs(map, res, tmp, 0);
return res;
}
void dfs(vector<string> map, vector<string>& res, string tmp, int lv)
{
if (map.size() == lv)
{
if (tmp != "")
res.push_back(tmp);
return;
}
for(int i = 0; i < map[lv].size(); ++i)
{
dfs(map, res, tmp + map[lv][i], lv+1);
}
}
};
参考答案
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> combinations;
if (digits.empty()) {
return combinations;
}
unordered_map<char, string> phoneMap{
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
string combination;
backtrack(combinations, phoneMap, digits, 0, combination);
return combinations;
}
void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) {
if (index == digits.length()) {
combinations.push_back(combination);
} else {
char digit = digits[index];
const string& letters = phoneMap.at(digit);
for (const char& letter: letters) {
combination.push_back(letter);
backtrack(combinations, phoneMap, digits, index + 1, combination);
combination.pop_back();
}
}
}
};
感想
看了题解，是同一种思路，唯一的不同是我没有用哈希表，但是我认为算法是dfs，题解说是回溯，差不多啦~
19. 删除链表的倒数第 N 个结点(medium)
2023/7/13
题目描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
我的答案
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* pl = head;
ListNode* pbefore = head;
for (int i = 0; i < n; ++i)
{
pl = pl->next;
}
if (pl == nullptr)
{
return head->next;
}
while(pl->next != nullptr)
{
pl = pl->next;
pbefore = pbefore->next;
}
pbefore->next = pbefore->next->next;
return head;
}
};
参考答案
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
ListNode* first = head;
ListNode* second = dummy;
for (int i = 0; i < n; ++i) {
first = first->next;
}
while (first) {
first = first->next;
second = second->next;
}
second->next = second->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
感想
很简单，双指针秒杀，没什么好说的。
20. 有效的括号(easy)
2023/7/13
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
我的答案
#include <stack>
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
int size = s.size();
for (int i = 0; i < size; ++i)
{
if (s[i] == ')')
{
if(!stk.empty() && stk.top() == '(')
{
stk.pop();
}
else
{
return false;
}
}
else if (s[i] == ']')
{
if(!stk.empty() && stk.top() == '[')
{
stk.pop();
}
else
{
return false;
}
}
else if (s[i] == '}')
{
if(!stk.empty() && stk.top() == '{')
{
stk.pop();
}
else
{
return false;
}
}
else
{
stk.push(s[i]);
}
}
return stk.empty();
}
};
参考答案
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if (n % 2 == 1) {
return false;
}
unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
stack<char> stk;
for (char ch: s) {
if (pairs.count(ch)) {
if (stk.empty() || stk.top() != pairs[ch]) {
return false;
}
stk.pop();
}
else {
stk.push(ch);
}
}
return stk.empty();
}
};
感想
很基础的栈的题目，秒杀。
21. 合并两个有序链表(easy)
2023/7/13
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
我的答案
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr)
{
return list2;
}
else if (list2 == nullptr)
{
return list1;
}
ListNode* res = list1->val < list2->val ? list1 : list2;
ListNode* p1 = list1 == res ? list1->next : list1;
ListNode* p2 = list2 == res ? list2->next : list2;
ListNode* res_tail = res;
while (p1 != nullptr || p2 != nullptr)
{
if (p1 == nullptr)
{
res_tail->next = p2;
break;
}
else if (p2 == nullptr)
{
res_tail->next = p1;
break;
}
else if (p1->val < p2->val)
{
res_tail->next = p1;
p1 = p1->next;
res_tail = res_tail->next;
}
else if (p1->val >= p2->val)
{
res_tail->next = p2;
p2 = p2->next;
res_tail = res_tail->next;
}
}
return res;
}
};
参考答案
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) {
return l2;
} else if (l2 == nullptr) {
return l1;
} else if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
感想
我写的是迭代法，参考答案就放另一种递归的思路，都不难，递归相对更加简洁。
22. 括号生成(medium)
2023/7/13
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
我的答案
class Solution {
public:
vector<string> generateParenthesis(int n) {
int remain_left = n, remain_right = n;
vector<string> res;
string tmp;
generate(remain_left, remain_right, res, tmp);
return res;
}
void generate(int remain_left, int remain_right, vector<string> &res, string tmp)
{
if (remain_left == 0)
{
for (int i = 0; i < remain_right; ++i)
{
tmp += ")";
}
res.push_back(tmp);
return;
}
if (remain_right > remain_left)
{
generate(remain_left, remain_right - 1, res, tmp + ")");
generate(remain_left - 1, remain_right, res, tmp + "(");
}
else if (remain_right <= remain_left)
{
generate(remain_left - 1, remain_right, res, tmp + "(");
}
}
};
参考答案
class Solution {
void backtrack(vector<string>& ans, string& cur, int open, int close, int n) {
if (cur.size() == n * 2) {
ans.push_back(cur);
return;
}
if (open < n) {
cur.push_back('(');
backtrack(ans, cur, open + 1, close, n);
cur.pop_back();
}
if (close < open) {
cur.push_back(')');
backtrack(ans, cur, open, close + 1, n);
cur.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
string current;
backtrack(result, current, 0, 0, n);
return result;
}
};
感想
又是dfs回溯，和第17题电话号码类似，题解还提供了一种比较巧妙的方法，但是感觉容易出错，还是用老老实实dfs吧。
23.合并 K 个升序链表(hard)
2023/7/14
题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
我的答案
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* min = nullptr;
for (auto& it : lists)
{
if (it == nullptr || it->val == 1E5)
{
continue;
}
if (min == nullptr || min->val > it->val)
{
min = it;
}
}
if (min == nullptr)
{
return nullptr;
}
ListNode* res = new ListNode(min->val);
if (min->next != nullptr)
{
// ListNode* tmp = min->next;
min->val = min->next->val;
min->next = min->next->next;
// delete tmp;
}
else
{
min->val = 1E5;
}
res->next = mergeKLists(lists);
return res;
}
};
参考答案
class Solution {
public:
struct Status {
int val;
ListNode *ptr;
bool operator < (const Status &rhs) const {
return val > rhs.val;
}
};
priority_queue <Status> q;
ListNode* mergeKLists(vector<ListNode*>& lists) {
for (auto node: lists) {
if (node) q.push({node->val, node});
}
ListNode head, *tail = &head;
while (!q.empty()) {
auto f = q.top(); q.pop();
tail->next = f.ptr;
tail = tail->next;
if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
}
return head.next;
}
};
感想
现在写hard题没有很吃力了，很快就有了思路但是四十分钟才ac，时间和空间都不太好，题解里面优先队列的做法还不错。
31.下一个排列(medium)
2023/8/9
题目描述
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
- 例如，
arr = [1,2,3]的下一个排列是[1,3,2]。 - 类似地，
arr = [2,3,1]的下一个排列是[3,1,2]。 - 而
arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
我的答案
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
if (n <= 1)
{
return;
}
for (int i = 1; i <= n; ++i)
{
if(Process(nums, i))
{
return;
}
}
for (int i = 0; i < n / 2; ++i)
{
int temp = nums[i];
nums[i] = nums[n - 1 - i];
nums[n - 1 - i] = temp;
}
return;
}
bool Process(vector<int> &nums, int n)
{
int size = nums.size();
int i = size - 1, j = size - n;
while(i > size - n && j >= size - n)
{
if (nums[i] > nums[j])
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
sort(nums.begin()+j+1, nums.end());
return true;
}
if (j != size - n)
{
j--;
}
else
{
j = --i - 1;
}
}
return false;
}
};
参考答案
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int size = nums.size();
if (size <= 1) return;
int now = nums[size - 1];
int loc = -1;
for (int i = size - 2; i >= 0; --i)
{
if (nums[i] < now)
{
loc = i;
now = nums[loc];
break;
}
now = nums[i];
}
if (loc != -1)
{
for (int i = size - 1; i > loc; --i)
{
if (nums[i] > now)
{
nums[loc] = nums[i];
nums[i] = now;
break;
}
}
}
for (int i = 0; i < (size - loc - 1) / 2; ++i)
{
// loc+1+i, size - 1 - i
int temp = nums[loc+1+i];
nums[loc+1+i] = nums[size-1-i];
nums[size-1-i] = temp;
}
return;
}
};
感想
边上课边写了一个小时，上面gif图就是最好的理解，可惜的是我一直到提交都没有想到这么naive的做法，不过代码的本质倒是对了，感觉可以写得优雅很多。
32.最长有效括号(hard)
2023/8/9
01 : 13 : 26
题目描述
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
提示：
0 <= s.length <= 3 * 104s[i]为'('或')'
我的答案
class Solution {
public:
int longestValidParentheses(string s) {
int size = s.size();
int max = 0;
int* dp = new int[size+1]();
// dp[i]代表从i开始有几位有效
for (int i = size - 2; i >= 0; --i)
{
if (s[i] == '(')
{
int tmp1 = 0, tmp2 = 0;
if (s[i+1] == ')')
{
tmp1 = dp[i+2] + 2;
}
if (s[i + 1 + dp[i+1]] == ')')
{
tmp2 = dp[i+1] + 2 + dp[i + 2 + dp[i+1]];
}
dp[i] = tmp1 > tmp2 ? tmp1 : tmp2;
max = dp[i] > max ? dp[i] : max;
}
}
return max;
}
};
参考答案
class Solution {
public:
int longestValidParentheses(string s) {
int left = 0, right = 0, maxlength = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = max(maxlength, 2 * right);
} else if (right > left) {
left = right = 0;
}
}
left = right = 0;
for (int i = (int)s.length() - 1; i >= 0; i--) {
if (s[i] == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = max(maxlength, 2 * left);
} else if (left > right) {
left = right = 0;
}
}
return maxlength;
}
};
感想
第一反应是使用动规，但是看答案3的做法非常自然，因为判断括号是否匹配只需要数个数即可。
33.搜索旋转排序数组(medium)
2023/8/9
00 : 55 : 36
题目描述
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000-104 <= nums[i] <= 104nums中的每个值都 独一无二- 题目数据保证
nums在预先未知的某个下标上进行了旋转 -104 <= target <= 104
我的答案
class Solution {
public:
int search(vector<int>& nums, int target) {
int size = nums.size();
if (size == 1)
{
return target == nums[0] ? 0 : -1;
}
if (target > nums[size-1] && target < nums[0]) return -1;
int left = 0, right = size - 1;
while (left < right - 1)
{
if (nums[(left + right) / 2] > nums[0])
{
left = (left + right) / 2;
}
else
{
right = (left + right) / 2;
}
}
if (target >= nums[0])
{
right = left;
left = 0;
}
else
{
++left;
right = size - 1;
}
while (left < right - 1)
{
if (nums[(left + right) / 2] >= target)
{
right = (left + right) / 2;
}
else
{
left = (left + right) / 2;
}
}
if (nums[left] == target)
{
return left;
}
else if (left + 1 < size && nums[left + 1] == target)
{
return left + 1;
}
else if (right + 1 < size && nums[right + 1] == target)
{
return right + 1;
}
return -1;
}
};
参考答案
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = (int)nums.size();
if (!n) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return mid;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
};
感想
速度还是有点慢，但是可能是不够专注因为在上课，好在是第一时间就想到了二分查找，写的时候用了很多hack
34.在排序数组中查找元素的第一个和最后一个位置(medium)
2023/8/9
00 : 27 : 12
题目描述
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
我的答案
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res;
res.push_back(-1);
res.push_back(-1);
int l = 0, size = nums.size();
int r = size - 1;
if (size == 1 && nums[0] == target)
{
res[0] = res[1] = 0;
return res;
}
while (l <= r)
{
int mid = (l + r) / 2;
if (nums[mid] >= target)
{
r = mid - 1;
res[0] = nums[mid] == target ? mid : res[0];
}
else
{
l = mid + 1;
}
}
l = 0;
r = size - 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (nums[mid] > target)
{
r = mid - 1;
}
else
{
l = mid + 1;
res[1] = nums[mid] == target ? mid : res[1];
}
}
return res;
}
};
参考答案
class Solution {
public:
int binarySearch(vector<int>& nums, int target, bool lower) {
int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target || (lower && nums[mid] >= target)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftIdx = binarySearch(nums, target, true);
int rightIdx = binarySearch(nums, target, false) - 1;
if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
return vector<int>{leftIdx, rightIdx};
}
return vector<int>{-1, -1};
}
};
感想
速度还是有点慢，但是可能是不够专注因为在上课，好在是第一时间就想到了二分查找，写的时候用了很多hack
39. 组合总和(medium)
2023/8/26
01 : 14 : 01
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
提示：
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
我的答案
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
int size = candidates.size();
vector<vector<int>> res;
if (target == 0)
{
vector<int> tmp;
res.push_back(tmp);
return res;
}
else if (target < 0)
{
return res;
}
for (int i = 0; i < size; ++i)
{
auto tmp = combinationSum(candidates, target - candidates[i]);
if (!tmp.empty())
{
for (auto &it : tmp)
{
if (it.empty() || it.back() <= candidates[i])
{
it.push_back(candidates[i]);
res.push_back(it);
}
}
}
}
return res;
}
};
参考答案
class Solution {
public:
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx) {
if (idx == candidates.size()) {
return;
}
if (target == 0) {
ans.emplace_back(combine);
return;
}
// 直接跳过
dfs(candidates, target, ans, combine, idx + 1);
// 选择当前数
if (target - candidates[idx] >= 0) {
combine.emplace_back(candidates[idx]);
dfs(candidates, target - candidates[idx], ans, combine, idx);
combine.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> combine;
dfs(candidates, target, ans, combine, 0);
return ans;
}
};
感想
想了很久硬做出来的，没有用到答案的回溯剪枝，还需要要多加练习
42. 接雨水(hard)
2023/8/26
00 : 49 : 24
题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
我的答案
class Solution {
public:
int boxSum(vector<int>& height, int l, int r)
{
int sum = 0;
for (; l <= r; ++l)
{
sum += height[l];
}
return sum;
}
int trap(vector<int>& height) {
int size = height.size();
int *dp = new int[size]();
for (int i = 2; i < size; ++i)
{
if (height[i] <= height[i-1])
{
dp[i] = dp[i-1];
continue;
}
int index = -1, max = 0;
for (int j = i - 2; j >= 0; --j)
{
if (height[j] > max)
{
index = j;
max = height[index];
if (max >= height[i])
{
max = height[i];
break;
}
}
}
if (index >= 0)
{
int append = max * (i - index - 1) - boxSum(height, index + 1, i - 1);
if (append > 0 && height[i - 1] <= max)
{
dp[i] = dp[index] + append;
}
else
{
dp[i] = dp[i - 1];
}
}
else
{
dp[i] = dp[i - 1];
}
}
return dp[size - 1];
}
};
参考答案
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
if (n == 0) {
return 0;
}
vector<int> leftMax(n);
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = max(leftMax[i - 1], height[i]);
}
vector<int> rightMax(n);
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = max(rightMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
};
感想
知道是dp，但是dp的方式不如官方题解的那样清晰简洁
46. 全排列(medium)
2023/8/27
题目描述
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
我的答案
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
res.push_back(vector<int>{nums[0]});
int size = nums.size();
for (int i = 1; i < size; ++i)
{
int res_size = res.size();
for (int k = 0; k < res_size; ++k)
{
int len = res[k].size();
for (int j = 0; j < len; ++j)
{
vector<int>* temp = new vector<int> (res[k]);
temp->push_back(nums[i]);
swap((*temp)[j], (*temp)[len]);
res.push_back(*temp);
}
res[k].push_back(nums[i]);
}
}
return res;
}
};
参考答案
class Solution {
public:
void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
// 所有数都填完了
if (first == len) {
res.emplace_back(output);
return;
}
for (int i = first; i < len; ++i) {
// 动态维护数组
swap(output[i], output[first]);
// 继续递归填下一个数
backtrack(res, output, first + 1, len);
// 撤销操作
swap(output[i], output[first]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
backtrack(res, nums, 0, (int)nums.size());
return res;
}
};
感想
不太熟悉回溯的做法，我的方法是对每一个新的数字插入到之前已有的res中，并且与每一个元素交换位置获得一个新的排列
48. 旋转图像(medium)
2023/8/27
题目描述
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
提示：
n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000
我的答案
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int levels = matrix.size();
int times = levels / 2;
for (int i = 0; i < times; ++i)
{
int sizeLen = levels - 2 * i - 1;
for (int j = 0; j < 3 * sizeLen; ++j)
{
int dest;
int destX, destY, srcX, srcY;
dest = j + sizeLen;
if (j < sizeLen)
{
srcX = i + j;
srcY = i;
}
else if (j < 2 * sizeLen)
{
srcX = i+sizeLen;
srcY = i+j-sizeLen;
}
else if (j < 3 * sizeLen)
{
srcX = i+sizeLen-(j-2*sizeLen);
srcY = i+sizeLen;
}
else if (j < 4 * sizeLen)
{
srcX = i;
srcY = i+sizeLen-(j-3*sizeLen);
}
if (dest < sizeLen)
{
destX = i + dest;
destY = i;
}
else if (dest < 2 * sizeLen)
{
destX = i+sizeLen;
destY = i+dest-sizeLen;
}
else if (dest < 3 * sizeLen)
{
destX = i+sizeLen-(dest-2*sizeLen);
destY = i+sizeLen;
}
else if (dest < 4 * sizeLen)
{
destX = i;
destY = i+sizeLen-(dest-3*sizeLen);
}
swap(matrix[destX][destY], matrix[srcX][srcY]);
}
}
}
};
参考答案
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < (n + 1) / 2; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = temp;
}
}
}
};
感想
限定了原地交换，感觉更像是一道数学题，我是考虑了连续反方向交换可以达到正方向插入的效果，感觉官方题解的思路更简洁，既然都是要换四个，确实可以一次性把这四个全部找到，我的答案也可以用这种思路优化，速度可以提升四倍
49. 字母异位词分组(medium)
2023/8/27
00 : 49 : 24
题目描述
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示：
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]仅包含小写字母
我的答案
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
unordered_map<string, int> map;
for (auto &str : strs)
{
string temp = str;
sort(temp.begin(), temp.end());
if (map.find(temp) == map.end())
{
map.emplace(temp, res.size());
res.push_back(vector<string>({str}));
}
else
{
res[map[temp]].push_back(str);
}
}
return res;
}
};
参考答案
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (string& str: strs) {
string key = str;
sort(key.begin(), key.end());
mp[key].emplace_back(str);
}
vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};
感想
我第一次写是用的暴力解法，最后一个测试用例过不去，看了评论区的话，改用了哈希，知道哈希的话很好过
53. 最大子数组和(medium)
2023/8/27
00 : 09 : 01
题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
我的答案
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int size = nums.size();
int max = nums[0];
int *dp = new int[size];
dp[0] = max;
for (int i = 1; i < size; ++i)
{
dp[i] = (dp[i-1] > 0 ? dp[i-1] : 0) + nums[i];
max = dp[i] > max ? dp[i] : max;
}
return max;
}
};
参考答案
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
pre = max(pre + x, x);
maxAns = max(maxAns, pre);
}
return maxAns;
}
};
感想
非常简单的dp，也很容易反应过来是dp，秒杀
55. 跳跃游戏(medium)
2023/8/27
00 : 05 : 44
题目描述
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 1040 <= nums[i] <= 105
我的答案
class Solution {
public:
bool canJump(vector<int>& nums) {
int size = nums.size();
bool *dp = new bool[size]();
dp[0] = true;
for (int i = 0; i < size; ++i)
{
if (dp[i] == false)
{
continue;
}
for (int j = 1; j <= nums[i] && i + j < size; ++j)
{
dp[i + j] = true;
}
}
return dp[size - 1];
}
};
参考答案
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int rightmost = 0;
for (int i = 0; i < n; ++i) {
if (i <= rightmost) {
rightmost = max(rightmost, i + nums[i]);
if (rightmost >= n - 1) {
return true;
}
}
}
return false;
}
};
感想
用dp的话很简单但是效率不高，题解给的是贪心的做法，贪心确实是最好的做法，我有点dp上头了。
56. 合并区间(medium)
2023/8/28
00 : 09 : 30
题目描述
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
我的答案
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(),
[](vector<int> a, vector<int> b)
{
return a[0] < b[0];
});
int size = intervals.size();
vector<vector<int>> result;
result.push_back(intervals[0]);
int lastRight = intervals[0][1];
for (int i = 1; i < size; ++i)
{
if (intervals[i][0] <= lastRight && intervals[i][1] > lastRight)
{
vector<int> temp = result.back();
result.pop_back();
lastRight = temp[1] = intervals[i][1];
result.push_back(temp);
}
else if (intervals[i][0] > lastRight)
{
result.push_back(intervals[i]);
lastRight = intervals[i][1];
}
}
return result;
}
};
参考答案
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.size() == 0) {
return {};
}
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
for (int i = 0; i < intervals.size(); ++i) {
int L = intervals[i][0], R = intervals[i][1];
if (!merged.size() || merged.back()[1] < L) {
merged.push_back({L, R});
}
else {
merged.back()[1] = max(merged.back()[1], R);
}
}
return merged;
}
};
感想
和官方题解给出的做法一致, 都是先排序再贪心, 速度比较一般
62. 不同路径(medium)
2023/8/28
00 : 30 : 55
题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
提示：
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 109
我的答案
class Solution {
public:
int uniquePaths(int m, int n) {
int **dp = new int*[m];
for (int i = 0; i < m; ++i)
{
dp[i] = new int[n];
for (int j = 0; j < n; ++j)
{
if (i == 0 || j == 0)
{
dp[i][j] = 1;
}
else
{
dp[i][j] = 0;
}
}
}
for (int i = 1; i < m; ++i)
{
for (int j = 1; j < n; ++j)
{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
参考答案
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> f(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
f[i][0] = 1;
}
for (int j = 0; j < n; ++j) {
f[0][j] = 1;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
}
};
感想
第一遍写的时候没有用动态规划,而是当成寻路的题, 用的dfs, 效率很灾难, 于是改用dp, 发现很简单
64. 最小路径和(medium)
2023/8/28
00 : 06 : 37
题目描述
给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
我的答案
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
for (int i = 1; i < n; ++i)
{
grid[0][i] += grid[0][i-1];
}
for (int i = 1; i < m; ++i)
{
grid[i][0] += grid[i-1][0];
}
for (int i = 1; i < m; ++i)
{
for (int j = 1; j < n; ++j)
{
grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
}
}
return grid[m-1][n-1];
}
};
参考答案
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.size() == 0 || grid[0].size() == 0) {
return 0;
}
int rows = grid.size(), columns = grid[0].size();
auto dp = vector < vector <int> > (rows, vector <int> (columns));
dp[0][0] = grid[0][0];
for (int i = 1; i < rows; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int j = 1; j < columns; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[rows - 1][columns - 1];
}
};
感想
这题的思路和62很像, 也是基本一致的dp
70. 爬楼梯(easy)
2023/8/28
00 : 03 : 00
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
提示：
1 <= n <= 45
我的答案
class Solution {
public:
int climbStairs(int n) {
if (n == 1)
{
return 1;
}
int *dp = new int[n];
for (int i = 0; i < n; ++i)
{
dp[i] = 0;
}
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < n; ++i)
{
dp[i] = dp[i-2] + dp[i-1];
}
return dp[n-1];
}
};
参考答案
class Solution {
public:
int climbStairs(int n) {
int p = 0, q = 0, r = 1;
for (int i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
};
感想
不愧是easy题, 比前面的dp更快, 不过看题解说是可以用「滚动数组思想」(类似滑动窗口)解决, 可以省下很多空间
72. 编辑距离(hard)
2023/8/28
题目描述
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500word1和word2由小写英文字母组成
我的答案
class Solution {
public:
int min(int x, int y, int z)
{
int temp = y < z ? y : z;
return x < temp ? x : temp;
}
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
int **dp = new int*[m+1];
for (int i = 0; i <= m; ++i)
{
dp[i] = new int[n+1];
for (int j = 0; j <= n; ++j)
{
dp[i][j] = 0;
}
}
for (int i = 0; i <= m; ++i)
{
dp[i][0] = i;
}
for (int j = 0; j <= n; ++j)
{
dp[0][j] = j;
}
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
{
int temp1 = dp[i-1][j-1] + (word1[i-1] == word2[j-1] ? 0 : 1);
int temp2 = dp[i-1][j] + 1;
int temp3 = dp[i][j-1] + 1;
dp[i][j] = min(temp1, temp2, temp3);
}
}
return dp[m][n];
}
};
参考答案
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.length();
int m = word2.length();
// 有一个字符串为空串
if (n * m == 0) return n + m;
// DP 数组
vector<vector<int>> D(n + 1, vector<int>(m + 1));
// 边界状态初始化
for (int i = 0; i < n + 1; i++) {
D[i][0] = i;
}
for (int j = 0; j < m + 1; j++) {
D[0][j] = j;
}
// 计算所有 DP 值
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
int left = D[i - 1][j] + 1;
int down = D[i][j - 1] + 1;
int left_down = D[i - 1][j - 1];
if (word1[i - 1] != word2[j - 1]) left_down += 1;
D[i][j] = min(left, min(down, left_down));
}
}
return D[n][m];
}
};
感想
确实写不出来, 看了题解才能做出来, 这个dp的思路很巧妙, 还是先背下来吧
75. 颜色分类(medium)
2023/8/30
00 : 10 : 00
题目描述
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
提示：
n == nums.length1 <= n <= 300nums[i]为0、1或2
进阶：
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
我的答案
class Solution {
public:
void quickSort(vector<int>& nums, int l, int r)
{
if (l >= r)
{
return;
}
int left = l, right = r-1;
// srand(time(NULL));
// swap(nums[r], nums[rand() % (r-l+1) + l]);
int pivot = r;
while (left < right)
{
while (left < right && nums[left] <= nums[pivot])
{
left++;
}
while (left < right && nums[right] > nums[pivot])
{
right--;
}
swap(nums[left], nums[right]);
}
if (nums[left] > nums[pivot])
{
swap(nums[left], nums[pivot]);
pivot = left;
}
quickSort(nums, l, pivot-1);
quickSort(nums, pivot+1, r);
}
void sortColors(vector<int>& nums) {
quickSort(nums, 0, nums.size()-1);
}
};
参考答案
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int p0 = 0, p2 = n - 1;
for (int i = 0; i <= p2; ++i) {
while (i <= p2 && nums[i] == 2) {
swap(nums[i], nums[p2]);
--p2;
}
if (nums[i] == 0) {
swap(nums[i], nums[p0]);
++p0;
}
}
}
};
感想
知道不需要用快排, 但是正好复习一下快排(), 说回题目本身, 只需要把0放最前, 2放最后即可
76. 最小覆盖子串(hard)
2023/8/30
题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
m == s.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
我的答案
class Solution {
public:
bool isInclude(unordered_map<char, int>& hash)
{
for (auto &it : hash)
{
if (it.second > 0)
{
return false;
}
}
return true;
}
string minWindow(string s, string t)
{
unordered_map<char, int> hash;
int m = s.size();
int n = t.size();
for (int i = 0; i < n; ++i)
{
if (hash.find(t[i]) != hash.end())
{
hash[t[i]]++;
}
else
{
hash.insert({t[i], 1});
}
}
int left = 0, right = 0, index = 0, len = 0x3f3f3f3f;
while (right < m)
{
while (right < m)
{
if (hash.find(s[right]) != hash.end())
{
hash[s[right]]--;
}
else
{
right++;
continue;
}
if (hash[s[right]] == 0 && isInclude(hash))
{
if (right - left + 1 < len)
{
index = left;
len = right - left + 1;
}
right++;
break;
}
right++;
}
if (!isInclude(hash))
{
break;
}
while (right - left >= n)
{
if (hash.find(s[left]) != hash.end())
{
hash[s[left]]++;
}
else
{
left++;
continue;
}
if (hash[s[left]] == 1 && !isInclude(hash))
{
if (right - left < len)
{
index = left;
len = right - left;
}
left++;
break;
}
left++;
}
}
if (len != 0x3f3f3f3f)
{
return s.substr(index, len);
}
else
{
return "";
}
}
};
参考答案
class Solution {
public:
unordered_map <char, int> ori, cnt;
bool check() {
for (const auto &p: ori) {
if (cnt[p.first] < p.second) {
return false;
}
}
return true;
}
string minWindow(string s, string t) {
for (const auto &c: t) {
++ori[c];
}
int l = 0, r = -1;
int len = INT_MAX, ansL = -1, ansR = -1;
while (r < int(s.size())) {
if (ori.find(s[++r]) != ori.end()) {
++cnt[s[r]];
}
while (check() && l <= r) {
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
}
if (ori.find(s[l]) != ori.end()) {
--cnt[s[l]];
}
++l;
}
}
return ansL == -1 ? string() : s.substr(ansL, len);
}
};
感想
写了很久, 摸索出来是滑动窗口, 但是关于具体怎么划总是出bug, 于是看了一眼题解再重写了一遍
78. 子集(medium)
2023/8/30
题目描述
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
我的答案
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
int size = nums.size();
vector<vector<int>> res;
if (size == 0)
{
return res;
}
else
{
vector<int> temp;
res.push_back(temp);
temp.push_back(nums[0]);
res.push_back(temp);
}
for (int i = 1; i < size; ++i)
{
vector<vector<int>> newSubsets;
for (auto &it : res)
{
vector<int> tmp = it;
tmp.push_back(nums[i]);
newSubsets.push_back(tmp);
}
res.insert(res.end(), newSubsets.begin(), newSubsets.end());
}
return res;
}
};
参考答案
class Solution {
public:
vector<int> t;
vector<vector<int>> ans;
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size();
for (int mask = 0; mask < (1 << n); ++mask) {
t.clear();
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
t.push_back(nums[i]);
}
}
ans.push_back(t);
}
return ans;
}
};
感想
这个不难, 注意代码19行使用的newSubsets
79. 单词搜索(medium)
2023/8/30
00 : 35 : 49
题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
提示：
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board和word仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
我的答案
class Solution {
public:
bool search(int posx, int posy, vector<vector<char>>& board, string& word, vector<vector<bool>>& passedby)
{
passedby[posx][posy] = true;
if (word == "")
{
passedby[posx][posy] = false;
return true;
}
string str = word.substr(1);
if (posx > 0 && !passedby[posx-1][posy] && board[posx-1][posy] == word[0] && search(posx-1, posy, board, str, passedby))
{
passedby[posx][posy] = false;
return true;
}
if (posx+1 < board.size() && !passedby[posx+1][posy] && board[posx+1][posy] == word[0] && search(posx+1, posy, board, str, passedby))
{
passedby[posx][posy] = false;
return true;
}
if (posy > 0 && !passedby[posx][posy-1] && board[posx][posy-1] == word[0] && search(posx, posy-1, board, str, passedby))
{
passedby[posx][posy] = false;
return true;
}
if (posy+1 < board[0].size() && !passedby[posx][posy+1] && board[posx][posy+1] == word[0] && search(posx, posy+1, board, str, passedby))
{
passedby[posx][posy] = false;
return true;
}
passedby[posx][posy] = false;
return false;
}
bool exist(vector<vector<char>>& board, string word) {
vector<vector<bool>> passedby;
for (int i = 0; i < board.size(); ++i)
{
vector<bool> temp;
for (int j = 0; j < board[i].size(); ++j)
{
temp.push_back(false);
}
passedby.push_back(temp);
}
string str = word.substr(1);
for (int i = 0; i < board.size(); ++i)
{
for (int j = 0; j < board[i].size(); ++j)
{
if (board[i][j] == word[0])
{
if (search(i, j, board,str, passedby))
{
return true;
}
}
}
}
return false;
}
};
参考答案
int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool check(char** board, int boardSize, int boardColSize, int** visited, int i, int j, char* s, int sSize, int k) {
if (board[i][j] != s[k]) {
return false;
} else if (k == sSize - 1) {
return true;
}
visited[i][j] = true;
bool result = false;
for (int sel = 0; sel < 4; sel++) {
int newi = i + directions[sel][0], newj = j + directions[sel][1];
if (newi >= 0 && newi < boardSize && newj >= 0 && newj < boardColSize) {
if (!visited[newi][newj]) {
bool flag = check(board, boardSize, boardColSize, visited, newi, newj, s, sSize, k + 1);
if (flag) {
result = true;
break;
}
}
}
}
visited[i][j] = false;
return result;
}
bool exist(char** board, int boardSize, int* boardColSize, char* word) {
int** visited = malloc(sizeof(int*) * boardSize);
for (int i = 0; i < boardSize; i++) {
visited[i] = malloc(sizeof(int) * boardColSize[0]);
memset(visited[i], 0, sizeof(int) * boardColSize[0]);
}
int wordSize = strlen(word);
for (int i = 0; i < boardSize; i++) {
for (int j = 0; j < boardColSize[0]; j++) {
bool flag = check(board, boardSize, boardColSize[0], visited, i, j, word, wordSize, 0);
if (flag) {
return true;
}
}
}
return false;
}
感想
很容易想到的方法, 问题是时间复杂度很高, 写出来之后发现超时限了, 看了眼题解发现思路没问题, 把代码优化了一下, 比如参数从传值变成传引用, 增加判定条件剪枝等
84. 柱状图中最大的矩形(hard)
2023/8/30
题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
提示：
1 <= heights.length <=1050 <= heights[i] <= 104
我的答案
class Solution {
public:
int largestRectangleArea(vector<int> &heights)
{
int size = heights.size();
int *preorder = new int[size]();
int *postorder = new int[size]();
stack<int> stk;
stk.push(-1);
int top = -1;
for (int i = 0; i < size; ++i)
{
if (top == -1 || heights[top] < heights[i])
{
stk.push(i);
top = i;
}
else
{
while (top != -1 && heights[top] >= heights[i])
{
int tmp = top;
stk.pop();
top = stk.top();
preorder[tmp] = top;
}
stk.push(i);
top = i;
}
}
while (top != -1)
{
int tmp = top;
stk.pop();
top = stk.top();
preorder[tmp] = top;
}
// post
stk.pop();
stk.push(size);
top = size;
for (int i = size - 1; i >= 0; --i)
{
if (top == size || heights[top] < heights[i])
{
stk.push(i);
top = i;
}
else
{
while (top != size && heights[top] >= heights[i])
{
int tmp = top;
stk.pop();
top = stk.top();
postorder[tmp] = top;
}
stk.push(i);
top = i;
}
}
while (top != size)
{
int tmp = top;
stk.pop();
top = stk.top();
postorder[tmp] = top;
}
int max = 0;
for (int i = 0; i < size; ++i)
{
int area = heights[i] * (postorder[i] - preorder[i] - 1);
max = max < area ? area : max;
}
return max;
}
};
参考答案
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> left(n), right(n);
stack<int> mono_stack;
for (int i = 0; i < n; ++i) {
while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
mono_stack.pop();
}
left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
mono_stack.push(i);
}
mono_stack = stack<int>();
for (int i = n - 1; i >= 0; --i) {
while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
mono_stack.pop();
}
right[i] = (mono_stack.empty() ? n : mono_stack.top());
mono_stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
};
感想
暴搜的速度太慢了, 无论怎么优化都过不去最后两个测试点, 无奈放弃, 看了题解说是单调栈, 好像是第一次接触单调栈的题目, 光是理解题解都花了好一段时间, 好在最后还是写了出来, 但是不敢保证下次碰见还能做出来
85. 最大矩形(hard)
2023/8/31
01 : 14 : 15
题目描述
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。
示例 2：
输入：matrix = []
输出：0
示例 3：
输入：matrix = [["0"]]
输出：0
示例 4：
输入：matrix = [["1"]]
输出：1
示例 5：
输入：matrix = [["0","0"]]
输出：0
提示：
rows == matrix.lengthcols == matrix[0].length1 <= row, cols <= 200matrix[i][j]为'0'或'1'
我的答案
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
int size = m*n;
int max = 0;
bool *dp = new bool[size];
for (int i = 0; i < size; ++i)
{
int rowX = n-i%n;
int rowY = m-i/n;
int banX = n;
int size_j = rowX * rowY;
if (size_j < max)
{
i = (i/n + 1) * n - 1;
continue;
}
dp[0] = matrix[i/n][i%n] == '1';
max = dp[0] && max == 0 ? 1 : max;
for (int j = 1; j < size_j; ++j)
{
if (j/rowX == 0)
{
dp[j] = dp[j-1] && matrix[i/n][i%n+j] == '1';
}
else if (j%rowX == 0)
{
dp[j] = dp[j-rowX] && matrix[i/n + j/rowX][i%n] == '1';
}
else
{
if (i%n + j%rowX >= banX)
{
j = (j/rowX + 1) * rowX - 1;
continue;
}
dp[j] = dp[j-1] && dp[j-rowX] && matrix[i/n + j/rowX][i%n + j%rowX] == '1';
}
if (dp[j])
{
int area = (j%rowX + 1) * (j/rowX + 1);
max = max > area ? max : area;
}
else
{
banX = banX < i%n + j%rowX ? banX : i%n + j%rowX;
}
}
}
return max;
}
};
参考答案
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) {
return 0;
}
int n = matrix[0].size();
vector<vector<int>> left(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
left[i][j] = (j == 0 ? 0: left[i][j - 1]) + 1;
}
}
}
int ret = 0;
for (int j = 0; j < n; j++) { // 对于每一列，使用基于柱状图的方法
vector<int> up(m, 0), down(m, 0);
stack<int> stk;
for (int i = 0; i < m; i++) {
while (!stk.empty() && left[stk.top()][j] >= left[i][j]) {
stk.pop();
}
up[i] = stk.empty() ? -1 : stk.top();
stk.push(i);
}
stk = stack<int>();
for (int i = m - 1; i >= 0; i--) {
while (!stk.empty() && left[stk.top()][j] >= left[i][j]) {
stk.pop();
}
down[i] = stk.empty() ? m : stk.top();
stk.push(i);
}
for (int i = 0; i < m; i++) {
int height = down[i] - up[i] - 1;
int area = height * left[i][j];
ret = max(ret, area);
}
}
return ret;
}
};
感想
我的是暴力解法, 应该参考84题使用单调栈会更好
94. 二叉树的中序遍历(easy)
2023/8/31
00 : 02 : 43
题目描述
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
我的答案
class Solution {
public:
void dfs(vector<int> &res, TreeNode* node)
{
if (node == nullptr)
{
return;
}
dfs(res, node->left);
res.push_back(node->val);
dfs(res, node->right);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
dfs(res, root);
return res;
}
};
参考答案
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while (root != nullptr || !stk.empty()) {
while (root != nullptr) {
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}
};
感想
自然的思路是递归, 本质上就是隐式地维护了一个栈
96. 不同的二叉搜索树(medium)
2023/8/31
00 : 24 : 24
题目描述
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 19
我的答案
class Solution {
public:
int numTrees(int n) {
int *dp = new int[n+1]();
dp[0] = 1;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= i; ++j)
{
dp[i] += dp[j-1] * dp[i-j];
}
}
return dp[n];
}
};
参考答案
class Solution {
public:
int numTrees(int n) {
vector<int> G(n + 1, 0);
G[0] = 1;
G[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
G[i] += G[j - 1] * G[i - j];
}
}
return G[n];
}
};
感想
一个递推公式, 想清楚了再下笔就不难, 题解有一个数学方法还有点意思, 应该是利用这个递推公式算出来的
98. 验证二叉搜索树(medium)
2023/8/31
00 : 26 : 29
题目描述
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
- 树中节点数目范围在
[1, 104]内 -231 <= Node.val <= 231 - 1
我的答案
class Solution {
public:
bool isValid(TreeNode* root, int min, int max, bool hasMin, bool hasMax)
{
if (root == nullptr)
{
return true;
}
if ((!hasMax || root->val < max) && (!hasMin || root->val > min))
{
return isValid(root->left, min, root->val, hasMin, true) && isValid(root->right, root->val, max, true, hasMax);
}
else
{
return false;
}
}
bool isValidBST(TreeNode* root) {
return isValid(root, 0, 0, false, false);
}
};
参考答案
class Solution {
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
// 访问左子树
if (!isValidBST(root.left)) {
return false;
}
// 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
if (root.val <= pre) {
return false;
}
pre = root.val;
// 访问右子树
return isValidBST(root.right);
}
}
感想
我是递归做的 ,用中序遍历也可以做, 设一个全局变量维护遍历到的上一个节点即可
101. 对称二叉树(easy)
2023/8/31
00 : 05 : 02
题目描述
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
提示：
- 树中节点数目在范围
[1, 1000]内 -100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
我的答案
class Solution {
public:
bool dfs(TreeNode* l, TreeNode* r)
{
if (l == nullptr || r == nullptr)
{
return l == r;
}
return l->val == r->val && dfs(l->left, r->right) && dfs(l->right, r->left);
}
bool isSymmetric(TreeNode* root) {
return dfs(root->left, root->right);
}
};
参考答案
感想
感觉我写的代码比题解写得要简洁, 就不贴题解了, 简单题基本能做到十分钟以内解决了
102. 二叉树的层序遍历(medium)
2023/9/1
00 : 08 : 35
题目描述
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
我的答案
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
vector<vector<int>> res;
vector<int> level;
if (root == nullptr)
{
return res;
}
q.push(root);
q.push(nullptr);
while (!q.empty())
{
if (q.front() == nullptr)
{
q.pop();
res.push_back(level);
if (q.empty())
{
break;
}
else
{
level = vector<int>();
q.push(nullptr);
}
}
TreeNode* temp = q.front();
q.pop();
level.push_back(temp->val);
if (temp->left != nullptr)
{
q.push(temp->left);
}
if (temp->right != nullptr)
{
q.push(temp->right);
}
}
return res;
}
};
参考答案
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector <vector <int>> ret;
if (!root) {
return ret;
}
queue <TreeNode*> q;
q.push(root);
while (!q.empty()) {
int currentLevelSize = q.size();
ret.push_back(vector <int> ());
for (int i = 1; i <= currentLevelSize; ++i) {
auto node = q.front(); q.pop();
ret.back().push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return ret;
}
};
感想
注意在队列中要想办法维护行与行的分界
104. 二叉树的最大深度(easy)
2023/9/1
00 : 04 : 30
题目描述
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
提示：
- 树中节点的数量在
[0, 104]区间内。 -100 <= Node.val <= 100
我的答案
class Solution {
public:
int dfs(TreeNode* node, int depth)
{
if (node == nullptr)
{
return depth;
}
depth++;
int temp1 = dfs(node->left, depth);
int temp2 = dfs(node->right, depth);
return temp1 > temp2 ? temp1 : temp2;
}
int maxDepth(TreeNode* root) {
return dfs(root, 0);
}
};
参考答案
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
感想
经典的dfs
105. 从前序与中序遍历序列构造二叉树(medium)
2023/9/1
00 : 15 : 15
题目描述
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列inorder保证 为二叉树的中序遍历序列
我的答案
class Solution {
public:
TreeNode* build(vector<int>& preorder, int pre_begin, vector<int>& inorder, int in_begin, int len)
{
if (len == 0)
{
return nullptr;
}
TreeNode* root = new TreeNode(preorder[pre_begin]);
int index = 0;
for (int i = 0; i < len; ++i)
{
if (inorder[in_begin+i] == preorder[pre_begin])
{
index = i;
break;
}
}
root->left = build(preorder, pre_begin+1, inorder, in_begin, index);
root->right = build(preorder, pre_begin+1+index, inorder, in_begin+index+1, len - index - 1);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder, 0, inorder, 0, inorder.size());
}
};
参考答案
class Solution {
private:
unordered_map<int, int> index;
public:
TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return nullptr;
}
// 前序遍历中的第一个节点就是根节点
int preorder_root = preorder_left;
// 在中序遍历中定位根节点
int inorder_root = index[preorder[preorder_root]];
// 先把根节点建立出来
TreeNode* root = new TreeNode(preorder[preorder_root]);
// 得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
// 递归地构造左子树，并连接到根节点
// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
// 递归地构造右子树，并连接到根节点
// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
// 构造哈希映射，帮助我们快速定位根节点
for (int i = 0; i < n; ++i) {
index[inorder[i]] = i;
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
};
感想
可以用哈希表辅助定位根节点在中序遍历中的下标位置
114. 二叉树展开为链表(medium)
2023/9/1
00 : 15 : 12
题目描述
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [0]
输出：[0]
提示：
- 树中结点数在范围
[0, 2000]内 -100 <= Node.val <= 100
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
我的答案
class Solution {
public:
void flatten(TreeNode* root) {
if (root == nullptr)
{
return;
}
if (root->left == nullptr)
{
flatten(root->right);
return;
}
// TreeNode* temp = root->right;
// root->right = root->left;
flatten(root->left);
flatten(root->right);
swap(root->left, root->right);
TreeNode* it = root->right;
while (it->right != nullptr)
{
it = it->right;
}
it->right = root->left;
root->left = nullptr;
}
};
参考答案
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode *curr = root;
while (curr != nullptr) {
if (curr->left != nullptr) {
auto next = curr->left;
auto predecessor = next;
while (predecessor->right != nullptr) {
predecessor = predecessor->right;
}
predecessor->right = curr->right;
curr->left = nullptr;
curr->right = next;
}
curr = curr->right;
}
}
};
感想
这题我自己的思路感觉挺不错的, 主要是做到了"原地"
121. 买卖股票的最佳时机(easy)
2023/9/1
00 : 11 : 29
题目描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 1050 <= prices[i] <= 104
我的答案
class Solution {
public:
int maxProfit(vector<int>& prices) {
stack<int> stk;
int buttom = -1;
int max = 0;
int size = prices.size();
for (int i = size-1; i >= 0; --i)
{
if (stk.empty())
{
stk.push(prices[i]);
buttom = prices[i];
}
else
{
if (stk.top() > prices[i])
{
stk.push(prices[i]);
}
else
{
while (!stk.empty() && stk.top() <= prices[i])
{
int income = buttom - stk.top();
max = income > max ? income : max;
stk.pop();
}
if (stk.empty())
{
buttom = prices[i];
}
stk.push(prices[i]);
}
}
}
int income = buttom - stk.top();
max = income > max ? income : max;
return max;
}
};
参考答案
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;
}
};
感想
前些天单调栈的题目写多了, 看到这题就想到了单调栈, 但是实际上只需要size为1的栈即可, 小于栈顶则替换, 大于栈顶则计算
124. 二叉树中的最大路径和(medium)
2023/9/2
00 : 35 : 23
题目描述
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
- 树中节点数目范围是
[1, 3 * 104] -1000 <= Node.val <= 1000
我的答案
class Solution {
public:
int dfs(TreeNode* root , int& res)
{
if (root == nullptr)
{
return 0;
}
int left = dfs(root->left, res);
int right = dfs(root->right, res);
int max = (left > 0 ? left : 0) + (right > 0 ? right : 0) + root->val;
res = res > max ? res : max;
if (left < 0 && right < 0)
{
return root->val;
}
return (left > right ? left : right) + root->val;
}
int maxPathSum(TreeNode* root) {
int res = root->val;
dfs(root, res);
return res;
}
};
参考答案
class Solution {
private:
int maxSum = INT_MIN;
public:
int maxGain(TreeNode* node) {
if (node == nullptr) {
return 0;
}
// 递归计算左右子节点的最大贡献值
// 只有在最大贡献值大于 0 时，才会选取对应子节点
int leftGain = max(maxGain(node->left), 0);
int rightGain = max(maxGain(node->right), 0);
// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
int priceNewpath = node->val + leftGain + rightGain;
// 更新答案
maxSum = max(maxSum, priceNewpath);
// 返回节点的最大贡献值
return node->val + max(leftGain, rightGain);
}
int maxPathSum(TreeNode* root) {
maxGain(root);
return maxSum;
}
};
感想
和题解几乎一样的做法, 这道hard并没有很难, 重点是思路要对
128. 最长连续序列(medium)
2023/9/2
00 : 54 : 49
题目描述
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109
我的答案
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
// 前大后小
unordered_map<int, int> hash1;
// 前小后大
unordered_map<int, int> hash2;
int size = nums.size();
int max = 0;
for (int i = 0; i < size; ++i)
{
if (hash1.find(nums[i]) != hash1.end() || hash2.find(nums[i]) != hash2.end())
{
continue;
}
auto it_hash1 = hash1.find(nums[i]-1);
auto it_hash2 = hash2.find(nums[i]+1);
if (it_hash1 != hash1.end())
{
if (it_hash2 != hash2.end())
{
int small = hash1[nums[i]-1];
int large = hash2[nums[i]+1];
hash1.erase(it_hash1);
hash1.erase(hash1.find(large));
hash1.insert({large, small});
hash2.erase(it_hash2);
hash2.erase(hash2.find(small));
hash2.insert({small, large});
max = (large - small + 1) > max ? (large - small + 1) : max;
}
else
{
int small = hash1[nums[i]-1];
hash1.erase(it_hash1);
hash1.insert({nums[i], small});
hash2[small]++;
max = (nums[i] - small + 1) > max ? (nums[i] - small + 1) : max;
}
}
else
{
if (it_hash2 != hash2.end())
{
int large = hash2[nums[i]+1];
hash1[large]--;
hash2.erase(it_hash2);
hash2.insert({nums[i], large});
max = (large - nums[i] + 1) > max ? (large - nums[i] + 1) : max;
}
else
{
hash1.insert({nums[i], nums[i]});
hash2.insert({nums[i], nums[i]});
max = 1 > max ? 1 : max;
}
}
}
return max;
}
};
参考答案
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> num_set;
for (const int& num : nums) {
num_set.insert(num);
}
int longestStreak = 0;
for (const int& num : num_set) {
if (!num_set.count(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (num_set.count(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = max(longestStreak, currentStreak);
}
}
return longestStreak;
}
};
感想
果然是hash表, 难度不大但是有很多hack, 所以花了很长时间
136. 只出现一次的数字(easy)
2023/9/2
00 : 25 : 04
题目描述
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
提示：
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- 除了某个元素只出现一次以外，其余每个元素均出现两次。
我的答案
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (auto& i : nums)
{
res ^= i;
}
return res;
}
};
参考答案
感想
题目说时间要O(n),空间只能常数, 实在想不到这样的算法, 于是看了题解, 说是用异或, 茅塞顿开
139. 单词拆分(medium)
2023/8/24
题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同
我的答案
class Solution {
public:
bool Compare(string s, string& word)
{
int size = word.size();
for (int i = 0; i < size; ++i)
{
if (s[i] != word[i])
{
return false;
}
}
return true;
}
bool wordBreak(string s, vector<string>& wordDict) {
int len = s.size();
bool* dp = new bool[len + 1]; // dp[i]表示前i个ok
dp[0] = true;
for (int i = 1; i <= len; ++i)
{
dp[i] = false;
for (auto & word : wordDict)
{
int size = word.size();
if (size <= i && dp[i - size] && Compare(s.substr(i - size), word))
{
dp[i] = true;
break;
}
}
}
return dp[len];
}
};
参考答案
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
auto wordDictSet = unordered_set <string> ();
for (auto word: wordDict) {
wordDictSet.insert(word);
}
auto dp = vector <bool> (s.size() + 1);
dp[0] = true;
for (int i = 1; i <= s.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {
dp[i] = true;
break;
}
}
}
return dp[s.size()];
}
};
感想
同样是dp，比官方题解快了7倍，官方题解的第二个for循环感觉没有意义，很浪费时间
141. 环形链表(easy)
2023/9/2
00 : 05 : 45
题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
- 链表中节点的数目范围是
[0, 104] -105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
我的答案
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* p1, *p2;
p1 = p2 = head;
while (p1 != nullptr && p2 != nullptr)
{
p2 = p2->next;
if (p2 == nullptr)
{
return false;
}
else if (p2 == p1)
{
return true;
}
p2 = p2->next;
p1 = p1->next;
}
return false;
}
};
参考答案
class Solution {
public:
bool hasCycle(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return false;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (fast == nullptr || fast->next == nullptr) {
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};
感想
依稀记得以前在学校里有学到过快慢指针的方法, 脑测可行之后直接写了, 只用了五分钟
142. 环形链表 II(medium)
2023/9/2
00 : 18 : 57
题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
- 链表中节点的数目范围在范围
[0, 104]内 -105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
我的答案
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode*> set;
ListNode* p = head;
while (p != NULL)
{
if (set.find(p) == set.end())
{
set.insert(p);
p = p->next;
}
else
{
return p;
}
}
return NULL;
}
};
参考答案
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast != nullptr) {
slow = slow->next;
if (fast->next == nullptr) {
return nullptr;
}
fast = fast->next->next;
if (fast == slow) {
ListNode *ptr = head;
while (ptr != slow) {
ptr = ptr->next;
slow = slow->next;
}
return ptr;
}
}
return nullptr;
}
};
感想
依然可以用快慢指针, 根据数学推导, 在相遇后保持slow继续运动,
同时新增一个速度为1的指针从头开始运动, 他们相遇的点必为环起点
146. LRU 缓存(medium)
2023/9/3
01 : 11 : 05
题目描述
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 105- 最多调用
2 * 105次get和put
我的答案
class LRUCache {
struct Node
{
int key, val;
Node* prev, *next;
Node(int k = 0, int v = 0, Node* p = nullptr, Node* n = nullptr) : key (k), val(v), prev(p), next(n) {}
};
public:
LRUCache(int capacity) {
m_capacity = capacity;
m_size = 0;
m_head = new Node();
m_tail = new Node();
m_head->next = m_tail;
m_tail->prev = m_head;
}
int get(int key) {
auto it = m_hash.find(key);
if (it != m_hash.end())
{
// 移到最前
Node* p = it->second;
p->prev->next = p->next;
p->next->prev = p->prev;
Node* tmp = m_head->next;
p->next = tmp;
tmp->prev = p;
p->prev = m_head;
m_head->next = p;
// ////
return p->val;
}
else
{
return -1;
}
}
void put(int key, int value) {
auto it = m_hash.find(key);
Node *p;
if (it != m_hash.end())
{
// 移到最前
p = it->second;
p->prev->next = p->next;
p->next->prev = p->prev;
p->val = value;
}
else
{
if (m_size >= m_capacity)
{
Node* toErase = m_tail->prev;
m_size--;
m_hash.erase(m_hash.find(toErase->key));
toErase->prev->next = toErase->next;
toErase->next->prev = toErase->prev;
delete toErase;
}
m_size++;
p = new Node(key, value);
m_hash.insert({key, p});
}
Node* tmp = m_head->next;
p->next = tmp;
tmp->prev = p;
p->prev = m_head;
m_head->next = p;
}
private:
int m_capacity;
int m_size;
unordered_map<int, Node*> m_hash;
Node* m_head, *m_tail;
};
/**
* 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);
*/
参考答案
struct DLinkedNode {
int key, value;
DLinkedNode* prev;
DLinkedNode* next;
DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
unordered_map<int, DLinkedNode*> cache;
DLinkedNode* head;
DLinkedNode* tail;
int size;
int capacity;
public:
LRUCache(int _capacity): capacity(_capacity), size(0) {
// 使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!cache.count(key)) {
return -1;
}
// 如果 key 存在，先通过哈希表定位，再移到头部
DLinkedNode* node = cache[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if (!cache.count(key)) {
// 如果 key 不存在，创建一个新的节点
DLinkedNode* node = new DLinkedNode(key, value);
// 添加进哈希表
cache[key] = node;
// 添加至双向链表的头部
addToHead(node);
++size;
if (size > capacity) {
// 如果超出容量，删除双向链表的尾部节点
DLinkedNode* removed = removeTail();
// 删除哈希表中对应的项
cache.erase(removed->key);
// 防止内存泄漏
delete removed;
--size;
}
}
else {
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
DLinkedNode* node = cache[key];
node->value = value;
moveToHead(node);
}
}
void addToHead(DLinkedNode* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
void removeNode(DLinkedNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void moveToHead(DLinkedNode* node) {
removeNode(node);
addToHead(node);
}
DLinkedNode* removeTail() {
DLinkedNode* node = tail->prev;
removeNode(node);
return node;
}
};
感想
记住几个细节:
- 自己定义链表
- dummy node首尾
- hash存指针方便定位
148. 排序链表(medium)
2023/9/3
00 : 48 : 32
题目描述
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中节点的数目在范围
[0, 5 * 104]内 -105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
我的答案
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeSort(ListNode* p1, ListNode* p2)
{
if (p1 == nullptr)
{
return p2;
}
if (p2 == nullptr)
{
return p1;
}
ListNode *res_head = nullptr, *res_tail = nullptr;
if (p1->val < p2->val)
{
res_head = p1;
p1 = p1->next;
res_tail = res_head;
}
else
{
res_head = p2;
p2 = p2->next;
res_tail = res_head;
}
while (p1 != nullptr || p2 != nullptr)
{
if (p1 == nullptr)
{
res_tail->next = p2;
return res_head;
}
if (p2 == nullptr)
{
res_tail->next = p1;
return res_head;
}
if (p1->val < p2->val)
{
res_tail->next = p1;
p1 = p1->next;
}
else
{
res_tail->next = p2;
p2 = p2->next;
}
res_tail = res_tail->next;
}
return res_head;
}
ListNode* FindMedium(ListNode* head)
{
if (head == nullptr || head->next == nullptr)
{
return head;
}
ListNode *p1 = head, *p2 = head->next;
while (p2 && p2->next)
{
p1 = p1->next;
p2 = p2->next->next;
}
return p1;
}
ListNode* sortList(ListNode* head) {
if (head == nullptr || head->next == nullptr)
{
return head;
}
ListNode* medium = FindMedium(head);
ListNode* p1 = head, *p2 = medium->next;
medium->next = nullptr;
ListNode *list1 = sortList(p1);
ListNode *list2 = sortList(p2);
return mergeSort(list1, list2);
}
};
参考答案
class Solution {
private:
ListNode* getMedian(ListNode* head) {
if (!head || !head->next) return head;
ListNode *slow = head;
ListNode *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* mergeSortedList(ListNode* head1, ListNode* head2) {
if (!head1 || !head2) return head1 ? head1 : head2;
if (head1->val < head2->val) {
head1->next = mergeSortedList(head1->next, head2);
return head1;
} else {
head2->next = mergeSortedList(head1, head2->next);
return head2;
}
}
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *mid = getMedian(head);
ListNode *next = mid->next;
mid->next = nullptr;
ListNode *list1 = sortList(head);
ListNode *list2 = sortList(next);
return mergeSortedList(list1, list2);
}
};
感想
使用归并排序, 利用两倍速指针寻找中点
152. 乘积最大子数组(medium)
2023/9/3
01 : 07 : 30
题目描述
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10nums的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
我的答案
class Solution {
public:
int maxProduct(vector<int>& nums) {
int size = nums.size();
int product = nums[0];
int max = product;
int last = 0;
int lastIndex = -1;
for (int i = 1; i < size ; ++i)
{
if (nums[i] > 0)
{
if (product == 0)
{
product = nums[i];
}
else
{
product *= nums[i];
}
}
else if (nums[i] == 0)
{
max = max > 0 ? max : 0;
max = product > max ? product : max;
product = 0;
}
else
{
if (product < 0)
{
product *= nums[i];
max = product > max ? product : max;
}
else if (product == 0)
{
product = nums[i];
}
else
{
max = product > max ? product : max;
product *= nums[i];
}
last = product;
lastIndex = i;
}
}
if (last < 0 && lastIndex != size-1 && product < 0)
{
product /= last;
}
max = product > max ? product : max;
// 反向
product = nums[size - 1];
last = 0;
lastIndex = -1;
for (int i = size - 2; i >= 0 ; --i)
{
if (nums[i] > 0)
{
if (product == 0)
{
product = nums[i];
}
else
{
product *= nums[i];
}
}
else if (nums[i] == 0)
{
max = max > 0 ? max : 0;
max = product > max ? product : max;
product = 0;
}
else
{
if (product < 0)
{
product *= nums[i];
max = product > max ? product : max;
}
else if (product == 0)
{
product = nums[i];
}
else
{
max = product > max ? product : max;
product *= nums[i];
}
last = product;
lastIndex = i;
}
}
if (last < 0 && lastIndex != 0 && product < 0)
{
product /= last;
}
max = product > max ? product : max;
return max;
}
};
参考答案
class Solution {
public:
int maxProduct(vector<int>& nums) {
int maxF = nums[0], minF = nums[0], ans = nums[0];
for (int i = 1; i < nums.size(); ++i) {
int mx = maxF, mn = minF;
maxF = max(mx * nums[i], max(nums[i], mn * nums[i]));
minF = min(mn * nums[i], min(nums[i], mx * nums[i]));
ans = max(maxF, ans);
}
return ans;
}
};
感想
动态规划优化后只需要常数空间, 就是存上一个位置包含其自身的最大最小值
155. 最小栈(medium)
2023/9/3
题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
-231 <= val <= 231 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 104次
我的答案
class MinStack {
public:
MinStack() {
}
void push(int val) {
stk.push(val);
if (map.find(val) == map.end())
{
map.insert({val, 1});
}
else
{
map[val]++;
}
}
void pop() {
// set.erase(set.find(stk.top()));
map[stk.top()]--;
if (map[stk.top()] == 0)
{
map.erase(map.find(stk.top()));
}
stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return map.begin()->first;
}
private:
stack<int> stk;
map<int, int> map;
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
参考答案
class MinStack {
stack<int> x_stack;
stack<int> min_stack;
public:
MinStack() {
min_stack.push(INT_MAX);
}
void push(int x) {
x_stack.push(x);
min_stack.push(min(min_stack.top(), x));
}
void pop() {
x_stack.pop();
min_stack.pop();
}
int top() {
return x_stack.top();
}
int getMin() {
return min_stack.top();
}
};
感想
竟然真的可以用stl, 维护两个栈和维护一个栈一个红黑树也差不多了
160. 相交链表(easy)
2023/9/3
题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中（从头节点开始）跳到交叉节点的节点数skipB- 在listB中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
listA中节点数目为mlistB中节点数目为n1 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点，intersectVal为0 - 如果
listA和listB有交点，intersectVal == listA[skipA] == listB[skipB]
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
我的答案
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p1 = headA, *p2 = headB;
if (p1 == nullptr || p2 == nullptr)
{
return nullptr;
}
int len1 = 0, len2 = 0;
while (p1->next != nullptr)
{
p1 = p1->next;
len1++;
}
while (p2->next != nullptr)
{
p2 = p2->next;
len2++;
}
if (p1 != p2)
{
return nullptr;
}
int diff;
p1 = headA;
p2 = headB;
if (len1 < len2)
{
diff = len2 - len1;
while (diff > 0)
{
p2 = p2->next;
diff--;
}
}
else if (len1 > len2)
{
diff = len1 - len2;
while (diff > 0)
{
p1 = p1->next;
diff--;
}
}
while (p1 != nullptr)
{
if (p1 == p2)
{
return p1;
}
p1 = p1->next;
p2 = p2->next;
}
return nullptr;
}
};
参考答案
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode *pA = headA, *pB = headB;
while (pA != pB) {
pA = pA == nullptr ? headB : pA->next;
pB = pB == nullptr ? headA : pB->next;
}
return pA;
}
};
感想
快慢指针yyds
不过题解的方法代码量更少, 就是换条路走, 其实本质上和我的没区别, 都是第二圈相遇, 指针需要移动的次数完全一样
169. 多数元素(easy)
2023/9/4
00 : 03 : 53
题目描述
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
我的答案
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> map;
int n = nums.size();
for (int i = 0; i < n; ++i)
{
if (map.find(nums[i]) != map.end())
{
map[nums[i]]++;
if (map[nums[i]] > n/2)
{
return nums[i];
}
}
else
{
map.insert({nums[i], 1});
if (map[nums[i]] > n/2)
{
return nums[i];
}
}
}
return false;
}
};
参考答案
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = -1;
int count = 0;
for (int num : nums) {
if (num == candidate)
++count;
else if (--count < 0) {
candidate = num;
count = 1;
}
}
return candidate;
}
};
感想
这个题有个很不错的算法Boyer-Moore, 引用评论区的解释:
“同归于尽消杀法” ：
由于多数超过50%, 比如100个数，那么多数至少51个，剩下少数是49个。
- 第一个到来的士兵，直接插上自己阵营的旗帜占领这块高地，此时领主 winner 就是这个阵营的人，现存兵力 count = 1。
- 如果新来的士兵和前一个士兵是同一阵营，则集合起来占领高地，领主不变，winner 依然是当前这个士兵所属阵营，现存兵力 count++；
- 如果新来到的士兵不是同一阵营，则前方阵营派一个士兵和它同归于尽。 此时前方阵营兵力count --。（即使双方都死光，这块高地的旗帜 winner 依然不变，因为已经没有活着的士兵可以去换上自己的新旗帜）
- 当下一个士兵到来，发现前方阵营已经没有兵力，新士兵就成了领主，winner 变成这个士兵所属阵营的旗帜，现存兵力 count ++。
就这样各路军阀一直以这种以一敌一同归于尽的方式厮杀下去，直到少数阵营都死光，那么最后剩下的几个必然属于多数阵营，winner 就是多数阵营。（多数阵营 51个，少数阵营只有49个，死剩下的2个就是多数阵营的人）
198. 打家劫舍(medium)
2023/9/4
00 : 07 : 22
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
我的答案
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
int *dp = new int[n+1]();
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= n; ++i)
{
dp[i] = max(dp[i-2]+nums[i-1], dp[i-1]);
}
return dp[n];
}
};
参考答案
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
int size = nums.size();
if (size == 1) {
return nums[0];
}
int first = nums[0], second = max(nums[0], nums[1]);
for (int i = 2; i < size; i++) {
int temp = second;
second = max(first + nums[i], second);
first = temp;
}
return second;
}
};
感想
考虑到每个dp只与前两次的结果有关, 可以使用大小为3的滚动数组优化空间
200. 岛屿数量(medium)
2023/9/4
00 : 12 : 04
题目描述
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
我的答案
class Solution {
public:
void dfs(int i, int j, vector<vector<char>>& grid, vector<vector<bool>>& visited)
{
visited[i][j] = true;
int m = grid.size();
int n = grid[0].size();
if (i > 0 && grid[i-1][j] == '1' && visited[i-1][j] == false)
{
dfs(i-1, j, grid, visited);
}
if (j > 0 && grid[i][j-1] == '1' && visited[i][j-1] == false)
{
dfs(i, j-1, grid, visited);
}
if (i < m-1 && grid[i+1][j] == '1' && visited[i+1][j] == false)
{
dfs(i+1, j, grid, visited);
}
if (j < n-1 && grid[i][j+1] == '1' && visited[i][j+1] == false)
{
dfs(i, j+1, grid, visited);
}
}
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
int res = 0;
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
if (visited[i][j])
{
continue;
}
else
{
visited[i][j] = true;
}
if (grid[i][j] == '1')
{
dfs(i, j, grid, visited);
res++;
}
}
}
return res;
}
};
参考答案
class Solution {
private:
void dfs(vector<vector<char>>& grid, int r, int c) {
int nr = grid.size();
int nc = grid[0].size();
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
}
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
};
感想
还可以广度优先优化空间也可以用并查集, 但是我觉得还是dfs最直观
206. 反转链表(easy)
2023/9/4
00 : 05 : 59
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
我的答案
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* ret = head;
if (ret == nullptr)
{
return ret;
}
ListNode* p = ret->next;
ret->next = nullptr;
while (p != nullptr)
{
ListNode *tmp = p->next;
p->next = ret;
ret = p;
p = tmp;
}
return ret;
}
};
参考答案
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};
感想
经典头插, 迭代比递归省了很多栈空间(O(1))
207. 课程表(medium)
2023/9/4
01 : 04 : 44
题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
提示：
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[i]中的所有课程对 互不相同
我的答案
class Solution {
public:
int FindIndex(vector<int>& comein, vector<bool>& visited)
{
int n = comein.size();
for (int i = 0; i < n; ++i)
{
if (visited[i] == false && comein[i] == 0)
{
return i;
}
}
return -1;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<bool>> g(numCourses, vector<bool>(numCourses, false));
vector<int> comein(numCourses, 0);
for (auto& it : prerequisites)
{
g[it[0]][it[1]] = true;
comein[it[1]]++;
}
vector<bool> visited(numCourses, false);
int index = FindIndex(comein, visited);
while (index != -1)
{
for (int i = 0; i < numCourses; ++i)
{
if (g[index][i] == true)
{
comein[i]--;
}
}
visited[index] = true;
index = FindIndex(comein, visited);
}
for (int i = 0; i < numCourses; ++i)
{
if (visited[i] == false)
{
return false;
}
}
return true;
}
};
参考答案
class Solution {
private:
vector<vector<int>> edges;
vector<int> visited;
bool valid = true;
public:
void dfs(int u) {
visited[u] = 1;
for (int v: edges[u]) {
if (visited[v] == 0) {
dfs(v);
if (!valid) {
return;
}
}
else if (visited[v] == 1) {
valid = false;
return;
}
}
visited[u] = 2;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
edges.resize(numCourses);
visited.resize(numCourses);
for (const auto& info: prerequisites) {
edges[info[1]].push_back(info[0]);
}
for (int i = 0; i < numCourses && valid; ++i) {
if (!visited[i]) {
dfs(i);
}
}
return valid;
}
};
感想
就是拓扑排序, 对于有向图找入度为0, 弹出, 消边; 对于无向图, 找度<=1
208. 实现 Trie (前缀树)(medium)
2023/9/5
00 : 20 : 37
题目描述
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
示例：
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
提示：
1 <= word.length, prefix.length <= 2000word和prefix仅由小写英文字母组成insert、search和startsWith调用次数 总计 不超过3 * 104次
我的答案
class Trie {
public:
Trie() {
dummy = new TrieNode;
}
void insert(string word) {
int len = word.size();
TrieNode *p = dummy;
for (int i = 0; i < len; ++i)
{
if (p->next.find(word[i]) != p->next.end())
{
p = p->next[word[i]];
}
else
{
p->next.insert({word[i], new TrieNode});
p = p->next[word[i]];
}
}
p->isEnd = true;
}
bool search(string word) {
int len = word.size();
TrieNode *p = dummy;
for (int i = 0; i < len; ++i)
{
if (p->next.find(word[i]) != p->next.end())
{
p = p->next[word[i]];
}
else
{
return false;
}
}
return p->isEnd;
}
bool startsWith(string prefix) {
int len = prefix.size();
TrieNode *p = dummy;
for (int i = 0; i < len; ++i)
{
if (p->next.find(prefix[i]) != p->next.end())
{
p = p->next[prefix[i]];
}
else
{
return false;
}
}
return true;
}
struct TrieNode
{
bool isEnd = false;
unordered_map<char, TrieNode*> next;
};
TrieNode* dummy;
};
参考答案
class Trie {
private:
vector<Trie*> children;
bool isEnd;
Trie* searchPrefix(string prefix) {
Trie* node = this;
for (char ch : prefix) {
ch -= 'a';
if (node->children[ch] == nullptr) {
return nullptr;
}
node = node->children[ch];
}
return node;
}
public:
Trie() : children(26), isEnd(false) {}
void insert(string word) {
Trie* node = this;
for (char ch : word) {
ch -= 'a';
if (node->children[ch] == nullptr) {
node->children[ch] = new Trie();
}
node = node->children[ch];
}
node->isEnd = true;
}
bool search(string word) {
Trie* node = this->searchPrefix(word);
return node != nullptr && node->isEnd;
}
bool startsWith(string prefix) {
return this->searchPrefix(prefix) != nullptr;
}
};
感想
完全忘记前缀树了, 看了下前缀树的表示方法就可以很轻松的做出来, 所以这题的重点是要记得前缀树的样子, 相较于题解, 我的做法优化了空间, 但是由于要经常在哈希表中插入, 所以速度稍慢于题解
215. 数组中的第K个最大元素(medium)
2023/9/5
00 : 08 : 35
题目描述
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
我的答案
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> min_heap;
int size = nums.size();
min_heap.push(nums[0]);
for (int i = 1; i < size; ++i)
{
if (min_heap.size() < k)
{
min_heap.push(nums[i]);
}
else if (nums[i] > min_heap.top())
{
min_heap.pop();
min_heap.push(nums[i]);
}
}
return min_heap.top();
}
};
参考答案
class Solution {
public:
int quickselect(vector<int> &nums, int l, int r, int k) {
if (l == r)
return nums[k];
int partition = nums[l], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (nums[i] < partition);
do j--; while (nums[j] > partition);
if (i < j)
swap(nums[i], nums[j]);
}
if (k <= j)return quickselect(nums, l, j, k);
else return quickselect(nums, j + 1, r, k);
}
int findKthLargest(vector<int> &nums, int k) {
int n = nums.size();
return quickselect(nums, 0, n - 1, n - k);
}
};
感想
经典topK问题, 可以用快速选择(简单来说就是只要递归一半的快排)或者堆排, 不过真要到面试的时候可能要自己手撕一个最小堆, 就不如快排省事了
221. 最大正方形(medium)
2023/9/5
00 : 56 : 54
题目描述
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
示例 2：
输入：matrix = [["0","1"],["1","0"]]
输出：1
示例 3：
输入：matrix = [["0"]]
输出：0
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j]为'0'或'1'
我的答案
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
int maxSide = 0;
for (int i = 1; i < m+1; ++i)
{
for (int j = 1; j < n+1; ++j)
{
if (matrix[i-1][j-1] == '0')
{
dp[i][j] = 0;
}
else
{
dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
maxSide = dp[i][j] > maxSide ? dp[i][j] : maxSide;
}
}
}
return maxSide * maxSide;
}
};
参考答案
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) {
return 0;
}
int maxSide = 0;
int rows = matrix.size(), columns = matrix[0].size();
vector<vector<int>> dp(rows, vector<int>(columns));
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
maxSide = max(maxSide, dp[i][j]);
}
}
}
int maxSquare = maxSide * maxSide;
return maxSquare;
}
};
感想
一开始写的时候因为想到了85最大矩形, 所以一直在写用单调栈的方法, 写着写着感觉不对劲, 好像很浪费, 看了眼题解, 竟然只需要dp就可以了(), 于是用dp重写, 很快能ac
226. 翻转二叉树(easy)
2023/9/5
00 : 02 : 28
题目描述
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
提示：
- 树中节点数目范围在
[0, 100]内 -100 <= Node.val <= 100
我的答案
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr)
{
return root;
}
TreeNode* tmp = root->left;
root->left = invertTree(root->right);
root->right = invertTree(tmp);
return root;
}
};
参考答案
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};
感想
递归实现, 很简单
234. 回文链表(easy)
2023/9/5
00 : 26 : 21
题目描述
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
- 链表中节点数目在范围
[1, 105]内 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
我的答案
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr)
{
return head;
}
ListNode *slow = head, *fast = head->next;
ListNode *half = nullptr;
int cnt = 0;
while (fast != nullptr && fast->next != nullptr)
{
ListNode* tmp = slow;
slow = slow->next;
tmp->next = half;
half = tmp;
fast = fast->next->next;
cnt++;
}
if (fast != nullptr)
{
ListNode* tmp = slow;
slow = slow->next;
tmp->next = half;
half = tmp;
}
else
{
slow = slow->next;
}
while (half != nullptr || slow != nullptr)
{
if (half == nullptr || slow == nullptr)
{
return false;
}
if (half->val != slow->val)
{
return false;
}
else
{
half = half->next;
slow = slow->next;
}
}
return true;
}
};
参考答案
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode* firstHalfEnd = endOfFirstHalf(head);
ListNode* secondHalfStart = reverseList(firstHalfEnd->next);
// 判断是否回文
ListNode* p1 = head;
ListNode* p2 = secondHalfStart;
bool result = true;
while (result && p2 != nullptr) {
if (p1->val != p2->val) {
result = false;
}
p1 = p1->next;
p2 = p2->next;
}
// 还原链表并返回结果
firstHalfEnd->next = reverseList(secondHalfStart);
return result;
}
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
ListNode* endOfFirstHalf(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
};
感想
上来就直奔最优解去了, 和题解几乎一样的思路, 先快慢指针找中点, 然后反转其中的一半链表, 再逐个比较
236. 二叉树的最近公共祖先(medium)
2023/9/6
00 : 19 : 40
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
- 树中节点数目在范围
[2, 105]内。 -109 <= Node.val <= 109- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
我的答案
class Solution {
public:
bool dfs(TreeNode *root, TreeNode *p, vector<TreeNode*> &prev)
{
if (root == nullptr)
{
return false;
}
else
{
prev.push_back(root);
}
if (root == p)
{
return true;
}
if (dfs(root->left, p, prev) || dfs(root->right, p, prev))
{
return true;
}
else
{
prev.pop_back();
return false;
}
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> prevp, prevq;
dfs(root, p, prevp);
dfs(root, q, prevq);
int p_size = prevp.size();
int q_size = prevq.size();
TreeNode *tmp = nullptr;
for (int i = 0; i < p_size && i < q_size; ++i)
{
if (prevp[i] == prevq[i])
{
tmp = prevp[i];
}
}
return tmp;
}
};
参考答案
class Solution {
public:
TreeNode* ans;
bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) return false;
bool lson = dfs(root->left, p, q);
bool rson = dfs(root->right, p, q);
if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
ans = root;
}
return lson || rson || (root->val == p->val || root->val == q->val);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
dfs(root, p, q);
return ans;
}
};
感想
看了题解, 我多遍历了一次, 效率和空间都有损耗, 直接在dfs的过程中判断是最好的
238. 除自身以外数组的乘积(medium)
2023/9/6
00 : 11 : 03
题目描述
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(*n*) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
提示：
2 <= nums.length <= 105-30 <= nums[i] <= 30- 保证 数组
nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
我的答案
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int size = nums.size();
vector<int> preProd(size, 0), postProd(size, 0), res(size, 0);
postProd[size - 1] = nums[size - 1];
preProd[0] = nums[0];
for (int i = 1; i < size; ++i)
{
preProd[i] = preProd[i-1] * nums[i];
postProd[size-1-i] = postProd[size-i] * nums[size-1-i];
}
res[0] = postProd[1];
res[size-1] = preProd[size-2];
for (int i = 1; i < size-1; ++i)
{
res[i] = preProd[i-1] * postProd[i+1];
}
return res;
}
};
参考答案
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int length = nums.size();
// L 和 R 分别表示左右两侧的乘积列表
vector<int> L(length, 0), R(length, 0);
vector<int> answer(length);
// L[i] 为索引 i 左侧所有元素的乘积
// 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
L[0] = 1;
for (int i = 1; i < length; i++) {
L[i] = nums[i - 1] * L[i - 1];
}
// R[i] 为索引 i 右侧所有元素的乘积
// 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
R[length - 1] = 1;
for (int i = length - 2; i >= 0; i--) {
R[i] = nums[i + 1] * R[i + 1];
}
// 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
for (int i = 0; i < length; i++) {
answer[i] = L[i] * R[i];
}
return answer;
}
};
感想
O(1)不能做到, 题解说输出的数组不算空间, emmm, 反正就是把一个dp的数组当成是输出数组, 本质还是左右乘积列表
239. 滑动窗口最大值(hard)
2023/9/6
00 : 26 : 35
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
我的答案
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
priority_queue<int, vector<int>, less<int>> max_heap;
unordered_map<int, int> hash;
int size = nums.size();
vector<int> res;
for (int i = 0; i < k; ++i)
{
max_heap.push(nums[i]);
}
for (int i = k; i < size; ++i)
{
int top = max_heap.top();
while (hash.find(top) != hash.end() && hash[top] > 0)
{
hash[top]--;
max_heap.pop();
top = max_heap.top();
}
res.push_back(top);
if (hash.find(nums[i-k]) != hash.end())
{
hash[nums[i-k]]++;
}
else
{
hash.insert({nums[i-k], 1});
}
max_heap.push(nums[i]);
}
int top = max_heap.top();
while (hash.find(top) != hash.end() && hash[top] > 0)
{
hash[top]--;
max_heap.pop();
top = max_heap.top();
}
res.push_back(top);
return res;
}
};
参考答案
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
deque<int> q;
for (int i = 0; i < k; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
}
vector<int> ans = {nums[q.front()]};
for (int i = k; i < n; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
while (q.front() <= i - k) {
q.pop_front();
}
ans.push_back(nums[q.front()]);
}
return ans;
}
};
感想
单调队列是个很聪明的方法, 但是不容易想到, 相反维护一个最小堆就是很自然的想法, 要注意stl的priority_queue是没有删除指定元素的操作的, 可以用额外的空间存信息来判断当前top是否是不在窗口内的, 如果不在则pop出去
240. 搜索二维矩阵 II(medium)
2023/9/6
00 : 27 : 17
题目描述
编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrix[i][j] <= 109- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
-109 <= target <= 109
我的答案
class Solution {
public:
bool search(vector<vector<int>>& matrix, int target, int x1, int y1, int x2, int y2)
{
if (x1 > x2 || y1 > y2)
{
return false;
}
if (target == matrix[x1][y1] || target == matrix[x2][y2])
{
return true;
}
else if (target < matrix[x1][y1] || target > matrix[x2][y2] || x1==x2&&y1==y2)
{
return false;
}
int xm = x1 + (x2-x1) / 2, ym = y1 + (y2-y1) / 2;
return search(matrix, target, x1, y1, xm, ym) ||
search(matrix, target, xm+1, ym+1, x2, y2) ||
search(matrix, target, xm+1, y1, x2, ym) ||
search(matrix, target, x1, ym+1, xm, y2);
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
return search(matrix, target, 0, 0, m-1, n-1);
}
};
参考答案
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for (const auto& row: matrix) {
auto it = lower_bound(row.begin(), row.end(), target);
if (it != row.end() && *it == target) {
return true;
}
}
return false;
}
};
感想
独创的四分查找(bushi), 感觉不如逐行二分
279. 完全平方数(medium)
2023/9/6
00 : 27 : 46
题目描述
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
提示：
1 <= n <= 104
我的答案
class Solution {
public:
int numSquares(int n) {
int min = n;
for (int i = 1; i*i <= n; ++i)
{
int tmp = n / (i*i) + numSquares(n%(i*i));
min = min < tmp ? min : tmp;
}
return min;
}
};
参考答案
class Solution {
public:
int numSquares(int n) {
vector<int> f(n + 1);
for (int i = 1; i <= n; i++) {
int minn = INT_MAX;
for (int j = 1; j * j <= i; j++) {
minn = min(minn, f[i - j * j]);
}
f[i] = minn + 1;
}
return f[n];
}
};
感想
确实该用dp的, 递归多了很多次重复
283. 移动零(easy)
2023/9/7
00 : 02 : 38
题目描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
进阶：你能尽量减少完成的操作次数吗？
我的答案
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int cnt = 0;
for (int i = 0; i < n; ++i)
{
if (nums[i] != 0)
{
swap(nums[i], nums[cnt++]);
}
}
}
};
参考答案
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size(), left = 0, right = 0;
while (right < n) {
if (nums[right]) {
swap(nums[left], nums[right]);
left++;
}
right++;
}
}
};
感想
很简单, 双指针交换即可
287. 寻找重复数(medium)
2023/9/7
00 : 52 : 22
题目描述
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
提示：
1 <= n <= 105nums.length == n + 11 <= nums[i] <= nnums中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
- 如何证明
nums中至少存在一个重复的数字? - 你可以设计一个线性级时间复杂度
O(n)的解决方案吗？
我的答案
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = 0, fast = 0;
do
{
slow = nums[slow];
fast = nums[nums[fast]];
}while (slow != fast);
slow = 0;
while (slow != fast)
{
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};
参考答案
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = 0, fast = 0;
do
{
slow = nums[slow];
fast = nums[nums[fast]];
}while (slow != fast);
slow = 0;
while (slow != fast)
{
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};
感想
想不到O(n)+O(1)的算法, 看了题解再写的
297. 二叉树的序列化与反序列化(hard)
2023/9/7
00 : 25 : 36
题目描述
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例 1：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
提示：
- 树中结点数在范围
[0, 104]内 -1000 <= Node.val <= 1000
我的答案
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
void rserialize(TreeNode* root, string& str) {
if (root == nullptr)
{
str += "None,";
}
else
{
str += to_string(root->val)+',';
rserialize(root->left, str);
rserialize(root->right, str);
}
}
TreeNode* rdeserialize(list<string>& data) {
if (data.front() == "None")
{
data.erase(data.begin());
return nullptr;
}
TreeNode* root = new TreeNode(stoi(data.front()));
data.erase(data.begin());
root->left = rdeserialize(data);
root->right = rdeserialize(data);
return root;
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string str;
rserialize(root, str);
return str;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
list<string> dataArray;
string str;
for (auto &ch : data)
{
if (ch == ',')
{
dataArray.push_back(str);
str.clear();
}
else
{
str += ch;
}
}
return rdeserialize(dataArray);
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
参考答案
class Codec {
public:
void rserialize(TreeNode* root, string& str) {
if (root == nullptr) {
str += "None,";
} else {
str += to_string(root->val) + ",";
rserialize(root->left, str);
rserialize(root->right, str);
}
}
string serialize(TreeNode* root) {
string ret;
rserialize(root, ret);
return ret;
}
TreeNode* rdeserialize(list<string>& dataArray) {
if (dataArray.front() == "None") {
dataArray.erase(dataArray.begin());
return nullptr;
}
TreeNode* root = new TreeNode(stoi(dataArray.front()));
dataArray.erase(dataArray.begin());
root->left = rdeserialize(dataArray);
root->right = rdeserialize(dataArray);
return root;
}
TreeNode* deserialize(string data) {
list<string> dataArray;
string str;
for (auto& ch : data) {
if (ch == ',') {
dataArray.push_back(str);
str.clear();
} else {
str.push_back(ch);
}
}
if (!str.empty()) {
dataArray.push_back(str);
str.clear();
}
return rdeserialize(dataArray);
}
};
感想
也是几乎对着答案写的, 想复杂了感觉, 而且也不太熟悉to_string和stoi这俩函数
300. 最长递增子序列(medium)
2023/9/7
01 : 06 : 25
题目描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104
进阶：
- 你能将算法的时间复杂度降低到
O(n log(n))吗?
我的答案
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> res;
for (int i = 0; i < n; ++i)
{
auto p = lower_bound(res.begin(), res.end(), nums[i]);
if (p == res.end())
{
res.push_back(nums[i]);
}
else
{
swap(*p, nums[i]);
}
}
return res.size();
}
};
参考答案
略
感想
很神奇的算法, 看着答案写的也是, 对着代码理解是最容易理解的了()
301. 删除无效的括号(hard)
2023/9/7
00 : 46 : 33
题目描述
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25s由小写英文字母以及括号'('和')'组成s中至多含20个括号
我的答案
class Solution {
public:
int max = 0;
void backTrace(string s, vector<string>& ret, int state, string str)
{
if (state < 0 || s.size() < state || s.size() + str.size() < max)
{
return;
}
if (s.size() == 0)
{
if (state == 0)
{
if (max < str.size())
{
ret = vector<string>(1, str);
max = str.size();
}
else if (max == str.size() && find(ret.begin(), ret.end(), str) == ret.end())
{
ret.push_back(str);
}
}
return;
}
if (s[0] == '(')
{
backTrace(s.substr(1), ret, state+1, str+'(');
backTrace(s.substr(1), ret, state, str);
}
else if (s[0] == ')')
{
backTrace(s.substr(1), ret, state-1, str+')');
backTrace(s.substr(1), ret, state, str);
}
else
{
backTrace(s.substr(1), ret, state, str+s[0]);
}
}
vector<string> removeInvalidParentheses(string s) {
vector<string> ret;
backTrace(s, ret, 0, "");
return ret;
}
};
参考答案
class Solution {
public:
vector<string> res;
vector<string> removeInvalidParentheses(string s) {
int lremove = 0;
int rremove = 0;
for (char c : s) {
if (c == '(') {
lremove++;
} else if (c == ')') {
if (lremove == 0) {
rremove++;
} else {
lremove--;
}
}
}
helper(s, 0, lremove, rremove);
return res;
}
void helper(string str, int start, int lremove, int rremove) {
if (lremove == 0 && rremove == 0) {
if (isValid(str)) {
res.push_back(str);
}
return;
}
for (int i = start; i < str.size(); i++) {
if (i != start && str[i] == str[i - 1]) {
continue;
}
// 如果剩余的字符无法满足去掉的数量要求，直接返回
if (lremove + rremove > str.size() - i) {
return;
}
// 尝试去掉一个左括号
if (lremove > 0 && str[i] == '(') {
helper(str.substr(0, i) + str.substr(i + 1), i, lremove - 1, rremove);
}
// 尝试去掉一个右括号
if (rremove > 0 && str[i] == ')') {
helper(str.substr(0, i) + str.substr(i + 1), i, lremove, rremove - 1);
}
}
}
inline bool isValid(const string & str) {
int cnt = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') {
cnt++;
} else if (str[i] == ')') {
cnt--;
if (cnt < 0) {
return false;
}
}
}
return cnt == 0;
}
};
感想
回溯说得好听, 其实就是暴力破解, 加入了一点剪枝而已, 时间复杂度很高, 但是看题解的几个方法都是\(O(n\times 2^n)\)的复杂度, 所以我选择最自然的回溯剪枝算法了
309. 买卖股票的最佳时机含冷冻期(medium)
2023/9/8
00 : 46 : 47
题目描述
给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
提示：
1 <= prices.length <= 50000 <= prices[i] <= 1000
我的答案
class Solution {
public:
int max(int x, int y)
{
return x > y ? x : y;
}
int maxProfit(vector<int>& prices) {
int n = prices.size();
int res = 0;
vector<vector<int>> dp(n, vector<int>(3, 0));
// dp[i][0] -> 第i天买入的收益
// dp[i][1] -> 第i天冷冻期的收益
// dp[i][2] -> 第i天卖出的收益
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
for (int i = 1; i < n; ++i)
{
dp[i][0] = dp[i-1][1] - prices[i];
dp[i][1] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2]));
for (int j = 0; j < i; ++j)
{
dp[i][2] = max(dp[i][2], dp[j][0] + prices[i]);
}
res = max(res, dp[i][2]);
}
return res;
}
};
参考答案
int maxProfit(vector<int>& prices) {
if(prices.size()==1)
return 0;
vector<vector<int>> dp(prices.size(),vector<int>(2));
dp[0][0]=-prices[0];
dp[1][0]=max(-prices[0],-prices[1]);
dp[1][1]=max(0,prices[1]-prices[0]);
for(int i=2;i<prices.size();i++){
dp[i][0]=max(dp[i-1][0],dp[i-2][1]-prices[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);
}
return dp[prices.size()-1][1];
}
感想
知道是dp, 但是想不到这个dp的方式, 还是要多做
312. 戳气球(hard)
2023/9/8
题目描述
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
示例 2：
输入：nums = [1,5]
输出：10
提示：
n == nums.length1 <= n <= 3000 <= nums[i] <= 100
我的答案
class Solution {
public:
int FindMaxProfit(vector<int> &profits)
{
int max = profits[0];
int index = 0;
int n = profits.size();
for (int i = 1; i < n; ++i)
{
if (profits[i] > max)
{
max = profits[i];
index = i;
}
}
return index;
}
int maxCoins(vector<int> &nums)
{
int n = nums.size();
vector<int> profits(n, 0);
if (n == 1)
{
return nums[0];
}
else if (n == 0)
{
return 0;
}
int res = 0;
nums.insert(nums.begin(), 1);
nums.insert(nums.begin(), 1);
nums.push_back(1);
nums.push_back(1);
for (int i = 0; i < n; ++i)
{
int j = i;
i += 2;
profits[j] = nums[i - 1] * nums[i] * nums[i + 1] + nums[i - 2] * nums[i - 1] * (nums[i + 1] - nums[i]) + nums[i + 2] * nums[i + 1] * (nums[i - 1] - nums[i]);
i -= 2;
}
while (!profits.empty())
{
int index = FindMaxProfit(profits);
res += nums[index + 1] * nums[index + 2] * nums[index + 3];
nums.erase(nums.begin() + index + 2);
profits.erase(profits.begin() + index);
int i;
if (index > 0)
{
i = index + 1;
profits[index - 1] = nums[i - 1] * nums[i] * nums[i + 1] + nums[i - 2] * nums[i - 1] * (nums[i + 1] - nums[i]) + nums[i + 2] * nums[i + 1] * (nums[i - 1] - nums[i]);
}
if (index > 1)
{
i = index;
profits[index - 2] = nums[i - 1] * nums[i] * nums[i + 1] + nums[i - 2] * nums[i - 1] * (nums[i + 1] - nums[i]) + nums[i + 2] * nums[i + 1] * (nums[i - 1] - nums[i]);
}
if (index < profits.size())
{
i = index + 2;
profits[index] = nums[i - 1] * nums[i] * nums[i + 1] + nums[i - 2] * nums[i - 1] * (nums[i + 1] - nums[i]) + nums[i + 2] * nums[i + 1] * (nums[i - 1] - nums[i]);
}
if (index < profits.size() - 1)
{
i = index + 3;
profits[index + 1] = nums[i - 1] * nums[i] * nums[i + 1] + nums[i - 2] * nums[i - 1] * (nums[i + 1] - nums[i]) + nums[i + 2] * nums[i + 1] * (nums[i - 1] - nums[i]);
}
}
return res;
}
};
参考答案
class Solution {
public:
vector<vector<int>> rec;
vector<int> val;
public:
int solve(int left, int right) {
if (left >= right - 1) {
return 0;
}
if (rec[left][right] != -1) {
return rec[left][right];
}
for (int i = left + 1; i < right; i++) {
int sum = val[left] * val[i] * val[right];
sum += solve(left, i) + solve(i, right);
rec[left][right] = max(rec[left][right], sum);
}
return rec[left][right];
}
int maxCoins(vector<int>& nums) {
int n = nums.size();
val.resize(n + 2);
for (int i = 1; i <= n; i++) {
val[i] = nums[i - 1];
}
val[0] = val[n + 1] = 1;
rec.resize(n + 2, vector<int>(n + 2, -1));
return solve(0, n + 1);
}
};
感想
用的贪心, 没做出来, 很好的证明了局部最优不是全局最优(), 这题放弃了, 浅浅记录一下思路: 不要考虑删除, 而是考虑一个一个增加, \(dp[i][j]\)表示从i到j填满能获得的最大收益
322. 零钱兑换(medium)
2023/9/8
01 : 26 : 31
题目描述
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
我的答案
class Solution {
public:
int FindMin(vector<int>& coins, vector<int>& dp, int &index)
{
int min = 0x3f3f3f3f;
for (auto & i : coins)
{
if (index >= i)
{
min = min < dp[index-i] ? min : dp[index-i];
}
}
return min;
}
int coinChange(vector<int>& coins, int amount) {
if (amount == 0)
{
return 0;
}
vector<int> dp(amount+1, 0x3f3f3f3f);
dp[0] = 0;
for (int i = 1; i < amount+1; ++i)
{
int min = FindMin(coins, dp, i);
if (min < 0x3f3f3f3f)
dp[i] = min + 1;
}
if (dp[amount] != 0x3f3f3f3f)
{
return dp[amount];
}
else
{
return -1;
}
}
};
参考答案
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int Max = amount + 1;
vector<int> dp(amount + 1, Max);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int j = 0; j < (int)coins.size(); ++j) {
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
感想
这个dp竟然真的是用的amount的大小, 其实我老早就想到这个方法了, 但是脑测可能会超时间和空间于是就没有写下去, 在尝试了其他方案无果之后最终还是妥协了, 时间竟然还超过了85.12%
337. 打家劫舍 III(medium)
2023/9/8
00 : 33 : 22
题目描述
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
提示：
- 树的节点数在
[1, 104]范围内 0 <= Node.val <= 104
我的答案
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
unordered_map<TreeNode*, int> notInc;
unordered_map<TreeNode*, int> Inc;
int Include(TreeNode* root)
{
if (Inc.find(root) != Inc.end())
{
return Inc[root];
}
int tmp = root->val+NotInclude(root->left)+NotInclude(root->right);
Inc.insert({root, tmp});
return tmp;
}
int NotInclude(TreeNode* root)
{
if (root == nullptr)
{
return 0;
}
if (notInc.find(root) != notInc.end())
{
return notInc[root];
}
int tmp, a = 0, b = 0;
if (root->left != nullptr)
{
tmp = NotInclude(root->left);
a = Include(root->left);
a = a > tmp ? a : tmp;
}
if (root->right != nullptr)
{
tmp = NotInclude(root->right);
b = Include(root->right);
b = b > tmp ? b : tmp;
}
notInc.insert({root, a+b});
return a + b;
}
int rob(TreeNode* root) {
if (root == nullptr)
{
return 0;
}
int a = Include(root);
int b = NotInclude(root);
return a > b ? a : b;
}
};
参考答案
class Solution {
public:
unordered_map <TreeNode*, int> f, g;
void dfs(TreeNode* node) {
if (!node) {
return;
}
dfs(node->left);
dfs(node->right);
f[node] = node->val + g[node->left] + g[node->right];
g[node] = max(f[node->left], g[node->left]) + max(f[node->right], g[node->right]);
}
int rob(TreeNode* root) {
dfs(root);
return max(f[root], g[root]);
}
};
感想
十分钟就只差最后两个点没过了, 时间超了, 然后优化了很多代码还是超了, 突然想到有很多重复计算, 于是使用了哈希表, 最后和标准答案已经差不多了
338. 比特位计数(easy)
2023/9/8
00 : 06 : 06
题目描述
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
提示：
0 <= n <= 105
进阶：
- 很容易就能实现时间复杂度为
O(n log n)的解决方案，你可以在线性时间复杂度O(n)内用一趟扫描解决此问题吗？ - 你能不使用任何内置函数解决此问题吗？（如，C++ 中的
__builtin_popcount）
我的答案
class Solution {
public:
int Count(int x)
{
int cnt = 0;
while (x)
{
cnt += x % 2 ? 1 : 0;
x /= 2;
}
return cnt;
}
vector<int> countBits(int n) {
vector<int> res(n+1, 0);
for (int i = 1; i < n+1; ++i)
{
res[i] = Count(i);
}
return res;
}
};
参考答案
class Solution {
public:
vector<int> countBits(int n) {
vector<int> bits(n + 1);
for (int i = 1; i <= n; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
};
感想
需要理解的是x&(x-1)是x去掉最后一位1之后的数, 根据这个特性就可以dp了
347. 前 K 个高频元素(medium)
2023/9/8
题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
1 <= nums.length <= 105k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
我的答案
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> map;
int n = nums.size();
for (int i = 0; i < n; ++i)
{
if (map.find(nums[i]) != map.end())
{
map[nums[i]]++;
}
else
{
map.insert({nums[i], 1});
}
}
int cnt = 0;
vector<int> res(k, 0);
auto cmp = [&](int p1, int p2){ return map[p1] > map[p2]; };
priority_queue<int, vector<int>, decltype(cmp)> heap(cmp);
for (auto & it : map)
{
if (cnt < k)
{
heap.push(it.first);
cnt++;
}
else if (it.second > map[heap.top()])
{
heap.pop();
heap.push(it.first);
}
}
for (int i = 0; i < k; ++i)
{
res[i] = heap.top();
heap.pop();
}
return res;
}
};
参考答案
class Solution {
public:
static bool cmp(pair<int, int>& m, pair<int, int>& n) {
return m.second > n.second;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> occurrences;
for (auto& v : nums) {
occurrences[v]++;
}
// pair 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);
for (auto& [num, count] : occurrences) {
if (q.size() == k) {
if (q.top().second < count) {
q.pop();
q.emplace(num, count);
}
} else {
q.emplace(num, count);
}
}
vector<int> ret;
while (!q.empty()) {
ret.emplace_back(q.top().first);
q.pop();
}
return ret;
}
};
感想
堆+哈希
394. 字符串解码(medium)
2023/9/8
题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
提示：
1 <= s.length <= 30s由小写英文字母、数字和方括号'[]'组成s保证是一个 有效 的输入。s中所有整数的取值范围为[1, 300]
我的答案
class Solution {
public:
string decodeString(string s) {
string result;
stack<string> stk;
int n = s.length();
for (int i = 0; i < n; ++i)
{
if (s[i] >= 'a' && s[i] <= 'z')
{
if (stk.empty() || stk.top() == "[")
{
string tmp;
tmp += s[i];
stk.push(tmp);
}
else
{
stk.top() += s[i];
}
}
else if (s[i] == ']')
{
string tmp = stk.top();
string str;
stk.pop();
stk.pop();
int times = stoi(stk.top());
stk.pop();
for (int j = 0; j < times; ++j)
{
str += tmp;
}
if (!stk.empty() && stk.top()[0] >= 'a' && stk.top()[0] <= 'z')
{
str = stk.top() + str;
stk.pop();
}
stk.push(str);
}
else if (s[i] == '[')
{
stk.push("[");
}
else
{
string tmp;
if (!stk.empty() && stk.top()[0] >= '0' && stk.top()[0] <= '9')
{
tmp = stk.top();
stk.pop();
}
tmp += s[i];
stk.push(tmp);
}
}
return stk.top();
}
};
参考答案
class Solution {
public:
string getDigits(string &s, size_t &ptr) {
string ret = "";
while (isdigit(s[ptr])) {
ret.push_back(s[ptr++]);
}
return ret;
}
string getString(vector <string> &v) {
string ret;
for (const auto &s: v) {
ret += s;
}
return ret;
}
string decodeString(string s) {
vector <string> stk;
size_t ptr = 0;
while (ptr < s.size()) {
char cur = s[ptr];
if (isdigit(cur)) {
// 获取一个数字并进栈
string digits = getDigits(s, ptr);
stk.push_back(digits);
} else if (isalpha(cur) || cur == '[') {
// 获取一个字母并进栈
stk.push_back(string(1, s[ptr++]));
} else {
++ptr;
vector <string> sub;
while (stk.back() != "[") {
sub.push_back(stk.back());
stk.pop_back();
}
reverse(sub.begin(), sub.end());
// 左括号出栈
stk.pop_back();
// 此时栈顶为当前 sub 对应的字符串应该出现的次数
int repTime = stoi(stk.back());
stk.pop_back();
string t, o = getString(sub);
// 构造字符串
while (repTime--) t += o;
// 将构造好的字符串入栈
stk.push_back(t);
}
}
return getString(stk);
}
};
感想
和题解差不多, 也是利用栈
399. 除法求值(medium)
2023/9/9
00 : 50 : 24
题目描述
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
注意：未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。
示例 1：
输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
注意：x 是未定义的 => -1.0
示例 2：
输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出：[3.75000,0.40000,5.00000,0.20000]
示例 3：
输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]
提示：
1 <= equations.length <= 20equations[i].length == 21 <= Ai.length, Bi.length <= 5values.length == equations.length0.0 < values[i] <= 20.01 <= queries.length <= 20queries[i].length == 21 <= Cj.length, Dj.length <= 5Ai, Bi, Cj, Dj由小写英文字母与数字组成
我的答案
class Solution {
public:
struct vertex
{
string name;
unordered_map<vertex*, double> sides;
vertex(string n) : name (n) {}
};
double dfs(string srcName, string destName, unordered_map<string, vertex*>& vertexes, unordered_set<string> passedby)
{
if (srcName == destName)
{
return 1;
}
if (vertexes[srcName]->sides.find(vertexes[destName]) != vertexes[srcName]->sides.end())
{
return vertexes[srcName]->sides[vertexes[destName]];
}
passedby.insert(srcName);
for (auto & side : vertexes[srcName]->sides)
{
if (passedby.find(side.first->name) != passedby.end())
{
continue;
}
double tmp = dfs(side.first->name, destName, vertexes, passedby);
if (tmp != -1)
{
return tmp * side.second;
}
}
return -1;
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
int n = equations.size();
unordered_map<string, vertex*> vertexes;
for (int i = 0; i < n; ++i)
{
string srcName = equations[i][0];
string destName = equations[i][1];
if (vertexes.find(srcName) == vertexes.end())
{
vertexes.insert({srcName, new vertex(srcName)});
}
if (vertexes.find(destName) == vertexes.end())
{
vertexes.insert({destName, new vertex(destName)});
}
vertexes[srcName]->sides.insert({vertexes[destName], values[i]});
vertexes[destName]->sides.insert({vertexes[srcName], 1/values[i]});
}
int size = queries.size();
vector<double> ret(size, -1.0);
for (int i = 0; i < size; ++i)
{
string srcName = queries[i][0];
string destName = queries[i][1];
if (vertexes.find(srcName) != vertexes.end() && vertexes.find(destName) != vertexes.end())
{
unordered_set<string> passedby;
ret[i] = dfs(srcName, destName, vertexes, passedby);
}
}
return ret;
}
};
参考答案
class Solution {
public:
int findf(vector<int>& f, vector<double>& w, int x) {
if (f[x] != x) {
int father = findf(f, w, f[x]);
w[x] = w[x] * w[f[x]];
f[x] = father;
}
return f[x];
}
void merge(vector<int>& f, vector<double>& w, int x, int y, double val) {
int fx = findf(f, w, x);
int fy = findf(f, w, y);
f[fx] = fy;
w[fx] = val * w[y] / w[x];
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
int nvars = 0;
unordered_map<string, int> variables;
int n = equations.size();
for (int i = 0; i < n; i++) {
if (variables.find(equations[i][0]) == variables.end()) {
variables[equations[i][0]] = nvars++;
}
if (variables.find(equations[i][1]) == variables.end()) {
variables[equations[i][1]] = nvars++;
}
}
vector<int> f(nvars);
vector<double> w(nvars, 1.0);
for (int i = 0; i < nvars; i++) {
f[i] = i;
}
for (int i = 0; i < n; i++) {
int va = variables[equations[i][0]], vb = variables[equations[i][1]];
merge(f, w, va, vb, values[i]);
}
vector<double> ret;
for (const auto& q: queries) {
double result = -1.0;
if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) {
int ia = variables[q[0]], ib = variables[q[1]];
int fa = findf(f, w, ia), fb = findf(f, w, ib);
if (fa == fb) {
result = w[ia] / w[ib];
}
}
ret.push_back(result);
}
return ret;
}
};
感想
这题有点难, 我的方法是邻接表+dfs, 效率是不如并查集的, 但是并查集有点不知道怎么写
406. 根据身高重建队列(medium)
2023/9/9
00 : 30 : 43
题目描述
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
示例 1：
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
示例 2：
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
提示：
1 <= people.length <= 20000 <= hi <= 1060 <= ki < people.length- 题目数据确保队列可以被重建
我的答案
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
auto func = [](vector<int> a, vector<int> b){
if (a[0] > b[0])
{
return true;
}
else if (a[0] == b[0])
{
return a[1] < b[1];
}
else
{
return false;
}
};
sort(people.begin(), people.end(), func);
int n = people.size();
vector<vector<int>> res;
res.push_back(people[0]);
for (int i = 1; i < n; ++i)
{
res.insert(res.begin() + people[i][1], people[i]);
}
return res;
}
};
参考答案
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](const vector<int>& u, const vector<int>& v) {
return u[0] > v[0] || (u[0] == v[0] && u[1] < v[1]);
});
vector<vector<int>> ans;
for (const vector<int>& person: people) {
ans.insert(ans.begin() + person[1], person);
}
return ans;
}
};
感想
一句话解释答案：高个子的人是看不到低个子人的
416. 分割等和子集(medium)
2023/9/9
00 : 24 : 20
题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
我的答案
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for (int i = 0; i < n; ++i)
{
sum += nums[i];
}
if (sum % 2)
{
return false;
}
else
{
sum /= 2;
}
sort(nums.begin(), nums.end());
vector<vector<bool>> dp(sum+1, vector<bool>(n+1, false));
dp[0][0] = true;
for (int i = 1; i <= sum; ++i)
{
for (int j = 0; j < n && i >= nums[j]; ++j)
{
if (dp[i-nums[j]][0] && dp[i-nums[j]][j+1] == false)
{
dp[i] = dp[i-nums[j]];
dp[i][j+1] = true;
break;
}
}
}
return dp[sum][0];
}
};
参考答案
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return false;
}
int sum = accumulate(nums.begin(), nums.end(), 0);
int maxNum = *max_element(nums.begin(), nums.end());
if (sum & 1) {
return false;
}
int target = sum / 2;
if (maxNum > target) {
return false;
}
vector<vector<int>> dp(n, vector<int>(target + 1, 0));
for (int i = 0; i < n; i++) {
dp[i][0] = true;
}
dp[0][nums[0]] = true;
for (int i = 1; i < n; i++) {
int num = nums[i];
for (int j = 1; j <= target; j++) {
if (j >= num) {
dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n - 1][target];
}
};
感想
我的dp也不错, 时间空间都还可以
437. 路径总和 III(medium)
2023/9/10
00 : 8 : 20
题目描述
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
提示:
- 二叉树的节点个数的范围是
[0,1000] -109 <= Node.val <= 109-1000 <= targetSum <= 1000
我的答案
class Solution {
public:
void dfs(TreeNode* root, int targetSum, int& res, bool included)
{
if (root == nullptr || abs(targetSum) > 0x3f3f3f3f)
{
return;
}
if (root->val == targetSum)
{
res++;
}
if (!included)
{
dfs(root->left, targetSum, res, false);
dfs(root->right, targetSum, res, false);
}
dfs(root->left, targetSum-root->val, res, true);
dfs(root->right, targetSum-root->val, res, true);
}
int pathSum(TreeNode* root, int targetSum) {
int res = 0;
dfs(root, targetSum, res, false);
return res;
}
};
参考答案
class Solution {
public:
unordered_map<long long, int> prefix;
int dfs(TreeNode *root, long long curr, int targetSum) {
if (!root) {
return 0;
}
int ret = 0;
curr += root->val;
if (prefix.count(curr - targetSum)) {
ret = prefix[curr - targetSum];
}
prefix[curr]++;
ret += dfs(root->left, curr, targetSum);
ret += dfs(root->right, curr, targetSum);
prefix[curr]--;
return ret;
}
int pathSum(TreeNode* root, int targetSum) {
prefix[0] = 1;
return dfs(root, 0, targetSum);
}
};
感想
前缀和很巧妙, 值得学习
438. 找到字符串中所有字母异位词(medium)
2023/9/10
00 : 35 : 12
题目描述
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104s和p仅包含小写字母
我的答案
class Solution {
public:
bool AllZero(unordered_map<char, int>& hash)
{
for (auto& it : hash)
{
if (it.second != 0)
return false;
}
return true;
}
vector<int> findAnagrams(string s, string p) {
int windowSize = p.length();
int n = s.length();
unordered_map<char, int> remain;
vector<int> res;
unordered_map<char, int> total;
for (int i = 0; i < windowSize; ++i)
{
if (remain.find(p[i]) != remain.end())
{
remain[p[i]]++;
total[p[i]]++;
}
else
{
remain.insert({p[i], 1});
total.insert({p[i], 1});
}
}
for (int i = 0; i < windowSize; ++i)
{
if (remain.find(s[i]) != remain.end())
{
remain[s[i]]--;
}
}
if (AllZero(remain))
{
res.push_back(0);
}
for (int i = 0; i < n - windowSize; ++i)
{
if (total.find(s[i]) != total.end())
{
remain[s[i]]++;
}
if (total.find(s[i+windowSize]) != total.end())
{
remain[s[i+windowSize]]--;
}
if (remain[s[i]] == 0 && remain[s[i+windowSize]] == 0 && AllZero(remain))
{
res.push_back(i+1);
}
}
return res;
}
};
参考答案
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int sLen = s.size(), pLen = p.size();
if (sLen < pLen) {
return vector<int>();
}
vector<int> ans;
vector<int> count(26);
for (int i = 0; i < pLen; ++i) {
++count[s[i] - 'a'];
--count[p[i] - 'a'];
}
int differ = 0;
for (int j = 0; j < 26; ++j) {
if (count[j] != 0) {
++differ;
}
}
if (differ == 0) {
ans.emplace_back(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
if (count[s[i] - 'a'] == 1) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s[i] - 'a'] == 0) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
++differ;
}
--count[s[i] - 'a'];
if (count[s[i + pLen] - 'a'] == -1) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
--differ;
} else if (count[s[i + pLen] - 'a'] == 0) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
++differ;
}
++count[s[i + pLen] - 'a'];
if (differ == 0) {
ans.emplace_back(i + 1);
}
}
return ans;
}
};
感想
滑动窗口经典题, 注意细节即可
448. 找到所有数组中消失的数字(easy)
2023/9/10
00 : 16 : 08
题目描述
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]
示例 2：
输入：nums = [1,1]
输出：[2]
提示：
n == nums.length1 <= n <= 1051 <= nums[i] <= n
进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
我的答案
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int n = nums.size();
vector<int> res;
for (int j = 0; j < 4; ++j)
{
for (int i = 0; i < n; ++i)
{
if (nums[i] != i+1)
{
swap(nums[i], nums[nums[i]-1]);
}
}
}
for (int i = 0; i < n; ++i)
{
if (nums[i] != i+1)
{
res.push_back(i+1);
}
}
return res;
}
};
参考答案
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int n = nums.size();
for (auto& num : nums) {
int x = (num - 1) % n;
nums[x] += n;
}
vector<int> ret;
for (int i = 0; i < n; i++) {
if (nums[i] <= n) {
ret.push_back(i + 1);
}
}
return ret;
}
};
感想
我的方法是一个取巧的方法, 我注意到当j为2时只能通过二十几个测试点, j为3时可以通过只剩最后两个, j为4就能ac, 无法解释其中的原理, 还是看题解的吧
461. 汉明距离(easy)
2023/9/10
00 : 00 : 30
题目描述
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例 1：
输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
示例 2：
输入：x = 3, y = 1
输出：1
提示：
0 <= x, y <= 231 - 1
我的答案
class Solution {
public:
int hammingDistance(int x, int y) {
int tmp = x ^ y;
int cnt = 0;
while (tmp)
{
if (tmp % 2)
{
cnt++;
}
tmp /= 2;
}
return cnt;
}
};
参考答案
class Solution {
public:
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
};
感想
标准库的这个函数竟然是O(1)复杂度
494. 目标和(medium)
2023/9/10
00 : 24 : 20
题目描述
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：
输入：nums = [1], target = 1
输出：1
提示：
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
我的答案
class Solution {
public:
void dfs(vector<int>& nums, int target, int index, int& res)
{
if (index == nums.size()-1)
{
if (nums[index] == target)
{
res++;
}
if (nums[index] == -target)
{
res++;
}
return;
}
dfs(nums, target-nums[index], index+1, res);
dfs(nums, target+nums[index], index+1, res);
}
int findTargetSumWays(vector<int>& nums, int target) {
int res = 0;
dfs(nums, target, 0, res);
return res;
}
};
参考答案
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (int& num : nums) {
sum += num;
}
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) {
return 0;
}
int n = nums.size(), neg = diff / 2;
vector<vector<int>> dp(n + 1, vector<int>(neg + 1));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
int num = nums[i - 1];
for (int j = 0; j <= neg; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= num) {
dp[i][j] += dp[i - 1][j - num];
}
}
}
return dp[n][neg];
}
};
感想
这题用dp很巧妙, 比回溯要好
538. 把二叉搜索树转换为累加树(medium)
2023/9/10
00 : 16 : 20
题目描述
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
输入：root = [0,null,1]
输出：[1,null,1]
示例 3：
输入：root = [1,0,2]
输出：[3,3,2]
示例 4：
输入：root = [3,2,4,1]
输出：[7,9,4,10]
提示：
- 树中的节点数介于
0和104之间。 - 每个节点的值介于
-104和104之间。 - 树中的所有值 互不相同 。
- 给定的树为二叉搜索树。
我的答案
class Solution {
public:
int sum = 0;
void dfs(TreeNode* root)
{
if (root->right != nullptr)
{
dfs(root->right);
}
root->val += sum;
sum = root->val;
if (root->left != nullptr)
{
dfs(root->left);
}
}
TreeNode* convertBST(TreeNode* root) {
if (root == nullptr)
{
return root;
}
dfs(root);
return root;
}
};
参考答案
class Solution {
public:
int sum = 0;
TreeNode* convertBST(TreeNode* root) {
if (root != nullptr) {
convertBST(root->right);
sum += root->val;
root->val = sum;
convertBST(root->left);
}
return root;
}
};
感想
反序中序遍历, 挺好的
543. 二叉树的直径(easy)
2023/9/10
00 : 12 : 28
题目描述
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2]
输出：1
提示：
- 树中节点数目在范围
[1, 104]内 -100 <= Node.val <= 100
我的答案
class Solution {
public:
int max = 0;
int dfs(TreeNode* root)
{
if (root == nullptr)
{
return 0;
}
int left = dfs(root->left);
int right = dfs(root->right);
max = left + right + 1 > max ? left + right + 1 : max;
return left > right ? left+1 : right+1;
}
int diameterOfBinaryTree(TreeNode* root) {
int tmp = dfs(root);
return max > tmp ? max-1 : tmp-1;
}
};
参考答案
class Solution {
int ans;
int depth(TreeNode* rt){
if (rt == NULL) {
return 0; // 访问到空节点了，返回0
}
int L = depth(rt->left); // 左儿子为根的子树的深度
int R = depth(rt->right); // 右儿子为根的子树的深度
ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
return max(L, R) + 1; // 返回该节点为根的子树的深度
}
public:
int diameterOfBinaryTree(TreeNode* root) {
ans = 1;
depth(root);
return ans - 1;
}
};
感想
简单的dfs
560. 和为 K 的子数组(medium)
2023/9/10
00 : 30 : 19
题目描述
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
提示：
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
我的答案
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> prifixSum;
int n = nums.size();
int sum = 0;
int res = 0;
prifixSum[0] = 1;
for (int i = 0; i < n; ++i)
{
sum += nums[i];
if (prifixSum.find(sum-k) != prifixSum.end())
{
res += prifixSum[sum-k];
}
prifixSum[sum]++;
}
return res;
}
};
参考答案
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1;
int count = 0, pre = 0;
for (auto& x:nums) {
pre += x;
if (mp.find(pre - k) != mp.end()) {
count += mp[pre - k];
}
mp[pre]++;
}
return count;
}
};
感想
对于这道题前缀和就是神
581. 最短无序连续子数组(medium)
2023/9/10
题目描述
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
示例 1：
输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
示例 2：
输入：nums = [1,2,3,4]
输出：0
示例 3：
输入：nums = [1]
输出：0
提示：
1 <= nums.length <= 104-105 <= nums[i] <= 105
进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？
我的答案
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int n = nums.size();
vector<int> tmp = nums;
sort(tmp.begin(), tmp.end());
int left = 0, right = n-1;
while (left < n && tmp[left] == nums[left])
{
left++;
}
if (left == n)
{
return 0;
}
while (right >= 0 && tmp[right] == nums[right])
{
right--;
}
return right - left + 1;
}
};
参考答案
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int n = nums.size();
int maxn = INT_MIN, right = -1;
int minn = INT_MAX, left = -1;
for (int i = 0; i < n; i++) {
if (maxn > nums[i]) {
right = i;
} else {
maxn = nums[i];
}
if (minn < nums[n - i - 1]) {
left = n - i - 1;
} else {
minn = nums[n - i - 1];
}
}
return right == -1 ? 0 : right - left + 1;
}
};
感想
没想出来这个一次遍历的方法, 还是老老实实建数组了 一句话描述题解:
右边界: 从前往后找最后一个不比左边所有元素都大的元素
左边界: 从后往前找最后一个不比右边所有元素都小的元素
617. 合并二叉树(easy)
2023/9/10
00 : 01 : 00
题目描述
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]
示例 2：
输入：root1 = [1], root2 = [1,2]
输出：[2,2]
提示：
- 两棵树中的节点数目在范围
[0, 2000]内 -104 <= Node.val <= 104
我的答案
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root2 == nullptr)
{
return root1;
}
if (root1 == nullptr)
{
return root2;
}
TreeNode* tmp = new TreeNode(root1->val + root2->val);
tmp->left = mergeTrees(root1->left, root2->left);
tmp->right = mergeTrees(root1->right, root2->right);
return tmp;
}
};
参考答案
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == nullptr) {
return t2;
}
if (t2 == nullptr) {
return t1;
}
auto merged = new TreeNode(t1->val + t2->val);
merged->left = mergeTrees(t1->left, t2->left);
merged->right = mergeTrees(t1->right, t2->right);
return merged;
}
};
感想
竟然和题解一模一样, 一分钟速通
621. 任务调度器(medium)
2023/9/12
题目描述
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
示例 1：
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
示例 2：
输入：tasks = ["A","A","A","B","B","B"], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
诸如此类
示例 3：
输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案是：
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A
提示：
1 <= task.length <= 104tasks[i]是大写英文字母n的取值范围为[0, 100]
我的答案
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
int size = tasks.size();
unordered_map<char, int> freq;
for (auto & task : tasks)
{
freq[task]++;
}
int time = 0;
multimap<int, int, greater<int>> todo; // freq, nextTime
for (auto & it : freq)
{
todo.insert({it.second, 0});
}
int remain = todo.size();
while (remain > 0)
{
auto i = todo.begin();
for (; i != todo.end(); ++i)
{
if (i->second <= time)
{
break;
}
}
if (i == todo.end())
{
time++;
continue;
}
i->second = time + n + 1;
if (i->first == 1)
{
todo.erase(i);
remain--;
}
else
{
int tmp1 = i->first;
int tmp2 = i->second;
todo.erase(i);
todo.insert({tmp1-1, tmp2});
}
time++;
}
return time;
}
};
参考答案
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
unordered_map<char, int> freq;
for (char ch: tasks) {
++freq[ch];
}
// 任务总数
int m = freq.size();
vector<int> nextValid, rest;
for (auto [_, v]: freq) {
nextValid.push_back(1);
rest.push_back(v);
}
int time = 0;
for (int i = 0; i < tasks.size(); ++i) {
++time;
int minNextValid = INT_MAX;
for (int j = 0; j < m; ++j) {
if (rest[j]) {
minNextValid = min(minNextValid, nextValid[j]);
}
}
time = max(time, minNextValid);
int best = -1;
for (int j = 0; j < m; ++j) {
if (rest[j] && nextValid[j] <= time) {
if (best == -1 || rest[j] > rest[best]) {
best = j;
}
}
}
nextValid[best] = time + n + 1;
--rest[best];
}
return time;
}
};
感想
没做出来, 看了题解
647. 回文子串(medium)
2023/9/12
00 : 04 : 15
题目描述
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000s由小写英文字母组成
我的答案
class Solution {
public:
int countSubstrings(string s) {
int n = s.length();
vector<vector<bool>> dp;
for (int i = 0; i < n; ++i)
{
dp.push_back(vector<bool>(n-i, false));
}
// dp[i][j] = (j < 2 || dp[i+1][j-2]) && s[i] == s[i+j]
int res = 0;
for (int i = n-1; i >= 0; --i)
{
for (int j = 0; j < n-i; ++j)
{
dp[i][j] = (j < 2 || dp[i+1][j-2]) && s[i] == s[i+j];
res += dp[i][j] ? 1 : 0;
}
}
return res;
}
};
参考答案
class Solution {
public:
int countSubstrings(string s) {
int n = s.size(), ans = 0;
for (int i = 0; i < 2 * n - 1; ++i) {
int l = i / 2, r = i / 2 + i % 2;
while (l >= 0 && r < n && s[l] == s[r]) {
--l;
++r;
++ans;
}
}
return ans;
}
};
感想
和中心扩展本质一样的, 但是dp会多浪费许多空间
739. 每日温度(medium)
2023/9/12
00 : 02 : 38
题目描述
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
提示：
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
我的答案
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
stack<int> stk;
vector<int> ans(n, 0);
for (int i = 0; i < n; ++i)
{
if (stk.empty() || temperatures[stk.top()] >= temperatures[i])
{
stk.push(i);
}
else
{
while (!stk.empty() && temperatures[stk.top()] < temperatures[i])
{
int top = stk.top();
ans[top] = i - top;
stk.pop();
}
stk.push(i);
}
}
return ans;
}
};
参考答案
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n);
stack<int> s;
for (int i = 0; i < n; ++i) {
while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
int previousIndex = s.top();
ans[previousIndex] = i - previousIndex;
s.pop();
}
s.push(i);
}
return ans;
}
};
感想
经典单调栈