LeetCode題目精選
- 兩數(shù)之和
鏈接：https://leetcode-cn.com/problems/two-sum/
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target倡缠，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)腐芍，并返回他們的數(shù)組下標(biāo)则披。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素精偿。
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
題解：
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");
}
}
- 爬樓梯
鏈接：https://leetcode-cn.com/problems/climbing-stairs/
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階椰拒。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(shù)癞尚。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂耸三。
1. 1 階 + 1 階
2. 2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階
題解：
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];
}
}
- 翻轉(zhuǎn)二叉樹(shù)
鏈接：https://leetcode-cn.com/problems/invert-binary-tree/
翻轉(zhuǎn)一棵二叉樹(shù)浇揩。
示例：
輸入：
4
/ \
2 7
/ \ / \
1 3 6 9
輸出：
4
/ \
7 2
/ \ / \
9 6 3 1
題解：
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;
}
- 反轉(zhuǎn)鏈表
鏈接：https://leetcode-cn.com/problems/reverse-linked-list/
反轉(zhuǎn)一個(gè)單鏈表仪壮。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
題解：
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;
}
- LRU緩存機(jī)制
鏈接：https://leetcode-cn.com/problems/lru-cache/
運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU (最近最少使用) 緩存機(jī)制胳徽。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 积锅。
獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數(shù)）养盗，否則返回 -1缚陷。
寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在，則寫入其數(shù)據(jù)值往核。當(dāng)緩存容量達(dá)到上限時(shí)箫爷，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。
進(jìn)階:
你是否可以在 O(1) 時(shí)間復(fù)雜度內(nèi)完成這兩種操作虎锚？
示例:
LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 該操作會(huì)使得密鑰 2 作廢
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 該操作會(huì)使得密鑰 1 作廢
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
題解：
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 對(duì)象會(huì)以如下語(yǔ)句構(gòu)造和調(diào)用:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
- 最長(zhǎng)回文子串
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring/
給定一個(gè)字符串 s硫痰，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000窜护。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案效斑。
示例 2：
輸入: "cbbd"
輸出: "bb"
題解：
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;
}
- 有效的括號(hào)
鏈接：https://leetcode-cn.com/problems/valid-parentheses/
給定一個(gè)只包括 '('，')'柱徙，'{'缓屠，'}'，'['护侮，']' 的字符串敌完，判斷字符串是否有效。
有效字符串需滿足：- 左括號(hào)必須用相同類型的右括號(hào)閉合概行。
- 左括號(hào)必須以正確的順序閉合蠢挡。
注意空字符串可被認(rèn)為是有效字符串。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
題解：
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();
}
}
- 數(shù)組中的第K個(gè)最大元素
鏈接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
在未排序的數(shù)組中找到第 k 個(gè)最大的元素凳忙。請(qǐng)注意业踏，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素涧卵。
示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5
示例 2:
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4
說(shuō)明:
你可以假設(shè) k 總是有效的勤家，且 1 ≤ k ≤ 數(shù)組的長(zhǎng)度。
題解：
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);
}
}
- 實(shí)現(xiàn) Trie (前綴樹(shù))
實(shí)現(xiàn)一個(gè) Trie (前綴樹(shù))柳恐，包含 insert, search, 和 startsWith 這三個(gè)操作伐脖。
示例:
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
說(shuō)明:
- 你可以假設(shè)所有的輸入都是由小寫字母 a-z 構(gòu)成的。
- 保證所有輸入均為非空字符串乐设。
題解：
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();
}
}
- 編輯距離
鏈接：https://leetcode-cn.com/problems/edit-distance/
給定兩個(gè)單詞 word1 和 word2讼庇，計(jì)算出將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。
你可以對(duì)一個(gè)單詞進(jìn)行如下三種操作：- 插入一個(gè)字符
- 刪除一個(gè)字符
- 替換一個(gè)字符
示例 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')
題解：
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];
}
}
