一道算法题

梦里梦外; 2021-12-23 06:31 324阅读 0赞

package test.algo;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.LinkedHashMap;
    import java.util.List;
    import java.util.Map;
    
    /**
     * 一道算法题，原题是：
     * 
     * 字符串的完美度
     * 我们要给每个字母配一个1-26之间的整数，具体怎么分配由你决定，但不同字母的完美度不同， 
    而一个字符串的完美度等于它里面所有字母的完美度之和，且不在乎字母大小写，
    也就是说字母F和f的完美度是一样的。 
    现在给定一个字符串，输出它的最大可能的完美度。 
    例如：dad，你可以将26分配给d，25分配给a，这样整个字符串最大可能的完美度为77。
    
     * @author lushuaiyin
     *
     */
    public class TestMain {
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		String ss="abcAdG";
    		int[] arr=resort(getCharMap(ss));
    		printResult(arr);
    	}
    	
    	public static void printResult(int[] arr){
    		int[] value=new int[26];
    		int k=26;
    		for(int i=0;i<value.length;i++){
    			value[i]=k;
    			k--;
    		}
    		
    		int sum=0;
    		for(int i=0;i<arr.length;i++){
    			sum+=arr[i]*value[i];
    			System.out.println("累加一次："+arr[i]+"*"+value[i]+"="+arr[i]*value[i]);
    		}
    		System.out.println("最后完美度是："+sum);
    	}
    	
    	public static Map  getCharMap(String str){
    		Map m=new HashMap();
    		if(str==null||str.trim().equals("")){
    			
    		}else{
    			str=str.trim();
    			str=str.toLowerCase();
    			for(int i=0;i<str.length();i++){
    				char c=str.charAt(i);
    				if(m.containsKey(c)){
    					int number=(Integer)m.get(c);
    					number++;
    					m.put(c, number);
    				}else{
    					m.put(c, 1);
    				}
    			}
    		}
    		System.out.println(m.toString());
    		return m;
    	}
    	
    	public static int[] resort(Map m){
    		int[] arr=new int[m.size()] ;
    		
    		List ll=new ArrayList();
    		if(m==null||m.size()<=0){
    			
    		}else{
    			Iterator it=m.keySet().iterator();
    			for(int i=0;it.hasNext();){
    				char key=(Character)it.next();
    				int value=(Integer)m.get(key);
    				
    				//排序
    				ll.add(value);
    				Collections.sort(ll);
    				Collections.reverse(ll);
    			}
    		}
    		//打印
    		String res="";
    		for(int h=0;h<ll.size();h++){
    			int oo=(Integer)ll.get(h);
    			arr[h]=oo;
    			if(h==ll.size()-1){
    				res+=oo;
    			}else{
    				res+=oo+",";
    			}
    		}
    		System.out.println(res);
    		return arr;
    	}
    	
    	
    }
    
    /*
    {g=1, d=1, b=1, c=1, a=2}
    2,1,1,1,1
    累加一次：2*26=52
    累加一次：1*25=25
    累加一次：1*24=24
    累加一次：1*23=23
    累加一次：1*22=22
    最后完美度是：146
    
     */