Week4‐Week5 - Joanna-0427/leetcode GitHub Wiki

1. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Input: nums = [1,1,1], k = 2
Output: 2 Input: nums = [1, 2, 3], k = 7
Output: 0

2. Check if Array Is Sorted and Rotated

Given an array nums, return True if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return False.

There may be duplicates in the original array. Note: Rotating an array by a certain number of positions means shifting each element that many positions to the right (or left). When shifted one position to the right, the last element in the array becomes the first element in the array. Formally, an array A rotated by x positions results in an array B of the same length such that:

B[i] == A[(i + x) % A.length]

where % is the modulo operation.

Input: nums = [3,4,5,1,2]
Output: True
Explanation: [1,2,3,4,5] is the original sorted array.
You can rotate the array by x = 3 positions to begin on the element of value 3: [3,4,5,1,2].

Input: nums = [2,1,3,4]
Output: False
Explanation: There is no sorted array once rotated that can make nums.

3. Find Closest NFT Values

Buyers often look for NFTs that are closest in value to their budget. Given a sorted list of NFT values and a budget, you need to find the two NFT values that are closest to the given budget: one that is just below or equal to the budget and one that is just above or equal to the budget. If an exact match exists, it should be included as one of the values.

Write the find_closest_nft_values() function, which takes a sorted list of NFT values and a budget, and returns the pair of the two closest NFT values.

Evaluate the time and space complexity of your solution. Define your variables and provide a rationale for why you believe your solution has the stated time and space complexity.

nft_values = [3.5, 5.4, 7.2, 9.0, 10.5] nft_values_2 = [2.0, 4.5, 6.3, 7.8, 12.1] nft_values_3 = [1.0, 2.5, 4.0, 6.0, 9.0]

print(find_closest_nft_values(nft_values, 8.0)) print(find_closest_nft_values(nft_values_2, 6.5)) print(find_closest_nft_values(nft_values_3, 3.0))

4. Copy Linked List

Write a function copy_ll() that takes in the head of a linked list and creates a complete copy of that linked list.

The function should return the head of a new linked list which is identical to the given list in terms of its structure and contents, but does not use any of the node objects from the original list.

class Node: def init(self, value, next=None): self.value = value self.next = next

/For testing/ def print_linked_list(head): current = head while current: print(current.value, end=" -> " if current.next else "\n") current = current.next

def copy_ll(head): pass Example Usage:

mario = Node("Mario") daisy = Node("Daisy") luigi = Node("Luigi") mario.next = daisy daisy.next = luigi

/Linked List: Mario -> Daisy -> Luigi/ copy = copy_ll(mario)

/Change original list -- should not affect the copy/ mario.value = "Original Mario"

print_linked_list(mario)

5. Find Length of Doubly Linked List from Any Node

Write a function get_length() that takes in a node at an unknown position within a doubly linked list. The function should return the length of the entire list.

class Node: def init(self, value, next=None, prev=None): self.value = value self.next = next self.prev = prev

/ For testing / def print_linked_list(head): current = head while current: print(current.value, end=" -> " if current.next else "\n") current = current.next

def get_length(node): pass
Example Usage:

yoshi_falls = Node("Yoshi Falls") moo_moo_farm = Node("Moo Moo Farm") rainbow_road = Node("Rainbow Road") dk_mountain = Node("DK Mountain") yoshi_falls.next = moo_moo_farm moo_moo_farm.next = rainbow_road rainbow_road.next = dk_mountain dk_mountain.prev = rainbow_road rainbow_road.prev = moo_moo_farm moo_moo_farm.prev = yoshi_falls

print(get_length(rainbow_road))

Problem 8: Get Rank

The Player class has been updated below with a new attribute ahead to represent the player currently directly ahead of them in the race.

Write a function get_rank() that accepts a Player object my_player and returns their current place number in the race.

class Player: def init(self, character, kart, opponent=None): self.character = character self.kart = kart self.items = [] self.ahead = opponent

def get_rank(my_player): pass