LeetCode题解集合

LeetCode 48 Rotate Image(旋转图像)

翻译

给定一个$n * n$的2D矩阵表示一个图像。

顺时针旋转90度。

跟进:
你可以就地完成它吗?

原文

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

分析

尊重原创,一个很好的思路~

这里写图片描述

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void rotate(int[][] matrix) {
for (int i = 0; i < matrix.length / 2; i++) {
swapArray(matrix, i, matrix.length - i);
}
for (int i = 0; i < matrix.length; ++i) {
for (int j = i + 1; j < matrix[i].length; ++j) {
swapValue(matrix, i, j);
}
}
}
void swapArray(int[][] matrix, int a, int b) {
int[] tmp = matrix[a];
matrix[a] = matrix[b];
matrix[b] = tmp;
}
void swapValue(int[][] matrix, int i, int j) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}

LeetCode 234 Palindrome Linked List(回文链表)(*)

翻译

给定一个单链表,判断它是否是回文的。

跟进:
你可以只用O(n)的时间和O(1)的空间吗?

原文

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

分析

一种比较简单的做法,用stack来存储值,充分利用了栈的后进先出的特点进行对值的反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public boolean isPalindrome(ListNode head) {
Stack<Integer> original = new Stack<>();
int len = 0;
while (head != null) {
original.push(head.val);
head = head.next;
len++;
}
Stack<Integer> compare = new Stack<>();
for (int i = 0; i < len / 2; i++) {
compare.push(original.pop());
}
if (len % 2 != 0)
original.pop();
while (!original.empty()) {
int a = original.pop();
int b = compare.pop();
if (original.pop() != compare.pop())
return false;
}
return true;
}
}

除此之外,也可以直接对链表进行反转。

比如说对于 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1,反转后半部分,得到 1 -> 2 -> 3 -> 4 -> 1 -> 2 -> 3,然后直接逐个遍历比较即可。下面的代码中我已经附上了注释,就不多说了。

代码

Java

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
public class Solution {
public ListNode reverse(ListNode head) {
ListNode newHead = null;
while (head != null) {
ListNode tmp = head.next;
head.next = newHead;
newHead = head;
head = tmp;
}
return newHead;
}
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode snake = head;
int len = 0;
// 计算长度,用时为O(n)
while (snake != null) {
len++;
snake = snake.next;
}
snake = head; // 为了下一步的重新遍历
for (int i = 0; i < len / 2 - 1; i++) {
snake = snake.next;
}
// 对于1-2-3-4-4-3-2-1,此时snake到第一个4
// 对于1-2-3-2-1,此时snake到3
// 将后半部分进行反转,用时为O(n/2)
snake.next = reverse(snake.next);
ListNode snake2 = head;
snake = snake.next;
// 对未反转的前半部分和经过反转的后半部分进行逐个比较,用时为O(n/2)
for (int i = 0; i < len / 2; i++) {
if (snake2.val != snake.val) {
return false;
} else {
snake = snake.next;
snake2 = snake2.next;
}
}
return true;
}
}



年龄在18、智商在80以上,除非征得同意,本站所有文章严禁以任何形式转载。当然了,提前联系的话一般都是允许的……😶

本站地址:http://nomasp.com/,欢迎留言、邮件


坚持原创,坚持分享✊,想要请我吃包辣条吗?🍻