下一个排列

下一个排列
构造方式：从右往左找到第一个非递减的元素将其与右侧大于该元素的最小元素进行交换，将右边所有的元素进行逆置

class Solution {
    public void nextPermutation(int[] nums) {
        int n=nums.length;
        int k=n-1;
        while(k>0&&nums[k]<=nums[k-1]){
            k--;
        }
        k-=1;
        if(k<0){
            //将序列
            for(int i=0,j=nums.length-1;i<j;i++,j--){
                int t=nums[i];
                nums[i]=nums[j];
                nums[j]=t;
            }
        }else{
            int t=k+1;
            while(t<n&&nums[t]>nums[k]){
                t++;
            }
            //将对应的t与k进行交换
            t-=1;
            int temp=nums[k];
            nums[k]=nums[t];
            nums[t]=temp;

            for(int i=k+1,j=n-1;i<j;i++,j--){
                int tt=nums[i];
                nums[i]=nums[j];
                nums[j]=tt;
            }

        }

    }
}

寻找最近的回文数

寻找最近的回文数
先将长度小于n字符串的最大回文数，长度大于n字符串的最小回文数放入集合

class Solution {
     public String nearestPalindromic(String n) {
        long number=Long.parseLong(n);
        long res=-1;
        List<Long> candidates=getCandidate(n);
        for (Long candidate : candidates) {
            if(candidate!=number){
                //最接近的
                if(res==-1||Math.abs(candidate-number)<Math.abs(res-number)||(Math.abs(candidate-number)==Math.abs(res-number)&&candidate<res)){
                    res=candidate;
                }
            }
        }
        return String.valueOf(res);
    }

    public List<Long> getCandidate(String n){
        int len=n.length();
        //所有可能回文串
        List<Long> candidates=new ArrayList<>(){
            {
                add((long)Math.pow(10,len-1)-1);
                add((long)Math.pow(10,len)+1);
            }
        };
        //前缀
        long prefix=Long.parseLong(n.substring(0,(len+1)/2));
        for(long i=prefix-1;i<=prefix+1;i++){
            StringBuilder sb=new StringBuilder();
            String pre=String.valueOf(i);
            sb.append(pre);
            StringBuilder suf=new StringBuilder(pre).reverse();
             sb.append(suf.substring(len&1));
            String candidate=sb.toString();
            candidates.add(Long.parseLong(candidate));
        }
        return candidates;
    }
}

不含aaa和bbb字符串

不含aaa和bbb字符串
贪心策略：优先将剩余最多的字符使用，除非约束必须使用剩余次数更少的字符

class Solution {
    public String strWithout3a3b(int a, int b) {
       StringBuilder sb=new StringBuilder();
        while(a>0||b>0){
            boolean writea=false;
            //下一个是否写a
            if(sb.length()>=2&&sb.charAt(sb.length()-1)==sb.charAt(sb.length()-2)){
                //必须写a
                if(sb.charAt(sb.length()-1)=='b'){
                    writea=true;
                }
            }else{
                //贪心，优先a
                if(a>b){
                    writea=true;
                }
            }
            if(writea){
                sb.append('a');
                a--;
            }else{
                sb.append('b');
                b--;
            }
        }
        return sb.toString();
    }
}

单调递增的数字

单调递增的数字
贪心法

class Solution {
    public int monotoneIncreasingDigits(int n) {
        //通过构造的方式
        char[] s=Integer.toString(n).toCharArray();
        int index=1;
        for(int i=1;i<s.length;i++){
            if(s[i]>=s[i-1]){
                index++;
            }else{
                break;
            }
        }
        if(index<s.length){
            int idx=index;
            while(idx>0&&s[idx]<s[idx-1]){
                s[idx-1]=(char)(s[idx-1]-'0'-1+'0');
                // s[idx-1]-=1;
                idx--;
            }
            for(int i=idx+1;i<s.length;i++){
                s[i]='9';
            }
        }

        return Integer.parseInt(new String(s));
    }
}