LeetCode - Day 1

1. Two Sum

Given 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
Examples:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

读入数组中的一个数num1，需要找num2使得num1 + num2 = target。
建立一个空字典re_dict，用于存放待寻找的num2（即target - num1），key为num2，value为下标值。继续遍历数组，判断num[i]是否存在对应re_dict中的key：有则返回key对应的value和此时的i；无则继续将target - num[i]存入re_dict。
所以整个过程是：遍历整个nums，读入的num1如果不在re_dict中就把它对应的num2计算出来包括下标一起存到字典中；如果在就直接返回两者的下标。

class Solution:
    def twoSum(self, nums, target):
        if len(nums)<=1:
            return false
        else:
            re_dict = {}
            for i in range(len(nums)):
                if nums[i] in re_dict:
                    return (re_dict[nums[i]], i)
                else:
                    re_dict[target - nums[i]] = i

注：在python的set和dict中使用x in s的时间复杂度ave为O(1)
以上解法的时间复杂度为O(n)

421. Maximum XOR of Two Numbers in an Array

Given anon-emptyarray of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 2^31.Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.Could you do this in O(n) runtime?
Example:

Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.

参考大神StefanPochmann的代码。看了很久才理解。
利用动态规划的思想。题目中说ai < 2³¹，用位运算比较方便。要求求出XOR的最大值，则我们从左到右（高位到低位）按位读数。如果我们已经知道了最大的前七位，我们很希望第八位是1（最大），那么我们就假设第八位为1，前七位作为已知前缀。XOR运算有个规律：a^b=c,a^c=b,b^c=a。这时我们将假设的值与所有数的八位前缀做XOR运算，只要存在一个运算的结果（即c = answer^b）仍旧在所有数的八位前缀中，那么就说明存在这样两个数XOR的值使得第八位为1，此时继续遍历直到32位全部完成。大神的算法有几个细节很巧妙：
1.any返回的为bool，只要存在一个True那么就会返回True。python中True = 1，False = 0，可以直接做数值运算。
2.每一次遍历之前answer都进行一次<<1运算。因为是按位判断，所以answer的值也是按位通过any来改变。
3.由于XOR以及动态规划上一个结果影响下一个结果的特性，处于前缀状态的answer的值取决于上一个前缀，并不会出现多个值交叉影响结果的情况。
6行代码，66666666.

class Solution(object):
    def findMaximumXOR(self, nums):
        answer = 0
        for i in range(32)[::-1]:
                answer <<= 1 prefixes = {num >> i for num in nums}
                answer += any(answer ^ 1 ^ p in prefixes for p in prefixes)
        return answer

注：在python的set和dict中使用x in s的时间复杂度ave为O(1)
以上解法的时间复杂度为O(n)