leetcode——每日一題(最大、最小數字元拼接問題)

179. 最大數

使用的全排列的時候肯定是超過時間的記憶體的限制了，是以需要思考的是怎麼怎麼樣構成最大的數字 怎麼樣是才能構成最小的數字。

package leetode每日一題;

import org.junit.Test;
import 牛客網練習題.Solution;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 * @Classname 最大的數字179 就是一個的重新組合的數字問題
 * @Description TODO
 * @Date 2021/4/12 10:03
 * @Created by xjl
 */
public class 最大的數字179 {

    @Test
    public void test() {
        String s = largestNumber(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 0});
        System.out.println("res=" + s);
    }

    public String largestNumber(int[] nums) {
        int n = nums.length;
        String numsToWord[] = new String[n];
        for (int i = 0; i < n; i++) {
            numsToWord[i] = String.valueOf(nums[i]);
        }
        //compareTo()方法比較的時候是按照ASCII碼逐位比較的
        //通過比較(a+b)和(b+a)的大小，就可以判斷出a,b兩個字元串誰應該在前面
        //是以[3,30,34]排序後變為[34,3,30]
        //[233，23333]排序後變為[23333，233]
        Arrays.sort(numsToWord, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);
            }
        });
        //如果排序後的第一個元素是0，那後面的元素肯定小于或等于0，則可直接傳回0
        if (numsToWord[0].equals("0")) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(numsToWord[i]);
        }
        return sb.toString();
    }

    String result = "";

    public String largestNumber2(int[] nums) {
        if (nums.length == 1) return String.valueOf(nums[0]);
        String[] arr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = String.valueOf(nums[i]);
        }

        ArrayList<String> list = new ArrayList<>();
        boolean[] vis = new boolean[arr.length];
        //開始通路的位置
        int index = 0;
        dfs(list, vis, index, arr);
        return result;
    }

    private void dfs(ArrayList<String> list, boolean[] vis, int index, String[] arr) {
        //表示周遊完成
        if (index == arr.length) {
            if (list.get(0) != "0") {
                //将list中的資料便成為string
                String res = "";
                for (String s : list) {
                    res += s;
                }
                result = result.compareTo(res) > 0 ? result : res;
            }
        } else {
            for (int i = 0; i < arr.length; i++) {
                if (vis[i] == false) {
                    vis[i] = true;
                    list.add(arr[i]);
                    dfs(list, vis, index + 1, arr);
                    //删除的最後的添加來的數字 進行回溯的算法
                    list.remove(list.size() - 1);
                    vis[i] = false;
                }
            }
        }
    }
}
           

劍指 Offer 45. 把數組排成最小的數

package leetode每日一題;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Classname 最小數字45
 * @Description TODO
 * @Date 2021/4/12 11:23
 * @Created by xjl
 */
public class 最小數字45 {

    @Test
    public void test(){
        String s = minNumber(new int[]{3,30,34,5,9});
        System.out.println(s);
    }

    public String minNumber(int[] nums) {
        String[] arr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
        }
        return sb.toString();
    }
}