
88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。
示例 1:
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。
示例 2:
输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3:
输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
1 | package h.xd.algo; |
1 | package algo |
注意点:
- 一个数组为空的判断是m-1 < 0 和 n-1<0 而不是 <=
- 一个驻足为空也要last–
27. 移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k,要通过此题,您需要执行以下操作:
更改 nums 数组,使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。
用户评测:
评测机将使用以下代码测试您的解决方案:
1 | int[] nums = [...]; // 输入数组 |
如果所有的断言都通过,你的解决方案将会 通过。
示例 1:
输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2,,]
解释:你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要(因此它们并不计入评测)。
示例 2:
输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3,,,_]
解释:你的函数应该返回 k = 5,并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要(因此它们并不计入评测)。
1 | class Solution { |
1 | func removeElement(nums []int, val int) int { |
注意点:
- 不要忘了两指针交会 if(i > last) break
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 升汽油。
因此,无论怎样,你都不可能绕环路行驶一周。
以下解题暴力解法,一个一个看能不能走一圈,不能走一圈就break掉,下一个继续走,以此类推。 双轮循环, 时间复杂度超了,为n^2
难点:
- 怎么判断走一圈,用计数法,计数等于长度则为走了一圈以下为时间复杂度N的解法,遍历一次,用多个存储变量记录状态并判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
for(int i=0;i<gas.length;i++){
int current = 0;
current += gas[i];
if(current < cost[i]){
continue;
}
current -= cost[i];
int start = i;
int next = start+1;
for (int j=0;j<gas.length;j++){
if(next > gas.length-1)
next=0;
current += gas[next];
if(current < cost[next]){
break;
}
if(next == start){
return start;
}
current-=cost[next];
next++;
}
}
return -1;
}
}
需要记录总油,总花费,用来判断总油不够总花费,直接-1
需要记录 result 为暂时起点,默认无暂时起点,为-1
需要记录 curLast 为有暂时起点情况下, 暂时起点至目前总剩余油量
难点:
- 逻辑复杂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int allGas = 0;
int allCost = 0;
int result = -1;
int curLast = 0;
for(int i=0;i<gas.length;i++){
allGas = allGas + gas[i];
allCost = allCost +cost[i];
if(gas[i] >= cost[i]){
if(result == -1){
result = i;
curLast = gas[i] - cost[i];
}else{
curLast = curLast + gas[i] - cost[i];
}
}else{
if(result != -1){
if(curLast + gas[i] - cost[i] < 0){
result = -1;
curLast = 0;
}else{
curLast = curLast + gas[i] - cost[i];
}
}else{
continue;
}
}
}
if(allGas - allCost >= 0){
return result;
}else{
return -1;
}
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42func canCompleteCircuit(gas []int, cost []int) int {
allGas :=0
allCost :=0
result := -1
curLast := 0
for i,_ := range gas{
allGas = allGas + gas[i]
allCost = allCost + cost[i]
if gas[i] >= cost[i] {
//当前为起点的话,油够跑到下一个点
if result == -1 {
//当前没有暂存点,开始记录暂存点
result = i
curLast = gas[i] - cost[i]
}else {
//当前有暂存点,一定能过去,暂存点一定需要改变,记录花费
curLast = curLast + gas[i] - cost[i]
}
}else{
//当前为起点的话,油不够跑到下一个点
if result == -1 {
//没有起点,当前也不能是起点 应跳过
continue
}else{
//有起点了,需要看下是否需要重置起点
if curLast + gas[i] - cost[i] < 0 {
//走不到下个点,重置
result = -1
curLast = 0
}else{
//走到下个点了,记录汇总油耗
curLast = curLast + gas[i] - cost[i];
}
}
}
}
if allGas - allCost >= 0 {
return result
}else{
return -1
}
}
135. 分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求,给这些孩子分发糖果:
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。
示例 1:
输入:ratings = [1,0,2]
输出:5
解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2:
输入:ratings = [1,2,2]
输出:4
解释:你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。
解题思路:例子比较少,不好看出规律,注意左右相等, 右侧可以为1糖果
自己再举几个特殊的例子:
1,2,3,4,5 的话, 糖果为 1,2,3,4,5 需要15个
1,1,1,1,1 的话,需要 1,1,1,1,1 需要5个
5,4,3,2,1的话, 需要 5,4,3,2,1 需要15个, 和第一个对称。对称很重要,距离几个对称的例子。
1,2,2,3,3的话,需要 1,2,1,2,1 需要 7个
3,3,2,2,1的话,需要 1,2,1,1,0,需要 5个,但是不满足条件,而是 1,2,1,2,1 需要7个是最优解
这里有个规律, 正反求一次, max 上下 ,时间复杂度2N, , 还可以
1 | class Solution { |
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
思路:
两个单调递增栈,找规律比较大小
1 | class Solution { |
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 | class Solution { |
12. 整数转罗马数字
七个不同的符号代表罗马数字,其值如下:
符号 值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则:
如果该值不是以 4 或 9 开头,请选择可以从输入中减去的最大值的符号,将该符号附加到结果,减去其值,然后将其余部分转换为罗马数字。
如果该值以 4 或 9 开头,使用 减法形式,表示从以下符号中减去一个符号,例如 4 是 5 (V) 减 1 (I): IV ,9 是 10 (X) 减 1 (I):IX。仅使用以下减法形式:4 (IV),9 (IX),40 (XL),90 (XC),400 (CD) 和 900 (CM)。
只有 10 的次方(I, X, C, M)最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V),50 (L) 或 500 (D)。如果需要将符号附加4次,请使用 减法形式。
给定一个整数,将其转换为罗马数字。
示例 1:
输入:num = 3749
输出: “MMMDCCXLIX”
解释:
3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)
700 = DCC 由于 500 (D) + 100 (C) + 100 (C)
40 = XL 由于 50 (L) 减 10 (X)
9 = IX 由于 10 (X) 减 1 (I)
注意:49 不是 50 (L) 减 1 (I) 因为转换是基于小数位
示例 2:
输入:num = 58
输出:”LVIII”
解释:
50 = L
8 = VIII
示例 3:
输入:num = 1994
输出:”MCMXCIV”
解释:
1000 = M
900 = CM
90 = XC
4 = IV
1 | class Solution { |
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 | class Solution { |
6. Z 字形变换
将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时,排列如下:
1 | P A H N |
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:”PAHNAPLSIIGYIR”。
请你实现这个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);
示例 1:
输入:s = “PAYPALISHIRING”, numRows = 3
输出:”PAHNAPLSIIGYIR”
示例 2:
输入:s = “PAYPALISHIRING”, numRows = 4
输出:”PINALSIGYAHRPI”
解释:
1 | P I N |
示例 3:
输入:s = “A”, numRows = 1
输出:”A”
思路:
根据路径, 向下走,或者向上走,两个方向,判断边界即可
1 |
|
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 仅由小写英文字符组成
1 | class Solution { |
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 | class Solution { |
- 本文标题:Letcode刷题记录
- 本文作者:形而上
- 创建时间:2019-01-01 00:00:00
- 本文链接:https://deepter.gitee.io/2019_01_01_letcode/
- 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!