import numpy as np
import matplotlib.pyplot as plt
from sklearn import metrics
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn.datasets import load_iris
%matplotlib inline

X,y = make_blobs(n_samples=100,n_features=2,centers=[[-1,-1],[0,0],[1,1],[2,2]],cluster_std=[0.4,0.2,0.2,0.2])#使用make_blobs生成训练数据,生成100个样本,每个样本2个特征,共4个聚类,聚类中心分别为[-1,-1],[0,0],[1,1],[2,2],聚类方差分别为0.4,0.2,0.2,0.2
plt.scatter(X[:,0],X[:,1])#画出训练样本的散点图,散点图的横坐标为样本的第一维特征,纵坐标为样本的第二维特征
plt.show()

kmeans = KMeans(n_clusters=3)#生成kmeans分类器,聚类数量为3,其余参数使用默认值。

y_pred = kmeans.fit_predict(X)#使用fit_predict方法计算聚类中心并且预测每个样本的聚类索引。

plt.scatter(X[:,0],X[:,1],c=y_pred)#画出训练样本的散点图,散点图的横坐标为样本的第一维特征,纵坐标为样本的第二维特征,将各聚类结果显示为不同的颜色
plt.show()

kmeans = KMeans(n_clusters=4)#生成kmeans分类器,聚类数量为4,其余参数使用默认值。

y_pred = kmeans.fit_predict(X)#使用fit_predict方法计算聚类中心并且预测每个样本的聚类索引。

plt.scatter(X[:,0],X[:,1],c=y_pred)#画出训练样本的散点图,散点图的横坐标为样本的第一维特征,纵坐标为样本的第二维特征,将各聚类结果显示为不同的颜色
plt.show()

iris = load_iris()     #导入iris数据集,iris数据集包含了150个样本,分别属于3类,每个样本包含4个特征
data_train=iris.data   #iris样本集的样本特征
label_train=iris.target #iris样本集的样本标签

kmeans = KMeans(n_clusters=3)#生成kmeans分类器,聚类数量为3,其余参数使用默认值。
y_predict = kmeans.fit_predict(data_train)#使用fit_predict方法计算聚类中心并且预测每个样本的聚类索引。

plt.scatter(data_train[:,0],data_train[:,2],c=y_predict)#画出训练样本的散点图,散点图的横坐标为样本的第一维特征,纵坐标为样本的第三维特征,将各聚类结果显示为不同的颜色

plt.show()

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

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root == None:
            return None
        temp = root.left
        root.left = root.right
        root.right = temp
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        if l1.val <= l2.val:
            l1.next = self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1,l2.next)
            return l2

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        # 滑动窗口大小为 n-k
        windowSize = n - k
        # 选前 n-k 个作为初始值
        s = sum(cardPoints[:windowSize])
        minSum = s
        for i in range(windowSize, n):
            # 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
            s += cardPoints[i] - cardPoints[i - windowSize]
            minSum = min(minSum, s)
        return sum(cardPoints) - minSum

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        median = lambda a: (a[(len(a)-1)//2] + a[len(a)//2]) / 2
        res = []
        for i in range(len(nums)-k+1):
            res.append(median(sorted(nums[i:i+k])))
        return res