前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家:点击跳转
目录
2. 两数相加
4. 寻找两个正序数组的中位数
5. 最长回文子串(python)
6. N 字形变换
10. 正则表达式匹配(python)
13. 罗马数字转整数
16. 最接近的三数之和(python)
17. 电话号码的字母组合(python)
24. 两两交换链表中的节点
32. 最长有效括号
38. 外观数列(python)
40. 组合总和 II
43. 字符串相乘
415. 字符串相加
722. 删除注释
1091. 二进制矩阵中的最短路径
1285. 找到连续区间的开始和结束数字(MySql)
1294. 不同国家的天气类型(MySql)
1303. 求团队人数(MySql)
1350. 院系无效的学生(MySql)
1355. 活动参与者(MySql)
2490. 回环句
本文给的都是AI作答的结果,所有问答都是纯文本。
只给出AI给出的AC代码,不能AC的就算了。
有些题目,AI给不出c++代码,但是可以给出python代码。我默认都是用c++,c++无解答的才会尝试python。
2. 两数相加
问:
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 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
题目数据保证列表表示的数字不含前导零
填充c++代码:
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
}
};
答:
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0); // 创建一个虚拟头结点
ListNode* cur = dummy; // cur指向虚拟头结点
int carry = 0; // 进位
while (l1 || l2 || carry) { // 只要有一个链表不为空或者有进位,就继续循环
int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry; // 计算当前位的和
carry = sum / 10; // 计算进位
cur->next = new ListNode(sum % 10); // 创建新结点存储当前位的值
cur = cur->next; // cur指向新结点
if (l1) l1 = l1->next; // l1指向下一个结点
if (l2) l2 = l2->next; // l2指向下一个结点
}
return dummy->next; // 返回虚拟头结点的下一个结点
}
};
4. 寻找两个正序数组的中位数
问:
给定两个大小分别为 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 == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
}
};
答:
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if (m > n) {
return findMedianSortedArrays(nums2, nums1);
}
int left = 0, right = m, half_len = (m + n + 1) / 2;
while (left <= right) {
int i = (left + right) / 2;
int j = half_len - i;
if (i < m && nums2[j-1] > nums1[i]) {
left = i + 1;
} else if (i > 0 && nums1[i-1] > nums2[j]) {
right = i - 1;
} else {
int max_left = 0;
if (i == 0) {
max_left = nums2[j-1];
} else if (j == 0) {
max_left = nums1[i-1];
} else {
max_left = max(nums1[i-1], nums2[j-1]);
}
if ((m + n) % 2 == 1) {
return max_left;
}
int min_right = 0;
if (i == m) {
min_right = nums2[j];
} else if (j == n) {
min_right = nums1[i];
} else {
min_right = min(nums1[i], nums2[j]);
}
return (max_left + min_right) / 2.0;
}
}
return 0.0;
}
};
5. 最长回文子串(python)
问:
给你一个字符串 s,找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母组成
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
答:
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s)
dp = [[False] * n for _ in range(n)]
ans = ""
# 枚举子串的长度 l+1
for l in range(n):
# 枚举子串的起始位置 i,这样可以通过 j=i+l 得到子串的结束位置
for i in range(n):
j = i + l
if j >= n:
break
if l == 0:
dp[i][j] = True
elif l == 1:
dp[i][j] = (s[i] == s[j])
else:
dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])
if dp[i][j] and l + 1 > len(ans):
ans = s[i:j+1]
return ans
6. N 字形变换
问:
将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:
P A H N
A P L S I I G
Y I R
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);
示例 1:
输入:s = "PAYPALISHIRING", numRows = 3
输出:"PAHNAPLSIIGYIR"
示例 2:
输入:s = "PAYPALISHIRING", numRows = 4
输出:"PINALSIGYAHRPI"
解释:
P I N
A L S I G
Y A H R
P I
示例 3:
输入:s = "A", numRows = 1
输出:"A"
提示:
1 <= s.length <= 1000
s 由英文字母(小写和大写)、',' 和 '.' 组成
1 <= numRows <= 1000
class Solution {
public:
string convert(string s, int numRows) {
}
};
答:
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) {
return s;
}
vector<vector<char>> matrix(numRows, vector<char>(s.size()));
int row = 0, col = 0, flag = -1;
for (char c : s) {
matrix[row][col] = c;
if (row == 0 || row == numRows - 1) {
flag = -flag;
}
row += flag;
col++;
}
string ans;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < s.size(); j++) {
if (matrix[i][j] != 0) {
ans += matrix[i][j];
}
}
}
return ans;
}
};
10. 正则表达式匹配(python)
问:
给你一个字符串 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 <= 20
1 <= p.length <= 20
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母,以及字符 . 和 *。
保证每次出现字符 * 时,前面都匹配到有效的字符
class Solution:
def isMatch(self, s: str, p: str) -> bool:
答:
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n+1) for _ in range(m+1)]
dp[0][0] = True
for i in range(2, n+1):
if p[i-1] == '*':
dp[0][i] = dp[0][i-2]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1] == p[j-1] or p[j-1] == '.':
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
dp[i][j] = dp[i][j-2] or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
return dp[m][n]
13. 罗马数字转整数
问:
罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1 。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。
示例 1:
输入: s = "III"
输出: 3
示例 2:
输入: s = "IV"
输出: 4
示例 3:
输入: s = "IX"
输出: 9
示例 4:
输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
提示:
1 <= s.length <= 15
s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
题目数据保证 s 是一个有效的罗马数字,且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则,不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求,49 应该写作 XLIX,999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则,可以参考 罗马数字 - Mathematics 。
class Solution {
public:
int romanToInt(string s) {
}
};
答:
class Solution {
public:
int romanToInt(string s) {
unordered_map<char, int> m = {
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000}
};
int res = 0;
for (int i = 0; i < s.size(); i++) {
if (i < s.size() - 1 && m[s[i]] < m[s[i+1]]) {
res -= m[s[i]];
} else {
res += m[s[i]];
}
}
return res;
}
};
16. 最接近的三数之和(python)
问:
给你一个长度为 n
的整数数组 nums
和 一个目标值 target
。请你从 nums
中选出三个整数,使它们的和与 target
最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1:
输入:nums = [-1,2,1,-4], target = 1 输出:2 解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2:
输入:nums = [0,0,0], target = 1 输出:0
提示:
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
答:
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
ans = float('inf')
for i in range(n):
left, right = i + 1, n - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if abs(sum - target) < abs(ans - target):
ans = sum
if sum < target:
left += 1
elif sum > target:
right -= 1
else:
return target
return ans
17. 电话号码的字母组合(python)
问:
给定一个仅包含数字 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 <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
答:
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
mapping = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
res = []
def backtrack(combination, next_digits):
if not next_digits:
res.append(combination)
else:
for letter in mapping[next_digits[0]]:
backtrack(combination + letter, next_digits[1:])
backtrack('', digits)
return res
24. 两两交换链表中的节点
问:
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
提示:
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
}
};
答:
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* p1 = dummy;
ListNode* p2 = head;
while (p2 && p2->next) {
ListNode* next = p2->next->next;
p1->next = p2->next;
p2->next->next = p2;
p2->next = next;
p1 = p2;
p2 = next;
}
return dummy->next;
}
};
32. 最长有效括号
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 1:
输入:s = "(()" 输出:2 解释:最长有效括号子串是 "()"
示例 2:
输入:s = ")()())" 输出:4 解释:最长有效括号子串是 "()()"
示例 3:
输入:s = "" 输出:0
提示:
0 <= s.length <= 3 * 104
-
s[i]
为'('
或')'
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stk;
stk.push(-1);
int maxLen = 0;
for(int i = 0; i < s.size(); i++) {
if(s[i] == '(') {
stk.push(i);
} else {
stk.pop();
if(stk.empty()) {
stk.push(i);
} else {
maxLen = max(maxLen, i - stk.top());
}
}
}
return maxLen;
}
};
38. 外观数列(python)
给定一个正整数 n
,输出外观数列的第 n
项。
「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列:
countAndSay(1) = "1"
-
countAndSay(n)
是对countAndSay(n-1)
的描述,然后转换成另一个数字字符串。
前五项如下:
1. 1 2. 11 3. 21 4. 1211 5. 111221 第一项是数字 1 描述前一项,这个数是1
即 “ 一 个 1 ”,记作"11"
描述前一项,这个数是11
即 “ 二 个 1 ” ,记作"21"
描述前一项,这个数是21
即 “ 一 个 2 + 一 个 1 ” ,记作 "1211"
描述前一项,这个数是1211
即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ,记作 "111221"
要 描述 一个数字字符串,首先要将字符串分割为 最小 数量的组,每个组都由连续的最多 相同字符 组成。然后对于每个组,先描述字符的数量,然后描述字符,形成一个描述组。要将描述转换为数字字符串,先将每组中的字符数量用数字替换,再将所有描述组连接起来。
例如,数字字符串 "3322251"
的描述如下图:
示例 1:
输入:n = 1 输出:"1" 解释:这是一个基本样例。
示例 2:
输入:n = 4 输出:"1211" 解释: countAndSay(1) = "1" countAndSay(2) = 读 "1" = 一 个 1 = "11" countAndSay(3) = 读 "11" = 二 个 1 = "21" countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
提示:
1 <= n <= 30
class Solution:
def countAndSay(self, n: int) -> str:
if n == 1:
return '1'
prev = self.countAndSay(n-1)
res = ''
i = 0
while i < len(prev):
count = 1
while i < len(prev)-1 and prev[i] == prev[i+1]:
count += 1
i += 1
res += str(count) + prev[i]
i += 1
return res
40. 组合总和 II
问:
给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
}
};
答:
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> path;
sort(candidates.begin(), candidates.end()); // 对候选人编号集合进行排序
backtrack(candidates, target, 0, path, res);
return res;
}
void backtrack(vector<int>& candidates, int target, int start, vector<int>& path, vector<vector<int>>& res) {
if (target == 0) { // 如果当前的数字和等于目标数,就将当前的组合加入结果集
res.push_back(path);
return;
}
for (int i = start; i < candidates.size() && candidates[i] <= target; i++) {
if (i > start && candidates[i] == candidates[i-1]) continue; // 去重
path.push_back(candidates[i]);
backtrack(candidates, target-candidates[i], i+1, path, res); // 从当前数字的下一个位置开始继续回溯
path.pop_back();
}
}
};
43. 字符串相乘
给定两个以字符串形式表示的非负整数 num1
和 num2
,返回 num1
和 num2
的乘积,它们的乘积也表示为字符串形式。
注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3" 输出: "6"
示例 2:
输入: num1 = "123", num2 = "456" 输出: "56088"
提示:
1 <= num1.length, num2.length <= 200
-
num1
和num2
只能由数字组成。 -
num1
和num2
都不包含任何前导零,除了数字0本身。
class Solution {
public:
string multiply(string num1, string num2) {
int n1 = num1.size();
int n2 = num2.size();
vector<int> result(n1 + n2, 0);
for (int i = n1 - 1; i >= 0; i--) {
for (int j = n2 - 1; j >= 0; j--) {
int mul = (num1[i] - '0') * (num2[j] - '0');
int p1 = i + j, p2 = i + j + 1;
int sum = mul + result[p2];
result[p1] += sum / 10;
result[p2] = sum % 10;
}
}
string ans = "";
for (int num : result) {
if (!(ans.empty() && num == 0)) {
ans += to_string(num);
}
}
return ans.empty() ? "0" : ans;
}
};
44. 通配符匹配
给你一个输入字符串 (s
) 和一个字符模式 (p
) ,请你实现一个支持 '?'
和 '*'
匹配规则的通配符匹配:
-
'?'
可以匹配任何单个字符。 -
'*'
可以匹配任意字符序列(包括空字符序列)。
判定匹配成功的充要条件是:字符模式必须能够 完全匹配 输入字符串(而不是部分匹配)。
示例 1:
输入:s = "aa", p = "a" 输出:false 解释:"a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:s = "aa", p = "*" 输出:true 解释:'*' 可以匹配任意字符串。
示例 3:
输入:s = "cb", p = "?a" 输出:false 解释:'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
提示:
0 <= s.length, p.length <= 2000
-
s
仅由小写英文字母组成 -
p
仅由小写英文字母、'?'
或'*'
组成
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n+1) for _ in range(m+1)]
dp[0][0] = True
for j in range(1, n+1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-1]
for i in range(1, m+1):
for j in range(1, n+1):
if p[j-1] == s[i-1] or p[j-1] == '?':
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
dp[i][j] = dp[i][j-1] or dp[i-1][j]
return dp[m][n]
48. 旋转图像
给定一个 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].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
// 矩阵转置
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
// 每行翻转
for (int i = 0; i < n; i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
}
};
57. 插入区间
给你一个 无重叠的 ,按照区间起始端点排序的区间列表。
在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。
示例 1:
输入:intervals = [[1,3],[6,9]], newInterval = [2,5] 输出:[[1,5],[6,9]]
示例 2:
输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 输出:[[1,2],[3,10],[12,16]] 解释:这是因为新的区间[4,8]
与[3,5],[6,7],[8,10]
重叠。
示例 3:
输入:intervals = [], newInterval = [5,7] 输出:[[5,7]]
示例 4:
输入:intervals = [[1,5]], newInterval = [2,3] 输出:[[1,5]]
示例 5:
输入:intervals = [[1,5]], newInterval = [2,7] 输出:[[1,7]]
提示:
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 105
-
intervals
根据intervals[i][0]
按 升序 排列 newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 105
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> res;
int n = intervals.size();
int i = 0;
// 找到新区间左侧不重叠的区间
while (i < n && intervals[i][1] < newInterval[0]) {
res.push_back(intervals[i++]);
}
// 合并重叠的区间
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
i++;
}
res.push_back(newInterval);
// 将右侧不重叠的区间加入结果
while (i < n) {
res.push_back(intervals[i++]);
}
return res;
}
};
415. 字符串相加
问:
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。
示例 1:
输入:num1 = "11", num2 = "123"
输出:"134"
示例 2:
输入:num1 = "456", num2 = "77"
输出:"533"
示例 3:
输入:num1 = "0", num2 = "0"
输出:"0"
提示:
1 <= num1.length, num2.length <= 104
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零
class Solution {
public:
string addStrings(string num1, string num2) {
}
};
答:
class Solution {
public:
string addStrings(string num1, string num2) {
string res = "";
int carry = 0;
int i = num1.size() - 1, j = num2.size() - 1;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry;
if (i >= 0) sum += num1[i--] - '0';
if (j >= 0) sum += num2[j--] - '0';
carry = sum / 10;
sum %= 10;
res = to_string(sum) + res;
}
return res;
}
};
722. 删除注释
问:
给一个 C++ 程序,删除程序中的注释。这个程序source是一个数组,其中source[i]表示第 i 行源码。 这表示每行源码由 '\n' 分隔。
在 C++ 中有两种注释风格,行内注释和块注释。
字符串// 表示行注释,表示//和其右侧的其余字符应该被忽略。
字符串/* 表示一个块注释,它表示直到下一个(非重叠)出现的*/之间的所有字符都应该被忽略。(阅读顺序为从左到右)非重叠是指,字符串/*/并没有结束块注释,因为注释的结尾与开头相重叠。
第一个有效注释优先于其他注释。
如果字符串//出现在块注释中会被忽略。
同样,如果字符串/*出现在行或块注释中也会被忽略。
如果一行在删除注释之后变为空字符串,那么不要输出该行。即,答案列表中的每个字符串都是非空的。
样例中没有控制字符,单引号或双引号字符。
比如,source = "string s = "/* Not a comment. */";" 不会出现在测试样例里。
此外,没有其他内容(如定义或宏)会干扰注释。
我们保证每一个块注释最终都会被闭合, 所以在行或块注释之外的/*总是开始新的注释。
最后,隐式换行符可以通过块注释删除。 有关详细信息,请参阅下面的示例。
从源代码中删除注释后,需要以相同的格式返回源代码。
示例 1:
输入: source = ["/*Test program */", "int main()", "{ ", " // variable declaration ", "int a, b, c;", "/* This is a test", " multiline ", " comment for ", " testing */", "a = b + c;", "}"]
输出: ["int main()","{ "," ","int a, b, c;","a = b + c;","}"]
解释: 示例代码可以编排成这样:
/*Test program */
int main()
{
// variable declaration
int a, b, c;
/* This is a test
multiline
comment for
testing */
a = b + c;
}
第 1 行和第 6-9 行的字符串 /* 表示块注释。第 4 行的字符串 // 表示行注释。
编排后:
int main()
{
int a, b, c;
a = b + c;
}
示例 2:
输入: source = ["a/*comment", "line", "more_comment*/b"]
输出: ["ab"]
解释: 原始的 source 字符串是 "a/*comment\nline\nmore_comment*/b", 其中我们用粗体显示了换行符。删除注释后,隐含的换行符被删除,留下字符串 "ab" 用换行符分隔成数组时就是 ["ab"].
提示:
1 <= source.length <= 100
0 <= source[i].length <= 80
source[i] 由可打印的 ASCII 字符组成。
每个块注释都会被闭合。
给定的源码中不会有单引号、双引号或其他控制字符。
class Solution {
public:
vector<string> removeComments(vector<string>& source) {
}
};
答:
class Solution {
public:
vector<string> removeComments(vector<string>& source) {
vector<string> res;
bool inBlock = false;
string cur = "";
for (string s : source) {
for (int i = 0; i < s.size(); i++) {
if (!inBlock && i + 1 < s.size() && s[i] == '/' && s[i + 1] == '/') {
break;
} else if (!inBlock && i + 1 < s.size() && s[i] == '/' && s[i + 1] == '*') {
inBlock = true;
i++;
} else if (inBlock && i + 1 < s.size() && s[i] == '*' && s[i + 1] == '/') {
inBlock = false;
i++;
} else if (!inBlock) {
cur += s[i];
}
}
if (!inBlock && cur != "") {
res.push_back(cur);
cur = "";
}
}
return res;
}
};
1091. 二进制矩阵中的最短路径
问:
给你一个 n x n 的二进制矩阵 grid 中,返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径,返回 -1 。
二进制矩阵中的 畅通路径 是一条从 左上角 单元格(即,(0, 0))到 右下角 单元格(即,(n - 1, n - 1))的路径,该路径同时满足下述要求:
路径途经的所有单元格的值都是 0 。
路径中所有相邻的单元格应当在 8 个方向之一 上连通(即,相邻两单元之间彼此不同且共享一条边或者一个角)。
畅通路径的长度 是该路径途经的单元格总数。
示例 1:
输入:grid = [[0,1],[1,0]]
输出:2
示例 2:
输入:grid = [[0,0,0],[1,1,0],[1,1,0]]
输出:4
示例 3:
输入:grid = [[1,0,0],[1,1,0],[1,1,0]]
输出:-1
提示:
n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] 为 0 或 1
填充c++代码:
class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
}
};
答:
class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int n = grid.size();
if (grid[0][0] == 1 || grid[n-1][n-1] == 1) {
return -1;
}
vector<vector<int>> dirs = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};
queue<pair<int,int>> q;
q.push({0,0});
grid[0][0] = 1;
int steps = 1;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
auto curr = q.front();
q.pop();
if (curr.first == n-1 && curr.second == n-1) {
return steps;
}
for (auto dir : dirs) {
int x = curr.first + dir[0];
int y = curr.second + dir[1];
if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0) {
q.push({x,y});
grid[x][y] = 1;
}
}
}
steps++;
}
return -1;
}
};
1285. 找到连续区间的开始和结束数字(MySql)
问:
表:Logs
+---------------+---------+
| Column Name | Type |
+---------------+---------+
| log_id | int |
+---------------+---------+
id 是上表的主键。
上表的每一行包含日志表中的一个 ID。
后来一些 ID 从 Logs 表中删除。编写一个 SQL 查询得到 Logs 表中的连续区间的开始数字和结束数字。
将查询表按照 start_id 排序。
查询结果格式如下面的例子。
示例 1:
输入:
Logs 表:
+------------+
| log_id |
+------------+
| 1 |
| 2 |
| 3 |
| 7 |
| 8 |
| 10 |
+------------+
输出:
+------------+--------------+
| start_id | end_id |
+------------+--------------+
| 1 | 3 |
| 7 | 8 |
| 10 | 10 |
+------------+--------------+
解释:
结果表应包含 Logs 表中的所有区间。
从 1 到 3 在表中。
从 4 到 6 不在表中。
从 7 到 8 在表中。
9 不在表中。
10 在表中。
# Write your MySQL query statement below
答:
SELECT MIN(log_id) AS start_id, MAX(log_id) AS end_id
FROM (
SELECT log_id, log_id - ROW_NUMBER() OVER (ORDER BY log_id) AS group_id
FROM Logs
) AS temp
GROUP BY group_id
ORDER BY start_id;
1294. 不同国家的天气类型(MySql)
问:
国家表:Countries
+---------------+---------+
| Column Name | Type |
+---------------+---------+
| country_id | int |
| country_name | varchar |
+---------------+---------+
country_id 是这张表的主键。
该表的每行有 country_id 和 country_name 两列。
天气表:Weather
+---------------+---------+
| Column Name | Type |
+---------------+---------+
| country_id | int |
| weather_state | varchar |
| day | date |
+---------------+---------+
(country_id, day) 是该表的复合主键。
该表的每一行记录了某个国家某一天的天气情况。
写一段 SQL 来找到表中每个国家在 2019 年 11 月的天气类型。
天气类型的定义如下:当 weather_state 的平均值小于或等于15返回 Cold,当 weather_state 的平均值大于或等于 25 返回 Hot,否则返回 Warm。
你可以以任意顺序返回你的查询结果。
查询结果格式如下所示:
Countries table:
+------------+--------------+
| country_id | country_name |
+------------+--------------+
| 2 | USA |
| 3 | Australia |
| 7 | Peru |
| 5 | China |
| 8 | Morocco |
| 9 | Spain |
+------------+--------------+
Weather table:
+------------+---------------+------------+
| country_id | weather_state | day |
+------------+---------------+------------+
| 2 | 15 | 2019-11-01 |
| 2 | 12 | 2019-10-28 |
| 2 | 12 | 2019-10-27 |
| 3 | -2 | 2019-11-10 |
| 3 | 0 | 2019-11-11 |
| 3 | 3 | 2019-11-12 |
| 5 | 16 | 2019-11-07 |
| 5 | 18 | 2019-11-09 |
| 5 | 21 | 2019-11-23 |
| 7 | 25 | 2019-11-28 |
| 7 | 22 | 2019-12-01 |
| 7 | 20 | 2019-12-02 |
| 8 | 25 | 2019-11-05 |
| 8 | 27 | 2019-11-15 |
| 8 | 31 | 2019-11-25 |
| 9 | 7 | 2019-10-23 |
| 9 | 3 | 2019-12-23 |
+------------+---------------+------------+
Result table:
+--------------+--------------+
| country_name | weather_type |
+--------------+--------------+
| USA | Cold |
| Austraila | Cold |
| Peru | Hot |
| China | Warm |
| Morocco | Hot |
+--------------+--------------+
USA 11 月的平均 weather_state 为 (15) / 1 = 15 所以天气类型为 Cold。
Australia 11 月的平均 weather_state 为 (-2 + 0 + 3) / 3 = 0.333 所以天气类型为 Cold。
Peru 11 月的平均 weather_state 为 (25) / 1 = 25 所以天气类型为 Hot。
China 11 月的平均 weather_state 为 (16 + 18 + 21) / 3 = 18.333 所以天气类型为 Warm。
Morocco 11 月的平均 weather_state 为 (25 + 27 + 31) / 3 = 27.667 所以天气类型为 Hot。
我们并不知道 Spain 在 11 月的 weather_state 情况所以无需将他包含在结果中。
# Write your MySQL query statement below
答:
SELECT c.country_name,
CASE
WHEN AVG(w.weather_state) <= 15 THEN 'Cold'
WHEN AVG(w.weather_state) >= 25 THEN 'Hot'
ELSE 'Warm'
END AS weather_type
FROM Countries c
JOIN Weather w
ON c.country_id = w.country_id
WHERE w.day BETWEEN '2019-11-01' AND '2019-11-30'
GROUP BY c.country_name;
1303. 求团队人数(MySql)
问:
员工表:Employee
+---------------+---------+
| Column Name | Type |
+---------------+---------+
| employee_id | int |
| team_id | int |
+---------------+---------+
employee_id 字段是这张表的主键,表中的每一行都包含每个员工的 ID 和他们所属的团队。
编写一个 SQL 查询,以求得每个员工所在团队的总人数。
查询结果中的顺序无特定要求。
查询结果格式示例如下:
Employee Table:
+-------------+------------+
| employee_id | team_id |
+-------------+------------+
| 1 | 8 |
| 2 | 8 |
| 3 | 8 |
| 4 | 7 |
| 5 | 9 |
| 6 | 9 |
+-------------+------------+
Result table:
+-------------+------------+
| employee_id | team_size |
+-------------+------------+
| 1 | 3 |
| 2 | 3 |
| 3 | 3 |
| 4 | 1 |
| 5 | 2 |
| 6 | 2 |
+-------------+------------+
ID 为 1、2、3 的员工是 team_id 为 8 的团队的成员,
ID 为 4 的员工是 team_id 为 7 的团队的成员,
ID 为 5、6 的员工是 team_id 为 9 的团队的成员。
# Write your MySQL query statement below
答:
SELECT employee_id,
(SELECT COUNT(*) FROM Employee WHERE team_id = e.team_id) AS team_size
FROM Employee e
1350. 院系无效的学生(MySql)
问:
院系表: Departments
+---------------+---------+
| Column Name | Type |
+---------------+---------+
| id | int |
| name | varchar |
+---------------+---------+
id 是该表的主键
该表包含一所大学每个院系的 id 信息
学生表: Students
+---------------+---------+
| Column Name | Type |
+---------------+---------+
| id | int |
| name | varchar |
| department_id | int |
+---------------+---------+
id 是该表的主键
该表包含一所大学每个学生的 id 和他/她就读的院系信息
写一条 SQL 语句以查询那些所在院系不存在的学生的 id 和姓名
可以以 任何顺序 返回结果。
下面是返回结果格式的例子。
示例 1:
输入:
Departments 表:
+------+--------------------------+
| id | name |
+------+--------------------------+
| 1 | Electrical Engineering |
| 7 | Computer Engineering |
| 13 | Bussiness Administration |
+------+--------------------------+
Students 表:
+------+----------+---------------+
| id | name | department_id |
+------+----------+---------------+
| 23 | Alice | 1 |
| 1 | Bob | 7 |
| 5 | Jennifer | 13 |
| 2 | John | 14 |
| 4 | Jasmine | 77 |
| 3 | Steve | 74 |
| 6 | Luis | 1 |
| 8 | Jonathan | 7 |
| 7 | Daiana | 33 |
| 11 | Madelynn | 1 |
+------+----------+---------------+
输出:
+------+----------+
| id | name |
+------+----------+
| 2 | John |
| 7 | Daiana |
| 4 | Jasmine |
| 3 | Steve |
+------+----------+
解释:
John, Daiana, Steve 和 Jasmine 所在的院系分别是 14, 33, 74 和 77, 其中 14, 33, 74 和 77 并不存在于院系表
# Write your MySQL query statement below
答:
SELECT id, name
FROM Students
WHERE department_id NOT IN (SELECT id FROM Departments)
1355. 活动参与者(MySql)
表: Friends
+---------------+---------+
| Column Name | Type |
+---------------+---------+
| id | int |
| name | varchar |
| activity | varchar |
+---------------+---------+
id 是朋友的 id 和该表的主键
name 是朋友的名字
activity 是朋友参加的活动的名字
表: Activities
+---------------+---------+
| Column Name | Type |
+---------------+---------+
| id | int |
| name | varchar |
+---------------+---------+
id 是该表的主键
name 是活动的名字
写一条 SQL 查询那些既没有最多,也没有最少参与者的活动的名字
Activities 表中的任意活动都有在 Friends 中参与过
可以以 任何顺序 返回结果。
下面是查询结果格式的例子。
示例 1:
输入:
Friends 表:
+------+--------------+---------------+
| id | name | activity |
+------+--------------+---------------+
| 1 | Jonathan D. | Eating |
| 2 | Jade W. | Singing |
| 3 | Victor J. | Singing |
| 4 | Elvis Q. | Eating |
| 5 | Daniel A. | Eating |
| 6 | Bob B. | Horse Riding |
+------+--------------+---------------+
Activities 表:
+------+--------------+
| id | name |
+------+--------------+
| 1 | Eating |
| 2 | Singing |
| 3 | Horse Riding |
+------+--------------+
输出:
+--------------+
| activity |
+--------------+
| Singing |
+--------------+
解释:
Eating 活动有三个人参加, 是最多人参加的活动 (Jonathan D. , Elvis Q. and Daniel A.)
Horse Riding 活动有一个人参加, 是最少人参加的活动 (Bob B.)
Singing 活动有两个人参加 (Victor J. and Jade W.)
SELECT a.name AS activity
FROM Activities a
JOIN Friends f ON a.name = f.activity
GROUP BY a.name
HAVING COUNT(DISTINCT f.id) NOT IN (
(SELECT COUNT(DISTINCT f1.id) FROM Friends f1 GROUP BY f1.activity ORDER BY COUNT(DISTINCT f1.id) DESC LIMIT 1),
(SELECT COUNT(DISTINCT f2.id) FROM Friends f2 GROUP BY f2.activity ORDER BY COUNT(DISTINCT f2.id) ASC LIMIT 1)
)
2490. 回环句
问:
句子 是由单个空格分隔的一组单词,且不含前导或尾随空格。
例如,"Hello World"、"HELLO"、"hello world hello world" 都是符合要求的句子。
单词 仅 由大写和小写英文字母组成。且大写和小写字母会视作不同字符。
如果句子满足下述全部条件,则认为它是一个 回环句 :
单词的最后一个字符和下一个单词的第一个字符相等。
最后一个单词的最后一个字符和第一个单词的第一个字符相等。
例如,"leetcode exercises sound delightful"、"eetcode"、"leetcode eats soul" 都是回环句。然而,"Leetcode is cool"、"happy Leetcode"、"Leetcode" 和 "I like Leetcode" 都 不 是回环句。
给你一个字符串 sentence ,请你判断它是不是一个回环句。如果是,返回 true ;否则,返回 false 。
示例 1:
输入:sentence = "leetcode exercises sound delightful"
输出:true
解释:句子中的单词是 ["leetcode", "exercises", "sound", "delightful"] 。
- leetcode 的最后一个字符和 exercises 的第一个字符相等。
- exercises 的最后一个字符和 sound 的第一个字符相等。
- sound 的最后一个字符和 delightful 的第一个字符相等。
- delightful 的最后一个字符和 leetcode 的第一个字符相等。
这个句子是回环句。
示例 2:
输入:sentence = "eetcode"
输出:true
解释:句子中的单词是 ["eetcode"] 。
- eetcode 的最后一个字符和 eetcode 的第一个字符相等。
这个句子是回环句。
示例 3:
输入:sentence = "Leetcode is cool"
输出:false
解释:句子中的单词是 ["Leetcode", "is", "cool"] 。
- Leetcode 的最后一个字符和 is 的第一个字符 不 相等。
这个句子 不 是回环句。
提示:
1 <= sentence.length <= 500
sentence 仅由大小写英文字母和空格组成
sentence 中的单词由单个空格进行分隔
不含任何前导或尾随空格文章来源:https://www.toymoban.com/news/detail-461031.html
class Solution {
public:
bool isCircularSentence(string sentence) {
}
};
答:文章来源地址https://www.toymoban.com/news/detail-461031.html
class Solution {
public:
bool isCircularSentence(string sentence) {
vector<string> words;
string word = "";
for (char c : sentence) {
if (c == ' ') {
words.push_back(word);
word = "";
} else {
word += c;
}
}
words.push_back(word); // 加入最后一个单词
int n = words.size();
for (int i = 0; i < n - 1; i++) {
if (words[i][words[i].size() - 1] != words[i + 1][0]) {
return false;
}
}
return words[n - 1][words[n - 1].size() - 1] == words[0][0];
}
};
到了这里,关于AI刷力扣的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!