ARTS 03 - 使用图解的方式来解决链表的算法问题

发布于: 2 小时前
ARTS 03 - 使用图解的方式来解决链表的算法问题

ARTS左耳朵耗子提出来的一个打卡任务。每周一个 Algorithm,Review 一篇英文文章,总结一个工作中的技术 Tip,以及 Share 一个传递价值观的东西!我希望这个事可以给大家得到相应的算法、代码、技术和影响力的训练。

这是我的第三周打卡,标题为“使用图解的方式来解决算法问题”。这周在刷算法的时候,发现对于双指针、引用传递等问题用画图来理解的话,十分容易理解。

Algorithm

奇偶链表

描述:

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。

示例:

示例1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例2:

输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL

说明:

  • 应当保持奇数节点和偶数节点的相对顺序。

  • 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。

题解:

这个问题最直接的想法就是双指针思想来构建奇偶链表,然后把偶链表连接在奇链表的尾部。

const oddEvenList = (head) => {
if (head == null) {
return null
}
let odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
}
odd.next = evenHead
return head
};

时间复杂度:O(n)

Review

Adding pipelines to JavaScript

ES2019的提案状态有两个新语法:可选链管道语法。这篇文章主要讲的是管道语法在JavaScript中的使用。

管道操作可以使某些类型的操作变得真正易于阅读,可以举个例子直观地感受到。

//传统方式
const capitalize = (input) => input[0].toUpperCase() + input.substring(1)
const removeSpaces = (input) => input.trim()
const repeat = (input, times) => input.repeat(times)
const withoutPipe = repeat(capitalize(removeSpaces(' i am gods ')), 2)
console.log(withoutPipe)
//使用管道运算符
const withPipe = ' i am gods '
|> removeSpaces
|> capitalize
|> (str => repeat(str, 2))
console.log(withPipe)

上面的例子是对一个字符进行各种转换操作,可以看到使用管道语法后大大地减少嵌套括号的数量,阅读起来十分方便。之前在函数式编程语言 Elixir 中接触到管道操作符,在TC39提案中发现 JavaScript 也开始支持管道操作,觉得这个特性很棒。个人觉得,管道语法结合箭头函数可以在未来给 JavaScript 带来更多灵活地运用。

有一点需要注意的是,对多参数的使用发现没有像 Elixir 那样直接。如果有一个期望是两个参数的函数,则需要将其包装在一个箭头函数里。另一种方法可以使用函数柯里化来实现,如下:

const repeat = times => input => input.repeat(times)
const withPipe = ' i am gods '
|> removeSpaces
|> capitalize
|> repeat(2)

这种写法比上面就更加简洁一些了。

另外,在TC39提案的建议里,有两种新的管道模式:smart pipelineF# pipeline

F# pipeline建议十分接近简单管道,唯一的区别是允许在管道操作中使用 await 来支持异步操作

url
|> fetch
|> await
|> (res => res.json())
|> doSomeJsonOperations

smart pipeline 是借鉴 Hack 语言的。管道的输出被放到一个 # 的 token 中,以供管道右侧的表达式使用。

// With smart pipes
" string"
|> toUpper
|> # + " 😎"
|> prepend("😎 ", #)
// Without pipes
prepend(
"😎 ",
toUpper(" string") + " 😎"
)

这种方式增加了额外的语法糖,感觉理解起来没有前两种方式直接。

Tip

ssh免密登录

在开发过程中,经常要连接到远程服务器。之前在windows下开发,使用 secureCRT 这样的软件来连接到远程主机,可以记住密码。后来换到mac环境,直接在终端中用 ssh 命令去连接,比较方便,但每次都需要手动输入密码。

于是配置了下ssh的免密登录。原理和操作都十分简单,主要是利用 ssh-copy-id 命令把ssh-key的公钥上传到远程服务器来进行认证。

1. 生成秘钥

cd ~/.ssh
ssh-keygen

2. 使用 ssh-copy-id 复制到远程主机

ssh-copy-id -i .ssh/id_rsa.pub root@192.168.0.100

3. 免密登录

ssh root@192.168.0.100

Share

分享文章:使用图解的方式来解决算法问题

这周在刷奇偶链表这个算法的时候,发现把链表画出来,通过图解的方式去写算法不到1分钟就可以写完,而且没有错误。官方的题解里也说到“解决链表问题最好的办法是在脑中或者纸上把链表画出来”。有时通过这种方式比看代码要更容易理解。

发布于: 2 小时前 阅读数: 30
用户头像

jerry.mei

关注

Coding is ARTS 2019.01.03 加入

全栈工程师,目前研究领域为函数式编程、使用Vue构建大型项目、企业级项目架构

评论

发布
暂无评论
ARTS 03 - 使用图解的方式来解决链表的算法问题