7. LeetCode题目精选
7.1 两数之和
问题链接：https://leetcode-cn.com/problems/two-sum/
7.1.1 问题描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
```
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
```
7.1.2 参考答案
```java
class Solution {
public int[] twoSum(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");
}
}
```
7.2 爬楼梯
问题链接：https://leetcode-cn.com/problems/climbing-stairs/
7.2.1 问题描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
```
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
```
示例 2：
```
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
```
7.2.2 参考答案
```java
public class Solution {
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
```
7.3 翻转二叉树
链接：https://leetcode-cn.com/problems/invert-binary-tree/
7.3.1 问题描述
翻转一棵二叉树。
示例：
输入：
```
4
/ \
2 7
/ \ / \
1 3 6 9
```
输出：
```
4
/ \
7 2
/ \ / \
9 6 3 1
```
7.3.2 参考答案
```java
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode right = invertTree(root.right);
TreeNode left = invertTree(root.left);
root.left = right;
root.right = left;
return root;
}
```
7.4 反转链表
链接：https://leetcode-cn.com/problems/reverse-linked-list/
7.4.1 问题描述
反转一个单链表。
示例:
```
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
```
7.4.2 参考答案
```java
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
```
7.5 LRU缓存机制
链接：https://leetcode-cn.com/problems/lru-cache/
7.5.1 问题描述
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
```
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
```
7.5.2 参考答案
```java
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
/**
* LRUCache 对象会以如下语句构造和调用:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
```
7.6 最长回文子串
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/
7.6.1 问题描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
```
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
```
示例 2：
```
输入: "cbbd"
输出: "bb"
```
7.6.2 参考答案
```java
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}
```
7.7 有效的括号
链接：https://leetcode-cn.com/problems/valid-parentheses/
7.7.1 问题描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
```
输入: "()"
输出: true
```
示例 2:
```
输入: "()[]{}"
输出: true
```
示例 3:
```
输入: "(]"
输出: false
```
示例 4:
```
输入: "([)]"
输出: false
```
示例 5:
```
输入: "{[]}"
输出: true
```
7.7.2 参考答案
```java
class Solution {
// Hash table that takes care of the mappings.
private HashMap<Character, Character> mappings;
// Initialize hash map with mappings. This simply makes the code easier to read.
public Solution() {
this.mappings = new HashMap<Character, Character>();
this.mappings.put(')', '(');
this.mappings.put('}', '{');
this.mappings.put(']', '[');
}
public boolean isValid(String s) {
// Initialize a stack to be used in the algorithm.
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// If the current character is a closing bracket.
if (this.mappings.containsKey(c)) {
// Get the top element of the stack. If the stack is empty, set a dummy value of '#'
char topElement = stack.empty() ? '#' : stack.pop();
// If the mapping for this bracket doesn't match the stack's top element, return false.
if (topElement != this.mappings.get(c)) {
return false;
}
} else {
// If it was an opening bracket, push to the stack.
stack.push(c);
}
}
// If the stack still contains elements, then it is an invalid expression.
return stack.isEmpty();
}
}
```
7.8 数组中的第K个最大元素
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
7.8.1 问题描述
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
```
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
```
示例 2:
```
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
```
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
7.8.2 参考答案
```java
import java.util.Random;
class Solution {
int [] nums;
public void swap(int a, int b) {
int tmp = this.nums[a];
this.nums[a] = this.nums[b];
this.nums[b] = tmp;
}
public int partition(int left, int right, int pivot_index) {
int pivot = this.nums[pivot_index];
// 1. move pivot to end
swap(pivot_index, right);
int store_index = left;
// 2. move all smaller elements to the left
for (int i = left; i <= right; i++) {
if (this.nums[i] < pivot) {
swap(store_index, i);
store_index++;
}
}
// 3. move pivot to its final place
swap(store_index, right);
return store_index;
}
public int quickselect(int left, int right, int k_smallest) {
/*
Returns the k-th smallest element of list within left..right.
*/
if (left == right) // If the list contains only one element,
return this.nums[left]; // return that element
// select a random pivot_index
Random random_num = new Random();
int pivot_index = left + random_num.nextInt(right - left);
pivot_index = partition(left, right, pivot_index);
// the pivot is on (N - k)th smallest position
if (k_smallest == pivot_index)
return this.nums[k_smallest];
// go left side
else if (k_smallest < pivot_index)
return quickselect(left, pivot_index - 1, k_smallest);
// go right side
return quickselect(pivot_index + 1, right, k_smallest);
}
public int findKthLargest(int[] nums, int k) {
this.nums = nums;
int size = nums.length;
// kth largest is (N - k)th smallest
return quickselect(0, size - 1, size - k);
}
}
```
7.9 实现 Trie (前缀树)
7.9.1 问题描述
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
```
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
```
说明:
- 你可以假设所有的输入都是由小写字母 a-z 构成的。
- 保证所有输入均为非空字符串。
7.9.2 参考答案
```java
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char currentChar = word.charAt(i);
if (!node.containsKey(currentChar)) {
node.put(currentChar, new TrieNode());
}
node = node.get(currentChar);
}
node.setEnd();
}
// search a prefix or whole key in trie and
// returns the node where search ends
private TrieNode searchPrefix(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char curLetter = word.charAt(i);
if (node.containsKey(curLetter)) {
node = node.get(curLetter);
} else {
return null;
}
}
return node;
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd();
}
}
```
7.10 编辑距离
链接：https://leetcode-cn.com/problems/edit-distance/
7.10.1 问题描述
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
1. 插入一个字符
2. 删除一个字符
3. 替换一个字符
示例 1:
```
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
```
示例 2:
```
输入: word1 = "intention", word2 = "execution"
输出: 5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
```
7.10.2 参考答案
```java
class Solution {
public int minDistance(String word1, String word2) {
int n = word1.length();
int m = word2.length();
// if one of the strings is empty
if (n * m == 0)
return n + m;
// array to store the convertion history
int [][] d = new int[n + 1][m + 1];
// init boundaries
for (int i = 0; i < n + 1; i++) {
d[i][0] = i;
}
for (int j = 0; j < m + 1; j++) {
d[0][j] = j;
}
// DP compute
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
int left = d[i - 1][j] + 1;
int down = d[i][j - 1] + 1;
int left_down = d[i - 1][j - 1];
if (word1.charAt(i - 1) != word2.charAt(j - 1))
left_down += 1;
d[i][j] = Math.min(left, Math.min(down, left_down));
}
}
return d[n][m];
}
}
```
