建立打印力扣(Leetcode)中的二叉树-java

发表于 2021-04-27 更新于 2021-09-01 分类于力扣 Changyan：

建立打印LeetCode中的二叉树

在刷力扣题时遇到二叉树的问题时，建树较为麻烦，打印树更加是不方便。

因为力扣中二叉树定义多为

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

再增加建树的成员方法

public static TreeNode creatABitTree(Integer[] nums) {

    if (nums.length == 0 || nums[0] == null) return null;
    if (nums.length == 1) return new TreeNode(nums[0]);

    Queue<TreeNode> queue = new LinkedList<>();  // 得用队列
    // 根结点的处理
    TreeNode node = new TreeNode(nums[0]);
    queue.offer(node);

    TreeNode temp;
    for (int i = 1; i < nums.length; ) {
        temp = queue.poll();
        if (nums[i] != null) {
            assert temp != null;
            temp.left = new TreeNode(nums[i++]);
            queue.offer(temp.left);
        } else
            i++;
        if (i >= nums.length)
            break;
        if (nums[i] != null) {
            assert temp != null;
            temp.right = new TreeNode(nums[i++]);
            queue.offer(temp.right);
        } else
            i++;
    }


    return node;
}

参考 StackOverflow中How to print binary tree diagram?这个问答，再添加树的打印方法

public StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) {
    if (right != null) {
        right.toString(new StringBuilder().append(prefix).append(isTail ? "│   " : "    "), false, sb);
    }
    sb.append(prefix).append(isTail ? "└── " : "┌── ").append(val).append("\n");
    if (left != null) {
        left.toString(new StringBuilder().append(prefix).append(isTail ? "    " : "│   "), true, sb);
    }
    return sb;
}

@Override
public String toString() {
    return this.toString(new StringBuilder(), true, new StringBuilder()).toString();
}

测试

使用以下测试函数

class Main {
    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.creatABitTree(new Integer[]{
                0,1,2,3,4,5,6
        });
        System.out.println(treeNode);
    }
}

获得的测试结果：

│       ┌── 6
│   ┌── 2
│   │   └── 5
└── 0
    │   ┌── 4
    └── 1
        └── 3

完整的TreeNode类

import java.util.LinkedList;
import java.util.Queue;

/**
 * create time: 2021/3/9 上午 10:01
 *
 * @author DownUpZ
 */
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }

    /***
     * 不选择 int[] 原因是 int 无法表示空
     * @param nums
     * @return
     */
    public static TreeNode creatABitTree(Integer[] nums) {

        if (nums.length == 0 || nums[0] == null) return null;
        if (nums.length == 1) return new TreeNode(nums[0]);

        Queue<TreeNode> queue = new LinkedList<>();  // 得用队列
        // 根结点的处理
        TreeNode node = new TreeNode(nums[0]);
        queue.offer(node);

        TreeNode temp;
        for (int i = 1; i < nums.length; ) {
            temp = queue.poll();
            if (nums[i] != null) {
                assert temp != null;
                temp.left = new TreeNode(nums[i++]);
                queue.offer(temp.left);
            } else
                i++;
            if (i >= nums.length)
                break;
            if (nums[i] != null) {
                assert temp != null;
                temp.right = new TreeNode(nums[i++]);
                queue.offer(temp.right);
            } else
                i++;
        }


        return node;
    }

    public StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) {
        if (right != null) {
            right.toString(new StringBuilder().append(prefix).append(isTail ? "│   " : "    "), false, sb);
        }
        sb.append(prefix).append(isTail ? "└── " : "┌── ").append(val).append("\n");
        if (left != null) {
            left.toString(new StringBuilder().append(prefix).append(isTail ? "    " : "│   "), true, sb);
        }
        return sb;
    }

    @Override
    public String toString() {
        return this.toString(new StringBuilder(), true, new StringBuilder()).toString();
    }

}

力扣938.二叉搜索树的范围和

发表于 2021-04-27 更新于 2021-09-01 分类于力扣 Changyan：

题目

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

示例 1：

二叉搜索树1

1 2	输入：root = [10,5,15,3,7,null,18], low = 7, high = 15 输出：32

示例 2：

二叉搜索树2


输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23

提示：

树中节点数目在范围 [1, 2 * 104] 内
1 <= Node.val <= 105
1 <= low <= high <= 105
所有 Node.val 互不相同

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/range-sum-of-bst

解答

一道简单题，中序遍历递归即可

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        int leftVal = rangeSumBST(root.left, low, high);
        int midVal = 0;
        if (low <= root.val && root.val <= high) midVal = root.val;
        int rightVal = rangeSumBST(root.right, low, high);
        return leftVal + midVal + rightVal;
    }
}

力扣1011.在D天内送达包裹的能力

发表于 2021-04-26 更新于 2021-09-01 分类于力扣 Changyan：

问题

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1：

输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。

示例 2：

输入：weights = [3,2,2,4,1,4], D = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4

示例 3：

输入：weights = [1,2,3,1,1], D = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1

提示：

1 2	1 <= D <= weights.length <= 50000 1 <= weights[i] <= 500

来源：链接

解答

二分法

引用用户@Celia的解释：

二分查找，根据题意，结果一定落在【max(weights), sum(weights）】这个区间之间，因为左端点对应每天一条船，右端点对应只有一条超级大船。然后利用二分法，每一次循环模拟运货的过程，然后根据需要的天数与输入 D 的关系来调整区间左右端点。

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l, r = max(weights), sum(weights)
        while l < r:
            mid = (l + r) // 2
            if self.isEnough(weights, D, mid) is False:
                l = mid + 1
            else:
                r = mid
        return l

    def isEnough(self, weights, D, load):
        curD, curLoad = 1, 0
        for w in weights:
            if curLoad + w > load:
                curLoad = w
                curD += 1
            else:
                curLoad += w
            if curD > D: return False
        return True

力扣377.组合综合Ⅳ

发表于 2021-04-24 更新于 2021-09-01 分类于力扣 Changyan：

题目

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

1 2	输入：nums = [9], target = 3 输出：0

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/combination-sum-iv

解答

递归。加上lru_cache后不会超时

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        self.nums = nums
        return self.recur(target)

    @lru_cache(1000 * 1000)
    def recur(self, target):
        ret = 0
        if target == 0:
            return 1
        for x in self.nums:
            if x <= target:
                ret += self.recur(target - x)
        return ret

动态规划

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [1] + [0] * target
        for i in range(1, target + 1):
            for x in nums:
                if x <= i:
                    dp[i] += dp[i - x]
        return dp[target]

力扣69.x的平方根

发表于 2021-04-23 更新于 2021-09-01 分类于力扣 Changyan：

题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

1 2	输入: 4 输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

链接：

https://leetcode-cn.com/problems/sqrtx/

解答

二分查找

二分法是符合计算机思想的解法。

二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 bit 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0: return 0
        small = 1
        big = x
        while big - small > 1:
            bit = (small + big) // 2
            if bit ** 2 == x:
                return bit
            elif bit ** 2 < x:
                small = bit
            elif bit ** 2 > x:
                big = bit

        return int(small)

牛顿法

这个题解说的比较好：

https://link.zhihu.com/?target=https%3A//leetcode-cn.com/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/

该方法比较适合机器学习背景。

class Solution:
    def mySqrt(self, x: int) -> int:
        r = x
        while r * r > x:
            r = (r + x / r) // 2
        return int(r)

实用python小工具--函数运行时间装饰器

发表于 2021-04-23 更新于 2021-09-01 分类于 python Changyan：

装饰器定义如下：

import time
def CalculateTime(a_func):
    def wrapTheFunction():
        start = time.time()
        a_func()
        cost = time.time() - start
        print(f"Function \"{a_func.__name__}\" cost : {cost} second(s).")
    return wrapTheFunction

测试部分

@CalculateTime
def func():
    s = 0
    for i in range(10 ** 7):
        s += 1
    print(s)


if __name__ == '__main__':
    func()

结果

1 2	10000000 Function "func" cost : 1.7449958324432373 second(s).

箱型图法处理异常

发表于 2021-04-23 更新于 2021-09-01 分类于 python Changyan：

箱型图介绍看链接：

Python异常数据处理——箱型图分析

一下Python是使用箱型图找到异常值并用线性插值把剔除异常后的缺失填充上。

核心代码

import pandas as pd

def wash_data(df: pd.DataFrame):
    """箱型图法"""
    q1 = df.quantile(0.25)
    q3 = df.quantile(0.75)
    iqr = q3 - q1
    mi = q1 - 1.5 * iqr
    ma = q3 + 1.5 * iqr
    # error = df[(df < mi) | (df > ma)]
    data_c = df[(df >= mi) & (df <= ma)]
    return data_c.interpolate().bfill()  # 线性插值

测试代码

import pandas as pd
import numpy as np

if __name__ == '__main__':
    df = pd.DataFrame(data=np.random.rand(10, 2))
    df[0][1] = 100
    df[0][2] = 99
    print(df)
    washedDf = wash_data(df)
    print(washedDf)

输出结果

            0         1
0    0.385158  0.469756
1  100.000000  0.090029
2   99.000000  0.807008
3    0.832849  0.672141
4    0.965382  0.847540
5    0.275084  0.003218
6    0.366026  0.211611
7    0.462773  0.226748
8    0.244522  0.916068
9    0.906602  0.029235
          0         1
0  0.385158  0.469756
1  0.534389  0.090029
2  0.683619  0.807008
3  0.832849  0.672141
4  0.965382  0.847540
5  0.275084  0.003218
6  0.366026  0.211611
7  0.462773  0.226748
8  0.244522  0.916068
9  0.906602  0.029235

进程已结束，退出代码为 0

python读取pickle,csv,excel文件速度大比拼

发表于 2021-04-23 更新于 2021-09-01 分类于 python Changyan：

进行数据处理时数据量一大，excel文件就力不从心。
这次对三个文件格式的读取速度做大比拼。

# -*- coding: UTF-8 -*-
import time
import pandas as pd
"""
csv
excel
pkl
速度大比拼

"""
start = time.clock()
df = pd.read_pickle('table.pkl')
elapsed = (time.clock() - start)
print("PKL Time used:", elapsed)

start = time.clock()
df = pd.read_csv('table.csv')
elapsed = (time.clock() - start)
print("CSV Time used:", elapsed)

start = time.clock()
df = pd.read_excel('table.xlsx')
elapsed = (time.clock() - start)
print("EXCEL Time used:", elapsed)

输出结果

1
2
3

PKL Time used: 0.0913808
CSV Time used: 0.2128232
EXCEL Time used: 10.9964416

pickle完美胜出。参考链接中有大佬的更详细的比拼。

参考

https://www.jianshu.com/p/d857c0f472f4

postgresql使用速记

发表于 2020-05-24 更新于 2021-09-01 Changyan：

基本使用1

登录

psql -U postgres

创建数据库用户

CREATE USER user_name WITH PASSWORD 'password';

创建用户数据库

CREATE DATABASE user_name OWNER user_name;

给予权限

GRANT ALL PRIVILEGES ON DATABASE user_name to user_name;

删除用户与数据库

DROP DATABASE user_name;
DROP USER user_name;

控制台命令

\l 列出所有数据库
\d 列出当前数据库的所有表格
\d [table_name] 列出某一张表格的结构
\c [database_name] 切换数据库
\c - [user_name] 切换用户

查看数据库占用的物理存储空间大小2

sql语句查询：

postgres=# select pg_size_pretty(pg_database_size('postgres'));

pg_size_pretty
----------------
6229 kB
(1 行记录)

配置PostgreSQL允许远程连接的方法

配置PostgreSQL允许远程连接的方法（PostgreSQL新手入坑）

linux 下怎么看postgresql安装到哪个目录了？

psql -U postgres -c 'SHOW config_file'

可参考以下配置文件目录：

sudo vim /var/lib/postgres/data/postgresql.conf
sudo vim /var/lib/postgres/data/pg_hba.conf

参考

https://www.jianshu.com/p/34afe4072598

https://www.cnblogs.com/liuyuanyuanGOGO/p/3224554.html

踩坑笔记

1

如果出现这种情况：

~ >>> psql
psql: error: could not connect to server: could not connect to server: No such file or directory
        Is the server running locally and accepting
        connections on Unix domain socket "/run/postgresql/.s.PGSQL.5432"?

是根本没启动！！！
一个命令可直接启动

sudo systemctl start postgresql.service
sudo systemctl restart postgresql.service

python创建文件夹

发表于 2020-04-18 更新于 2021-09-01 分类于 python Changyan：

如果文件夹不存在创建文件夹

1 2	if not os.path.exists(dirs): os.makedirs(dirs)

参考

https://blog.csdn.net/qq_39575835/article/details/103974778