中等五星
2. 两数相加
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
3. 无重复字符的最长子串
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
// 保证出现重复，但是可能比i小，例如abba
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128]; // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}
}
5. 最长回文子串
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;
}
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 2) {
return s;
}
int strLen = s.length();
int maxStart = 0; //最长回文串的起点
int maxEnd = 0; //最长回文串的终点
int maxLen = 1; //最长回文串的长度
boolean[][] dp = new boolean[strLen][strLen];
for (int r = 1; r < strLen; r++) {
for (int l = 0; l < r; l++) {
if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
dp[l][r] = true;
if (r - l + 1 > maxLen) {
maxLen = r - l + 1;
maxStart = l;
maxEnd = r;
}
}
}
}
return s.substring(maxStart, maxEnd + 1);
}
}
15. 三数之和
class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList();
int len = nums.length;
if(nums == null || len < 3) return ans;
Arrays.sort(nums); // 排序
for (int i = 0; i < len ; i++) {
if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
int L = i+1;
int R = len-1;
while(L < R){
int sum = nums[i] + nums[L] + nums[R];
if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
while (L<R && nums[L] == nums[L+1]) L++; // 去重
while (L<R && nums[R] == nums[R-1]) R--; // 去重
L++;
R--;
}
else if (sum < 0) L++;
else if (sum > 0) R--;
}
}
return ans;
}
}
11. 盛最多水的容器
public class Solution {
public int maxArea(int[] height) {
int l = 0, r = height.length - 1;
int ans = 0;
while (l < r) {
int area = Math.min(height[l], height[r]) * (r - l);
ans = Math.max(ans, area);
if (height[l] <= height[r]) {
++l;
}
else {
--r;
}
}
return ans;
}
}
146. LRU缓存机制
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;
}
}
import java.util.Hashtable;
public class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
}
private void addNode(DLinkedNode node) {
/**
* Always add the new node right after head.
*/
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node){
/**
* Remove an existing node from the linked list.
*/
DLinkedNode prev = node.prev;
DLinkedNode next = node.next;
prev.next = next;
next.prev = prev;
}
private void moveToHead(DLinkedNode node){
/**
* Move certain node in between to the head.
*/
removeNode(node);
addNode(node);
}
private DLinkedNode popTail() {
/**
* Pop the current tail.
*/
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
private Hashtable<Integer, DLinkedNode> cache =
new Hashtable<Integer, DLinkedNode>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
// head.prev = null;
tail = new DLinkedNode();
// tail.next = null;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) return -1;
// move the accessed node to the head;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if(node == null) {
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
cache.put(key, newNode);
addNode(newNode);
++size;
if(size > capacity) {
// pop the tail
DLinkedNode tail = popTail();
cache.remove(tail.key);
--size;
}
} else {
// update the value.
node.value = value;
moveToHead(node);
}
}
}
/**
* LRUCache 对象会以如下语句构造和调用:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
33. 搜索旋转排序数组
class Solution {
public int search(int[] nums, int target) {
if(nums==null || nums.length==0){
return -1;
}
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right-left)/2;
if(nums[left]==target){
return left;
}
if(nums[mid]==target){
return mid;
}
if(nums[right]==target){
return right;
}
// 左边有序
if(nums[left]<nums[mid]){
// 在(左，中)范围内
if(target>nums[left]&&target<nums[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
}// 右边有序
else{
// 在(中，右)范围内
if(target>nums[mid]&&target<nums[right]){
left = mid + 1;
}else{
right = mid - 1;
}
}
}
return -1;
}
}
56. 合并区间
class Solution {
public int[][] merge(int[][] intervals) {
List<Interval> intervalList = new ArrayList<>();
for(int[] interval : intervals){
intervalList.add(new Interval(interval[0],interval[1]));
}
Collections.sort(intervalList,new IntervalComparator());
LinkedList<Interval> mergeList = new LinkedList<>();
for(Interval i : intervalList){
if(mergeList.isEmpty() || mergeList.getLast().end < i.start){
mergeList.add(i);
}else{
mergeList.getLast().end = Math.max(mergeList.getLast().end,i.end);
}
}
int size = mergeList.size();
int[][] result = new int[size][2];
for(int i=0;i<size;i++){
result[i] = new int[]{mergeList.get(i).start,mergeList.get(i).end};
}
return result;
}
class Interval{
public int start;
public int end;
public Interval(int start, int end){
this.start = start;
this.end = end;
}
}
private class IntervalComparator implements Comparator<Interval>{
@Override
public int compare(Interval a,Interval b){
return a.start < b.start ? -1 : a.start == b.start ? 0 : 1;
}
}
}
784. 字母大小写全排列
46. 全排列
class Solution {
public void backtrack(int n,
ArrayList<Integer> nums,
List<List<Integer>> output,
int first) {
// if all integers are used up
if (first == n)
output.add(new ArrayList<Integer>(nums));
for (int i = first; i < n; i++) {
// place i-th integer first
// in the current permutation
Collections.swap(nums, first, i);
// use next integers to complete the permutations
backtrack(n, nums, output, first + 1);
// backtrack
Collections.swap(nums, first, i);
}
}
public List<List<Integer>> permute(int[] nums) {
// init output list
List<List<Integer>> output = new LinkedList();
// convert nums into list since the output is a list of lists
ArrayList<Integer> nums_lst = new ArrayList<Integer>();
for (int num : nums)
nums_lst.add(num);
int n = nums.length;
backtrack(n, nums_lst, output, 0);
return output;
}
}
215. 数组中的第K个最大元素
class Solution {
public int findKthLargest(int[] nums, int k) {
// init heap 'the smallest element first'
PriorityQueue<Integer> heap =
new PriorityQueue<Integer>((n1, n2) -> n1 - n2);
// keep k largest elements in the heap
for (int n: nums) {
heap.add(n);
if (heap.size() > k)
heap.poll();
}
// output
return heap.poll();
}
}
200. 岛屿数量
class Solution {
void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
}
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0';
Queue<Pair<Integer,Integer>> neighbors = new LinkedList<>();
neighbors.add(new Pair(r,c));
while (!neighbors.isEmpty()) {
Pair<Integer,Integer> id = neighbors.poll();
int row = id.getKey();
int col = id.getValue();
if (row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.add(new Pair(row-1,col));
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
neighbors.add(new Pair(row+1,col));
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.add(new Pair(row,col-1));
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
neighbors.add(new Pair(row,col+1));
grid[row][col+1] = '0';
}
}
}
}
}
[https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/](https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/)
return num_islands;
}
}
93. 复原IP地址
class Solution {
public static List<String> restoreIpAddresses(String s) {
List<String> ans = new ArrayList<>();
Deque<String> path = new LinkedList<>();
dfs(s, 0, 0, path, ans);
return ans;
}
// start开始的位置,count剩余的个数
public static void dfs(String s, int start, int count, Deque<String> path, List<String> ans) {
if (start == s.length() && count == 4) {
ans.add(String.join(".", path));
return;
}
for (int a = start; a < start + 3; a++) {
if (a >= s.length()) {
break;
}
// 开始位置+1是个数，因为start~a直接算一个，因此是3-count
if (a+1 + (3 - count) * 3 < s.length()) {
continue;
}
if (judgeSegment(s, start, a)) {
path.addLast(s.substring(start, a + 1));
dfs(s, a + 1, count + 1, path, ans);
path.removeLast();
}
}
}
private static boolean judgeSegment(String s, int left, int right) {
int len = right - left + 1;
if (len > 1 && s.charAt(left) == '0') {
return false;
}
int value = Integer.parseInt(s.substring(left, right + 1));
return value >= 0 && value <= 255;
}
}
19. 删除链表的倒数第N个节点
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Advances first pointer so that the gap between first and second is n nodes apart
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
// Move first to the end, maintaining the gap
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
22. 括号生成
https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/
199. 二叉树的右视图
class Solution {
public List<Integer> rightSideView(TreeNode root) {
Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
int max_depth = -1;
Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
Queue<Integer> depthQueue = new LinkedList<Integer>();
nodeQueue.add(root);
depthQueue.add(0);
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.remove();
int depth = depthQueue.remove();
if (node != null) {
// 维护二叉树的最大深度
max_depth = Math.max(max_depth, depth);
// 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
rightmostValueAtDepth.put(depth, node.val);
nodeQueue.add(node.left);
nodeQueue.add(node.right);
depthQueue.add(depth+1);
depthQueue.add(depth+1);
}
}
List<Integer> rightView = new ArrayList<Integer>(rightmostValueAtDepth.values());
return rightView;
}
}
31. 下一个排列
public class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i + 1] <= nums[i]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
private void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
322. 零钱兑换
class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
int min = max;
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i && dp[i-coins[j]]<min) {
min = dp[i-coins[j]];
}
}
dp[i] = min+1;
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
54. 螺旋矩阵
class Solution {
public List < Integer > spiralOrder(int[][] matrix) {
List ans = new ArrayList();
if (matrix.length == 0)
return ans;
int r1 = 0, r2 = matrix.length - 1;
int c1 = 0, c2 = matrix[0].length - 1;
while (r1 <= r2 && c1 <= c2) {
for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
if (r1 < r2 && c1 < c2) {
for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
}
r1++;
r2--;
c1++;
c2--;
}
return ans;
}
}
102. 二叉树的层序遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if(root==null){
return ans;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<>();
for(int i=0;i<size;i++){
TreeNode tree = queue.poll();
list.add(tree.val);
if(tree.left!=null){
queue.offer(tree.left);
}
if(tree.right!=null){
queue.offer(tree.right);
}
}
ans.add(list);
}
return ans;
}
}
class Solution {
List<List<Integer>> levels = new ArrayList<List<Integer>>();
public void helper(TreeNode node, int level) {
// start the current level
if (levels.size() == level)
levels.add(new ArrayList<Integer>());
// fulfil the current level
levels.get(level).add(node.val);
// process child nodes for the next level
if (node.left != null)
helper(node.left, level + 1);
if (node.right != null)
helper(node.right, level + 1);
}
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) return levels;
helper(root, 0);
return levels;
}
}
94. 二叉树的中序遍历
public class Solution {
public List < Integer > inorderTraversal(TreeNode root) {
List < Integer > res = new ArrayList < > ();
Stack < TreeNode > stack = new Stack < > ();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
}
103. 二叉树的锯齿形层次遍历
{
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean reverse = true;
while (!queue.isEmpty()) {
int size = queue.size();
LinkedList<Integer> tmp = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode tree = queue.poll();
if (tree.left != null) {
queue.add(tree.left);
}
if (tree.right != null) {
queue.add(tree.right);
}
if (reverse) {
tmp.addLast(tree.val);
} else {
tmp.addFirst(tree.val);
}
}
ans.add(tmp);
reverse = !reverse;
}
return ans;
}
445. 两数相加 II
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<ListNode> stack1 = new Stack();
Stack<ListNode> stack2 = new Stack();
while(l1!=null){
stack1.push(l1);
l1=l1.next;
}
while(l2!=null){
stack2.push(l2);
l2=l2.next;
}
ListNode ans = null;
int carry = 0;
while(!stack1.isEmpty()||!stack2.isEmpty()){
int v1 = stack1.isEmpty()?0:stack1.pop().val;
int v2 = stack2.isEmpty()?0: stack2.pop().val;
int sum = v1+v2+carry;
carry = sum/10;
ListNode tmp = new ListNode(sum%10);
tmp.next = ans;
ans = tmp;
}
if(carry!=0){
ListNode c = new ListNode(carry);
c.next = ans;
ans = c;
}
return ans;
}
}
92. 反转链表 II
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// Empty list
if (head == null) {
return null;
}
// Move the two pointers until they reach the proper starting point
// in the list.
ListNode cur = head, prev = null;
while (m > 1) {
prev = cur;
cur = cur.next;
m--;
n--;
}
// The two pointers that will fix the final connections.
ListNode con = prev, tail = cur;
// Iteratively reverse the nodes until n becomes 0.
ListNode third = null;
while (n > 0) {
third = cur.next;
cur.next = prev;
prev = cur;
cur = third;
n--;
}
// Adjust the final connections as explained in the algorithm
if (con != null) {
con.next = prev;
} else {
head = prev;
}
tail.next = cur;
return head;
}
}
