Forem: さるでもわかるアルゴリズム

ビット演算 - Bit Manipulation

さるでもわかるアルゴリズム — Mon, 31 Aug 2020 00:44:24 +0000

Basic Calculator - LeetCode Problem

さるでもわかるアルゴリズム — Mon, 10 Aug 2020 06:03:12 +0000

問題

https://leetcode.com/problems/basic-calculator-iii/

コード

class Solution {
 public:
  int calculate(string s) {
    long l1 = 0, o1 = 1;  // level one: +, -
    long l2 = 1, o2 = 1;  // level two: *, /
    bool s2 = false;      // weather l2 is set or not
    const int n = s.size();
    for (int i = 0; i < s.size(); i++) {
      auto c = s[i];
      if (isdigit(c)) {  // parse digits
        int last = i + 1;
        for (; last < n; last++) {
          if (!isdigit(s[last])) {
            break;
          }
        }
        long num = stol(s.substr(i, last - i));
        s2 = true;
        i = last - 1;
        l2 = (o2 == 1 ? l2 * num : l2 / num);
      } else if (isalpha(c)) {
        // TODO: parse variable
      } else if (c == '(') {
        int last = i + 1;
        int count = 1;  // parenthesis count
        for (; last < n; last++) {
          if (s[last] == '(') {
            count++;
          } else if (s[last] == ')') {
            count--;
          }
          if (count == 0) {
            break;
          }
        }
        string subExpr = s.substr(i + 1, last - i + 1 - 2);
        int num = calculate(subExpr);
        i = last;
        s2 = true;
        l2 = (o2 == 1 ? l2 * num : l2 / num);
      } else if (c == '*' || c == '/') {
        o2 = (c == '*' ? 1 : -1);
      } else if (c == '+' || c == '-') {
        if (s2) {
          l1 = l1 + o1 * l2;
        }
        o1 = (c == '+' ? 1 : -1);
        s2 = true;
        l2 = o2 = 1;
      } else {  // space
        continue;
      }
    }
    return l1 + o1 * l2;
  }
};

参考: https://leetcode.com/problems/basic-calculator-iii/discuss/113592/Development-of-a-generic-solution-for-the-series-of-the-calculator-problems

K Sum - Two Pointers

さるでもわかるアルゴリズム — Sun, 26 Jul 2020 11:17:51 +0000

Two Sum

https://leetcode.com/problems/two-sum/

Greedy

class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    const int n = nums.size();
    for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
        if (nums[i] + nums[j] == target) {
          return vector<int>{i, j};
        }
      }
    }
    throw "no combination";
  }
};

Hash Table

class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    const int n = nums.size();
    unordered_map<int, int> m;
    for (int i = 0; i < n; i++) {
      const int complement = target - nums[i];
      if (m.find(complement) != m.end()) {
        return vector<int>{m[complement], i};
      }
      m[nums[i]] = i;
    }
    throw "no combination";
  }
};

Two Sum II - Input array is sorted

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

class Solution {
 public:
  vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0;
    int r = numbers.size() - 1;
    while (l < r) {
      const int sum = numbers[l] + numbers[r];
      if (sum == target) {
        return vector<int>{l + 1, r + 1};
      } else if (sum < target) {
        l++;
      } else {
        r--;
      }
    }
    throw "no combination";
  }
};

3Sum

https://leetcode.com/problems/3sum/

class Solution {
  int twoSumSmaller(vector<int> &nums, int start, int target) {
    int count = 0;
    int l = start;
    int r = nums.size() - 1;
    while (l < r) {
      int sum = nums[l] + nums[r];
      if (sum >= target) {
        r--;
        continue;
      }
      count += r - l;
      l++;
    }
    return count;
  }

 public:
  int threeSumSmaller(vector<int> &nums, int target) {
    int count = 0;
    sort(nums.begin(), nums.end());
    const int n = nums.size();
    for (int i = 0; i < n; i++) {
      count += twoSumSmaller(nums, i + 1, target - nums[i]);
    }
    return count;
  }
};

4Sum

https://leetcode.com/problems/4sum/

class Solution {
  vector<vector<int>> kSum(vector<int> &nums, int k, int start, int target) {
    const int n = nums.size();
    vector<vector<int>> results;
    if (k == 2) {
      // two sum
      int l = start;
      int r = n - 1;
      while (l < r) {
        const int sum = nums[l] + nums[r];
        if (sum < target || (start < l && nums[l] == nums[l - 1])) {
          l++;
        } else if (target < sum || (r < n - 1 && nums[r] == nums[r + 1])) {
          r--;
        } else {
          results.push_back(vector<int>{nums[l], nums[r]});
          l++;
          r--;
        }
      }
      return results;
    }
    for (int i = start; i <= n - k; i++) {
      if (i > start && nums[i - 1] == nums[i]) {
        continue;
      }
      for (auto result : kSum(nums, k - 1, i + 1, target - nums[i])) {
        result.insert(result.begin(), nums[i]);
        results.push_back(result);
      }
    }

    return results;
  }

 public:
  vector<vector<int>> fourSum(vector<int> &nums, int target) {
    sort(nums.begin(), nums.end());
    auto results = kSum(nums, 4, 0, target);
    return results;
  }
};

エラトステネスの篩 (Sieve of Eratosthenes)

さるでもわかるアルゴリズム — Mon, 15 Jun 2020 07:23:38 +0000

code

最近JavaScriptでPriorityQueueとかなくて悲しいことが多いのでさけがちです。今回はC++にしました。

class Solution {
 public:
  int countPrimes(int n) {
    int count = 0;
    if (n < 2) {
      return count;
    }
    vector<bool> visit(n);
    for (int i = 2; i < n; i++) {
      if (visit[i]) {
        continue;
      }
      count++;
      int v = i;
      while (v <= n) {
        visit[v] = true;
        v += i;
      }
    }
    return count;
  }
};

問題

https://leetcode.com/problems/count-primes/submissions/

ベルマンフォード法 (Bellman-Ford algorithm)

さるでもわかるアルゴリズム — Sun, 31 May 2020 01:04:11 +0000

コード

let v = 0, e = 0, r = 0
let path = []

process.stdin.resume();
process.stdin.setEncoding("utf-8");

process.stdin.on("data", function (input) {
  let num = 0
  const lines = input.split("\n")
  for (const line of lines) {
    if (line === "") {
      break
    }
    const m = line.split(" ").map(v => parseInt(v))
    if (num === 0) {
      v = m[0]
      e = m[1]
      r = m[2]
    } else {
      path.push(m)
    }
    num++
  }
});

process.stdin.on("end", function () {
  // console.log(v, e, r)
  // console.log(path)
  bellmanFord(v, r, path)
});

/**
 * @param {number} v 
 * @param {number} r 
 * @param {number[][]} path 
 */
function bellmanFord(v, r, path) {
  const inf = Number.MAX_SAFE_INTEGER
  const dist = Array(v).fill(inf)
  dist[r] = 0
  for (let i = 0; i < v; i++) {
    let change = false
    for (const [s, t, d] of path) {
      if (dist[s] === inf) {
        continue
      }
      if (dist[s] + d < dist[t]) {
        if (i + 1 === v) {
          console.log('NEGATIVE CYCLE')
          return
        }
        dist[t] = dist[s] + d
        change = true
      } else {
        continue
      }
    }
    if (!change) {
      break
    }
  }
  for (const d of dist) {
    console.log(d === inf ? 'INF' : d)
  }
}

問題

https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_1_B

プリム法 (Prim's Algorithm)

さるでもわかるアルゴリズム — Fri, 29 May 2020 12:52:49 +0000

コード

let input = require('fs').readFileSync('/dev/stdin', 'utf8');
const lines = input.trim().split("\n")
let v, e, path = []

for (let i = 0; i < lines.length; i++) {
  if (i === 0) {
    [v, e] = lines[i].split(" ").map(v => parseInt(v))
    path = [...Array(v)].map(() => [])
    continue
  }
  const [s, t, w] = lines[i].split(" ").map(v => parseInt(v))
  path[s].push([t, w])
  path[t].push([s, w])
}

const parent = (i) => Math.floor((i - 1) / 2)
const leftChild = (i) => 2 * i + 1
const rightChild = (i) => 2 * i + 2

const MinHeap = function (n) {
  this.a = [...Array(n).keys()].map(v => [v, Number.MAX_SAFE_INTEGER]) // [vertex, weight]
  this.pos = [...Array(n).keys()].map(v => v)
  this.size = n
}

MinHeap.prototype.extractMin = function () {
  const [v, w] = this.a[0]
  this.swap(0, this.size - 1)
  this.size--
  this.popDown(0)
  return [v, w]
}

MinHeap.prototype.swap = function (i, j) {
  const vi = this.a[i][0], vj = this.a[j][0];
  [this.a[i], this.a[j]] = [this.a[j], this.a[i]];
  [this.pos[vi], this.pos[vj]] = [this.pos[vj], this.pos[vi]]
}

MinHeap.prototype.decreaseKey = function (v, val) {
  const i = this.pos[v]
  this.a[i][1] = val
  this.popUp(i)
}

// vertexが含まれているか
MinHeap.prototype.contains = function (v) {
  return this.pos[v] < this.size
}

// 適切な位置まで上げる
MinHeap.prototype.popUp = function (i) {
  let pi = parent(i)
  while (i > 0 && this.a[i][1] < this.a[pi][1]) { // 親が子より大きかったら交換
    this.swap(i, pi)
    i = pi
    pi = parent(i)
  }
}

// 値を取得
MinHeap.prototype.val = function (v) {
  return this.a[this.pos[v]][1]
}

// 適切な位置まで下げる
MinHeap.prototype.popDown = function (i) {
  const val = this.a[i][1]
  let candidate = null // 子供のほうが小さかったら交換
  const ri = rightChild(i)
  const li = leftChild(i)
  if (ri < this.size) { // right child exist
    if (this.a[ri][1] < val) {
      candidate = ri
    }
  }
  if (li < this.size) {
    if (candidate == null) {
      if (this.a[li][1] < val) {
        candidate = li
      }
    } else {
      if (this.a[li][1] < this.a[ri][1]) {
        candidate = li
      }
    }
  }
  if (candidate != null) {
    this.swap(i, candidate)
    this.popDown(candidate)
  }
}

function prim(n, path) {
  const minHeap = new MinHeap(n)
  minHeap.decreaseKey(0, 0)

  let total = 0
  while (minHeap.size > 0) {
    const [v, w] = minHeap.extractMin()
    // check neighbors
    for (const [next, nextWeight] of path[v]) {
      if (!minHeap.contains(next)) {
        continue
      }
      const currentWeight = minHeap.val(next)
      if (nextWeight < currentWeight) {
        minHeap.decreaseKey(next, nextWeight)
      }
    }
    total += w
  }
  console.log(total)
}

// console.log(v, e)
// console.log(path)
prim(v, path)

問題

https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A

重み付きUnion-Find木(Weighted Union-Find Tree)

さるでもわかるアルゴリズム — Thu, 28 May 2020 12:27:43 +0000

コード

const Node = function (val) {
  this.val = val
  this.parent = this
  this.rank = 1
  this.weight = 0 // 親に対してのweight
}

const WeightedDisjointSet = function () {
  this.m = []
}

WeightedDisjointSet.prototype.add = function (val) {
  this.m[val] = new Node(val)
}

WeightedDisjointSet.prototype.merge = function (val1, val2, weight) {
  const p1 = this.find(val1)
  const p2 = this.find(val2)
  const w1 = this.weight(val1)
  const w2 = this.weight(val2)
  if (p1 === p2) {
    return
  }
  if (p2.rank <= p1.rank) {
    if (p1.rank == p2.rank) {
      p1.rank++
    }
    p2.parent = p1
    p2.weight = weight + w1 - w2
  } else {
    p1.parent = p2
    p1.weight = -weight - w1 + w2
  }
}

WeightedDisjointSet.prototype.find = function (val) {
  let cur = this.m[val]
  if (cur.parent != cur) {
    const root = this.find(cur.parent.val)
    cur.weight += cur.parent.weight
    cur.parent = root
  }
  return cur.parent
}

WeightedDisjointSet.prototype.diff = function (val1, val2) {
  const p1 = this.find(val1)
  const p2 = this.find(val2)
  if (p1 != p2) {
    return null
  }
  return this.weight(val2) - this.weight(val1)
}

WeightedDisjointSet.prototype.weight = function (val) {
  let weight = 0
  let cur = this.m[val]
  while (cur.parent != cur) {
    weight += cur.weight
    cur = cur.parent
  }
  return weight
}

let input = require('fs').readFileSync('/dev/stdin', 'utf8');
const lines = input.trim().split("\n")
let n, q, d

for (let i = 0; i < lines.length; i++) {
  if (i === 0) {
    [n, q] = lines[i].split(" ")
    d = new WeightedDisjointSet()
    for (let i = 0; i < n; i++) {
      d.add(i)
    }
  } else {
    const [com, x, y, w] = lines[i].split(" ").map(v => parseInt(v))
    switch (com) {
      case 0:
        d.merge(x, y, w)
        break;
      case 1:
        const diff = d.diff(x, y)
        console.log(diff == null ? '?' : diff)
        break;
      default:
        throw Error('invalid com')
    }
  }
}

問題

https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_B

クラスカル法 (Kruskal's Algorithm)

さるでもわかるアルゴリズム — Wed, 27 May 2020 08:15:46 +0000

コード

let input = require('fs').readFileSync('/dev/stdin', 'utf8');
const lines = input.trim().split("\n")
let v, e, path = []

for (let i = 0; i < lines.length; i++) {
  if (i === 0) {
    [v, e] = lines[i].split(" ")
    continue
  }
  path.push(lines[i].split(" ").map(v => parseInt(v)))
}

const DisjointSet = function () {
  this.m = new Map()
}

DisjointSet.prototype.add = function (val) {
  this.m.set(val, new Node(val))
}

DisjointSet.prototype.union = function (val1, val2) {
  const p1 = this.find(this.m.get(val1).val)
  const p2 = this.find(this.m.get(val2).val)
  if (p1.rank === p2.rank) {
    p2.rank++
    p1.parent = p2
  } else if (p1.rank < p2.rank) {
    p1.parent = p2
  } else {
    p2.parent = p1
  }
}

DisjointSet.prototype.find = function (val) {
  let cur = this.m.get(val)
  if (cur.parent != cur) {
    cur.parent = this.find(cur.parent.val)
  }
  return cur.parent
}

const Node = function (val) {
  this.val = val
  this.parent = this
  this.rank = 1
}

function kruskal(v, path) {
  path.sort((a, b) => a[2] - b[2])

  // initialize nodes
  const ds = new DisjointSet()
  for (let i = 0; i < v; i++) {
    ds.add(i)
  }
  let total = 0
  for (const [s, t, w] of path) {
    if (ds.find(s) === ds.find(t)) {
      continue
    }
    ds.union(s, t)
    total += w
  }
  console.log(total)
}

// console.log(v, e)
// console.log(path)
kruskal(v, path)

問題

https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_1_

素集合データ構造 (Disjoin-set または Union-Find)

さるでもわかるアルゴリズム — Tue, 26 May 2020 07:59:32 +0000

コード

const Node = function (val) {
  this.val = val
  this.parent = this
  this.rank = 1
}

const DisjointSet = function () {
  this.m = []
}

DisjointSet.prototype.add = function (val) {
  this.m[val] = new Node(val)
}

DisjointSet.prototype.union = function (val1, val2) {
  const p1 = this.find(this.m[val1].val)
  const p2 = this.find(this.m[val2].val)
  if (p1 === p2) {
    return
  }
  if (p1.rank === p2.rank) {
    p2.rank++
    p1.parent = p2
  } else if (p1.rank < p2.rank) {
    p1.parent = p2
  } else {
    p2.parent = p1
  }
}

DisjointSet.prototype.find = function (val) {
  let cur = this.m[val]
  if (cur.parent != cur) {
    cur.parent = this.find(cur.parent.val)
  }
  return cur.parent
}

let input = require('fs').readFileSync('/dev/stdin', 'utf8');
const lines = input.trim().split("\n")
let n, q, d

for (let i = 0; i < lines.length; i++) {
  if (i === 0) {
    [n, q] = lines[i].split(" ")
    d = new DisjointSet()
    for (let i = 0; i < n; i++) {
      d.add(i)
    }
  } else {
    const [com, x, y] = lines[i].split(" ").map(v => parseInt(v))
    switch (com) {
      case 0:
        d.union(x, y)
        break;
      case 1:
        console.log(d.find(x) === d.find(y) ? 1 : 0)
        break;
      default:
        throw Error('invalid com')
    }
  }
}

問題

https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_A

ダイクストラ法 (Dijkstra's Algorithm)

さるでもわかるアルゴリズム — Mon, 25 May 2020 06:09:22 +0000

let input = require("fs").readFileSync("/dev/stdin", "utf8");
const lines = input.trim().split("\n");

let v, e, r, path = []

for (let i = 0; i < lines.length; i++) {
  if (i === 0) {
    [v, e, r] = lines[i].split(" ").map((v) => parseInt(v));
    path = [...Array(v)].map(() => new Set());
    continue;
  }
  const [s, t, d] = lines[i].split(" ").map((v) => parseInt(v));
  path[s].add([t, d])
}

const parent = (i) => Math.floor((i - 1) / 2)
const leftChild = (i) => 2 * i + 1
const rightChild = (i) => 2 * i + 2

const MinHeap = function (n) {
  this.a = [...Array(n).keys()].map(v => [v, Number.MAX_SAFE_INTEGER]) // [vertex, weight]
  this.pos = [...Array(n).keys()].map(v => v)
  this.size = n
}

MinHeap.prototype.extractMin = function () {
  const [v, w] = this.a[0]
  this.swap(0, this.size - 1)
  this.size--
  this.popDown(0)
  return [v, w]
}

MinHeap.prototype.swap = function (i, j) {
  const vi = this.a[i][0], vj = this.a[j][0];
  [this.a[i], this.a[j]] = [this.a[j], this.a[i]];
  [this.pos[vi], this.pos[vj]] = [this.pos[vj], this.pos[vi]]
}

MinHeap.prototype.decreaseKey = function (v, val) {
  const i = this.pos[v]
  this.a[i][1] = val
  this.popUp(i)
}

// vertexが含まれているか
MinHeap.prototype.contains = function (v) {
  return this.pos[v] < this.size
}

// 適切な位置まで上げる
MinHeap.prototype.popUp = function (i) {
  let pi = parent(i)
  while (i > 0 && this.a[i][1] < this.a[pi][1]) { // 親が子より大きかったら交換
    this.swap(i, pi)
    i = pi
    pi = parent(i)
  }
}

// 値を取得
MinHeap.prototype.val = function (v) {
  return this.a[this.pos[v]][1]
}

// 適切な位置まで下げる
MinHeap.prototype.popDown = function (i) {
  const val = this.a[i][1]
  let candidate = null // 子供のほうが小さかったら交換
  const ri = rightChild(i)
  const li = leftChild(i)
  if (ri < this.size) { // right child exist
    if (this.a[ri][1] < val) {
      candidate = ri
    }
  }
  if (li < this.size) {
    if (candidate == null) {
      if (this.a[li][1] < val) {
        candidate = li
      }
    } else {
      if (this.a[li][1] < this.a[ri][1]) {
        candidate = li
      }
    }
  }
  if (candidate != null) {
    this.swap(i, candidate)
    this.popDown(candidate)
  }
}


function dijkstra(n, r, path) {
  const minHeap = new MinHeap(n)
  const dist = Array(n).fill(null)
  const parent = Array(n).fill(null)

  // initialization
  minHeap.decreaseKey(r, 0)
  dist[r] = 0

  while (minHeap.size > 0) {
    const [u, d] = minHeap.extractMin()
    for (const [v, w] of path[u]) {
      if (!minHeap.contains(v)) {
        continue
      }
      if (d + w < minHeap.val(v)) {
        parent[v] = u
        dist[v] = d + w
        minHeap.decreaseKey(v, d + w)
      }
    }
  }

  for (const d of dist) {
    if (d == null) {
      console.log('INF')
    } else {
      console.log(d)
    }
  }
}


// console.log(v, e, r)
// console.log(path)
dijkstra(v, r, path)

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=ja

二分ヒープの解説

さるでもわかるアルゴリズム — Sun, 24 May 2020 12:46:38 +0000

参考のためDijkstraの際に使った最小ヒープのコード抜粋を下に貼ります。

const MinHeap = function (n) {
  this.a = [...Array(n).keys()].map(v => [v, Number.MAX_SAFE_INTEGER]) // [vertex, weight]
  this.pos = [...Array(n).keys()].map(v => v)
  this.size = n
}

MinHeap.prototype.extractMin = function () {
  const [v, w] = this.a[0]
  this.swap(0, this.size - 1)
  this.size--
  this.popDown(0)
  return [v, w]
}

MinHeap.prototype.swap = function (i, j) {
  const vi = this.a[i][0], vj = this.a[j][0];
  [this.a[i], this.a[j]] = [this.a[j], this.a[i]];
  [this.pos[vi], this.pos[vj]] = [this.pos[vj], this.pos[vi]]
}

MinHeap.prototype.decreaseKey = function (v, val) {
  const i = this.pos[v]
  this.a[i][1] = val
  this.popUp(i)
}

// vertexが含まれているか
MinHeap.prototype.contains = function (v) {
  return this.pos[v] < this.size
}

// 適切な位置まで上げる
MinHeap.prototype.popUp = function (i) {
  let pi = parent(i)
  while (i > 0 && this.a[i][1] < this.a[pi][1]) { // 親が子より大きかったら交換
    this.swap(i, pi)
    i = pi
    pi = parent(i)
  }
}

// 値を取得
MinHeap.prototype.val = function (v) {
  return this.a[this.pos[v]][1]
}

// 適切な位置まで下げる
MinHeap.prototype.popDown = function (i) {
  const val = this.a[i][1]
  let candidate = null // 子供のほうが小さかったら交換
  const ri = rightChild(i)
  const li = leftChild(i)
  if (ri < this.size) { // right child exist
    if (this.a[ri][1] < val) {
      candidate = ri
    }
  }
  if (li < this.size) {
    if (candidate == null) {
      if (this.a[li][1] < val) {
        candidate = li
      }
    } else {
      if (this.a[li][1] < this.a[ri][1]) {
        candidate = li
      }
    }
  }
  if (candidate != null) {
    this.swap(i, candidate)
    this.popDown(candidate)
  }
}