Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

class Solution {
public:
    int jump(int A[], int n) {
        if (n <= 1) return 0;
        int standpoint = 0;
        int frontier = A[0];
        int count = 1;
        while (true) {
            if (frontier >= n-1) return count;
            int newFrontier = frontier;
            for(int ii = standpoint; ii <= frontier; ++ii) {
                newFrontier = std::max(newFrontier, ii + A[ii]);
            }
            ++count;
            standpoint = frontier;
            frontier = newFrontier;
        }
        return count;
    }
};

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 isSymmetric(TreeNode *root) {
        if (root == NULL) return true;
        return isMirror(root->left, root->right);
    }
   
    bool isMirror(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL && t2 == NULL) return true;
        if (t1 == NULL || t2 == NULL || t1->val != t2->val) return false;
        return isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);
    }
  
};

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

 class Solution {
public:
    string longestCommonPrefix(vector &strs) {
        if (strs.size() < 1) return "";
        string pre = strs[0];
        for(int index = 0; index < pre.length(); ++index) {
            for(int ii = 0; ii < strs.size(); ++ii) {
                string current = strs[ii];
                if (current[index] != pre[index]) return pre.substr(0, index);
            }
        }
        return pre;
    }
};

Palindrome Number

//not the best

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        string s = "";
        while(x > 0) {
            int dig = x % 10;
            x /= 10;
            s.push_back(dig);
        }
        for(int ii = 0; ii < s.size(); ++ii){
            int jj = s.size()-1-ii;
            if (s[ii] != s[jj]) return false;
        }
        return true;
    }
};


// better, without extra space
class Solution {
public:
    bool isPalindrome(int x) {
        if (x == 0 ) return true;
        if (x < 0 || x / 10 * 10 == x) return false;
        int mirror = 0;
        while (mirror < x) {
            int dig = x % 10;
            mirror = mirror * 10 + dig;
            if (mirror == x) return true;
            x /= 10;
            if (mirror == x) return true;
        }
        return false;
    }
};

Reverse Integer

class Solution:
    # @return an integer
    def reverse(self, x):
        if not x:
            return x
        s = str(x)
        first = s[0]
        result = 0
        if (first.isdigit()):
            sub = int(s[::-1])
            if sub < 2147483648:
                result = sub
        else:
            sub = int(s[1:][::-1])
            if sub < 2147483648:
                result = int(first + s[1:][::-1])
        return result
       

Valid Palindrome

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0;
        int right = s.size() - 1;
        while (left <= right) {
          if (!isLetter(s[left])) {
              ++left;
              continue;
          }
          if (!isLetter(s[right])) {
              --right;
              continue;
          }
          if (toLower(s[left]) != toLower(s[right])) return false;
          ++left;
          --right;
        }
        return true;
    }
   
    bool isLetter(char c) {
        return ('a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9');
    }
   
    char toLower(char c) {
        if ('A' <= c && c <= 'Z') return c + 'a' - 'A';
        return c;
    }
};

Add Two Numbers

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode* root = new ListNode(0);
        add(l1, l2, root, 0);
        return root->next;
    }
   
    void add(ListNode *l1, ListNode *l2, ListNode* pre, int carry) {
        if (l1 == NULL) addSingle(l2, pre, carry);
        else if (l2 == NULL) addSingle(l1, pre, carry);
        else {
            int num = l1->val + l2->val + carry;
            pre->next = new ListNode(num % 10);
            add(l1->next, l2->next, pre->next, num/10);
        }
       
    }
   
    void addSingle(ListNode* n, ListNode* pre, int carry) {
        if (n == NULL) {
            if (carry == 0 ) return;
            else {
                pre->next = new ListNode(carry);
                return;
            }
        }
        int num = carry + n->val;
        pre->next = new ListNode(num % 10);
        addSingle(n->next, pre->next, num/10);
    }
};

Two Sum

class Solution {
public:
    vector twoSum(vector &numbers, int target) {
        vector n2 = numbers;
        std::sort(n2.begin(), n2.end());
        for (int ii = 0; ii < n2.size(); ++ii) {
            int subTarget = target - n2[ii];
            bool subFound = std::binary_search(n2.begin()+ii+1, n2.end(), subTarget);
            if (subFound) {
                vector result;
                for(int jj = 0; jj < numbers.size(); ++jj) {
                    if (numbers[jj] == n2[ii] || numbers[jj] == subTarget) result.push_back(jj+1);
                }
                return result;
            }
        }
        return vector(2,0);
    }
};

First Missing Positive

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for(int ii = 0; ii < n; ++ii) {
            while (A[ii] != ii + 1 ) {
                if (A[ii] <= 0 || A[ii] > n || A[ii] == A[A[ii] - 1]) {
                    A[ii] = -1;
                    break;
                }
                swap(A, ii, A[ii]-1);
            }
        }
       
        for (int ii = 0; ii < n; ++ii) {
            if (A[ii] != ii+1) return ii+1;
        }
        return n+1;
    }
   
    void swap(int A[], int here, int other) {
        int temp = A[here];
        A[here] = A[other];
        A[other] = temp;
        return;
    }
};

Edit Distance

class Solution {
public:
    map, int> m;
    int minDistance(string word1, string word2) {
        return minDistHelper(word1, word2, 0, 0);
    }
   
    int minDistHelper(string const& word1, string const& word2, int const index1, int const index2) {
        pair p = make_pair(index1, index2);
        if (m[p]) return m[p];
        if (index1 == word1.size()) return word2.size() - index2;
        if (index2 == word2.size()) return word1.size() - index1;
       
        if (word1[index1] == word2[index2]) return minDistHelper(word1, word2, index1 + 1, index2 + 1);
        m[p] = 1 + min(minDistHelper(word1, word2, index1+1, index2+1), min(minDistHelper(word1, word2, index1+1, index2), minDistHelper(word1, word2, index1, index2+1)));
        return m[p];
    }
};

Majority Element

class Solution {
public:
    int majorityElement(vector &num) {
        map m;
        for (int ii = 0; ii < num.size(); ++ii) {
            int count = m[num[ii]];
            m[num[ii]] = ++count;
        }
        int maxEle = 0;
        int maxCount = 0;
        for(auto it = m.begin(); it != m.end(); ++it) {
            if (it->second > maxCount) {
                maxEle = it->first;
                maxCount = it->second;
            }
        }
        return maxEle;
    }
};

Excel Sheet Column Number

class Solution {
public:
    int titleToNumber(string s) {
        int result = 0;
        for (int ii = 0; ii < s.size(); ++ii) {
            result = result * 26 + s[ii] - 'A' + 1;
        }
        return result;
    }
};

count and say

class Solution {
public:
    string countAndSay(int n) {
        string s = "1";
        for (int ii = 0; ii < n-1; ++ii) {
            s = getNext(s);
        }
        return s;
       
    }
   
    string getNext(string s) {
        string say = "";
        for(int ii = 0; ii < s.size(); ++ii) {
            int repeat = countRepeat(s, ii);
            say.push_back(repeat + '0');
            say.push_back(s[ii]);
            ii += repeat-1;
        }
        return say;
    }
   
    unsigned int countRepeat(string s, unsigned int pos) {
        char c = s[pos];
        int ii = pos;
        for(; ii < s.size(); ++ii){
            if (s[ii] != c) break;
        }
        return ii - pos;
    }
};

Valid Parentheses

class Solution {
public:
    bool isValid(string s) {
        vector v;
        for(int ii = 0; ii < s.size(); ++ii) {
            switch (s[ii]) {
                case '(':
                case '{':
                case '[': v.push_back(s[ii]); break;
                case ')':
                  if (v.empty() || v.back() != '(') return false;
                  else {
                      v.pop_back();
                      break;
                  }
                case ']':
                  if (v.empty() || v.back() != '[') return false;
                  else {
                      v.pop_back();
                      break;
                  }
                case '}':
                  if (v.empty() || v.back() != '{') return false;
                  else {
                      v.pop_back();
                      break;
                  }
            }
        }
       
        return v.empty();
       
       
    }
};

Compare Version Numbers

Compare Version Numbers

 Total Accepted: 10377 Total Submissions: 70133My Submissions

Compare two version numbers version1 and version1.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

 https://oj.leetcode.com/problems/compare-version-numbers/

python --

class Solution:
    # @param version1, a string
    # @param version2, a string
    # @return an integer
    def compareVersion(self, version1, version2):
        vlong = version1.split('.')
        vshort = version2.split('.')
        swapflag = 1
        if len(vlong) < len(vshort):
            swapflag = -1
            vlong, vshort = vshort, vlong
        for index in range(0, len(vlong)):
            v1 = float(vlong[index])
            v2 = float(vshort[index]) if (index < len(vshort)) else 0
            if (v1 > v2):
                return 1 * swapflag
            elif (v1 < v2):
                return -1 * swapflag
        return 0

C++
class Solution {
public:
    int compareVersion(string version1, string version2) {
        unsigned int p1 = 0;
        unsigned int p1pre = 0;
        unsigned int p2 = 0;
        unsigned int p2pre = 0;
        while(p1 < version1.size() && p2 < version2.size()) {
            string v1 = "";
            string v2 = "";
            for (p1 = p1pre; p1 < version1.size(); ++p1){
                if (version1[p1] == '.') break;
                v1.push_back(version1[p1]);
            }

            for (p2 = p2pre; p2 < version2.size(); ++p2){
                if (version2[p2] == '.') break;
                v2.push_back(version2[p2]);
            }

            int n1 = stoi(v1);
            int n2 = stoi(v2);
            if (n1 > n2) return 1;
            if (n1 < n2) return -1;
           
            p1pre = p1 + 1;
            p2pre = p2 + 1;
        }
       
        if (p2 >= version2.size()) {
            for(unsigned int ii = p1pre; ii < version1.size(); ++ii) {
                if (version1[ii] != '0' && version1[ii] != '.') return 1;
            }
        }
        else if (p1 >= version1.size()) {
            for(unsigned int ii = p2pre; ii < version2.size(); ++ii) {
                if (version2[ii] != '0' && version2[ii] != '.') return -1;
            }
        }

        return 0;

    }
   
 
};       

email server; web server; free dns subdomain

1. Register a subdomain, pointing to the static IP
http://freedns.afraid.org/domain/

2. Install and config postfix
https://help.ubuntu.com/community/Postfix
https://help.ubuntu.com/lts/serverguide/postfix.html 

php gearman

1. Download from http://pecl.php.net/package/gearman

and unpack

2. under the unpacked folder,

$phpize
$./configure
$make
$sudo make install

if $phpize gives you an "not found error", install php5-dev:

$sudo apt-get install php5-dev

3. edit ini file

$php --ini

then choose a file, e.g.

$sudo vi /etc/php5/cli/php.ini

and add the line  extension=gearman.so

4. verify

$php --info | grep "gearman support"

or

$php -a

php > print gearman_version();

http://edvanbeinum.com/how-to-install-gearman-php-ubuntu


5. Test as a gearman client (An Example Client):
http://gearman.org/gearman_php_extension
save the file as hello.php
and in terminal, run

$php hello.php

6. More to read:
http://www.php.net/manual/en/book.gearman.php
http://toys.lerdorf.com/archives/51-Playing-with-Gearman.html
https://www.rssinclude.com/blog/36_how_to_run_php_scripts_in_html_or_htm_files

7. Running on a web browser:
  a. create a script to be executed, name it cal.php
and "chmod 500" to it
  b. in same folder, created a file to be displayed, name it hello.php
and now open the browser address: http://127.0.0.1/hello.php
it should work, provided there's a gearman worker already up. 

The peripheral stuff

feedback system: helpscout : https://www.helpscout.net/
ticket system: redmine: http://www.redmine.org/
monitoring heartbeat: http://www.linux-ha.org/wiki/Main_Page
Qgis, amazon aws

OpenTripPlanner

Getting OpenTripPlanner to work and more:

1. Download, configure and test run on http
https://github.com/openplans/OpenTripPlanner/wiki/TwoMinutes

note: once the browser opens http://localhost:8080/opentripplanner-webapp
the background maybe empty. On the far right of the  page, click the "+" sign. Then under "Base Layer" and choose "Open Street Map" (or others, instead of the default "Mapbox Steets")



2. Test the Stand-alone mode, which is used as an API
https://github.com/openplans/OpenTripPlanner/wiki


3. Json or Xml (default) result can be generated:
 https://github.com/openplans/OpenTripPlanner/wiki/JsonOrXml

EXAMPLE:
curl --header "Accept: application/json" "http://maps5.trimet.org/osm?mode=BICYCLE&toPlace=45.504966%2C-122.654349&fromPlace=45.5115225%2C-122.647633"
vs.
curl --header "Accept: application/xml" "http://maps5.trimet.org/osm?mode=BICYCLE&toPlace=45.504966%2C-122.654349&fromPlace=45.5115225%2C-122.647633"

4. Build graphs:
https://github.com/openplans/OpenTripPlanner/wiki/GraphBuilder

protoc protobuf Protocol Buffers

This blog entry lists the process to use google's Protoco Buffers, on x64 Linux Mint 14.

1. Download protobuf-2.5.0.tar.bz2 from
https://code.google.com/p/protobuf/downloads/list


2.  Extract the file anywhere.

3. Under the extracted folder, run

$./configure
$make
$make check
$sudo make install

4.  View the README file in the folder, and test some common:

  $pkg-config --cflags protobuf         # print compiler flags
  $pkg-config --libs protobuf           # print linker flags
  $pkg-config --cflags --libs protobuf  # print both

5.  Download a proto file. e.g. from
https://developers.google.com/transit/gtfs-realtime/gtfs-realtime-proto

6.  Go to the proto file folder and generate the C++ header and source file:

$protoc gtfs-realtime.proto --cpp_out=./

Ref: https://developers.google.com/protocol-buffers/docs/proto


7. If there are some errors, check the environment variables 

$export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib   $export PKG_CONFIG_PATH=/usr/local/lib/pkgconfig

Ref:  http://blog.csdn.net/programmer_h/article/details/8890800


8.  Write a sample main file:

#include <iostream>
#include <string>
#include <fstream>
#include "gtfs-realtime.pb.h"
using namespace std;

int main()
{
   fstream file("alert2.dat");
   string outline;
   getline(file, outline);
   cout <&lt outline << endl;
}

9. Download a sample encoded binary data file: e.g.
 http://www.bart.gov/dev/gtrtfs/alerts.aspx


10. Compile:

$clang++ main.cpp gtfs-realtime.pb.cc `pkg-config --cflags --libs protobuf`