Leetcode: Palindrome Number

Problem

Leetcode link for this question
Determine whether an integer is a palindrome. Do this without extra space.

Analyze

This is the previous post on this question
This is easy question, just find the most left digit and then compare each digit from left-right ends to center.

Code

C++ code accept by Leetcode, which exclude negative number like -121 as palindrome

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0)
            return false;
        int highDigit = 1;
        while(x / highDigit >= 10)
            highDigit *= 10;
        int lowDigit = 1;
        while(highDigit > lowDigit){
            int high = (x / highDigit) % 10;
            int low = (x/lowDigit) % 10;
            if(high != low)
                return false;
            highDigit /= 10;
            lowDigit *= 10;
        }
        return true;
    }
};

C++ code for who consider negative number like -121 also as palindrome

class Solution {
public:
    bool isPalindrome(int x) {
        int highDigit = 1;
        while(x / highDigit >= 10 || x / highDigit <= -10)
            highDigit *= 10;
        int lowDigit = 1;
        while(highDigit > lowDigit){
            int high = (x / highDigit) % 10;
            int low = (x/lowDigit) % 10;
            if(high != low)
                return false;
            highDigit /= 10;
            lowDigit *= 10;
        }
        return true;
    }
};

Leetcode: String to Integer (atoi)

Problem

Leetcode link
Implement atoi to convert a string to an integer.

Analyze

This is the previous answer to this question

The complexity of this problem is how to handle edge cases.
For int, standard as 32-bit length, has a max value of (1<<31) - 1 and a min value of (1<<31).
When read each digit from string, need check if the result will be overflow.
And another situation is that the leading blank spaces, and possibly has + or -.

Code

class Solution {
public:
    const int max = (1<<31) - 1;
    const int min = -max - 1;

    inline bool willOverflow(int sign, int base, int digit) {
        static const int maxTenth = max / 10;
        static const int maxDigit = max % 10;
        static const int minTenth = - (min / 10);
        static const int minDigit = - (min % 10);
        if(sign == 1){
            return (base > maxTenth || base == maxTenth && digit > maxDigit);
        } else {
            return (base > minTenth || base == minTenth && digit > minDigit);
        }
    }

    // The test case only allow "    -123" like this, after hit sign or digit, can not take any invalid or blank char.
    int myAtoi(string str) {
        if (str.size() == 0) return 0;
        int sign = 1;
        bool gotNumber = false; //allow blank space before number
        bool gotSign = false; // allow <= 1 sign
        int result = 0;
        for(int i = 0; i < str.size(); ++i) {
            if(!gotNumber && str[i] == ' ') continue; 
            if(!gotNumber && !gotSign && (str[i] == '+' || str[i] == '-')){
                sign = str[i]=='-' ? -1 : 1;
                gotSign = true;
                gotNumber = true;
                continue;
            }
            if(str[i] < '0' || str[i] > '9')
                return result * sign;
            gotNumber = true;
            int digit = str[i] - '0';
            if(willOverflow(sign, result, digit))
                return sign == 1 ? max : min;
            result = result * 10 + digit;
        }
        return result * sign;
    }
};

Leetcode: Contains Duplicate II

Question

Contains Duplicate II
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

Analyze

It’s strait forward to using dictionary on this question. First run, save position of each number in the dictionary; Second run, check the dictionary to see if there is another duplication in this array and check the position of it.
But there is a situation that need take into consideration, that the array may contain the duplication multiple times. To deal with this, just checking in the first run, to see if the last position (if any) is close enough.

Code

C++ code

class Solution {
public:
    inline int abs(int v) {
        return v < 0 ? -v : v;
    }
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int, int> dict;
        for(int i=0; i<nums.size(); ++i) {
            if(dict.find(nums[i]) != dict.end()) {
                if(abs(dict[nums[i]]-i) <= k)
                    return true;
            }
            dict[nums[i]]=i;
        }
        for(int j=0; j<nums.size(); ++j){
            map<int,int>::iterator it = dict.find(nums[j]);
            map<int,int>::iterator endit = dict.end();
            if(endit != it){
                int i = it->second;
                if(i != j && abs(i-j) <= k)
                    return true;
            }
        }
        return false;
    }
};

Remapkey by Microsoft

Official remapkey.exe by MS. To edit the hardware keys to any keys you want.
Especially useful of Mac users on windows.
I always remap the “command” key to “control” and “control” to “command”. Then all the frequently used shortcuts like:

Cmd Windows Key Mac key
copy control + c command + c
paste control + v command + v
cut control + x command + x
select-all control + a command + a
save control + s command + s
new-tab control + t command + t
new-file control + n command + n

will remain the same as Mac OS.

Usage

Take my usage as example, swap the Command and Control:
Remapkey Usage

Open Remapkey.exe with Admin permission, then drag the left control on the above to the left windows in the bottom; and drag the left windows on the above to the left control at the bottom.
Then click the save and quit button.
It require a restart of windows, then enjoy!

Here is the software download:

RemapKey.zip from unieagle.net

Leetcode: Integer to Roman

Question:

Integer to Roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

Analyze:

Just handle each digit in the number.
For numbers from [0, 9], they are mapping to:
0 – ‘ ‘
1 – ‘I’
2 – ‘II’
3 – ‘III’
4 – ‘IV’
5 – ‘V’
6 – ‘VI’
7 – ‘VII’
8 – ‘VIII’
9 – ‘IX’

The patten is that for digit in [0,3], repeat ‘I’ digit times;
for digit == 4, ‘IV’
for digit in [5, 8], put digit-5 times ‘I’ after ‘V’;
for digit == 9, ‘IX’

Then from 10 – 90, using ‘X’, ‘L’, ‘C’ instead of ‘I’, ‘V’, ‘X’. So if we store all the available chars in an array, it just move the base index += 2 each time we handle next digit.

Code

C++ Code

char* intToRoman(int num) {
    char chars[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M', 'C', 'D'};
    char * result = malloc(100);
    if(num <= 0 || num >= 4000)
        return result;

    int tail = 100;
    int charBase = 0;
    while(num != 0)
    {
        int digit = num % 10;
        char temp[3];
        int templen = 0;
        if(digit <= 3)
        {
            for(int i = 1; i <= digit; ++i)
            {
                temp[i-1] = chars[charBase];
            }
            templen = digit;
        } 
        else if (digit == 4)
        {
            temp[0] = chars[charBase];
            temp[1] = chars[charBase + 1];
            templen = 2;
        }
        else if(digit <= 8)
        {
            temp[0] = chars[charBase + 1];
            templen = 1;
            for(int i = 6; i <= digit; ++i)
            {
                temp[i-5] = chars[charBase];
                templen += 1;
            }
        } 
        else
        {
            temp[0] = chars[charBase];
            temp[1] = chars[charBase + 2];
            templen = 2;
        }

        //copy temp to result
        tail = tail - templen;
        for(int i = 0; i < templen; ++i)
        {
            result[tail + i] = temp[i];
        }

        charBase += 2;
        num /= 10;
    }

    //move result to start
    for(int i = tail; i < 100; ++i) {
        result[i-tail] = result[i];
        result[i] = 0;
    }

    return result;
}

LeetCode: Reverse Integer

Previous Post

This is the previous post on same question.

Question

LeetCode Link
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321

Analyze

Careful about the overflow. For ruby, it’s not a problem. For c++, need more consideration.

Code

Ruby Code

# @param {Integer} x
# @return {Integer}
def reverse(x)
    sign = x >= 0 ? 1 : -1
    x = x.abs
    y = 0
    int_max = 2 ** 31 - 1
    while x > 0 do
        digit = x % 10
        y = y * 10 + digit
        if y > int_max
            y = 0
            break
        end
        x /= 10
    end
    y * sign
end

C++ Code

class Solution {
public:
    int reverse(int x) {
        int sign = 1;
        if(x < 0) {
            sign = -1;
            x = -x;
        }
        int int_max = (1 << 31) - 1; //notice the priority of << is lower than -
        int dime = int_max / 10;
        int tail = int_max % 10 + (sign == 1 ? 0 : 1);

        int y = 0;
        while(x > 0){
            int digit = x % 10;
            if(y > dime || (y == dime && digit > tail)){
                return 0;
            }
            y = y * 10 + digit;
            x /= 10;
        }
        return y * sign;
    }
};

LeetCode: ZigZag Conversion

Previous post

This is the old post on this question, using another method.

Question

Leetcode Link
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".

Analyze

This question is simple, one method is that build strings for each row, and for each char in the string, determine the target row of the position based on the total row count, and append it to the target string. Then concat all the strings together in the last.

Code

The fast ruby version

# @param {String} s
# @param {Integer} num_rows
# @return {String}
def convert(s, num_rows)
    result = []
    tail_size = num_rows > 2 ? num_rows - 2 : 0
    group_size = num_rows + tail_size

    s.length.times do |i|
        in_group_position = i % group_size
        target_row = if in_group_position < num_rows
            in_group_position
        else
            num_rows - 1 - (in_group_position - num_rows)
        end
        result[target_row] ||= ""
        result[target_row] << s[i]
    end

    result
end

Screen Shot 2016-05-04 at 16.20.51

Require Administration Permission in VS 2013

C++ Project

  1. Right click the Project, click Properties
  2. Navigate to Linker
  3. Navigate to Manifest File
  4. Edit the UAC Execution Level to requireAdministrator

C# project:

Edit the properties\app.manifest, modify the permission node as the one in the specifications there.

Debug with UAC:

Start the VisualStudio with Administrator permission, and you can debug the projects need UAC.

Distribution Items Equally in View with Auto-Layout in iOS

Taking this layout as example, we want to place 2 buttons in the view, and need them distributed in the view equally in the view.
Screen Shot 2016-02-27 at 21.57.16



So there are 3 spaces:
1. from superview left to center of “Previous” button;
2. from center of “Previous” button to center of “Next” button;
3. from center of “Next” button to right edge of superview.



If those 3 spaces are equal, then we achieved the goal.
It’s simple to do this with automatic layout in iOS:
Create 2 constrains:
Screen Shot 2016-02-27 at 21.58.19
1. from “Previous” button center to tailing of superview, with constant 0 and multiplier 3:1;
2. from “Next” button center to tailing of superview, with constant 0 and multiplier 3:2.



All set, enjoy!

Manage User Group in Mac

List all users

dscl . list /users
dscl . readall /users

List all groups

dscl . list /groups
dscl . readall /groups

Check members under a group

members () { dscl . -list /Users | while read user; do printf "$user "; dsmemberutil checkmembership -U "$user" -G "$*"; done | grep "is a member" | cut -d " " -f 1; };
members $group_name_you_want_to_check

Check groups a user belongs to

groups $user_name

Add user to a group

sudo dseditgroup -o edit -a $user_name_to_add -t user $group_want_add