[LintCode/LeetCode] Single Number I & II [位运算]

Drinkey 发布于2019-08-14 15:33 / 3374人阅读

摘要：整个过程相当于，直接在和里去掉既是又是的。所以最后返回的，一定是只出现过一次的，而出现两次的都在里，出现三次的都被消去了。

Single Number I Problem

Given 2*n + 1 numbers, every numbers occurs twice except one, find it.

Example

Given [1,2,2,1,3,4,3], return 4

Challenge

One-pass, constant extra space.

Note

只要循环异或，出现两次的都变成0了，最后只剩下出现一次的single number。但要注意，要分析A为空或为null的情况，返回0.

Solution

public class Solution {
    public int singleNumber(int[] A) {
        if (A == null || A.length == 0) return 0;
        int n = 0;
        for (int num: A) {
            n ^= num;
        }
        return n;
    }
}

HashSet

public class Solution {
    public int singleNumber(int[] A) {
        if (A == null || A.length == 0) return 0;
        Set set = new HashSet();
        int res = 0;
        for (int a: A) {
            if (set.contains(a)) set.remove(a);
            else set.add(a);
        }
        res = set.iterator().next();
        return res;
    }
}

Single Number II Problem

Given 3*n + 1 numbers, every numbers occurs triple times except one, find it.

Example

Given [1,1,2,3,3,3,2,2,4,1] return 4

Challenge

One-pass, constant extra space.

Note

假设数a第一次出现，只存在ones里，第二次出现，从ones里消去，然后存在twos里，第三次出现，由于ones不存取已经在twos里的数，就只从twos里消去。整个过程相当于，直接在ones和twos里去掉既是ones又是twos的threes。所以最后返回的ones，一定是只出现过一次的single number，而出现两次的都在twos里，出现三次的都被消去了。

Solution

public class Solution {
    public int singleNumberII(int[] A) {
        int ones = 0, twos = 0;
        for (int a: A) {
            ones = ones^a & ~twos;
            twos = twos^a & ~ones;
        }
        return ones;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65845.html

[LintCode/LeetCode] Combination Sum I &amp; II

摘要：和唯一的不同是组合中不能存在重复的元素，因此，在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

ThreeWords 2019-08-14 15:23 评论0 收藏0
[LintCode/LeetCode] Jump Game I &amp; II

摘要：建立动规数组，表示从起点处到达该点的可能性。循环结束后，数组对所有点作为终点的可能性都进行了赋值。和的不同在于找到最少的步数。此时的一定是满足条件的最小的，所以一定是最优解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

rose 2019-08-14 15:27 评论0 收藏0
[LintCode/LeetCode] Subsets &amp; Subsets II

Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...

tracy 2019-08-14 14:26 评论0 收藏0
[LintCode/LeetCode] Single Number III

摘要：去掉最后一个保留最后一个保留最后一个保留第一个这道题在论坛里参考了和两位仁兄的解法。思想是将中所有的数进行异或运算。不同的两个数异或的结果，一定至少有一位为。最后，将和存入数组，返回。 Problem Given 2*n + 2 numbers, every numbers occurs twice except two, find them. Example Given [1,2,2...

lanffy 2019-08-14 15:33 评论0 收藏0
[LintCode/LeetCode] Unique Paths II

摘要：和完全一样的做法，只要在初始化首行和首列遇到时置零且即可。对了，数组其它元素遇到也要置零喏，不过就不要啦。 Problem Follow up for Unique Paths: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle...

firim 2019-08-14 15:29 评论0 收藏0