Letcode刷题记录
形而上 Lv5

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
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
42
43
package h.xd.algo;

public class Main39 {
public static void main(String[] args) {
new Solution39().merge(new int[]{1,2,3,0,0,0},3, new int[]{2,5,6},3);
}
}

class Solution39 {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int last = m+n-1;
for(;;){
if(m-1 < 0){
while(n-1 >=0){
nums1[last] = nums2[n-1];
n--;
last--;
}
return;
}
if(n-1 <0) {
while(m-1 >=0){
nums1[last] = nums1[m-1];
m--;
last--;
}
return;
}
if(nums1[m-1] > nums2[n-1]){
nums1[last] = nums1[m-1];
m--;
last--;
continue;
}else{
nums1[last] = nums2[n-1];
n--;
last--;
continue;
}

}
}
}
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
package algo

import "testing"

func TestAlgo1(t *testing.T) {
merge([]int{1, 2, 3, 0, 0, 0}, 3, []int{2, 5, 6}, 3)
}

func merge(nums1 []int, m int, nums2 []int, n int) {
last := m + n - 1
for {
if m-1 < 0 {
for n-1 >= 0 {
nums1[last] = nums2[n-1]
n--
last--
}
return
}
if n-1 < 0 {
for m-1 >= 0 {
nums1[last] = nums1[m-1]
m--
last--
}
return
}

if nums1[m-1] > nums2[n-1] {
nums1[last] = nums1[m-1]
m--
last--
} else {
nums1[last] = nums2[n-1]
n--
last--
}
}
}

注意点:

  1. 一个数组为空的判断是m-1 < 0 和 n-1<0 而不是 <=
  2. 一个驻足为空也要last–

27. 移除元素

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k,要通过此题,您需要执行以下操作:

更改 nums 数组,使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。
用户评测:

评测机将使用以下代码测试您的解决方案:

1
2
3
4
5
6
7
8
9
10
11
12
int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
// 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}

如果所有的断言都通过,你的解决方案将会 通过。

示例 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int removeElement(int[] nums, int val) {
int last = nums.length-1;
int start = 0;
for(int i=0;i<nums.length-1;i++){
if(i > last) break;
if(nums[i] == val){
int tmp = nums[i];
nums[i] = nums[last];
nums[last] = tmp;
last--;
i--;
}
}
return last +1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func removeElement(nums []int, val int) int {
start := 0
last := len(nums)-1
for {
if start > last {
break
}
if nums[start] == val {
nums[start],nums[last] = nums[last],nums[start]
last--
}else{
start++
}
}
return last+1
}

注意点:

  1. 不要忘了两指针交会 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
难点:

  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
    class 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;
    }
    }
    以下为时间复杂度N的解法,遍历一次,用多个存储变量记录状态并判断。
    需要记录总油,总花费,用来判断总油不够总花费,直接-1
    需要记录 result 为暂时起点,默认无暂时起点,为-1
    需要记录 curLast 为有暂时起点情况下, 暂时起点至目前总剩余油量

难点:

  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
    class 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
    42
    func 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
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
class Solution {
public int candy(int[] ratings) {
int[] left = new int[ratings.length];
int[] right = new int[ratings.length];

for(int i=0;i<ratings.length;i++){
if(i>0 && ratings[i] > ratings[i-1]){
left[i] = left[i-1] + 1;
}else{
left[i] = 1;
}
}
for(int i=ratings.length-1;i>=0;i--){
if(i < ratings.length-1 && ratings[i]>ratings[i+1]){
right[i] = right[i+1] + 1;
}else{
right[i] = 1;
}
}

int rst = 0;
for(int i=0;i<ratings.length;i++){
rst += (left[i] > right[i]? left[i]:right[i]);
}
return rst;
}
}

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
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
class Solution {
//3,3,3,3,3,3,3,3,2,2,2,1
//0,1,1,2,2,2,2,3,3,3,3,3
//0,1,0,2,1,0,1,3,2,1,2,1
//0,0,1,0,1,2,1,0,0,1,0,0
public int trap(int[] height) {
int[] left = new int[height.length];
int[] right = new int[height.length];
left[0] = height[0];
for(int i=1;i<height.length;i++){
left[i] = height[i] > left[i-1] ? height[i]:left[i-1];
}
right[height.length-1] = height[height.length-1];
for(int i=height.length-1-1;i>=0;i--){
right[i] = height[i] > right[i+1] ? height[i]:right[i+1];
}

int cost = 0;
for(int i=0;i<height.length;i++){
int min = left[i] < right[i] ? left[i]:right[i];
if (height[i] < min) {
cost = cost + min - height[i];
}
}
return cost;
}
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
//穷举 1到10 I II III VI V VI VII VIII IX X
//重点需要关注4 9 40 90 400 900,其他相加即可
public int romanToInt(String s) {
String str = s.replace("CM","900,").replace("CD","400,").replace("XC","90,")
.replace("XL","40,").replace("IX","9,").replace("IV","4,")
.replace("M","1000,").replace("D","500,").replace("C","100,")
.replace("L","50,").replace("X","10,").replace("V","5,").replace("I","1,");
String[] strArray = str.split(",");
int rst = 0;
for(int i=0;i<strArray.length;i++){
rst+=Integer.parseInt(strArray[i]);
}
return rst;
}
}

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
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public String intToRoman(int num) {
int t = num / 1000;
int to = num % 1000;
int h = to / 100;
int ho = to % 100;
int ten = ho / 10;
int teno = ho % 10;
String rst = "";
for (int i=0;i<t;i++){
rst += "M";
}
if(h == 9){
rst+="CM";
h-=9;
}
if (h >= 5) {
rst += "D";
h-=5;
}
if(h == 4){
rst+="CD";
h-=4;
}
for(int i=0;i<h;i++){
rst+="C";
}
if(ten == 9){
rst+="XC";
ten-=9;
}
if(ten >=5){
rst+="L";
ten-=5;
}
if(ten == 4){
rst+="XL";
ten-=4;
}
for(int i=0;i<ten;i++){
rst+="X";
}
if(teno ==9){
rst+="IX";
teno-=9;
}
if(teno >=5) {
rst+="V";
teno-=5;
}
if(teno == 4){
rst+="IV";
teno-=4;
}
for(int i=0;i< teno;i++){
rst+="I";
}
return rst;

}
}

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. 双指针法
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
class Solution {
public String reverseWords(String s) {
int all = s.length();
int last = all;
int start = all;
String str = "";
for(int i=all-1;i>=0;i--){
if(s.charAt(i) == ' ' && start==last){
last--;
start--;
}
if(s.charAt(i) == ' ' && start!=last){
str+=(" " +s.substring(start,last));
start =i;
last=i;
}
if(s.charAt(i) != ' '){
start--;
}
}
if(start !=last)
str+=(" " +s.substring(start,last));
return str.substring(1);
}
}

6. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时,排列如下:

1
2
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”
解释:

1
2
3
4
P     I    N
A L S I G
Y A H R
P I

示例 3:

输入:s = “A”, numRows = 1
输出:”A”

思路:
根据路径, 向下走,或者向上走,两个方向,判断边界即可

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
42
43
44
45
46
47
48
49
50

class Solution {
//00 02
//10 11
//20

//俩方向,向下,斜向上! 到边界就切换, 到数组结尾就结束,边界为行数3,列数小于等于 总数/行数
public String convert(String s, int numRows) {
if(numRows == 1) return s;
char[][] rst = new char[numRows][10000];
int a = 0;int b=0;
boolean isBottom = true;
for(int i = 0;i< s.length();i++){
if (isBottom) {
if(a<numRows){
rst[a][b] = s.charAt(i);
a++;
continue;
}else{
isBottom = false;
i--;
a--;
continue;
}
}
if(!isBottom){
if(a>0){
rst[a-1][b+1] = s.charAt(i);
a--;
b++;
continue;
}else{
isBottom = true;
i--;
a++;
continue;
}
}
}
String result = "";
for(int i=0; i< rst.length;i++){
for(int j=0;j<rst[0].length;j++){
if(rst[i][j] != '\0'){
result+=rst[i][j];
}
}
}
return result;
}
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int strStr(String haystack, String needle) {
for(int i=0;i<haystack.length();i++){
if(haystack.charAt(i) != needle.charAt(0)){
continue;
}
int start = i;
int j;
for(j=0;j<needle.length();j++){
if(start >= haystack.length()) break;
if(needle.charAt(j) != haystack.charAt(start)){
break;
}
start++;
}
if(j==needle.length())
return i;
}
return -1;
}
}

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. 比较无聊,边间很麻烦
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class Solution {
// this is an
// example of text
// justification.
public List<String> fullJustify(String[] words, int maxWidth) {
List<Line> ll = new ArrayList();
int count = 0;
List<String> tmp = new ArrayList();
for(int i=0;i<words.length;i++){
if(count == 0){
tmp = new ArrayList();
count+=words[i].length();
tmp.add(words[i]);
}else{
if(count + 1 + words[i].length() > maxWidth){
i--;
Line l = new Line();
l.w = tmp;
ll.add(l);
count=0;
}else if(count + 1 + words[i].length() == maxWidth){
tmp.add(words[i]);
Line l = new Line();
l.w = tmp;
ll.add(l);
count=0;
}else{
tmp.add(words[i]);
count = count + 1 + words[i].length();
}
}
}
if(count !=0){
Line l = new Line();
l.w = tmp;
ll.add(l);
}

List<String> rst = new ArrayList();
for(int i=0;i<ll.size()-1;i++){
Line l = ll.get(i);
int[] blk = getBlk(l,maxWidth);
List<String> s = l.w;
String ln = "";
for(int j=0;j<s.size();j++){
ln += s.get(j);
if(j < s.size()-1){
for(int k=0;k<blk[j];k++){
ln += " ";
}
}
if(blk.length == s.size()){
for(int k=0;k<blk[s.size()-1];k++){
ln += " ";
}
}

}
rst.add(ln);
}
Line lastLine = ll.get(ll.size()-1);
List<String> lastLineStr = lastLine.w;
String ln = "";
for(int i=0;i<lastLineStr.size();i++){
ln = ln + lastLineStr.get(i) + " ";
}
ln = ln.substring(0,ln.length()-1);
int blank = maxWidth - ln.length();
for(int i=0;i<blank;i++){
ln = ln + " ";
}
rst.add(ln);
return rst;
}

int[] getBlk(Line l, int maxWidth){
int se = l.w.size();
if(se == 1) return new int[]{maxWidth - l.w.get(0).length()};
int count = 0;
for(int i=0;i<se;i++){
count+=l.w.get(i).length();
}
int blk = maxWidth - count;
int f = blk / (se-1);
int e = blk % (se-1);
int[]rst= new int[se-1];
for(int i=0;i<rst.length;i++){
if(i< e){
rst[i] = f+1;
continue;
}
rst[i] = f;
}
return rst;
}
}

class Line{
List<String> w;
int[] blk;
}
  • 本文标题:Letcode刷题记录
  • 本文作者:形而上
  • 创建时间:2019-01-01 00:00:00
  • 本文链接:https://deepter.gitee.io/2019_01_01_letcode/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!