Posts

Showing posts from September, 2013

remove the duplicate character in a string

/*** remove the duplicate in an unsorted array and return its new length of array. adapt to any unsorted array with the template table of range table. ***/ int findIdx( string s , unordered_map < int , bool > wmap , int index ) {        while ( index < s .size()) {               if (! wmap [ s [ index ]]) return index ;               index ++;        }        return index ; } int removedup( string str ) {        if ( str .size() < 2) return str .size();        unordered_map < int , bool > wordmap;        for ( int i=0; i<256; i++) {               wor...

Trapping Rain Water

Image
Trapping Rain Water AC Rate: 165/540 My Submissions Given  n  non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given  [0,1,0,2,1,0,1,3,2,1,2,1] , return  6 . Algorithm: scan from left to right get the leftMostHeight scan from right to left get the rightMost Height at the pos i, if(A[i] < min(left, right)) trap[i] = min(left, right) – A[i]; class Solution { public :        int trap( int A [], int n ) {               // Start typing your C/C++ solution below               // DO NOT write int main() function               if ( n < 3) return 0;        ...

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. For example, Given   1->2->3->4 , you should return the list as   2->1->4->3 . Your algorithm should use only constant space. You may   not   modify the values in the list, only nodes itself can be changed. /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public :     ListNode* swap(ListNode * head ) {         ListNode *tmp = head ->next;         tmp->next = head ;         head ->next = nullptr ;         return tmp;     }  ...

Rotate Matrix

#include <iostream> using namespace std; #define N 4 void rotate90( int (* a )[N], int st , int ed ) {        if ( st >= ed ) return ;        int tmp;        for ( int i = 0 ; i < ed - st ; i++ ) { // index start from zero               // Note the rotate order               tmp = a [ st ][i+ st ];               a [ st ][i+ st ] = a [ ed -i][ st ];               a [ ed -i][ st ] = a [ ed ][ ed -i];               a [ ed ][ ed -i] = a [i+ st ][ ed ];               a [i+ st ][ ed ] = tmp;      ...

Check is Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric:     1    / \   2   2  / \ / \ 3  4 4  3 But the following is not:     1    / \   2   2    \   \    3    3 /**  * Definition for binary tree  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public :        bool SymmetricUtil(TreeNode * n1 , TreeNode * n2 ) {               if ( n1 == nullptr && n2 == nullpt...