lingguang1997
BAN USERT(n)=(2n)!/(n)!*(n+1)!
seems correct, how do u get it?
Thanks
a non-recursive way:
template <typename T>
void BinaryTree<T>::mirror() {
queue<BinaryTreeNode<T> *> q;
if (root) {
q.push(root);
while (!q.empty()) {
BinaryTreeNode<T> *front = q.front();
q.pop();
BinaryTreeNode<T> *temp = front->getLeftChild();
front->setLeftChild(front->getRightChild());
front->setRightChild(temp);
if (front->getLeftChild()) {
q.push(front->getLeftChild());
}
if (front->getRightChild()) {
q.push(front->getRightChild());
}
}
}
}
- lingguang1997 August 10, 2013assume the array is already sorted in ascending order.
vector<vector<int>> p15(int array[], int arrayLen, int sum) {
if (array != NULL) {
if (arrayLen == 1) {
if (array[0] >= sum) {
vector<int> v(1, array[0]);
vector<vector<int>> rr(1, v);
return rr;
}
vector<vector<int>> r;
return r;
} else if (arrayLen > 0) {
vector<vector<int>> r;
for (int i = arrayLen - 1; i >= 0; i--) {
int diff = sum - array[i];
vector<vector<int>> vect = p15(array, i, diff);
if (vect.size() > 0) {
for (vector<vector<int>>::iterator it = vect.begin(); it != vect.end(); it++) {
it->push_back(array[i]);
}
r.insert(r.end(), vect.begin(), vect.end());
}
if (array[i] >= sum) {
vector<int> v(1, array[i]);
vector<vector<int>> rr(1, v);
r.insert(r.end(), rr.begin(), rr.end());
}
}
return r;
}
}
vector<vector<int>> r;
return r;
}
- lingguang1997 August 10, 2013idea:
Step 1: Sort the array in an acending order
Step 2: Iterater from the end of the array, get the diff between the current elem and the sum, say sum1.
then the problem's order gets decreased by 1, it is equivalent to ask, find the subset of the array[1, n-1], which have sum >= sum1. Then integrate the results of all subproblems.
I think both greedy and dynamic are work.
greedy:
int getMaxDenomination(map<int, int> m, int change) {
int max = -1;
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
if (it->second > 0 && it->first > max && it->first <= change) {
max = it->first;
}
}
return max;
}
bool supply(map<int, int> m, int change) {
assert(change > 0);
int max = getMaxDenomination(m, change);
if (max != -1) {
if (change - max > 0) {
m[max] = m[max] - 1;
return supply(m, change - max);
} else {
return true;
}
} else {
return false;
}
}
void main() {
map<int, int> m;
m[1] = 2; // has 2 pennies
m[5] = 3;
m[25] = 4;
m[50] = 12;
m[100] = 1;
cout << supply(m, 20) << endl;
}
Generate a identity for each word based on counted bit vector.
- lingguang1997 September 27, 2015#import <Foundation/Foundation.h>
@interface BitVectorWithOccurences : NSObject <NSCopying>
@property (nonatomic) NSUInteger count;
- (void)setBitVectorByIndex:(CFIndex)index;
- (UInt8)getSetCountByIndex:(CFIndex)index;
- (void)reset;
@end
#import "BitVectorWithOccurences.h"
static const NSUInteger kBitVectorWithOccurencesCountDefault = 26;
static const NSUInteger kBitsPerByte = 8;
@interface BitVectorWithOccurences ()
@property (nonatomic) CFMutableBitVectorRef bitVector;
@end
@implementation BitVectorWithOccurences
- (instancetype)init {
if (self = [super init]) {
_bitVector = CFBitVectorCreateMutable(NULL, 0);
self.count = kBitVectorWithOccurencesCountDefault;
}
return self;
}
- (void)setCount:(NSUInteger)count {
if (_count != count) {
_count = count;
[self reset];
}
}
- (void)reset {
CFIndex bitsPerUnit = sizeof(UInt8) * kBitsPerByte;
CFBitVectorSetCount(_bitVector, bitsPerUnit * _count);
CFBitVectorSetAllBits(_bitVector, 0);
}
- (void)setBitVectorByIndex:(CFIndex)index {
[self addCountAtIndex:index countForSetBits:0];
}
- (UInt8)getSetCountByIndex:(CFIndex)index {
CFIndex bitsPerUnit = sizeof(UInt8) * kBitsPerByte;
UInt8 count = 0;
CFBitVectorGetBits(_bitVector, CFRangeMake(index * bitsPerUnit, bitsPerUnit), &count);
return count;
}
- (void)addCountAtIndex:(CFIndex)index countForSetBits:(NSUInteger)count {
CFIndex bitsPerUnit = sizeof(UInt8) * kBitsPerByte;
if (count < bitsPerUnit) {
CFBit bit = CFBitVectorGetBitAtIndex(_bitVector, (index + 1) * bitsPerUnit - count - 1);
CFBit valueToSet = 1 ^ bit;
CFBitVectorSetBitAtIndex(_bitVector, (index + 1) * bitsPerUnit - count - 1, valueToSet);
if (valueToSet == 0) {
[self addCountAtIndex:index countForSetBits:count + 1];
}
} else {
[NSException raise:@"" format:@"Set index so many times!"];
}
}
- (BOOL)isEqual:(id)object {
if ([object isKindOfClass:[self class]]) {
BitVectorWithOccurences *another = (BitVectorWithOccurences *)object;
if (_count == another.count) {
UInt8 selfByte = 0, anotherByte = 0;
for (NSInteger idx = 0; idx < _count; idx++) {
CFIndex bitsPerUnit = sizeof(UInt8) * kBitsPerByte;
CFBitVectorGetBits(_bitVector, CFRangeMake(idx * bitsPerUnit, bitsPerUnit), &selfByte);
CFBitVectorGetBits(another->_bitVector, CFRangeMake(idx * bitsPerUnit, bitsPerUnit), &anotherByte);
if (selfByte != anotherByte) {
return NO;
}
}
return YES;
}
}
return NO;
}
- (NSString *)description {
NSMutableString *bits = [NSMutableString stringWithString:@""];
NSUInteger countUnits = 0;
NSUInteger bitsPerUnit = sizeof(UInt8) * kBitsPerByte;
for (CFIndex i = 0; i < CFBitVectorGetCount(_bitVector); i++) {
CFBit bit = CFBitVectorGetBitAtIndex(_bitVector, i);
if (bit == 1) {
[bits appendString:@"1"];
} else {
[bits appendString:@"0"];
}
countUnits++;
if ((countUnits % bitsPerUnit) == 0) {
[bits appendString:@"|"];
}
}
return [bits copy];
}
- (id)copyWithZone:(nullable NSZone *)zone {
BitVectorWithOccurences *bitVector = [BitVectorWithOccurences new];
bitVector.count = _count;
bitVector->_bitVector = CFBitVectorCreateMutableCopy(NULL, 0, _bitVector);
return bitVector;
}
@end
void main() {
NSArray *wordArray1 = @[@"bag", @"bat", @"tab"];
NSArray *wordArray2 = @[@"gab", @"bat", @"laf"];
NSLog(@"%d", [self containsAnagrams:wordArray1]);
NSLog(@"%d", [self containsAnagrams:wordArray2]);
}
- (BOOL)containsAnagrams:(NSArray *)wordArray
{
NSMutableDictionary *dict = [NSMutableDictionary dictionaryWithCapacity:wordArray.count];
__block BOOL found = NO;
[wordArray enumerateObjectsUsingBlock:^(NSString * _Nonnull word, NSUInteger idx, BOOL * _Nonnull stop) {
BitVectorWithOccurences *bitVector = [self wordIdentity:word];
NSArray *array = [dict objectForKey:bitVector];
if (array.count) {
found = YES;
*stop = YES;
} else {
[dict setObject:[NSMutableArray arrayWithObject:word] forKey:bitVector];
}
}];
return found;
}