ARTS （第49周）

很多事情，结果好与不好，哪种最好，都要经历过，尝试过才知道。

勇于尝试。

Algorithm 算法

丑数

1
2

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b?tpId=13&tqId=11186&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法动态规划

每次维护最小的那个丑数队列。

public int GetUglyNumber_Solution(int index) {
		if (index < 7)
			return index;
		int[] res = new int[index];
		res[0] = 1;
		int p2 = 0, p3 = 0, p5 = 0;
		int r2 = 0;
		int r3 = 0;
		int r5 = 0;
		for (int i = 1; i < index; i++) {
			r2 = res[p2] * 2;
			r3 = res[p3] * 3;
			r5 = res[p5] * 5;
			res[i] = Math.min(r2, Math.min(r3, r5));
			if (res[i] == r2) {
				p2++;
			}
			if (res[i] == r3) {
				p3++;
			}
			if (res[i] == r5) {
				p5++;
			}

		}
	//	System.out.println(Arrays.toString(res));
		return res[index-1];
	}

把数组排成最小的数

1
2

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
https://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993?tpId=13&tqId=11185&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1 排序

两个字符s1,s2俩俩比较，如果s1拼接s2的结果比s2拼接s1的结果更小，那么s1就应该排在前面。


public String PrintMinNumber(int[] numbers) {
	if (numbers == null || numbers.length == 0)
		return "";
	String[] s = new String[numbers.length];
	for (int i = 0; i < s.length; i++) {
		s[i] = String.valueOf(numbers[i]);
	}
	sort(s);
	String res = s[0];
	for (int i = 1; i < s.length; i++) {
		res += s[i];
	}
	return res;
}

private void sort(String[] s) {
     //最简单的冒泡排序
	for (int i = 0; i < s.length; i++) {
		for (int j = i + 1; j < s.length; j++) {
			if (compare(s[i], s[j]) > 0) {
				String temp = s[i];
				s[i] = s[j];
				s[j] = temp;
			}
		}
	}

}

private int compare_(String s1, String s2) {
	String a = s1 + s2;
	String b = s2 + s1;
	return a.compareTo(b);
}

解法2

其它东西一样，不过比较方法换了，变成短的数字循环和长的数字比较（短的数字匹配完了就重新再来一轮匹配）

	public String PrintMinNumber(int[] numbers) {
		if (numbers == null || numbers.length == 0)
			return "";
		String[] s = new String[numbers.length];
		for (int i = 0; i < s.length; i++) {
			s[i] = String.valueOf(numbers[i]);
		}
		sort(s);
		String res = s[0];
		for (int i = 1; i < s.length; i++) {
			res += s[i];
		}
		return res;
	}

	private void sort(String[] s) {
		for (int i = 0; i < s.length; i++) {
			for (int j = i + 1; j < s.length; j++) {
				if (compare(s[i], s[j]) > 0) {
					String temp = s[i];
					s[i] = s[j];
					s[j] = temp;
				}
			}
		}

	}
// 短字符串循环比较 和长字符串
	// 同样符合题意 越小的数字越应该靠前
	public int compare(String o1, String o2) {
		int i = 0, j = 0;
		while (i < o1.length() || j < o2.length()) {
			if (j == o2.length())
				j -= o2.length();
			if (i == o1.length())
				i -= o1.length();
			if (o1.charAt(i) < o2.charAt(j)) {
				return -1;
			} else if (o1.charAt(i) > o2.charAt(j)) {
				return 1;
			}
			i++;
			j++;
		}
		return 0;
	}

布隆过滤器完整实现

位图



/**
 * 位图
 * 
 * @author la-huan
 *
 */
public interface BitMap {
	/**
	 * 设置位图大小
	 * @param s
	 */
	public void setSize(int s);
	/**
	 * 设置为某位true
	 * @param idx
	 */
	public void setTrue(int idx);
	/**
	 * 设置为某位false
	 * @param idx
	 */
	public void setFalse(int idx);
	/**
	 * 获取某位
	 * @param idx
	 */
	public boolean get(int idx);
}



/**
 * 位图的内存实现 辅助给布隆过滤器使用
 * 
 * @author la-huan
 *
 */
public class BitMapMemoryImpl implements BitMap {
	private int[] bytes;// c
	private int size = 0;

	public BitMapMemoryImpl(int size) {
		if (size <= 0)
			throw new UnsupportedOperationException("size不可以小于等于0");
		this.size = size;
		bytes = new int[size / 32 + 1];
	}

	public BitMapMemoryImpl() {
	}

	public int getSize() {
		return size;
	}
	// public void print() {
	// for (int i = 0; i < size; i++) {
	// System.out.print((get(i) ? "1" : "0") + ",");
	// }
	// System.out.println();
	// }

	public void setTrue(int idx) {
		int arrIdx = idx / 32;// 数组索引
		int byteIdx = idx % 32;// byte索引
		// 二进制的或计算
		bytes[arrIdx] |= (1 << byteIdx);
	}

	public void setFalse(int idx) {
		int arrIdx = idx / 32;// 数组索引
		int byteIdx = idx % 32;// byte索引
		// 索引反码 然后与计算
		bytes[arrIdx] &= (~(1 << byteIdx));
	}

	public boolean get(int idx) {
		int arrIdx = idx / 32;// 数组索引
		int byteIdx = idx % 32;// byte索引
		// 二进制的与计算
		// (1 << byteIdx))的二进制只有byteIdx位置会是1 其它都是0
		// 所以结果如果为0 就是false 其它情况则是true
		return (bytes[arrIdx] & (1 << byteIdx)) != 0;

	}

	@Override
	public void setSize(int size) {
		if (size != 0)
			throw new UnsupportedOperationException("size只可以构造一次");
		this.size = size;
		bytes = new int[size / 32 + 1];
	}

}

布隆过滤器



/**
 * 布隆过滤器工具
 * 
 * @author la-huan
 *
 */

public class BloomFilter {
	private BitMap bitmap;// 位图
	private BloomHash[] hashs = new BloomHash[5];// 固定5个hash算法

	public BloomFilter() {
		// 位图大小设置为Integer.MAX_VALUE 即0和正数都包含
		//在这里我曾经纠结bitmap这样设置是否能够存放第Integer.MAX_VALUE个数据
		//后面debug后发现 Integer.MAX_VALUE除以32是不能整除的(余数31),因为Integer.max = 2^31-1.
		//因此刚好有一个位置的冗余，可以存放第Integer.MAX_VALUE个数据
		bitmap = new BitMapMemoryImpl(Integer.MAX_VALUE);
		// 固定5个哈希算法
		hashs[0] = new JavaHash();
		hashs[1] = new Md5Hash();
		hashs[2] = new SimpleHash(1);
		hashs[3] = new Md5Hash("salt");
		hashs[4] = new SimpleHash(2);
	}

	public boolean contains(String url) {
		if (url == null) {
			return false;
		}
		for (BloomHash f : hashs) {
			if (!bitmap.get(f.hash(url))) {
				return false;
			}
		}
		return true;
	}

	
	public boolean filter(String url) {
		// 计算所有的hash
		int h = 0;
		boolean ret = true;
		for (int i = 0; i < hashs.length; i++) {
			h = hashs[i].hash(url);
			ret = ret && bitmap.get(h);
			bitmap.setTrue(h);
		}
		if (ret) {
			// 5个hash对应位置都是true,代表这个数据是重复的（有几率误判，但不妨碍大局）
			return false;
		}
		return true;
	}
	
}

哈希算法

/**
 * 给布隆过滤器用的 hash
 * @author la-huan
 *
 */
public interface BloomHash {
	/**
	 * 给布隆过滤器用的 hash
	 * 要求返回值在在0x00000000~0x7FFFFFFF之间(正数以及0)
	 * @param url
	 * @return
	 */
	int hash(String url);
	
}



/**
 * 调用java的hash
 * @author la-huan
 *
 */
public class JavaHash implements BloomHash{

	@Override
	public int hash(String url) {
		return url.hashCode() & (Integer.MAX_VALUE);
	}
	
	
}



import com.lahuan.common.util.MD5Util;

/**
 * md5实现hash
 * @author la-huan
 *
 */
public class Md5Hash implements BloomHash{
	private String salt="";
	public Md5Hash() {
	}
	public Md5Hash(String salt) {
		this.salt = salt;
	}
	
	@Override
	public int hash(String url) {
		// Integer.MAX_VALUE是掩码 屏蔽首位符号位 最终显示0或正数
		return MD5Util.string2MD5Salt(url,salt).hashCode() & Integer.MAX_VALUE;
	}

}



/**
 * 简易的哈希算法
 *
 */
public class SimpleHash implements BloomHash {
	private int seed;

	public SimpleHash(int seed) {
		// this.cap = cap;
		this.seed = seed;
	}

	public int hash(String url) {
		int res = 0;
		for (int i = 0; i <  url.length(); i++) {
			res = seed * res + url.charAt(i);
		}
		// Integer.MAX_VALUE是掩码 屏蔽首位符号位 最终显示0或正数
		return Integer.MAX_VALUE & res;
	}
}

Review 英文文章

http://kafka.apache.org/uses

kafka使用案例

Tip 技巧

windows桌面程序的开发到底选用什么界面技术

不跨平台，小项目，功能为先，界面次要就winform，这货还是可靠的
不跨平台，环境较高级，对界面有一定要求，就WPF，
跨平台，撸QT吧

来自https://bbs.csdn.net/topics/392341830

kafka是不是分区越多越好

一、客户端/服务器端需要使用的内存就越多

二、文件句柄的开销

三、降低高可用性

其实最好的情况还是要将各种情况都多测试看看。

来自https://www.jianshu.com/p/dbbca800f607

https://www.jianshu.com/p/dbbca800f607 Kafka的分区数和消费者个数

https://bbs.csdn.net/topics/392341830 windows桌面程序的开发到底选用什么界面技术

https://blog.csdn.net/zhiboshequ/article/details/104485987 如何搭建一个优酷、爱奇艺这样的视频网站，都会有哪些技术难点？