Algorithm: The use of "istringstream"

Here shows some usages of the class "istringstream".

1. Decode sub-strings from a pure char string

e.g.,

       string str = "qq cc ddd";

       istringstream stream(str);

       int a;

       while (stream >> a){

              cout << a << endl;

       }

the sub-string in str is definded as strings separating by ' '. and therefore, the output should be:

qq

cc

ddd

And the loop will terminated automatically when it reaches the end of the str. 

2. Decode sub-strings from a int/char mixed string

       string str = "1, 22, 33";

       istringstream stream(str);

       int a;

       string b;

       while (stream >> a){

              stream >> b;

              cout << a << endl;

              cout << b << endl;

       }

So in this string str, there are int and char. In order to decode the int and char inside, the above code will output

1

,

22

,

33

,

 

 

Algorithm: reverse the whole liked list

e.g., list=1->2->3->4->null

reverse it to: 4->3->2->1->Null;

-------------------------
1. The procedure is shown below:
using three pointers: cur, pre and tmp. As following example shown, in the first step, put 2 in front of 1, then put 3 in front of 2, ........ until all are reversed. 

2. Note the case when only one node exist. In such a case, "temp = pre->next;" will be wrong! So this line of code should be within the while loop as the codes shown below. 

   

//////////////////////////////////

//code

class Solution {

public:

       ListNode* reorderList(ListNode* head) {

              // reverse the link list

              //ListNode *dum = new ListNode(-1);

              //dum->next = head;

              ListNode* cur = head;

              ListNode* pre = head->next;

             

              cur->next = NULL;//the final node after reverse

              while (pre != NULL)

              {

                     ListNode* temp = pre->next;

                     pre->next = cur;

                     cur = pre;

                     pre = temp;

              }

              head = cur;

              return head;

       }

};

algorithms: merge sort

Merge Sort:

It uses divide and conquer method to simplify the problem. It has O(nlgn) running time in general, even in worst case. But it introduces extra memory to do the sorting (as it needs a tmp vector to temparally store the input vector). When using back tracking, the space efficiency is not so good compared with quick sort.

The general algorithm is shown below:

An example is shown below:

/////////////////////////////////////////////////////////////////////////

//codes:

class Solution {

public:

       // s[first, last] -- is part of the data in s that needs to be sorted.

       vector<int> MergeSort(vector<int> s, int first, int last)

       {

              //devide s into two halves

              if (last - first > 0){//more than 2 elements

                     s = MergeSort(s, first, (first + last) / 2);

                     s = MergeSort(s, (first + last) / 2+1, last);

                     //merge the two halves into one

                     vector<int> tmp=s;

                     int i = first, j = (first + last) / 2 + 1, k=first;

                     while ( i <= (first + last) / 2 || j <= last){ //at least one half is not empty

                           if (i>(first + last) / 2) s[k++] = tmp[j++]; //i is out of bound

                           else if (j>last) s[k++] = tmp[i++];  //j is out of bound

                           else if (tmp[i] <= tmp[j]) s[k++] = tmp[i++];

                           else s[k++] = tmp[j++];

                     }

              }

              else {//only one element

                     ;

              }

              return s;

       }

};

Algorithm: Insertion sort

Insertion sort:

Insert the current data into a proper position of the sorted array.

Running time is around O(n^2).

/////////////////////////

#include "stdafx.h"

# include <cstdlib>

#include <iostream>     // std::cout

#include <algorithm>    // std::sort

#include <vector>       // std::vector

# include <map>         // std::map

# include <unordered_map>

# include <string>

#include <bitset>

#include <ctype.h>

using namespace std;

class Solution {

public:

       vector<int> InsersionSort(vector<int> s)

       {

           //implement the insersion sort

              int i, j, tmp,sLen=s.size();

              for (i = 1; i < sLen; i++){

                     tmp = s[i];

                     j = i;

                     while (j>0 && tmp < s[j - 1]){

                           s[j] = s[j - 1];

                           j--;

                     }

                     s[j] = tmp;

              }

              return s;

       }

};

int main(int argc, char *argv[])

{

       vector<int> inp = { 3, 4, 1};

       Solution s;

       vector<int> l = s.InsersionSort(inp);

}