アルゴリズムのチートシート

def linear(nums, t):
    steps = 0
    for x in nums:
        steps += 1
        if x == t:
            break
    return steps

def binary(nums, t):
    lo, hi = 0, len(nums) - 1
    steps = 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if nums[mid] == t:
            break
        if nums[mid] < t:
            lo = mid + 1
        else:
            hi = mid - 1
    return steps

for n in (10, 100, 1000):
    nums = list(range(n))
    print(n, linear(nums, n - 1),
          binary(nums, n - 1))

function linear(nums, t) {
  let steps = 0;
  for (const x of nums) {
    steps += 1;
    if (x === t) break;
  }
  return steps;
}

function binary(nums, t) {
  let lo = 0;
  let hi = nums.length - 1;
  let steps = 0;
  while (lo <= hi) {
    steps += 1;
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] === t) break;
    if (nums[mid] < t) lo = mid + 1;
    else hi = mid - 1;
  }
  return steps;
}

for (const n of [10, 100, 1000]) {
  const nums = [...Array(n).keys()];
  console.log(n, linear(nums, n - 1),
    binary(nums, n - 1));
}

def max_window(nums, k):
    cur = sum(nums[:k])
    best = cur
    for i in range(k, len(nums)):
        cur += nums[i]
        cur -= nums[i - k]
        best = max(best, cur)
    return best

nums = [2, 1, 5, 1, 3, 2]
print(max_window(nums, 3))

function maxWindow(nums, k) {
  let cur = 0;
  for (let i = 0; i < k; i++) {
    cur += nums[i];
  }
  let best = cur;
  for (let i = k; i < nums.length; i++) {
    cur += nums[i] - nums[i - k];
    best = Math.max(best, cur);
  }
  return best;
}

const nums = [2, 1, 5, 1, 3, 2];
console.log(maxWindow(nums, 3));

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i

print(*two_sum([3, 8, 2, 7], 9))

function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) {
      return [seen.get(need), i];
    }
    seen.set(nums[i], i);
  }
}

console.log(...twoSum([3, 8, 2, 7], 9));

def search(nums, t):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == t:
            return mid
        if nums[mid] < t:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

nums = [
    2, 5, 8, 12, 16,
    23, 38, 56, 72, 91,
]
print(search(nums, 23))
rest = sorted([10, 9, 1])
print(*rest)

function search(nums, t) {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] === t) return mid;
    if (nums[mid] < t) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

const nums = [
  2, 5, 8, 12, 16,
  23, 38, 56, 72, 91,
];
console.log(search(nums, 23));
const rest = [10, 9, 1];
rest.sort((a, b) => a - b);
console.log(...rest);

def lower(nums, t):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < t:
            lo = mid + 1
        else:
            hi = mid
    return lo

nums = [1, 2, 2, 2, 3, 5]
first = lower(nums, 2)
count = lower(nums, 3) - first
print(first, count)
print(lower(nums, 4))

function lower(nums, t) {
  let lo = 0;
  let hi = nums.length;
  while (lo < hi) {
    const half = Math.floor((hi - lo) / 2);
    const mid = lo + half;
    if (nums[mid] < t) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

const nums = [1, 2, 2, 2, 3, 5];
const first = lower(nums, 2);
const count = lower(nums, 3) - first;
console.log(first, count);
console.log(lower(nums, 4));

def smallest_root(n):
    lo, hi = 0, n
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if mid * mid >= n:
            hi = mid
        else:
            lo = mid + 1
    return lo

print(smallest_root(1000))
print(smallest_root(1024))

function smallestRoot(n) {
  let lo = 0;
  let hi = n;
  while (lo < hi) {
    const half = Math.floor((hi - lo) / 2);
    const mid = lo + half;
    if (mid * mid >= n) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

console.log(smallestRoot(1000));
console.log(smallestRoot(1024));

def is_valid(s):
    pairs = {
        ")": "(",
        "]": "[",
        "}": "{",
    }
    st = []
    for ch in s:
        if ch not in pairs:
            st.append(ch)
        elif not st:
            return False
        elif st.pop() != pairs[ch]:
            return False
    return not st

def show(ok):
    print("ok" if ok else "ng")

show(is_valid("({[]})"))
show(is_valid("(]"))

function isValid(s) {
  const pairs = {
    ")": "(",
    "]": "[",
    "}": "{",
  };
  const st = [];
  for (const ch of s) {
    if (!(ch in pairs)) {
      st.push(ch);
    } else if (st.pop() !== pairs[ch]) {
      return false;
    }
  }
  return st.length === 0;
}

function show(ok) {
  console.log(ok ? "ok" : "ng");
}

show(isValid("({[]})"));
show(isValid("(]"));

class Node:
    def __init__(self, v,
                 l=None, r=None):
        self.v = v
        self.l = l
        self.r = r

def depth(node):
    if node is None:
        return 0
    return 1 + max(depth(node.l),
                   depth(node.r))

left = Node(2, Node(4))
tree = Node(1, left, Node(3))
print(depth(tree))

class Node {
  constructor(v, l = null, r = null) {
    this.v = v;
    this.l = l;
    this.r = r;
  }
}

function depth(node) {
  if (node === null) return 0;
  return 1 + Math.max(depth(node.l),
    depth(node.r));
}

const left = new Node(2, new Node(4));
const tree = new Node(1, left, new Node(3));
console.log(depth(tree));

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}

def bfs(start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if v in dist:
                continue
            dist[v] = dist[u] + 1
            queue.append(v)
    return dist

def dfs(u, seen):
    seen[u] = True
    for v in graph[u]:
        if v not in seen:
            dfs(v, seen)
    return seen

dist = bfs("A")
print(" ".join(dist), dist["E"])
print(" ".join(dfs("A", {})))

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C", "E"],
  E: ["D"],
};

function bfs(start) {
  const dist = new Map([[start, 0]]);
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];
    for (const v of graph[u]) {
      if (dist.has(v)) continue;
      dist.set(v, dist.get(u) + 1);
      queue.push(v);
    }
  }
  return dist;
}

function dfs(u, seen) {
  seen.add(u);
  for (const v of graph[u]) {
    if (!seen.has(v)) {
      dfs(v, seen);
    }
  }
  return seen;
}

const dist = bfs("A");
const order = [...dist.keys()];
console.log(order.join(" "), dist.get("E"));
const seen = dfs("A", new Set());
console.log([...seen].join(" "));

def climb(n):
    dp = [1, 1]
    for i in range(2, n + 1):
        dp.append(dp[-1] + dp[-2])
    return dp[n]

print(climb(6))

function climb(n) {
  const dp = [1, 1];
  for (let i = 2; i <= n; i++) {
    dp.push(dp[i - 1] + dp[i - 2]);
  }
  return dp[n];
}

console.log(climb(6));

calls = [0, 0]
memo = {}

def plain(n):
    calls[0] += 1
    if n <= 1:
        return 1
    a = plain(n - 1)
    return a + plain(n - 2)

def with_memo(n):
    calls[1] += 1
    if n <= 1:
        return 1
    if n not in memo:
        a = with_memo(n - 1)
        b = with_memo(n - 2)
        memo[n] = a + b
    return memo[n]

print(plain(25), with_memo(25))
print(*calls)

const calls = [0, 0];
const memo = new Map();

function plain(n) {
  calls[0] += 1;
  if (n <= 1) return 1;
  return plain(n - 1) + plain(n - 2);
}

function withMemo(n) {
  calls[1] += 1;
  if (n <= 1) return 1;
  if (!memo.has(n)) {
    const a = withMemo(n - 1);
    const b = withMemo(n - 2);
    memo.set(n, a + b);
  }
  return memo.get(n);
}

console.log(plain(25), withMemo(25));
console.log(...calls);