目录
238. 除自身以外数组的乘积
给你一个整数数组 nums
,返回 数组 answer
,其中 answer[i]
等于 nums
中除 nums[i]
之外其余各元素的乘积 。
题目数据 保证 数组 nums
之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法,且在 O ( n ) O(n) 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 位 整数范围内
思路:
用两个额外的数组分别保存当前位置之前的所有的乘积和当前位置之后的所有的乘积。之后再遍历相乘。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> front(n);
vector<int> back(n);
int mul;
front[0] = 1;
mul = nums[0];
for(int i = 1; i < n; i ++){
front[i] = mul;
mul = mul * nums[i];
}
back[n-1] = 1;
mul = nums[n-1];
for(int i = n - 2; i >= 0; i --){
back[i] = mul;
mul = mul * nums[i];
}
for(int i = 0; i < n; i ++){
front[i] = front[i] * back[i];
}
return front;
}
};
134. 加油站
在一条环路上有 n
个加油站,其中第 i
个加油站有汽油 gas[i]
升。
你有一辆油箱容量无限的的汽车,从第 i
个加油站开往第 i+1
个加油站需要消耗汽油 cost[i]
升。你从其中的一个加油站出发,开始时油箱为空。
给定两个整数数组 gas
和 cost
,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1
。如果存在解,则 保证 它是 唯一 的。
示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。
因此,3 可为起始索引。
示例 2:
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。
因此,无论怎样,你都不可能绕环路行驶一周。
提示:
gas.length == n
cost.length == n
1 <= n <= 105
0 <= gas[i], cost[i] <= 104
思路:
a → d a \to d a→d走的通,但是 a → e a \to e a→e走不通,一定意味着 d → e d \to e d→e的 c o s t cost cost非常大,以至于之前路程的余油加上 d d d的油量都无法满足 d → e d \to e d→e的 c o s t cost cost。而之前 a → d a \to d a→d走的通,意味着沿途至少都是有余油的,不然欠着油也走不到。比如 a → d a \to d a→d走的通,意味着 a → b a \to b a→b和 b → d b \to d b→d走的通走的通,且 a → b a \to b a→b走的通余油大于等于0,那么 b → d b \to d b→d的最终余油小于等于 a → d a \to d a→d的最终余油, a → e a \to e a→e都走不通(最终余油不够),那么 b → e b \to e b→e更是走不通的。同理, a ∼ d a \thicksim d a∼d中间的所有节点都无法到达 e e e。直接否定中间所有节点,继续考虑新节点 e e e就可以了。
最终还要判断是不是整体油不够,如果不够,就是最后一个点 f f f也是无法循环加油的。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int total = 0;
int tempsum = 0;
int start = 0;
for(int i = 0; i < gas.size(); i++){
total += gas[i] - cost[i];
tempsum += gas[i] - cost[i];
if(tempsum < 0){
start = i + 1;
tempsum = 0;
}
}
if(total < 0) return -1;
return start;
}
};
135. 分发糖果
n
个孩子站成一排。给你一个整数数组 ratings
表示每个孩子的评分。
你需要按照以下要求,给这些孩子分发糖果:
- 每个孩子至少分配到
1
个糖果。 - 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。
示例 1:
输入:ratings = [1,0,2]
输出:5
解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2:
输入:ratings = [1,2,2]
输出:4
解释:你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。
思路:
将「相邻的孩子中,评分高的孩子必须获得更多的糖果」这句话拆分为两个规则,分别处理。
左规则:当 r a t i n g s [ i − 1 ] < r a t i n g s [ i ] ratings[i−1]<ratings[i] ratings[i−1]<ratings[i] 时, i i i 号学生的糖果数量将比 i − 1 i-1 i−1 号孩子的糖果数量多。
右规则:当 r a t i n g s [ i ] > r a t i n g s [ i + 1 ] ratings[i]>ratings[i+1] ratings[i]>ratings[i+1] 时, i i i 号学生的糖果数量将比 i + 1 i+1 i+1 号孩子的糖果数量多。
我们遍历该数组两次,处理出每一个学生分别满足左规则或右规则时,最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值。
时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( n ) O(n) O(n)。
——力扣官方题解
提示:
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> left(n);
vector<int> right(n);
int total = 0;
for(int i = 0; i < n; i++){
if(i > 0 && ratings[i] > ratings[i-1]){
left[i] = left[i-1] + 1;
}else{
left[i] = 1;
}
}
for(int i = n-1; i >= 0; i--){
if(i < n-1 && ratings[i] > ratings[i+1]){
right[i] = right[i+1] + 1;
}else{
right[i] = 1;
}
total += max(left[i], right[i]);
}
return total;
}
};
42. 接雨水
给定 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.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
思路:和上题相同思路,分别记录左边相邻最高的,和右边相邻最高的,然后计算积水。
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int left_height = height[0];
vector<int> left(n);
for(int i = 0; i < n; i++){
if(i > 0 && height[i] < left_height){
left[i] = left_height;
}else{
left[i] = height[i];
left_height = height[i];
}
//left[i] = max(left[i-1], height[i]); //上面if..else语句可以替换为这句话
}
int right_height = height[n-1];
vector<int> right(n);
for(int i = n-1; i >= 0; i--){
if(i < n-1 && height[i] < right_height){
right[i] = right_height;
}else{
right[i] = height[i];
right_height = height[i];
}
//right[i] = max(right[i-1], height[i]); //上面if..else语句可以替换为这句话
}
int rec = 0;
for(int i = 0; i < n; i ++){
rec += min(left[i], right[i]) - height[i];
}
return rec;
}
};
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 {
private:
unordered_map<char, int> hash = {
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000}
};
public:
int romanToInt(string s) {
int n = s.size();
int total = 0;
for(int i = 0; i < n; i ++){
if(i < n - 1 && hash[s[i]] < hash[s[i + 1]]){
total -= hash[s[i]];
}else{
total += hash[s[i]];
}
}
return total;
}
};
12. 整数转罗马数字
罗马数字包含以下七种字符: 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:
输入: num = 3
输出: “III”
示例 2:
输入: num = 4
输出: “IV”
示例 3:
输入: num = 9
输出: “IX”
示例 4:
输入: num = 58
输出: “LVIII”
解释: L = 50, V = 5, III = 3.
示例 5:
输入: num = 1994
输出: “MCMXCIV”
解释: M = 1000, CM = 900, XC = 90, IV = 4.
提示:
1 <= num <= 3999
思路:把特殊情况的也罗列出来
class Solution {
public:
string intToRoman(int num) {
int w = num;
string s = "";
vector<int> v(13);
vector<string> ss(13);
v = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
ss = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
for(int i = 0; i < 13 ; i++){
if(w == 0) return s;
while(w / v[i] >= 1){
s += ss[i];
w -= v[i];
}
}
return s;
}
};
58. 最后一个单词的长度
给你一个字符串 s
,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
示例 1:
输入:s = “Hello World”
输出:5
解释:最后一个单词是“World”,长度为5。
示例 2:
输入:s = " fly me to the moon "
输出:4
解释:最后一个单词是“moon”,长度为4。
示例 3:
输入:s = “luffy is still joyboy”
输出:6
解释:最后一个单词是长度为6的“joyboy”。
提示:
1 <= s.length <= 104
s
仅有英文字母和空格 ' '
组成
s
中至少存在一个单词
注意:还要考虑最后一个单词后面也有空格的情况,防止返回的值为0。
class Solution {
public:
int lengthOfLastWord(string s) {
int n = s.size();
int count = 0;
for(int i = n-1; i >= 0; i--){
if(s[i] == ' ' && count > 0) return count;
if(s[i] != ' ') count++;
}
return count;
}
};
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""
。
示例 1:
输入:strs = [“flower”,“flow”,“flight”]
输出:“fl”
示例 2:
输入:strs = [“dog”,“racecar”,“car”]
输出:“”
解释:输入不存在公共前缀。
提示:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]
仅由小写英文字母组成
注意,需要考虑的特殊情况,["ab", "a"]
初始公共串比后续的串长,["","flower","flow"]
和["flower","flow",""]
空串问题,
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string pub = strs[0];
int pub_long = pub.size();
int n = strs.size();
for(int i = 1; i < n; i++){
string temp = strs[i];
int m = temp.size();
if(m < pub_long) pub = pub.substr(0, m);
for(int j = 0; j < m; j++){
if(j >= pub_long) break;
if(pub[j] != temp[j]){
pub = pub.substr(0, j);
pub_long = pub.size();
}
}
}
return pub;
}
};
151. 反转字符串中的单词
给你一个字符串 s
,请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s
中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意:输入字符串 s
中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。
示例 1:
输入:s = “the sky is blue”
输出:“blue is sky the”
示例 2:
输入:s = " hello world "
输出:“world hello”
解释:反转后的字符串中不能存在前导空格和尾随空格。
示例 3:
输入:s = “a good example”
输出:“example good a”
解释:如果两个单词间有多余的空格,反转后的字符串需要将单词间的空格减少到仅有一个。
提示:
1 <= s.length <= 104
s
包含英文大小写字母、数字和空格 ' '
s
中 至少存在一个 单词
思路:当first和end不指向同一个位置时,表明中间存在单词,first指向单词一个字母之前的位置,end指向单词最后一个字母。
class Solution {
public:
string reverseWords(string s) {
int n = s.size();
int first = n-1;
int end = n-1;
string rec = "";
while(first >= 0){
if(s[first] == ' '){
if(first < end){ // 保证不插入空格,即结果的空格不是源自s,而是自己根据单词数量插入的
rec += s.substr(first + 1, end - first);
rec += ' ';
}
first --;
end = first;
}else{
first --;
}
}
if(end >= 0){ // 要包含等于0,不然单个字母的单词无法插入
rec += s.substr(0, end + 1); // 如果第一个单词前没空格,不要忘了补上第一个单词
}else{
rec = rec.substr(0, rec.size() - 1); // 如果第一个单词前有空格,则自己根据单词数量插入的时候最后会多一个空格,要删去
};
return rec;
}
};
6. Z字形变换
将一个给定字符串 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
思路:随时判断这样按照周期和周期内相对位置的元素循环会不会超过s的边界
class Solution {
public:
string convert(string s, int numRows) {
int n = s.size();
if(n < numRows || numRows == 1) return s;
int circle = n / numRows;
if(n % numRows > 0) circle ++; // 有几个周期,向上取整
int one_c = 2 * numRows - 2; //一个周期内有几个元素
string rec = "";
for(int j = 0; j <= one_c / 2; j++){ // 周期内循环
for(int i = 0; i < circle; i++){ // 循环周期
if(i * one_c + j < n){
rec += s[i * one_c + j];
}
if(j > 0 && ((i + 1) * one_c - j) < n && ((i + 1) * one_c - j) > (i * one_c + j)){
rec += s[(i + 1) * one_c - j];
}
}
}
return rec;
}
};
28. 找出字符串中第一个匹配项的下标
给你两个字符串 haystack
和 needle
,请你在 haystack
字符串中找出 needle
字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle
不是 haystack
的一部分,则返回 -1
。
示例 1:
输入:haystack = “sadbutsad”, needle = “sad”
输出:0
解释:“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。
示例 2:
输入:haystack = “leetcode”, needle = “leeto”
输出:-1
解释:“leeto” 没有在 “leetcode” 中出现,所以返回 -1 。
提示:
1 <= haystack.length, needle.length <= 104
haystack
和 needle
仅由小写英文字符组成
偷懒方法:
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size();
int m = needle.size();
if(m > n) return -1;
for(int i = 0; i <= n - m; i++){
string temp = haystack.substr(i, m);
if(temp == needle) return i;
}
return -1;
}
};
KMP算法:没理解透,暂时没写
68. 文本左右对齐
给定一个单词数组 words
和一个长度 maxWidth
,重新排版单词,使其成为每行恰好有 maxWidth
个字符,且左右两端对齐的文本。
你应该使用 “贪心算法” 来放置给定的单词;也就是说,尽可能多地往每行中放置单词。必要时可用空格 ' '
填充,使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配,则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐,且单词之间不插入额外的空格。
注意:
- 单词是指由非空格字符组成的字符序列。
- 每个单词的长度大于 0,小于等于 maxWidth。
- 输入单词数组
words
至少包含一个单词。
示例 1:
输入: words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”], maxWidth = 16
输出:
[
"This is an",
"example of text",
"justification. "
]
示例 2:
输入:words = [“What”,“must”,“be”,“acknowledgment”,“shall”,“be”], maxWidth = 16
输出:
[
"What must be",
"acknowledgment ",
"shall be "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 “shall be”,
因为最后一行应为左对齐,而不是左右两端对齐。
第二行同样为左对齐,这是因为这行只包含一个单词。
示例 3:
输入:words = [“Science”,“is”,“what”,“we”,“understand”,“well”,“enough”,“to”,“explain”,“to”,“a”,“computer.”,“Art”,“is”,“everything”,“else”,“we”,“do”],maxWidth = 20
输出:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
提示:
1 <= words.length <= 300
1 <= words[i].length <= 20
words[i]
由小写英文字母和符号组成
1 <= maxWidth <= 100
words[i].length <= maxWidth
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
int n = words.size();
int word_num = 0;
int count_char = 0;
int start = 0;
string s;
vector<string> rec;
for(int i = 0; i < n; i++){
if(count_char + words[i].size() + word_num <= maxWidth){ // +word_num是要考虑单词中间至少一个空格
// 加空格加单词满足条件
count_char += words[i].size();
word_num++;
}else{
//将将超过,生成带空格的字符串
if(word_num == 1){ // 和最后一行一样,只在右边加所有的空格
s = back_place(words, start, start + 1, maxWidth);
}else{ // 在单词中间加空格
s = middle_place(words, start, i, count_char, word_num, maxWidth);
}
start = i; //以为当前的但是是正好超过的那个,所以是下一行的首单词
count_char = 0;
word_num = 0;
rec.push_back(s);
i --;
}
}
if(start < n){
s = back_place(words, start, n, maxWidth);
rec.push_back(s);
}
return rec;
}
string back_place(vector<string> words, int start, int end, int maxWidth){
string s = words[start];
for(int i = start + 1; i < end; i++){
s += " ";
s += words[i];
}
for(int i = s.size(); i < maxWidth; i++){
s += " ";
}
return s;
}
string middle_place(vector<string> words, int start,int end, int count_char, int word_num, int maxWidth){
string s = words[start];
int place = (maxWidth - count_char) / (word_num - 1);
int place_plus = (maxWidth - count_char) % (word_num - 1);
for(int j = start + 1; j < end; j ++){
//加空格
int k = 0;
while(k < place){
s += " ";
k++;
}
if(j - start - 1 < place_plus) s += " ";
s += words[j];
}
return s;
}
};