Lcof-I
👨🏻‍💻

Lcof-I

Created
May 18, 2021 11:37 AM
status
Published

03.数组中重复的数字

public class Solution {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) return nums[i];
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return -1;
    }
}

04.二维数组中的查找

public class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (matrix[i][j] == target) return true;
            if (matrix[i][j] < target) {
                j++;
                continue;
            }
            if (matrix[i][j] > target) {
                i--;
                continue;
            }
        }
        return false;
    }
}

06.从尾到头打印链表

class Solution {
    int index = 0;
    int[] result = null;

    public int[] reversePrint(ListNode head) {
        if (head == null) {
            result = new int[index];
            return result;
        } else {
            index++;
        }
        result = reversePrint(head.next);
        result[result.length - (index--)] = head.val;
        return result;
    }
}

07. 重建二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        int index = findIndex(preorder, inorder);
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, index + 1),
                Arrays.copyOfRange(inorder, 0, index));
        root.right = buildTree(Arrays.copyOfRange(preorder, index + 1, preorder.length),
                Arrays.copyOfRange(inorder, index + 1, inorder.length));
        return root;
    }

    public int findIndex(int[] preorder, int[] inorder) {
        int rootValue = preorder[0];
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootValue) return i;
        }
        return 0;
    }
}
public class Solution {
    HashMap<Integer, Integer> map = new HashMap<>();
    int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return recur(0, 0, inorder.length - 1);
    }

    public TreeNode recur(int pre_root, int in_left, int in_right) {
        if (in_left > in_right) return null;
        TreeNode root = new TreeNode(preorder[pre_root]);
        int index = map.get(preorder[pre_root]);
        root.left = recur(pre_root + 1, in_left, index - 1);
        root.right = recur(pre_root + (index - in_left) + 1, index + 1, in_right);
        return root;
    }
}

10- I. 斐波那契数列

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

11. 旋转数组的最小数字

public class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
}

12. 矩阵中的路径

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

    public boolean dfs(char[][] board, char[] words, int i, int j, int k) {
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[k]) return false;
        if (k == words.length - 1) return true;
        board[i][j] = '/';
        boolean result = (dfs(board, words, i + 1, j, k + 1) ||
                dfs(board, words, i - 1, j, k + 1) ||
                dfs(board, words, i, j + 1, k + 1) ||
                dfs(board, words, i, j - 1, k + 1));
        board[i][j] = words[k];
        return result;
    }
}

15. 二进制中1的个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int result = 0;
        while (n != 0) {
            n = n & (n - 1);
            result++;
        }
        return result;
    }
}

16. 数值的整数次方

class Solution {
    public double myPow(double x, int n) {
        if (x == 0) return 0;
        double result = 1;
        long b = n;
        if (b < 0) {
            x = 1 / x;
            b = -b;
        }
        while (b > 0) {
            if ((b & 1) == 1) result = result * x;
            x = x * x;
            b = b >> 1;
        }
        return result;
    }
}

17. 打印从1到最大的n位数

class Solution {
    public int[] printNumbers(int n) {
        int num = (int) Math.pow(10, n) - 1;
        int[] result = new int[num];
        for (int i = 0; i < result.length; i++) {
            result[i] = i + 1;
        }
        return result;
    }
}

18.删除链表的节点

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode pre = head, cur = head.next;
        if (pre.val == val) {
            return cur;
        }
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
                break;
            }
            pre = cur;
            cur = cur.next;
        }
        return head;
    }
}

21.调整数组顺序使奇数位于偶数前面

class Solution {
    public int[] exchange(int[] nums) {
        int mid = nums.length / 2;
        int left = 0, right = nums.length - 1;
        while (left < right) {
            if (nums[left] % 2 == 0 && nums[right] % 2 == 1) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
            if (nums[left] % 2 == 1) left++;
            if (nums[right] % 2 == 0) right--;
        }
        return nums;
    }
}

22.链表中倒数第k个节点

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast=head, slow = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

24.反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

25.合并两个排序的链表

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode temp = new ListNode(0);
        ListNode ans = temp;
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                temp.next = l2;
                return ans.next;
            }
            if (l2 == null) {
                temp.next = l1;
                return ans.next;
            }
            if (l1.val > l2.val) {
                temp.next = l2;
                temp = temp.next;
                l2 = l2.next;
            } else {
                temp.next = l1;
                temp = temp.next;
                l1 = l1.next;
            }
        }
        return ans.next;
    }
}

26.树的子结构

class Solution {
    private TreeNode B;

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (B == null) return false;
        this.B = B;
        return dfs(A);
    }

    private boolean dfs(TreeNode A) {
        if (A == null) {
            return false;
        }
        if (helper(A, B)) {
            return true;
        }
        return dfs(A.left) || dfs(A.right);
    }

    private boolean helper(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        }
        if (A == null || A.val != B.val) {
            return false;
        }
        return helper(A.left, B.left) && helper(A.right, B.right);
    }
}

27.二叉树的镜像

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode newRight = mirrorTree(root.left);
        TreeNode newLeft = mirrorTree(root.right);
        root.left = newLeft;
        root.right = newRight;
        return root;
    }
}

28.对称的二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        else return recur(root.left, root.right);
    }

    private boolean recur(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null || left.val != right.val) {
            return false;
        }
        return recur(left.right, right.left) && recur(left.left, right.right);
    }
}

31.栈的压入、弹出序列

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int popIndex = 0;
        Stack<Integer> stack = new Stack();
        for (int pushNum : pushed) {
            stack.push(pushNum);
            while (!stack.isEmpty() && popped[popIndex] == stack.peek()) {
                stack.pop();
                popIndex++;
            }
        }
        return stack.isEmpty();
    }
}

32 - I.从上到下打印二叉树

class Solution {
    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }
}

32 - II.从上到下打印二叉树 II

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            result.add(temp);
        }
        return result;
    }
}
💡
循环中的int i = queue.size(); i > 0; i-- 能有效的避免queue.size() 改变而导致的错误

33.二叉搜索树的后序遍历序列

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    private boolean recur(int[] postorder, int i, int j) {
        if (i >= j) {
            return true;
        }
        int p = i;
        while (postorder[p] < postorder[j]) {
            p++;
        }
        int m = p;
        while (postorder[p] > postorder[j]) {
            p++;
        }
        return (p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1));
    }
}

34.二叉树中和为某一值的路径

classSolution {
    LinkedList<List<Integer>> res =newLinkedList<>();
    LinkedList<Integer> path =newLinkedList<>();

publicList<List<Integer>> pathSum(TreeNode root,inttarget) {
        recur(root, target);
returnres;
    }

private voidrecur(TreeNode root,inttarget) {
if(root ==null)return;
        path.add(root.val);
        target -= root.val;
if(target == 0 && root.right ==null&& root.left ==null) {
            res.add(newLinkedList(path));
        }
        recur(root.left, target);
        recur(root.right, target);
        path.removeLast();
    }
}

35.复杂链表的复制

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node cur = head;
        HashMap<Node, Node> map = new HashMap<>();
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

39.数组中出现次数超过一半的数字

class Solution {
    public int majorityElement(int[] nums) {
        int result = 0, votes = 0;
        for (int num : nums) {
            if (votes == 0) result = num;
            if (num == result) votes++;
            else votes--;
        }
        return result;
    }
}

42.连续子数组的最大和

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

45.把数组排成最小的数

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < strs.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs, ((x, y) -> {
            String s1 = x + y, s2 = y + x;
            return s1.compareTo(s2);
        }));
        StringBuilder stringBuilder=new StringBuilder();
        for (String str : strs) {
            stringBuilder.append(str);
        }
        return stringBuilder.toString();
    }
}

47.礼物的最大价值

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

48.最长不含重复字符的子字符串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int left = -1, res = 0;
        for (int right = 0; right < s.length(); right++) {
            if (map.containsKey(s.charAt(right))) {
                left = Math.max(left, map.get(s.charAt(right)));
            }
            map.put(s.charAt(right), right);
            res = Math.max(res, right - left);
        }
        return res;
    }
}

50.第一个只出现一次的字符

class Solution {
    public char firstUniqChar(String s) {
        HashMap<Character, Boolean> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), !map.containsKey(s.charAt(i)));
        }
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i))) return s.charAt(i);
        }
        return ' ';
    }
}

52.两个链表的第一个公共节点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
}

53 - I.在排序数组中查找数字 I

class Solution {
    public int search(int[] nums, int target) {
        return findRight(nums, target) - findRight(nums, target - 1);
    }

    private int findRight(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}

53 - II. 0~n-1中缺失的数字

class Solution {
    public int missingNumber(int[] nums) {
        int i=0,j=nums.length-1;
        while (i<=j){
            int m=(i+j)/2;
            if(nums[m]!=m) j=m-1;
            else i=m+1;
        }
        return i;
    }
}

54.二叉搜索树的第k大节点

class Solution {
    int res, k;

    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }

    private void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.right);
        if (k == 0) return;
        if (--k == 0) res = root.val;
        dfs(root.left);
    }
}

55 - I.二叉树的深度

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

55 - II.平衡二叉树

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

Loading Comments...