Revers String & Array - Q7 Algorithm

1. Reverse words in a phrase

Reverse the order of words in a sentence, but keep words themselves unchanged.

void reverse(char chars[],int start,int end) 
{
if( start >= end ) return;

for(;start < end ; start++,end--) {
std::swap(chars[start],chars[end]);
}
}

void ReverseInPhrase(char chars[],int size)
{
reverse(chars,0,size-1);

int wordStart = 0;

for(int i=0;i < size; i++ ) {

if( chars[i] == ' ' )
{
reverse(chars,wordStart,i-1);
wordStart = i + 1;
}
}

reverse(chars,wordStart,size-1);
}

2. Rotate an array K times to its left.
Reverse the whole array, Then reverse the part 0 to n-k and n-k+1 to n. 

void reverse(std::vector<int> &v, int start, int end) {

if( (int) v.size() < (end - start) ) return;

for(;start < end;start++,end--) {
std::swap(v[start],v[end]);
}
}

void rotate(std::vector<int> &v, int k) {

reverse(v, 0, v.size() - 1);

reverse(v,0,k-1);
reverse(v,k,v.size()-1);
}

Largest Sub-Array - Q6 Algorithm

1. 1D Array
template <int size> 
int MaxSubsetSum(int nums[size]) {

int maxToHere = 0;
int maxSofar = 0;

for(unsigned int i=0; i < size; i++ ) {

if (maxToHere < 0) {
maxToHere = nums[i];
}
else {
maxToHere += nums[i];
}

if (maxToHere > maxSofar) {
maxSofar = maxToHere;
}
}

return maxSofar;
}
2. 2D Array
(combine with the first problem)


template <int NumberOfRow, int NumberOfColumn>
int MaxSubsetSumIn2DArray(int matrix[NumberOfRow][NumberOfColumn])
{
int maxSum = 0;

for (int startRow = 0; startRow<NumberOfRow; startRow++) {
for (int endRow = startRow; endRow<NumberOfColumn; endRow++) {

int tempSum[NumberOfColumn] = { 0, };

for (int col = 0; col<NumberOfColumn; col++) {

for (int row = startRow; row <= endRow; row++)
tempSum[col] = matrix[row][col];
}

int tempLargest = MaxSubset(tempSum);

if (tempLargest > maxSum)
maxSum = tempLargest;
}
}

return maxSum;

}

Tree Traversal - Q5 Algorithm


<will be completed for several days >


0. Tree
      

0.1. Pre-Order   :  F, B, A, D, C, E, G, I, H.
  0.2. In-Order: A, B, C, D, E, F, G, H, I
  0.3.Post-order: A, C, E, D, B, H, I, G, F
          0.4.Level-Order :  F, B, G, A, D, I, C, E, H

1. Pre-Order

  1. Visit the root.
  2. Traverse the left subtree.
  3. Traverse the right subtree.
void TreePreorderNoRecursion(TreeNode* root) { 

std::stack<TreeNode *> myStack;

while (root != nullptr || !myStack.empty()) {

if (root != nullptr) {
myStack.push(root);
std::cout << root->value << std::endl;
root = root->left;
}
else
{
root = myStack.top();
myStack.pop();
root = root->right;
}
}
}
2. In-Order

  1. Traverse the left sub-tree.
  2. Visit the root.
  3. Traverse the right sub-tree.

void TreeInorderNoRecursion(TreeNode* root) { 

std::stack<TreeNode *> myStack;

while (root != nullptr || !myStack.empty()){

if (root != nullptr) {
myStack.push(root);
root = root->left;
}
else
{
root = myStack.top();
myStack.pop();

std::cout << root->value << std::endl;

root = root->right;
}
}
}
3. Post-Order
  1. Traverse the left subtree.
  2. Traverse the right subtree.
  3. Visit the root.

void TreePostorderNoRecursion(TreeNode* root) { 

std::stack<TreeNode *> myStack;
myStack.push(root);

TreeNode *prev = nullptr;

while (!myStack.empty()) {

auto curr = myStack.top();

// if previous node is parent or current node is root
if (prev == nullptr || prev->left == curr || prev->right == curr) {

if (curr->left != nullptr) { // left first
myStack.push(curr->left);
}
else if (curr->right != nullptr) // then right
{
myStack.push(curr->right);
}
else { // no - children & print & pop - up

std::cout << curr->value << std::endl;
myStack.pop();
}

}
else if (curr->left == prev) { // when left node is visited

if (curr->right != nullptr)
{
myStack.push(curr->right);
}
else {

std::cout << curr->value << std::endl;
myStack.pop();
}
}
else if (curr->right == prev) // when left & right node are visited
{
std::cout << curr->value << std::endl;
myStack.pop();

}
prev = curr;
}

}

Merge Sorted Array - Q4 Algorithm

 1. merge to new Array
void Merge(int A[], int m, int B[], int n, int C[])
{
int i = 0, j = 0, k = 0;

while (i < m && j < n) {

if (A[i] < B[j]) {
C[k] = A[i];
i++;
}
else {
C[k] = B[j];
j++;
}

k++;
}

while (i < m) {
C[k++] = A[i++];
}

while (j < n) {
C[k++] = B[j++];
}

}
2. Without Additional Memory
 
int MergeTwoSortedArray(int longArray[],int shortArray[],int longTail,int shortTail)
{
int ret = longTail + shortTail;

longTail--;
shortTail--;

while( longTail >= 0 && shortTail >= 0 ) {

int index = longTail + shortTail + 1;

if( longArray[longTail] > shortArray[shortTail] ) {
longArray[index] = longArray[longTail];
longTail--;
}
else {
longArray[index] = shortArray[shortTail];
shortTail--;
}
}

while(shortTail >= 0 ) {
longArray[shortTail] = shortArray[shortTail];
shortTail--;
}

return ret;
}


1 2 3 4 5 6 7 8 9 10 다음