コンピュータプログラムで問題を解決するための手順や計算方法のこと

Algorithm

Amazon.comにより提供されているクラウドコンピューティングサービス

継続的インテグレーション＆継続的デリバリーの略で、アプリケーションの構築、テスト、および展開の自動化を指す

CI/CD

コンテナ仮想化を用いてアプリケーションを開発・配置・実行するためのDocker​社製オープンソースソフトウェア

Docker

GitHub社によって運営されているソースコードの変更履歴を管理するホスティングサービス

GitHub

静的なHTMLをベースに、JavaScriptを用いたAPIを通じて動的なコンテンツを扱うWebサービスのアーキテクチャ

Jamstack

Facebook社がOSSとして開発を進めているJavaScript用テスティングフレームワーク

Jest

MVCモデルでWebアプリケーションを開発できるオープンソースWebアプリケーションフレームワーク

Laravel

GoogleのMaterialデザインをベースに開発された、ウェブ開発をより高速かつ簡単にするReactコンポーネント

Material-UI

Oracle社が中心となって開発しているオープンソースのリレーショナルデータベース管理システム

MySQL

Vercel社がOSSとして開発を進めているReactベースのフロントエンドフレームワーク

Next.js

The PHP Groupによってコミュニティベースで開発されているオープンソースの汎用プログラミング言語。

Facebook社とコミュニティによって開発されているUI構築のためのJavaScriptライブラリ

React

マイクロソフトが開発・販売しているGUIを採用したオペレーティングシステムの製品群

Windows

Algorithm - Breathnote

JavaScriptで解くLeetCodeシリーズ。

第2回は、連結リストが登場する「Add-Two-Numbers」という問題を紹介します。

- [Add Two Numbers - LeetCode](https://leetcode.com/problems/add-two-numbers/)
- [How to Implement a Linked List in JavaScript](https://www.freecodecamp.org/news/implementing-a-linked-list-in-javascript/)

## 問題

自然数を1桁ごとに格納した連結リストが2つ与えられたとき、その連結リストが表す自然数同士を加算した連結リストを返却する。ただし自然数は逆順で格納されており、返却する連結リストも逆順でなければならない。なお、連結リストの最終ノードに0が与えられることはない。

<div className="codeblock-filename">Example</div>

```
Input: [2,4,3], [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807
```

## 解法

Solutionの中でも人気だった、再帰処理を用いた解答例を紹介します。

<div className="codeblock-filename">JavaScript</div>

```js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

var addTwoNumbers = function(l1, l2) {
  let node = null
  const carry = arguments[2]

  if (l1 || l2) {
    const val1 = l1 ? l1.val : 0
    const val2 = l2 ? l2.val : 0
    const next1 = l1 ? l1.next : null
    const next2 = l2 ? l2.next : null
    const val = carry ? val1 + val2 + 1 : val1 + val2
    node = new ListNode(val % 10)
    node.next = addTwoNumbers(next1, next2, val >= 10)
  } else if (carry) {
    node = new ListNode(1)
  }

  return node
};
```

三項演算子のおかげで、再帰呼び出し時の分岐処理が分かりやすくなっており、`else if`で最終桁の繰り上がりも考慮されています。繰り上がりの有無を`arguments[2]`で受け取っている部分がスマートですね。

## 所感

私もこんなコードがスッと書けるようになりたい…。

LeetCodeの「Add-Two-Numbers」を、JavaScriptを用いて解きます。Solutionで見つけた良さそうな答えを紹介するだけの記事になりました。

LeetCodeの「Add-Two-Numbers」をJavaScriptで解く

最近[LeetCode](https://leetcode.com/)で勉強しています。

今回は、記憶定着のためのアウトプットを兼ねて、「Two-Sum」という問題を紹介します。

- [Two Sum - LeetCode](https://leetcode.com/problems/two-sum/)

## 問題

整数が格納された配列numsと整数targetが与えられたとき、足してtargetになる2つの要素をnumsから選択し、そのインデックスを返却する。各入力には必ず1つの解があると仮定し、同じ要素を2回使用することはできない。2つの要素の返却順は問わない。

<div className="codeblock-filename">Example</div>

```
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] == 9
```

## 解法

メジャーな2種類を紹介します。

### 1. 総当たり法

- 時間計算量：$O(n^2)$
- 空間計算量：$O(1)$

ループをネストして2種類のインデックスを用意し、numsの要素を2つ指定してターゲットと比較していきます。下のコードでは、jループの開始を`i + 1`とすることで無駄なループを省いています。

<div className="codeblock-filename">JavaScript</div>

```js
const twoSum = (nums, target) => {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
}
```

### 2. ハッシュテーブル法

- 時間計算量：$O(n)$
- 空間計算量：$O(n)$

オブジェクトを利用して時間計算量を削減します。`{ nums[index]: index }`といった形式のオブジェクトを用意し、`target - nums[i]`の値がプロパティに含まれているかチェックします。

<div className="codeblock-filename">JavaScript</div>

```js
const twoSum = (nums, target) => {
  let hashTable = {}

  for (let i = 0; i < nums.length; i++) {
    hashTable[nums[i]] = i
  }

  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i]
    if (hashTable.hasOwnProperty(diff) && hashTable[diff] !== i) {
      return [i, hashTable[diff]]
    }
  }
}
```

LeetCodeの「Two-Sum」を、JavaScriptを用いて解きます。オブジェクトを用いたハッシュテーブル法と、総当たり法の2つの解法を紹介します。

Algorithm

LeetCodeの「Add-Two-Numbers」をJavaScriptで解く

LeetCodeの「Two-Sum」をJavaScriptで解く