Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day32 "437. Path Sum III" starting from zero

Basically, I would like to solve the easy acceptance in descending order.

Twitter I'm doing it.

problem

1. Two Sum

I didn't write about the problem that I would solve first when I registered with LeetCode, so I will write it now.

The difficulty level is Easy. Excerpt from Top 100 Liked Questions.

The problem is that you are given an array of integers and a variable target that contains a particular value. Choose two integers from the array, find a combination that matches target, and implement a function that returns the index of the array. Note that there is only one combination, and the same value cannot be used twice.

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

solution

For example, if you write it in full search, it will be like this.

A full search is a so-called scrutiny, and in most cases it results in fatal performance instead of trying to search all patterns.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                ans =  nums[i] + nums[j]
                if target == ans:
                    return [i,j]
# Runtime: 6848 ms, faster than 5.01% of Python3 online submissions for Two Sum.
# Memory Usage: 14.6 MB, less than 18.14% of Python3 online submissions for Two Sum.

It's late. Let's write using a hash map instead.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        
        for i in range(len(nums)):
            num = nums[i]
            complement = target - num
            if num in hashmap:
                return [hashmap[num],i]
            else:
                hashmap[complement] = i
# Runtime: 52 ms, faster than 60.15% of Python3 online submissions for Two Sum.
# Memory Usage: 15.3 MB, less than 5.11% of Python3 online submissions for Two Sum.

The speed has improved considerably.

It's important to learn how to write a language and write it short, but not only that, but one of the major reasons for learning data structures and algorithms is that you can change the speed significantly with just one writing method.

I will write it here as a commandment to myself.

This way of writing is better! I wrote it in this language! If you have any questions, please feel free to comment.

[PYTHON] Let Code Day 33 "1. Two Sum" starting from scratch

Overview

problem

solution