Recursion

1. print 0,1,2,.. to n

void printArray(int n)
{
if(n > 0)
{printArray(n-1);
cout << ',' << ' ' << n;}
else if ( n == 0)
cout << n;
}

2. print following pattern

void printPattern(int n)
{
if (n == 0 || n < 0) {
cout << n ;
return;
}
cout << n << " ";
printPattern(n - 5);

cout << " " << n;

}

3. find Max in Array

int findMax(int* arr, int length)
{
if(length == 1)
return arr[0];
return max(arr[length-1], findMax(arr, length-1));
}

4. check if string is palindrome

bool isPalindrome(string str)
{
int n = str.length();
if(n == 1 || n == 0)
{return 1;}
if(str[0] != ' ' && str[n-1] != ' ')
{
if(str[0] != str[n-1])
return 0;
else if(str[0] == str[n - 1])
return 1 & isPalindrome(str.substr(1,n-2));
}
else if(str[0] == ' ' && str[n-1] == ' ')
{
if(str[1] != str[n-2])
return 0;
else if (str[1] == str[n-2])
return 1& isPalindrome(str.substr(2, n-4));
}
else if(str[0] == ' ')
{
if(str[1] != str[n-1])
return 0;
else if (str[1] == str[n-1])
return 1& isPalindrome(str.substr(2, n-3));
}
else if(str[n-1] == ' ')
{
if(str[0] != str[n-2])
return 0;
else if(str[0] == str[n - 2])
return 1& isPalindrome(str.substr(1,n-3));
}

return 0;

5.findGCD
int findGCD(int a, int b)
{
if (a == 0)
return b;
if (b == 0)
return a;

if(a == b)
return a;
if(a > b)
return findGCD(a-b, b);
else return findGCD(a, b-a);
}

7.
void printHailstone(int number)
{
if(number == 1)
cout << 1;
else if(number%2 == 0)
{ cout << number << ' ';
printHailstone(number/2);}
else
{
cout << number << ' ';
printHailstone(number*3+1);
}
}

8.
int myArrayToInt(char *str, int n)
{
int num = 0;
if(n == 1)
{
num += (str[0]-48);
return num;
}
else
{
num += (str[0]-48)*pow(10,n-1);
return num + myArrayToInt(++str,n-1);
}
}

9. find LCM (have to find GCD then find LCM by multiply A*B/GCD)
int findGCD(int a, int b)
{
if (a == 0)
return b;
if (b == 0)
return a;

if(a == b)
return a;
if(a > b)
return findGCD(a-b, b);
else return findGCD(a, b-a);
}
int LCM(int a, int b)
{
int GCD = findGCD(a,b);
return a*b/GCD;
}

10. find number of brackets need to be added

int mininumBracketAdd(string s) {
// STUDENT ANSWER
if(s.find("()") == -1)
return s.length();
else
{
s.replace(s.find("()"), 2, "");
return mininumBracketAdd(s);
}
}
11.

12. Using recursive to count Char size

int strLen(char* str)
{
/*
* STUDENT ANSWER
*/
if(str[0] == '\0')
return 0;
else
{
return 1 + strLen(++str);
}
}

ARRAY_LIST

template<class T>
void ArrayList<T>::ensureCapacity(int cap){
/*
if cap > capacity:
new_capacity = capacity * 1.5;
create new array with new_capacity
else: do nothing
*/
if(cap > capacity)
{
int newCapacity = capacity*3/2;
int *newData = new int[newCapacity];
for(int i = 0; i < count; i++)
{
newData[i] = this->data[i];
}
this->capacity = newCapacity;
delete [] this->data;
this->data = newData;
}
}

template <class T>

void ArrayList<T>::add(T e) {
/* Insert an element into the end of the array. */
this->ensureCapacity(this->count + 1);
this->data[this->count] = e;
this->count++;
}

template<class T>
void ArrayList<T>::add(int index, T e) {
/*
Insert an element into the array at given index.
if index is invalid:
throw std::out_of_range("the input index is out of range!");
*/
if(index > count||index < 0)
{
cout << "the input index is out of range!"<<endl;
}
else{
this->ensureCapacity(this->count+1);
for(int i = this->count-1; i>=index; i--)
{
this->data[i+1] = this->data[i];
}
this->data[index] = e;
this->count++;}
}

template<class T>
int ArrayList<T>::size() {
/* Return the length (size) of the array */
return count;
}

VECTOR
vector<int> updateArrayPerRange(vector<int>& nums, vector<vector<int>>& operations)
{
// STUDENT ANSWER
int size = operations.size();
for(int i = 0; i < size;i++)
{
int L,R,X;
L = operations[i][0];
R = operations[i][1];
X = operations[i][2];
for(int j = L; j <= R;j++)
{
nums[j] += X;
}
}
return nums;
}
int equalSumIndex(vector<int>& nums) {
// STUDENT ANSWER
int size = nums.size();
for(int i = 0; i < size;i++)
{
int left = 0;
int right = 0;
for(int n = i-1;n>=0;n--)
{
left += nums[n];
}
for(int m = i+1; m < size;m++)
{
right += nums[m];
}
if(left == right)
{
return i;
}
}
return -1;
}
int buyCar(int* nums, int length, int k) {
sort(nums, nums + length);
int count = 0;
int sum = k;
while(nums[count] <= sum)
{
sum -= nums[count];
count++;
}
return count;
}

SINGLY LINKED LIST

template <class T>
void SLinkedList<T>::add(const T& e) {
/* Insert an element into the end of the list. */
Node* pNew = new Node();
pNew->data = e;
pNew->next = NULL;
if(count == 0)
{
this->head = pNew;
this->tail = pNew;
count+=1;
}
else if (count > 0)
{
this->tail->next = pNew;
this->tail = pNew;
count+=1;
}
}

template<class T>
void SLinkedList<T>::add(int index, const T& e) {
/* Insert an element into the list at given index. */
Node* pNew = new Node();
pNew->data = e;
pNew->next = NULL;
if(count == 0)
{
this->head = this->tail = pNew;
count++;
}
else
{
if(index == 0)
{
pNew->next = this->head;
this->head = pNew;
count+=1;
}
else if (index >= count)
{
this->tail->next = pNew;
this->tail = pNew;
count+=1;
}
else
{
Node* pre = this->head;
for(int i = 1; i < index; i++)
{
pre = pre->next;
}
pNew->next = pre->next;
pre->next = pNew;
}
}
}

template<class T>
int SLinkedList<T>::size() {
/* Return the length (size) of list */
return this->count;
}
template<class T>
T SLinkedList<T>::get(int index) {
/* Give the data of the element at given index in the list. */
Node* ptr = this->head;
for(int i = 0; i<index;i++)
{
ptr = ptr->next;
}
return ptr->data;
}
template <class T>
void SLinkedList<T>::set(int index, const T& e) {
/* Assign new value for element at given index in the list */
Node* ptr = this->head;
for(int i = 0; i<index;i++)
{
ptr = ptr->next;
}
ptr->data = e;
}

template<class T>
bool SLinkedList<T>::empty() {
/* Check if the list is empty or not. */
return (this->head == NULL && this->tail == NULL);

template<class T>
int SLinkedList<T>::indexOf(const T& item) {
/* Return the first index wheter item appears in list, otherwise return -1 */
Node* ptr = this->head;
int i = 0;
while(ptr != NULL)
{
if(ptr->data == item)
{
return i;
}
else
{
i+=1;
ptr = ptr->next;
}
}
return -1;
}

template<class T>
bool SLinkedList<T>::contains(const T& item) {
/* Check if item appears in the list */
Node* ptr = this->head;
while(ptr != NULL)
{
if(ptr->data == item)
{
return 1;
}
else
ptr = ptr->next;
}
return 0;
}
template <class T>
T SLinkedList<T>::removeAt(int index)
{
/* Remove element at index and return removed value */
T removed;
if(index == 0)
{
if(count == 1)
{
Node* ptr = this->head;
removed = ptr->data;
free(this->head);
this->head = NULL;
this->tail = NULL;
ptr = NULL;
count -=1;
return removed;
}
else
{
Node* ptr = this->head;
Node* tmp = this->head->next;
removed = ptr->data;
free(this->head);
this->head = tmp;
ptr = NULL;
count -=1;
return removed;
}
}
else if (index == count - 1)
{
Node* ptr = this->tail;
Node* tmp = this->head;
for(int i = 0; i < index -1 ;i++)
{
tmp = tmp->next;
}
removed = ptr->data;
free(this->tail);
tmp->next = NULL;
this->tail = tmp;
ptr = NULL;
count-=1;
return removed;
}
else
{
Node* ptr = this->head;
Node* pre = this->head;
for(int i = 0; i< index;i++)
{
ptr = ptr->next;
}
for(int i = 0; i<index-1;i++)
{
pre = pre->next;
}
removed = ptr->data;
pre->next = ptr->next;
free(ptr);
ptr = NULL;
count-=1;
return removed;
}
}

template <class T>

bool SLinkedList<T>::removeItem(const T& item)
{
/* Remove the first apperance of item in list and return true, otherwise return
false */
Node* ptr = head;
int index = 0;
while(ptr != NULL)
{
if(ptr->data == item)
{
if(index == 0)
{
if(count == 1)
{
free(this->head);
this->head = NULL;
this->tail = NULL;
ptr = NULL;
count -=1;
return 1;
}
else if (count > 1)
{
Node* tmp = this->head->next;
free(this->head);
this->head = tmp;
ptr = NULL;
count -=1;
return 1;
}
}
else if(index == count - 1)
{
Node* tmp = this->head;
for(int i = 0; i < index -1 ;i++)
{
tmp = tmp->next;
}
free(this->tail);
tmp->next = NULL;
this->tail = tmp;
ptr = NULL;
count-=1;
return 1;
}
else
{
Node* pre = this->head;
for(int i = 0; i<index-1;i++)
{
pre = pre->next;
}
pre->next = ptr->next;
free(ptr);
ptr = NULL;
count-=1;
return 1;
}
}
else
{
index+=1;
ptr = ptr->next;
}
}
return 0;
}

template<class T>
void SLinkedList<T>::clear(){
/* Remove all elements in list */
Node* tmp = this->head;
while(tmp != NULL)
{
tmp = this->head->next;
free(this->head);
this->head = tmp;
}
}

LLNode* reverseLinkedList(LLNode* head) {

// STUDENT ANSWER
int count = 0;
LLNode* tmp = head;
while(tmp != NULL)
{
count+=1;
tmp = tmp->next;
}
if(count == 0)
{
return head;
}
else if(count <= 2)
{
tmp = head->next;
tmp->next = head;
head->next = NULL;
return tmp;
}
else
{
tmp = NULL;
LLNode* tmp2 = NULL;
while(head != NULL)
{
tmp2 = head->next;
head->next = tmp;
tmp = head;
head = tmp2;
}
return tmp;
}
}
LLNode* addLinkedList(LLNode* l0, LLNode* l1) {
// STUDENT ANSWER
LLNode* first = l0;
LLNode* second = l1;
queue<int> sohang1;
queue<int> sohang2;
queue<int> sonho;
queue<int> ketqua;
while(first != NULL)
{
sohang1.push(first->val);
first = first->next;
}
while(second != NULL)
{
sohang2.push(second->val);
second = second->next;
}
if(sohang1.size() > sohang2.size())
{
while(sohang1.size() != sohang2.size())
{
sohang2.push(0);
}
}
else if(sohang1.size() < sohang2.size())
{
while(sohang1.size() != sohang2.size())
{
sohang1.push(0);
}
}
while(sohang1.empty() == 0 && sohang2.empty() == 0)
{
int plus1 = sohang1.front();
int plus2 = sohang2.front();
sohang1.pop();
sohang2.pop();
int sum;
int remember;
if(sonho.empty() == 0)
{
int num = sonho.front();
sum = plus1 + plus2 + num;
sonho.pop();
}
else
{
sum = plus1 + plus2;
}
if(sum >= 10)
{
remember = sum%10;
sum = sum/10;
sonho.push(sum);
ketqua.push(remember);
}
else
{
ketqua.push(sum);
}
}
if(sonho.empty() == false)
{
int num = sonho.front();
ketqua.push(num);
sonho.pop();
}
int size = ketqua.size();
int arr[size];
for(int i = 0; i< size;i++)
{
arr[i] = ketqua.front();
ketqua.pop();
}
LLNode* sum = LLNode::createWithIterators(arr, arr + sizeof(arr) /
sizeof(int));
return sum;
}
LLNode* rotateLinkedList(LLNode* head, int k) {
// STUDENT ANSWER
int size = 0;
LLNode* ptr = head;
while(ptr != NULL)
{
size+=1;
ptr = ptr->next;
}
if(size == 0)
return head;
ptr = head;
while(ptr->next != NULL)
ptr = ptr->next;
ptr->next = head;
ptr = head;
int headposition = size - (k%size);
int ptrposition = size - (k%size) - 1;
for(int i = 0; i < headposition;i++)
{
head = head->next;
}
for(int i = 0; i < ptrposition;i++)
{
ptr = ptr->next;
}
ptr->next = NULL;
return head;
}S