又从夫字符串的排列组合 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例1:

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]
示例2:

 输入：S = "ab"
 输出：["ab", "ba"]
提示:

字符都是英文字母。
字符串长度在[1, 9]之间。
通过次数9,863提交次数13,825

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-ii-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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[] permutation(String S) {
        if (S == null || S.length() == 0) return new String[]{};
        char[] arr = S.toCharArray();
        Set<String> list = new HashSet<>();
        backtrack(arr, 0, arr.length, list);

        return list.toArray(new String[list.size()]);

    }
    public void backtrack(char[] arr, int start, int n, Set<String> list) {
        if (start == n - 1) {
            StringBuilder bd = new StringBuilder();
            for (int i = 0; i < arr.length; i++) {
                bd.append(arr[i]);
            }
            String val = bd.toString();
            if (!list.contains(val)) list.add(val);
            return;
        }

        for (int i = start; i < arr.length; i++) {
            swap(arr, start, i);
            backtrack(arr, start + 1, n, list);
            swap(arr, start, i);
        }

    }
    public void swap(char[] arr, int index1, int index2) {
        char temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

展开全文 >>

无重复字符串的排列组合 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

示例1:

 输入：S = "qwe"
 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
示例2:

 输入：S = "ab"
 输出：["ab", "ba"]
提示:

字符都是英文字母。
字符串长度在[1, 9]之间。
通过次数13,360提交次数16,468

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-i-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我们求整个字符串的排列，可以看成两步：

  1. 首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换,求后面所有字符的排列。

  2. 仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换

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
class Solution {
    public String[] permutation(String S) {
        if (S == null || S.length() == 0) return new String[]{};
        char[] arr = S.toCharArray();
        int len = 1;
        for (int i = 2; i <= S.length(); i++) {                                     //计算结果数组大小
            len = len * i;
        }
        String[] res = new String[len];
        backtrack(arr, 0, arr.length, res);                                   //回溯求解
        return res;
    }
    int index = 0;

    public void backtrack(char[] arr, int start, int n, String[] res) {

        if (start == n - 1) {
            StringBuilder bd = new StringBuilder();
            for (int i = 0; i < arr.length; i++) {
                bd.append(arr[i]);
            }
            res[index] = bd.toString();
            index++;
            return;
        }

        for (int i = start; i < arr.length; i++) {
            swap(arr, start, i);                                                    //交换
            backtrack(arr, start + 1, n, res);
            swap(arr, start, i);                                                    //换回来
        }

    }
    public void swap(char[] arr, int index1, int index2) {
        char temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public String[] permutation(String S) {
        List<String> list = new ArrayList<>();
        list.add(S);
        for (int i = 0; i < S.length() - 1; i++) {
            int size = list.size();
            for (int j = i + 1; j < S.length(); j++) {
                for (int index = 0; index < size; index++) {
                    list.add(swap(list.get(index), i, j));
                }
            }
        }
        return list.toArray(new String[list.size()]);
    }
    //交换位置
    private String swap(String s, int pos1, int pos2) {
        char[] chars = s.toCharArray();
        chars[pos1] ^= chars[pos2];
        chars[pos2] ^= chars[pos1];
        chars[pos1] ^= chars[pos2];
        return new String(chars);
    }
}

参考文献

作者：LineCutFeng
链接：https://leetcode-cn.com/problems/permutation-i-lcci/solution/shu-wo-zhi-yan-zai-zuo-de-ge-wei-du-shi-hao-yang-d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

递归乘法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

示例1:

 输入：A = 1, B = 10
 输出：10
示例2:

 输入：A = 3, B = 4
 输出：12
提示:

保证乘法范围不会溢出
通过次数12,738提交次数19,046

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recursive-mulitply-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int multiply(int A, int B) {
        if (A < B) {
            return mul(B, A);
        } else {
            return mul(A, B);
        }
    }
    public int mul(int val, int remain) {
        if (remain == 0) return 0;
        return val + mul(val, remain - 1);
    }
}

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int re = 0;
    public int multiply(int A, int B) {
        int min = A,max=B;
        if(A>B){
            min = B;
            max = A;
        }
        core(min,max,0);
        return re;
    }
    public void core(int min,int max,int i){
        if((min>>>i)==0) return;
        if(((min>>>i)&1)==1){
            re+=max<<i;
        }
        core(min,max,i+1);
    }
}

参考文献

Robin的评论

作者：yuruiyin 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

幂集 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

说明：解集不能包含重复的子集。

示例:

 输入： nums = [1,2,3]
 输出：
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
通过次数12,028提交次数14,707

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/power-set-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

回溯法

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
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        Set<List<Integer>> resList = new HashSet<>();

        if (nums == null || nums.length == 0) return new ArrayList<>();
        int len = nums.length;
        List<Integer> list = new ArrayList<>();

        resList.add(new ArrayList<>());                                             //空集
        for (Integer val : nums) {
            List<Integer> lst = Arrays.asList(val);
            resList.add(lst);                                                       //包含一个元素的集合
        }
        for (int i = 1; i < len - 1; i++) {
            backtrack(nums, 0, i + 1, resList, new ArrayList<>());
        }
        if (len > 1) {
            for (int i = 0; i < len; i++) {
                list.add(nums[i]);                                                 //包含所有元素的集合
            }
            resList.add(new ArrayList<>(list));
        }
        return new ArrayList<>(resList);
    }
    public void backtrack(int[] nums, int start, int n, Set<List<Integer>> resList, List<Integer> list) {
        if (list.size() == n) {
            resList.add(new ArrayList<>(list));
            return;
        }

        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            backtrack(nums, i + 1, n, resList, list);
            list.remove(list.size() - 1);
        }
    }
}

非递归

  1. 添加一个空集，结果是[]
  2. 访问数字1，对原来的子集追加1，结果是[],[1]
  3. 访问数字2，对原来的子集追加2，结果是[],[1],[2],[1,2]
  4. 访问数字3，对原来的子集追加3，结果是[],[1],[2],[1,2],[3][1,3],[2,3],[1,2,3]

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>(1 << nums.length);
    //先添加一个空的集合
    res.add(new ArrayList<>());
    for (int num : nums) {
        //每遍历一个元素就在之前子集中的每个集合追加这个元素，让他变成新的子集
        for (int i = 0, j = res.size(); i < j; i++) {
            //遍历之前的子集，重新封装成一个新的子集
            List<Integer> list = new ArrayList<>(res.get(i));
            //然后在新的子集后面追加这个元素
            list.add(num);
            //把这个新的子集添加到集合中
            res.add(list);
        }
    }
    return res;
}

优雅的回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
    //走过的所有路径都是子集的一部分，所以都要加入到集合中
    list.add(new ArrayList<>(tempList));
    for (int i = start; i < nums.length; i++) {
        //做出选择
        tempList.add(nums[i]);
        //递归
        backtrack(list, tempList, nums, i + 1);
        //撤销选择
        tempList.remove(tempList.size() - 1);
    }
}

位运算

1
2
3
4
5
6
7
8
9
10
11
12
nums = [1, 2, 3]，长度为3，取看成是1，不取看成是0.
那么就有：
[0, 0, 0] -> 0
[0, 0, 1] -> 1
[0, 1, 0] -> 2
[0, 1, 1] -> 3
[1, 0, 0] -> 4
[1, 0, 1] -> 5
[1, 1, 0] -> 6
[1, 1, 1] -> 7

把这些0和1看成是二进制，代表0~7共8个数字。幂集大小是2^nums.length。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        int total = (1 << nums.length);
        for (int i = 0; i < total; ++i) {
            LinkedList<Integer> list = new LinkedList<>();
            int num = i, idx = 0;
            while (num != 0) {
                if ((num & 1) != 0)
                    list.addLast(nums[idx]);
                num >>= 1;
                ++idx;
            }
            res.add(list);
        }
        return res;
    }
}

位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static List<List<Integer>> subsets(int[] nums) {
    //子集的长度是2的nums.length次方，这里通过移位计算
    int length = 1 << nums.length;
    List<List<Integer>> res = new ArrayList<>(length);
    //遍历从0到length中间的所有数字，根据数字中1的位置来找子集
    for (int i = 0; i < length; i++) {
        List<Integer> list = new ArrayList<>();
        for (int j = 0; j < nums.length; j++) {
            //如果数字i的某一个位置是1，就把数组中对
            //应的数字添加到集合
            if (((i >> j) & 1) == 1)
                list.add(nums[j]);
        }
        res.add(list);
    }
    return res;
}

参考文献

作者：sdwwld来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：gfu 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

迷路的机器人 

1
2


回溯

直接回溯会超时，dfs 的时候加一个 visited 标识一般是为了防止死循环，但这个题目只能向右向下走，所以不会死循环，所以很多人就不加 visited 了。

但其实这个题目仍然需要 visited 标识，因为我们可以通过不同的路径到达同一个位置：比如身处位置 (0,0) 时，可以通过”先右再下”和“先下再右”两种方式到达 (1,1)。

使用 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
29
30
31
32
33
34
class Solution {
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        boolean[][] vis = new boolean[obstacleGrid.length][obstacleGrid[0].length];
        if (obstacleGrid == null) return new ArrayList<>();
        if (obstacleGrid.length == 0 || obstacleGrid[0].length == 0) return new ArrayList<>();
        backtrack(obstacleGrid, 0, 0, new ArrayList<>(),vis);
        return resList;
    }

    List<List<Integer>> resList = new ArrayList<>();

    public boolean backtrack(int[][] obstacleGird, int y, int x, List<List<Integer>> list, boolean[][] vis) {
        if (y >= obstacleGird.length || y < 0 || x < 0 || x >= obstacleGird[0].length || obstacleGird[y][x] == 1||vis[y][x]) {
            return false;
        }
        if (y == obstacleGird.length - 1 && x == obstacleGird[0].length - 1 && obstacleGird[y][x] == 0) {
            list.add(Arrays.asList(y, x));
            resList = new ArrayList<>(list);
            return true;
        }

        if (obstacleGird[y][x] == 0) {
            vis[y][x] = true;
            list.add(Arrays.asList(y, x));
            if (backtrack(obstacleGird, y + 1, x, list, vis)) return true;
            if (backtrack(obstacleGird, y, x + 1, list, vis)) return true;
            list.remove(list.size() - 1);
        }
        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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {

        int row = obstacleGrid.length;
        if (row == 0) {
            return res;
        }
        int col = obstacleGrid[0].length;
        if (col == 0) {
            return res;
        }

        // 起点或终点是障碍，不可能到达
        if (obstacleGrid[0][0] == 1 || obstacleGrid[row - 1][col - 1] == 1) {
            return res;
        }

        int dp[][] = new int[row+1][col+1];
        dp[0][0] = 1;
        // 初始化首列
        for (int i = 1; i < row; i++) {
            if (obstacleGrid[i][0] == 1) {
                dp[i][0] = 0;
            } else {
                dp[i][0] = dp[i - 1][0];
            }
        }
        // 初始化首行
        for (int i = 1; i < col; i++) {
            if (obstacleGrid[0][i] == 1) {
                dp[0][i] = 0;
            } else {
                dp[0][i] = dp[0][i - 1];
            }
        }
        // 求路径
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else { // 无需保存和，保存最大的即可
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // 到达终点的路径为0，直接返回
        if (dp[row - 1][col - 1] == 0) {
            return res;
        }

        // 从终点反推回起点
        int r = row - 1, c = col - 1;
        while (r != 0 || c != 0) {
            res.add(Arrays.asList(r,c));

            int up = 0;
            if (r > 0) {
                up = dp[r - 1][c];
            }

            int left = 0;
            if (c > 0) {
                left = dp[r][c - 1];
            }

            if (up >= left) {
                r--;
            } else {
                c--;
            }
        }
        res.add(Arrays.asList(0,0));
        Collections.reverse(res);
        return res;
    }
}


user83429423的评论

展开全文 >>

无重叠区间 

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
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:

输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
通过次数34,605提交次数73,959

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/non-overlapping-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

贪心

对题目的理解不够，无重叠区间并不是连续区间，给出的样例迷惑人,无需考虑区间是否连续

对区间的右边界进行排序，冲突时选择右边界小的那个，这样右边就可以容下更多的区间

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 int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null) return 0;
        if (intervals.length <=1) return 0;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int count = 1;
        int[] last = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= last[1]) {
                last = intervals[i];
                count++;
            }

        }
        int res = intervals.length - count;
        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
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });

        int n = intervals.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (intervals[j][1] <= intervals[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return n - Arrays.stream(dp).max().getAsInt();
    }
}

参考文献

作者：LeetCode-Solution来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

下一个数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。

示例1:

 输入：num = 2（或者0b10）
 输出：[4, 1] 或者（[0b100, 0b1]）
示例2:

 输入：num = 1
 输出：[2, -1]
提示:

num的范围在[1, 2147483647]之间；
如果找不到前一个或者后一个满足条件的正数，那么输出 -1。
通过次数3,168提交次数6,994

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/closed-number-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
class Solution {
    public int[] findClosedNumbers(int num) {

        if (num == 0) return new int[]{-1, -1};
        int[] n = new int[32];
        int flag = 1;

        for (int i = 0; i < 32; i++) {
            if ((flag & num) != 0) {
                n[31 - i] = 1;
            }
            flag <<= 1;
        }

        int[] n1 = new int[32];
        int[] n2 = new int[32];

        int index = 0;
        for (int i = 0; i < 32; i++) {
            n1[i] = n[i];
            n2[i] = n[i];
            if (n[i] == 1) {
                index = i;
            }
        }


        boolean flag1 = false;
        boolean flag2 = false;
        int[] res = new int[]{-1, -1};
        for (int i = index + 1; i < 32; i++) {
            if (n1[i] == 0) {
                n1[i] = 1;
                n1[index] = 0;
                flag1 = true;
                break;
            }
        }

        if (flag1 == false) {
            for (int i = index - 1; i >= 0; i--) {
                if (n1[i] == 1) {
                    for (int j = i + 1; j < 32; j++) {
                        if (n1[j] == 0) {
                            n1[j] = 1;
                            n1[i] = 0;
                            flag1 = true;
                            //右边的1，替换到左边
                            int left = j + 1, right = 31;
                            while (left < right) {
                                if (n1[left] == 0 && n1[right] == 1) {
                                    n1[left] = n1[left] ^ n1[right];
                                    n1[right] = n1[left] ^ n1[right];
                                    n1[left] = n1[left] ^ n1[right];
                                }

                                left++;
                                right--;
                            }
                            break;
                        }
                    }
                }
                if (flag1) break;
            }
        }
        
        for (int i = index - 1; i >= 0; i--) {
            if (n2[i] == 0) {
                n2[i] = 1;
                n2[index] = 0;
                flag2 = true;
                int left = i + 1, right = 31;
                while (left < right) {
                    if (n2[left] == 1 && n2[right] == 0) {
                        n2[left] = n2[left] ^ n2[right];
                        n2[right] = n2[left] ^ n2[right];
                        n2[left] = n2[left] ^ n2[right];
                    }

                    left++;
                    right--;
                }

                break;
            }
        }

        if (flag1) {
            StringBuilder bd = new StringBuilder();
            for (int i = 0; i < 32; i++) {
                bd.append(n1[i]);
            }

            res[1] = Integer.valueOf(bd.toString(), 2);
        }

        if (flag2) {
            StringBuilder bd = new StringBuilder();
            for (int i = 0; i < 32; i++) {
                bd.append(n2[i]);
            }

            res[0] = Integer.valueOf(bd.toString(), 2);
        }

        return res;
    }
}

展开全文 >>

二进制数转字符 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
二进制数转字符串。给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表达式。如果该数字无法精确地用32位以内的二进制表示，则打印“ERROR”。

示例1:

 输入：0.625
 输出："0.101"
示例2:

 输入：0.1
 输出："ERROR"
 提示：0.1无法被二进制准确表示
提示：

32位包括输出中的"0."这两位。
通过次数4,343提交次数6,986

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bianry-number-to-string-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String printBin(double num) {
        if (num == 0) return "0.0";
        StringBuilder bd = new StringBuilder();
        bd.append("0.");
        double ret = num;
        int count = 0;
        while (ret > 0 && count < 31) {
            ret = ret * 2;
            int val = (int) ret;
            bd.append(val);
            if (val == 1) ret = ret - 1;
            count++;
        }
        if (ret > 0) {
            return "ERROR";
        }
        return bd.toString();
    }
}

展开全文 >>

十进制转二进制

二进制整数转十进制

由二进制数转换成十进制数的基本做法是，把二进制数首先写成加权系数展开式，然后按十进制加法规则求和。这种做法称为”按权相加”法。

十进制整数转二进制

十进制整数转换为二进制整数采用”除2取余，逆序排列”法。具体做法是：用2去除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为零时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

十进制小数转二进制

十进制小数转换成二进制小数采用”乘2取整，顺序排列”法。具体做法是：用2乘十进制小数，可以得到积，将积的整数部分取出，再用2乘余下的小数 部分，又得到一个积，再将积的整数部分取出，如此进行，直到积中的小数部分为零，或者达到所要求的精度为止。

然后把取出的整数部分按顺序排列起来，先取的整数作为二进制小数的高位有效位，后取的整数作为低位有效位。

1
2
3
4
5
6
7
8
9
10
11
12
0.7=（0.1 0110 0110...）B

0.7*2=1.4========取出整数部分1 
0.4*2=0.8========取出整数部分0 
0.8*2=1.6========取出整数部分1 
0.6*2=1.2========取出整数部分1 
0.2*2=0.4========取出整数部分0　 
0.4*2=0.8========取出整数部分0 
0.8*2=1.6========取出整数部分1 
0.6*2=1.2========取出整数部分1 
0.2*2=0.4========取出整数部分0

参考文献

RUNOOB.COM十进制小数转化为二进制小数

展开全文 >>

求和路径 

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
给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，
打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，
但是其方向必须向下(只能从父节点指向子节点方向)。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

3
解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]
提示：

节点总数 <= 10000
通过次数9,725提交次数20,108

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/paths-with-sum-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

不求树的深度的修改

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 int pathSum(TreeNode root, int sum) {
        if (root == null && sum == 0) return 0;
        if (root == null) return 0;
        deep(root, new ArrayList<>(), sum);
        return res;
    }

    int res = 0;

    public void deep(TreeNode root, List<Integer> list, int sum) {
        if (root == null) return;
        list.add(root.val);
        int curSum = 0;
        for (int i = list.size() - 1; i >= 0; i--) {
            //必须要自叶子节点方向向根节点方向求和，不然会重复计数
            curSum += list.get(i);
            if (curSum == sum) res++;
        }
        deep(root.left, list, sum);
        deep(root.right, list, sum);
        list.remove(list.size() - 1);
    }

}

直接暴力递归

分别计算当前的节点和左子树与右子树的满足路径和等于sum的路径数量，并对三个计算的结果求和

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    int res=0;
    public int pathSum(TreeNode root, int sum) {
        if(root==null) return 0;
        return dfs(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum);        //检查根节点的和，检查左右子树的和
    }
    private int dfs(TreeNode root,int sum){
        if(root==null) return 0;
        sum-=root.val;
        return (sum==0?1:0)+dfs(root.left,sum)+dfs(root.right,sum);                 //如果当前节点的和等于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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        int dep = depth(root);
        int[] paths = new int[dep];
        pathSum(root, sum, 0, paths);
        return res;
    }

    int res = 0;

    public void pathSum(TreeNode root, int sum, int level, int[] paths) {
        if (root == null) {
            return;
        }
        paths[level] = root.val;
        int t = 0;
        for (int i = level; i >= 0; i--) {
            t += paths[i];
            if (t == sum) {
                res += 1;
            }
        }
        pathSum(root.left, sum, level + 1, paths);
        pathSum(root.right, sum, level + 1, paths);
    }

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

参考文献

作者：dadou来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：geguanting来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走