Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function(s) {
  s = s.replace(/\s/g, '');
  var num = 0;
  var numStack = [];
  var sym = '+';  // 前一个符号，默认可为 '+'

  for (var i = 0, len = s.length; i < len; i++) {
    var item = s[i];

    if (~'+-*/'.indexOf(item) || i === len - 1) {
      (i === len - 1) && (num = num * 10 + (+item));

      if (sym === '-')
        numStack.push(-num);
      else if (sym === '+')
        numStack.push(+num);
      else if (sym === '*')
        numStack.push(numStack.pop() * num);
      else
        numStack.push(~~(numStack.pop() / num));

      num = 0;
      sym = item;
    } else {
      num = num * 10 + (+item);
    }
  }

  var ans = 0;
  numStack.forEach(function(item) {
    ans += item;
  });

  return ans;
};

Battleships in a Board

Given an 2D board, count how many battleships are in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may assume the following rules:

1. You receive a valid board, made of only battleships or empty slots.
2. Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
3. At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

Example:

X..X
...X
...X

In the above board there are 2 battleships.

Invalid Example:

...X
XXXX
...X

This is an invalid board that you will not receive - as battleships will always have a cell separating between them.

Follow up:

Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board

"use strict";

/**
 * @param {character[][]} board
 * @return {number}
 */
var countBattleships = function(board) {
  const dir = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  const m = board.length;
  const n = board[0].length;
  const hash = [];
  let ans = 0;

  for (let i = 0; i < m; i++)
    hash[i] = [];

  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) {
      if (board[i][j] === '.' || hash[i][j])
        continue;
      hash[i][j] = true;
      ans++;
      dfs(i, j);
    }

  function dfs(x, y) {
    for (let i = 0; i < 4; i++) {
      let nx = x + dir[i][0];
      let ny = y + dir[i][1];
      if (nx < 0 || nx >= m || ny < 0 || ny >= n || board[nx][ny] === '.' || hash[nx][ny])
        continue;
      hash[nx][ny] = true;
      dfs(nx, ny);
    }
  }

  return ans;
};

Beautiful Arrangement

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the i-th position (1 <= i <= N) in this array:

1. The number at the i-th position is divisible by i.
2. i is divisible by the number at the i-th position.

Now given N, how many beautiful arrangements can you construct?

Example 1:

Input: 2
Output: 2
Explanation: 

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).

Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:

Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).

Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

Note:

1. N is a positive integer and will not exceed 15.

/**
 * @param {number} N
 * @return {number}
 */
var countArrangement = function(N) {
  let [ans, hash] = [0, {}];

  let dfs = (index) => {
    if (index === N + 1) {
      ans++;
      return;
    }

    for (let i = 1; i <= N; i++) {
      if (!hash[i] && (index % i === 0 || i % index === 0)) {
        hash[i] = true;
        dfs(index + 1);
        hash[i] = false;
      }
    }
  };

  dfs(1);
  return ans;
};

Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  var ans = 0;

  var len = prices.length;
  
  var minn = Infinity;

  for (var i = 0; i < len; i++) {
    minn = Math.min(minn, prices[i]);
    ans = Math.max(ans, prices[i] - minn);
  }

  return ans;

};