s = '{name} has {n} apples'
# 使用参数
s.format(name='link', n=10)
#'link has 10 apples'

# 使用mapping
s.format_map({'name': 'link', 'n': 10})
#'link has 10 apples'

# vars()
name = 'link'
n = 10
s.format_map(vars())
#'link has 10 apples'

class Info:
  def __init__(self, name=None, n=None):
      self.name = your
      self.n =n

info = Info(name='link', n=10)
s.format_map(vars(info))
#'link has 10 apples'

class SafeSub(dict):
  def __missing__(self, key):
    return '{' + key + '}'

info = Info(name='link')
s.format_map(SafeSub(vars()))
##'link has {n} apples'

import sys

def sub(text):
    return text.format_map(safesub(sys._getframe(1).f_locals))
# sub() 函数使用 sys._getframe(1) 返回调用者的栈帧。可以从中访问属性 f_locals
# 来获得局部变量。 毫无疑问绝大部分情况下在代码中去直接操作栈帧应该是不推荐的。
# 但是，对于像字符串替换工具函数而言它是非常有用的。 另外，值得注意的是 f_locals
# 是一个复制调用函数的本地变量的字典。 尽管你可以改变 f_locals 的内容，
# 但是这个修改对于后面的变量访问没有任何影响。 所以，虽说访问一个栈帧看上去很邪恶，
# 但是对它的任何操作不会覆盖和改变调用者本地变量的值。

name = 'Guido'
n = 37
'%(name)s  %(n)d messages.' % vars()

import string
s = string.Template('$name has $n messages.')
s.substitute(vars())

s = "Look into my eyes, look into my eyes, the eyes, the eyes, \
the eyes, not around the eyes, don't look around the eyes, \
look into my eyes, you're under."

import textwrap
textwrap.fill(s, width=20)
# Look into my eyes,
# look into my eyes,
# the eyes, the eyes,
# the eyes, not around
# the eyes, don't look
# around the eyes,
# look into my eyes,
# you're under.

textwrap.fill(s, 40, initial_indent='****')
# ****Look into my eyes, look into my
# eyes, the eyes, the eyes, the eyes, not
# around the eyes, don't look around the
# eyes, look into my eyes, you're under.

textwrap.fill(s, 40, subsequent_indent='****')
# Look into my eyes, look into my eyes,
# ****the eyes, the eyes, the eyes, not
# ****around the eyes, don't look around
# ****the eyes, look into my eyes, you're
# ****under.

import os
os.get_terminal_size()
# os.terminal_size(columns=76, lines=32)

s = 'Elements are written as "<tag>text</tag>".'
from html import escape, unescape
es = escape(s)
# 'Elements are written as &quot;&lt;tag&gt;text&lt;/tag&gt;&quot;.'

escape(s, quote=False) # 不转化 " 和 '
# 'Elements are written as "&lt;tag&gt;text&lt;/tag&gt;".'

unescape(es)
# 'Elements are written as "<tag>text</tag>".'

setup(
    # other arguments here...
    entry_points={
        'console_scripts': [
            'foo = my_package.some_module:main_func',
            'bar = other_module:some_func',
        ],
        'gui_scripts': [
            'baz = my_package_gui:start_func',
        ]
    })

'''
 Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?
'''

class Solution(object):
    def addDigits(self, num):
      pass

class Solution(object):
    def addDigits(self, num):
      if num==0:
        return 0
      return num % 9 if num % 9 !=0 else 9

    def addDigits(self, num):
      if num==0:
        return 0
      return (num - 1) % 9 + 1

    # 迭代
    def addDigits(self, num):
      return num if num < 10 else self.addDigits(reduce(lambad x,y: int(x) + int(y), list(str(num))))

'''
 Given an array of 2n integers, your task is to group these integers
 into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn)
 which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4.

Note:

    n is a positive integer, which is in the range of [1, 10000].
    All the integers in the array will be in the range of [-10000, 10000].

'''
class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        pass

class Solution(object):
def arrayPairSum(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    return sum(sorted(nums)[::2])

'''
 Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

    All letters in this word are capitals, like "USA".
    All letters in this word are not capitals, like "leetcode".
    Only the first letter in this word is capital if it has more than one letter, like "Google".

Otherwise, we define that this word doesn't use capitals in a right way.

Example 1:

Input: "USA"
Output: True

Example 2:

Input: "FlaG"
Output: False


'''

class Solution(object):
    def detectCapitalUse(self, word):
        """
        :type word: str
        :rtype: bool
        """

class Solution(object):
    def detectCapitalUse(self, word):
        """
        :type word: str
        :rtype: bool
        """
        return word.isupper() or word.istitle()

"""
Given an integer array with even length, where different
numbers in this array represent different kinds of candies.
Each number means one candy of the corresponding kind.
You need to distribute these candies equally in number to
brother and sister. Return the maximum number of kinds of
candies the sister could gain.

Example 1:
Input: candies = [1,1,2,2,3,3]
Output: 3
Explanation:
There are three different kinds of candies (1, 2 and 3),
 and two candies for each kind.
Optimal distribution: The sister has candies [1,2,3] and
the brother has candies [1,2,3], too.
The sister has three different kinds of candies.
Example 2:
Input: candies = [1,1,2,3]
Output: 2
Explanation: For example, the sister has candies [2,3] and
the brother has candies [1,1].
The sister has two different kinds of candies, the brother
has only one kind of candies.
Note:

The length of the given array is in range [2, 10,000], and
 will be even.
The number in given array is in range [-100,000, 100,000].


class Solution(object):
    def distributeCandies(self, candies):
        """
        :type candies: List[int]
        :rtype: int
        """

class Solution(object):
    def distributeCandies(self, candies):
        """
        :type candies: List[int]
        :rtype: int
        """
        return min(len(candies)//2, len(set(candies)))

'''
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
'''

class Solution(object):

    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """

'''
Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
'''
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

"""
Given a string, you need to reverse the order
of characters in each word within a sentence while
still preserving whitespace and initial word order.

Example 1:
Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Note: In the string, each word is separated by
single space and there will not be any extra space in the string.
"""


class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """

'''
Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
'''

# Definition for a binary tree node.
#class TreeNode(object):
#    def __init__(self, x, left=None, right=None):
#        self.val = x
#        self.left = left
#        self.right = right

class Solution(object):
    def sumOfLeftLeaves(self, root):
      """
      :type root: TreeNode
      :rtype: int
      """

'''
 Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal".

Example 1:

Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal".
For the left two athletes, you just need to output their relative ranks according to their scores.

Note:

    N is a positive integer and won't exceed 10,000.
    All the scores of athletes are guaranteed to be unique.

'''


class Solution(object):
    def findRelativeRanks(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """

'''
 Given an arbitrary ransom note string and another string containing letters
  from all the magazines, write a function that will return true if the ransom
  note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

'''
class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """

'''
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.
Example 1:
Input:

0 0 0
0 1 0
0 0 0
Output:
0 0 0
0 1 0
0 0 0
Example 2:
Input:

0 0 0
0 1 0
1 1 1
Output:
0 0 0
0 1 0
1 2 1
Note:
The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.

'''

class Solution(object):
    def updateMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[List[int]]
        """

'''
We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

Example 1:
Input:
bits = [1, 0, 0]
Output: True
Explanation:
The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.
Example 2:
Input:
bits = [1, 1, 1, 0]
Output: False
Explanation:
The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character.
Note:

1 <= len(bits) <= 1000.
bits[i] is always 0 or 1.
'''


class Solution(object):
    def isOneBitCharacter(self, bits):
        """
        :type bits: List[int]
        :rtype: bool
        """

Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Example 1:
Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.
Example 2:
Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:
Input: [-1, 3, 2, 0]

Output: True

Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

class Solution(object):
    def find132pattern(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """