Leetcode Hot100

1.两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }
}

2.两数相加

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int sum = 0, carry = 0;
        ListNode head = null, tail = null;
        while (l1 != null || l2 != null) {
            int n1 = l1 == null ? 0 : l1.val;
            int n2 = l2 == null ? 0 : l2.val;
            sum = n1 + n2 + carry;
            if (head == null) {
                head = new ListNode(sum % 10);
                tail = head;
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
            if (carry > 0) {
                tail.next = new ListNode(carry);
            }
        }
        return head;
    }
}

3.无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        int begin = 0, end = 0;
        int maxLen = 0;
        while (end < chars.length) {
            if (map.containsKey(chars[end]) && map.get(chars[end]) >= begin) {
                begin = map.get(chars[end]) + 1;
            }
            map.put(chars[end], end);
            end++;
            maxLen = Math.max(end - begin, maxLen);
        }
        return maxLen;
    }
}

4.寻找两个正序数组的中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        int size = 0;
        double result = 0;
        for (int num : nums1) {
            list.add(num);
        }
        for (int num : nums2) {
            list.add(num);
        }
        list.sort(Comparator.naturalOrder());
        size = list.size();
        result = size % 2 == 0 ? (list.get(size / 2) + list.get(size / 2 - 1)) / 2.0 : list.get(size / 2);
        return result;
    }
}

5.最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        int max = 1, begin = 0;
        boolean dp[][] = new boolean[s.length()][s.length()];
        char[] chars = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        for (int right = 1; right < chars.length; right++) {
            for (int left = 0; left < right; left++) {
                if (chars[left] != chars[right]){
                    dp[left][right] = false;
                }else{
                    //相等
                    if (right - left < 3) {
                        dp[left][right] = true;
                    } else {
                        dp[left][right] = dp[left + 1][right - 1];
                    }
                }
                if (dp[left][right] && max < (right - left + 1)) {
                    max = right - left + 1;
                    begin = left;
                }
            }
        }
        return s.substring(begin, begin + max);
    }
}

11.盛最多水的容器

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, result = 0;
        while (left < right) {
            int h = Math.min(height[left], height[right]);
            int area = h * (right - left);
            result = Math.max(result, area);
            if (height[left] > height[right]) {
                right--;
            } else {
                left++;
            }
        }
        return result;
    }
}

17.电话号码的字母组合

class Solution {
    List<String> res = new ArrayList<>();
    HashMap<Integer, String> map = new HashMap<>();

    public List<String> letterCombinations(String digits) {
        map.put(1, "");
        map.put(2, "abc");
        map.put(3, "def");
        map.put(4, "ghi");
        map.put(5, "jkl");
        map.put(6, "mno");
        map.put(7, "pqrs");
        map.put(8, "tuv");
        map.put(9, "wxyz");
        if (digits == null || digits.length() == 0) {
            return new ArrayList<>();
        }
        iterStr(digits, new StringBuilder(), 0);
        return res;
    }

    private void iterStr(String digits, StringBuilder stringBuilder, int index) {
        if (index == digits.length()) {
            res.add(stringBuilder.toString());
            return;
        }
        int pos = Integer.parseInt(String.valueOf(digits.charAt(index)));
        String temp = map.get(pos);
        for (int i = 0; i < temp.length(); i++) {
            stringBuilder.append(temp.charAt(i));
            iterStr(digits, stringBuilder, index + 1);
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
    }
}

19.删除链表的倒数第 N 个结点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode forward = pre, back = pre;
        for (int i = 0; i < n; i++) {
            forward = forward.next;
        }
        while (forward.next != null) {
            forward = forward.next;
            back = back.next;
        }
        back.next = back.next.next;
        return pre.next;
    }
}

20.有效的括号

class Solution {
    public boolean isValid(String s) {
        if (s.isEmpty()) return true;
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || c != stack.pop()) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

21.合并两个有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }
        if(l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

22.括号生成

class Solution {
    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        if (n == 0) return new ArrayList<>();
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("(");
        produce(n - 1, stringBuilder, n);
        return res;
    }

    private void produce(int left, StringBuilder stringBuilder, int right) {
        if (left == 0 && right == 0) {
            res.add(stringBuilder.toString());
            return;
        }
        if (left < 0 || right < 0) {
            return;
        }
        if (left > right) {
            return;
        }
        if(left>0){
            stringBuilder.append("(");
            produce(left-1,stringBuilder,right);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
        if(right>0){
            stringBuilder.append(")");
            produce(left,stringBuilder,right-1);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
    }
}

31.下一个排列

class Solution {
    public void nextPermutation(int[] nums) {
        int index = nums.length - 1;
        while (index - 1 >= 0 && nums[index] <= nums[index - 1]) {
            index--;
        }
        if (index == 0) {
            reverse(nums, index);
        } else {
            int temp = index;
            while (temp < nums.length - 1 && nums[temp + 1] > nums[index - 1]) {
                temp++;
            }
            swap(nums, temp, index - 1);
            reverse(nums, index);
        }
    }

    private void reverse(int[] nums, int index) {
        int i = index, j = nums.length - 1;
        while (i < j) {
            swap(nums, i++, j--);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

33.搜索旋转排序数组

class Solution {
    public int search(int[] nums, int target) {
        if (nums==null||nums.length == 0) return -1;
        if (nums.length == 1) return nums[0] == target ? 0 : -1;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            if (target >= nums[0]) {
                //target在左端  4567xxx
                if (nums[mid] < nums[0]) {
                    nums[mid] = Integer.MAX_VALUE;
                }
            } else {
                //target在右端  xxxx123
                if (nums[mid] >= nums[0]) {
                    nums[mid] = Integer.MIN_VALUE;
                }
            }
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

34.在排序数组中查找元素的第一个和最后一个位置

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (nums[left] != target) {
            return new int[]{-1, -1};
        }
        int l = left;
        right = nums.length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return new int[]{l, right};
    }
}

39.组合总和

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, target, res, new ArrayList<Integer>(), 0, 0);
        return res;
    }

    private void backtrack(int[] candidates, int target, List<List<Integer>> res, ArrayList<Integer> temp, int begin, int sum) {
        if (sum == target) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = begin; i < candidates.length; i++) {
            if (sum + candidates[i] <= target) {
                temp.add(candidates[i]);
                backtrack(candidates, target, res, temp, i, sum + candidates[i]);
                temp.remove(temp.size() - 1);
            } else {
                break;
            }
        }
    }
}

42.接雨水

class Solution {
    public int trap(int[] height) {
        int result = 0;
        if (height == null) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int temp = stack.pop();
                while (!stack.isEmpty() && height[stack.peek()] == height[temp]) {
                    stack.pop();
                }
                if (!stack.isEmpty()) {
                    int left = stack.peek();
                    result += (Math.min(height[i], height[left]) - height[temp]) * (i - left - 1);
                }
            }
            stack.push(i);
        }
        return result;
    }
}

49.字母异位词分组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

53.最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

55.跳跃游戏

public class Solution {
    public boolean canJump(int[] nums) {
        int des = nums.length - 1;
        int canReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i <= canReach) {
                canReach = Math.max(canReach, i + nums[i]);
                if (canReach >= des) {
                    return true;
                }
            }
        }
        return false;
    }
}

62.不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] road = new int[m][n];
        for (int i = 0; i < m; i++) {
            road[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
            road[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                road[i][j] = road[i - 1][j] + road[i][j - 1];
            }
        }
        return road[m - 1][n - 1];
    }
}

64.最小路径和

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0) return -1;
        for (int i = 1; i < grid.length; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int j = 1; j < grid[0].length; j++) {
            grid[0][j] += grid[0][j - 1];
        }
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length;j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

70.爬楼梯

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

75.颜色分类

class Solution {
    public void sortColors(int[] nums) {
        int zero = 0;
        int one = 0;
        int two = 0;
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int temp = nums[i];
            nums[two] = 2;
            two++;
            if (temp <= 1) {
                nums[one] = 1;
                one++;
            }
            if (temp == 0) {
                nums[zero] = 0;
                zero++;
            }
        }
    }
}

79.单词搜索

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board.length == 0) return false;
        char[] chars = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, i, j, chars, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, char[] chars, int begin) {
        if (begin >= chars.length) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
                || board[i][j] != chars[begin]) {
            return false;
        } else {
            char temp = board[i][j];
            board[i][j] = '/';
            try {
                return dfs(board, i + 1, j, chars, begin + 1) || dfs(board, i - 1, j, chars, begin + 1) ||
                        dfs(board, i, j + 1, chars, begin + 1) ||
                        dfs(board, i, j - 1, chars, begin + 1);
            } finally {
                board[i][j] = temp;
            }
        }
    }
}

102.二叉树的层序遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null) {
            return res;
        }
        deque.add(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                if (node.left != null) deque.add(node.left);
                if (node.right != null) deque.add(node.right);
                temp.add(node.val);
            }
            res.add(temp);
        }
        return res;
    }
}