[apprentissage de l'algorithme] 1486. Fonctionnement exclusif du tableau (Java / C / C + + / python / go / Rust)

Deux chapeaux blancs. 2021-10-13 16:50:23
apprentissage algorithme fonctionnement exclusif du


Merci beaucoup de lire cet article~ Bienvenue【- Oui.】【Collection】【Commentaires】~ Il n'est pas difficile d'abandonner,Mais ça doit être cool d'insister~ J'espère que nous progresserons tous un peu tous les jours~ Cet article est rédigé par Deux chapeaux blancs https://juejin.cn/user/2771185768884824/posts Blog original~


1486. Tableau Xor Operation:

Deux entiers.,n Et start .

Tableau nums Défini comme suit::nums[i] = start + 2 * i(Indice de 0 C'est parti.)Et n == nums.length .

Veuillez revenir. nums Tous les éléments en bitxor(XOR)Résultats ultérieurs.

Exemple 1

Entrée:
n = 5, start = 0
Produits:
8
Explication:
Tableau nums Pour [0, 2, 4, 6, 8],Parmi eux (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 .
"^" Xor bitwise XOR Opérateur.
Copier le Code

Exemple 2

Entrée:
n = 4, start = 3
Produits:
8
Explication:
Tableau nums Pour [3, 5, 7, 9],Parmi eux (3 ^ 5 ^ 7 ^ 9) = 8.
Copier le Code

Exemple 3

Entrée:
n = 1, start = 7
Produits:
7
Copier le Code

Exemple 4

Entrée:
n = 10, start = 5
Produits:
2
Copier le Code

Conseils

  • 1 <= n <= 1000
  • 0 <= start <= 1000
  • n == nums.length

Analyse

On peut suivre l'ordre du jour. ,Le cycle de la violence,Donc la complexité temporelle estO(n), Si la complexité temporelle est O(1) Et l'algorithme de ?

NotexVariable,^Est une opération XOR, L'opération Xor satisfait aux propriétés suivantes: :

  1. x ^ x = 0;
  2. x ^ 0 = x;
  3. x ^ y = y ^ x(Loi d'échange);
  4. (x ^ y) ^ z = x ^ (y ^ z)(Droit de l'Union);
  5. x ^ y ^ y = x(Réflexivité);
  6. Six- Oui.4Multiple de,x ^ (x + 1) ^ (x + 2) ^ (x + 3) = 0;
  • À calculer Formule de résultat Pour:start ^ (start + 2) ^ (start + 4) ^ ⋯ ^(start + 2 * (n − 1)).
  • S'il y a une fonction sumXor(x) Peut être calculé 0 ^ 1 ^ 2 ^ ⋯ ^ x .
  • Pour une variable xEtn,CalculsumXor(s - 1) ^ sumXor(s + n - 1)Les résultats de,D'après ce qui précède Nature1 Vous pouvez 0 ^ 1 ^ 2 ^ ... ^ (s - 1) La valeur de 0,C'est devenu 0 ^ s ^ (s + 1) ^ (s + 2) ^ ⋯ ^ (s + n - 1) ,Selon Nature2 Et 0 Faire une opération Xor ou vous - même , Et le résultat final est s ^ (s + 1) ^ (s + 2) ^ ⋯ ^ (s + n - 1) , Ce résultat est très proche de ce que nous allons calculer. .
  • Si on commande s = start / 2 ,Prends ça. Formule de résultat Convertir en (s ^ (s + 1) ^ (s + 2) ^ ⋯ ^ (s + n - 1)) * 2, Ce n'est pas vrai. , Parce que c'est fait divisé par 2Pendant le fonctionnement de, Le BIT le plus bas est perdu. , Mais nous pouvons gérer les bits les plus bas individuellement .
  • Observation Formule de résultat C'est clair. (start + 2),(start + 4) ,... ,(start + 2 * (n − 1)) Les mêmes propriétés impaires et paires ,EtstartD'accord., C'est le plus bas ou les deux. 0,Ou les deux.1, Base seulement 1 Seulement si l'opération Xor est effectuée 1.C'est juste questart Est impair et n C'est un nombre impair. , Le résultat final le plus bas e C'est ça. 1.
  • À ce moment - là, Formule de résultat Peut être transformé en: ((sumXor(s - 1) ^ sumXor(s + n - 1)) * 2) | e .

Tant que nous pouvons implémenter la fonction sumXor(x), Alors le calcul du problème peut être fait O(1)La complexité temporelle de,Selon Nature6 Et Nature2 On doit juste y réfléchir. xDivisé par4Le reste de, C'est le plus bas. 2Bits, On peut déduire ce qui suit: :

x % 4 = 0 Binaire de:xx...x00 x % 4 = 1 Binaire de:xx...x01 x % 4 = 2 Binaire de:xx...x10 x % 4 = 3 Binaire de:xx...x11

  • x % 4 = 0,sumXor(x) = x;
  • x % 4 = 1,sumXor(x) = (x - 1) ^ x, Disponibilité simplifiée sumXor(x) = 1;
  • x % 4 = 2,sumXor(x) = (x - 2) ^ (x - 1) ^ x, Disponibilité simplifiée sumXor(x) = x | 1;
  • x % 4 = 3,sumXor(x) = 0;
  • x % 4 équivalent à x & 3 Fonctionnement, Et en théorie, & L'opération est plus efficace que % Fonctionnement plus rapide;

Explication du problème

java

class Solution {
public int xorOperation(int n, int start) {
int s = start >> 1, e = n & start & 1;
int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
return ret << 1 | e;
}
public int sumXor(int x) {
switch (x & 3) {
case 0:
return x;
case 1:
return 1;
case 2:
return x | 1;
default:
// x & 3 == 3
return 0;
}
}
}
Copier le Code

c

int xorOperation(int n, int start) {
int s = start >> 1, e = n & start & 1;
int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
return ret << 1 | e;
}
int sumXor(int x) {
switch (x & 3) {
case 0:
return x;
case 1:
return 1;
case 2:
return x | 1;
default:
// x & 3 == 3
return 0;
}
}
Copier le Code

c++

class Solution {
public:
int xorOperation(int n, int start) {
int s = start >> 1, e = n & start & 1;
int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
return ret << 1 | e;
}
int sumXor(int x) {
switch (x & 3) {
case 0:
return x;
case 1:
return 1;
case 2:
return x | 1;
default:
// x & 3 == 3
return 0;
}
}
};
Copier le Code

python

class Solution:
def xorOperation(self, n: int, start: int) -> int:
def sumXor(x):
if x % 4 == 0:
return x
if x % 4 == 1:
return 1
if x % 4 == 2:
return x | 1
return 0
s = start >> 1
e = n & start & 1
ans = sumXor(s - 1) ^ sumXor(s + n - 1)
return ans << 1 | e
Copier le Code

go

func xorOperation(n, start int) (ans int) {
s, e := start>>1, n&start&1
ret := sumXor(s-1) ^ sumXor(s+n-1)
return ret<<1 | e
}
func sumXor(x int) int {
switch x & 3 {
case 0:
return x
case 1:
return 1
case 2:
return x | 1
default:
return 0
}
}
Copier le Code

rust

impl Solution {
pub fn xor_operation(n: i32, start: i32) -> i32 {
let s = start >> 1;
let e = n & start & 1;
let ret = Solution::sum_xor(s - 1) ^ Solution::sum_xor(s + n - 1);
return ret << 1 | e
}
fn sum_xor(x: i32) -> i32 {
match x & 3 {
0 => x,
1 => 1,
2 => x | 1,
_ => 0
}
}
}
Copier le Code

Insérer la description de l'image ici


Porte d'entrée d'origine


版权声明
本文为[Deux chapeaux blancs.]所创,转载请带上原文链接,感谢
https://qdmana.com/2021/10/20211013164946015z.html

  1. Projet Java: système de gestion du rendement des employés (Java + SSM + MySQL + Maven + HTML)
  2. CSS tips | one line of code to realize the integration of avatar and national flag
  3. Maotai and Paris Fashion Week joined hands to make Chinese elements appear on the show
  4. Wang Xiaoya showed up in a sleeveless skirt and reappeared her intellectual elegance. She was still full of temperament after leaving the nest CCTV
  5. Comment écrire un document de conception frontale
  6. Créer une api javascript haute performance avec Rust et l'exécuter dans webassembly
  7. Analyse de certains principes techniques clés du SDK de surveillance frontale
  8. Point de vue: la NFT de type portrait a formé un modèle d'entreprise. Quelles sont ses perspectives d'avenir et ses difficultés?
  9. Stars celebrate the motherland's birthday in patterns: Tang Yan Bixin, Liu Xiaoqing in military uniform, Zhao Liying and he Jiong send blessings
  10. L'amour entre Wing Mei et Luan Tree: de l'amour à première vue à l'amour éternel
  11. Disappeared car companies: tape measure is useless? Zhongtai is on the verge of death and has no way to return to heaven
  12. BUUCTF [极客大挑战 2019]Http
  13. element缓存到本地使用
  14. How can the volunteer army with less steel and more gas beat the American army with more steel and less gas? Changjin Lake gives you the answer
  15. CentOS installation source package nginx error
  16. Mise en cache des éléments pour utilisation locale
  17. Disappeared car companies: tape measure is useless? Zhongtai is on the verge of death and has no way to return to heaven
  18. He saifei est si naturel!58 ans est si beau, porter des vêtements de vieillesse pour accepter de vieillir!
  19. Finally pregnant! Seven years of pregnancy, collective blessing of the entertainment industry
  20. Wu Qili sent blessings on the national day. She looked haggard and thin on her own. It was worrying
  21. Error in spring source code compilation: the monoprocessor in reactor.core.publisher is outdated
  22. Buctf [geek Challenge 2019] http
  23. 20 个值得学习的 Vue 开源项目
  24. 20 projets open source à apprendre
  25. Scène et application de la manette des gaz anti - bavardage
  26. Qu'est - ce que j'ai gagné en abandonnant vue pour les six mois de React?
  27. À partir de [Bytecode cache] et de [http cache], intervieweur: « est - ce si mince? »
  28. [niveau intermédiaire et avancé] obligatoire, 30 + questions manuscrites à haute fréquence et réponses détaillées (dix mille caractères longs), voyez comment "vous" ne pouvez pas m'abattre
  29. Mise en œuvre d'un outil d'échafaudage universel pour l'ingénierie Web de 0 à 1
  30. 【中高级前端】必备,30+高频手写题及详细答案(万字长文),看“你”怎么难倒我
  31. In less than two days, the box office exceeded 400 million, and Changjin Lake broke out, breaking seven records in Chinese film history
  32. Tong Liya Jin Chen bumps her hair, Xie Na Zhao Liying bumps her shirt, and she sees EQ from the reaction
  33. react之组件生命周期
  34. L'équipe de vue dévoile un nouvel outil d'échafaudage rapide comme la foudre Create View, qui remplacera la vue CLI à l'avenir, avec seulement 300 lignes de code, apprenez - le!
  35. 20 dessins illustrant le fonctionnement du moteur de rendu du Navigateur
  36. In less than two days, the box office exceeded 400 million, and Changjin Lake broke out, breaking seven records in Chinese film history
  37. 千锋重庆web前端学习之理解CSS位置属性
  38. 什么是语义HTML标记以及如何使用它们?
  39. Si vous vous représentez avec un tableau, c'est le champ de Van Gogh.
  40. 前端面试手写代码
  41. 前端开发框架Vue中Vuex的使用原理分享
  42. vue-echarts初次体验
  43. 分享一些web前端开发好用的网站
  44. 每天读一点webpack-003
  45. react之组件生命周期
  46. Alibaba collection version of mybatis handwritten documents, Java front-end interview questions
  47. SpringBoot Java后端实现okhttp3超时设置
  48. react之組件生命周期
  49. Cycle de vie des composants de React
  50. 使用Reactor将阻塞调用变为异步非阻塞
  51. Baked cake wife sun photos, plain face on camera, beautiful appearance is still a beauty, watching children during the festival is a little helpless
  52. 亚洲知名插画师荒川(arakawa) 仅8件独版NFT作品系列《Can't Out》正式上架Element综合市场
  53. Taiyuan: singing, welcoming the national day, gathering to praise blessings
  54. Arakawa, un illustrateur Asiatique bien connu, n'a mis sur le marché que huit pièces de la collection NFT "can't out" en une seule édition.
  55. Résumé des questions d'entrevue Hadoop (II) - - hdfs
  56. 如何解决“Serverless”系统的冷启动问题
  57. BootstrapBlazor 模板安装
  58. BootstrapBlazor 模板安装
  59. Tong Liya Jin Chen bumps her hair, Xie Na Zhao Liying bumps her shirt, and she sees EQ from the reaction
  60. 使用ESLint+Prettier来统一前端代码风格