Kirago
Stay hungry Stay foolish!!
  • 回文链表

    回文链表 请判断一个单链表是否为回文链表 输入:1->2->1 输出:true 输入:1->2->2->1 输出:true 输入: 1->2->3 输出:false 注:空链表,单节点链表也为回文链表 考虑空间复杂度O(1),时间复杂度为O(n) 分析思路 基于链表的节点获取,只能通过遍历的形式,基于空间复杂度的情况,肯定是不能申请例如 list、map的数据结构去存储的。 通过大脑的第一反应就是找到中间节点将链表切分为 pre 前段链表、 aft 后段链表两个链表,然后将 pre 链表逆序遍历,aft 链表正序遍历,逐一比对节点值,当发现节点值不相等的时候即输出 false,否则为 true。 那么根据上面的思路,我们的解决思路总结如下: 找到中间节点 pre 逆序遍历, aft 正序遍历 节点值比对 找到中间节点 各位想想对于链表数据结构我们如何找到中间节点呢? 快慢双指针,即 fa...
    • 0
    • 25
    • 0
    • 2020-01-09
  • 相交链表

    注意: 如果两个链表没有交点,返回 null. 在返回结果后,两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。【此处由于存在时间和空间复杂度的限制,所以无法利用之前如通过HashSet 进行环形列表判断的方法,不满足空间复杂度,那么暴力遍历法也是不满足条件的】 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/intersection-of-two-linked-lists 简单理解下题目,其实可以比喻成 路程A,运动员A及路程B,运动员B,运动员A和B的跑步速度是一致的,那么在总路程相同的情况下,运动员A和运动员B在同一时间起跑,那么肯定是能够同时到达终点的。 路程引申到这里可以理解为链表长度,那么如何保证路程距离相同呢?那就是遍历到链表尾结点的话就将指针指向另...
    • 0
    • 14
    • 0
    • 2020-01-07
  • 环形链表

    给定一个链表,判断链表中是否有环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/linked-list-cycle 通过 HashSet 来存储环形链表中的索引位置。 代码如下: public class HasCycle{          public class ListNode() {         int val;         ListNode  next;         ListNode(int x) {             val = x;             next = null;         }     }     public boolean...
    • 0
    • 7
    • 0
    • 2020-01-07
  • 自定义实现循环列表

    /**  * 条件为循环数组中插入的是非负数。  */ public class MyCircularQueue {     private int[] data;     private int head, tail, size;     public MyCircularQueue(int k){         data = new int[k];         head = tail = -1;         size = k;     }     public boolean enQueue(int value) {         if(isEmpty()) {             head = 0;         }         if(isFull()) {             return false;         }         ...
    • 1
    • 14
    • 0
    • 2019-12-24
  • 爬楼梯问题

    场景需求 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 示例 1: 输入: 2 输出: 2 解释: 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 示例 2: 输入: 3 输出: 3 解释: 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶 解题分析 通过题目描述可以得知,有1阶楼梯的话 就仅仅只有1种方法, 2阶楼梯的话,我们可以第一步爬1阶,第二步爬1阶 + 第一步直接爬2阶 得到 2种解法。 3阶楼梯的话,那么方式就是 1+1+1 或者 1+2 或者 2+1 等于3种。 4阶楼梯的话 。。。。如果是这种思路的话 估计会累死 实际上只要有接触过动态规划概念的话,就会知道这种情况如何去处理了。下面聊下...
    • 1
    • 21
    • 0
    • 2019-12-19
  • 将有序数组转换为一颗高度平衡的二叉搜索树

    二叉搜索树 二叉搜索树可以是一颗空树或者具备如下特性的一棵树: 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值 任意节点的左、右子树也分别为二叉搜索树 没有键值相等的节点 一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 前置条件 给定一个数组,但此数组是有序的。 解决思路 通过结合二叉搜索树的特性可以得知,二叉搜索树通过 中序遍历之后得到的是一个有序数组。 中序输出的过程为:左节点 -> 根节点 -> 右节点 此时发现其实这是一个逆向过程,根据已有的排序数组逆向构造二叉树。 那么我们如何保证高度平衡呢? 很简单,我们是否想到了二分法?通过二分法找到根节点,然后再在二分好数组的基础上重复性的执行。 想到了重复,我们根据自己的经验学习,第一反应出现的应该是递归和迭代。此...
    • 0
    • 22
    • 0
    • 2019-12-19
  • 数据结构与算法分析系列之开篇序言

    常规性扯淡 任何代码一线开发人员在任何阶段复习数据结构,学习算法阶段都是有收获的,更何况很多时候我们并没有真正掌握这门“技巧”。 为啥 ”技巧“ 一词是带有引号,个人觉得这其实是一种思维习惯与解决问题思路吧。代码开发工作实际上就是掌握开发语言工具,通过抽象现实世界通过机器能够读懂的方式让计算机能够根据我们设计的逻辑解决实际需求问题。经历了这么多年的发展,将场景需求拆分粒度够细,最终可能都会映射到数据结构比如 数组、链表、队列、栈、树、图 等等的应用上。 其实这也是一个建模的过程,通过掌握数据结构的特性,再粘合上特定的逻辑,加上那么点数学技巧处理,我们就能够解决问题。 很多高级语言,比如 Java ,实际上在基础库已经有对应数据结构的实现,我们直接拿过来用就行了,那是不是意味着我们根本不需要再去看 数据结构和算法? 答案肯定是否定的,且不说面试的时候会被问到,有没有看过 XXX 的实现,其实...
    • 1
    • 8
    • 0
    • 2019-12-19
  • Prometheus 入门及进阶

    欢迎大家订阅本人维护的微信公众号或者今日头条头条号,第一时间获取分享:)。 Warning!!!内容较多备好板凳与瓜子矿泉水!! 参考1 参考2 什么是TSDB? TSDB(Time Series Database)时序列数据库,我们可以简单的理解为一个优化后用来处理时间序列数据的软件,并且数据中的数组是由时间进行索引的。 时间序列数据库的特点 大部分时间都是写入操作。 写入操作几乎是顺序添加,大多数时候数据到达后都以时间排序。 写操作很少写入很久之前的数据,也很少更新数据。大多数情况在数据被采集到数秒或者数分钟后就会被写入数据库。 删除操作一般为区块删除,选定开始的历史时间并指定后续的区块。很少单独删除某个时间或者分开的随机时间的数据。 基本数据大,一般超过内存大小。一般选取的只是其一小部分且没有规律,缓存几乎不起任何作用。 读操作是十分典型的升序或者降序的顺序读。 高并发的读操作十分常...
    • 0
    • 55
    • 0
    • 2019-08-16
  • 编译Linux内核源码

    此文算是水文一篇了,还是很早以前突发心思搞下 Linux 内核编译时记录的,感觉可装X。。。 欢迎大家订阅本人维护的微信公众号或者今日头条头条号,第一时间获取分享:)。 升级一些依赖包 yum install -y rpm-build redhat-rpm-config asciidoc hmaccalc perl-ExtUtils-Embed pesign xmlto yum install -y audit-libs-devel binutils-devel elfutils-devel elfutils-libelf-develsudo yum install -y ncurses-devel newt-devel numactl-devel pciutils-devel python-devel zlib-devel bison 创建源码的编译书目录及目的源码存放地址 mkdi...
    • 0
    • 23
    • 2
    • 2019-08-16
  • Kubernetes 使用Prometheus 搭建监控平台

    欢迎大家订阅本人维护的微信公众号或者今日头条头条号,第一时间获取分享:)。 转载自阳明老哥技术blog,发现其中有部分问题加上自己实践踩坑 本人维护的yaml配置文件链接 一般情况下我们是直接通过Dashboard的资源统计图标进行观察的,但是很显然如果要上到生产环境,就需要更自动化的方式来对集群、Pod甚至容器进行监控了。Kubernetes内置了一套监控方案:influxdb+grafana+heapster。但由于之前我们的应用的业务监控使用的是Prometheus,所以这里准备使用Prometheus来完成k8s的集群监控。 Prometheus 简介 Prometheus是SoundCloud开源的一款开源软件。它的实现参考了Google内部的监控实现,与源自Google的Kubernetes结合起来非常合适。另外相比influxdb的方案,性能更加突出,而且还内置了报警功能。它...
    • 2
    • 42
    • 0
    • 2019-08-16
文章分组
暂无数据