[algorithme] swordfinger offer2 golang question d'entrevue 2: addition binaire

[Algorithmes] Un doigt d'épée.offer2 golang Questions d'entrevue2：Addition binaire

Titre1:

Compte tenu de deux 01 String a Et b ,Veuillez calculer leur somme,Et sortie sous forme de chaîne binaire.

Entrée comme Non vide Chaîne et ne contient que des nombres 1 Et 0.

Exemple 1:

Entrée: a = “11”, b = “10”
Produits: “101”
Exemple 2:

Entrée: a = “1010”, b = “1011”
Produits: “10101”

Conseils：

Chaque chaîne est composée uniquement de caractères ‘0’ Ou ‘1’ Composition.
1 <= a.length, b.length <= 10^4
Chaîne sinon “0” ,Il n'y a pas de zéros d'avance..

Source:：Boucle de force（LeetCode）
Liens：https://leetcode-cn.com/problems/JFETK5
Le droit d'auteur est la propriété du réseau de saisie.Pour les réimpressions commerciales, veuillez contacter l'autorisation officielle,Reproduction non commerciale Veuillez indiquer la source.

Idées1: Addition binaire analogique

Complexité temporelle de l'addition binaire analogique O(n)

Code

func addBinary(a string, b string) string {
    
	//Idées: Calcul binaire analogique
	length := len(a)
	if len(b) > len(a) {
    
		length = len(b)
	}
	//Retour de la construction
	resBs := make([]byte, length)
	// Pointeur vers l'arrière et vers l'avant 
	aP, bP := len(a)-1, len(b)-1
	//Oui Non
	up := 0
	for i := len(resBs) - 1; i >= 0; i-- {
    
		var aByte byte = '0'
		var bByte byte = '0'
		if aP >= 0 {
    
			aByte = a[aP]
			aP--
		}
		if bP >= 0 {
    
			bByte = b[bP]
			bP--
		}
		// Nombre de statistiques
		count1 := 0
		if aByte == '1' {
    
			count1++
		}
		if bByte == '1' {
    
			count1++
		}
		count1 += up
		// Déterminer la valeur actuelle et up
		if count1 == 0 {
    
			up = 0
			resBs[i] = '0'
		} else if count1 == 1 {
    
			up = 0
			resBs[i] = '1'
		} else if count1 == 2 {
    
			up = 1
			resBs[i] = '0'
		} else {
    
			up = 1
			resBs[i] = '1'
		}
	}
	//Le dernier.up
	res := string(resBs)
	if up == 1 {
    
		res = "1" + res
	}
	return res
}

Tests