只出現(xiàn)一次的數(shù)字
給你一個(gè) 非空 整數(shù)數(shù)組 nums 卷仑，除了某個(gè)元素只出現(xiàn)一次以外窜锯，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。
你必須設(shè)計(jì)并實(shí)現(xiàn)線性時(shí)間復(fù)雜度的算法來(lái)解決此問(wèn)題眉菱，且該算法只使用常量額外空間华坦。
異或，相同為0，不同為1，所以任何數(shù)和0做異或都是等于本身，本身和本身異或?yàn)?
class Solution {
public int singleNumber(int[] nums) {
int r = 0;
for(int i=0;i<nums.length;i++){
r = r^nums[i];
}
return r;
}
}
只出現(xiàn)一次的數(shù)字Ⅱ
給你一個(gè)整數(shù)數(shù)組 nums 警医，除某個(gè)元素僅出現(xiàn) 一次 外吟温，其余每個(gè)元素都恰出現(xiàn) 三次 律秃。請(qǐng)你找出并返回那個(gè)只出現(xiàn)了一次的元素柜裸。
你必須設(shè)計(jì)并實(shí)現(xiàn)線性時(shí)間復(fù)雜度的算法且不使用額外空間來(lái)解決此問(wèn)題蔬崩。
示例 1：
輸入：nums = [2,2,3,2]
輸出：3
示例 2：
輸入：nums = [0,1,0,1,0,1,99]
輸出：99
數(shù)字的二進(jìn)制形式险掀，對(duì)于出現(xiàn)三次的數(shù)字死宣，各 二進(jìn)制位 出現(xiàn)的次數(shù)都是 3的倍數(shù)。
因此橡淆，統(tǒng)計(jì)所有數(shù)字的各二進(jìn)制位中 1 的出現(xiàn)次數(shù)构韵，并對(duì) 3 求余，結(jié)果則為只出現(xiàn)一次的數(shù)字矛绘。
class Solution {
public int singleNumber(int[] nums) {
int r = 0;
for(int i=0;i<32;i++){//對(duì)每一位
int count = 0;//統(tǒng)計(jì)數(shù)組中所有數(shù)字的二進(jìn)制 在 i 位上 是 1 的個(gè)數(shù)
for(int j=0;j<nums.length;j++){
if(((nums[j]>>i)&1)==1){//nums[j] 二進(jìn)制 i 位 上是否是 1
count++;
}
}
if(count%3==0){
continue;
}else{
//i 位上 1 的個(gè)數(shù)不是 3 的倍數(shù)喧锦，因?yàn)橹怀霈F(xiàn)了 1 次的數(shù)貢獻(xiàn)出了 1
r = r | (1<<i);
}
}
return r;
}
}
尋找重復(fù)數(shù)
給定一個(gè)包含 n + 1 個(gè)整數(shù)的數(shù)組 nums 定铜，其數(shù)字都在 [1, n] 范圍內(nèi)（包括 1 和 n），可知至少存在一個(gè)重復(fù)的整數(shù)涩惑。
假設(shè) nums 只有 一個(gè)重復(fù)的整數(shù) ，返回 這個(gè)重復(fù)的數(shù) 晋被。
你設(shè)計(jì)的解決方案必須 不修改 數(shù)組 nums 且只用常量級(jí) O(1) 的額外空間。
示例 1：
輸入：nums = [1,3,4,2,2]
輸出：2
示例 2：
輸入：nums = [3,1,3,4,2]
輸出：3
class Solution {
public int findDuplicate(int[] nums) {
int slow=0,fast=0;
while(true){
slow = nums[slow];
fast = nums[nums[fast]];
if(slow==fast){//相遇了翘魄，但是不是在入環(huán)口 根據(jù)定律：入環(huán)口到相遇點(diǎn)的距離（腹躁，即慢指針還需要走的路程到入環(huán)點(diǎn)->包含轉(zhuǎn)圈圈的）等于起點(diǎn)到入環(huán)口的的距離
fast = 0;
while(nums[fast]!=nums[slow]){
slow=nums[slow];
fast=nums[fast];
}
return nums[slow];
}
}
}
}
存在重復(fù)元素 2
給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k 弱左，判斷數(shù)組中是否存在兩個(gè) 不同的索引 i 和 j ，滿足 nums[i] == nums[j] 且 abs(i - j) <= k 九妈。如果存在翠霍，返回 true 棵癣；否則壁榕，返回 false 牡辽。
滑動(dòng)窗口 + 哈希表
整理題意：是否存在長(zhǎng)度不超過(guò)的 k+1 窗口挺尿，窗口內(nèi)有相同元素窄俏。
我們可以從前往后遍歷 nums踪区，同時(shí)使用 Set 記錄遍歷當(dāng)前滑窗內(nèi)出現(xiàn)過(guò)的元素拦盹。
假設(shè)當(dāng)前遍歷的元素為 nums[i]：下標(biāo)小于等于 k（起始滑窗長(zhǎng)度還不足 k+1）：直接往滑窗加數(shù)养铸，即將當(dāng)前元素加入 Set 中；下標(biāo)大于 k：將上一滑窗的左端點(diǎn)元素 nums[i?k?1] 移除轧膘，判斷當(dāng)前滑窗的右端點(diǎn)元素 nums[i] 是否存在 Set 中钞螟，若存在，返回 True谎碍，否則將當(dāng)前元素 nums[i] 加入 Set 中筛圆。重復(fù)上述過(guò)程，若整個(gè) nums 處理完后仍未找到椿浓，返回 False。
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
int n = nums.length;
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
if (i > k) set.remove(nums[i - k - 1]);
if (set.contains(nums[i])) return true;
set.add(nums[i]);
}
return false;
}
}
數(shù)組中最小正整數(shù)
給你一個(gè)未排序的整數(shù)數(shù)組 nums 闽晦，請(qǐng)你找出其中沒(méi)有出現(xiàn)的最小的正整數(shù)扳碍。
請(qǐng)你實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(n) 并且只使用常數(shù)級(jí)別額外空間的解決方案。
示例 1：
輸入：nums = [1,2,0]
輸出：3
示例 2：
輸入：nums = [3,4,-1,1]
輸出：2
示例 3：
輸入：nums = [7,8,9,11,12]
輸出：1
對(duì)于一個(gè)長(zhǎng)度為 N 的數(shù)組仙蛉，其中沒(méi)有出現(xiàn)的最小正整數(shù)只能在 [1,N+1] 中笋敞。這是因?yàn)槿绻?[1,N] 都出現(xiàn)了，那么答案是 N+1
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for(int i=0;i<n;i++){
if(nums[i]<=0){
nums[i]=n+1;
}
}
for(int i=0;i<n;i++){
//得到該數(shù)的絕對(duì)值
int t = Math.abs(nums[i]);
if(t>n){
continue;
}
nums[t-1]=-1*Math.abs(nums[t-1]);
}
for(int i=0;i<n;i++){
if(nums[i]>0){//表示沒(méi)有數(shù)來(lái)覆蓋這個(gè)位置
return i+1;
}
}
return n+1;
}
}
丟失的數(shù)字
給定一個(gè)包含 [0, n] 中 n 個(gè)數(shù)的數(shù)組 nums 荠瘪，找出 [0, n] 這個(gè)范圍內(nèi)沒(méi)有出現(xiàn)在數(shù)組中的那個(gè)數(shù)夯巷。
示例 1：
輸入：nums = [3,0,1]
輸出：2
解釋：n = 3，因?yàn)橛?3 個(gè)數(shù)字哀墓，所以所有的數(shù)字都在范圍 [0,3] 內(nèi)趁餐。2 是丟失的數(shù)字，因?yàn)樗鼪](méi)有出現(xiàn)在 nums 中篮绰。
示例 2：
輸入：nums = [0,1]
輸出：2
解釋：n = 2后雷，因?yàn)橛?2 個(gè)數(shù)字，所以所有的數(shù)字都在范圍 [0,2] 內(nèi)吠各。2 是丟失的數(shù)字臀突，因?yàn)樗鼪](méi)有出現(xiàn)在 nums 中。
示例 3：
輸入：nums = [9,6,4,2,3,5,7,0,1]
輸出：8
解釋：n = 9贾漏，因?yàn)橛?9 個(gè)數(shù)字候学，所以所有的數(shù)字都在范圍 [0,9] 內(nèi)。8 是丟失的數(shù)字纵散，因?yàn)樗鼪](méi)有出現(xiàn)在 nums 中梳码。
示例 4：
輸入：nums = [0]
輸出：1
解釋：n = 1隐圾，因?yàn)橛?1 個(gè)數(shù)字，所以所有的數(shù)字都在范圍 [0,1] 內(nèi)边翁。1 是丟失的數(shù)字翎承，因?yàn)樗鼪](méi)有出現(xiàn)在 nums 中。
找缺失數(shù)符匾、找出現(xiàn)一次數(shù)都是異或的經(jīng)典應(yīng)用叨咖。
我們可以先求得 [1,n] 的異或和 ans，然后用 ans 對(duì)各個(gè) nums[i] 進(jìn)行異或啊胶。這樣最終得到的異或和表達(dá)式中甸各，只有缺失元素出現(xiàn)次數(shù)為 1 次，其余元素均出現(xiàn)兩次（x⊕x=0）焰坪，即最終答案 ans 為缺失元素趣倾。
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int r = 0;
for(int i=0;i<=n;i++){
r = r^i;
}
for(int i=0;i<n;i++){
r = r^nums[i];
}
return r;
}
}
錯(cuò)誤的集合
集合 s 包含從 1 到 n 的整數(shù)。不幸的是某饰，因?yàn)閿?shù)據(jù)錯(cuò)誤儒恋，導(dǎo)致集合里面某一個(gè)數(shù)字復(fù)制了成了集合里面的另外一個(gè)數(shù)字的值，導(dǎo)致集合 丟失了一個(gè)數(shù)字 并且 有一個(gè)數(shù)字重復(fù) 黔漂。
給定一個(gè)數(shù)組 nums 代表了集合 S 發(fā)生錯(cuò)誤后的結(jié)果诫尽。
請(qǐng)你找出重復(fù)出現(xiàn)的整數(shù)，再找到丟失的整數(shù)炬守，將它們以數(shù)組的形式返回牧嫉。
示例 1：
輸入：nums = [1,2,2,4]
輸出：[2,3]
示例 2：
輸入：nums = [1,1]
輸出：[1,2]
class Solution {
public int[] findErrorNums(int[] nums) {
int n = nums.length;
int xor = 0;
for(int i=1;i<=n;i++){
xor = xor ^ i;
}
for(int i=0;i<n;i++){
xor = xor ^ nums[i];
}
int lowBit = xor & (xor ^ (xor-1));
int num1 = 0;
int num2 = 0;
for(int i=1;i<=n;i++){
if((i & lowBit) ==0){
num1 = num1 ^ i;
}else{
num2 = num2 ^ i;
}
}
for(int i=0;i<n;i++){
if((nums[i] & lowBit) ==0){
num1 = num1 ^ nums[i];
}else{
num2 = num2 ^ nums[i];
}
}
for(int i=0;i<n;i++){
if(nums[i]==num1){
return new int[]{num1,num2};
}
}
return new int[]{num2,num1};
}
}
小于n的最大值-字節(jié)面試題
數(shù)組A中給定可以使用的1~9的數(shù)，返回由A數(shù)組中的元素組成的小于n（n > 0）的最大數(shù)减途。 例如：A = {1, 2, 4, 9}酣藻，n = 2533，返回2499鳍置。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
private static int result = 0;
public static void main(String[] args) {
int[] nums = new int[]{1,2,4,9};
int target = 2533;
List<Integer> sk = new ArrayList<>();
Arrays.sort(nums);
getMinNMax(nums,sk,target);
System.out.println(result);
}
public static void getMinNMax(int[] nums,List<Integer> sk,int target){
int r = getSum(sk);
if(r<target){
result = Math.max(r,result);
}
if(r>=target){
return;
}
for(int i=0;i< nums.length;i++){
sk.add(nums[i]);
getMinNMax(nums,sk,target);
sk.remove(sk.size()-1);
}
}
public static int getSum(List<Integer> sk){
int r = 0;
int t = 1;
for(int i=sk.size()-1;i>=0;i--){
r+=t*sk.get(i);
t*=10;
}
return r;
}
}
