LeetCode过程中的记录和总结(做题的速度总赶不上出题的速度……

目录

  1. 前言
  2. LeetCode 1 Two Sum 两数之和
    1. 题目
    2. 代码
      1. Java
      2. Python
  3. LeetCode 48 Rotate Image(旋转图像)
    1. 翻译
    2. 原文
    3. 分析
    4. 代码
  4. LeetCode 234 Palindrome Linked List(回文链表)(*)
    1. 翻译
    2. 原文
    3. 分析
    4. 代码
      1. Java
  5. LeetCode 561 Array Partition I(数组拆分)
    1. 题目
    2. 分析
    3. 代码
      1. Java
    4. Python
  6. LeetCode 766 Toeplitz Matrix (托普利茨矩阵)
    1. 题目
    2. 分析
    3. 代码
      1. Java
      2. Python

前言

created on 05/06/2017

以后不再去CSDN更新LeetCode了,还是在自己个人站点玩耍吧~

updated on 04/22/2018

发现leetcode推出了中文版哎,赞!新开始,新征程!

LeetCode 1 Two Sum 两数之和

题目

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
* Brute Force,
* Time: O(n*n), Space: O(1)
* @param nums
* @param target
* @return
*/
public int[] twoSum_A(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[] {i, j};
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
/**
* Two-pass hash table
* Time: O(n), Space: O(n)
* @param nums
* @param target
* @return
*/
public int[] twoSum_B(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int diff = target - nums[i];
if (map.containsKey(diff) && map.get(diff) != i) {
return new int[] {i, map.get(diff)};
}
}
throw new IllegalArgumentException("No two sum solution");
}
/**
* One-pass hash table
* Time: O(n), Space: O(n)
* @param nums
* @param target
* @return
*/
public int[] twoSum_C(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] {map.get(complement), i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}

Python

1
2
3
4
5
6
7
def twoSum(self, nums, target):
complement = {}
for i in range(len(nums)):
if nums[i] in complement:
return [complement[nums[i]], i]
else:
complement[target - nums[i]] = i

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;
}
}

LeetCode 561 Array Partition I(数组拆分)

题目

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。
示例 1:

1
2
3
4
输入: [1,4,3,2]
输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).

提示:

1.    n 是正整数,范围在 [1, 10000].
2.    数组中的元素范围在 [-10000, 10000].

分析

排序后,取每两个中的第一个(最小),加起来就是最大的。没证明出来,只是自己举了几个例子,排序后再交换,发现结果确实是变小了。

代码

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* Created on 2018/04/22
* @param nums
* @return
*/
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length; i += 2) {
sum += nums[i];
}
return sum;
}

Python

1
2
3
4
5
6
7
# Created on 04/22/2018
def arrayPairSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return sum(sorted(nums)[::2])

LeetCode 766 Toeplitz Matrix (托普利茨矩阵)

题目

如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素,那么这个矩阵是托普利茨矩阵。
给定一个 M x N 的矩阵,当且仅当它是托普利茨矩阵时返回 True。
示例 1:

1
2
3
4
5
6
7
8
输入: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
输出: True
解释:
1234
5123
9512
在上面这个矩阵中, 对角线分别是 "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", 各条对角线上的所有元素都相同, 因此答案是True。
1
2
3
4
5
示例 2:
输入: matrix = [[1,2],[2,2]]
输出: False
解释:
对角线, 比如: "[1, 2]" 上有不同的元素。

注意:

1.     matrix (矩阵)是一个包含整数的二维数组。
2.    matrix 的行数和列数均在 [1, 20]范围内。
3.    matrix[i][j] 包含的整数在 [0, 99]范围内。

分析

最简单的方法,就是暴力求解了。

代码

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* Created on 04/22/2018
* Brust Force, Time: O(n*n), Space: 0
* @param matrix
* @return
*/
public boolean isToeplitzMatrix_A(int[][] matrix) {
for (int r = 0; r < matrix.length - 1; r++) {
for (int c = 0; c < matrix[0].length - 1; c++) {
if (matrix[r][c] != matrix[r+1][c+1])
return false;
}
}
return true;
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Created on 04/22/2018
def isToeplitzMatrix_A(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: bool
"""
for r in range(len(matrix) - 1):
for c in range(len(matrix[0]) - 1):
if matrix[r][c] != matrix[r+1][c+1]:
return False
return True
# Created on 04/22/2018
def isToeplitzMatrix_B(self, matrix):
return all(matrix[r][c] == matrix[r+1][c+1] for r in range(len(matrix) - 1) for c in range(len(matrix[0]) - 1))


本站地址:http://nomasp.com/

欢迎交流,转载请联系本人,多谢🙏