The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Solution I:

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        str1 = bin(x)[2:]
        str2 = bin(y)[2:]
        len1 = len(str1)
        len2 = len(str2)
        num = abs(len1 - len2)
        if len1 < len2:
            str1 = '0' * num + str1
        elif len2 < len1:
            str2 = '0' * num + str2

        res = 0
        for i in range(0, len(str1)):
            if str1[i] != str2[i]:
                res += 1
        return res

slt = Solution()
print(slt.hammingDistance(x=3, y=4))

Solution II:

class Solution(object):
    def hammingDistance(self, x, y):
        return bin(x ^ y).count('1')

via: http://zhangzhenyu.com.cn/, all copyright by Mr.zzy.

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output Fizz instead of the number and for the multiples of five output Buzz. For numbers which are multiples of both three and five output FizzBuzz.

Example:

Input:
n = 15

Output:
Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

Solution Ⅰ:

class Solution(object):
    def fizzBuzz(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        self = []
        for i in range(1, n+1):
            if i % 15 == 0:
                self.append('FizzBuzz')
            elif i % 3 == 0:
                self.append('Fizz')
            elif i % 5 == 0:
                self.append('Buzz')
            else:
                self.append(str(i))

        return self

Solution Ⅱ:

class Solution(object):
    def fizzBuzz(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        self = []
        for x in range(1, n+1):
            self.append("Fizz"[x % 3 * 4:] + "Buzz"[x % 5 * 4:] or x)
        return self

via: http://zhangzhenyu.com.cn/, all copyright by Mr.zzy.

用Python不仅能节省了大量coding / debug的时间。也让人在编程时更注重逻辑思考,印证了那句

Programming not coding

当然,缺点也十分明显,损失了大量的时间和内存性能,回头golang学起来哈


Russian Doll Envelopes

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:
Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Solution:

class Solution(object):
    """docstring for Solution"""
    def maxEnvelopes(self, envelopes):
        nums = sorted(envelopes, 
                      cmp = lambda x,y: x[0] - y[0] if x[0] != y[0] else y[1] - x[1])
        size = len(nums)
        dp = []
        for x in range(size):
            low, high = 0, len(dp) - 1
            while low <= high:
                mid = (low + high) / 2
                if dp[mid][1] < nums[x][1]:
                    low = mid + 1
                else:
                    high = mid - 1
            if low < len(dp):
                dp[low] = nums[x]
            else:
                dp.append(nums[x])
        return len(dp)

 

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector> pathSum(TreeNode* root, int sum) {
    vector > collect;  
    vector solution;  
    if(root!=NULL)  
        GetPath(root, sum, 0, solution, collect);  
    return collect;  
}  

void GetPath(TreeNode* node, int sum, int cal, vector& solution, vector >& collect)  {   
    solution.push_back(node->val);  
    cal += node->val;  
    if(cal == sum && node->left == NULL && node->right == NULL)  
    {  
        collect.push_back(solution);        
    }  
    else  
    {      
        if(node->left != NULL)  
        {        
          GetPath(node->left, sum, cal, solution, collect);        
        }  
        if(node->right != NULL)  
        {        
          GetPath(node->right, sum, cal, solution, collect);  
        }  
    }  
    solution.pop_back();  
    cal -= node->val;  
    return;  
    }
};

今天来公司写完周报,无聊又刷了几道题,这道题给我印象很深,虽然逻辑简单,但是代码相当优美.

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Solution:

/*Split the whole step into two binary characters added and carry. 
In fact all similar additions can be disassembled like this.*/
class Solution {
public:
    string addBinary(string a, string b) {
        string result = "";
        int c = 0;
        int i = a.size()-1;
        int j = b.size()-1;
        
        while(i>=0 || j>=0 || c==1)
        {
            c += i >= 0 ? a[i--] - '0' : 0;
            c += j >= 0 ? b[j--] - '0' : 0;
            result = char(c%2 + '0') + result;
            c /= 2;
        }
        return result;
    }
};

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Note: Your solution should be in logarithmic complexity.

Solution:

class Solution {
public:
    int findPeakElement(vector& num) {
        int n = num.size();
        if(n == 1) 
        {
            return 0;
        }

        int start = 0;
        int end = n - 1;
        int mid = 0;

        while(start <= end) { mid = start + (end - start) / 2; if((mid == 0 || num[mid] >= num[mid - 1]) && (mid == n - 1 || num[mid] >= num[mid + 1])) // mid is peak
            {
                return mid;
            } else if(mid > 0 && num[mid-1] > num[mid]) // mid is left
            {
                end = mid - 1;
            } else // mid is right 
            {
                start = mid + 1;
            }
        }
        return mid;
    } 
};

今天在StackOverflow上看到这样一道题,原题是这样的:

Divide a number by 3 without using *, /, +, -, % operators

===========================

This question has been asked in an Oracle interview.

How would you divide a number by 3 without using */+-%, operators?

The number may be signed or unsigned.

===========================

unsigned add(char const zero[], unsigned const x, unsigned const y) {
  // this exploits that &foo[bar] == foo+bar if foo is of type char*
  return (int)(uintptr_t)(&((&zero[x])[y]));
}

unsigned div_by(unsigned const x, unsigned const by) {
  unsigned floor = 0;
  for (unsigned cmp = 0, r = 0; cmp <= x;) {
    cmp = add(0,cmp,by);
    floor = r;
    r = add(0,r,1);
  }
  return floor;
}

===========================

Using cloud computing 😀

Google Search: 30 divided by 3

INTERSETING…

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Solution:

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # output[i] = (x0 * x1 * ... * xi-1) * (xi+1 * .... * xn-1)
        size = len(nums)
        output = [1] * size
        left = 1
        for x in range(size - 1):
            left *= nums[x]
            output[x + 1] *= left
        right = 1
        for x in range(size - 1, 0, -1):
            right *= nums[x]
            output[x - 1] *= right
        return output

Q1: Given an array of integers, every element appears twice except for one. Find that single one.

Solution:

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = nums[0]
        for i in range(1, len(nums)):
            ans = ans ^ nums[i]
        return ans

Continue reading