发表于 | 分类于 ， ，

本篇博客仅作为学习,如有侵权必删。

详解机器学习中的熵、条件熵、相对熵、交叉熵

1. 信息量：

一个事件发生的概率越小，信息量越大，所以信息量应该为概率的减函数，对于相互独立的两个事有p(xy)=p(x)p(y)，对于这两个事件信息量应满足h(xy)=h(x)+h(y)，那么信息量应为对数函数：

​ h(x) = -ln p(x)

​ 对于一个随机变量可以以不同的概率发生，那么通过信息量期望的方式衡量，即信息熵。

2. 熵

熵：信息不确定性度量（信息量与不确定性相关）。事件发生的概率越小则携带的信息越大。

​ 一个离散随机变量X的可能取值为X=x1,x2,…,xn，而对应的概率为pi=p(X=xi),则随机变量的熵定义为：

​ 每个xi表示一种特征。 H(X)在每个p(xi) = 1/N是最大，N为信息的个数。在概率为1/N时信息是最不确定的。

​ 规定当p(xi)=0时，p(xi)log⁡(p(xi)=0

【小思考：为何公式是这样子的？其实只需熵和概率P成反比，1/P , 但是有个量纲缺点：地震发生的概率很小（P = 1/百万)，则信息量为一百万。抛硬币概率1/2，则信息量为2。两者量纲差太大，取log之后，使得低范围的值稍微放大，高范围的值稍微放小。】

3. 联合熵H(p,q)

两个随机变量的p与q的联合分布形成的熵称为联合熵，记为H(p, q)。

4. 条件熵H(q|p)

X给定的条件下，Y的信息熵，即H (Y |X )。公式为：

推导过程：

5. KL散度（相对熵）：

交叉熵：两个概率分布之间的一个比较，如果两个分布越匹配，交叉熵就越低；如果两个概率分布完全比配，那么交叉熵就为 0。

如果是两个随机变量P,Q，且其概率分布分别为p(x),q(x),则p相对q的相对熵为：

6. 几种熵之间的关系：

发表于 | 分类于 ，

本篇博客仅作为学习,如有侵权必删。

Mysql

1. 相关概念：

  • sql语句必须以分号结尾
  • 数据库：文件夹。
  • 表：文件夹里的文件。
  • 记录：文件中的一行行数据。

2. 数据库

1
2
3
4
5
6
7
8
9
10
11
12
13
'''基于库的增删改查'''
1.创建库
	create database 库名;
2.查看库
	show databases;  查看所有的库名称
 	show create database 库名;  查看指定库信息
 	select database(); 查看当前使用的数据库
3.编辑库
	alter database 库名 charset='utf8';
4.删除库
	drop database 库名;
5.查看数据库使用端口
	show variables like 'port';

3. 表

（1)构成

  • 字段：事物的所有属性
  • 列：事物的某一个属性的集合
  • 记录：行
  • 主键：区分表里的每一条数据行。唯一标识。
  • NULL值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
操作表之前需要先确定库
	create database db1;
切换操作库
	use db1;
	
1.创建表
	create table 表名(字段名 字段类型,字段名 字段类型);
2.查看表
	show tables;  查看库下所有的表名称
	show create table 表名;  查看指定表信息
    show create table <表名\G> (加上\G，有较高的易读性)
	describe 表名;  查看表结构
	desc 表名;
 	ps:如果想跨库操作其他表 只需要在表名前加库名即可
        desc mysql.user;
3.编辑表
	alter table 表名 rename 新表名;
4.删除表
	drop table 表名;

4. 记录

（1）数据类型

  • 定长字符串：CHAR(n)，n为最多保存字符数量。如果字符长度是10，而输入的数据只有5位，则用5位空格填充。
  • 变长字符串：VARCHAR(n)， n为最多字符数量
  • 大对象类型：TEXT，大VARCHAR字段，可用于存储大字符集，如JHTML输入。
  • 数值类型：NUMERIC，通用的数值类型
  • 小数类型：DECIMAL(p,s)，p表示数值总位数，s表示小数点后位数。DECIMAL（4，2）:12.449存为12.45。
  • 整数：
  • 浮点数：FLOAT，总位数和小数点位数都可变。
  • 日期和时间：DATE、TIME、DATETIME（YEAR、MONTH、DAY、HOUR、MINUTE、SECOND）、TIMESTAMP
  • 直义字符串：？？？
  • NULL
  • 布尔值：TRUE、FALSE、NULL
  • 自定义类型：采用语句创建类型。create type PERSON AS OBJECT（NAME VARCHAR（30））
  • 域：有效数据类型的集合。create domain MONEY_D AS NUMBER(8,2) ？？？
1
2
3
4
5
6
7
8
9
10
'''基于记录的增删改查'''
1.插入数据
	insert into 表名 values(数据值1,数据值2);
2.查询数据
	select * from 表名;  		查询表中所有的数据
3.编辑数据
	update 表名 set 字段名=新数据 where 筛选条件;
4.删除数据
	delete from 表名;
	delete from 表名 where id=2;

发表于 | 分类于 ，

本篇博客仅作为学习,如有侵权必删。

https://blog.csdn.net/weixin_48534929/article/details/123404348

DBMTL模型

1. 简单总结：

阿里19年提出的一个多任务模型，该模型显示地建模目标间的贝叶斯网络因果关系。

2. 背景：

目前单任务（如CTR）不能满足工业界推荐算法的需求，还需关注后续的转化链路，如：是否评论、收藏、加购、购买、观看时长等。

常见的多目标转化模型结构：

img

  1. 底层共享参数
  2. 各塔学习自己的目标
  3. 此类网络的概率模型：

img

其中l,m为目标，x为样本特征，H是模型。（各目标独立假设）

3. DBMTL介绍

img

DBMTL与传统MTL结构（认为各目标独立）最主要差别在于构建了目标节点之间的贝叶斯网络，显式建模了目标间可能存在的因果关系。

img

DBMTL模型结构：

img

贝叶斯层对应的损失函数是：

img

不同目标加权后：

img

在网络的贝叶斯层中，函数f1, f2, f3 被实现为全连接的MLP，以学习目标间的隐含因果关系。他们把函数输入变量的embedding级联作为输入，并输入一个表示函数输出变量的embedding。每一个目标的embedding最后再经过一层MLP以输出最终目标的概率。

发表于 | 分类于 ，

一、题目

1. 给定一个整型矩阵，按照转圈方式打印。

例如

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

打印结果：1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10

要求：

额外空间复杂度为O(1)

思路：

时间复杂度：O(mn)

空间复杂度：O（1）

设置左上角坐标 (lu1,lu2), 右下角坐标 (rd1,rd2), 4个变量。

停止条件：直到左上角坐标在右下角坐标的右下方。

(第一次：lu1=0,lu2=0—rd1=3,rd2=3)，

———左上角坐标都+1, 右下角坐标都 -1.

（第二次：lu1 = 1, lu2 = 1, rd1 = 2, rd2 = 2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 方法一：
def eachPrint(lu1, lu2, rd1, rd2, matrix, res):
    """
    :param lu1: 左上角横坐标
    :param lu2: 左上角纵坐标
    :param rd1: 右下角横坐标
    :param rd2: 右下角纵坐标
    :param matrix: 矩阵
    :return: 返回每次打印结果
    """
    # 边界条件：
    if lu1 == rd1:
        for i in range(lu2, rd2 + 1):
            res.append(matrix[lu1][i])
    elif lu2 == rd2:
        for i in range(lu1, rd1 + 1):
            res.append(matrix[i][lu2])
    else:
        curl1 , curl2 = lu1, lu2
        while curl2 != rd2:
            res.append(matrix[lu1][curl2])
            curl2 += 1
        while curl1 != rd1:
            res.append(matrix[curl1][rd2])
            curl1 += 1
        while curl2 != lu2:
            res.append(matrix[rd1][curl2])
            curl2 -= 1
        while curl1 != lu1:
            res.append(matrix[curl1][lu2])
            curl1 -= 1


def printAll(matrix):
    if len(matrix) <= 0 or len(matrix[0]) <= 0:
        return
    lu1, lu2, rd1, rd2 = 0, 0, len(matrix) - 1, len(matrix[0]) - 1
    res = []
    while lu1 <= rd1 and lu2 <= rd2:
        eachPrint(lu1, lu2, rd1, rd2, matrix, res)
        lu1 += 1
        lu2 += 1
        rd1 -= 1
        rd2 -= 1
    return res

matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
print(printAll(matrix))

思路二：

时间复杂度：O(mn)

空间复杂度：O(1)

将已经走过的地方置0，在拐弯时取模判断下是否已经走过，走过则转变方向。

1
2
3
4
5
6
7
8
9
10
11
12
# 方法二：
def printMatrix2(matrix):
    r, i, j , di, dj = [], 0, 0, 0, 1
    if matrix != []:
        for _ in range(len(matrix) * len(matrix[0])):
            r.append(matrix[i][j])
            matrix[i][j] = 0
            if matrix[(i + di) % len(matrix)][(j + dj) % len(matrix[0])] == 0:
                di, dj = dj, -di
            i += di
            j += dj
    return r

1、题目118:杨辉三角（1）

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

img

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:

输入: numRows = 1
输出: [[1]]

提示:

1 <= numRows <= 30

思路：

  1. 直接暴力

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
# 1. 暴力
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 1:
            return [[1]]
        res = []
        for i in range(numRows):
            row = [1] * (i + 1)
            if i > 1:
                for j in range(1, i):
                    row[j] = (res[i-1][j-1] + res[i-1][j])
            res.append(row)
        return res

2.题目189: 旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

1
2
3
4
5
6
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

1
2
3
4
5
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明
  尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
  要求使用空间复杂度为 O(1) 的 原地 算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
	public void rotate(int[] nums, int k)
    {
        k %= nums.length;
        reverse(nums,0,nums.length - 1);
        reverse(nums,0,k - 1);
        reverse(k,nums.length - 1);
    }
	public static void reverse(int[] nums, int start, int end)
    {
        while (start < end){
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }      
    }
}

发表于 | 分类于 ，

（以下内容是参考加上自己的理解，存在不对之处麻烦指出~)

一、存在的意义：

将现实生活的事物用计算机来识别并可以进行相应的处理。

例子：现实生活的红色，人眼能直接判断，但计算机表示会转为RGB向量。若对颜色进行转换，加深或改变颜色则要进行向量的加法、数乘等。

1. 主要内容：向量、矩阵、方程组

2、相关概念：

（1）N维空间：

  • 零维空间：一个点（标量）存在于零维空间
  • 一维空间：一条线（向量）
  • 二维空间：一个面（矩阵）
  • 三维空间：一个物体（三维张量），一个向量也可存在于三维空间
  • 四维空间：一个物体 + 时间维

（2）意思一样的几个概念：行列式不为0，满秩，线性无关，两个向量可以形成一个平面/两个向量不平行，齐次方程组只有零解，非齐次方程组有唯一解

阐述的是：

​ 向量：在空间中两个向量并不平行可以形成平面。

​ 矩阵：矩阵里几个行向量或列向量是线性无关的，其行列式不等于0且满秩。

3、标量：

  • 是什么：一个数字
  • 作用：在向量空间中，标量的一个重要作用是缩放拉伸向量。

4、 向量：

  • 是什么：物理上，一个箭头，起点为坐标系的原点；如：作用力可以用一个向量来表示，一个方向为Y=X，大小为根号2的力用向量表示为[1,1].

    ​ 数学（计算机）上，一个有序的数字列表；如：一部电影多个评分2,3,5,4，可表示为[2,3,5,4]； 一个苹果重量1g, 价格1元，向量表示[1,1],存在于二维空间。

  • 怎么用：

    • 加法：点的运动，方向改变。
    • 乘法：向量的拉伸缩放，方向不变。
    • 线性无关的向量通过加法和数乘的运算可以表示二维空间中所有向量。
    • 内积（数量积）：在某个方向上，两个向量在上面的投影长度之和（即两个向量不同方向的能量忽略，考虑同方向所蕴含的能量，跟外积相反）
    • 外积（向量积）：其大小是两个向量不同方向所积累的长度（能量）相乘。方向是跟两个向量正交，即形成平面的垂直方向。

5、 矩阵：一种线性变换。

  • 线性变换：保持网格线平行且等距分布。如：一个平面要逆时针旋转90度，即让该基左乘另一个矩阵。
  • 矩阵的列：坐标系中的一个轴/一个方向/一个基等
  • 矩阵的行：空间的维数，3行2列的矩阵表示三维空间中的两个轴。
  • 矩阵左乘：换基或线性变换，主要对矩阵行进行操作。
  • 行列式：线性变换后改变面积/体积等的比例。

发表于 | 分类于 ，

一、题目

1、题目: 判断字符是否唯一

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1:

1
2
输入: s = "leetcode"
输出: false

示例 2:

1
2
输入: s = "abc"
输出: true

说明
  如果你不使用额外的数据结构，会很加分。

法一：使用字符数组

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution{
    public boolean isUnique(String astr) {
        char[] astrArray = astr.toCharArray();
        Arrays.sort(astrArray);
        for (int i = 0; i < astrArray.length - 1; i++){
            if (astrArray[i] == astrArray[i+1]){
                return false;
            }
        }
        return true; 

    }
}

法二：不使用额外空间

1
2
3
4
5
6
7
8
9
10
class Solution{
    public boolean isUnique(String astr){
        for (int i = 0; i < astr.length() - 1; i++){
            if (astr.insdexOf(astr.charAt(i),i+1) != -1 ){
                return false;
            }
        }
        return true;
    }
}

2、题目：字符串轮转

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。

示例1:

输入：s1 = “waterbottle”, s2 = “erbottlewat”
输出：True
示例2:

输入：s1 = “aa”, “aba”
输出：False

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length()){
            return false;
        }
        s1 += s1;
        return s1.contains(s2);

    }
}

发表于 | 分类于 ，

类型一：邻接表

题目一：员工的重要性

题目描述

给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。

比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。

现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。

示例 1:

1
2
3
4
输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出: 11
解释:
员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。

注意:

  1. 一个员工最多有一个直系领导，但是可以有多个直系下属
  2. 员工数量不超过2000。

思路：DFS

  【注意点：应使用局部变量（weight）记录结果，不能使用全局变量】

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
# Employee info
class Employee(object):
    def __init__(self, id, importance, subordinates):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
"""
class Solution(object):
    def getImportance(self, employees, id):
        """
        :type employees: Employee
        :type id: int
        :rtype: int
        """
        if not employees:
            return 0
        ##局部变量
        weight = 0
        for item in employees:
            if item.id == id:
                weight += item.importance
                for j in item.subordinates:
                    weight += self.getImportance(employees, j)
        return weight

题目二：钥匙和房间

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初，除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true，否则返回 false。

示例 1：

1
2
3
4
5
6
7
8
输入: [[1],[2],[3],[]]
输出: true
解释:  
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例 2：

1
2
3
输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

提示：

  1. 1 <= rooms.length <= 1000
  2. 0 <= rooms[i].length <= 1000
  3. 所有房间中的钥匙数量总计不超过 3000。

思路：DFS

每个房间找钥匙，找到则到下一个钥匙对应的房间DFS。采用一个visited列表存储是否到达过这个房间，最后如果所有房间都达到过则返回True。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def canVisitAllRooms(rooms):
    if not rooms:
        return True
    n = len(rooms)
    visited = [False] * n 
    visited[0] = True
    def dfs(rooms,keys,visited):
        for key in keys:
            if not visited[key]:
                visited[key] = True
                dfs(rooms,rooms[key],visited)
    dfs(rooms,rooms[0],visited)
    return all(visited)

类型二：DAG拓扑排序

题目一：课程安排207

题目二：课程安排210

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1:

1
2
3
输入: 2, [[1,0]] 
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:

1
2
3
4
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
     因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

说明:

  1. 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
  2. 你可以假定输入的先决条件中没有重复的边。

提示:

  1. 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
  2. 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
  3. 拓扑排序也可以通过 BFS 完成。

思路：DFS

　　1、建立图

　　2、循环n次，每次是遍历一个节点是否已经visited且合法地加入path中了，如果False不合法则直接返回【】。

　　3、遍历一个节点时会将其后面的所有子节点都处理掉。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from collections import defaultdict
def findPath(n,arr):
    if n == 0:
        return []
    graph = defaultdict(list)
    for u , v in arr:
        graph[v].append(u)
    # 0为Unkown，1为visiting，2为visited
    path = []
    visited = [0] * n
    for i in range(n):
        if not DFS(graph,visited,path,i):
            return []
    return path[::-1]
def DFS(graph,visited,path,i):
    ####i节点：其正在遍历，但它的子节点的子节点也是它，表示产生了有环，则return FALSE
    if visited[i] == 1: return False
    ####i节点 ：已经遍历过，后面已经没有节点了，return true
    elif visited[i] == 2:return True
    ####表示正在遍历i节点
    visited[i] = 1
    for j in graph[i]:
        if not DFS(graph,visited,path,j):
            return False
    path.append(i)
    visited[i] = 2
    return True


n = 5
arr = [[1,0],[2,0],[3,1],[3,2],[4,0]]
print(findPath(n,arr))

发表于 | 分类于 ，

题目：输出所有路径数

题目描述

思路：DFS

  从起点开始，DFS，直到走到终点，用一个全局变量res[0]记录所有路径数量。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
##dirs为上下左右方向
dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
##结果设为全局变量
res = 0
##原始矩阵
graph = [[0, 1, 0, 0, 0], [0, 2, 3, 0, 0], [0, 0, 4, 5, 0], [0, 0, 7, 6, 0]]
row = 4
col = 5
##起始点和终点
x1, y1, x2, y2 = 0, 1, 3, 2

def dfs(x1, y1, visited):
	global res
    if x1 == x2 and y1 == y2:
        res += 1
        return
    for i, j in dirs:
        tmp_x = i + x1
        tmp_y = j + y1
        if 0 <= tmp_x < row and 0 <= tmp_y < col and graph[tmp_x][tmp_y] > graph[x1][y1] \
                and (tmp_x, tmp_y) not in visited:
            dfs(tmp_x, tmp_y, visited | {(tmp_x, tmp_y)})

dfs(x1, y1, {(x1, y1)})
print(res)

题目：图像渲染

题目描述

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

示例 1:

1
2
3
4
5
6
7
8
9
输入: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。

思路：DFS

​ 边界：如果当前值被浏览过则停止。即被赋予过新值。

​ 递归子问题：从起点开始，将当前点赋值为新值，上下左右移动查看符合条件（值与起始点相同，在矩阵维度内）的位置点，进行DFS。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def floodFill(self, image, sr, sc, newColor):
    """
    :type image: List[List[int]]
    :type sr: int
    :type sc: int
    :type newColor: int
    :rtype: List[List[int]]
    """
    ##上下左右移动方向
    stack = [(-1,0),(1,0),(0,-1),(0,1)] 
    ##矩阵维度
    self.m , self.n = len(image) , len(image[0])
    ##val表示起点值
    self.val = image[sr][sc] 
    ##递归函数
    def dfs(image,x,y,newColor):
        ##如果该值被浏览过，则退出（边界）
        if image[x][y] == newColor:
            return image
        ##将当前位置赋值为新值
        image[x][y] = newColor
        for i,j in stack:
            ##tmpx,tmpy是上下左右移动的值
            tmpx = x + i
            tmpy = y + j
            ##如果tmpx,tmpy在矩阵维度范围内，且该位置的值和起始点值一样，则进入递归。
            if 0 <= tmpx < self.m and 0 <= tmpy < self.n and image[tmpx][tmpy] == self.val:
                dfs(image,tmpx,tmpy,newColor)
    if 0 <= sr < self.m and 0 <= sc < self.n:
        dfs(image,sr,sc,newColor)
    return image

题目：单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

1
2
3
4
5
6
7
8
9
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

思路：DFS

对所有的点进行遍历，找到第一个字母与word的第一个字母相同的，开始进行dfs。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def exist(self, board,word):
        if not word:
            return True
        if not board or not board[0]:
            return False
        self.m , self.n = len(board) , len(board[0])
        stack = [(0,1),(0,-1),(1,0),(-1,0)]
        self.flag = False
        ##DFS
        def dfs(board,word,stack,x,y,w,visited):
            if w == len(word):
                self.flag = True
                return 
            for i,j in stack:
                temx = x + i
                temy = y + j
                if 0 <= temx < self.m and 0 <= temy < self.n and board[temx][temy] == word[w] and (temx,temy) not in visited:
                    dfs(board,word,stack,temx,temy,w+1,visited|{(temx,temy)})
                    ##这里是要一遇到可不继续递归则立马停止，不然时间复杂度太高
                    if self.flag:
                        return
        #每个点都有看是不是可以作为起始。
        for i in range(self.m):
            for j in range(self.n):
                if board[i][j] == word[0]:
                    dfs(board,word,stack,i,j,1,{(i,j)})
                    ##这里是要一遇到可不继续递归则立马停止，不然时间复杂度太高
                    if self.flag:
                        return True
        return self.flag

题目：岛屿的最大面积

题目描述

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1:

1
2
3
4
5
6
7
8
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

1
[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

思路：DFS

  遍历矩阵，遇到 grid [i] [j] = 1时，就算值【采用dfs来算】

  dfs : 先将grid [i] [j] 置0，然后再 return 1 + dfs [i-1] [j] + dfs [i+1] [j] +dfs [i] [j-1] +dfs [i] [j+1]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def maxAreaOfIsland(self, grid):
       """
       :type grid: List[List[int]]
       :rtype: int
       """
       if not grid:
           return 0
       l,h = len(grid),len(grid[0])
       
       def dfs(i,j):
           if 0 <= i < l and 0 <= j < h and grid[i][j]:
               grid[i][j] = 0
               return 1 + dfs(i-1,j) + dfs(i+1,j) +dfs(i,j-1) + dfs(i,j+1)
           return 0
           
       result = [dfs(i,j) for i in range(l) for j in range(h) if grid[i][j]]
       return max(result) if result else 0

题目：岛屿的个数

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3

思路：DFS

​ 遍历矩阵，遇到 grid [i] [j] = 1时，将最大面积的岛屿置0【采用dfs来算】，res记录几个岛屿个数。

  dfs : 将grid [i] [j] 置0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0
        stack = [(-1,0),(1,0),(0,1),(0,-1)]
        self.m , self.n = len(grid) , len(grid[0])
        res = 0
        def dfs(grid,stack,x,y):
            grid[x][y] = '0'
            for i,j in stack:
                tmpx = x + i
                tmpy = y + j
                if 0 <= tmpx < self.m and 0 <= tmpy < self.n and grid[tmpx][tmpy] == '1':
                    dfs(grid,stack,tmpx,tmpy)
            return grid
        for i in range(self.m):
            for j in range(self.n):
                if grid[i][j]=='1':
                    dfs(grid,stack,i,j)
                    res += 1
        return res

题目：最大正方形

题目描述

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

1
2
3
4
5
6
输入: 
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

思路：动态规划

img

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int max = 0;
        int[][] dp = new int[m][n];
        // 第一列赋值
        for(int i = 0; i < m; i++){
            dp[i][0] = matrix[i][0] - '0';
            max = Math.max(max, dp[i][0]);
        }
        // 第一行赋值
        for(int i = 0; i < n; i++){
            dp[0][i] = matrix[0][i] - '0';
            max = Math.max(max, dp[0][i]);
        }
        // 递推
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = matrix[i][j] == '1' ? Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1 : 0;
                max = Math.max(max, dp[i][j]);
            }
        }
        return max * max;
    }
}

题目：01矩阵

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:
输入:

1
2
3
0 0 0
0 1 0
0 0 0

输出：

1
2
3
0 0 0
0 1 0
0 0 0

示例 2:
输入:

1
2
3
0 0 0
0 1 0
1 1 1

输出:

1
2
3
0 0 0
0 1 0
1 2 1

注意:

  1. 给定矩阵的元素个数不超过 10000。
  2. 给定矩阵中至少有一个元素是 0。
  3. 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

思路1：DFS

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int dfs(vector<vector<int>> &matrix,int i,int j,int R,int C,bool** visited){
        int res=R+C;

        if (0==matrix[i][j]) return 0;

        visited[i][j]=true;

        if (j>0&&!visited[i][j-1]){//left
            res=min(res,1+dfs(matrix,i,j-1,R,C,visited));
        }
        if (j<C-1&&!visited[i][j+1]){//right
            res=min(res,1+dfs(matrix,i,j+1,R,C,visited));
        }
        if (i>0&&!visited[i-1][j]){//up
            res=min(res,1+dfs(matrix,i-1,j,R,C,visited));
        }
        if (i<R-1&&!visited[i+1][j]){//down
             res=min(res,1+dfs(matrix,i+1,j,R,C,visited));
        }

        visited[i][j]=false;

        return res;
    }

    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int R=matrix.size(),C=matrix[0].size();
        vector<vector<int>> ret(R,vector<int>(C,0));

        bool **visited=new bool *[R];
        for (int i=0;i<R;i++){
           visited[i]=new bool [C];
           fill(visited[i],visited[i]+C,false);
        }

        for (int i=0;i<R;i++){
            for (int j=0;j<C;j++){
                ret[i][j]=dfs(matrix,i,j,R,C,visited);
            }
        }
        delete [] visited;
        return ret;
    }
};

思路2：BFS

题目：被围绕的区域

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

1
2
3
4
X X X X
X O O X
X X O X
X O X X

运行你的函数后，矩阵变为：

1
2
3
4
X X X X
X X X X
X X X X
X O X X

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

思路：DFS

题意就是找出被‘X’完全包围的‘O’的区域，填充为‘X’。

解决思路就是反向找出没有完全被‘X’完全包围的‘O’的区域，标记一下，然后没有标记的就是要被填充的。

  • 思路就是绕着矩阵的最外圈转一圈，碰到‘O’，说明这里可以往里进行深搜；
  • 将深搜经过的所有‘O’都标记成‘Y’；
  • 外圈深搜完成后，所有没有被包围的‘O’都已经标记成了‘Y’；
  • 将所有‘Y’填充为‘O’，所有‘O’填充为‘X’。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def solve(board):
    """
    Do not return anything, modify board in-place instead.
    """
    if not board or not board[0]:
        return
    m , n = len(board) , len(board[0])
    stack = [(0,1),(0,-1),(1,0),(-1,0)]
    #将深搜经过的所有‘O’都标记成‘Y’；
    def dfs(board,x,y,stack,m,n):
        board[x][y] = 'Y'
        for i,j in stack:
            temx = x + i
            temy = y + j
            if 0 <= temx < m and 0 <= temy < n and board[temx][temy] == 'O':
                board[temx][temy] = 'Y'
                dfs(board,temx,temy,stack,m,n)
    #外圈深搜完成后，所有没有被包围的‘O’都已经标记成了‘Y’；
    for y in range(n):
        if board[0][y] == 'O':
            dfs(board,0,y,stack,m,n)
    for x in range(m):
        if board[x][n-1] == 'O':
            dfs(board,x,n-1,stack,m,n)            
    for y in range(n):
        if board[m-1][y] == 'O':
            dfs(board,m-1,y,stack,m,n)
    for x in range(m):
        if board[x][0] == 'O':
            dfs(board,x,0,stack,m,n)
    #将所有‘Y’填充为‘O’，所有‘O’填充为‘X’。
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == 'Y':
                board[i][j] = 'O'

发表于 | 分类于 ，

类型一：树的深度

题目1：二叉树的最大深度

题目描述

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明 : 叶子节点是指没有子节点的节点。
示例 ：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。

思路1：递归

  边界： 一旦root == None则返回深度为0。否则进入递归子问题。
  递归子问题： max(左树深度，右树深度）+ 1

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def dfs(root):
    #边界
    if not root:
        return 0
    #递归子问题
    else:
        left = dfs(root.left)
        right = dfs(root.right)
        return max(left,right)+1


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.right = TreeNode(5)
height = dfs(root)

思路2：深度遍历DFS

  边界：一旦root == None则记录深度大小tmp，判断是否大于res（结果）。否则进入递归子问题。
  递归子问题：将当前深度tmp+1，传入左子树和右子树

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class TreeNode(object):
	def __init__(self, x):
   		self.val = x
       		self.left = None
       		self.right = None
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.right = TreeNode(5)
#全局变量
res = 0
def dfs(root,tmp):
    	global res
     	##边界
     	if not root:
        		res = max(res,tmp)
   		return
	###递归子问题
	else:
   		dfs(root.left,tmp+1)
   		dfs(root.right,tmp+1)
dfs(root,0)
print(res)

代码3

1
2
3
4
5
6
7
8
9
10
11
res = 0
def dfs(root,height):
    global res
    if root:
    	if not root.left and not root.right:
    		self.res = max(res,height)
    	else:
    		dfs(root.left,height+1)
    		dfs(root.right,height+1)
dfs(root,1)
print(res)

题目2：二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回它的最小深度 2.

思路1：DFS

如果根节点没有左子树或右子树，则返回（ 1+左子树深度+右子树深度）

如果根节点左右子树都有，则返回（1+min(左子树深度，右子树深度)

代码

1
2
3
4
5
6
def minDepth(root)
    if not root:
        return 0
    left = self.minDepth(root.left)
    right = self.minDepth(root.right)
    return 1+min(left,right) if left and right else 1 + left + right

思路2：迭代

层次遍历，一旦有一层存在左右子树都没有，则返回height

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def minDepth(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    
    if not root:
        return 0
    prev,height=[root],1
    while prev:
        cur=[]
        while prev:
            node=prev.pop(0)
            if node.left:
                cur.append(node.left)
            if node.right:
                cur.append(node.right)
            if not node.left and not node.right:
                return height 
        prev=cur
        height+=1
        
    return height

题目3：平衡二叉树

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

1
2
3
4
5
6
7
      1
     / \
    2   2
   / \
  3   3
 / \
4   4

返回 false 。

思路：DFS

【和求深度思想一样】

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def helper(root):
            if not root:
                return 0
            left=helper(root.left)
            right=helper(root.right)
            if left==-1 or right==-1 or abs(left-right)>1:
                return -1
            return 1+max(left,right)
        res=helper(root)
        return False if res==-1 else True

题目4：找树左下角的值

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

1
2
3
4
5
6
7
输入:

    2
   / \
  1   3

输出:1

示例 2: 

1
2
3
4
5
6
7
8
9
10
11
输入:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输出:7

思路1：DFS

维护一个最大深度 self.height 如果深度更新，则对应的值也更新。

这里注意先更新右边再更新左边，这样最后的值将会是最左边的值，左边的值会把右边的覆盖掉，如果深度相同的话

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def leftValue(root):
    if not root:
        return None
    def dfs(root,tmpheight):
        if not root:
            return 0
        if tmpheight > self.height:
            self.height = tmpheight
        if self.height <= tmpheight and not root.left and not root.right:
            self.res = root.val
        dfs(root.right,tmpheight+1)
        dfs(root.left,tmpheight+1)

    self.res = root.val
    self.height = 0
    tmpheight = 0
    dfs(root,tmpheight)
    return self.res

思路2：层次遍历

代码2

1
2
3
4
5
6
7
8
9
10
11
def leftValue(root):
    if not root:
        return None
    prev = [root]
    while prev:
        node = prev.pop(0)
        if node.right:
            prev.append(node.right)
        if node.left:
            prev.append(node.left)
    return node.val

题目5：二叉树的右视图

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

1
2
3
4
5
6
7
8
9
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

思路1:DFS
代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
def treeRight(root):
    if not root:
        return []
    res = [root.val]
    def dfs(root,height):
        if not root:
            return
        if len(res) < height:
            res.append(root.val)
        dfs(root.right,height+1)
        dfs(root.left,height+1)
    dfs(root,1)
    return res

思路2：层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def rightSideView(root):
    if not root:
        return []
    prev,res = [root],[root.val]
    while prev:
        cur = []
        while prev:
            node = prev.pop(0)
            if node.right:
                cur.append(node.right)
            if node.left:
                cur.append(node.left)
        if cur:
            res.append(cur[0].val)
        prev = cur
    return res

题目6：在每个树行中找最大值

您需要在二叉树的每一行中找到最大的值。

示例：

1
2
3
4
5
6
7
8
9
输入: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

输出: [1, 3, 9]

思路1：层次遍历
代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def largestValues(root):
    if not root:
        return []
    res = [root.val]
    prev = [root]
    while prev:
        cur = []
        while prev:
            node = prev.pop()
            if node.left:
                cur.append(node.left)
            if node.right:
                cur.append(node.right)
        if cur:
            res.append(max([i.val for i in cur]))
        prev = cur
    return res

思路2：DFS
代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def largestValues(root):
    if not root:
        return []
    res = [root.val]
    def dfs(root,height):
        if root:
            if len(res) <= height:
                res.append(root.val)
            if len(res) > height and root.val > res[height]:
                res[height] = root.val
            dfs(root.left,height + 1)
            dfs(root.right,height+1)
    dfs(root,0)
    return res

类型二：树的路径

题目1：二叉树的所有路径

题目描述

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
输入:

1
/ \
2 3
\
5

输出: [“1->2->5”, “1->3”]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

思路：DFS

  边界:

    如果root==None，不管

    如果root.left和root.right同时为空，则将这条路径加入res数组中。

  递归子问题：

    如果root.left或者root.right有一个不为空，继续dfs(root.left,path),dfs(root.right,path)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Node():
    def __init__(self,value):
        self.val = value
        self.left = None
        self.right = None
def test(root):
    if not root:
        return []
    res = []
    def dfs(root,path):
        if root:
            path = path + str(root.val) + '->'
            if not root.left and not root.right:
                res.append(path[:-2])
            else:
                dfs(root.left,path)
                dfs(root.right,path)
    dfs(root,'')
    return res
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
test(root)

题目2：路径总和

题目描述

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

思路：DFS

查看每条路径和是否等于sum，

递归边界：没有左子树也没有右子树时，判断是否等于sum。

递归子问题：递归左子树，递归右子树

代码

1
2
3
4
5
6
7
8
9
10
11
def hasPathSum(root,sum):
    if not root:
        return False
    def dfs(root,sum,tmpSum):
        if root:
            tmpSum += root.val
            if not root.left and not root.right:
                return tmpSum == sum
            else:
                return dfs(root.left,sum,tmpSum) or dfs(root.right,sum,tmpSum)
    return dfs(root,sum,0)

题目3：路径总和II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]

思路：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def pathSum(root,sum):
    if not root:
        return []
    res = []
    tmp = ''
    def dfs(root,tmp,res):
        if root:
            tmp += str(root.val)+','
            if not root.left and not root.right:
                new = list(map(int,tmp.split(',')[:-1]))
                newsum = 0
                for i in new:
                    newsum += i
                if newsum == sum:
                    res.append(new)
            else:
                dfs(root.left,tmp,res)
                dfs(root.right,tmp,res)
    dfs(root,tmp,res)
    return res

题目4：叶子相似的树

题目描述

请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子，如上图所示，给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

提示：

  • 给定的两颗树可能会有 1 到 100 个结点。

思路：DFS

  思路和二叉树的所有路径一样，边界只有遇到叶子节点才将其加入res中。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def leafsimilar(root1,root2):    
    if not root1 and not root2:
            return True
        if not root1 or not root2:
            return False
        leaf1 , leaf2 = [] , []
        def dfs(root,leaf):
            if root:
                if not root.left and not root.right:
                    leaf.append(root.val)
                else:
                    dfs(root.left,leaf)
                    dfs(root.right,leaf)
        dfs(root1,leaf1)
        dfs(root2,leaf2)
        return leaf1 == leaf2

题目5：求根到叶子节点数字之和

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

示例 1:

1
2
3
4
5
6
7
8
9
输入: [1,2,3]
    1
   / \
  2   3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
输入: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.

思路：DFS

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def sumNumbers(self, root: TreeNode) -> int:
    if not root:
        return 0
    res = []
    def dfs(root,path):
        if root:
            path += str(root.val) 
            if not root.left and not root.right:
                res.append(int(path))
                return
            dfs(root.left,path)
            dfs(root.right,path)
    dfs(root,'')
    return sum(res)

题目6：节点与其祖先之间的最大差值

给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

示例：

img

1
2
3
4
5
6
7
8
9
输入：[8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释： 
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。

思路：DFS

​ 找树的每条路径中的最小值和最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def __init__(self):
        self.res = 0
    def maxAncestorDiff(self, root: TreeNode) -> int:
        if not root:
            return 0
        self.res = 0
        minV , maxV = 9999999,-9999999
        def findpath(root,minV,maxV):
            if root:
                minV = min(minV,root.val)
                maxV = max(maxV,root.val)
                if not root.left and not root.right:
                    self.res = max(self.res,abs(maxV-minV))
                    return 
                findpath(root.left,minV,maxV)
                findpath(root.right,minV,maxV)
        findpath(root,minV,maxV)
        return self.res

类型三：二叉树类型

题目1：对称二叉树

题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
2
3
4
5
  1
 / \
2   2
 \   \
 3    3

思路1：DFS

先判断二叉树是否是平衡树，

比如有两个节点left, right，

需要比较left的左子节点的值和right的右子节点的值是否相等，

同时还要比较left的右子节点的值和right的左子结点的值是否相等，

以此类推比较完所有的左右两个节点。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
def isSymmetric(root):    
    if not root:
            return True
        def dfs(left,right):
            ##判断是否是平衡树
            if not left and not right:
                return True
            elif (not left and right) or (not right and left) or left.val != right.val:
                return False
            else:
                return dfs(left.left,right.right) and dfs(left.right,right.left)
        return dfs(root.left,root.right)

思路2：迭代

层次遍历，判断每层数据是否是对称的。

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def isSymmetric(root): 
    if not root:
            return True
    prev=[root]
    while prev:
        cur=[]
        while prev:
            node=prev.pop()
            if node:
                cur.append(node.left)
                cur.append(node.right)
        prev=cur
        if len(cur)%2==1:
            return False
        i=0
        while i<len(cur)//2:
            if cur[i] and cur[~i]:
                if cur[i].val!=cur[~i].val:
                    return False
            elif cur[i] or cur[~i]:
                return False
            i+=1
    return True

类型四：二叉树操作

题目1：在二叉树中分配硬币

给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。

在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。

返回使每个结点上只有一枚硬币所需的移动次数。

示例 1：

1
2
3
输入：[3,0,0]
输出：2
解释：从树的根结点开始，我们将一枚硬币移到它的左子结点上，一枚硬币移到它的右子结点上。

示例 2：

1
2
3
输入：[0,3,0]
输出：3
解释：从根结点的左子结点开始，我们将两枚硬币移到根结点上 [移动两次]。然后，我们把一枚硬币从根结点移到右子结点上。

示例 3：

1
2
输入：[1,0,2]
输出：2

示例 4：

1
2
输入：[1,0,0,null,3]
输出：4

提示：

  1. 1<= N <= 100
  2. 0 <= node.val <= N

思路：DFS

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def distributeCoins(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.res = 0
        self.dfs(root)
        return self.res
        
    def dfs(self, root):
        if root:
            l, r = self.dfs(root.left), self.dfs(root.right)
            self.res += abs(l) + abs(r)
            return l + r + root.val - 1
        return 0

发表于 | 分类于 ，

十大排序

题目一：922. 按奇偶排序数组 II

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

示例：

1
2
3
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受

提示：

  1. 2 <= A.length <= 20000
  2. A.length % 2 == 0
  3. 0 <= A[i] <= 1000

思路：奇偶下标的错误数进行交换。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def sortArrayByParityII(A):
    if not A:
        return []
    even , odd = 0 , 1
    while even < len(A) and odd < len(A):
        ##一旦两个下标的数不对，则交换
        if A[even] % 2 and A[odd] % 2 == 0:
            A[even] , A[odd] = A[odd] , A[even]
            even += 2
            odd += 2
        elif A[even] % 2 == 0 and A[odd] % 2:
            even += 2
            odd += 2
        elif A[even] % 2 == 0 and A[odd] % 2 == 0:
            even += 2
        elif A[even] % 2 and A[odd] % 2 :
            odd += 2
    return A

题目二：349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

1
2
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:

1
2
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

说明:

  • 输出结果中的每个元素一定是唯一的。
  • 我们可以不考虑输出结果的顺序。

思路一：采用字典，时间O（m+n)，空间O（min(m,n)）

​ 采用字典存储nums1的数，然后遍历nums2的数，一旦在字典中则加入结果中

代码：

1
2
3
4
5
6
7
8
9
10
11
12
from collections import Counter
class Solution:
    def intersection(self, nums1, nums2):
        if not nums1 or not nums2:
            return nums1 if nums2 else nums2
        res = []
        n1 , n2 = len(nums1) , len(nums2)
        counter1 = Counter(nums1)
        for num in nums2:
            if num in counter1:
                res.append(num)
        return list(set(res))

思路二：排序，时间O(mn)，空间O（1）

​ 对两个数组进行排序，同时遍历两个数组

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def intersection(self, nums1, nums2):
        snum1 = sorted(nums1)
        snum2 = sorted(nums2)
        res = []
        i , j = 0 , 0
        while i < len(snum1) and j < len(snum2):
            if snum1[i] == snum2[j]:
                res.append(snum2[j])
                i += 1
                j += 1
            elif snum1[i] < snum2[j]:
                i += 1
            else:
                j += 1
        return list(set(res))

思路三：采用集合交集特性，平均时间O（min(m,n))，最坏时间O（m*n)，空间O（m+n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
def intersection(nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: List[int]
    """
    if not nums1 or not nums2:
        return []
    else:
        a=set(nums1)
        b=set(nums2)
        return list(a&b)

题目三：976. 三角形的最大周长

给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。

如果不能形成任何面积不为零的三角形，返回 0。

示例 1：

1
2
输入：[2,1,2]
输出：5

示例 2：

1
2
输入：[1,2,1]
输出：0

示例 3：

1
2
输入：[3,2,3,4]
输出：10

示例 4：

1
2
输入：[3,6,2,3]
输出：8

思路：反向排序，第一个满足A[i+2] + A[i+1] > A[i]为所求

代码

1
2
3
4
5
6
7
8
def largestPerimeter(A):
    if len(A) <= 2:
        return 0
    A.sort(reverse = True)
    for i in range(len(A)-2):
        if A[i+2] + A[i+1] > A[i]:
            return A[i+2] + A[i+1] + A[i]
    return 0

题目四：242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。

示例 1:

1
2
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

1
2
输入: s = "rat", t = "car"
输出: false

说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

思路一：排序，比较s和t

代码一

1
2
3
4
5
6
7
8
9
def isAnagram(s,t):
    if len(s)!=len(t):
        return False
    s.sort()
    t.sort()
    for i in range(len(s)):
        if s[i] != t[i]:
            return False
    return True

思路二：字典

代码二：

1
2
3
4
5
6
7
8
9
from collections import Counter
def isAnagram(s,t):
    if len(s) !=len(t):
        return False
    else:
        if Counter(s) == Counter(t):
            return True
        else:
            return False