0%

leetcode每日一题2

记录leetcode的每日一题2

406 根据身高重排队列

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
import java.util.*;

/*
* @lc app=leetcode.cn id=406 lang=java
*
* [406] 根据身高重建队列
*/
/**
* 先排序,后插入
* 1:按照H高度降序、K个数升序
* 2:根据k插到k的位置上
*
* 高个子先站位,矮个子再插入时不会影响高个子前面比他高的个数
*/
// @lc code=start
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);

LinkedList<int[]> list = new LinkedList<>();
for (int[] i : people){
list.add(i[1], i);
}
return list.toArray(new int[list.size()][2]);
}
}
// @lc code=end

402 移除k位数字

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
import java.util.*;
/*
* @lc app=leetcode.cn id=402 lang=java
*
* [402] 移掉K位数字
*/

/**
* 移掉k位数字等于:
* 1:移掉k-1位数字
* 2:移掉1位数字
*/
// @lc code=start
class Solution {
/**
* 给定一个长度为n的数字序列:从左往右找到第一个位置i使得num[i]<num[i-1]
* 删去num[i-1],如果不存在,说明数字序列单调不降,删去最后一个数即可。
*/
public String removeKdigits(String num, int k) {
Deque<Character> deque = new LinkedList<Character>();
int len = num.length();
for (int i = 0; i < len; i++) {
char digit = num.charAt(i);
while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
deque.pollLast();
k--;
}
deque.offerLast(digit);
}
for (int i = 0; i < k; i++) {
deque.pollLast();
}
StringBuilder ret = new StringBuilder();
boolean leadingZero = true;
while (!deque.isEmpty()) {
char digit = deque.pollFirst();
if (leadingZero && digit == '0'){
continue;
}
leadingZero = false;
ret.append(digit);
}
return ret.length() == 0 ? "0" : ret.toString();
}
}
// @lc code=end

[1030] 距离顺序排列矩阵单元格

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
import java.util.ArrayList;
import java.util.List;

/*
* @lc app=leetcode.cn id=1030 lang=java
*
* [1030] 距离顺序排列矩阵单元格
*/

// @lc code=start
class Solution {
public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
int maxDist = Math.max(r0, R - 1 - r0) + Math.max(c0, C - 1 - c0);
List<List<int[]>> bucket = new ArrayList<List<int[]>>();
//每个距离一个桶
for (int i = 0; i <= maxDist; i++){
bucket.add(new ArrayList<int[]>());
}

for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
int d = dist(i, j, r0, c0);
bucket.get(d).add(new int[]{i,j});
}
}

int[][] ret = new int[R * C][];
int index = 0;
for (int i = 0; i <= maxDist; i++) {
for (int[] it : bucket.get(i)) {
ret[index++] = it;
}
}
return ret;
}

public int dist (int r1, int c1, int r2, int c2) {
return Math.abs(r1 - r2) + Math.abs(c1 - c2);
}
}
// @lc code=end

134加油站

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
/*
* @lc app=leetcode.cn id=134 lang=java
*
* [134] 加油站
*/
/**
* 假设从x只能到加油站y,则从x,y之间的任意一个加油站出发都不能到达y。
* 算法思路:首先检查第0个加油站,并判断能不能围绕一周,
* 如果不能,就从第一个无法到达的加油站开始继续检查。
*/
// @lc code=start
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int i = 0;
while (i < n) {
int sumGas = 0, sumCost = 0, cnt = 0;
while (cnt < n) {
int j = (i + cnt) % n;
sumGas += gas[j];
sumCost += cost[j];
if(sumCost > sumGas){
break;
}
cnt++;
}
if(cnt == n) {
return i;
}else {
i = i + cnt + 1;
}
}
return -1;
}
}
// @lc code=end

147对链表进行插入排序

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
/*
* @lc app=leetcode.cn id=147 lang=java
*
* [147] 对链表进行插入排序
*/

// @lc code=start
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode lastSorted = head;
ListNode curr = head.next;
while (curr != null) {
if (lastSorted.val <= curr.val) {
lastSorted = lastSorted.next;
} else {
ListNode pre = dummy;
while (pre.next.val <= curr.val) {
pre = pre.next;
}
lastSorted.next = curr.next;
curr.next = pre.next;
pre.next = curr;
}
curr = lastSorted.next;
}
return dummy.next;
}
}
// @lc code=end
-------------本文结束感谢您的阅读-------------