LeetCode Problem : Two Sum

Problem

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Code

class HashTable32
{
    static const unsigned int A = 2654435769;
    static const int m = 1024;
    int hash(unsigned int key);
    struct Node
    {
        int val;
        int index;
        Node* next;
        Node(int k,int i):val(k),index(i),next(0){}
    };
    Node* Bucket[m];
    public:
    HashTable32();
    ~HashTable32();
    void insert(int key,int i);
    bool find(int key,int j,int& index);
    bool find_r(int key,int j);
};


int HashTable32::hash(unsigned int key)
{
    int result = ((A*key)>>(sizeof(int)*CHAR_BIT - 10));
    return result;
}
HashTable32::HashTable32()
{
    for(int i = 0; i < m; ++i)
        Bucket[i] = 0;
}
HashTable32::~HashTable32()
{
    for(int i = 0; i < m; ++i){
        Node* node = Bucket[i];
        while(node){
            Node* temp = node->next;
            delete node;
            node = temp;
        }
    }
}
void HashTable32::insert(int key,int i)
{
    int hashVal = hash(key);
    Node* temp = new Node(key,i);
    temp->next = Bucket[hashVal];
    Bucket[hashVal] = temp;
}
bool HashTable32::find(int key,int j,int& index)
{
    int hashVal = hash(key);
    Node* node = Bucket[hashVal];
    if(!node){
        return false;
    }
    while(node){
        if(node->val == key && node->index > j){
            index = node->index;
            return true;
        }
        node = node->next;
    }
    return false;
}

bool HashTable32::find_r(int key,int j)
{
    int hashVal = hash(key);
    Node* node = Bucket[hashVal];
    if(!node){
        return false;
    }
    while(node){
        if(node->val == key && node->index == j)
        return true;
        node = node->next;
    }
    return false;
}

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        vector<int> result;
        int n = numbers.size();
        HashTable32 htbl;
        for(int i = 0;i < n; ++i){
            htbl.insert(numbers[i],i + 1);
        }
        for(int i = 0;i < n - 1; ++i){
            int index;
            if(htbl.find(target - numbers[i],i + 1,index)){
                result.push_back(i+1);
                result.push_back(index);
                return result;
            }
        }
        return result;
    }
};

LeetCode Problem : Add Two Numbers

Problem

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Code

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int carry = 0;
    ListNode *head = 0,*node = 0;
    while(l1 || l2){
        int num1 = 0,num2 = 0;
        if(l1){
            num1 = l1->val;
            l1 = l1->next;
        }
        if(l2){
            num2 = l2->val;
            l2 = l2->next;
        }
        int sum = num1 + num2 + carry;
        carry = sum / 10;
        sum = sum % 10;
        if(!head){
            head = new ListNode(sum);
            node = head;
        }
        else{
            node->next = new ListNode(sum);
            node = node->next;
        }
    }
    if(carry > 0)
        node->next = new ListNode(carry);
    return head;
}

LeetCode Problem : ZigZag Conversion

Problem

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P   A   H   N
A P L S I I G

Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Code

string convert(string s, int nRows) {
    // Note: The Solution object is instantiated only once and is reused by each test case.    
    int n = s.size();
    if(nRows == 1)
        return s;
    bool bleft;
    int lgap = 2*(nRows - 1);
    int rgap = 0;
    int count = 0,offset;
    string out;
    out.resize(n);
    for(int i = 0;i < nRows; ++i){
        offset = i; 
        bleft = false;
        while(offset < n){
            out[count++] = s[offset];
            bleft = !bleft;
            if(i == 0)
             offset += lgap;
            else if(i == nRows - 1)
             offset += rgap;
            else
             offset += (bleft ? lgap : rgap);
        }
        lgap -= 2;
        rgap += 2;
    }
    return out;
}

LeetCode Problem : Reverse Integer

Problem

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

Code

int rev_r(int num,int prod)
{
    if(num/10 == 0)
        return 10*prod + num;
    int n = num % 10;
    return rev_r(num/10,10*prod + n);
}
int reverse(int x) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    int num = abs(x);
    bool isNegative = (x < 0);
    while(num !=0 && num %10 == 0)
        num /= 10;
    int ret = rev_r(num,0);
    if(isNegative)
        ret *= -1;
    return ret;  
}

LeetCode Problem : String to Integer (atoi)

Problem

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

spoilers alert... click to show requirements for atoi.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Code

bool isWhitespace(char c)
{
    return (c == ' ' || c == '\t' || c == '\n' ||
    c == '\v' || c == '\f' || c == '\r');
}
int atoi(const char *str) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    if(!str)
        return 0;
    bool isNegative = false;
    while(*str && (*str < '0' || *str > '9')){
        if(isWhitespace(*str)){
            ++str;continue;
        }
        if(*str == '-'){
            isNegative = true;
            ++str;break;
        }
        else if(*str == '+'){
            //isNegative = true;
            ++str;break;
        }
        else
            return 0;
    }
    int sum = 0;
    while(*str){
        if(*str >= '0' && *str <= '9'){
            if(sum > INT_MAX/10){
                if(isNegative)
                    return INT_MIN;
                else
                    return INT_MAX;
            }
            else if(sum == INT_MAX/10){
                if(isNegative){
                    if(*str - '0' > INT_MAX%10)
                        return INT_MIN;
                    sum = 10*sum + (*str - '0');
                }
                else{
                if(*str - '0' > INT_MAX%10)
                return INT_MAX;
                sum = 10*sum + (*str - '0');
                }
            }
            else
                sum = 10*sum + (*str - '0');
        }
        else
            break;
        ++str;
    }
    if(isNegative)
    sum *= -1;
    return sum; 
}

LeetCode Problem : Palindrome Number

Problem

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

Code

int numDigits(int n){
    int count = 1;
    while(n/10 != 0 ){
        n = n/10;
        count *= 10;
    }
    return count;
}
bool isPalindrome(int x) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    if(x < 0)
        return false;
    int n1 = numDigits(x);
    int n2 = 1;
    while(n1 > n2){
        if(( x/n1 % 10 ) != ( x/n2 % 10 ))
            return false;
        n2 *= 10;n1 /= 10;
    }
    return true; 
}

LeetCode Problem : Longest Substring Without Repeating Characters

Problem

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Code

int lengthOfLongestSubstring(string s) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    int n = s.size();
    if(n < 2)
        return n;
    int max_a = 1;
    vector<int> M(n,1);
    for(int i = 1;i < n; ++i){
        for(int j = i - 1;j >= i - M[i - 1]; --j){
            if(s[i] != s[j]){
                ++M[i];
                if(max_a < M[i])
                    max_a = M[i];
            }
            else
                break;
        }
    }
    return max_a;
}