First non duplicate character in string C++

Find out the first non duplicate character in a string.
eg: "nasa" output: 'n' 
Require to scan the string only once.

思路：要求只能扫一遍string，既然时间严格限制，那只好多用空间了。一个map用来计数，一个double linkedlist用来存character candidates.最后总时间是O(n).
注：本代码未测试，懒得自己写double linked node的定义了。。

0. //assume that s is nonempty  
1. char firstnondup(string s){  
2.   
3.    unordered_map<char, ListNode*>  visited;  
4.   
5.    ListNode *tail = new ListNode(s[0]);  
6.   
7.    ListNode dummy(0);  
8.   
9.    dummy.next = tail;  
10.   
11.    tail->prev = dummy;  
12.   
13.    visited[s[0]] = tail;  
14.   
15.    for(int i = 1; i < s.length(); i++){  
16.    
17.       //if first occured  
18.       if(visited.find(s[i]) == visited.end()){  
19.   
20.         ListNode *cur = new ListNode(s[i]);  
21.   
22.         visited[s[i]] = cur;  
23.   
24.         tail->next = cur;  
25.   
26.         cur->prev = tail;  
27.   
28.         tail = cur;  
29.   
30.       }  
31.   
32.      else{  
33.   
34.        //if second occured, delete node  
35.        if(visited[s[i]] != NULL) {  
36.   
37.             ListNode *tmp = visited[s[i]]->prev;  
38.   
39.             tmp->next = visited[s[i]]->next;  
40.   
41.             visited[s[i]]->next->prev = tmp;  
42.   
43.             if(visited[s[i]] == tail) tail = tmp;  
44.   
45.             delete visited[s[i]];  
46.       }  
47.   
48.       //if more than secondly occured, just continue  
49.     }  
50.   }  
51.   
52. return dummy.next.val;  
53.   
54. }  
55.   
56.    

Six digit number with equal sum C++

Write an algorithm to find the number of six digit numbers where the sum of the first three digits is equal to the sum of the last three digits.

思路：找总数太简单了，写个找所有满足条件的数的code吧。
3位数的数字之和最多27,0不用考虑，所以建一个size为27的bucket,遍历所有的三位数组合，按数字和分类放入bucket里面，这样要得到要求的6位数，只要前三位和后三位在同一个bucket就可以了。复杂度就是n^3+27*n^2~1000+2700~O(n^3), n=10. 这里用string来存每个整数，一个是节省空间，还有就是输出的code写起来方便，如果要把结果存入变量，只要append两个三位数的string就行了。

0. void findall(){  
1.   //set up an array, each element stores strings with sum = index of the element  
2.   vector<string> digit3[27];   
3.   
4.   string str;  
5.   //group 3-digit integers with equal sum into each array element  
6.   for(int i = 0; i < 10; i++){  
7.             
8.     for(int j = 0; j < 10; j++){  
9.   
10.        for(int k = 0; k < 10; k++){  
11.   
12.           int sum = i + j + k;  
13.   
14.           if(sum > 0) {  
15.             str.clear();  
16.             str.push_back(i+'0');   
17.             str.push_back(j+'0');  
18.             str.push_back(k+'0');   
19.   
20.             digit3[sum-1].push_back(str);  
21.          }  
22.       }    
23.     }  
24.   }  
25.   
26.  //print out all 6-digit numbers  
27.  for(int i = 0; i < 27; i++){  
28.    //len is the number of 3-digit integers with sum = i  
29.    int len = digit3[i].size();    
30.   
31.    for(int j =0; j < len; j++){  
32.              
33.       for(int k = 0; k < len; k++){  
34.   
35.            string str1 = digit3[i][j];  
36.   
37.            string str2 = digit3[i][k];  
38.             
39.            if(str1[0] != '0') cout<<str1<<str2<<endl;  
40.   
41.       }  
42.    }  
43. }  
44. }  

Maximum subsequence sum C++

Find the maximum subsequence sum of an array of integers which contains both positive and negative numbers and return the starting and ending indices within the array.

For example:

int array[] = {1, -2, -3, 4, 5, 7, -6}

The max subsquence sum is 4+5+7= 16 and start index is at 3 and end index is at 5.

思路：DP，用一个int maxsofar记录当前最大和，对每个元素记录包含此元素的最大和cursum，同时更新maxsofar,这样做一遍就行了。

0. //assume n>0  
1.   
2. int maxsubsum(int A[], int n){  
3.   
4.   int maxsofar = A[0], cursum = A[0];  
5.   
6.   for(int i = 1; i < n; i++){  
7.   
8.     cursum = A[i] + max(cursum, 0);  
9.   
10.     maxsofar = max(maxsofar, cursum);  
11.   
12.  }  
13.   
14.  return maxsofar;  
15.   
16. }  

Print linked list in reverse order C++

Print a linked list recursively in a reverse manner without changing the actual list

思路：可以用stack或者vector做buffer, stack的default implementation是deque,对于本题来说有些浪费，只要用array-based vector然后倒着读就行了。如果不让用额外空间，那只能O(n^2)递归了。

0. void printlist(ListNode *head){  
1.   
2.  vector<int> v;  
3.   
4.  while(head){  
5.   
6.       v.push_back(val);  
7.   
8.       head = head->next;  
9.   
10.  }  
11.   
12.  for(int i = v.size() - 1; i >=0; i--){  
13.   
14.   cout<<v[i]<<" ";  
15.   
16. }  
17. }   

递归：

0. void printlist(ListNode *head){  
1.   if(!head) return;  
2.   printlist(head->next);  
3.   cout<<" "<<head->val;  
4. }   

Move zeros to end C++

Given an unsorted integer array, place all zeros to the end of the array without changing the sequence of non-zero elements. (i.e. [1,3,0,8,12, 0, 4, 0,7] --> [1,3,8,12,4,7,0,0,0])

思路：用个index记录当前需要填充的位置，扫一遍就行了，跟quicksort思路一致。复杂度O(n)

0. void pushzeros(int A[], int n){  
1.   
2.   int index = 0;  
3.   
4.   for(int i = 0; i < n; i++){  
5.   
6.     if(A[i] != 0){  
7.          int tmp = A[index];  
8.   
9.          A[index++] = A[i];  
10.   
11.          A[i] = tmp;  
12.   
13.     }  
14.      
15.   }     
16.   
17. }