# Given an array of integers and an integer k, find out whether there are two distinct indices i and j
# in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
#
# Example 1:
#
# Input: nums = [1,2,3,1], k = 3
# Output: true
# Example 2:
#
# Input: nums = [1,0,1,1], k = 1
# Output: true
# Example 3:
#
# Input: nums = [1,2,3,1,2,3], k = 2
# Output: false

class Solution:
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        temp_dict = {}
        for idx in range(len(nums)):
            if nums[idx] in temp_dict:
                if idx - temp_dict.get(nums[idx]) <= k:
                    return True
            temp_dict[nums[idx]] = idx
        return False

# Given an array of integers, find if the array contains any duplicates.
#
# Your function should return true if any value appears at least twice in the array, and it should return false
# if every element is distinct.
#
# Example 1:
#
# Input: [1,2,3,1]
# Output: true
# Example 2:
#
# Input: [1,2,3,4]
# Output: false
# Example 3:
#
# Input: [1,1,1,3,3,4,3,2,4,2]
# Output: true

class Solution:
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        temp_dict = {}
        for val in nums:
            if val in temp_dict:
                return True
            temp_dict[val] = val
        return False

    def containsDuplicate_via_set(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        return len(nums) != len(set(nums))

# Reverse a singly linked list.
#
# Example:
#
# Input: 1->2->3->4->5->NULL
# Output: 5->4->3->2->1->NULL
#
# Follow up:
#
# A linked list can be reversed either iteratively or recursively. Could you implement both?

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

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


# 迭代法
class SolutionIteratively:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre_node = None
        while head is not None:
            pre_node, head.next, head = head, pre_node, head.next
        return pre_node


# 递归法
class SolutionRecursively:
    def reverseTail(self, cur, pre=None):
        if not cur:
            return pre
        temp_node = cur.next
        cur.next = pre
        return self.reverseTail(temp_node, cur)

    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        return self.reverseTail(head)


node_5 = ListNode(5)
node_4 = ListNode(4)
node_4.next = node_5
node_3 = ListNode(3)
node_3.next = node_4
node_2 = ListNode(2)
node_2.next = node_3
node_1 = ListNode(1)
node_1.next = node_2

solution = SolutionIteratively()
result = solution.reverseList(node_1)
print(result)

result_rec = SolutionRecursively().reverseList(node_5)
print(result_rec)

class Solution:
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        temp_s_t_map = {}
        temp_t_s_map = {}
        for idx in range(len(s)):
            if temp_s_t_map.get(s[idx]) is None and temp_t_s_map.get(t[idx]) is None:
                temp_s_t_map[s[idx]] = t[idx]
                temp_t_s_map[t[idx]] = s[idx]
            elif temp_s_t_map.get(s[idx]) is not t[idx] or temp_t_s_map.get(t[idx]) is not s[idx]:
                return False
        return True


s = Solution()
print(s.isIsomorphic("egg","add"))
print(s.isIsomorphic("foo","bar"))
print(s.isIsomorphic("paper","title"))
print(s.isIsomorphic("ab","aa"))

# Count the number of prime numbers less than a non-negative number, n.

class Solution:
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return 0
        primes = [True] * n
        primes[0] = primes[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if primes[i]:
                primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
        return sum(primes)


solution = Solution()
print(solution.countPrimes(2))
print(solution.countPrimes(499979))

# Remove all elements from a linked list of integers that have value val.
#
# Example
# Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
# Return: 1 --> 2 --> 3 --> 4 --> 5

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        pre_node = None
        cur_node = head
        while cur_node is not None:
            if cur_node.val == val:
                if pre_node is None:
                    head = head.next
                else:
                    pre_node.next = cur_node.next
            else:
                pre_node = cur_node
            cur_node = cur_node.next
        return head

# Write an algorithm to determine if a number is "happy".
#
# A happy number is a number defined by the following process: Starting with any positive integer, replace the number by
#  the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay),
# or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy
# numbers.
#
# Example: 19 is a happy number
#
# 1^2 + 9^2 = 82
# 8^2 + 2^2 = 68
# 6^2 + 8^2 = 100
# 1^2 + 0^2 + 0^2 = 1

class Solution:
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        temp_result = {}
        return self.docharge(n, temp_result)

    def docharge(self, n, temp_result):
        if temp_result.get(n) is not None:
            return False
        temp_result[n] = n
        cur_sum = 0
        while n > 0:
            cur_num = n % 10
            cur_sum += cur_num ** 2
            n //= 10
        if cur_sum == 1:
            return True
        else:
            return self.docharge(cur_sum, temp_result)

solution = Solution()
print(solution.isHappy(19))
print(solution.isHappy(23))
print(solution.isHappy(22))

# You are a professional robber planning to rob houses along a street.
# Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is
# that adjacent houses have security system connected and it will automatically contact the police
# if two adjacent houses were broken into on the same night.
#
# Given a list of non-negative integers representing the amount of money of each house, determine the maximum
# amount of money you can rob tonight without alerting the police.

# author li.hzh
class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        last = now = 0
        for i in nums:
            last, now = now, max(last + i, now)
        return now


solution = Solution()
print(solution.rob([5, 3, 1, 10]))