1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
    public int strToInt(String str) {
        if (str == null || str.length() == 0){
            return 0;
        }
        
        int i = 0;
        int n = str.length();
        long res = 0;
        char[] charArray = str.toCharArray();
        int sign = 1;

        //去除空格
        while (i < n && charArray[i] == ' '){
            i++;
        }
        
        //首先需要判断下标是否会越过数组长度
        //判断符号位是否存在，存在的话是什么,这里不用循环，就可以避免“+++”、“+-+”这种情况
        if (i < n && (charArray[i] == '+' || charArray[i] == '-')) {
            sign = (charArray[i] == '-') ? -1 : 1;
            i++;
        }
        
        //判断数字位，并且在添加下一个数之前判断是否溢出
        while (i < n && Character.isDigit(charArray[i])){
            //res*10之后可能会越界导致数据溢出，造成结果不准确，所以一开始的res要用long类型
            long tmp = res * 10 + charArray[i] - '0';
            //判断是否会越界
            //这里要带上符号位来比较大小
            if (tmp * sign > Integer.MAX_VALUE){
                return Integer.MAX_VALUE;
            }else if (tmp * sign < Integer.MIN_VALUE){
                return Integer.MIN_VALUE;
            }
            //这里先不急着赋予符号位，因为给了符号之后就不好使用res * 10 + charArray[i] - '0'来得到下一个数了。所以res在函数结尾return的时候才带上符号位
            res = tmp;
            i++;
        }

        //带上符号位
        return (int)res*sign;
       
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public Node copyRandomList(Node head) {
        //这里判断条件不能有head.next==null，否则会导致下面对应的value节点不能正常生成
        if (head == null) {
            return head;
        }

        Map<Node, Node> nodeMap = new HashMap<>();

        Node p = head;
        //第一次遍历：复制节点值建立新节点，利用map映射使得新节点顺序和旧节点顺序一致，
        while (p != null){
            Node newNode = new Node(p.val);
            nodeMap.put(p, newNode);
            p = p.next;
        }

        p = head;
        //第二次遍历: 建立新结点之间的关系,即：建立新节点的 next 和 random 指针
        while (p != null){
            //使用p作为旧链表的指针, 把p当成旧节点，这样我们就可以不通过map的key来知道旧节点的next和value了
            Node newNode = nodeMap.get(p);
            newNode.next = nodeMap.get(p.next);
            newNode.random = nodeMap.get(p.random);
            p = p.next;
        }
        return nodeMap.get(head);  // 返回新链表的头节点
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public ListNode deleteNode(ListNode head, int val) {
    if (head == null) {
        return head;
    }

    ListNode dummy = new ListNode(-1);
    ListNode pre = dummy;
    pre.next = head;
    ListNode cur = dummy.next;

    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
            return dummy.next;
        }

        cur = cur.next;
        pre = pre.next;
    }

    return dummy.next;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == headB) return headA;
    if (headA == null || headB == null){
        return null;
    }

    ListNode pA = headA;
    ListNode pB = headB;

    while (pA != pB) {
        pB = pB.next;
        pA = pA.next;

        if (pA == pB) return pA;

        if (pA == null) {
            pA = headB;
        }

        if (pB == null) {
            pB = headA;
        }

    }
    return pA;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public String reverseWords(String s) {
        //删除前后的空格部分
        s = s.trim();

        List<String> list = new ArrayList<>();
        StringBuilder stringBuilder = new StringBuilder();
        char[] charArray = s.toCharArray();
        //开始读取单词部分
        for (int i = 0; i < charArray.length; i++) {
            if (charArray[i] == ' ') {
                //说明不存在空格或SB不是空字符串，是我们想要的要的SB
                String curStr = stringBuilder.toString();
                //改成 if (curStr != "") 也可以通过测试
                if (curStr != " " && curStr != "") {
                    list.add(curStr);
                    stringBuilder.delete(0, stringBuilder.length());
                }
            }else {
                stringBuilder.append(charArray[i]);
            }
        }
        if (stringBuilder.indexOf(" ") == -1) {
            list.add(stringBuilder.toString());
            stringBuilder.delete(0, stringBuilder.length());
        }

        for (int i = list.size() - 1; i >= 0; i--) {
            stringBuilder.append(list.get(i) + " ");
        }

        return stringBuilder.delete(stringBuilder.length() - 1, stringBuilder.length()).toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public String reverseWords(String s) {

            /*
            "the        sky         is         blue"
            字符区[空白区]字符区[空白区]字符区[空白区]字符区
             */

            int left = s.length() - 1;
            int right = left + 1;
            StringBuilder sb = new StringBuilder();
            //trim保证了left指针一开始就是在字符区
            s = s.trim();
            while (left >= 0) {
                //先让left指针移动到空白区，使得left和right能包裹住这片字符
                //只要移动了left，一定要保证不会越界，当left走到第一个位置的时候，还会执行left--，这就会导致越界
                while (left >= 0 && s.charAt(left) != ' '){
                    left--;
                }

                //情况一：此时left走到了空白区的最后一个位置, 我们把字符区给截取下来
                //情况二：此时left为-1，越界，我们也可以截取下来
                sb.append(s.substring(left+1, right));
                sb.append(" ");

                //接下来让left指针走出空白区
                while (left >= 0 && s.charAt(left) == ' ') {
                    left--;
                }

                //现在left指针走到了字符区，修改right指针的位置，重复循环
                right = left + 1;
            }
            
            return sb.toString().trim();
        }

1
2
3
4
5
6

if (min.size() != 0){
    int tmp = min.peekLast();
    min.addLast(tmp >= x ? x : tmp);
}else {
    min.addLast(x);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class MinStack {
    Deque<Integer> deque;
    Deque<Integer> min;

    /** initialize your data structure here. */
    public MinStack() {
        deque = new ArrayDeque();
        min = new ArrayDeque();
    }
    
    public void push(int x) {
        deque.addLast(x);
        if (min.size() == 0 || min.peekLast() >= x){
            min.addLast(x);
        }
    }
    
    public void pop() {
        int x = deque.pollLast();
        if (x == min.peekLast()) {
            min.pollLast();
        }
    }
    
    public int top() {
        return deque.peekLast();
    }
    
    public int min() {
        return min.peekLast();
    }
}

1
2
3
4
5
6
7
8

    //添加大于队列中的元素到max队列中，这里的逻辑有问题，如果总是添加了大的到最前面，那么无法判定是否第一个是最大的
//所以这里的思路是有问题的
public void push_back(int value) {
    deque.addLast(value);
    if (max.size() == 0 || max.peekLast() <= value) {
        max.addFirst(value);
    }
}

1
2
3
4
5
6
7

public void push_back(int value) {
    deque.addLast(value);
    while (!max.isEmpty() && max.peekLast() < value){
        max.pollLast();
    }
    max.addLast(value);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class MaxQueue {
    Deque<Integer> deque;
    Deque<Integer> max;
    public MaxQueue() {
        deque = new ArrayDeque<>();
        max = new ArrayDeque<>();
    }
    
    public int max_value() {
        return max.size() == 0 ? -1 : max.peekFirst();
    }
    
    public void push_back(int value) {
        deque.addLast(value);
        //要保留能和value相等的元素，所以判断条件里面不能写等于
        while (!max.isEmpty() && max.peekLast() < value){
            max.pollLast();
        }
        max.addLast(value);
    }
    
    public int pop_front() {
        if (deque.size() == 0) return -1;
        
        int res = deque.pollFirst();
        if (res == max.peekFirst()) {
            max.pollFirst();
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        int rowCount = matrix.length;
        if (matrix == null || rowCount == 0) return new int[]{};
        int columnCount = matrix[0].length;

        int left = 0, right = columnCount - 1, top = 0, buttom = rowCount - 1;
        int[] res = new int[rowCount * columnCount];
        int index = 0;
        while (left <= right && top <= buttom){
            //从左到右
            for (int i = left; i <= right; i++) {
                res[index++] = matrix[top][i];
            }
            top++;

            //从上往下
            for (int i = top; i <= buttom; i++) {
                res[index++] = matrix[i][right];
            }
            right--;

            //从右往左
            if (top <= buttom){
                for (int i = right; i >= left; i--) {
                    res[index++] = matrix[buttom][i];
                }
                buttom--;
            }

            //从下往上
            if (left <= right){
                for (int i = buttom; i >= top; i--) {
                    res[index++] = matrix[i][left];
                }
                left++;
            }
        }
        
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {

        Deque<Integer> stack = new ArrayDeque<>();
        int pushIndex = 0;
        for (int curPop : popped) {
            //条件应该是栈为空时必成成立，栈顶元素和当前遍历元素不相等时必成立
            while (stack.isEmpty() || stack.peekLast() != curPop) {
                if (pushIndex >= pushed.length) {
                    return false;
                }
                stack.addLast(pushed[pushIndex]);
                pushIndex++;
            }

            //此时栈不为空且栈顶元素和当前遍历的值相等，那么弹出栈顶元素，让下标移动；
            stack.pollLast();
            //由于在循环中，进行了下标自增之后才判断栈顶元素是否和遍历元素是否相等，所以pushindex比栈顶元素在push数组中的位置更靠后，此处就不需要在自增了
            //pushIndex++;

        }

        return stack.isEmpty();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int rowCount = matrix.length;
        if (matrix == null || rowCount == 0){
            return false;
        }
        int columnCount = matrix[0].length;
        int row = 0; // 指针row指向第一行
        int column = columnCount - 1; // 指针col指向最后一列
        while (row < rowCount && column >= 0){
            if (matrix[row][column] == target) {
                return true;
            }else if (matrix[row][column] > target) {
                //说明下面的行只会更大，那么我们后面只会在这一行不断地缩小column就能找到答案
                column--;
            }else {
                //说明我们需要走到下一行更大的数字中去
                row++;
            }
        }
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public char firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return ' ';
        }
        int[] arr = new int[26];
        Arrays.fill(arr, 0);
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            arr[ch - 'a']++;
        }
        for (char ch : chars) {
            if (arr[ch - 'a'] == 1) {
                return ch;
            }
        }
        return ' ';
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Deque<TreeNode> nodes = new ArrayDeque<>();
        Deque<Integer> resSubList = new ArrayDeque<>();
        List<List<Integer>> res = new ArrayList<>();
        nodes.add(root);
        int level = 1;
        while (!nodes.isEmpty()){
            int size = nodes.size();
            for (int i = 0; i < size; i++) {
                TreeNode tempNode = nodes.pollFirst();
                if (tempNode.left != null ) {
                    nodes.add(tempNode.left);
                }
                if (tempNode.right != null) {
                    nodes.add(tempNode.right);
                }
                //奇数层，按顺序加入
                if (level % 2 == 1) {
                    resSubList.addLast(tempNode.val);
                }else {
                    resSubList.addFirst(tempNode.val);
                }
            }
            res.add(new ArrayList<>(resSubList));
            resSubList.clear();
            level++;
        }

        return res;
    }
}

1
2
3

题目：输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //自己调用自己时的终止条件或直接判断题目的输入参数是否满足要求
        if (A == null || B == null){
            return false;
        }
        return isSameStruct(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    private boolean isSameStruct(TreeNode A, TreeNode B) {

        //自己调用自己时的终止条件
        if (B == null) {
            return true;
        }
        //自己调用自己时的终止条件
        if(A == null || A.val != B.val) {
            return false;
        }
        return isSameStruct(A.left, B.left) && isSameStruct(A.right, B.right);
    }

}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return root;

        TreeNode tmp = root.left;
        //把整理好的镜像右子树直接赋给左子树
        root.left = mirrorTree(root.right);

        //把整理好的暂存镜像左子树直接赋给右子树
        root.right = mirrorTree(tmp);

        return root;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

    private boolean recur(TreeNode left, TreeNode right) {
        if (left == null && right != null) return false;

        if (left != null && right == null) return false;

        if (left == null && right == null) return true;

        if (left.val != right.val) return false;

        return recur(left.left, right.right) && recur(left.right, right.left);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) return false;

        int maxRow = board.length;
        int maxColumn = board[0].length;
        boolean[][] visited = new boolean[maxRow][maxColumn];

        for (int i = 0; i < maxRow; i++) {
            for (int j = 0; j < maxColumn; j++) {
                if (dfs(board, i, j, 0, word, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, int wordIndex, String word, boolean[][] visited) {
        //每次递归调用 dfs 时，index 参数表示当前正在匹配的 word 中的字符索引。
      //如果能使得这一步的判断条件为true，那么表示前面的都已经匹配了，现在是最后一步
      //当 index 的值等于 word.length() 时，说明已经匹配完整个 word 字符串，找到了符合条件的路径，可以返回 true。
        if (wordIndex == word.length()) return true;
    
    
        //这里是递归终止的第二种情况：失败
      //如果当前的下标越界、当前字符不相等，那么就可以停止这一条路径的遍历
      //如果当前位置已经被访问过，那么说明其他路径已经把这一个位置走了，我这条路径的下一步就不用走这个位置了
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(wordIndex) ||
        visited[i][j]) {
            return false;
        }
    
        //没越界、字符相等、这个位置没被其他路径访问过，那么我就得把这个路径给标记成已访问
        visited[i][j] = true;
    
        if (dfs(board, i+1, j, wordIndex+1, word, visited) ||
            dfs(board, i, j+1, wordIndex+1, word, visited) ||
            dfs(board, i-1, j, wordIndex+1, word, visited) ||
            dfs(board, i, j-1, wordIndex+1, word, visited)) {
            return true;
        }
    
        //我这条路径已经走完了，并且保证以指定初始起点开始遍历，没法得到正确结果，所以我应该把visited数组中对应的位置标记为false
        //这样，当初始起点不同的时候，别的起点才能正常遍历他们自己的路径
        //同时，也可以保证走到我这一步的起点的其他路径能正常访问
        visited[i][j] = false;
    
        return false;
    }
  }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
    int res = 0;
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        dfs(0, 0, m, n, k, visited);
        return res;
    }

    private void dfs(int row, int column, int m, int n, int k, boolean[][] visited) {
        //计算数位和
        int count = 0;
        int tempRow = row;
        while (tempRow != 0){
            count = count + tempRow % 10;
            tempRow /= 10;
        }
        int tempColumn = column;
        while (tempColumn != 0){
            count = count + tempColumn % 10;
            tempColumn /= 10;
        }

        //递归终止条件
        if (row < 0 || row >= m || column < 0 || column >= n || count > k || visited[row][column]){
            return;
        }

        //标记当前单元格已走过
        visited[row][column] = true;
		//能走的单元格数量+1
        res++;

        //走下一个格子
        dfs(row+1, column, m, n, k, visited);
        dfs(row - 1, column, m, n, k, visited);
        dfs(row, column+1, m, n, k, visited);
        dfs(row, column-1, m, n, k, visited);
    }

  }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class MovingCount {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return dfs(0, 0, m, n, k, visited);
    }

    private int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || getDigitSum(i) + getDigitSum(j) > k) {
            return 0;
        }

        visited[i][j] = true;

        return 1 + dfs(i - 1, j, m, n, k, visited)
                 + dfs(i + 1, j, m, n, k, visited)
                 + dfs(i, j - 1, m, n, k, visited)
                 + dfs(i, j + 1, m, n, k, visited);
    }

    private int getDigitSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> pathSum = new ArrayList<>();
        reverseToSum(res, root, target, 0, pathSum);
        return res;
    }

    private void reverseToSum(List<List<Integer>> res, TreeNode root, int target, int curVal, List<Integer> pathSum) {
        if (root == null) {
            return;
        }

        curVal += root.val;
        pathSum.add(root.val);
        if (curVal == target && root.left == null && root.right == null){
            res.add(new ArrayList<>(pathSum));
        }
        reverseToSum(res, root.left, target, curVal, pathSum);
        reverseToSum(res, root.right, target, curVal, pathSum);

        pathSum.remove(pathSum.size() - 1);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if (root == null) return root;
        traverseInOrder(root);

        //当我们完成中序遍历之后，pre会出现在链表的最后一个元素，head会指向第一个元素，我们现在要给
        //这两个元素互相指向
        head.left = pre;
        pre.right = head;
        return head;
    }

      private void traverseInOrder(Node root) {
          if (root == null) return;


          traverseInOrder(root.left);

          //在当前节点应做的处理：
          //我们先把cur拿出来, 不管当前pre是否有值，当前节点的左指针都应该指向pre
          root.left = pre;

          //如果pre不为null，那么让pre的右指针指向当前节点
          if (pre != null) {
              pre.right = root;
          }else {
              //否则，说明当前节点是第一个节点，应该让head也指向这个节点
              head = root;
          }

          //pre此时完成了右指针的指向任务，应该移动到当前节点了
          pre = root;

          traverseInOrder(root.right);
      }

  }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    int res, z;
    public int kthLargest(TreeNode root, int k) {
        z = k;
        traverseInOrder(root);
        return res;
    }

    private void traverseInOrder(TreeNode root) {
        if (root == null) return;

        //反着的中序遍历
        traverseInOrder( root.right);
        z--;
        if (z == 0) res = root.val;
        traverseInOrder( root.left);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        /*
        * 要知道当前节点左右指数的深度之差是否大于一，那么就需要使用一个函数，它能够返回当前节点左右子树的深度
        * */
        int leftDepth = getDepth(root.left) ;
        int rightDepth = getDepth(root.right) ;

        //这里的返回值是最容易出错的，要记得判断左右子节点是否也是平衡二叉树。
        return Math.abs(leftDepth - rightDepth) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int getDepth (TreeNode root) {
        if (root == null) return 0;

        int leftDepth = getDepth(root.left) ;
        int rightDepth = getDepth(root.right) ;

        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;

    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    public boolean isBalanced(TreeNode root) {
        //如果树根节点高度是-1,说明树非平衡,返回false
        return height(root) != -1; 
    }

    public int height(TreeNode root) {
        //递归终止条件
        if (root == null) {  
            return 0;  
        }
        
        //分别递归计算左右子树高度 
        int leftHeight = height(root.left);
        //如果左子树已经非平衡,直接返回-1
        if(leftHeight == -1) {
            return -1;
        }
        
        int rightHeight = height(root.right);
        //如果右子树已经非平衡,直接返回-1
        if(rightHeight == -1) {  
            return -1;
        }
        
        //比较左右子树高度差
        if (Math.abs(leftHeight - rightHeight) > 1) {
            //如果左右子树高度差>1,返回-1表示非平衡
            return -1;
        }
        
        //如果该节点平衡,则计算该节点树高  
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int sumNums(int n) {
        return sum(n);
    }

    public int sum(int n) {
        boolean x = n > 0 && (n = n + sum(n - 1)) > 0;
        return n;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val > q.val) {
            TreeNode tmp = p;
            p = q;
            q = tmp;
        }

        while (root != null) {
            if (root.val < p.val) {
                root = root.right;
            }else if (root.val > q.val) {
                root = root.left;
            }else {
                break;
            }
        }
        return root;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left == null && right == null) {
            return null;
        }

        if (left != null && right == null) {
            return left;
        }

        if (left == null && right != null) {
            return right;
        }

        return root;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        if(nums == null || nums.length==0) return 0;
        myMergeSort(nums, 0, nums.length-1, new int[nums.length]);
        return count;
    }

     private  void myMergeSort(int[] arr, int left, int right, int[] tmp) {
         //这里不能写等于，因为mid向下取整，会导致left为0，right为1时mid为0，递归恒成立，栈溢出
        if (left < right) {
            int mid = left + ((right - left) >> 1);
            myMergeSort(arr, left, mid, tmp);
            myMergeSort(arr, mid + 1, right, tmp);
            merge(arr, left, mid, right, tmp);
        }
    }

    private void merge(int[] arr, int left, int mid, int right, int[] tmp) {
        int le = left;
        int ri = mid + 1;
        int t = 0;
        while (le <= mid && ri <= right) {
            //注意这里要写等于，保证else中统计的是逆序对。如果不写等于的话else中会把等于的情况也统计进去
            if (arr[le] <= arr[ri]) {
                tmp[t++] = arr[le++];
               
            }else {
                tmp[t++] = arr[ri++];
                //这里要考虑左边的都是有序的，所以是当前次数加一得到count+1，然后左边部分的在当前数字右边的数都要加一次所以mid-le
                count = count + 1 + (mid - le);
            }
        }

        while (le <= mid) {
            tmp[t++] = arr[le++];
           
        }

        while (ri <= right) {
            tmp[t++] = arr[ri++];
        }

        t = 0;
        //注意这里是left<=right而不是t<=right，因为我们现在把数放回到原数组对应位置，只有left才能定位到原位置，t是不行的，
        //t只能用来定位tmp数组
        while (left <= right) {
            arr[left++] = tmp[t++];
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class Solution {
    public String minNumber(int[] nums) {
        myQuickSort(nums, 0, nums.length-1);
        StringBuilder stringBuilder = new StringBuilder();
        for (int i : nums) {
            stringBuilder.append(i);
        }
        return stringBuilder.toString();
    }

        private  void myQuickSort(int[] arr, int left, int right) {
        int mid = left + ((right - left) >> 1);
        //总是向下取整的中间值
        int pivot = arr[mid];
        int le = left;
        int ri = right;
        while (le < ri) {
            while (arr[le] < pivot) {
                le++;
            }
            while (arr[ri] > pivot) {
                ri--;
            }

            if (le >= ri) break;
            swap(arr, le, ri);

            if (greaterThan(arr[ri], pivot) == 0) {
                le++;
            }

            if (greaterThan(arr[le], pivot) == 0) {
                ri--;
            }
        }
        if (le == ri){
            le++;
            ri--;
        }

        if (left < ri) {
            myQuickSort(arr, left, ri);
        }

        if (le < right) {
            myQuickSort(arr, le, right);
        }
    }

    private  void swap(int[] arr, int le, int ri) {
        int tmp = arr[le];
        arr[le] = arr[ri];
        arr[ri] = tmp;
    }

}