Cousera OA1

Problem1-Array Reduction

import java.util.*;
public class ArrayReduction {
    public int mincost(int[] nums){
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for(int num : nums) heap.offer(num);
        int minval = 0;
        while(heap.size()>1){
            int crtcost = heap.poll()+heap.poll();
            minval += crtcost;
            heap.offer(crtcost);
        }
        return minval;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ipt = new int[n];
        for(int i=0;i<n;i++) ipt[i] = sc.nextInt();
        ArrayReduction test = new ArrayReduction();
        System.out.println(test.mincost(ipt));
    }
}

Problem2-Royal Names

import java.util.*;
public class RoyalNames {
    public String[] sortName(String[] names){
        Arrays.sort(names, new Comparator<String>(){
            public int compare(String a, String b){
                String[] c1 = a.split(" ");
                String[] c2 = b.split(" ");
                if(!c1[0].equals(c2[0])) return c1[0].compareTo(c2[0]);
                else return romanToInt(c1[1])-romanToInt(c2[1]);
            }
        });
        return names;
    }
    private int romanToInt(String s) {
        HashMap<Character,Integer> map = new HashMap<>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);
        int val = 0;
        int prev = Integer.MAX_VALUE;
        for(char c : s.toCharArray()){
            int crt = map.get(c);
            if(prev<crt) val -= prev*2;
            val += crt;
            prev = crt;
        }
        return val;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        String[] ipt = new String[n];
        for(int i=0;i<n;i++) ipt[i] = sc.nextLine();
        RoyalNames test = new RoyalNames();
        System.out.println(Arrays.toString(test.sortName(ipt)));
    }
}

Problem3-LastSubstring

返回一个string的所有substring按字典顺序排序后的最后一个substring. 例子："acb"的substring排序{"a", "ac", "acb", "b", "c", "cb"}， 返回"cb" 。

import java.util.*;
public class LastSubstring {
    public String laststring(String s){
        char c = 'a';
        for(int i=0;i<s.length();i++){
            char crt = s.charAt(i);
            if(crt>c) c = crt;
        }
        String max = "";
        for(int i=0;i<s.length();i++){
            char crt = s.charAt(i);
            if(crt==c&&max.compareTo(s.substring(i))<0){
                max = s.substring(i);
            }
        }
        return max;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String ipt = sc.next();
        LastSubstring test = new LastSubstring();
        System.out.println(test.laststring(ipt));
    }
}

Problem4-Loves Number

主要就是给定一个数比如说n, 求0-n之间有多少个数，这些数的每一位的数字都不相同。 比如说n是3645，首先把1位数求出来，然后求出来2位数的，再是3位数的，但是4位数的因为有限制，所以开始分类讨论，当第一个数字为1或者2的时候，因为后面的数字可以随便选，所以当数字为1或者2时有9x8x7种,然后把第一位固定为3，对后面的情况再依次讨论

import java.util.*;
public class LoveNum {
    private int[] DP;//DP[i] means the unique number that i digits have 
    public LoveNum(){
        DP = new int[11];
        DP[0] = 1;
        DP[1] = 10;
        DP[2] = 81;
        for(int i=3;i<=10;i++) DP[i] = DP[i-1]*(11-i);
    }
    private int UniqNumCnt(int n){
        if(n==0) return 1;//handle base case
        List<Integer> num = new ArrayList<>();
        int cntdigt = 0;//count for total digits of n
        while(n!=0){
            num.add(n%10);
            cntdigt++;
            n /= 10;
        }//store all the digits to num array
        Collections.reverse(num);//reverse the digit order
        int cnt = 0;//the result count 
        //first calculate unique number that has smaller digits than n
        for(int i=1;i<cntdigt;i++) cnt += DP[i];
        //store the used digits
        HashSet<Integer> used = new HashSet<>();
        for(int i=0;i<num.size();i++){
            int digt = num.get(i);//get digit from num array from left to right
            //let's take 7 for example
            //if this digit is 7, then we need to calculate 1***,2***,3***...6***
            int count = 1;
            for(int j=1;j<cntdigt;j++) count *= 10-used.size()-j;//so now count is for 1***;
            //loop from 0 to 7
            for(int j=0;j<=digt;j++){
                if(i==0&&j==0) continue;//if this digit is first, then ingore 0
                if(i!=num.size()-1&&j==digt) continue;//if this digit is last, we should count 7
                if(!used.contains(j)) cnt += count;//if this digit is not used, calculate
            }
            cntdigt--;//then reduce this val proceed to next digit
            if(!used.add(digt)) break;//if this digit is used before, then we're done
        }
        return cnt;
    }
    public static void main(String[] args) {
        LoveNum test = new LoveNum();
        Scanner sc = new Scanner(System.in);
        int ipt = sc.nextInt();
        System.out.println(test.UniqNumCnt(ipt));
    }
}

Problem5-Segment

Minimum Sliding Window Problem

import java.util.*;
public class MinWindow {
    public int minSlidingWindow(int[] nums, int k){
        Deque<Integer> dq = new ArrayDeque<>();
        int rst = Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            while(!dq.isEmpty() && i-dq.peekFirst()+1>k) dq.pollFirst();
            while(!dq.isEmpty() && nums[dq.peekLast()]>=nums[i]) dq.pollLast();
            dq.offerLast(i);
            if(i>=k-1 && nums[dq.peekFirst()] > rst) rst = nums[dq.peekFirst()];
        }
        return rst;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++) nums[i] = sc.nextInt();
        MinWindow test = new MinWindow();
        System.out.println(test.minSlidingWindow(nums,k));
    }
}