uuuouou
BAN USERThe problem can be abstracted into divide n into an ascending sequence.
(1)suppose we have remaining S to divide and previous is P
(2)then in this level a valid choice X must be within [P+1, S]
(3)and when S - X <= X, which means no another level can be built, then all S must be used in this level
Following is a solution in C:
int next(int pre, int remain)
{
int sum = 0, i;
for(i = pre+1; i <= remain; ++i){
if(remain - i > i) sum += next(i, remain-i);
else{
++sum;
break;
}
}
return sum;
}
int main()
{
int n = 20;
printf("%d has %d ways\n", n, next(0, n));
return 0;
}
In C++:
bool hasLoops(Node* head)
{
if(head == NULL || head->next == NULL) return false;
//at least two nodes or a one-node loop
Node *pSlow = head->next, *pFast = pSlow->next;
if(pFast == NULL) return false;
//every time, move pFast two nodes and pSlow one node forward
//if list has an end, pFast must get there first
for(; true; pFast = pFast->next, pSlow = pSlow->next){
if(pFast == pSlow) return true;
pFast = pFast->next;
if(pFast == NULL) return false;
}
return false;
}
By adjusting each node's pointer to next, we can have
(1)O(len1+len2) time complexity in worst case, and O(min(len1,len2)) in best
(2)O(1) space complexity
Node* merge(Node* head1, Node* head2)
{
if(head1 == NULL) return head2;
if(head2 == NULL) return head1;
//determine head of the merged list
Node* head, *p;
if(head1->value > head2->value){
head = head2;
head2 = head2->next;
}
else{
head = head1;
head1 = head1->next;
}
//connect successors
for(p = head; head1 && head2; ){
if(head1->value > head2->value){
p->next = head2;
head2 = head2->next;
}
else{
p->next = head1;
head1 = head1->next;
}
}
//connect tail
p->next = head1 ? head1 : head2;
return head;
}
Just start to count when coming across a different number, the code is easy:
int findRepeatMost(int arr[], int n, int& mostItem)
{
int mostTimes = 0, i, j;
for(i = 0; i < n; i = j){
for(j = i+1; j < n; ++j){
if(arr[j] != arr[i]) break;
}
if(mostTimes < j-i){
mostItem = arr[i];
mostTimes = j-i;
}
}
return mostTimes;
}
Solution in C++:
#include <cstdio>
int printNumber(char num[], int next, int remain)
{
if(remain == 0){
puts(num);
return 1;
}
char smallest = next == 0 ? '1' : num[next-1]+1;
char largest = '9' - remain + 1;
int sum = 0;
for(--remain; smallest <= largest; ++smallest){
num[next] = smallest;
sum += printNumber(num, next+1, remain);
}
return sum;
}
int printNumber(int n)
{
if(n > 9) return 0;
if(n == 9){
puts("123456789");
return 1;
}
char num[9];
num[n] = '\0';
return printNumber(num, 0, n);
}
int main()
{
printf("%d in total\n", printNumber(4));
return 0;
}
Balanced tree is
(1)an empty tree
(2)left subtree is a balanced tree && right subtree is a balanced tree &&
abs(height difference of the two subtrees) <= 1
Following is C++ code:
bool isBalanced(Node* root) //interface to outside
{
int height;
return isBalanced(root, height);
}
bool isBalanced(Node* p, int& height)
{
if(p == NULL){
height = 0;
return true;
}
int leftHeight, rightHeight;
if(isBalanced(p->left, leftHeight) &&
isBalanced(p->right, rightHeight) &&
abs(leftHeight - rightHeight) <= 1
){
height = 1 + max(leftHeight, rightHeight);
return true;
}
return false;
}
(1)Do breath first seach, record each state's parent state during state extension.
(2)When reaching the target state, print the swaps using backtrace.
C++ code:
#include <vector>
#include <string>
#include <utility>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
void backtrace(vector<pair<string,int> >& queue, int parentIndex)
{
if(parentIndex == -1) return;
backtrace(queue, queue[parentIndex].second);
cout << queue[parentIndex].first << "\n";
}
bool extend(vector<pair<string,int> >& queue, int& i, int levelCount, set<string>& record, const string& target)
{
string s;
for(; levelCount > 0; --levelCount, ++i){
s = queue[i].first;
for(string::size_type k = 1, len = s.size(); k < len; ++k){
if(s[k] == s[k-1]) continue;
swap(s[k], s[k-1]);
if(s.compare(target) == 0){
backtrace(queue, queue[i].second);
cout << queue[i].first << "\n";
cout << target << "\n";
return false;
}
if(record.count(s) == 0){
queue.push_back(make_pair(s, i));
record.insert(s);
}
swap(s[k], s[k-1]);
}
}
return true;
}
int transform(const string& start, const string& target)
{
if(start.compare(target) == 0) return 0;
set<string> record;
vector<pair<string,int> > queue;
queue.push_back(make_pair(start, -1));
record.insert(start);
int step = 0, i = 0, levelCount = 1;
while(levelCount > 0){
++step;
if(!extend(queue, i, levelCount, record, target)) break;
else levelCount = queue.size() - i;
}
return step;
}
int main()
{
string start = "GUM", target = "MUG";
cout << "steps = " << transform(start, target);
return 0;
}
(1)count the times each character can be used.
(2)check each word's character use, if within limit, the word can be formed.
C++ Code:
#include <string>
#include <vector>
#include <iostream>
using namespace std;
void getWords(vector<string>& res, const vector<char>& vc, const vector<string>& vs)
{
res.clear();
if(vc.empty() || vs.empty()) return;
//get the count of all given characters
int count[128] = {0}, i, size;
for(i = 0, size = vc.size(); i < size; ++i) ++count[vc[i]];
//check each word
int times[128] = {0}, j, len;
for(i = 0, size = vs.size(); i < size; ++i){
const string& word = vs[i];
//check the count of each character
for(j = 0, len = word.size(); j < len; ++j){
if(++times[word[j]] > count[word[j]]) break;
}
//if can form this word
if(j == len) res.push_back(word);
//clear this word's count
for(; j >= 0; --j){
--times[word[j]];
}
}
}
test case:
int main()
{
vector<string> words;
words.push_back("cat");
words.push_back("act");
words.push_back("ac");
words.push_back("stop");
words.push_back("cac");
vector<char> characters;
characters.push_back('a');
characters.push_back('c');
characters.push_back('t');
vector<string> res;
getWords(res, characters, words);
for(int i = 0, size = res.size(); i < size; ++i){
cout << res[i] << "\n";
}
return 0;
}
Reverse the list and return the new head's pointer:
Node* reverse(Node* pre, Node* p)
{
Node* after = p->next;
p->next = pre;
if(after == NULL) return p;
else return (p, after);
}
Node* reverse(Node* head)
{
if(head == NULL || head->next == NULL) return head;
else return reverse(NULL, head);
}
Suppose the integers are a, b and c.
(1)int arr[3]; arr[0] = a; arr[1] = b; arr[2] = c;
(2)if(arr[0] > arr[1]) swap(arr, 0, 1);
if(arr[1] > arr[2]) swap(arr, 1, 2);
if(arr[0] > arr[1]) swap(arr, 0, 1);
(3)if(arr[0] <= 0 || arr[2] >= arr[0]+arr[1]) return error;
if(arr[0] == arr[1]){
if(arr[1] == arr[2]) return equilateral;
else return isosceles;
}
else if(arr[1] == arr[2]) return isosceles;
else return scalene;
Got it finally:
(1)do merge process, record each item is from a[] or b[].
(2)find the Kth smallest pair(remember a pair must be one from a[], the other from b[]).
time complexity: O(N)
space complexity: O(N)
As I'm more familiar with C++, following is my C++ code with annotation:
#include <cstdlib>
#include <utility>
#include <algorithm>
using namespace std;
pair<int,int> getKthSmallestPair(const int a[], const int b[], int N, int K)
{
//only exist N*N pairs of a[i]+b[j]
if(K <= 0 || K > N*N) return make_pair(-1, -1);
//alloc memory for the merged array flags
int total = N << 1;
bool* isFromA = new bool[total];
//do merge process, record whether the item is from a[] or not
int i = 0, j = 0, k = 0;
for(; i < N && j < N; ++k){
if(a[i] > b[j]){
isFromA[k] = false;
++j;
}
else{
isFromA[k] = true;
++i;
}
}
for(; i < N; ++i, ++k){
isFromA[k] = true;
}
for(; j < N; ++j, ++k){
isFromA[k] = false;
}
//find the Kth smallest pair of a[i] + b[j]
i = j = -1;
//step 1: find the certain i or j of the Kth pair
int itemsOfA = 0, itemsOfB = 0;
for(k = 0; k < total; ++k){
if(isFromA[k]){
++itemsOfA;
if(itemsOfA * itemsOfB >= K){
i = itemsOfA - 1;
break;
}
}
else{
++itemsOfB;
if(itemsOfA * itemsOfB >= K){
j = itemsOfB - 1;
break;
}
}
}
//step 2: find the matched j or i in the Kth pair
int dis = itemsOfA * itemsOfB - K + 1;
if(i == -1){//b[j] has been found in step 1, whose index is k in the merged array
for(--k; k >= 0; --k){
if(isFromA[k]){
--itemsOfA;
if(--dis == 0){
i = itemsOfA;
break;
}
}
}
}
else{//a[i] has been found in step 1, whose index is k in the merged array
for(--k; k >= 0; --k){
if(!isFromA[k]){
--itemsOfB;
if(--dis == 0){
j = itemsOfB;
break;
}
}
}
}
//free memory and return indexes
delete[] isFromA;
return make_pair(i, j);
}
int main()
{
int a[] = {1, 2, 3};
int b[] = {1, 4, 7};
pair<int,int> res;
for(int i = 1; i <= 9; ++i){
res = getKthSmallestPair(a, b, 3, i);
printf("%dth smallest pair is a[%d] + b[%d]\n", i, res.first, res.second);
}
puts("\nafter switch a[] and b[]:\n");
for(int i = 1; i <= 9; ++i){
res = getKthSmallestPair(b, a, 3, i);
printf("%dth smallest pair is a[%d] + b[%d]\n", i, res.first, res.second);
}
return 0;
}
I'm more familiar with C. Following is my C code:
#include <stdio.h>
#include <string.h>
int find(int row, int col, const char** matrix, int R, int C, const char* target, int index)
{
if(row >= R || col >= C) return 0;
if(matrix[row][col] == target[index]){
if(target[index+1] == '\0') return 1;
return find(row, col+1, matrix, R, C, target, index+1) +
find(row+1, col, matrix, R, C, target, index+1) +
find(row+1, col+1, matrix, R, C, target, index+1);
}
return 0;
}
int findWord(const char** matrix, int R, int C, const char* target)
{
int i, j, count = 0;
for(i = 0; i < R; ++i){
for(j = 0; j < C; ++j){
if(matrix[i][j] == target[0]){
count += find(i, j, matrix, R, C, target, 0);
}
}
}
return count;
}
int main()
{
const char* matrix[] = {
"wsrtgg",
"aachin",
"kchujj",
"ohinyq"
};
const char* target = "sachin";
printf("%s occurs %d times in the matrix\n", target,
findWord(matrix, sizeof(matrix)/sizeof(char*), strlen(matrix[0]), target)
);
return 0;
}
Why everybody makes the simple question so complicated?
int howManyWays(int total)
{
int a, ra, b, rb, ways = 0;
for(a = total/25; a >= 0; --a){
ra = total - 25 * a;
for(b = ra/10; b >= 0; --b){
rb = ra - 10 * b;
ways += rb/5 + 1;
}
}
return ways;
}
void printAllWays(int total)
{
int a, ra, b, rb, c, rc;
for(a = total/25; a >= 0; --a){
ra= total - 25 * a;
for(b = ra/10; b >= 0; --b){
rb = ra - 10 * b;
for(c = rb/5; c >= 0; --c){
rc = rb - 5 * c;
printf("%d quarters, %d nickels, %d dimes, %d pence\n",
a, b, c, rc);
}
}
}
}
Sorry for the above code. It should be like this:
Node* sort(Node* head)
{
if(head == NULL) return head;
//step 1: find the boundary of the two independently sorted list
Node *p = head, *q;
while(p->next != NULL && p->value <= p->next->value){
p = p->next;
}
if(p->next == NULL) return head;
else{
q = p->next;
p->next = NULL;
}
//step 2: merge list
if(head->value > q->value){
p = q;
q = head;
head = p;
}
Node* t = head;
for(p = p->next; p != NULL && q != NULL; t = t->next;){
if(p->value > q->value){
t->next = q;
q = q->next;
}
else{
t->next = p;
p = p->next;
}
}
if(p != NULL) t->next = p;
else t->next = q;
return head;
}
Let's look at it in another way:
We know that fib(0) is called only within fib(2), while fib(1) is called within fib(2) and fib(3). Let call(k) be the times fib(k) is called, we actually have this:
call(0) = call(2)
call(1) = call(2) + call(3)
call(2) = call(3) + call(4)
...
call(n-2) = call(n-1) + call(n)
call(n-1) = call(n) = 1
Calculate from bottom up, we have:
call(n) = 1 = Fibonacci(1)
call(n-1) = 1 = Fibonacci(2)
call(n-2) = 1 + 1 = 2 = Fibonacci(1) + Fibonacci(2) = Fibonacci(3)
call(n-3) = 2 + 1 = 3 = Fibonacci(2) + Fibonacci(3) = Fibonacci(4)
...
call(2) = Fibonacci(n - 3) + Fibonacci(n - 2) = Fibonacci(n - 1)
call(1) = Fibonacci(n - 2) + Fibonacci(n - 1) = Fibonacci(n)
call(0) = call(2) = Fibonacci(n-1)
The above Finonacci(k) is the k-th fibonacci number.
two steps:
(1)find the boundary of the two independently sorted list.
(2)change the pointer field of the node whose value is smaller.
Following is C code:
Node* sort(Node* head)
{
if(head == NULL) return head;
//step 1: find the boundary of the two independently sorted list
Node *p = head, *left = head, *right;
while(p->next != NULL && p->value <= p->next->value){
p = p->next;
}
if(p->next == NULL) return head;
else{
right = p->next;
p->next = NULL;
}
//step 2: change the pointer field of the node whose value is smaller
head = left->value > right->value ? right : left;
while(left != NULL && right != NULL){
if(left->value > right->value){
p = right->next;
right->next = left;
right = p;
}
else{
p = left->next;
left->next = right;
left = p;
}
}
return head;
}
We may need to change every node's data but we can not change the tree's shape, so my idea is:
(1)Inorder traverse the tree and save every node's data and pointers into two arrays. Here we do inorder traverse is because BST's inorder traversal is an sorted sequence.
(2)Sort the data array.
(3)Assign data array's elements to pointer array's data fields.
Time: O(Nlog(N))
Space: O(N)
C++ Code:
struct Node{
int value;
Node* left;
Node* right;
};
//1. Recursively
bool checkLeafLevel(const Node* p, int level, int& leaf_level)
{
if(!p->left && !p->right){//p is a leaf
if(leaf_level < 0) leaf_level = level;
return level == leaf_level;
}
else{ //p is not a leaf
if(p->left && !checkLeafLevel(p->left, level+1, leaf_level) ||
p->right && !checkLeafLevel(p->right, level+1, leaf_level)) return false;
return true;
}
}
bool areLeavesAtSameLevel(const Node* root)
{
if(root == NULL) return true;
int leave_level = -1;
return checkLeafLevel(root, 1, leave_level);
}
//2. Non-recursively
bool areLeavesAtSameLevel(const Node* root)
{
if(root == NULL) return true;
const Node* p;
queue<const Node*> q;
q.push(root);
int i, level_count, leaves;
while(!q.empty()){
leaves = 0;
for(i = 0, level_count = q.size(); i < level_count; ++i){
p = q.front();
if(!p->left && !p->right) ++leaves;
else{
if(p->left) q.push(p->left);
if(p->right) q.push(p->right);
}
}
if(leaves > 0 && leaves < level_count) return false;
}
return true;
}
I didn't test them. Hope they can work.
- uuuouou December 03, 2013Use two pointers, one points to the start of a substring made of a new character, the other moves backwards and record the repeat times till meet the first character not the same. Following is C code:
#include <stdio.h>
#define MAX 100
char* Encode(char* dest, const char* src)
{
if(src == NULL || *src == '\0'){
*dest = '\0';
return dest;
}
int times = 0;
char* t = dest, c;
const char* p;
for(; c = *src; src = p){
for(p = src+1, times = 1; *p != '\0' && *p == c; ++p, ++times) ;
*t++ = c;
t += sprintf(t, "%d", times);
}
return dest;
}
int main()
{
char dest[MAX], *src = "babbaaaaaaaaaaaaaaaaadddc";
Encode(dest, src);
puts(dest);//output is b1a1b2a17d3c1
return 0;
}
C version:
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
int n, kind;
char s[MAX*2+1];
/*
we can recursively determine next character of the string
if left < n
we can choose to use one more left parenthesis or not
if right < left
we use one more right parenthesis
*/
void print(char* dest, int left, int right)
{
if(left == n && right == n){
puts(dest);
++kind;
return;
}
if(left < n){
dest[left+right] = '(';
print(dest, left+1, right);
}
if(right < left){
dest[left+right] = ')';
print(dest, left, right+1);
}
}
int main()
{
while(scanf("%d", &n), n){
s[n<<1] = '\0';
kind = 0;
print(s, 0, 0);
printf("%d kinds in total\n", kind);
}
return 0;
}
Really sorry for making you feel so bad. This is the train of thought:
(1)Read the map into a 2d array(each row could be taken as a string)
(2)Find the start and destination
(3)Use breadth first search to find the shorest path and keep record the previous position of each position. The knight can make 8 kinds of moves, so the knight can move from one position to at most 8 positions, which should be within the border, not a cut cell, and not visited before.
(4)Though one state can have 8 substates at most, one state only has one former state, because each position will just be visited once as delicated in (3).
(5)When we find out that the destination point in the BFS queue, the shortest path must have been found, with the path from start to destination been recorded by each position's previous position.
(6)If shortest path is found, we can mark the path in the map and then print the map out. If the BFS queue becomes empty, it's impossible to make it.
Time complexity: O(N*N)
Space complexity: O(N*N)
I definitely can not get the job! There's a bug in the code above again.
#include <stdio.h>
#include <ctype.h>
void parse(const char* src)
{
int times;
char c;
for(; c = *src; ){
sscanf(src+1, "%d", ×);
for(; times > 0; --times) putchar(c);
for(src += 2; isdigit(*src); ++src) ;
}
}
int main()
{
parse("a3b2c4");
getchar();
return 0;
}
Sorry for the misleading code above. I was being stupid again.
#include <stdio.h>
#include <ctype.h>
void parse(const char* src)
{
int times;
char c, *p;
for(; c = *src; src = p){
sscanf(src+1, "%d", ×);
for(; times > 0; --times) putchar(c);
for(p = src+2; isdigit(*p); ++p) ;
}
}
int main()
{
parse("a3b2c4");
getchar();
return 0;
}
We can do breadth first search to find the shortest path, and along the searching path we can record each point's previous point so as to mark the map after finding it. Following is my C++ code. Hope it's easy to understand.
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define MAX 50
/*
coordinates of the map
-----------> X
|
|
|
|
|
Y
*/
struct Point{ //coordinate of a point
int y, x;
};
int N; //map's row and col size
char map[MAX][MAX+1]; //map's state
int prePos[MAX*MAX]; //prePos[i] is the previous position of i, i/N is row, i%N is col
const int step[][2] = { //8 kinds of steps of knight -> (dy, dx)
{-2,1},{-1,2},{1,2},{2,1},
{-2,-1},{-1,-2},{1,-2},{2,-1}
};
void markPath(int y, int x)
{
int now, pre;
for(now = y*N + x; (pre = prePos[now]) >= 0; now = pre){
map[pre/N][pre%N] = '@';
}
}
bool bfs()
{
int i;
//step 1: find start and destination
int sy, sx, dy, dx;
char* p;
for(i = 0; i < N; ++i){ //find start
if(p = strchr(map[i], '@')){
sy = i;
sx = p - map[i];
break;
}
}
if(p[1] && (p = strchr(p+1, '@'))){//if destination is at the same row
dy = i;
dx = p - map[i];
}
else{ //destination is at different row
for(++i; i < N; ++i){
if(p = strchr(map[i], '@')){
dy = i;
dx = p - map[i];
break;
}
}
}
//step 2: bfs to find the shortest path from start to destination
memset(prePos, 0xFF, sizeof(prePos));
Point now, nex;
int nowIndex, nexIndex;
queue<Point> q;
now.y = sy;
now.x = sx;
q.push(now);
while(!q.empty()){
now = q.front();
if(now.y == dy && now.x == dx){ //find path!
markPath(dy, dx); //mark path in the map
return true;
}
//get represent index of point now
nowIndex = now.y*N + now.x;
for(i = 0; i < 8; ++i){
nex.y = now.y + step[i][0];
nex.x = now.x + step[i][1];
if(nex.y < 0 || nex.y >= N || //y out of border
nex.x < 0 || nex.x >= N || //x out of border
map[nex.y][nex.x] == '#') continue;//it's a cut cell
//get represent index of point nex
nexIndex = nex.y*N + nex.x;
if(prePos[nexIndex] >= 0) continue; //already visited
//add nex point to position queue
prePos[nexIndex] = nowIndex;
q.push(nex);
}
}
return false;
}
int main()
{
int i;
//input map size
scanf("%d", &N);
while(getchar() != '\n');
//input each row
for(i = 0; i < N; ++i) gets(map[i]);
//bfs search path
if(bfs()){//can go
for(i = 0; i < N; ++i) puts(map[i]);
}
else puts("Impossible");
return 0;
}
Why not add two variables to save the results of the mod operations so as to save doing them once more?
void FooBar(int n){
int i, r3, r5;
for(i = 1; i <= n; ++i){
r3 = i % 3;
r5 = i % 5;
if(r3 && r5) printf("%d", i);
else{
if(!r3) printf("Foo");
if(!r5) printf("Bar");
}
putchar('\n');
}
}
If we don't use the mod operation, will it be faster?
void FooBar(int n){
int i1 = 1, i3 = 3, i5 = 5;
for(; i1 <= n; ++i1){
if(i1 != i3 && i1 != i5) printf("%d", i1);
else{
if(i1 == i3){
printf("Foo");
i3 += 3;
}
if(i1 == i5){
printf("Bar");
i5 += 5;
}
}
putchar('\n');
}
}
(1)As the tree's structure is unknown, we might have to use a general method.
(2)Because the rightest cousin is at the same level with the given node, we can traverse the tree by level to find the level of the given node. Meanwhile the fact is when we find the given node in a level loop, the last node of the loop will just be our target!
Following is my C++ code:
Node* getRightestCousin(Node* root, Node* p)
{
if(root == NULL || p == NULL || root == p) return NULL;
queue<Node*> q;
Node* tmp;
int levelCount, i;
q.push(root);
while(!q.empty()){
for(i = 0, levelCount = q.size(); i < levelCount; ++i){
tmp = q.front();
q.pop();
if(tmp != p){ //may not in this level, so push in next level's nodes
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
else{ //only need to find the last node in this level
Node* t = NULL; //this is because p may be the rightest node in its level
for(++i; i < levelCount; ++i){
t = q.front();
q.pop();
}
return t;
}
}
}
return NULL; //can not find p in this tree
}
First of all, it's obvious that the second new operation in enqueue() and dequeue() method is rebundant.
Then, as copy is so often to do, I suggest that your PersistentQueue implement Cloneable interface. Thus the way of creating a copy in enqueue() and dequeue() method could use clone() method, which is faster than new. This might be an improvement.
public class PersistentQueue<E> implements Cloneable{
private List<E> queue;
public PersistantQueue<E> clone(){
PersistantQueue<E> copy = null;
try{
copy = (PersistantQueue<E>)super.clone();
copy.queue = (list<E>)this.queue.clone();
}
catch(CloneNotSupportedException e){
e.printStackTrace();
}
return copy;
}
public PersistantQueue<E> enqueue(E e){
if(e == null){
throw new IllegalArgumentException();
}
List<E> copy = clone();
copy.add(e);
return copy;
}
public PersistantQueue<E> dequeue(){
if(queue.isEmpty()){
throw new NoSuchElementException();
}
List<E> copy = clone();
copy.remove(0);
return copy;
}
}
I don't know wheter I'am being stupid again. Can't the following code work?
bool isomorphic(const string& source, const string& target)
{
if(target.size() != source.size()) return false;
char mapped[128] = {0}; //no mapping has been done at first
for(string::size_type i = 0, s = target.size(); i < s; ++i){
if(mapped[source[i]]) return false;//the letter of same position in source has already been mapped
mapped[source[i]] = target[i]; //map source[i] to target[i]
}
return true;
}
I haven't test it yet. Hope this could work:
struct Node{
int value;
Node* left;
Node* right;
Node(int v):value(v), left(NULL), right(NULL){}
};
Node* getMirror(Node* p)
{
if(p == NULL) return NULL;
Node* root = new Node(p->value);
root->left = getMirror(p->right);
root->right = getMirror(p->left);
return root;
}
(1)On most part, I agree with the originator, such as storing data in a maxheap, doing sift to update.
(2)But in terms of picking top 5, there might be a simpler way to do that, I guess.
(3)We could build the maxheap with just a plain array and maintain it by ourselves. Then the GUI needs to be updated only when the first 5 items of the array is changed.
Null terminated string? Should the function's return type be char* ? If so, the caller will need to worry about the memory problem then, which I don't think is a very good way. If the function returns a string as an object, then the null terminated request will be redundant. Here is my C++ solution:
string intToString(int n)
{
if(n == 0) return "0";
string s;
if(n < 0){
s.push_back('-');
n = -n;
}
for(; n; n /= 10) s.push_back(n%10 + '0');
char c;
for(int i = s[0] == '-', j = s.size()-1; i < j; ++i, --j){
c = s[i];
s[i] = s[j];
s[j] = c;
}
return s;
}
Sorry for the unformatted code. It goes like this:
public boolean isLeft(char c){
return c == '(' || c == '[';
}
public boolean isMatch(char l, char r){
return l == '(' && r == ')' ||
l == '[' && r == ']' ;
}
public boolean isValid(CharStream in){
if(!in.hasNext()) return true; //it's only at the start that empty sequence is legal
char c = in.next();
return isLeft(c) && isValid(1, c, in); //legal sequence should start with a left bracket
}
public boolean isValid(int level, char left, CharStream in){
if(!in.hasNext()) return false; //it's empty, then left can not be matched, so it's illegal
char c = in.next();
if(!isLeft(c) && isMatch(left, c) ||
isLeft(c) && isValid(level+1, c, in) && in.hasNext() && isMatch(left, in.next()))
{
if(level == 1) return isValid(in); //this indicates that the sequence may be divided into two fully matched part
else return true; //this is not the first level, need to return to last level first
}
else return false; //left can not be matched, so it's illegal
}
The problem is easy solve with a container used, just as above has shown, while it could be a challenge to nail it completely recursively with just one function whose signature is given. The following is my code. It's also easy to add '{' and '}'.
public boolean isLeft(char c){
return c == '(' || c == '[';
}
public boolean isMatch(char l, char r){
return l == '(' && r == ')' ||
l == '[' && r == ']' ;
}
public boolean isValid(CharStream in){
if(!in.hasNext()) return true; //it's only at the start that empty sequence is legal
char c = in.next();
return isLeft(c) && isValid(1, c, in); //legal sequence should start with a left bracket
}
public boolean isValid(int level, char left, CharStream in){
if(!in.hasNext()) return false; //it's empty, then left can not be matched, so it's illegal
char c = in.next();
if(!isLeft(c) && isMatch(left, c) ||
isLeft(c) && isValid(level+1, c, in) && in.hasNext() && isMatch(left, in.next()))
{
if(level == 1) return isValid(in); //this indicates that the sequence may be divided into two fully matched part
else return true; //this is not the first level, need to return to last level first
}
else return false; //left can not be matched, so it's illegal
RepTristaRJohn, Reverse Engineering and System Developer at BT
I am an Ophthalmic medical assistant in bluefield USA, I assist in retinal exams and procedures. Referred patients to outside ...
Repkylieblindner, abc at ASAPInfosystemsPvtLtd
Hello, I am Kylie. I am working in a store as Supply chain managers promote the design, development, and implementation ...
RepI am Ricky from the USA. I am 29 year old. I am doing a job. I am doing a ...
Repsheilaahollins, Blockchain Developer at ASAPInfosystemsPvtLtd
Hello, I am working as a mineralogist studying rocks, gems, and other minerals, including their chemical and crystalline structures. I ...
Rephallieriddic, HR Executive Trainee at Barclays Capital
I am Hallie, Dedicated and experienced administrative secretary who excels at prioritizing , completing multiple tasks simultaneously and following through to ...
Repomarcdei, Android Engineer at Abs india pvt. ltd.
I'm Omar. I am working as a Mail carrier in Manning's Cafeterias company. I love to learn and ...
Repbarrybzane, AT&T Customer service email at ASU
By Profession, I am a Child protective services social worker in Newark USA. My strong interest is in yoga. My ...
Repfloydmsnyder, Theoretical mathematician at STM Auto Parts
As a Theoretical Mathematician,I’m little more interested in the theory involved with mathematics. In my free time , I ...
RepEwaMariaa, Cloud Support Associate at Abs india pvt. ltd.
Hi, I am an Localization translator from New York,Travelling with company executives on foreign trips is the favorite part ...
Repalicegpopa, Apple Phone Number available 24/7 for our Customers at AMD
I am working as a U.S. marshal in Pro Property Maintenance. I want to write about I Want My ...
Reprachelwrosa1, Computer Scientist at ABC TECH SUPPORT
Hello, I am Rachel and I live in Charleston, USA. I am working as a data entry clerk who is ...
Reppathfisher, Animator at Rack N Sack
I am Pat working in Rack N Sack where I use sequential images to produce the illusion of movement and ...
Repritahmixon, Analyst at ADP
Hi, I am a physiotherapy to help people handle everyday problems. I also assist peoples who have issues caused by ...
It's just like the activity arrangement problem. Greedy algorithm will work.
- uuuouou January 03, 2014(1)divide customers into several groups in which members have the same favourite room. customers in different groups are unrelated with each other.
(2)sort each group according to ending time.
(3)for each group, always add the next customer whose ending time is the earliest and whose starting time is not earlier than last one's ending time into the room's schedule.