1. Two Sum
# exactly one solution Input: nums = [2,7,11,15], target = 9 Output: [0,1] Output: Because nums[0] + nums[1] == 9, we return [0, 1].
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: # stack = {} stack = [] for idx, p in enumerate(nums): if p in stack: # idx2 = stack[p] idx2 = stack.index(p) return [idx2, idx] else: # stack[target-p]=idx stack.append(target-p)
7. Reverse Integer
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
Input: x = 123 Output: 321 Input: x = 120 Output: 21
class Solution: def reverse(self, x: int) -> int: reverse_str = str(int(abs(x)))[::-1] submit = int(reverse_str) # must check first if submit>= 2** 31 -1 or submit<= -2** 31: return 0 elif x<0: return -submit else: return submit
9. Palindrome Number
Given an integer x, return true if x is palindrome integer.
An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.
Input: x = 121 Output: true Input: x = -121 Output: false
class Solution: def isPalindrome(self, x: int) -> bool: return str(x)==str(x)[::-1]
13. Roman to Integer
Input: s = "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
class Solution: def romanToInt(self, s: str) -> int: d = {'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1} total = 0 for i in range(0, len(s)-1): if d[s[i]]>=d[s[i+1]]: total += d[s[i]] else: total -= d[s[i]] # last facter dose not be included in above loop total += d[s[-1]] return total
20. Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[', ']',
determine if the input string is valid.An input string is valid if:
・Open brackets must be closed by the same type of brackets.
・Open brackets must be closed in the correct order.
# sample1 Input: s = "{[]}" Output: true # sample2 Input: s = "()[]{}" Output: true # sample3 Input: s = "([)]" Output: false
class Solution(object): def isValid(self, s): stack = [] mapping = {")": "(", "}": "{", "]": "["} for char in s: if char in mapping.keys(): # when else, stack is empty c = stack.pop() if stack else '#' if mapping[char] != c: return False else: stack.append(char) # for cases like '[' return not stack
26. Remove Duplicates from Sorted Array
Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
# 訳:新しいlistを使わずに重複要素を削除して、listの長さをreturn しな Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4] Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.
class Solution: def removeDuplicates(self, nums: List[int]) -> int: i=0 n = len(nums) for _ in range(n-1): if nums[i]==nums[i+1]: del nums[i] else: i +=1 return len(nums)
35. Search Insert Position
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.# sample1 Input: nums = [1,3,5,6], target = 5 Output: 2 # sample2 Input: nums = [1,3,5,6], target = 2 Output: 1
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: for i,n in enumerate(nums): if nums[i] >= target: return i elif i == len(nums) - 1: return len(nums)
53. Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
class Solution: def maxSubArray(self, nums: List[int]) -> int: if not nums: return 0 # curSum : save add subarray # maxSum :maximum add subarray in loop curSum = maxSum = nums[0] for num in nums[1:]: curSum = max(num, curSum + num) maxSum = max(maxSum, curSum) return maxSum
167. Two Sum II - Input array is sorted
Given an array nums of size n, return the majority element.The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
# sample1 Input: nums = [3,2,3] Output: 3 # sample2 Input: nums = [2,2,1,1,1,2,2] Output: 2
class Solution: def majorityElement(self, nums: List[int]) -> int: d={} for val in nums: if val in d: d[val] +=1 else: d[val] =1 return max(d, key=d.get) # dictのvalueの最も大きいkeyをgetできる
171. Excel Sheet Column Number(解決法:ググリ力)
Given a column title as appear in an Excel sheet, return its corresponding column number.For example:
A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... # sample1 Input: "A" Output: 1 # sample 2 Input: "ZY" Output: 701
解決法:「アルファベット 数字 python」でググった。
class Solution: def titleToNumber(self, alpha: str) -> int: num=0 for index, item in enumerate(list(alpha)): num += pow(26,len(alpha)-index-1)*(ord(item)-ord('A')+1) return num