8.22 数组和字符串[PT1] cc150

- to do

• finish array&string (1-6)/11 on cc150 p66

- note

• unicode vs. ASCII:
• ASCII defines 128 characters, which map to the numbers 0–127. Unicode defines (less than) 221 characters, which, similarly, map to numbers 0–221
• (though not all numbers are currently assigned, and some are reserved). Unicode is a superset of ASCII, and the numbers 0–128 have the same meaning in ASCII as they have in Unicode.
• Because Unicode characters don't generally fit into one 8-bit byte, there are numerous ways of storing Unicode characters in byte sequences, such as UTF-32 and UTF-8.

1.1] 实现算法，判断一个字符串无重复，不许额外数据结构

• pseudo
  • create unordered_map, loop and check if non-exist
  • after: if it's ASCII, better if just use bool char_set[256]
  • use bit instead of byte

practice using bit map for a-z, see p108 answer

1.2] 实现void reverse(char* str)，反转以null结尾的字符串

• pseudo
  • swap [ptrl] with [ptrr] until they meet

    string reverseString(string s) {
        int ptrl = 0, ptrr = s.size()-1;
        while (ptrl < ptrr) {
            swap(s[ptrl++], s[ptrr--]);
        }
        return s;
    }

• mistake: forgot ++/--
• after: note the null char

1.3] 给定两个字符串，是否重排其一能变成另一个

• sort and compare (space: O(n), time: O(nlogn) for mergeSort or c++ sort)
• hashTable, ( Space: O(n), time O(n) )

bool isPremutation(string a, string b) {
  if (a.size() != b.size()) return false;
  unordered_map<char, int> hits;
  for (char c : a) {
      ++hits[c];
  }
  for (char c : b) {
      if (hits.find(c) == hits.end() ||
          !hits[c]) return false;
      --hits[c];
  }
  return true;
}

1.4] 把字符串中空格替换成“%20”。假定串尾有足够空间并知道字符串真实长度

• fill from back

string replace(string a, int realLen) {
    for (int writei = a.size()-1, readi = realLen-1; readi>=0; --readi, --writei) {
        if (a[readi]==' ') {
            a[writei] = '0';
            a[--writei] = '2';
            a[--writei] = '%';
        } else {
            a[writei] = a[readi];
        }
    }
    return a;
}

• mistake: made the assumption that there's exact extra space at the end; to fix, return substr or precompute length of ret

1.5] 利用出现次数压缩字符串，如“aabcccaaa” => "2a1b3c3a"; 如果没有变短，返回原来

• limit return str, compare len w/ s.size()-1
• += is O(n^2), use append!

    string compress(string str) {
        if (str.size()<2) return str;
        string ret;
        int ct = 1; 
        char lastc = str[0];
        for (int i=1; i<str.size(); ++i) {
            if (str[i] != lastc) {
                ret += to_string(ct);
                ret += lastc;
                if (ret.size() >= str.size()) return str;
                ct = 1;
                lastc = str[i];
            } else {
                ++ct;
            }
        }
        ret.append(to_string(ct));
        ret.append(lastc);
        return ret.size() >= str.size()? str : ret;
    }