Share two methods of C++, 4ms and 8ms


  • 0
    E
    string addBinary(string a, string b) {//4ms
      int len_a = a.length(), len_b = b.length();
      if (len_a > len_b) {
        std::swap(len_a, len_b);
        std::swap(a, b);
      }
      if (len_a == 0) return b;
      int carry = 0, num = 0, ia, ib;
      for (int i = 1; i <= len_a; i++) {
        ia = a[len_a - i] - '0';
        ib = b[len_b - i] - '0';
        num = carry ^ ia ^ ib;//one 1 or three 1s
        carry = (carry & (ia || ib)) || ia & ib;
        b[len_b - i] = num ? '1' : '0';
      }
      for (int i = len_a + 1; i <= len_b && carry; i++) {
        ib = b[len_b - i] - '0';
        b[len_b - i] = carry ^ ib ? '1' : '0';
        carry = carry & ib;
      }
      if (carry) b = '1' + b;
      return b;
    }
    //use addition idea but not well performed
    string addBinary(string a, string b) {//8ms
      int len_a = a.length(), len_b = b.length();
      if (len_a > len_b) {
        std::swap(len_a, len_b);
        std::swap(a, b);
      }
      if (len_a == 0) return b;
      bool *G = new bool[len_b], *P = new bool[len_b], *C = new bool[len_b + 1];
      memset(G, 0, len_b * sizeof(bool));
      memset(P, 0, len_b * sizeof(bool));
      memset(C, 0, (len_b + 1) * sizeof(bool));
      int carry = 0, num = 0, ia, ib;
      for (int i = 0; i < len_a; i++) {
        ia = a[len_a - 1 - i] - '0', ib = b[len_b - 1 - i] - '0';
        G[i] = ia & ib;
        P[i] = ia ^ ib;
      }
      for (int i = len_a; i < len_b; i++) {
        P[i] = b[len_b - 1 - i] - '0' ^ 0;
      }
      if (P[0]) b[len_b - 1] = '1';
      else b[len_b - 1] = '0';
      C[0] = G[0];
      for (int i = 1; i < len_b; i++) {
        C[i] = G[i - 1] | (P[i - 1] & C[i - 1]);
        b[len_b - 1 - i] = P[i] ^ C[i] ? '1' : '0';
      }
      C[len_b] = G[len_b - 1] | (P[len_b - 1] & C[len_b - 1]);
      if (C[len_b]) b = '1' + b;
      delete[] G, P, C;
      return b;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.