跳房子I Hopscotch(I)-HUAWEI-CodingInterview
1098
2023.08.10
发布于 未知归属地

Topic

23-跳房子I
Hopscotch(I)-HUAWEI-CodingInterview

Problem Description

image.png

Key Point & Tag

Difficulty Assessment: Easy

Approach

Use a Dict to record {val: min_idx} and try to get Dict.get(TARGET - val)

Code

class Hopscotch:
	# Input Part
	def GetInput(self)->None:
		'''
		Get Input Data and Preprocess Data
		'''
		self.nums = list(map(int, input().strip(' []').split(','))) # Allow Duplicates
		self.K = int(input()) # target amount

	# Algorithm Part
	def Solution(self)->int:
		'''
		Algorithm Solving Problem
		'''
		# Get data from self
		K = self.K
		nums = self.nums # sort ASC

		dic = {} # {val: min_idx}
		MSidx = float('inf') # Min Sum of Indexes

		for i in range(len(nums)):
			cur, tgt = nums[i], K - nums[i]

			if dic.get(tgt, None) == None: # val didn't show up
				dic[cur] = i # Record Current {val:idx}
			else:
				j = dic[tgt] # index of val2
				Sidx = i + j # Sum of Indexes
				if Sidx < MSidx: # Update Min-Sum-of-Indexes
					MSidx = Sidx
					# [nums[smaller-index], nums[larger-index]]
					res = f'[{cur}, {tgt}]' if i < j else f'[{tgt}, {cur}]'

		return res

# Execution Part
if __name__ == "__main__":
	# Instantiate
	obj = Hopscotch()
	# Get Input
	obj.GetInput()
	# Get Result
	print(obj.Solution())

Test Cases

[1,4,5,2,2]
7

[-1,2,4,9,6]
8
评论 (2)