Question 2 Iterator for Combination
Method 1
和刚才的题目一样
只不过字母不一定连续，但是保证了顺序是递增的
总结
Case 1: 已经处理完所有的位置，收集solution，减1把数字++
尝试把能的最后一位递增到原始given str中的下一位
Case 2:这个书自己超过了最大范围说明当前不合法必须回退到前一位
最大范围：这三位启示最大的就是原始given str中倒叙的后K位
对于查找谁是那个所谓的最高可以增大的位：倒叙遍历第一个不同的
最后一位找到了，他会变大成为谁呢？
Case 3:顺水推舟直到所有数字都递增
这一位以及这一位以后的所有字母都照搬given str
有一些浪费时间的String operation/use case
substring
indexOf
// Some code
class CombinationIterator {
char[] current;
String orignalStr;
boolean hasNext;
public CombinationIterator(String characters, int combinationLength) {
this.current = characters.substring(0,combinationLength).toCharArray();
this.originalStr = characters;
hasNext = true; // 注意CART
}
public String next(){
if (!hasNext) {
return "";
}
String result = new String(current);
int i = current.length - 1;
int j = originalStr.length() - 1;
while (i >= 0 && current[i] == originalStr.charAt(j)) {
i--;
j--;
}
if (i == -1) {
hasNext = false; // 没办法变化了
} else {
int index = priginalStr.indexOf(current[i]);
for (int k = i; k < current.length; k++) {
index++;
current[k] = originalStr.charAt(index);
}
}
return result;
}
public boolean hasNext(){
return this.hasNext;
}
}Method 2 看use case的情况：需要连续的情况下不真的连续--》 bit mask(bit operation)
bitmask: 我用一个数字代表我的选择
bit：要么0代表不选，要么1代表选（一个位置上，几个进制代表几个状态）
abcd：选与不选这些字母的问题其实就是这四位的数字里哪些是1，哪些是0
易错点
最小的mask是谁？最小的size combination 0011(cd)
开始的mask怎么做出来的呢？
ab --》 1100
一开始最小的combination = (1 << totalLength) - (1 << (totalLength - combinationLength))
// Some code
class CombinationIterator {
private int combinationLength;
private String originalStr;
private int totalLength;
private int minBitmask;
private int bitmask; //current
private boolean foundNext;
public CombinationIterator(String characters, int combinationLength) {
this.orginalStr = character;
this.combinationLength = combinationLength;
this.totalLength = characters.length();
this.bitmask = (1 << totalLength) - (1 << (totalLength - combinationLength));
this.foundNext = true;
this.minBitmask = (1 << comibinationLength) - 1;
}
public String next(){
if (!hasNext()) {
return "";
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < totalLength; i++) {
if ((bitmask & (1 << totalLength - 1 - i) != 0)) {
sb.append(originalStr.charAt(i));
}
}
foundNext = false;
return sb.toString();
}
public boolean hasNext(){
if (foundNext) {
return true;
}
if (bitmask < minBitmask) {
return false;
}
bitmask --;
while (bitmask >= minBitmask && Integer.bitCount(bitmask) != combinationLength) {
bitmask--;
}
foundNext = bitmask >= minBitmask;
return foundNext;
}
}API logic:
get next maskNumber:
能直接把currentmask 减1
1100（ab） - 1 = 1011(acd)
1011(acd) - 1= 1010(ac)
算法：逐次减1，直到得到hamming weight 和combinationLength一样的第一个mask
如何对应上Mask和String：bitGetter 把对应位是1的位填补位originalStr中对应character对于第i个index，是否要把它加到现在的current result里
（currentMask & (1 << n - 1 - i)）!= 0
Side Problem 1: Number of 1Bits
Method 1: Java Library:
return Integer.bitCount(n);
Method 2: 自己实现
// Some code
int count = 0;
while (n != 0) {
count += (n & 1);
n >>> 1;
}
return count;Method 3：技巧
// Some code
int count = 0;
while (n! = 0) {
n = n & (n - 1);
count++;
}
return count;竞赛技巧： n& (n - 1)是什么意思
把n的二进制表示中最低的上的1改成0
example
n = 0b10100, n-1 = 0b10011
n & n-1 = 0b10000
example: 判断一个数字是不是2的幂次方
return n > 0 && (n & (n - 1) == 0)
Side Problem 2: Hamming Distance
本质上就是异或之后的数字中的hamming weight是多少
// Some code
public int hammingDistance(int x, int y) {
int number = x ^ y;
int count = 0;
while (number != 0) {
number = number & (number - 1);
count++;
}
return distance;
}Last updated