国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

Drinkey / 3517人閱讀

摘要:整個過程相當(dāng)于,直接在和里去掉既是又是的。所以最后返回的,一定是只出現(xiàn)過一次的,而出現(xiàn)兩次的都在里,出現(xiàn)三次的都被消去了。

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

只要循環(huán)異或,出現(xiàn)兩次的都變成0了,最后只剩下出現(xiàn)一次的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

假設(shè)數(shù)a第一次出現(xiàn),只存在ones里,第二次出現(xiàn),從ones里消去,然后存在twos里,第三次出現(xiàn),由于ones不存取已經(jīng)在twos里的數(shù),就只從twos里消去。整個過程相當(dāng)于,直接在ones和twos里去掉既是ones又是twos的threes。所以最后返回的ones,一定是只出現(xiàn)過一次的single number,而出現(xiàn)兩次的都在twos里,出現(xiàn)三次的都被消去了。

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;
    }
}

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/65845.html

相關(guān)文章

  • [LintCode/LeetCode] Combination Sum I & II

    摘要:和唯一的不同是組合中不能存在重復(fù)的元素,因此,在遞歸時將初始位即可。 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 評論0 收藏0
  • [LintCode/LeetCode] Jump Game I & II

    摘要:建立動規(guī)數(shù)組,表示從起點處到達該點的可能性。循環(huán)結(jié)束后,數(shù)組對所有點作為終點的可能性都進行了賦值。和的不同在于找到最少的步數(shù)。此時的一定是滿足條件的最小的,所以一定是最優(yōu)解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

    rose 評論0 收藏0
  • [LintCode/LeetCode] Subsets & 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 評論0 收藏0
  • [LintCode/LeetCode] Single Number III

    摘要:去掉最后一個保留最后一個保留最后一個保留第一個這道題在論壇里參考了和兩位仁兄的解法。思想是將中所有的數(shù)進行異或運算。不同的兩個數(shù)異或的結(jié)果,一定至少有一位為。最后,將和存入數(shù)組,返回。 Problem Given 2*n + 2 numbers, every numbers occurs twice except two, find them. Example Given [1,2,2...

    lanffy 評論0 收藏0
  • [LintCode/LeetCode] Unique Paths II

    摘要:和完全一樣的做法,只要在初始化首行和首列遇到時置零且即可。對了,數(shù)組其它元素遇到也要置零喏,不過就不要啦。 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 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<