标签: 枚举

LeetCode刷题【剑指 Offer 57 – II】和为s的连续正数序列

输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。

序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

 

示例 1:

输入:target = 9
输出:[[2,3,4],[4,5]]

示例 2:

输入:target = 15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]

 

限制:

  • 1 <= target <= 10^5

 

Related Topics
  • 数学
  • 双指针
  • 枚举

  • 👍 449
  • 👎 0
  • 双指针

    class Solution {
        public int[][] findContinuousSequence(int target) {
            int l = 1;
            int r = 2;
            List<int[]> res = new ArrayList<>();
            while (l<r){
                int sum = (l + r) * (r - l + 1) / 2;
                if (sum == target){
                    int[] arr = new int[r - l + 1];
                    int tmp = l-1;
                    while (++tmp <=r){
                        arr[tmp - l] = tmp;
                    }
                    res.add(arr);
                    l++;
                    continue;
                }
                if (sum < target){
                    r++;
                }else{
                    l++;
                }
            }
    
            return res.toArray(new int[res.size()][]);
        }
    }

    LeetCode刷题【869】重新排序得到 2 的幂

    给定正整数 n ,我们按任何顺序(包括原始顺序)将数字重新排序,注意其前导数字不能为零。

    如果我们可以通过上述方式得到 2 的幂,返回 true;否则,返回 false

     

    示例 1:

    输入:n = 1
    输出:true
    

    示例 2:

    输入:n = 10
    输出:false
    

     

    提示:

    • 1 <= n <= 109
    Related Topics
  • 数学
  • 计数
  • 枚举
  • 排序

  • 👍 146
  • 👎 0
  • 明明各方面都非常的符合题意,但是只击败了5.28%的勇者【怎么都在打表】

    emmm,emmm,emmm,能AC,海星

    思路什么的,就回溯,转2进制,判断除了第一位之后有没有其他的1

    class Solution {
    
        int[] arr;
    
        int[] sizeMap = {0,9,99,999,9999,99999,999999,9999999,99999999,999999999,2147483647};
    
    
        public boolean reorderedPowerOf2(int n) {
            if (n==0){
                return false;
            }
            int size = 0;
            //看看这个数字能转成多大的int[]数组,然后用来执行回溯
            for (int i = 0; i < sizeMap.length; i++) {
                if (sizeMap[i] >= n){
                    size = i;
                    break;
                }
            }
            arr = new int[size];
            //把n数字的个位置上的数字放入数组中
            while (n > 0){
                arr[--size] = n % 10;
                n /= 10;
            }
            //执行回溯
            return dfs(0,0,new boolean[arr.length]);
        }
    
        /**
         * 判断一个数字是否是2的幂
         * @param num
         * @return
         */
        public boolean isPowerOf2(int num){
            int[] intArr = toBinaryArr(num);
            for (int i = 1; i < intArr.length; i++) {
                //2的幂的二进制有一个特点,就是只有第一位是1,后面都是0,
                //从第二位开始判断但凡有一个数字等于1,就返回false
                if (intArr[i] == 1){
                    return false;
                }
            }
            //后面都没有1,只有第一位是1,那么返回true;
            return true;
        }
    
        /**
         * 把一个数字转换成二进制int[]数组
         * @param num
         * @return
         */
        public int[] toBinaryArr(int num){
            int size = 32;
            //最大就32位,往大了写,之间判断某个数字的二进制数字有多长有点麻烦
            int[] intArr = new int[size];
            while (num > 0 ){
                //依次余2赋值在每一位上
                intArr[--size] = num % 2;
                num = num >> 1;
            }
            //到这里就已经知道之前用了多少位了,返回一个新的不含前面多余0的二进制数数字
            int[] res = new int[32 - size];
            System.arraycopy(intArr,size,res,0,32-size);
            return res;
        }
    
        /**
         * 回溯算法
         * @param num 当前数字
         * @param idx 当前数字的位数的
         * @param used arr[]数组中哪些位置已经被用过了
         * @return
         */
        public boolean dfs(int num, int idx, boolean[] used){
            if (idx == arr.length ){
                //终止条件,判断下这个数是否是2的幂数
                if (isPowerOf2(num)){
                    return true;
                }
                return false;
            }
            //当前数字乘以10,准备在后面再加上一个数字
            num *= 10;
            for (int i = 0; i < arr.length; i++) {
                //第一位数字不能为0
                //或者这个位置的数字已经用过了,那么跳过到下一个选项
                if ((idx == 0 && arr[i] == 0) || used[i]){
                    continue;
                }
                //标记当前数字用过了
                used[i] = true;
                //构建了新数字num+arr[i] 然后处理下一个情况
                if (dfs(num+arr[i],idx+1,used)){
                    //如果能满足就直接终止
                    return true;
                }
                //回溯的重要操作,将状态改回
                used[i] = false;
            }
            //如果都不能满足,返回false
            return false;
        }
    
    }
    

    看了一圈好像都在打表。。。。
    我也凑个热闹吧

    class Solution {
    
        int[][] arr = {
            {1,1,0,0,0,0,0,0,0,0,0},
            {1,2,0,0,0,0,0,0,0,0,0},
            {1,4,0,0,0,0,0,0,0,0,0},
            {1,8,0,0,0,0,0,0,0,0,0},
            {2,1,6,0,0,0,0,0,0,0,0},
            {2,2,3,0,0,0,0,0,0,0,0},
            {2,4,6,0,0,0,0,0,0,0,0},
            {3,1,2,8,0,0,0,0,0,0,0},
            {3,2,5,6,0,0,0,0,0,0,0},
            {3,1,2,5,0,0,0,0,0,0,0},
            {4,0,1,2,4,0,0,0,0,0,0},
            {4,0,2,4,8,0,0,0,0,0,0},
            {4,0,4,6,9,0,0,0,0,0,0},
            {4,1,2,8,9,0,0,0,0,0,0},
            {5,1,3,4,6,8,0,0,0,0,0},
            {5,2,3,6,7,8,0,0,0,0,0},
            {5,3,5,5,6,6,0,0,0,0,0},
            {6,0,1,1,2,3,7,0,0,0,0},
            {6,1,2,2,4,4,6,0,0,0,0},
            {6,2,2,4,5,8,8,0,0,0,0},
            {7,0,1,4,5,6,7,8,0,0,0},
            {7,0,1,2,2,5,7,9,0,0,0},
            {7,0,1,3,4,4,4,9,0,0,0},
            {7,0,3,6,8,8,8,8,0,0,0},
            {8,1,1,2,6,6,7,7,7,0,0},
            {8,2,3,3,3,4,4,5,5,0,0},
            {8,0,1,4,6,6,7,8,8,0,0},
            {9,1,1,2,2,3,4,7,7,8,0},
            {9,2,3,4,4,5,5,6,6,8,0},
            {9,0,1,2,3,5,6,7,8,9,0},
            {10,0,1,1,2,3,4,4,7,7,8}
        };
    
        int[] sizeMap = {0,9,99,999,9999,99999,999999,9999999,99999999,999999999,2147483647};
    
        public boolean reorderedPowerOf2(int n) {
            if (n==0){
                return false;
            }
            int size = 0;
            //看看这个数字能转成多大的int[]数组
            for (int i = 0; i < sizeMap.length; i++) {
                if (sizeMap[i] >= n){
                    size = i;
                    break;
                }
            }
            int[] numArr = new int[size];
            //把n数字的个位置上的数字放入数组中
            while (n > 0){
                numArr[--size] = n % 10;
                n /= 10;
            }
            Arrays.sort(numArr);
            for (int[] ints : arr) {
                if (ints[0] == numArr.length){
                    int idx = 0;
                    while (++idx<=ints[0] && ints[idx] == numArr[idx-1]){}
                    if(--idx == ints[0] && ints[idx] == numArr[idx-1]){
                        return true;
                    }
                }
            }
            return false;
        }
    
    }