Array & Numbers 4 - Others

int lengthOfLongestSubstring(string s) {
  //用bool数组记录是否出现过，因为一出现重复就需要重新计算i之前的数组，所以复杂度略高
  bool hash[256] = {false};  // 统一初始化C数组
  int maxLen = 0;
  int i = 0, j = 0;  // 一前，一后指针
  for (; j < s.size(); j++) {
    if (hash[s[j]]) {
      maxLen = max(maxLen, j - i);
      while (s[i] != s[j]) {  // efabcabc 第1个a之前清除标志
        hash[s[i]] = false;
        i++;
      }
      i++;
    }
    //不管如何，都需要记录下标；或放到else里，上一种情况，记录了其实
    hash[s[j]] = true;
  }
  return max(maxLen, j-i); //必须最后再比较一下，防止最后一次的遗漏!
}

int lengthOfLongestSubstring(string &s) {
    // write your code here
    if(s.empty()) return 0;  // 1. 错误处理
    std::vector<int> index(256, -1);  // 用int存上一次出现位置
    int longest = 1;  // 0已经返回了，那最小就是1
    int lastindex = 0;
    for(int i = 0; i < s.size(); i++) {
        if(index[s[i]] >= lastindex) {
            // 代表有了，那么就要重新计算了，记录上次的长度
            longest = max(longest, i - lastindex);
            lastindex = index[s[i]] + 1;  // 新的开始点index[s[i]], 不是last index!!
        }
        index[s[i]] = i; // 不管是否命中，都需要记录最新的下标
    }
    return max(longest, (int)(s.size() - lastindex));  // 必须最后再比较一下，防止最后一次的遗漏!如bba
}

int maxArea(vector<int> &height) {
  //两个指针，扫。注意，一前一后扫
  int start = 0, end = height.size() - 1;
  int maxW = 0;
  while (start < end) {
    if (height[end] >= height[start]) {  //以start起始的，已经找到了
      maxW = max(maxW, height[start] * (end - start));
      start++;
      end = height.size() - 1;  // end归到最后，重新算
    } else {
      maxW = max(maxW, height[end] * (end - start));
      end--;
    }
  }
  return maxW;
}

int maxArea(vector<int> &height) {
  int start = 0, end = height.size() - 1;
  int maxW = 0;
  while (start < end) {
    maxW = max(maxW, min(height[start], height[end]) * (end - start));
    if (height[end] >= height[start]) {  //以start起始的，已经找到了
      start++;  // end = height.size()-1; // end不需要归位，end之后的东西都是短于前一个start的，没必要计算了
    } else {
      end--;
    }
  }
  return maxW;
}

int trap(int A[], int n) {
  // 每根柱子分割开来，找到左、右边最高的，就能知道它上部能放多少水
  vector<int> left(n, 0);
  vector<int> right(n, 0);
  int high = 0, res = 0;
  for (int i = 1; i < n; i++) {  // 扫左边的
    high = high > A[i - 1] ? high : A[i - 1];
    left[i] = high;
  }
  high = 0;
  for (int i = n - 2; i >= 0; i--) {  // 扫右边的 + 顺便计算
    high = high > A[i + 1] ? high : A[i + 1];
    right[i] = high;
    int temp = min(left[i], right[i]) - A[i];
    if(temp > 0)    res += temp;    // 注意，不能加负的!
  }
  return res;
}

int trap(int A[], int n) {
  //扫描一遍，找到最高的柱子，这个柱子将数组分为两半；再分别处理左右2边
  int maxIndex = 0;
  for (int i = 0; i < n; i++)
    if (A[i] > A[maxIndex]) maxIndex = i;
  int res = 0;
  for (int i = 0, peak = 0; i < maxIndex; i++) {  // peak是左边最高点
    if (peak > A[i])   res += peak - A[i];
    else    peak = A[i];  //左边最高点，没自己高，不可能存水
  }
  for (int i = n - 1, peak = 0; i > maxIndex; i--) {  // peak是左边最高点
    if(peak > A[i])    res += peak- A[i];
    else    peak = A[i];
  }
  return res;
}

vector<int> findSubstring(string S, vector<string> &L) {
  //主要考察数据结构的使用
  int wLen = L.front().size();  //用front!
  int tLen = wLen * L.size();
  vector<int> res;
  if (tLen > S.size()) return res;

  unordered_map<string, int> times;
  for (int i = 0; i < L.size(); i++) {
    times[L[i]]++;  // int不是bool，可能有重复的
  }
  // 注意这种找字符串的题，一定优化到不够长!注意+1
  for (int i = 0; i < S.size() - tLen + 1; i++) {
    map<string, int> has_found;  //初始化全是0
    int j = 0;
    for (; j < L.size(); j++) {  //依次扫描L中的每一个单词，但不一定按L中的顺序!
      string t = S.substr(i + j * wLen, wLen);  //每次跳过S中的一个单词
      if (times.find(t) == times.end())  //没找到时, 这2个时要跳出
        break;
      ++has_found[t];
      if (has_found[t] > times[t])  //数量不对时
        break;
    }
    if(j == L.size()) {
      res.push_back(i);
    }
  }
  return res;
}

bool isPalindrome(string s) {
  //正常逻辑处理，先过滤字符，后判断
  string ss;
  for (int i = 0; i < s.size(); i++) {
    if ((s[i] >= '0' && s[i] <= '9') || (s[i] >= 'a' && s[i] <= 'z') ||
        (s[i] >= 'A' && s[i] <= 'Z'))
      // ss[ssindex++]错!应该用+=动态增长
      ss += (s[i] >= 'A' && s[i] <= 'Z') ? (s[i] + 'a' - 'A') : s[i];
  }
  int i = 0, j = ss.size() - 1;
  while (i < j) {            //不用判断==的情况
    if (ss[i++] != ss[j--])  //比下边调用i++; j--;更简洁
      return false;
  }
  return true;  // we define empty string as valid palindrome
}

int reverse(int x) {
  //时间复杂度 O(lgn)，空间复杂度 O(1),短小代码!
  int res = 0;
  for (; x; x /= 10) {        //一般for循环，都比while简洁
    res = 10 * res + x % 10;  //若x%10开头为0，结果是对的
  }
  return res; //负数，也是对的，不需要单独处理.  这里只是要提一下，溢出怎么办?
}

int reverse(int x) {
  //考虑溢出
  long long res = 0;             //这样的话，不会溢出
  for (; x; x /= 10) {        //一般for循环，都比while简洁
    res = 10 * res + x % 10;  //若x%10开头为0，结果是对的
  }
  if (res < INT_MIN) return INT_MIN;
  if (res > INT_MAX) return INT_MAX;
  return (int)res;
}

bool isPalindrome(int x) {
  //参考reverse的方法，直接一个一个比呗
  if (x < 0) return false;  //若负数，也算Palindrome的话==>问面试官
  int base = 1;
  while (x / base >= 10)  // find base，注意有==!
    base *= 10;
  //一次比较首尾位2位，所以除以100；另，x是个位数就跳出是true(错，10021)
  for (; x > 0; base /= 100) {
    if (x % 10 != x / base) return false;
    x = x % base / 10;      //x -= x / base * base;
  }
  return true;
}

string minWindow(string S, string T) {
  //用hash记录T，然后扫S，2个指针典型的题
  int lenT = T.size();
  string res = "";          //返回的是""
  int needFind[256] = {0};  //有可能出现多次，所以用int
  int hasFound[256] = {0};
  for (int i = 0; i < lenT; i++) needFind[T[i]]++;

  int count = 0, minLen = INT_MAX;
  for (int left = 0, right = 0; right < S.size(); right++) {
    if (needFind[S[right]] == 0)  //只关心相关的字母
      continue;
    hasFound[S[right]]++;  //每次碰到都加，但是count不用加
    if (hasFound[S[right]] <= needFind[S[right]])  //注意，有等于！
      count++;
    if (count == lenT) {  //说明找全乎了，可以收缩left了
      while (left <= right &&
             (!needFind[S[left]] || hasFound[S[left]] > needFind[S[left]])) {
        if (hasFound[S[left]] > needFind[S[left]]) hasFound[S[left]]--;
        left++;
      }
      if (right - left + 1 < minLen) {
        minLen = right-left+1;
        res = S.substr(left, minLen);
      }
    }
  }
  return res;
}

int firstMissingPositive(int A[], int n) {
  //用标记数组bool，出现的true，第一个没出现的就是答案，但是空间O(n)，不靠谱!
  //有个方法，各就各位:每当 A[i]!= i+1 的时候，将 A[i] 与 A[A[i]-1]
  //交换，直到无法交换为止
  for (int i = 0; i < n; i++) {  //先进行 各就各位 操作
    while (A[i] != i + 1 && A[i] > 0 && A[i] <= n &&
           A[i] != A[A[i] - 1]) {  // 0<A[i]<=n, 且防止无休止swap
      swap(A[i], A[A[i] - 1]);
    }
  }
  for(int i = 0; i < n; i++) {    //找结果
    if(A[i] != i+1)
      return i+1;
  }
  return n+1;
}

int findMissing(vector<int> &nums) {
  if (nums.size() == 0 || nums[0] != 0) return 0;  // 缺0单独考虑
  int start = 0, end = nums.size() - 1;
  while (start + 1 < end) {
    int mid = start + (end - start) / 2;
    if (nums[mid] == mid) {
      start = mid;
    } else {  // 缺的在前边
      end = mid;
    }
  }
  if (nums[end] == end) return end + 1;  // 如果end没错位，那肯定是end+1
  return start + 1;
}

int findMissing(vector<int> &nums) {
  int i = 0;
  for (; i < nums.size(); i++) {
    while (nums[i] != i && nums[i] < nums.size()) swap(nums[i], nums[nums[i]]);
  }  // 不存在重复的数字，所以不用判断nums[i]!=nums[nums[i]]
  for (int j = 0; j < nums.size(); j++)
    if (nums[j] != j) return j;
  return nums.size();
}

// 递归方法1
double pow(double x, int n) {
  if (n < 0)
    return 1.0 / power(x, -n);
  else
    return power(x, n);
}
double power(double x, int n) {
  if (n == 0) return 1;
  double v = power(x, n / 2);
  if (n % 2 == 0)
    return v * v;
  else
    return v * v * x;
}
// 递归方法2
double myPow(double x, long long n) {
  if (n == 0) return 1;
  if (n < 0) {
    x = 1.0 / x;
    n = -n;
  }
  double v = myPow(x * x, n / 2);
  if (n % 2 == 0)
    return v;
  else
    return v * x;
}

double myPow(double x, int n) {
  double ans = 1;
  unsigned long long p;
  if (n < 0) {
    p = -n;
    x = 1 / x;
  } else {
    p = n;
  }
  while (p) {
    if (p & 1) ans *= x;
    x *= x;
    p >>= 1;
  }
  return ans;
}

// 归并的思路, 边排序，边统计
vector<int> tmp;
long long reversePairs(vector<int> &A) {
  if (A.size() <= 1) return 0;
  tmp.resize(A.size());  // 这样提前分配好，比在子函数里效率高!
  return mergeSort(A, 0, A.size() - 1);
}
long long mergeSort(vector<int> &A, int beg, int end) {
  if (beg >= end) return 0;
  int mid = beg + ((end - beg) >> 1);
  // 必须是mid+1,end(否则，2个元素有死循环现象)
  long long res = mergeSort(A, beg, mid) + mergeSort(A, mid + 1, end);
  // merge
  int left = beg, right = mid + 1;
  int index = beg;  // 这里注意，下标和A的对应关系!!
  while (left <= mid && right <= end) {
    if (A[left] <= A[right]) {
      tmp[index++] = A[left++];
    } else {  //逆序了
      tmp[index++] = A[right++];
      res += mid - left + 1;  // 注意 +1
    }
  }
  while(left <= mid) {
    tmp[index++] = A[left++];
  }
  while(right <= end) {
    tmp[index++] = A[right++];
  }
  for (int i = beg;i <= end; ++i)
    A[i] = tmp[i];
  return res;
}

// 判断素数最简单的方法，复杂度O(n^1.5)
bool isPrime(int num) {
   if (num <= 1) return false;
   // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
   // to avoid repeatedly calling an expensive function sqrt().
   for (int i = 2; i * i <= num; i++) {
      if (num % i == 0) return false;
   }
   return true;
}
// [筛选法](https://leetcode.com/problems/count-primes/hints/)
// O(nloglog n)
int countPrimes(int num) {  //统计<=num的素数的数目
  if (num <= 1) return false;
  vector<bool> tags(num + 1, true);     // 初始化为都是素数
  for (int i = 2; i * i <= num; i++) {  // 优化：i * i <= num
    if (!tags[i]) continue;
    for (int j = i * i; j <= num; j += i) {  // 优化：从i*i开始,递加i,不是从2*i开始
      tags[j] = false;
    }
  }
  int count = 0;
  for (int i=2; i<=num; i++) {
    if (tags[i]) count++;
  }
  return count;
}
int firstMissingPrime(vector<int> nums) {
  if(nums.size()==0) return 2; // 边界条件
  int num = nums[nums.size() - 1] * 2;  // n和2n之间，肯定有素数
  vector<bool> tags(num, true); 
  for (int i = 2; i * i <= num; i++) {  // 从2开始乘倍数，筛选
    if (!tags[i]) continue;
    for (int j = i * i; j <= num; j += i) {  // 从i*i开始,递加i
      tags[j] = false;
    }
  }
  int count = 0;
  for (int i=2; i<=num; i++) {
    if (tags[i]) {
      if(i != nums[count++]) return i;
    }
  }
  return -1;
}

void QuickSort(int* array,int left,int right) {
  if(left >= right)  // 表示已经完成一个组
    return;
  int index = PartSort(array,left,right);  // 枢轴的位置
  QuickSort(array,left,index - 1);
  QuickSort(array,index + 1,right);
}

// 常见方法：左右指针法,左边一直找大于key的，右边一直找小于等于key的，之后交换
int PartSort(int* array,int left,int right) {
  int key = array[right];  // 比如选最后一个为 轴
  int ll = left, rr = right-1;  // Note: right--
  while(ll < rr) {
    while(ll < rr && array[ll] <= key) ++ll;
    while(ll < rr && array[rr] > key) --rr;
    swap(array, ll, rr);
  }
  swap(array, ll, right);
  return left;
}
// 挖坑法：一直更新坑的位置，往坑里放需要调换的值
int PartSort(int* array,int left,int right) {
  int key = array[right];  // 比如选最后一个为 轴
  int ll = left, rr = right;  // Note: right! 不是right-1
  while(ll < rr) {
    while(ll < rr && array[ll] <= key) ++ll;
    array[rr] = array[ll];
    while(ll < rr && array[rr] > key) --rr;
    array[ll] = array[rr];
  }
  array[rr] = key;
  return rr;
}