位操作 2016-08-08

[dayang]

268 Missing Number 187 Repeated DNA Sequences

[dayang]

/**
 * [AC] LeetCode 268 Missing Number
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    let res = 0;
    for(let i = 0; i < nums.length; i++){
        res ^= (i ^ nums[i]);
    }
    return res ^ nums.length;
};

[wolfogre]

等差数列求和，再减实际和的方法，与位运算相比缺点是可能出现上溢。

// [AC] LeetCode 268 Missing Number
public class Solution {
    public int missingNumber(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; ++i)
            sum += nums[i];
        return (0 + nums.length) * (nums.length + 1) / 2 - sum;
    }
}

[wolfogre]

// [AC] 187 Repeated DNA Sequences
public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Boolean[] record = new Boolean[1048576];
        ArrayList<String> result = new ArrayList<>();

        for(int i = 0; i <= s.length() - 10; ++i){
            String substr = s.substring(i, i + 10);
            int code = getTenDnaCode(substr);
            if(record[code] == null)
                record[code] = false;
            else
                if(record[code].equals(false)){
                    result.add(substr);
                    record[code] = true;
                }

        }
        return result;
    }

    private int getTenDnaCode(String s){
        if(s.length() != 10)
            throw new RuntimeException("Wrong length!");
        int result = 0;
        for(int i = 0; i < 10; ++i)
            result |= getCode(s.charAt(i)) << (i * 2);
        return result;
    }

    private int getCode(char ch){
        switch(ch){
            case 'A' :
                return 0;
            case 'C' :
                return 1;
            case 'G' :
                return 2;
            case 'T' :
                return 3;
        }
        throw new RuntimeException("Wrong char!");
    }
}

[SnackMen]

/*
*二分法
*[AC] LeetCode 268 Missing Number
*/
public class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length;
        int mid = 0;
        while(left<right){
            mid = (left+right)/2;[AC] LeetCode 268 Missing Number
            if(nums[mid]>mid)
                right=mid;
            else
                left=mid+1;
        }
        return left;
    }
}

[dayang]

/**
 * hash，没用到位操作
 * [AC] LeetCode 187 Repeated DNA Sequences
 * @param {string} s
 * @return {string[]}
 */
var findRepeatedDnaSequences = function (s) {
    if (s.length <= 10) return [];
    var res = [], hash = {}, i, len = s.length, subs;
    for (i = 0; i < len - 9; i++) {
        subs = s.substr(i, 10);
        if (hash[subs] !== undefined) {
            if (hash[subs] === 0) {
                res.push(subs);
                hash[subs]++;
            }
        } else {
            hash[subs] = 0;
        }
    }

    return res;
};

/**
 * 使用位操作，将10个字符变成整数作为hash key
 * @param {string} s
 * @return {string[]}
 */
var findRepeatedDnaSequences = function (s) {
    if (s.length <= 10) return [];
    var code = {'A':0,'G':1,'C':2,'T':3};
    var res = [], hash = {}, i, j, len = s.length,num;
    for (i = 0; i < len - 9; i++) {
        num = 0;
        for(j = i; j < i + 10; j++){
            num <<=2;
            num |= code[s[j]];
        }
        if(hash[num] !== undefined){
            if(hash[num] === 0){
                hash[num] ++;
                res.push(s.substr(i,10));
            }
        }else{
            hash[num] = 0;
        }
    }
    return res;
};

[zhaokuohaha]

268 - C# - 利用两个相同的数异或为零

public class Solution {
    public int MissingNumber(int[] nums) {
        for(int i=1; i<nums.Length; i++){
            nums[0] ^= nums[i]^i;
        }
        return nums[0] ^ nums.Length;
    }
}

[zhaokuohaha]

187 - C# - 直接用字符串做键

public class Solution
{
    public IList<string> FindRepeatedDnaSequences(string s)
    {
        List<string> res = new List<string>();
        Dictionary<string, bool> dic = new Dictionary<string, bool>();
        if (String.IsNullOrEmpty(s) || s.Length<10) return res;
        for(int i=9; i<s.Length; i++)
        {
            string ts = s.Substring(i - 9, 10);
            if (!dic.ContainsKey(ts)) dic.Add(ts, true);
            else
            {
                if (!res.Contains(ts)) res.Add(ts);
            }
        }
        return res;
    }
}

[wolfogre]

优化版，最快一次打败了96.24%

// [AC] 187 Repeated DNA Sequences
public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        ArrayList<String> result = new ArrayList<>();
        if(s.length() <= 10)
            return result;

        int[] record = new int[1048576];
        int code = 0;

        for(int i = 0; i < 10; ++i){
            code = code << 2;
            code |= getCode(s.charAt(i));
        }
        record[code] = 1;

        for(int i = 10; i < s.length(); ++i){
            code &= 0x3FFFF;// 00111111111111111111
            code = code << 2;
            code |= getCode(s.charAt(i));
            if(record[code] == 0)
                record[code] = 1;
            else
                if(record[code] == 1){
                    result.add(s.substring(i - 9, i + 1));
                    record[code] = 2;
                }
        }
        return result;
    }

    private int getCode(char ch){
        switch(ch){
            case 'A' :
                return 0;
            case 'C' :
                return 1;
            case 'G' :
                return 2;
            case 'T' :
                return 3;
        }
        throw new RuntimeException("Wrong char!");
    }
}