前回

今後は easyをやめて普通に上から順に解いていく予定です。

解答

Problem16

入力されるのは数値リストと数値。二つ目に入力された数値にもっとも近くなるような数値の3つ組（3つを足すと二つ目の数値にもっとも近い値になるような組み合わせ）を見つけ出し、その総和の値を返す。

はじめに結果の候補をリストで保持していて、ミスしたため辞書に結果を保存して回答。

Python

from typing import List

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # resは絶対誤差：総和の辞書
        res = {}
        N = len(nums)

        nums.sort()
        tried_num = nums[0] - 1

        for l in range(N-2):
            # 一度調べた数字は結果が同じはずなのでスキップする
            if nums[l]==tried_num:
                continue
            else:
                tried_num = nums[l]

            # 探索対象の左・右端のインデックスを決める. i=左端のインデックス
            l = l + 1
            r = N - 1

            while l<r:
                # 和を求めて結果を保存
                total = tried_num+nums[l]+nums[r]
                #res.append(total)
                res[abs(target-total)] = total

                if total<target:
                    # 左を減らす
                    l += 1
                elif total>target:
                    # 右を減らす
                    r -= 1
                else:
                    # ターゲットと一致する
                    return target

        return res[min(res)]

以下、確認のためのテスト。

import unittest
from typing import List
from problem16 import Solution

class CheckSolution(unittest.TestCase):
    def setUp(self):
        self.sol = Solution()
        pass

    def tearDown(self):
        pass

    def test_normal_00(self):
        self.assertEqual(2, self.sol.threeSumClosest([-1,2,1,-4], 2))

    def test_normal_01(self):
        self.assertEqual(3, self.sol.threeSumClosest([-1,2,2,100], 2))

    def test_normal_02(self):
        self.assertEqual(2, self.sol.threeSumClosest([-1,2,1,-4], 1))


if __name__ == "__main__":
    unittest.main()

Runtime: 88 ms, faster than 96.17% of Python3 online submissions for 3Sum Closest. Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for 3Sum Closest.

辞書は min(dict)で最小のキーが取れる。最小の値を取る場合は min(dict.values()) で取れる。

数値以外をソートして取得する場合は、

sorted(dict.items(), key=lambda x: len(x)]): などとラムダで指定する。

Problem1281

一桁ごとの数値の掛け算と足し算を行い、その差を返します。例：123が入力

→ (123)-(1+2+3)が答え。

１０で割りながら一桁ずつnの桁を減らしていくことで答えが出ます。

public class Solution {
    public int SubtractProductAndSum(int n) {
        int s = 0;
        int m = 1;
        
        while (n > 0) {
            s += n % 10;
            m *= n % 10;
            n /= 10;
        }
        return m - s;
    }
}

C#の単体テストについては以下を参照。

C# 単体テストチュートリアル - Visual Studio | Microsoft Docs

文字列にして一つずつ見ていく場合。

python

class Solution:
    def subtractProductAndSum(self, n: int) -> int:
        """入力の各桁の掛け算と足し算の差分を返す

        Arguments:
            n {int} -- 自然数(1<=n<=10^5)

        Returns:
            int -- answer
        """

        num_sum = 0
        num_prd = 1

        # もしもn<0のケースがある場合
        # if n<0:
        #   num_sum = int(str([:2]))
        #   num_prd = -1

        for num in str(n):
            num = int(num)
            num_sum+=num
            num_prd*=num

        return num_prd-num_sum

Runtime: 20 ms, faster than 96.14% of Python3 online submissions for Subtract the Product and Sum of Digits of an Integer. Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Subtract the Product and Sum of Digits of an Integer. (https://leetcode.com/submissions/detail/303466904)

Problem1295

入力した数値のリストの中に、偶数桁の数値が幾つ存在するかを求める。

python

ワンライナーの場合。

class Solution:
    def findNumbers(self, nums: List[int]) -> int:
        return len([n for n in nums if len(str(n))%2==0])

C++

class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int res = 0;
        for(const int n : nums){
            size_t len = std::to_string(n).length();
            if (len%2==0) res += 1;
        }
        return res;
    }
};

桁数はlog10でも求めることができるので

class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int res = 0;
        for(const int n : nums)
            if (int(std::log10(n)+1)%2 == 0)
                res += 1;
        return res;
    }
};

も可能。GoogleTestでテストケースを追記し、提出。

log10 - cpprefjp C++日本語リファレンス

Problem1313

特になし. itrs, valsは別に必要ありません.

class Solution:
    def decompressRLElist(self, nums: List[int]) -> List[int]:
        res = []
        itrs = [ii for i, ii in enumerate(nums) if i%2==0]
        vals = [vi for i, vi in enumerate(nums) if i%2==1]

        for itr, v in zip(itrs, vals):
            res += [v for _ in range(itr)]

        return res

Problem1342

２で割れる限り割り続け、最後に割った回数・１を引いた回数＋１を返す. 回答を見て気づいたのですが, バイナリで表現して１の数を数えるのがいいですね.

python

class Solution:
    def numberOfSteps (self, num: int) -> int:
        """/2と-1を何回行えば０になるかを求める

        Arguments:
            num {int} -- 数

        Returns:
            int -- /2, -1の適用回数
        """
        res = 0

        # /2 -1 を値が1になるまで繰り返す
        while(num>1):
            if num%2:
                num = num // 2
                res = res + 2
            else:
                num = num / 2
                res = res + 1

        # 1が余っている場合は+1して返す
        return int(res + num)

テスト：

import unittest
from problem1342 import Solution

class CheckSolution(unittest.TestCase):
    def setUp(self):
        self.sol = Solution()
        pass

    def tearDown(self):
        pass

    def test_normal_00(self):
        self.assertEqual(1, self.sol.numberOfSteps(1))

    def test_normal_01(self):
        self.assertEqual(6, self.sol.numberOfSteps(14))

if __name__ == "__main__":
    unittest.main()

結果:

Runtime: 20 ms, faster than 95.76% of Python3 online submissions for Number of Steps to Reduce a Number to Zero.
Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Number of Steps to Reduce a Number to Zero.