odcowl的个人博客

1239.串联字符串的最大长度

发表于 2021-06-18 更新于 2021-06-19 分类于 LeetCode

0.0.1. 题目

给定一个字符串数组arr，字符串s是将arr某一子序列字符串连接所得的字符串，如果s中的每一个字符都只出现过一次，那么它就是一个可行解。

请返回所有可行解s中最长长度。

示例 1：

1
2
3

输入：arr = ["un","iq","ue"]
输出：4
解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。

示例 2：

1
2
3

输入：arr = ["cha","r","act","ers"]
输出：6
解释：可能的解答有 "chaers" 和 "acters"。

示例 3：

1 2	输入：arr = ["abcdefghijklmnopqrstuvwxyz"] 输出：26

提示：

1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] 中只含有小写英文字母

0.0.2. 我的解法(79/85)

很遗憾。。。

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

        if not arr:
            return 0
        if len(arr) == 1:
            return len(arr[0])

        n = len(arr)
        max_ = 0
        act = ""
        def isAppeared(str1,str2):
            if len(str1) > len(str2):
                str1, str2 = str2, str1
            for ch in str1:
                if ch in str2:
                    return True
            return False
        def isPure(str1):
            if len(str1) == len(set(str1)):
                return True
            return False

        for i in range(n):
            if isPure(arr[i]):
                max_ = max(max_,len(arr[i]))
                act = arr[i]
            for j in range(i+1,n):
                if not isAppeared(act,arr[j]) and isPure(arr[j]):
                    act = act + arr[j]
                    max_ = max(max_,len(act))
        return max_

0.0.3. 好的解法

参考:benhao

0.0.3.1. 直白质朴法

我的思路总体和这个是一致的

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        def validStr(string):
            return len(set(string)) == len(string)
        
        dp = []
        for s in arr:
            if not validStr(s):
                continue
            for s_ in dp:
                if validStr(s_ + s):
                    dp.append(s_ + s)
            dp.append(s)
        return len(max(dp,key=len)) if dp else 0

0.0.4. 0.0.5. 回溯法

NoBug

回溯算法，采用递归实现

class Solution():
    def maxLength(self, arr):

        t = []
        for s in arr:
            if len(set(s)) == len(s):
                t.append(s)
        arr = t[:]

        def dfs(i, tmp):

            if i >= len(arr):
                return len(tmp)
            else:
                if not (set(tmp) & set(arr[i])):
                    return max(dfs(i+1,tmp+arr[i]),dfs(i+1,tmp))
                else:
                    return dfs(i + 1, tmp)

        l=dfs(0,'')
        return l

转载:音频处理基本概念

发表于 2021-06-08 分类于信号处理

转载自：
音频基础知识

音频前处理基本概念

0.0.1. 音频基础知识

声音信号通常是一种连续的波形来表示。波形的最大位移称为振幅A，反应音量。波形中两个连续波峰（或波谷）之间的距离称为周期T。周期的倒数即为频率f，以赫兹（Hz）为单位。频率反应了声音的音调。

声音可按频率分为三类：

次声波：频率低于20Hz。
音频；频率在20-20kHz。
超声：频率高于20kHz。

音频（Audio）指频率在20Hz-20kHz范围内的可听声音，是多媒体信息中的一种媒体类型 - 可听类媒体。

目前多媒体计算机中的音频主要由波形音频、CD音频和MIDE音乐3种形式。重点应该是波形音频。

波形音频

波形音频是由外部声音源通过数字化过程采集到多媒体计算机的所有声音形式。语音是波形声音中人说话的声音，具有内在的语言学、语音学的内涵。多媒体计算机可以利用特殊的方法分析、研究、抽取语音的相关特征，实现对不同语音的分辨、识别以及通过文字合成语音波形等。

CD音频

CD音频（CD-Audio）是存储在音乐CD光盘中的数字音频，可以通过CD-ROM驱动器读取并采集到多媒体计算机系统中，并以波形音频的相应形式存储和处理。

MIDI音频

MIDI音频（musical instrument digital interface），它将音乐符号化并保存在MIDI文件中，通过因为合成器产生相应的声音波形来还原播放。

音频是时间的函数，具有很强的前后相关性，所以实时性是音频处理的基本要求。

0.0.2. 音频的数字化

计算机处理音频信号前，必须将模拟的声音信号数字化，产生数字音频。具体过程包括采样、量化与编码。

采样与采样频率

采样就是每间隔一段时间读取一次声音信号幅度，使声音信号在时间上被离散化。

采样频率就是将模拟声音波形数字化时，每秒钟抽取声波幅度样本的次数，其计算单位是kHz（千赫兹）。一般来说，采样频率越高，声音失真越小，用于存储的数字音频的数据量也越大。

乃奎斯特(Nyquist)采样理论：采样频率不应低于声音信号最高频率的两倍。这样就能把以数字表达的声音还原成原来的声音。例如：电话话音的信号频率约为 3.4 kHz，采样频率一般选用 8 kHz。

音频抽样率有：8kHz、11.025kHz、22.05kHz、16kHz、37.8kHz、44.1kHz、48kHz。

量化与量化位数

量化就是把采样得到的信号幅度转化为数字值，是声音信号在幅度上被离散化。量化位数（位深）是每个采样点能够表示的数据范围，常用的有8位、12位和16位。图示一个：

声道

反映音频数字化质量的另一个因素是声道个数。记录音频时，如果每次生成一个声波的数据，称为单声道；每次记录两个声波数据，称为双声道（立体声）；每次生成二个以上的声波数据，称为多声道（环绕立体声）。

音频采样的数据量

数字音频的采样数据量主要取决两方面的因素：

音质因素：采样频率、量化位数和声道数三个参数决定。
时间：采样时间长短。

0.0.3. 音频的编码

音频数据压缩编码的方法有多种，可分为无损压缩和有损压缩两大类。无损压缩主要包含各种熵编码；有损压缩则分为波形编码、参数编码、感知编码和混合编码。

波形编码：模拟音频数字化（抽样和量化）的过程中，根据人耳的听觉特性进行编码，并使编码后的音频信号与原始信号的波形尽可能匹配，实现数据压缩。

PCM (Pulse Code Modulation)、脉冲编码调制。
DPCM (Differential Pulse Code Modulation)。
APCM (Adaptive Pulse Code Modulation)。
ADPCM (Adaptive Differential Pulse Code Modulation)。
参数编码：把音频信号表示成模型的输出，利用特征的方法抽取必要的模型参数和激励信号的信息，且对这些信息编码，最后在输出端合成原始信号。

0.0.4. 音频采集

音频采集播放流程：采集-前处理（回声消除、噪声抑制、音量调节、混响处理等）-编码-传输-解码-后处理-播放

采样率：原始PCM数据每秒采样次数

比特率：编码压缩后的码率，每秒音频的大小。（所以在编码效果好的情况下也会有高采样率对应相对低的比特率）

PCM(Pulse Code Modulation)，脉冲编码调制。人耳听到的是模拟信号，PCM是把声音从模拟信号转化为数字信号的技术。原理是用一个固定的频率对模拟信号进行采样，采样后的信号在波形上看就像一串连续的幅值不一的脉冲(脉搏似的短暂起伏的电冲击)，把这些脉冲的幅值按一定精度进行量化，这些量化后的数值被连续的输出、传输、处理或记录到存储介质中，所有这些组成了数字音频的产生过程(抽样、量化、编码三个过程)。

0.0.5. 音频前、后处理

ES: Echo Suppresion

EES: Enhanced Echo Suppresion

AEC: Acoustic Echo Cancellation 声学回声消除。在一般的VOIP软件或视频会议系统中，假设我们只有A和B两个人在通话，首先，A的声音传给B，B然后用喇叭放出来，而这时B的MIC呢则会采集到喇叭放出来的声音，然后传回给A，如果这个传输的过程中时延足够大，A就会听到一个和自己刚才说过的话一样的声音，这就是回声，声学回声消除器的作用就是在B端对B采集到的声音进行处理，把采集到声音包含的A的声音去掉再传给A，这样，A就不会听到自己说过的话了。就是说，在B端，接收到A说的话以后，要把这些话音数据传给回声消除器做参考，然后再传给声卡，声卡再放出来，这有一段延时，这时，B再采集，然后传给回声消除器，与那个参考数据比较，从采集到的数据中把频域和参考数据相同的部分消除掉。

NS: Noise Suppression 噪音抑制

NLP: Nonlinear Procession 去除残留的回声和背景噪声

NC: Noise Control

NR: Noise Reduction 降噪

CC: Clarity Control 清晰度控制

VAD: Voice Activity Detection 静音检测。静音检测（VAD）将检测被编码的音频数据是语音还是静音或背景噪声

DRC: Dynamic Range Control

AGC: Automatic Gain Control 自动增益控制。不同的设备，录音效果会有较大幅度的变动，自动增益控制（AGC）就是用来处理这种现象的。它提供了一种调整信号为参考音量的方法。这对VOIP（voice over IP）是非常有用的，因为它不需要再手动去调整麦克风增益。第二个好处是，将麦克风增益设置为保守(低)级别，可有效避免削波。

VBR: Variable Bit-Rate

CBR: Constant Bit-Rate

ABR: Average bit-rate

DTX: Discontinuous Transmission 非连续传输。非连续性传输（DTX）是静音检测（VAD）/变比特率（VBR）操作的额外选项，它能够在背景噪声固定时，完全的停止传输。

CNG: Comfort Noise Generator 舒适噪音生成。在非变比特率的情况下，检测非语音周期并对用足够的比特数重新生成的背景噪声进行编码。这个叫“舒适噪声生成（CNG）”。

音频加速器（Audio Accelerator）：即音频处理单元，有些厂家又叫APU(Audio Processing Unit)，好比计算机机的cpu，决定着声卡的音频处理能力。完全意义上的音频加速器由DSP(Digital Singnal Processor)和I/O控制器构成。I/O控制器即是输入/输出控制器，针对声卡的输入/输出进行控制。如果说一块声卡没有DSP，而只是一块I/O卡（比如绝大多数主板上自带的AC97声卡）那它所有的数据处理就只有交由CPU来完成。这将意味着增加CPU的负担，和低下的性能。

Codec：Codec一词由Coder和Decoder两个英文词组合而成，表示为多媒体数字信号解码器，专门负责模拟信号到数字信号的转换（ADC）以及数字信号到模拟信号的转换（DAC）工作。计算机声卡处理的信号全是数字信号，而声卡接收到的或者最终输出的信号大部份是模拟信号。从外办输入的信号，如CD、话筒等必须经过a/d转换后才能由声卡进行处理，然后又经过d/a转换后最终送入杨声器，被我们的耳朵所听到。因此Codec的质量直接决定着进出声卡的信号质量。

声卡的工作流程：MIDI、数字输入、模拟输入等信号—>通各种接口输入—>由晶震产生采样频率给Codec进行模/数转换—>交给DSP+I/O器进行信号处理和分配—>再由DAC或Codec进行数/模转换—>最后由放大电路放大—>输出至模拟输出接口

AC97（Audio Codec 97）：一种规范。

Amplitude（增益/衰减）:对于一个音频信号进行放大（正增益），或者衰减（负增益），是DSP一个最基本的功能。而这些操作实质上就是对电流脉冲的增强和减小。在电路中，可以通过电阻实现这项功能。

Filter（滤波器）：滤波器也是DSP的基础功能，所谓滤波器，就是过滤掉符合特定条件的声音，比如常见的频率滤波器。常见的频率滤波器包括低通滤波器（Low pass filter），高通滤波器(High pass filter)，带通滤波器(band pass filter)等。他们都是用来过滤掉特定的频率，比如低通滤波器。
低通滤波器，顾名思义就是让低频信号通过，而其他信号则被过滤掉，一般音响系统中习惯使用低通滤波器分离出单独的超重低音通道来，从而组成X.1系统。
高通滤波器，就是允许高频信号通过，而将其他信号拒之门外。
带通滤波器比较有意思，它会让需要的频段顺利通过，而阻止不需要的频段。
陷波滤波器（band reject filter）像一个倒置的带通滤波器，它会阻止需要的频段，而让不需要的频段顺利通过。
滤波器对于DSP的重要意义在于能够分离出不同的频段，从而进行相关的操作。

震荡器：是一个产生波形的设备，它能够发出规则的或者循环的正弦波、方波、三角波和锯齿波。而这些波形拥有不同的用途，比如正弦波可以当作激励来使用。因此在音频数据中添加不同种类的波，就可以制造出各种绚丽的效果来，比如镶边等。

Delay（延时）：所谓的延时，就是沿着时间轴移动音频数据，从而使得声音听起来要延后一些，在DSP中实现这项功能也是非常简单的。

ADSR（音色包络）：震荡器产生波形后，如果不加以控制，则这些波形将会一直震荡下去，这当然不是我们需要的。因此，我们需要给波形加上起止的控制，这就是ADSR包络了。A代表Attack，指的是声音从开始发声到最大振幅的过程；D代表Decay，指的是声音从最大振幅开始衰减的一段；S指的是Sustain，指的是声音衰减到一定位置维持住的过程；R代表Release，指的是停止发声后到声音消失的过程。有了ADSR，我们就能够控制一个波形的起止位置，从而实现我们想要的效果。

Gate门限：Gate应该算是计算机算法中的逻辑术语了。所谓门，就是按照一定的条件处理数据，符合条件的在门的一边，不符合条件的在门的另一边。门在DSP中主要用作按照条件对音频数据进行分离。

EQ：被称为均衡(Equalizer)，是DSP必备的高档功能之一。EQ基本作用是通过对声音某一个或多个频段进行增益或衰减，达到调整音色的目的。当然，EQ还有一个显著的功能，降噪。因此对于声音的整体音色有着很大的影响。
EQ通过将声音中各频率的组成泛音等级加以修改，专为某一类音乐进行优化，增强人们的感觉。常见包括：正常、摇滚、流行、舞曲、古典、柔和、爵士、金属、重低音和自定义。
EQ通常包括如下参数：F(requency)，频率――这是用于设定你要进行调整的频率点用的参数；G(ain)，增益――用于调整在你设定好的F值上进行增益或衰减的参数；Q(uantize)――用于设定你要进行增益或衰减的频段“宽度”。要注意的一点是：当你设定的Q值越小的时候，你所处理的频段就越宽，而当你设定的Q值越大的时候，你所处理的频段就越窄。
从控制的方式来说，EQ有图形EQ和参量EQ两种。

SRC：就是Sample Rate Convertor采样频率转换器，intel AC’97规范约定了声卡需要经过这样一个处理过程，即将所有信号重新转换成一个统一的采样率输出。SRC如果进行了非整数倍的转换的话，比如44100->48000，会有较大的噪声或者谐波出现，这些噪声因转换器的质量高低、算法好坏而定，不优秀的算法会比较严重的影响听感。既然SRC是一个可能破坏音质的过程，为什么会有这么一个产物呢？前面就说过，AC’97是为了节省成本而订，SRC的结果可以为声卡省下一颗Crystal。SRC一般都通过软件运算转换，这样受驱动版本的影响非常之大，例如Live!系列，SRC品质最好的是Windows Server2003 自带的驱动，也有使用硬件SRC的，例如：CS4630音频加速器。硬件SRC的品质往往大大优于软件的SRC，SRC品质的好坏的重要性甚至比Codec的档次更重要。

Crystal：中文名就是石英晶体振荡器或者简称晶振。常见的声卡都支持44.1kHz和48kHz的信号输入。

0.0.6. 混音技术介绍

混音，顾名思义，就是把两路或者多路音频流混合在一起，形成一路音频流。而混流，则是指音视频流的混合，也就是视频画面和声音的对齐，也称混流。

并非任何两路音频流都可以直接混合。两路音视频流，必须符合以下条件才能混合：

格式相同，要解压成 PCM 格式。
采样率相同，要转换成相同的采样率。主流采样率包括：16k Hz、32k Hz、44.1k Hz 和 48k Hz。
帧长相同，帧长由编码格式决定，PCM 没有帧长的概念，开发者自行决定帧长。为了和主流音频编码格式的帧长保持一致，推荐采用 20ms 为帧长。
位深（Bit-Depth）或采样格式 (Sample Format) 相同，承载每个采样点数据的 bit 数目要相同。
声道数相同，必须同样是单声道或者双声道 (立体声)。这样，把格式、采样率、帧长、位深和声道数对齐了以后，两个音频流就可以混合了。

在混音之前，还需要做回声消除、噪音抑制和静音检测等处理。回声消除和噪音抑制属于语音前处理范畴的工作。在编码之前，采集、语音前处理、混音之前的处理、混音和混音之后的处理应该按顺序进行。静音抑制（VAD，Voice Activity Detect）可做可不做。对于终端混音，是要把采集到的主播声音和从音频文件中读到的伴奏声音混合。如果主播停顿一段时间不发出声音，通过 VAD 检测到了，那么这段时间不混音，直接采用伴奏音乐的数据就好了。然而，为了简单起见，也可以不做 VAD。主播不发声音的期间，继续做混音也可以（主播的声音为零振幅）

0.0.7. 音频重采样

音频系统中可能存在多个音轨，而每个音轨的原始采样率可能是不一致的。比如在播放音乐的过程中，来了一个提示音，就需要把音乐和提示音都混合到codec输出，音乐的原始采样率和提示音的原始采样率可能是不一致的。问题来了，如果codec的采样率设置为音乐的原始采样率的话，那么提示音就会失真。因此最简单见效的解决方法是：codec的采样率固定一个值（44.1KHz/48KHz），所有音轨都重采样到这个采样率，然后才送到codec，保证所有音轨听起来都不失真。

重采样即是将音频进行重新采样得到新的采样率的音频。

0.0.8. 音频3A处理

音频3A处理在不同的应用场景三者的处理顺序也不同，如在WebRTC中音频数据回依次经过AEC和NS（noise suppression）或者 NS 与AECM（AECM 是WebRTC专门为移动端打造的算法，计算量低，而AEC 是为PC打造的）。而在AEC(回声消除算法)，为什么需要这个算法呢？当一个设备在播放声音经过空间中的多次反射会被麦克风再次捕捉并采集到系统当中，这时音频的输入既有空间反射的回声也有本端说话声，如果缺少此模块就意味着通话中说话人一直可以听到自己的声音回来，这是非常差的一种体验，这当然是需要我们避免的。这里AEC的作用就是通过播放的参考信号跟踪出回声并从采集信号中把回声消除掉，随后再经过降噪处理去除噪声。而其中的AECM是在NS模块之后通过获取clean与noise数据进行分析，AEC则是NS模块之前直接获取noise数据进行分析。

音频数据完成AEC与NS的处理后会进行AGC处理，其包括AAGC（模拟域的自动增益控制）与DAGC（数字域的自动增益控制）。其中AAGC的主要作用是通过系统的采集音量设置接口调整输入信号（大多用于PC端，移动端一般没有输入音量的系统接口），如借助Windows上的的API调整采集音量等参数。AAGC可为输入的音频数据带来明显的质量优化，如提高信噪比，避免输入信号溢出等。但由于我们服务的跨平台要求，我们需要构建一个面向多平台设备的框架，在不同的输入平台和设备都会有不同的输入音量，DAGC可以根据对输入信号的跟踪，尽量的调整信号到达期望大小(幅值或能量)，从而避免不同设备采集带来的音量差异过大。完成AGC处理的音频数据，即可进入Audio Encode进行编码操作。

读书笔记白夜行by东野圭吾

发表于 2021-05-27 分类于 2021读书笔记

继续读闲书…

上次读完湖泊后，对日本悬疑类小说名家东野圭吾的作品继续产生兴趣，于是就读了这本《白夜行》。

先说结尾，我还是不太习惯于戛然而止式的结尾😅总觉得坏人应该得到无论是法律上还是心灵上的惩罚，好人应该有好的结局。

亮跳下去后背过身的雪穗是真的有失控吗？

R&Y的未来如何？

警官是否心满意足的找到了真正的罪犯？

也有可能这大片的留白是作者留下的想象空间，只可惜我这种凡人想象不到罢了。

故事开始于大人的罪恶，小孩子无法选择的命运。

恶之花在废弃的大楼里流着泪生长，压抑又复杂的小孩子间惺惺相惜、共生的情感，最终造就了所有阳光下的罪恶。

我的天空里没有太阳，总是黑夜，但并不暗，因为有东西代替了太阳。虽然没有太阳那么明亮，但对我来说已经足够。凭借着这份光，我便能把黑夜当成白天。我从来就没有太阳，所以不怕失去。

我觉得亮心里有一丝愧疚，他认为是自己的责任要去守护雪穗。

这是一种复杂的情感。自己的父亲是变态，自己喜爱的女生惨遭毒手。所以他要成为代替太阳的守护者，他要保护心里的花朵，即便这朵花早已变质。

只希望能手牵手在太阳下散步

对于我来说，这早就不是雪穗的想法。

一个人越来越靠近阳光，一个人只能向蝼蚁般藏匿地下。

美佳差点惊呼失声，雪穗伸出食指抵住她的唇。

“那时，我比现在的你更小，真的还是孩子。但是，恶魔不会因为你是孩子就放过你。而且，恶魔还不止一个。”

“不……”美佳喃喃地说，却发不出声音。

“现在的你，就是那时的我。”雪穗压在美佳身上，双手抱住美佳的头，“真可怜。 »

应该是全文里我看的最有生理性反感的部分吧。

因为曾经见过黑暗，所以要把所有美好的人脱向黑暗。

所有和雪穗有关系的人最后都没有落得好的结局，而这些人都很善良。

雪穗像人偶般面无表情。她冰冷地回答：“我不知道。雇用临时工都由店长全权负责。

最终亮带着那把杀死父亲的小剪刀，一跃而下。

在大阪店的开业典礼上，所有的纸醉金迷，截然而止。

我不由地问，笹垣真的可以捉拿雪穗吗？

为什么要给这样子的人留下一条生路了？这大概是我还没有读懂作者的一点。

打算停下来阅读悬疑类别的小说，准备准备刷题啦❤️

想要自救

读书笔记湖泊by东野圭吾

发表于 2021-05-23 更新于 2021-05-24 分类于 2021读书笔记

尸体要在湖底消失需要好几年，不，大概要花好几十年吧。这中间我们肯定都会提心吊胆的。就算尸体不见了，我们的灵魂也无法离开这湖畔吧。

很搞笑的一件事是，我是从凌晨2点开始阅读这本书的，在5点前阅读完，期间伴随着窗对面法国年轻人soirée的欢呼声和音乐声。这一帮聚会的人，平时我肯定辗转难眠骂骂咧咧，这次却让我没有在读书的时候背脊发凉…

早就听闻东野圭吾的小说很精彩，这次果然感受到了其小说的魅力！

诸多的犯罪和真相细节在专业的文评里可以找到，博客里我只想简单记录每次阅读后的感悟和心情。

尸体要在湖底消失需要好几年，不，大概要花好几十年吧。这中间我们肯定都会提心吊胆的。就算尸体不见了，我们的灵魂也无法离开这湖畔吧。

小时候不懂得谎言的代价，用谎言换取奖励，用谎言逃避责罚。谎言的层次感也是长大后才明白，何为善意的谎言，何为恶意的谎言。

但每当不真诚的话说出口，总会担心着需要怎么把谎言说的更真，更让听者信服，不知不觉的又加重了语言上的负担感。久而久之，宁愿不去编造所谓的善意谎言，也不想说出不真诚的话。

一个谎言需要千千万万个谎言来圆谎。

你是说有的母亲为了招待老师，不惜牺牲自己的肉体吗？

读到这里心中最是沉重。千千万万的亚洲家长们（大部分的情况），为了孩子的学业，没有自己的生活，一掷千金还算好的，需要出卖自己的灵魂去谄媚，甚至出卖自己的肉体。

但我一直觉得很奇怪的是，真的会有人如此“饥渴”？

总而言之，坐在某种握着某种权利的位置上，再处于某种社会环境中，人就会变。

可怜天下父母心。

“嗯，回去的时候，你会跟我和妈妈一起吧？不是各走各路的吧？“ 章太。

孩子的内心需要保护，看起来再冷漠顽固的小孩子，心里的渴望或许就那么简单。

每个人心里都有那个自己认为的凶手，作者也似乎刻意给每个小孩子安排了合适的动机。悬疑未解，但已经不重要了。

父母的结合究竟对孩子有那么重要吗？其实我觉得并不是。父母如果能做到互相关心、爱护，那一定是最完美的家庭，但假如不呢？

我认为最重要的是父母之间的互相尊重，而不是单独在孩子面前指责不在场的另一半。

对于孩子来说，从小就要面临站哪一边的选择。

在俊介来到别墅前，美菜子跟所有人吐槽俊介的行为，章太也是看在眼里吧。即便不是血亲，父亲依然是章太的心里另一半天，作为母亲不应该试图把这一片天抹黑。

与其互相的指责，不如坐下来心平气和的告诉孩子：我们的爱情或许结束了，但我们还可以拥有亲情。

小孩子根本不懂得爱的差别，只有大人才斤斤计较。

——————

接下来还想阅读东野圭吾的其他作品。

2021.05.23

1035.不相交的线(Medium)

发表于 2021-05-21 更新于 2021-05-22 分类于 LeetCode

LeetCodee每日一题(2021.05.21)之不相交的线
难度：中等

0.0.1. 题目

在两条独立的水平线上按给定的顺序写下nums1和nums2中的整数。

现在，可以绘制一些连接两个数字nums1[i]和nums2[j]的直线，这些直线需要同时满足满足：

nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

示例1

输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

示例2

1 2	输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2] 输出：3

示例3

1 2	输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1] 输出：2

提示：

1 <= nums1.length <= 500
1 <= nums2.length <= 500
1 <= nums1[i], nums2[i] <= 2000

0.0.2. 暂时错误的思路

一开始看到这道题，我想到的是数学中如何验证平面上两条线段是否相交，也就是讲问题转化成了：给定两个线段的坐标（也就是四个点的直角坐标系坐标），判断这两个线段是否相交。

假定输入p1,p2,q1,q2四个点的坐标，p1p2为一条线段,q1q2为另外一条线段。

两条线段相交只有两种情况：

其中一条线段的某一端点在另一条线段上
两条线段成X型

详细的解题过程见：参考

实际上没有用上的代码部分:

def judge(a,b,c,d):
            if min(a[0],b[0])<=max(c[0],d[0]) and min(c[1],d[1])<=max(a[1],b[1]) and min(c[0],d[0])<=max(a[0],b[0]) and min(a[1],b[1])<=max(c[1],d[1]):
                print("True")
            else:
                print("False")

0.0.3. 解题思路

这道题LC解题思路里给出的基本为动态规划的解法，也是我算法里最差的一部分。

定义

dp[i][j]表示数组nums1的前i个数字和数组nums2的前j个数字能形成的不相交的线的最大数。（大问题化小问题）
其中m为nums1长度，n为nums2长度

重点：状态转移方程

对于任意 0 < j < m, 0 < j < n, 当nums1[i]和nums2[j]`数字相同的时候：
- 当前最大连线数又可以增加一条，用dp[i-1][j-1]+1表示
如果数字不相同，可以从nums1或nums2去掉一个数字进行比较
- 比如比较 dp[i-1][j]dp[i−1][j] 和 dp[i][j-1]dp[i][j−1], 取两者中的较大值来更新 dp[i][j]dp[i][j] 即可.
- dp[i-1][j]dp[i−1][j] 代表不考虑 nums[i]nums[i] 字符, nums[j]nums[j] 是考虑的, 但不是必须包含. dp[i][j-1]dp[i][j−1] 同理
最后，遍历完成后，结果在dp[m][n]上

实现代码：

class Solution(object):
    def maxUncrossedLines(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """

        m, n = len(nums1),len(nums2)

        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)
        
        return dp[m][n]

赤小豆

692.前K个高频单词(Medium)

发表于 2021-05-21 更新于 2021-05-22 分类于 LeetCode

LeetCode每日一题(2021.05.20)之前k个高频单词
难度: 中等

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例1：

输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

示例2:

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。

注意：

假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。
输入的单词均由小写字母组成。

0.0.1. 解析

利用双字典排列：

第一次排列：自带工具collections.Counter计算给出列表words里每一个单词的出现顺序
第二次排列：按照词频（从大到小）和单词顺序（从小到大）的方式排序，利用lambda

class Solution(object):
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        #双排列

        dic = collections.Counter(words)  #计算词频
        res = sorted(dic,key = lambda word:(-dic[word],word)) #词频倒序，字母正序
        
        return res[:k]

我的读书笔记-非暴力沟通

发表于 2021-05-18 更新于 2021-05-19 分类于 2021读书笔记

一些摘录:

非暴力沟通的过程

什么是我的观察

我的感受如何

那些需要（或价值、愿望等）导致那样的感受

为了改善，我的具体请求

举个例子，一个母亲可能对她处于青春期的儿子说：”菲利克斯，看到咖啡桌下的两> 只脏袜子和电视机旁的第三只，我不太高兴，因为我看重整洁，你是否愿意将袜子拿到房间或放进洗衣机？“

语言使我们陷入是非之中。它擅长将人分类，把人看做好人或坏人，正常或不正常，负责人或不负责任，聪明或愚蠢，等等。

有一些语言是”貌似客观”的，对他人的评价反应的是我们主观的需要和价值观。

我们不要将价值判断与道德评判混为一谈。什么是可贵的品质，我们每个人都有自己的看法。

不带评论的观察是人类智力的最高形式。——印度哲学家克里希那穆提

如果我们的表达言过其实，别人就可能产生逆反心理，而不愿作出友善的回应。

听到不中听的话时

听到不中听的话时，我们有四种选择：

第一种是认为自己犯了错。这会导致我们内疚、惭愧，甚至厌恶自己

第二种是指责对方

第三种是了解我们内心的感受和需要

第四种是用心体会他人的感受和需要

如果我们想利用他人的内疚，我们通常采取的方法是把自己不愉快的感觉归咎于对方。

批评往往暗含着期待。对他人的批评实际上间接表达了我们尚未满足的需要。

如果我们通过批评来提出主张，人们的反应常常是申辩或反击。反之，如果我们直接说出需要，其他人就较有可能作出积极的回应。

女性的角色

对于妇女来说，社会文化并不鼓励我们表达个人需要。一旦把照顾他人当作最高职责，她们也就会倾向于忽视个人的需要。
在社会文化的影响下，许多妇女在表达请求时感到别扭，好像做错了什么。例如，她可能不会说：“我今天累坏了，晚上想休息。”相反，她的话听起来也许就像是辩护词：“你知道我一整天都没歇过，我熨了所有的衬衣，把这周的脏衣服都洗了，准备了午餐和晚餐，还出去买了东西…你是否可以…?“

如果我们不看重自己的需要，别人可能也不会。

提出具体的请求