未分类题目

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is impossible, it must rearrange it to the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

解法：找到最后一个递增pair位置交换他们的位置，然后将A位置后的序列进行排序

class Solution {
    public void nextPermutation(int[] nums) {
        int left=-1,right=-1;
        //找到最后一个递增pair
        boolean flag=false;
        for(int i=nums.length-2;i>=0 &&!flag;i--){
            for(int j=nums.length-1;j>i;j--){
                if(nums[j]>nums[i]){
                    left=i;right=j;
                    flag=true;
                    break;
                }
            }
        }
        if(left!=-1) {
            //交换位置left right
            int temp = nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
        }
        //将left之后的数字重新排序
        Arrays.sort(nums,left+1,nums.length);
    }
}

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

class Solution {
    public double myPow(double x, int n) {
        long N=n;
        if(N<0){
            x = 1/x;
            N=-N;
        }
        double curr_p=x;
        double result = 1;
        for(long i=N;i>0;i=i/2){
            if(i%2==1) result*=curr_p;
            curr_p*=curr_p;
        }
        return result;
    }
}