Sword finger Offer 57 - II Continuous positive sequence with sum s

1. Title

Enter a positive integer target, and output a sequence of consecutive positive integers whose sum is target (containing at least two numbers).

The numbers in the sequence are arranged from small to large, and different sequences are arranged from small to large according to the first number

2. Problem solution

Method 1: backtracking algorithm

At first glance, this problem looks like a classic backtracking algorithm, so it pops out, and the result is a classic overtime slap in the face.

Method 2: double pointer + sliding window

If the left bound i and the right bound j of the continuous positive integer sequence are set, the sliding window can be constructed to slide from left to right. In the cycle, judge the size relationship between the elements in the sliding window and the target value target in each round. If it is equal, record the result. If it is greater than target, move the left boundary i (to reduce the sum of elements in the window), and if it is less than target, move the right boundary j (to increase the sum of elements in the window).

Algorithm flow:

1. Initialization: left bound i = 1, right bound j = 2, element sum = 3, result list res;

2. Cycle: jump out when i ≥ j;

   • When s > target: move the left boundary i = i + 1 to the right and update the element and sum;
   • When s < target: move the right boundary j = j + 1 to the right and update the element and sum;
   • When s = target: record the continuous integer sequence and move the left bound to the right, i = i + 1;

3. Return value: returns the result list res;

3. Code

Method 1: backtracking, timeout

class Solution {

    List<int[]> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public int[][] findContinuousSequence(int target) {
        backtrack(target, 1, 0);

        // int[][] result = new int[res.size()][];
        // for(int i = 0;i < res.size();i++){
        //     int[] array = res.get(i).stream().mapToInt(j->j).toArray();
        //     result[i] = array;
        // }
        return res.toArray(new int[res.size()][]);
    }

    public void backtrack(int target, int k, int sum){
        if(target == sum){
            res.add(path.stream().mapToInt(j->j).toArray());
            return;
        }

        for(int i = k;i < target;i++){
            if(path.size() > 0 && (path.get(path.size() - 1) + 1) != i){
                continue;
            }

            sum += i;   
            path.add(i);
            backtrack(target, i + 1, sum);
            sum -= i;
            path.remove(path.size() - 1);
            
        }
    }
}

Method 2: double pointer + sliding window

class Solution {

    public int[][] findContinuousSequence(int target) {
        int i = 1, j = 2, sum = 3;
        List<int[]> res = new ArrayList<>();
        while(i < j){
            if(sum == target){
                int[] path = new int[j - i + 1];
                for(int k = i;k <= j;k++){
                    path[k - i] = k;
                }
                res.add(path);
            }
            if(sum >= target){
                sum -= i;
                i++;
            }else{
                j++;
                sum += j;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

Sword finger Offer 51 Reverse order pair in array

1. Title

The N numbers 0,1, ····, n-1 are arranged in a circle, starting from the number 0, and the m-th number is deleted from the circle each time (counting from the next number after deletion). Find the last number left in the circle.

For example, the five numbers 0, 1, 2, 3 and 4 form a circle. Starting from the number 0, delete the third number each time, then the first four deleted numbers are 2, 0, 4 and 1 in turn, so the last remaining number is 3.

2. Problem solution

Method 1: simulation
Find the location index to be deleted each time, record the index, and then cycle.

Method 2: mathematical formula

3. Code

Method 1: simulation

class Solution {
    public int lastRemaining(int n, int m) {
        List<Integer> list = new ArrayList<>(n);
        for(int i = 0;i < n;i++){
            list.add(i);
        }

        int index = 0;
        while(n > 1){
            index = (index + m - 1) % n;
            list.remove(index);
            n--;
        }
        return list.get(0);

    }
}

Method 2: mathematical formula

class Solution {
    public int lastRemaining(int n, int m) {

        int count = 0;
        // There are 2 people left in the last round, so start from 2
        for (int i = 2; i <= n; i++) {
            count = (count + m) % i;
        }
        return count;

    }
}

Reference: K God Muyi