leetCode解题报告之SingleNumberI,II(知识点:位运算)

叁歲伎倆 2022-08-26 01:22 44阅读 0赞

由于两题是姐妹题，所以放在同一个博文里了！

**题目1：**

Given an array of integers, every element appears twice except for one. Find that single one.

Note:  
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

**题目2：**

Given an array of integers, every element appears three times except for one. Find that single one.

Note:  
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

不知道这个题目如何做分析和讲解，直接上AC代码，欢迎留言指点：

public class SingleNumber {
    	/* 简单的异或操作的处理！
    	 * 一个数组中只有一个数字出现了一次，其余都出现过两次，找出这个出现一次的数字
    	 * */
    	public int singleNumber1(int[] A) {
            int result = 0;
            for (int i=0; i<A.length; ++i){
            	result ^= A[i];
            }
    		return result;
        }
    	
    	/* 
    	 * 一个数组中只有一个数字出现了一次，其余都出现过三次，找出这个出现一次的数字
    	 * */
    	public int singleNumber2(int[] A) {
            if (A == null) return 0;
            int x0 = ~0, x1 = 0, x2 = 0, t;
            for (int i = 0; i < A.length; i++) {
                t = x2;
                x2 = (x1 & A[i]) | (x2 & ~A[i]);
                x1 = (x0 & A[i]) | (x1 & ~A[i]);
                x0 = (t & A[i]) | (x0 & ~A[i]);
            }
            return x1;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，44人围观）

还没有评论，来说两句吧...

相关阅读

相关【LeetCode】妙用位运算解题

【LeetCode】妙用位运算解题文章目录【LeetCode】妙用位运算解题交替位二进制数★ 插入★

ゝ一纸荒年。/ 2022年11月09日 14:24/ 0 赞/ 225 阅读

相关 leetCode解题报告之Clone Graph

题目： Clone an undirected graph. Each node in the graph contains a `label` and a list of

怼烎@/ 2022年08月26日 04:54/ 0 赞/ 128 阅读

相关 leetCode解题报告之Gas Station

题目： There are N gas stations along a circular route, where the amount of gas at station

偏执的太偏执、/ 2022年08月26日 04:45/ 0 赞/ 136 阅读

相关 leetCode解题报告之Candy（简单回溯）

题目： There are N children standing in a line. Each child is assigned a rating value. Yo

柔光的暖阳◎/ 2022年08月26日 04:44/ 0 赞/ 167 阅读

相关 leetCode解题报告之SingleNumberI,II(知识点:位运算)

由于两题是姐妹题，所以放在同一个博文里了！题目1： Given an array of integers, every element appears twic

叁歲伎倆/ 2022年08月26日 01:22/ 0 赞/ 45 阅读

相关 leetCode解题报告之Reorder List

题目： Given a singly linked list L: L0→L1→…→Ln\-1→Ln, reorder it to: L0→Ln→L1→Ln\-1→L2→

素颜马尾好姑娘i/ 2022年08月26日 00:45/ 0 赞/ 195 阅读

相关 leetCode解题报告之Sort List

勉励自己：坚持，谁说做工程的人不能学好算法！为面试做准备,加油！！！！！题目： Sort a linked list in O(n log n) time using c

你的名字/ 2022年08月25日 15:55/ 0 赞/ 106 阅读

相关 leetCode解题报告之Insertion Sort List

题目： Sort a linked list using insertion sort. 分析：这个题目是想要让我们来做一个链表的插入排序问题. 这样

曾经终败给现在/ 2022年08月25日 15:44/ 0 赞/ 195 阅读

相关二进制知识之位运算,

如果您是一名软件开发的从业人员,并且不知道下面的运算结果的话认真理解这篇文章或许可以帮助到你,本文转载不需要联系作者,也不用注明出处的,能帮助到你，觉得有用的话可以随意

你的名字/ 2022年06月12日 20:39/ 0 赞/ 331 阅读

相关 LeetCode: ZigZag Conversion 解题报告

ZigZag Conversion The string "PAYPALISHIRING" is written in a zigzag pattern on a give

- 日理万妓/ 2022年03月28日 15:44/ 0 赞/ 209 阅读