avatar

Leetcode-202010

LCP 19. 秋叶收藏集 - 20201001

小扣出去秋游,途中收集了一些红叶和黄叶,他利用这些叶子初步整理了一份秋叶收藏集 leaves, 字符串 leaves 仅包含小写字符 r 和 y, 其中字符 r 表示一片红叶,字符 y 表示一片黄叶。
出于美观整齐的考虑,小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等,但均需大于等于 1。每次调整操作,小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕

正值双节,力扣来了个开幕雷击,这种题还是有难度,从题解来分析吧。

动态规划

题解中有提到一个词 - 示性函数,其实就是一个结果为二元的函数,或者说布尔函数,这个问题不大,主要是对状态的分析,题解使用了f[i][j]来存储状态,最后取f[n-1][2]来作为return。

其中j可以为0、1、2,分别表示头部的红、中间的黄、和尾部的红,然后对每个j进行分析

  • j == 0,这个是最简单的,只需要把第i片叶子变成红色,题解的说明可能不太明了,其实这时候的意思是,f[i][j]是如果第i片叶子应该是头部红的话至此应该操作的次数。然后f[i][0] = f[i-1][0] + isYellow(i),因为第i片叶子需要是头部红,所以前面的叶子也应该是头部红,加上的就是f[i-1][0]
  • j == 1,第i - 1片叶子既可以是头部红又可以是中间黄,取其中最小的就可以,直接写f[i][1] = f[i-1][0] + isRed(i)
  • j == 2,稍微复杂一些,第i - 1片叶子既可以是中间黄又可以是尾部红,但是不能是头部黄(即不能跳过中间黄的状态,题目要求3种状态各个至少为1),f[i][2] = min(f[i-1][1], f[i-1][2]) + isYellow(i)
class Solution {
public:
int minimumOperations(string leaves) {
int n = leaves.size();
vector<vector<int>> f(n, vector<int>(3));
f[0][0] = (leaves[0] == 'y');
f[0][1] = f[0][2] = f[1][2] = INT_MAX; // 使用一个上限
int isRed, isYellow;
for (int i = 1; i < n; i++) {
isRed = (leaves[i] == 'r');
isYellow = (leaves[i] == 'y');
f[i][0] = f[i-1][0] + isYellow;
f[i][1] = min(f[i-1][0], f[i-1][1]) + isRed;
if (i >= 2) f[i][2] = min(f[i-1][1], f[i-1][2]) + isYellow; // 保证i是在第3片叶子开始才判断有无尾部红
}

return f[n-1][2];
}
};

image-20201001225313743

但是空间复杂度为O(n),可以简化状态存储,仔细查看上面的代码,所谓f[i-1]不过是上一次的f,并无必要开一个双重数组,使用一个vector<int>f(3)即可,使用以下代码。

class Solution {
public:
int minimumOperations(string leaves) {
int n = leaves.size();
vector<int> f(3);
f[0] = (leaves[0] == 'y');
f[1] = f[2] = INT_MAX;
int isRed, isYellow;
for (int i = 1; i < n; i++) {
isRed = (leaves[i] == 'r');
isYellow = (leaves[i] == 'y');
if(i >= 2) f[2] = min(f[1], f[2]) + isYellow;
f[1] = min(f[0], f[1]) + isRed;
f[0] += isYellow;
}
return f[2];
}
};

image-20201001225849353

771. 宝石与石头 - 20201002

给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复,J 和 S中的所有字符都是字母。字母区分大小写,因此”a”和”A”是不同类型的石头。

示例 1:

输入: J = “aA”, S = “aAAbbbb”
输出: 3

示例 2:

输入: J = “z”, S = “ZZ”
输出: 0

注意:

S 和 J 最多含有50个字母。
J 中的字符不重复。

水题,但是可以学习一下bitset,C++中的bitset类似封装过的bitmap,内存小,可以作为bool数组使用,(原来8位的bool现在只需要1位)。bitset不仅可以像一个int一样进行位运算,还有一些实例函数可以使用。

初始化方法: bitset<size> name(to_int_size)

size是指bitset长度,to_int_size是作为int的大小,

c.size()      // 返回大小(位数)
c.count() // 返回1的个数
c.any() // 返回是否有1
c.none() // 返回是否没有1
c.set() // 全都变成1
c.set(p) // 将第p + 1位变成1
c.set(p, x) // 将第p + 1位变成x
c.reset() // 全都变成0
c.reset(p) // 将第p + 1位变成0
c.flip() // 全都取反
c.flip(p) // 将第p + 1位取反
c.to_ulong() // 返回它转换为unsigned long的结果,如果超出范围则报错
c.to_ullong() // 返回它转换为unsigned long long的结果,如果超出范围则报错
c.to_string() // 返回它转换为string的结果
// 来源: https://blog.csdn.net/Q1410136042/article/details/82119599
class Solution {
public:
int numJewelsInStones(string J, string S) {
bitset<128> arr(0);
for (char i : J)
arr[(int)i] = 1;
int ret = 0;
for (char i : S)
if (arr[(int) i]) ret++;
return ret;
}
};

1. 两数之和 - 20201003

过于简单 不叙 (还忘记打卡了)

2. 两数相加 - 20201004

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

​ 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)

​ 输出:7 -> 0 -> 8

​ 原因:342 + 465 = 807

很直接的方法

class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
bitset<2> pend(0); // 0位是进位 1位是最后一位是否进位
int tmp = 0;

if (!l1) return l2;
if (!l2) return l1;

ListNode* n1 = l1;
ListNode* n2 = l2;
while (n1 && n2) {
n1 = n1->next;
n2 = n2->next;
}
if (n2) {
swap(l1, l2);
} // if n2 is longer
n1 = l1; n2 = l2;
while (n1 && n2) {
tmp = (pend[0]) ? 1 : 0;
tmp += (n1->val + n2->val);
if (tmp >= 10) {
tmp %= 10;
pend[0] = 1;
} else {
pend[0] = 0;
}
n1->val = tmp;
n1 = n1->next; n2 = n2->next;
}
if (n1) {
if (pend[0]) {
while (n1->val == 9) {
n1->val = 0;
if (n1->next) n1 = n1->next;
else pend[1] = 1;
}
if (n1 && !pend[1]) {
n1->val += 1;
}
if (pend[1]) {
n1->next = new ListNode(1);
}
}
}
else if (pend[0]) {
n1 = l1;
while (n1->next) n1 = n1->next;
n1->next = new ListNode(1);
}
return l1;
}
};

image-20201005002913474

18. 四数之和 - 20201005

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

注意:

答案中不可以包含重复的四元组。

示例:

给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。

满足要求的四元组集合为:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

本来用9月的dfs来做,但是去重上有一些问题,看看题解的双指针是怎么做的。

class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ret;
if (nums.size() < 4) return ret;

int size = nums.size();
sort(nums.begin(), nums.end()); // 进行排序

for (int i = 0; i < size - 3; i++) { //这里i到size-3以上,凑不满4个,进行减枝
if (target <= 0 && nums[i] > 0) break; // 因为进行了排序,所以小的在前面,到正数后必不会有负数使sum变小,故不需要考虑 target >= 0 && nums[i] < 0的情况
if (nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break; // 同样因为排序的问题 大于就没必要继续了,但是小于是可以的(可能后面先不选一个 等一个更大的),所以不用 !=
if (nums[i] + nums[size-1] + nums[size-2] + nums[size-3] < target) continue; // 这轮是没有希望了,但是之后i取更大时,还有机会,所以 continue
if (i > 0 && nums[i] == nums[i-1]) continue; // 对于重复项,因为(只需要第一个计算了就可以)例如(0 0 。。。)只需要第一个 0 的结果即可
// 对i减枝结束
for (int j = i + 1; j < size-2; j++) { // 这里只要到 size - 2 就行,因为i算进去了
// 以下三行减枝和对i的减枝思路类似
if (nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;
if (nums[i] + nums[j] + nums[size-1] + nums[size-2] < target) continue;
if (j > i + 1 && nums[j] == nums[j-1]) continue;

int start = j+1, end = size-1;
while (start < end) {
int sum = nums[i] + nums[j] + nums[start] + nums[end];
if (sum < target) start++;
else if (sum>target) end--;
else { // sum == target
ret.push_back({nums[i], nums[j], nums[start], nums[end]});
int last_start=start, last_end=end;
truetruetruetruetruetrue// 剔除重复项
truetruetruetruetruetruewhile(start<end && nums[start] == nums[last_start]) start++;
truetruetruetruetruetruewhile(start<end && nums[end] == nums[last_end]) end--;
}
}
}
}

return ret;
}
};

834. 树中距离之和 - 20201006

给定一个无向、连通的树。树中有 N 个标记为 0…N-1 的节点以及 N-1 条边 。

第 i 条边连接节点 edges[i][0]edges[i][1]

返回一个表示节点 i 与其他所有节点距离之和的列表 ans。

示例 1:

输入: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出: [8,12,6,10,10,10]
解释:
如下为给定的树的示意图:

0

/ \

1 2

​ /|\

3 4 5

我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
也就是 1 + 1 + 2 + 2 + 2 = 8。 因此,answer[0] = 8,以此类推。
说明: 1 <= N <= 10000

今天这个题目很有意思,但同时也有一定难度,这个说是一个无向联通树,但也是可以用到图的方法来做

思路来自https://leetcode-cn.com/problems/sum-of-distances-in-tree/solution/shou-hua-tu-jie-shu-zhong-ju-chi-zhi-he-shu-xing-d/

首先解决一棵树的子树节点,到根节点的距离,是一个后序遍历的递归求和,由distSum和nodeNum两个数组完成,至于根节点的父节点以外的,可以利用父节点的后序遍历通过减法和加法就可以完成。

class Solution {
public:
int N;
truevector<vector<int>> graph;
truevector<int> nodeNum;
truevector<int> distSum;
true
true// 后序遍历解决子树结点
truevoid postOrder(int root, int parent) {
truetruevector<int> neighbors = graph[root]; // 所有相连结点
truetruefor (auto neighbor : neighbors) {
truetruetrueif (neighbor == parent) continue; // 如果相连的是parent,即走了重复的路,那就可以下一个了
truetruetruepostOrder(neighbor, root);
truetruetruenodeNum[root] += nodeNum[neighbor]; // nodeNum(子树个数)全部加起来, 之后还要加dist
truetruetruedistSum[root] += nodeNum[neighbor] + distSum[neighbor];
truetrue}
true}
true// 先序遍历解决子树外的问题
truevoid preOrder(int root, int parent) {
truetruevector<int> neighbors = graph[root]; // 所有相连结点
truetruefor (auto neighbor : neighbors) {
truetruetrueif (neighbor == parent) continue; // 如果相连的是parent,即走了重复的路,那就可以下一个了
// distSum[neighbor] = distSum[root] - nodeNum[neighbor] + (N - nodeNum[neighbor]);
truetruetruedistSum[neighbor] = distSum[root] - 2 * nodeNum[neighbor] + N;
truetruetruepreOrder(neighbor, root);
truetrue}
true}
true
truevector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {
this->N = N;
truetrue// 建立邻接矩阵
truetruethis->graph.resize(N, vector<int>());
truetruefor (auto edge : edges) {
truetruetruegraph[edge[0]].push_back(edge[1]);
truetruetruegraph[edge[1]].push_back(edge[0]);
truetrue}
truetrue// node表和dist表初始化
truetruethis->nodeNum.resize(N, 1);
truetruethis->distSum.resize(N, 0);
truetrue
truetrue// 先把子树遍历了 parent写一个不存在的-1
truetruepostOrder(0, -1);
truetruepreOrder(0, -1);
truetruereturn this->distSum;
true}
};

75. 颜色分类 - 20201007

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶:

一个直观的解决方案是使用计数排序的两趟扫描算法。

首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。

你能想出一个仅使用常数空间的一趟扫描算法吗?

这个还算比较简单的,要么是空间换时间要么反过来就是按照进阶里的思路

class Solution {
public:
void sortColors(vector<int>& nums) {
int len = nums.size();
int head = 0, tail = len-1;
vector<int> arr(len, 0);
for (int i = 0; i < len; i++) {
if (nums[i] == 0) arr[head++] = 0;
else if (nums[i] == 2) arr[tail--] = 2;
}
while (head<=tail) arr[head++] = 1;
nums = arr;
}
};

当然,利用循环不变量来设定两个边界,利用swap可以在一个数组中完成操作。

class Solution {
public:
void sortColors(vector<int>& nums) {
int len = nums.size();
int head = 0, tail = len;
// for (int i = 0; i < tail; i++) {
// if (nums[i] == 0) {
// swap(nums[i], nums[head]);
// head++;
// } else if (nums[i] == 2) {
// tail--;
// swap(nums[i], nums[tail]);
// i--; // 这一点很关键,因为要保持i不变(所以这里可以用while循环)
// }
// }

/* while 缝合版 */
int i = 0;
while (i < tail) {
if (nums[i]==0)
swap(nums[i++], nums[head++]);
else if (nums[i] == 2)
swap(nums[i], nums[--tail]);
else i++; // nums[i] == 1
}
}
};

image-20201007114215296

344. 反转字符串 - 20201008

极为基础的一道题,但是发现了一个神奇的交换方法

s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];

很妙!

141. 环形链表 - 20201009

给定一个链表,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

如果链表中存在环,则返回 true 。 否则,返回 false 。

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?

INT_MAX

但是这一种方法改变了链表的值,虽然能过,但是实际应用不大行

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head) return false;
ListNode* node = head;
while (node->next != NULL && node->val != INT_MAX) {
node->val = INT_MAX;
node = node->next;
}
return (node->val == INT_MAX);
}
};

快慢指针

只要我比你跑得快,那么如果存在环,那我一定能追上你

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 - 20201010

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。

昨天的题加大了难度。借给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

首先借一个图

fig1

我们先设置fast、slow和done指针从head出发(这里done指针先不动,作用在之后提到),那么fast的路程为a + b + n * (b + c) ,slow的路程为a + b,最后得到a = c + (n - 1) * (b + c)

那么我们有三个点需要进行证明

  • n >= 1
  • C(slow) == a + b
  • a = c + (n - 1) * (b + c)

第一点容易证明,既然fast追上了slow,那么一定是多跑了至少一圈的距离

第二点,假设fast需要走最大的距离追上slow,那么就是slow刚入环的时候,fast在slow的下一个结点上,那么2k - k = b + c - 1 => k =( b + c - 1) / 2,即slow走的距离连环的一半都不到,肯定是C(slow) = a + b而不是 a + (b + c) + b的

第三点,由设定条件和C(fast) = 2C(slow) => a + b + n * (b + c) = 2(a + b)可以得到证明

由于证明了第三点,在fast和slow相遇后,开头的done和slow开始移动,当done指针和slow指针相遇时,指向的便是入口结点。

如何证明呢,此时C(slow) = a + b + c + (n - 1) * (b + c) = a + n * (b + c),即刚好走到环起始点。

class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head) return nullptr;

ListNode *fast, *slow, *done;
fast = slow = done = head;

while (fast != nullptr) {
if (fast->next == nullptr) return nullptr;
fast = fast->next->next;
slow = slow->next;
if (fast == slow) break;
}

if (fast == nullptr) return nullptr;
while (done != slow) {
done = done->next;
slow = slow->next;
}

return done;
}
};

image-20201010152101972

416. 分割等和子集 - 20201011

都是动态规划,但是思路不一样。

第二种相对容易理解,但是第一种的背包等学了《背包九讲》再回过头看看吧。

class Solution {
public:
bool canPartition(vector<int>& nums) {
int len = nums.size();
if (len == 0) return false;

int sum = 0;
for (auto i : nums) sum += i;
if (sum & 1) return false;

int target = sum / 2;
vector<vector<int>> dp(len, vector<int>(target+1, 0));
if (nums[0] <= target)
dp[0][nums[0]] = true;

for (int i = 1; i < len; i++) {
for (int j = 0; j <= target; j++) {
dp[i][j] = dp[i-1][j]; // 先抄下来结果
if(nums[i] == j) {
dp[i][j] = true;
continue;
}
if (nums[i] < j)
dp[i][j] = (dp[i-1][j] | dp[i-1][j-nums[i]]);
}
}

return dp[len-1][target];
}
};
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum & 1) return false;
unordered_set<int> dp({ sum / 2}), tmp{};

for (int i : nums) {
for (int j : dp) {
if (i - j == 0 || j == 0) return true;
if (j - i < 0 || dp.find(j-i)!=dp.end()) continue;
tmp.insert(j-i);
}
dp.insert(tmp.begin(), tmp.end());
tmp.clear();
}

return false;
}
};

530. 二叉搜索树的最小绝对差 - 20201012

给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。

搜索树的中序遍历。

class Solution {
public:
vector<int> arr;
void inOrder(TreeNode* root) {
if (!root) return;
inOrder(root->left);
arr.push_back(root->val);
inOrder(root->right);
}
int getMinimumDifference(TreeNode* root) {
inOrder(root);
int ret = INT_MAX;
for (auto i = (arr.begin() + 1); i != arr.end(); i++) {
ret = min(abs(*i - *(i-1)), ret);
}
return ret;
}
};

![image-20201012121909055](/Users/zrzz/Library/Application Support/typora-user-images/image-20201012121909055.png)

24. 两两交换链表中的节点 - 20201013

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

简单题

class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* hhead = new ListNode(0);
hhead->next = head;
ListNode* node = hhead, *node1, *node2;
while(node->next && node->next->next) {
node1 = node->next;
node2 = node->next->next;
node->next = node2;
node1->next = node2->next;
node2->next = node1;
node = node1;
}
return hhead->next;
}
};

1002. 查找常用字符 - 20201014

给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现 3 次,但不是 4 次,则需要在最终答案中包含该字符 3 次。

你可以按任意顺序返回答案。

简单题

class Solution {
public:
vector<string> commonChars(vector<string>& A) {
vector<int> tmp;
vector<int> ret(26, INT_MAX);
vector<int> cnt(26, 0);
vector<string> sret;
for (string i:A) {
tmp = vector<int>(26, 0);
for (char x: i){
tmp[x-'a']++;
}
for (int i = 0; i < 26; i++)
if (tmp[i] != 0) {
cnt[i]++;
if (ret[i] > tmp[i])
ret[i] = tmp[i];
}
}
int lenA = A.size();
for (int i = 0; i < 26; i++) {
if (ret[i] != INT_MAX && cnt[i] == lenA) {
for (int j = 0; j < ret[i]; j ++){
string a = "a";
a[0] = i+'a';
sret.push_back(a);
}
}
}
return sret;
}
};

image-20201015102124491

116. 填充每个节点的下一个右侧节点指针 - 20201015

给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

提示:

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。
class Solution {
public:
Node* connect(Node* root) {
if (!root) return root;

Node* lMost = root;
while (lMost->left) {
Node* head = lMost;

while (head) {
head->left->next = head->right;
if (head->next) head->right->next = head->next->left;
head = head->next;
}

lMost = lMost->left;
}
return root;
}
};

![image-20201015113212598](/Users/zrzz/Library/Application Support/typora-user-images/image-20201015113212598.png)

977. 有序数组的平方 - 20201016

给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序

class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
vector<int> ans;
for (int num: A) {
ans.push_back(num * num);
}
sort(ans.begin(), ans.end());
return ans;
}
};

52. N皇后 II - 20201017

给定一个整数 n,返回 n 皇后不同的解决方案的数量。

用三个int来作为bitset减少复杂度

class Solution {
public:
int totalNQueens(int n) {
return solve(n, 0, 0, 0, 0);
}

int solve(int n, int row, int columns, int diagonals1, int diagonals2) {
if (row == n) {
return 1;
} else {
int count = 0;
int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
while (availablePositions != 0) {
int position = availablePositions & (-availablePositions);
availablePositions = availablePositions & (availablePositions - 1);
count += solve(n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
}
return count;
}
}
};

844. 比较含退格的字符串 - 20201019

给定 S 和 T 两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。 # 代表退格字符。

注意:如果对空文本输入退格字符,文本继续为空。

这道题还比较简单,想到逆序的话就可以将空间复杂度控制在O(1)了

class Solution {
public:
bool backspaceCompare(string S, string T) {
int sSkipNum = 0; // 记录S的#数量
int tSkipNum = 0; // 记录T的#数量
int i = S.size() - 1;
int j = T.size() - 1;
while (1) {
while (i >= 0) { // 从后向前,消除S的#
if (S[i] == '#') sSkipNum++;
else {
if (sSkipNum > 0) sSkipNum--;
else break;
}
i--;
}
while (j >= 0) { // 从后向前,消除T的#
if (T[j] == '#') tSkipNum++;
else {
if (tSkipNum > 0) tSkipNum--;
else break;
}
j--;
}
// 后半部分#消除完了,接下来比较S[i] != T[j]
if (i < 0 || j < 0) break; // S 或者T 遍历到头了
if (S[i] != T[j]) return false;
i--;j--;
}
// 说明S和T同时遍历完毕
if (i == -1 && j == -1) return true;
return false;
}
};

143. 重排链表 - 20201020

给定一个单链表 L:L0→L1→…→Ln-1→Ln ,
将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

思路很简单

  • 先把链表分为两半,然后把后一半翻转
  • 再将两个链表Merge
class Solution {
public:
ListNode* findMid(ListNode* head) {
// fs pointer to find a mid node
ListNode* slow,* fast;
slow = fast = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}

ListNode* reversedList(ListNode* node) {
ListNode* pre = nullptr;
ListNode* cur = node;
ListNode* tmp;
while (cur) {
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}

void mergeList(ListNode* l1, ListNode* l2) {
ListNode *l1tmp, *l2tmp;
while(l1 && l2) {
l1tmp = l1->next;
l2tmp = l2->next;

l1->next = l2;
l2->next = l1tmp;

l1 = l1tmp;
l2 = l2tmp;
}
}

void reorderList(ListNode* head) {
if (!head) return;
// get the mid node
ListNode* mid = findMid(head);
// cut into two parts
ListNode* l1 = head, *l2 = mid->next;
mid->next = nullptr;
// reverse list
l2 = reversedList(l2);
// merge it!
mergeList(l1, l2);
}
};

image-20201020195343078

925. 长按键入 - 20201021

你的朋友正在使用键盘输入他的名字 name。偶尔,在键入字符 c 时,按键可能会被长按,而字符可能被输入 1 次或多次。

你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字(其中一些字符可能被长按),那么就返回 True。

超简单

class Solution {
public:
bool isLongPressedName(string name, string typed) {
if (name == typed) return true;
auto nameEnd = name.end(), typedEnd = typed.end();
if (*(nameEnd-1) != *(typedEnd-1)) return false;
auto a = name.begin(), b = typed.begin();
while (a != nameEnd && b != typedEnd) {
if (*a == *b) {
a++; b++;
}
else if (*b == *(a-1)) b++;
else return false;
}
return true;
}
};

image-20201021192937508

19. 删除链表的倒数第N个节点 - 20201022

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

快慢指针

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (!head->next) {
delete(head);
return nullptr;
}
ListNode *f, *s, *pre;
pre = f = s = head;
for (int i = 0; i < n-1; i++) f = f->next;

while (f->next) {
f = f->next;
pre = s;
s = s->next;
}

pre->next = s->next ? s->next : nullptr;
// if ()
if (s == head) head = head->next;
delete(s);
return head;
}
}

image-20201028174944894

234. 回文链表 - 20201023

请判断一个链表是否为回文链表。

class Solution {
public:
ListNode* findMid(ListNode* head) {
// fs pointer to find a mid node
ListNode* slow,* fast;
slow = fast = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}

ListNode* reversedList(ListNode* node) {
ListNode* pre = nullptr;
ListNode* cur = node;
ListNode* tmp;
while (cur) {
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}

bool isPalindrome(ListNode* head) {
if (!head) return true;
ListNode* mid = findMid(head);
ListNode *l1 = head, *l2 = mid->next;
l2 = reversedList(l2);
bool ret = true;
while (ret && l2) {
if (l1->val != l2->val)
return false;
l1=l1->next;l2=l2->next;
}

return true;
}
};

当然,也可以在return前把列表再翻转回来,这里就没做了。

image-20201023231232270

1024. 视频拼接 - 20201024

你将会获得一系列视频片段,这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠,也可能长度不一。

视频片段 clips[i] 都用区间进行表示:开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑,例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。

我们需要将这些片段进行再剪辑,并将剪辑后的内容拼接成覆盖整个运动过程的片段([0, T])。返回所需片段的最小数目,如果无法完成该任务,则返回 -1 。

Dp算法。。。

class ssSort {
public:
bool operator() (vector<int> a, vector<int> b) {
return (a[0] < b[0]);
}
};
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {

for (int i = 0; i < clips.size(); i++)
if (clips[i][0] == 0 && clips[i][1] >= T) return 1;

sort(clips.begin(), clips.end(), ssSort());
vector<int> dp(101, 101);
dp[0] = 0;

for (int i = 0; i < clips.size(); i++) {
int start = clips[i][0], end = clips[i][1];
for (int j = start + 1; j <= end; j++)
dp[j] = min(dp[j], dp[start] + 1);
}
return dp[T] == 101 ? -1 : dp[T];
}
};

845. 数组中的最长山脉 - 20201025

我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”:

B.length >= 3
存在 0 < i < B.length - 1 使得 B[0] < B[1] < … B[i-1] < B[i] > B[i+1] > … > B[B.length - 1]
(注意:B 可以是 A 的任意子数组,包括整个数组 A。)

给出一个整数数组 A,返回最长 “山脉” 的长度。

如果不含有 “山脉” 则返回 0。

是DP的思路,从左边和右边走一遍,找到“坡”最大的下标,返回两边的和减一,就是结果。

class Solution {
public:
int longestMountain(vector<int>& A) {
int aLen = A.size();
if (aLen < 3) return 0;

vector<int> arr1(aLen, 1), arr2(aLen, 1);
for (int i = 1; i < aLen; i++)
arr1[i] = (A[i] > A[i-1] ? arr1[i-1] + 1 : 1);

for (int i = aLen - 2; i >= 0; i--)
arr2[i] = (A[i] > A[i+1] ? arr2[i+1] + 1 : 1);

int ret = 0;
for (int i = 1; i < aLen - 1; i++)
if (arr1[i] > 1 && arr2[i] > 1)
ret = max(ret, arr1[i] + arr2[i] - 1);
return ret;
}
};

![image-20201027005857033](/Users/zrzz/Library/Application Support/typora-user-images/image-20201027005857033.png)

1365. 有多少小于当前数字的数字 - 20201026

给你一个数组 nums,对于其中每个元素 nums[i],请你统计数组中比它小的所有数字的数目。

换而言之,对于每个 nums[i] 你必须计算出有效的 j 的数量,其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

直接暴力即可

class Solution {
public:
vector<int> ret;

vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
ret = vector<int>(nums.size(), 0);
for (int i = 0; i < nums.size(); i++)
for (int j = 0; j < nums.size(); j++) {
if (nums[j] < nums[i]) ret[i]++;
}
return ret;
}
};

![image-20201026232555844](/Users/zrzz/Library/Application Support/typora-user-images/image-20201026232555844.png)

144. 二叉树的前序遍历 - 20201027

简单题,不过可以复习一下栈知识。

class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ret;
if (!root) return ret;
stack<TreeNode*> s;
TreeNode* node = root;
s.push(node);
while(!s.empty()) {
node = s.top();
s.pop();
// 访问node
ret.push_back(node->val);
if (node->right) s.push(node->right);
if (node->left) s.push(node->left);
}
return ret;
}
};

![image-20201027011157023](/Users/zrzz/Library/Application Support/typora-user-images/image-20201027011157023.png)

1207. 独一无二的出现次数 - 20201028

给你一个整数数组 arr,请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的,就返回 true;否则返回 false

简单题

class Solution {
public:
bool uniqueOccurrences(vector<int>& arr) {
map<int, int> m;
for (int i : arr) {
auto it = m.find(i);
if (it != m.end()) (it->second)++;
else m.insert(pair<int, int>(i, 1));
}

bitset<1000> b(0);
for (auto i = m.begin(); i!=m.end(); i++) {
if (b[i->second] == 0) b[i->second] = 1;
else return false;
}
return true;
}
};

![image-20201028165108396](/Users/zrzz/Library/Application Support/typora-user-images/image-20201028165108396.png)

129. 求根到叶子节点数字之和 - 20201029

给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。

例如,从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

一道简单的回溯

// Method 1
class Solution {
public:
int ret;
vector<int> cur;

void addToRet() {
int i = 0;
for (int x:cur) {
i = i * 10 + x;
}
ret += i;
return;
}

void dfs(TreeNode* root) {
if (!root) return;
cur.push_back(root->val);
dfs(root->left);
dfs(root->right);
if (!root->left && !root->right) {
addToRet();
}
cur.pop_back();
return;
}

int sumNumbers(TreeNode* root) {
if (!root) return 0;
dfs(root);
return ret;
}
};

// Method 2
class Solution {
public:
int dfs(TreeNode* root, int i) {
if (!root) return 0;
i = i*10 + root->val;
if (!root->left && !root->right) return i;
return dfs(root->left, i) + dfs(root->right, i);
}

int sumNumbers(TreeNode* root) {
if (!root) return 0;
// dfs(root);
// return ret;
return dfs(root, 0);
}
};

![image-20201029131359428](/Users/zrzz/Library/Application Support/typora-user-images/image-20201029131359428.png)

463. 岛屿的周长 - 20201030

给定一个包含 0 和 1 的二维网格地图,其中 1 表示陆地 0 表示水域。

网格中的格子水平和垂直方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。

岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。

class Solution {
public:
int calCount(const vector<vector<int>>& grid, int i, int j, int W, int L) {
int tmp = 0;
if (i > 0){
if (!grid[i-1][j])
tmp++;
} else tmp++;

if (i < W-1){
if (!grid[i+1][j])
tmp++;
} else tmp++;

if (j > 0){
if (!grid[i][j-1])
tmp++;
} else tmp++;

if (j < L-1){
if (!grid[i][j+1])
tmp++;
} else tmp++;

return tmp;
}

int islandPerimeter(vector<vector<int>>& grid) {
if (grid.empty()) return 0;
int W = grid.size(), L = grid[0].size();
int ret = 0;

for (int i = 0; i < W; i++)
for (int j = 0; j < L; j++)
if (grid[i][j])
ret += calCount(grid, i, j, W, L);
return ret;
}
};
文章作者: X Mεl0n
文章链接: http://www.zrzz.site/2020/10/01/Leetcode-202010/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 X Mεl0n | 随手记

评论