Leetcode20双周赛

本次排名:426 / 1541
第一题：根据数字二进制下 1 的数目排序
解题思路：把目标数组转成二进制，然后排序统计排序即可（之前代码是使用Pair存储，但是leetcode导包后没识别出来？？？然后换成List了）
代码：

class Solution {
    public int[] sortByBits(int[] arr) {
        int[] acc = new int[arr.length];
		List<List<Integer>> list =new ArrayList<>();
		for (int i = 0; i < arr.length; i++) {
			String string = Integer.toBinaryString(arr[i]);
			int t = 0;
			for (int j = 0; j < string.length(); j++) {
				if (string.charAt(j)=='1'){
					t++;
				}
			}
			acc[i]=t;
			List<Integer> temp = new ArrayList<>();
			temp.add(arr[i]);
			temp.add(acc[i]);
			list.add(temp);
		}
		Collections.sort(list, new Comparator<List<Integer>>() {
			@Override
			public int compare(List<Integer> o1, List<Integer> o2) {
				if (o1.get(1).equals(o2.get(1))){
					return o1.get(0)-o2.get(0);
				}
				return o1.get(1)-o2.get(1);
			}
		});
		int[] ans = new int[acc.length];
		for (int i = 0; i < list.size(); i++) {
			ans[i]=list.get(i).get(0);
		}
		return ans;
    }
}

第二题：每隔 n 个顾客打折
解题思路：一道简单的构造题，可以利用Map存储每一件商品的id与价格，然后一个全局变量统计用户的购买次数，以此来判断折扣。

class Cashier {
	int num = 0;
	int discountNum = 0;
	Map<Integer,Integer> pri;
	int flag = 0;
	public Cashier(int n, int discount, int[] products, int[] prices) {
		num = n;
		discountNum = discount;
		pri = new HashMap<>();
		for (int i = 0; i < products.length; i++) {
			pri.put(products[i],prices[i]);
		}
	}

	public double getBill(int[] product, int[] amount) {
		flag++;
		double a = 0;
		for(int i = 0;i<product.length;i++){
			int k = pri.get(product[i]);
			a+=k*amount[i];
		}
		if(flag%num==0){
			a = a - (discountNum * a) / 100;
		}
		return a;
	}
}

第三题：包含所有三种字符的子字符串数目
解题思路，题目提示说相同的字符串算多次，那么我们只要找到了首次满足条件的子字符串，那么后面的字符串也就一定满足，但是如果用简单的双循环碰到极端情况下算法的复杂度为O（n^2）,会超时，所以这里用了一个简单的判断，判断abc三个字母最开始出现的位置，来决定从头开始遍历，还是从后面开始遍历。（其实也不用这么麻烦，利用双指针也直接可以做。。。）

class Solution {
    public int numberOfSubstrings(String s) {	
        if (s.indexOf('a')>=s.length()/2 || s.indexOf('b')>=s.length()/2 ||s.indexOf('c')>=s.length()/2 ){
			int ans =0;
			for (int i = s.length()-1; i >=0 ; i--) {
				int a=0,b=0,c=0;
				int flag =0;
				for (int j = i; j >=0 ; j--) {
					if (s.charAt(j)=='a')a++;
					if (s.charAt(j)=='b')b++;if (s.charAt(j)=='c')c++;
					if (a>=1&&b>=1&&c>=1){
						flag=j+1;
						break;
					}
				}
				if (flag==0)break;
				ans+=flag;
			}
			return ans;
		}
		int ans =0;
		for (int i = 0; i < s.length(); i++) {
			int a=0,b=0,c=0;
			int flag =0;
			for (int j = i; j <s.length() ; j++) {
				if (s.charAt(j)=='a')a++;
				if (s.charAt(j)=='b')b++;if (s.charAt(j)=='c')c++;
				if (a>=1&&b>=1&&c>=1){
					flag=s.length()-j;
					break;
				}
			}
			if (flag==0)break;
			ans+=flag;
		}
		return ans;
    }
}