# Monthly Archives: August 2019

## UML Arrows

Aggregation

Books is a part of Library. Dismiss of Library, it won’t lead dismiss of books. ```class Library {
Book book;
}

```

Composition

Library has books. Dismiss of Library, then books will be dismissed as well. ```class Library {
Book book;

}```

Generalization/Extends

BankAccount implements Fixed Account ```class BankAccount extends FixedAccount {
}

```

Realization/Inheritance

BankAccount extends Fixed Account ```class PrinterSetup implements Printer {
}

```

Reference:

Class Diagram relationship

difference between association vs composition vs aggregation

## lc 600. Non-negative Integers without Consecutive Ones

100100001000

One[i]:  1XXXXXXXXXXXXX

Zero[i]: 1XXXXXXXXXXXXX

Zero[i] = zero[i + 1] + one[i + 1];

One[i] = zero[i]

One[i] is the number of combination without continuous 11, with MSB 1

Zero[i] is the number of combination without continuous 11, with MSB 0

Then go over from MSB to LSB.

XX 0 1 YY      1)

XX 1 0 YY      2)

XX 1 1 YY       3) illegal

Are the ones greater than XX00YY. But XX11YY is illegal, we will get rid of it.

Assume next one is also 00:XXX00Y

We know still it is:

XXX 1 0 Y     4) was covered by 1

XXX 0 1 Y     5)

XXX 1 1 Y     6)  illegal

We can see XXX10Y is already included in previous round. So we know, if we meet continuous XX00YY, we need to get rid of XX01YY.

Besides, we need to stop when we see 11(the two continuous 1).

```public static int findIntegers(int num) {
String str = new StringBuilder(Integer.toBinaryString(num)).toString();
int zero[] = new int[str.length()], one[] = new int[str.length()];
one[str.length() - 1] = zero[str.length() - 1] = 1;
for (int i = str.length() - 2; i >= 0; i--) {
zero[i] = zero[i + 1] + one[i + 1];
one[i] = zero[i + 1];
}
int ans = one + zero;
for (int i = 1; i < one.length; i++) {
if (str.charAt(i) == '1' && str.charAt(i - 1) == '1') {
break;
}
if (str.charAt(i) == '0' && str.charAt(i - 1) == '0') {
ans -= one[i];
}
}
return ans;
}```