Appearance
question:cpp class ListNode { public: int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseSecondHalf(ListNode* head); /** * Given a linked list, reverse the second half of the list and return the head of the updated list. * * @param head the head of the input linked list * @return the head of the modified linked list * * Example: * Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 * Output: 1 -> 2 -> 3 -> 6 -> 5 -> 4 * * Input: 1 -> 2 -> 3 -> 4 -> 5 * Output: 1 -> 2 -> 3 -> 5 -> 4 */
answer:class ListNode: def __init__(self, x): self.val = x self.next = None def reverseSecondHalf(head): # Find the middle of the list using the slow and fast pointers. slow, fast = head, head prev = None while fast and fast.next: prev = slow slow = slow.next fast = fast.next.next # If the list has odd number of nodes, move slow one step further. if fast: prev = slow slow = slow.next # Start reversing from slow. prev.next = None # break the list into two parts prev = None curr = slow while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node # Link the first half with the reversed second half. tail = head while tail.next: tail = tail.next tail.next = prev return head
question:def longest_substring_with_k_distinct(s: str, k: int) -> int: Find the length of the longest substring with exactly k distinct characters. >>> longest_substring_with_k_distinct("eceba", 2) 3 >>> longest_substring_with_k_distinct("aa", 1) 2 # Your implementation here pass Example Usage: print(longest_substring_with_k_distinct("eceba", 2)) # Output: 3 print(longest_substring_with_k_distinct("aa", 1)) # Output: 2 Unit Test: from solution import longest_substring_with_k_distinct def test_example_cases(): assert longest_substring_with_k_distinct("eceba", 2) == 3 assert longest_substring_with_k_distinct("aa", 1) == 2 def test_edge_cases(): assert longest_substring_with_k_distinct("", 1) == 0 assert longest_substring_with_k_distinct("a", 0) == 0 def test_general_cases(): assert longest_substring_with_k_distinct("abcba", 2) == 3 assert longest_substring_with_k_distinct("aabbcc", 2) == 4 assert longest_substring_with_k_distinct("aabbcc", 1) == 2 assert longest_substring_with_k_distinct("aabacbebebe", 3) == 7 def test_large_k_value(): assert longest_substring_with_k_distinct("abracadabra", 5) == 11 def test_all_same_characters(): assert longest_substring_with_k_distinct("aaaaaa", 1) == 6 def test_distinct_chars(): assert longest_substring_with_k_distinct("abcdef", 6) == 6 assert longest_substring_with_k_distinct("abcdef", 3) == 3 assert longest_substring_with_k_distinct("abcdef", 1) == 1
answer:def longest_substring_with_k_distinct(s: str, k: int) -> int: from collections import defaultdict if k == 0: return 0 window_start = 0 max_length = 0 char_frequency = defaultdict(int) for window_end in range(len(s)): right_char = s[window_end] char_frequency[right_char] += 1 while len(char_frequency) > k: left_char = s[window_start] char_frequency[left_char] -= 1 if char_frequency[left_char] == 0: del char_frequency[left_char] window_start += 1 max_length = max(max_length, window_end - window_start + 1) return max_length
question:def decodeString(s: str) -> str: Decodes the given encoded string according to the rule k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. >>> decodeString("3[a]") == "aaa" >>> decodeString("3[a]2[bc]") == "aaabcbc" >>> decodeString("3[a2[c]]") == "accaccacc" >>> decodeString("2[abc]3[cd]ef") == "abcabccdcdcdef"
answer:def decodeString(s: str) -> str: Decodes the given encoded string according to the rule k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. stack = [] current_num = 0 current_string = '' for char in s: if char.isdigit(): current_num = current_num * 10 + int(char) elif char == '[': stack.append((current_string, current_num)) current_string = '' current_num = 0 elif char == ']': prev_string, num = stack.pop() current_string = prev_string + num * current_string else: current_string += char return current_string
question:def find_nth_in_sequence(n: int) -> int: Returns the value at the nth position in the sequence defined as: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ... where the integer m occurs m times consecutively. Args: n (int): The position in the sequence (1 <= n <= 10^9) Returns: int: The value at the nth position Examples: >>> find_nth_in_sequence(1) 1 >>> find_nth_in_sequence(3) 2 >>> find_nth_in_sequence(10) 4 >>> find_nth_in_sequence(15) 5 # Your implementation here def test_find_nth_in_sequence(): assert find_nth_in_sequence(1) == 1 assert find_nth_in_sequence(2) == 2 assert find_nth_in_sequence(3) == 2 assert find_nth_in_sequence(4) == 3 assert find_nth_in_sequence(10) == 4 assert find_nth_in_sequence(15) == 5 assert find_nth_in_sequence(21) == 6 assert find_nth_in_sequence(28) == 7 assert find_nth_in_sequence(36) == 8 assert find_nth_in_sequence(5050) == 100 assert find_nth_in_sequence(5000000) == 3162
answer:def find_nth_in_sequence(n): Returns the value at the nth position in the sequence defined as: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ... where the integer m occurs m times consecutively. k = 1 # current integer in the sequence total_numbers = 0 # total numbers counted so far while True: total_numbers += k if n <= total_numbers: return k k += 1