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.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
Continue readingThere are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.
Continue readingGiven an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Continue readingGiven an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Today, I have taken an interview from Wechat.
To be honest, this question is easy, but I do not have sufficient time to complete coding. Maybe I took too much time in same trivial points with the “VERY PROFESSIONAL” interviewer.
The actual question is find the lowest common ancestor of three given nodes, but I thought we can expend this question to N nodes. For testing this question rapidly, I reuse the previous code of constructing a binary tree by the in-order and post-order traversals.
Continue readingThe Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Now your job is to find the total Hamming distance between all pairs of the given numbers.
Example:
Input: 4, 14, 2
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Note:
0 to 10^910^4.1）计算负数的逆元
def negative(n):
return bit_add(~n, 1)
2）加法计算
def bit_add(a, b):
b &= (2 ** 32 - 1)
while b:
tmp = a
sum = tmp ^ b
carry = (tmp & b) << 1
return a
3）减法计算
def bit_sub(a, b):
return bit_add(a, negative(b))
4）乘法计算
def bit_mul(a, b):
result = 0
while b:
if b & 0x1:
result = bit_add(result, a)
b >>= 1
a <<= 1
return result
乘法模拟手工计算乘法的流程，将乘数b的二进制表示从左往右移动，当最低位为1时 (b & 0x1 == 1)，把被乘数a加到result中，同时将被乘数a向左移动一位。
5）除法计算
def bit_div(x, y):
result = 0
for i in range(32)[::-1]:
if (x >> i) >= y:
result += (1 << i)
x -= (y << i)
return result
考虑32位整数表示 (64位改一下 i 就可以了)。从最大的倍数开始遍历，如果被除数x >> i 大于除数y，说明该位商为1，将1<<i加到结果中，并缩小x。