[toc]
第一题:数组问题
1007. 行相等的最少多米诺旋转 - 力扣（LeetCode）
很简单，搞3个统计数量的数组即可， 一个是去重后的总数，一个是A中各数字的总数，一个是B中各数字的总数
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
| class Solution {
public int minDominoRotations(int[] tops, int[] bottoms) {
int[] counts = new int[7];
int[] counts1 = new int[7];
int[] counts2 = new int[7];
for (int i = 0; i < tops.length;i++) {
if (tops[i] == bottoms[i]) {
counts[tops[i]]++;
} else {
counts[tops[i]]++;
counts[bottoms[i]]++;
}
counts1[tops[i]]++;
counts2[bottoms[i]]++;
}
int res = Integer.MAX_VALUE;
for (int i = 1; i<=6;i++) {
if (counts[i] == tops.length) {
int changeCount = Math.min(tops.length - counts1[i], tops.length - counts2[i]);
res = Math.min(res, changeCount);
}
}
if (res == Integer.MAX_VALUE) {
return -1;
} else {
return res;
}
}
}
|
第二题： 链表倒数第k个，用2个指针维护即可
1721. 交换链表中的节点 - 力扣（LeetCode）
求倒数第k个，那就是先走k步，然后再以起点为另一个指针，两边一起走，直到走到尾部即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public ListNode swapNodes(ListNode head, int k) {
ListNode newHead = new ListNode();
newHead.next = head;
ListNode node1 = head;
int count = k-1;
while(count-- > 0) {
node1 = node1.next;
}
ListNode node2 = newHead;
ListNode node = node1;
while(node != null) {
node = node.next;
node2 = node2.next;
}
int tmp = node1.val;
node1.val = node2.val;
node2.val = tmp;
return head;
}
}
|
第三题: 栈的验证
946. 验证栈序列 - 力扣（LeetCode）
数据结构很基础的题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stack = new LinkedList<>();
int i1 = 0, i2 = 0;
for( i2 = 0;i2 < popped.length;i2++) {
int pop = popped[i2];
if (!stack.isEmpty() && stack.peek() == pop) {
stack.pop();
continue;
}
while(i1 < pushed.length && pushed[i1] != pop) {
stack.push(pushed[i1]);
i1++;
}
if (i1 == pushed.length) {
return false;
}
i1++;
}
return true;
}
}
|