仅用于记录自己的刷题过程

1. 二分查找/排序

1. BM22 比较版本号

题目：

解析：
思路一：
分别遍历来两个字符串，将其在点号之间的数字变成数字比较。
step 1：利用两个指针表示字符串的下标，分别遍历两个字符串。
step 2：每次截取点之前的数字字符组成数字，即在遇到一个点之前，直接取数字，加在前面数字乘10的后面。（因为int会溢出，这里采用long记录数字）
step 3：然后比较两个数字大小，根据大小关系返回1或者-1，如果全部比较完都无法比较出大小关系，则返回0.

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串
     * @param version2 string字符串
     * @return int整型
     */
    public int compare (String version1, String version2) {
        int n1 = version1.length();
        int n2 = version2.length();
        int i = 0, j = 0;
        while (i < n1 || j < n2) {  
            long num1 = 0, num2 = 0;
            while ( i < n1 && version1.charAt(i) != '.') {
                num1 = num1 * 10 + (version1.charAt(i) - '0');
                i++;
            }
            i++;
            while ( j < n2 && version2.charAt(j) != '.') {
                num2 = num2 * 10 + (version2.charAt(j) - '0');
                j++;
            }
            j++;
            if (num1 > num2)
                return 1;
            if (num1 < num2)
                return -1;
        }
        return 0;
    }

}

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

注意：
1、这里的long num1 = 0, num2 = 0;要放在while循环内部，因为每次比较都是比较两个点之间的数字（以点为界限），如果不放在while循环内部那么就成了将整个字符串变成对应数字，那1.0和1.0.0就会判断错误。
2、***.charAt(i) - '0'：ASC码48就是’0’，也就是说’0’的值是48，而后依次是’1’到’9’。 这样正好是char型减去48就是它对应的int值。
也就是 char转换成int是char- '0'；int转换成char是char + '0'。
思路二：
直接分割后比较。
step 1：使用split函数或者字符串流输入，按照点将两个原始字符串分割，使每个修订号的数字单独呈现在数组中。
step 2：遍历数组，每次各自取出一个数字比较，较短的版本号没有可取的数字了，就直接取0。
step 3：遍历取出的数字字符串，将其转换成数字，然后比较数字大小。根据大小关系返回1或者-1，如果全部比较完都无法比较出大小关系，则返回0.

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串
     * @param version2 string字符串
     * @return int整型
     */
    public int compare (String version1, String version2) {
        // 原本version1 = “1.01”，version2“1.001”
        // 经过.split("\\.") 变成 nums1 = ["1","01"],nums2 = ["1","001"]
        String[] nums1 = version1.split("\\.");
        String[] nums2 = version2.split("\\.");
        for (int i = 0; i < nums1.length || i < nums2.length; i++) {
            String str1 = i < nums1.length ? nums1[i] : "0";
            String str2 = i < nums2.length ? nums2[i] : "0";
            long num1 = 0;
            //字符串转数字
            for (int j = 0; j < str1.length(); j++)
                num1 = num1 * 10 + (str1.charAt(j) - '0');
            long num2 = 0;
            for (int j = 0; j < str2.length(); j++)
                num2 = num2 * 10 + (str2.charAt(j) - '0');
            //比较数字大小
            if (num1 > num2)
                return 1;
            if (num1 < num2)
                return -1;
        }
        //版本相同
        return 0;
    }

}
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

2. BM20 数组中的逆序对

题目：

解析：
思路一：
利用归并排。其实就是在归并排序的过程中加上计数。

step 1： 划分阶段：将待划分区间从中点划分成两部分，两部分进入递归继续划分，直到子数组长度为1.
step 2： 排序阶段：使用归并排序递归地处理子序列，同时统计逆序对，因为在归并排序中，我们会依次比较相邻两组子数组各个元素的大小，并累计遇到的逆序情况。而对排好序的两组，右边大于左边时，它大于了左边的所有子序列，基于这个性质我们可以不用每次加1来统计，减少运算次数。
step 3： 合并阶段：将排好序的子序列合并，同时累加逆序对。

public class Solution {
    public int mod = 1000000007;
    public int InversePairs(int[] array) {
        int len = array.length;
        if (len < 2 ) {
            return 0;
        }
        int[] temp = new int[len];
        int counts = msort(array, 0, len - 1, temp);
        return counts;
    }
    public int msort(int[] nums, int left, int right, int[] temp) {
        // 递归终止条件
        if (left == right) {
            return 0;
        }
        // 当left和right非常大的时候，直接使用int mid = (left + righ) / 2容易发生整型溢出
        int mid = left + (right - left) / 2;
        int leftcount = msort(nums, left, mid, temp);
        int rightcount = msort(nums, mid + 1, right, temp);
        // 优化，如果左半部分最后一个元素小于右半部分第一个元素
        if (nums[mid] <= nums[mid + 1]) {
            return leftcount + rightcount;
        }
        // 防止溢出，在此处先mod一次，之后再mod一次，不然等后面一次解决mod会发生溢出
        int tempcount = (leftcount + rightcount) % mod;
        
        int count = merge(nums, left, mid, right, temp);
//         return (leftcount + rightcount +count) % mod;
        return (tempcount + count ) % mod;

    }
    public int merge(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left ; i <= right ; i++) {
            temp[i] = nums[i];
        }
        int i = left;
        int j = mid + 1;
        int count = 0;
        for (int k = left ; k <= right ; k++) {
            if (i == mid + 1) { // 左半部分已经排序完
                nums[k] = temp[j];
                j++;
            } else if ( j == right + 1) { // 右半部分已经排序完
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {// 这里要是保证归并排序是稳定排序，就必须加上等于temp[i] <= temp[j]
                nums[k] = temp[i];
                i++;
            } else {
                nums[k] = temp[j];
                j++;
                count += (mid - i + 1);
            }
        }
        return count;
    }
}
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
57
58

注意：
1、返回的时候不能直接return leftcount + rightcount +count;然后再对结果mod,也不能直接return (leftcount + rightcount +count) % mod;，这样在数字很大的时候会发生溢出。所以应该分成两部分，先对(leftcount + rightcount)%mod,然后将其结果和count相加后再次mod.

2、temp[i] <= temp[j] 这里要是保证归并排序是稳定排序，就必须加上等于，temp[i] <= temp[j]。

3、求中间值的时候需要按照 int mid = left + (right - left) / 2这样计算，因为当left和right非常大的时候，直接使用 int mid = (left + righ)） / 2容易发生整型溢出。

思路二：树状数组。不会。。。。

3. BM23 二叉树的前序遍历

题目：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

数据范围：二叉树的节点数量满足 0≤n≤100 ，二叉树节点的值满足 0 \1≤val≤100 ，树的各节点的值各不相同
解析：
思路一：递归
终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。
返回值： 每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。
本级任务： 每个子问题优先访问这棵子树的根节点，然后递归进入左子树和右子树。
具体做法：

step 1：准备数组用来记录遍历到的节点值，Java可以用List，C++可以直接用vector。
step 2：从根节点开始进入递归，遇到空节点就返回，否则将该节点值加入数组。
step 3：依次进入左右子树进行递归。

import java.util.*;
public class Solution {
    public void preorder(List<Integer> list, TreeNode root){
        //遇到空节点则返回
        if(root == null) 
            return;
        //先遍历根节点
        list.add(root.val); 
        //再去左子树
        preorder(list, root.left); 
        //最后去右子树
        preorder(list, root.right); 
    }
    
    public int[] preorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList(); 
        //递归前序遍历
        preorder(list, root); 
        //返回的结果
        int[] res = new int[list.size()]; 
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        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

思路二：栈
step 1：优先判断树是否为空，空树不遍历。
step 2：准备辅助栈，首先记录根节点。
step 3：每次从栈中弹出一个元素，进行访问，然后验证该节点的左右子节点是否存在，存的话的加入栈中，优先加入右节点。

import java.util.*;
public class Solution {
    public int[] preorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList(); 
        Stack<TreeNode> s = new Stack<TreeNode>();
        //空树返回空数组
        if(root == null) 
            return new int[0];
        //根节点先进栈
        s.push(root); 
        while(!s.isEmpty()){
            //每次栈顶就是访问的元素
            TreeNode node = s.pop(); 
            list.add(node.val);
            //如果右边还有右子节点进栈
            if(node.right != null) 
                s.push(node.right);
            //如果左边还有左子节点进栈
            if(node.left != null) 
                s.push(node.left);
        }
        //返回的结果
        int[] res = new int[list.size()]; 
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        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

4.BM24 二叉树的中序遍历

题目：
给定一个二叉树的根节点root，返回它的中序遍历结果。

数据范围：树上节点数满足0≤n≤1000，树上每个节点的值满足0≤val≤1000
进阶：空间复杂度 O(n)，时间复杂度 O(n)
解析：
思路一：递归
终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。
返回值： 每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。
本级任务： 每个子问题优先访问左子树的子问题，等到左子树的结果返回后，再访问自己的根节点，然后进入右子树。
具体做法：

step 1：准备数组用来记录遍历到的节点值，Java可以用List，C++可以直接用vector。
step 2：从根节点开始进入递归，遇到空节点就返回，否则优先进入左子树进行递归访问。
step 3：左子树访问完毕再回到根节点访问。
step 4：最后进入根节点的右子树进行递归。

import java.util.*;
public class Solution {
    public void inorder(List<Integer> list, TreeNode root){
        //遇到空节点则返回
        if(root == null) 
            return;
        //先去左子树
        inorder(list, root.left); 
        //再访问根节点
        list.add(root.val); 
        //最后去右子树
        inorder(list, root.right); 
    }
    
    public int[] inorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList(); 
        //递归中序遍历
        inorder(list, root); 
        //返回的结果
        int[] res = new int[list.size()]; 
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        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

思路二：栈
step 1：优先判断树是否为空，空树不遍历。
step 2：准备辅助栈，当二叉树节点为空了且栈中没有节点了，我们就停止访问。
step 3：从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。
step 4：到达最左后，可以开始访问，如果它还有右节点，则将右边也加入栈中，之后右子树的访问也是优先到最左。

import java.util.*;

public class Solution {

    public int[] inorderTraversal (TreeNode root) {
        ArrayList<Integer> list = new ArrayList();
        Stack<TreeNode> s = new Stack<TreeNode>();
        if (root == null)
            return new int[0];
        //当树节点不为空或栈中有节点时
        while ( root != null || !s.isEmpty()) {
            while ( root != null) {
                s.push(root);
                root = root.left;
            }
            //访问该节点
            TreeNode node = s.pop();
            list.add(node.val);
            //进入右节点
            root = node.right;
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        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

5.BM25 二叉树的后序遍历

题目：
略
解析：
思路一：递归
终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。
返回值： 每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。
本级任务： 对于每个子问题，优先进入左子树的子问题，访问完了再进入右子树的子问题，最后回到父问题访问根节点。
具体做法：

step 1：准备数组用来记录遍历到的节点值，Java可以用List，C++可以直接用vector。
step 2：从根节点开始进入递归，遇到空节点就返回，否则优先进入左子树进行递归访问。
step 3：左子树访问完毕再进入根节点的右子树递归访问。
step 4：最后回到根节点，访问该节点。

import java.util.*;
public class Solution {
    public void postorder(List<Integer> list, TreeNode root){
        //遇到空节点则返回
        if(root == null) 
            return;
        //先去左子树
        postorder(list, root.left); 
        //再去右子树
        postorder(list, root.right); 
        //最后访问根节点
        list.add(root.val); 
    }
    
    public int[] postorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList(); 
        //递归后序遍历
        postorder(list, root); 
        //返回的结果
        int[] res = new int[list.size()]; 
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        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

思路二：栈
step 1：开辟一个辅助栈，用于记录要访问的子节点，开辟一个前序指针pre。
step 2：从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。
step 3：弹出一个栈元素，看成该子树的根，判断这个根的右边有没有节点或是有没有被访问过，如果没有右节点或是被访问过了，可以访问这个根，并将前序节点标记为这个根。
step 4：如果没有被访问，那这个根必须入栈，进入右子树继续访问，只有右子树结束了回到这里才能继续访问根。

import java.util.*;
public class Solution {
    public int[] postorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList(); 
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode pre = null;
        while(root != null || !s.isEmpty()){ 
            //每次先找到最左边的节点
            while(root != null){ 
                s.push(root);
                root = root.left;
            }
            //弹出栈顶
            TreeNode node = s.pop(); 
            //如果该元素的右边没有或是已经访问过
            if(node.right == null || node.right == pre){ 
                //访问中间的节点
                list.add(node.val); 
                //且记录为访问过了
                pre = node; 
            }else{
                //该节点入栈
                s.push(node); 
                //先访问右边
                root = node.right; 
            }
        }
        //返回的结果
        int[] res = new int[list.size()]; 
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        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

6. BM26 求二叉树的层序遍历

题目：

解析：
利用队列。
step 1：首先判断二叉树是否为空，空树没有遍历结果。
step 2：建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面。
step 3：每次进入一层，统计队列中元素的个数。因为每当访问完一层，下一层作为这一层的子节点，一定都加入队列，而再下一层还没有加入，因此此时队列中的元素个数就是这一层的元素个数。
step 4：每次遍历这一层这么多的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点，依次加入队列排队等待访问。
step 5：访问完这一层的元素后，将这个一维数组加入二维数组中，再访问下一层。

import java.util.*;

public class Solution {

    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> arr = new ArrayList();
        if (root == null) {
            return null;
        }
        Queue<TreeNode> q = new ArrayDeque();
        q.add(root);
        while ( !q.isEmpty()) {
            ArrayList<Integer> row = new ArrayList();
            int n = q.size();
            for ( int i = 0 ; i < n; i++) {
                TreeNode cur = q.poll();
                row.add(cur.val);
                if (cur.left != null) {
                    q.add(cur.left);
                }
                if (cur.right != null) {
                    q.add(cur.right);
                }
            }
            arr.add(row);
        }
        return arr;
    }
}
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

7. BM28 二叉树的最大深度

题目：
求给定二叉树的最大深度，
深度是指树的根节点到任一叶子节点路径上节点的数量。
最大深度是所有叶子节点的深度的最大值。
（注：叶子节点是指没有子节点的节点。）
数据范围：0≤n≤100000，树上每个节点的val满足 ∣val∣≤100
要求： 时间复杂度 O(n)
解析：
思路一：
递归

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

1
2
3
4
5
6
7
8
9

思路二：
层次遍历，每遍历完一层，深度加一。

import java.util.*;

public class Solution {

    public int maxDepth (TreeNode root) {
        if (root == null)
            return 0;
        Queue<TreeNode> q = new ArrayDeque();
        q.offer(root);
        int hight = 0;
        while (! q.isEmpty()) {
            int n = q.size();
            for (int i = 0 ; i < n; i++) {
                TreeNode node = q.poll();

                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
            hight ++;
        }
        return hight;
    }
}
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

8. BM30 二叉搜索树与双向链表

题目：

解析：
注意是二叉搜索树的特点。解法就是在中序遍历的基础上加东西。
思路一：递归

import java.util.*;

public class Solution {
    public TreeNode head = null;
    public TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        Convert(pRootOfTree.left);
        if (pre == null) {
            head = pRootOfTree;
            pre = pRootOfTree;
        } else {
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路二：利用栈
二叉树中序遍历除了递归方法，我们还可以尝试非递归解法，与常规的非递归中序遍历几乎相同，还是借助栈来辅助，只是增加了连接节点。

具体做法：
step 1：创建两个指针，一个指向题目中要求的链表头（head），一个指向当前遍历的前一节点（pre)，创建一个布尔型变量，标记是否是第一次到最左，因为第一次到最左就是链表头。
step 2：判断空树不能连接。
step 3：初始化一个栈辅助中序遍历。
step 4：依次将父节点加入栈中，直接进入二叉树最左端。
step 5：第一次进入最左，初始化head与pre，然后进入它的根节点开始连接。
step 6：最后将右子树加入栈中，栈中依次就弹出“左中右”的节点顺序，直到栈为空。

import java.util.*;

public class Solution {

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        Stack<TreeNode> s = new Stack();
        TreeNode head = null;
        TreeNode pre = null;
       
        while (!s.isEmpty() || pRootOfTree != null) {
            while (pRootOfTree != null) {
                s.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            }
            pRootOfTree = s.pop();
            if (pre == null) {
                head = pRootOfTree;
                pre = pRootOfTree;
            } else {
                pre.right = pRootOfTree;
                pRootOfTree.left = pre;
                pre = pRootOfTree;
            }
            pRootOfTree = pRootOfTree.right;
        }
        return head;
    }
}
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

题目：
解析：

题目：
解析：

题目：
解析：

题目：
解析：

题目：
解析：