What I've done today is Pentagon numbers in Rust and Binary Tree Postorder Traversal in JavaScript.

Math

Problem

Pentagon numbers

Problem 44

Pentagonal numbers are generated by the formula, $P_n=n(3n−1)/2$. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that$ P_4 + P_7 = 22 + 70 = 92 = P_8$. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, $P_j$ and $P_k$, for which their sum and difference are pentagonal and$ D = |P_k − P_j|$ is minimized; what is the value of D?

Solution

$$P_n = \frac{n(3n-1)}{2}=\frac{(6n-1)^2-1}{24}​$$

if $P_k-P_j =P_x$ and $P_k+P_j=P_y$ are both pentagonal numbers, so there comes

$$(6k-1)^2-(6j-1)^2=(6x-1)^2-1​$$

$$(6k-1)^2+(6j-1)^2=(6y-1)^2+1$$

$$2(6k-1)^2=(6x-1)^2+(6y-1)^2$$

OK I don't know how to use these,,,,,, so just...

Brute Force?

Implementation

use std::collections::HashSet;

fn main() {
    let mut set: HashSet<i64> = HashSet::new();
    let mut arr: [i64; 5000] = [0; 5000];
    for i in 1..5001 {
        arr[i-1] = (i*(3*i-1)/2) as i64;
        set.insert((i*(3*i-1)/2) as i64);
    }
    let mut offset: usize = 1;
    let mut index: usize;
    let mut found: bool = false;
    let mut ans: i64 = 0;
    while offset < 5000 && !found {
        index = 0;
        while index < 5000 - offset && !found {
            if set.contains(&(arr[index]+arr[index+offset])) && set.contains(&(arr[index+offset]-arr[index])) {
                ans = arr[index+offset] - arr[index];
                found = true;
            }
            index += 1;
        }
        offset += 1;
    }
    println!("Answer is {}", ans);
}

Algorithm

Problem

145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution

Nothing to say.

Implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
  let ans = [];
  const postTravel = (root) => {
    if (root === null) return;
    postTravel(root.left);
    postTravel(root.right);
    ans.push(root.val);
  };
  postTravel(root);
  return ans;
};

non-recursive implementation

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
  if(root == null) return [];
  let ans = [root.val];
  let s = [];
  s.push(root.left);
  s.push(root.right);
  while (s.length) {
    let tmp = s.pop();
    if (tmp === null) continue;
    ans.unshift(tmp.val);
    s.push(root.left);
    s.push(root.right);
  }
  return ans;
};