Leetcode 141. Linked List Cycle. Python. Floyd's Tortoise and Hare Algorithm

141. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Solution :

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        s,f = head, head
        
        while f and f.next:
            s = s.next
            f = f.next.next
            if s == f:
                return True
        
        return False

Explaination :

Comments

Leetcode 322. Coin Change. Python (Greedy? vs DP?)

322 . Coin Change You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount . If that amount of money cannot be made up by any combination of the coins, return -1 . You may assume that you have an infinite number of each kind of coin. Example 1: Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Example 2: Input: coins = [2], amount = 3 Output: -1 Example 3: Input: coins = [1], amount = 0 Output: 0 Constraints: 1 <= coins.length <= 12 1 <= coins[i] <= 2 31 - 1 0 <= amount <= 10 4 Solution : class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [amount + 1] * (amount + 1) #[0...7] dp[0] = 0 ...

Leetcode 371. Sum of Two Integers. C++ / Java

371 . Sum of Two Integers Given two integers a and b , return the sum of the two integers without using the operators + and - . Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5 Constraints: -1000 <= a, b <= 1000 Solution : C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java : class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :

Leetcode 424. Longest Repeating Character Replacement. Python (Sliding Window)

424 . Longest Repeating Character Replacement You are given a string s and an integer k . You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations . Example 1: Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. Example 2: Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4. Constraints: 1 <= s.length <= 10 5 s consists of only uppercase English letters. 0 <= k <= s.length Solution : class Solution: def characterReplacement(self, s: str, k: int) -> int: hm = {} ans = 0 ...

LEETCODE SOLUTIONS

Search This Blog