面试常用算法复习

快速排序

void quicksort(vector<int> &v, int l, int r) {
  if (l >= r) {
    return;
  }
  int target = v[l];
  int start = l;
  int end = r;
  while (true) {
    while (l < r && v[r] >= target) {
      r--;
    }
    while (l < r && v[l] <= target) {
      l++;
    }
    if (l == r) {
      break;
    }
    swap(v[l], v[r]);
  }
  swap(v[start], v[l]);
  quicksort(v, start, l - 1);
  quicksort(v, l + 1, end);
}

快速幂

int fastPower(int x, int n) {
  int base = x;
  int ans = 1;
  while (n) {
    if (n & 1) {
      ans *= base;
    }
    base *= base;
    n >>= 1;
  }
  return ans;
}

int fastPowerWithMod(int x, int n, int mod) {
  int base = x;
  int ans = 1;
  while (n) {
    if (n & 1) {
      ans = ((ans % mod) * (base % mod)) % mod;
    }
    base = ((base % mod) * (base % mod)) % mod;
    n >>= 1;
  }
  return ans;
}

并查集

int find(vector<int> &fa, int x) {
  return (fa[x] == x) ? x : (fa[x] = find(fa, fa[x]));
}

void merge(vector<int> &fa, int x, int y) { 
    fa[find(fa, x)] = find(fa, y); 
}

堆

#define left_child(x) ((x + 1) * 2 - 1)
#define right_child(x) ((x + 1) * 2)
#define parent(x) ((x + 1) / 2 - 1)

void makeHeap(vector<int> &v) {
  int n = v.size();
  for (int i = 0; i < n; i++) {
    int leftIdx = left_child(i);
    int rightIdx = right_child(i);
    if (leftIdx >= n) {
      break;
    }
    if (leftIdx < n && v[leftIdx] > v[i]) {
      swap(v[leftIdx], v[i]);
    }
    if (rightIdx < n && v[rightIdx] > v[i]) {
      swap(v[rightIdx], v[i]);
    }
  }
}

void push(vector<int> &v, int ele) {
  v.push_back(ele);
  int idx = v.size() - 1;
  while (idx != 0) {
    int parentIdx = parent(idx);
    if (v[parentIdx] < v[idx]) {
      swap(v[parentIdx], v[idx]);
      idx = parentIdx;
    } else {
      break;
    }
  }
}

void siftDown(vector<int> &v) {
  int n = v.size();
  if (n == 0) {
    return;
  }
  int idx = 0;
  while (idx < n) {
    int leftIdx = left_child(idx);
    int rightIdx = right_child(idx);
    int maxIdx = -1;
    int maxV = v[idx];
    if (leftIdx < n && v[leftIdx] > maxV) {
      maxV = v[leftIdx];
      maxIdx = leftIdx;
    }
    if (rightIdx < n && v[rightIdx] > maxV) {
      maxV = v[rightIdx];
      maxIdx = rightIdx;
    }

    if (maxIdx == -1) {
      break;
    }
    swap(v[idx], v[maxIdx]);
    idx = maxIdx;
  }
}

int pop(vector<int> &v) {
  int n = v.size();
  if (n == 0) {
    return 0;
  }

  int ret = v[0];
  swap(v[n - 1], v[0]);
  v.pop_back();
  siftDown(v);
  return ret;
}

void heapSort(vector<int> &v) {
  vector<int> h(v);
  makeHeap(h);
  int n = v.size();
  for (int i = 0; i < n; i++) {
    v[i] = pop(h);
  }
}