暂时未有相关云产品技术能力~
10年Java开发经验,图书《漫画算法》作者,微信公众号【程序员小灰】运营者,全网粉丝超过100万,擅长Java语言和数据结构
和小灰所遇到的问题类似,旅行商问题所描述的是这样一个场景: 有一个商品推销员,要去若干个城市推销商品。该推销员从一个城市出发,需要经过所有城市后,回到出发地。每个城市之间都有道路连通,且距离各不相同,推销员应该如何选择路线,使得总行程最短呢?
对于偶数长度的数组,可以根据中位数分成长度相等的两部分,左半部分最大元素(6),永远小于等于右半部分的最小元素(7)。 对于奇数长度的数组,同样可以根据中位数分成两部分:
人们如何进行扑克牌的排序呢? 举个例子,比如我手中有红桃6,7,9,10这四张牌,已经处于升序排列:这时候,我又抓到了一张红桃8,如何让手中的五张牌重新变成升序呢?用冒泡排序,选择排序,亦或是快速排序?
旋转点是什么呢?我们这里规定,假设旋转有序数组恢复为普通有序数组,位于普通有序数组第一个位置的元素,就是旋转数组的旋转点。 直白地说,旋转点就是旋转数组中最小的元素:
如果我们把场景转换成最初的面试问题:在包含1000个整型元素的有序数组中查找某个特定整数,又该如何去做呢?
给定蛋糕大小的集合cakes,给定顾客饭量的集合mouths,如何计算出这些蛋糕可以满足的最大顾客数量?
下面我们来看一看Floyd算法的详细步骤。
如何求得最短路径的详细节点,而不仅仅是距离?
深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。
微信中,许许多多的用户组成了一个多对多的朋友关系网,这个关系网就是数据结构当中的图(Graph)。
如何进行加密呢?古人想出了一种非常朴素的加密方法,被称为凯撒密码。加密的原理就像下图这样。
让我们从链表头部开始,建立三个临时节点的引用,分别为p1,p2,p3。它们分别指向头节点、第二个节点、第三个节点。
题目是什么意思呢?比如给定的无序数组如下: 如果 k=6,也就是要寻找第6大的元素,这个元素是哪一个呢? 显然,数组中第一大的元素是24,第二大的元素是20,第三大的元素是17 ...... 第6大的元素是9。
1.持久节点 (PERSISTENT) 默认的节点类型。创建节点的客户端与zookeeper断开连接后,该节点依旧存在 。 2.持久节点顺序节点(PERSISTENT_SEQUENTIAL) 所谓顺序节点,就是在创建节点时,Zookeeper根据创建的时间顺序给该节点名称进行编号:
分布式锁的实现有哪些? 1.Memcached分布式锁 利用Memcached的add命令。此命令是原子性操作,只有在key不存在的情况下,才能add成功,也就意味着线程得到了锁。 2.Redis分布式锁 和Memcached的方式类似,利用Redis的setnx命令。此命令同样是原子性操作,只有在key不存在的情况下,才能set成功。(setnx命令并不完善,后续会介绍替代方案)
Zookeeper的数据模型,Zookeeper的数据模型是什么样子呢?它很像数据结构当中的树,也很像文件系统的目录。 树是由节点所组成,Zookeeper的数据存储也同样是基于节点,这种节点叫做Znode。 但是,不同于树的节点,Znode的引用方式是路径引用,类似于文件路径。
什么是蓝绿部署? 蓝绿部署,英文名Blue Green Deployment,是一种可以保证系统在不间断提供服务的情况下上线的部署方式。 如何保证系统不间断提供服务呢? 蓝绿部署的模型中包含两个集群,就好比海豚的左脑和右脑。
什么是分布式事务?分布式事务用于在分布式系统中保证不同节点之间的数据一致性。分布式事务的实现有很多种,最具有代表性的是由Oracle Tuxedo系统提出的XA分布式事务协议。
熔断这一概念来源于电子工程中的断路器(Circuit Breaker)。在互联网系统中,当下游服务因访问压力过大而响应变慢或失败,上游服务为了保护系统整体的可用性,可以暂时切断对下游服务的调用。
数据库和数据仓库之间的关系。如果说,那个世界的每一个生命个体都是一条数据记录,那么普通的魔戒的地位就好比是数据库,而至尊魔戒的地位就好比是数据仓库。
缺点一:项目过于臃肿,当大大小小的功能模块都集中在同一项目的时候,整个项目必然会变得臃肿,让开发者难以维护。 缺点二:资源无法隔离,就像刚刚小灰的经历一样,整个单体系统的各个功能模块都依赖于同样的数据库、内存等资源,一旦某个功能模块对资源使用不当,整个系统都会被拖垮。
什么是进程和线程有一定基础的小伙伴们肯定都知道进程和线程。 进程是什么呢?直白地讲,进程就是应用程序的启动实例。比如我们运行一个游戏,打开一个软件,就是开启了一个进程。 进程拥有代码和打开的文件资源、数据资源、独立的内存空间。
这一期我们来深入介绍之前遗留的两个问题:1. Java当中CAS的底层实现2. CAS的ABA问题和解决方法.
大整数相乘又是如何实现的呢? 起初,小灰认为只要按照大整数相加的思路稍微做一下变形,就可以轻松实现大整数相乘。但是随着深入的学习,小灰才发现事情并没有那么简单......
用户信息当然是存在数据库里。但是由于我们对用户系统的性能要求比较高,显然不能每一次请求都去查询数据库。 所以,小灰在内存中创建了一个哈希表作为缓存,每次查找一个用户的时候先在哈希表中查询,以此提高访问性能。
既然我们拥有两个栈,那么我们可以让其中一个栈作为队列的入口,负责插入新元素;另一个栈作为队列的出口,负责移除老元素。队列的主要操作无非有两个:入队和出队。在模拟入队操作时,每一个新元素都被压入到栈A当中。
让我们先来回顾一下计数排序: 计数排序需要根据原始数列的取值范围,创建一个统计数组,用来统计原始数列中每一个可能的整数值所出现的次数。
如何给无序的随机整数排序呢? 非常简单,让我们遍历这个无序的随机数列,每一个整数按照其值对号入座,对应数组下标的元素进行加1操作。 比如第一个整数是9,那么数组下标为9的元素加1
队列的特点是什么?聪明的小伙伴们都知道,是先进先出(FIFO)。那么,优先队列又是什么样子呢? 优先队列不再遵循先入先出的原则,而是分为两种情况: 最大优先队列,无论入队顺序,当前最大的元素优先出队。 最小优先队列,无论入队顺序,当前最小的元素优先出队。
在上一篇漫画中,小灰介绍了 二叉堆 这样一种强大的数据结构: 漫画:什么是二叉堆?(修正版) 那么,这个二叉堆怎样来使用呢?我们这一期将会详细讲述。
什么是二叉堆?二叉堆本质上是一种完全二叉树,它分为两个类型:1.最大堆2.最小堆 什么是最大堆呢?最大堆任何一个父节点的值,都大于等于它左右孩子节点的值。
时间复杂度的意义,究竟什么是时间复杂度呢?让我们来想象一个场景:某一天,小灰和大黄同时加入了一个公司......一天过后,小灰和大黄各自交付了代码,两端代码实现的功能都差不多。大黄的代码运行一次要花100毫秒,内存占用5MB。小灰的代码运行一次要花100秒,内存占用500MB。
同冒泡排序一样,快速排序也属于交换排序,通过元素之间的比较和交换位置来达到排序的目的。不同的是,冒泡排序在每一轮只把一个元素冒泡到数列的一端,而快速排序在每一轮挑选一个基准元素,并让其他比它大的元素移动到数列一边,比它小的元素移动到数列的另一边,从而把数列拆解成了两个部分。
昨天小灰发布的漫画中存在一些勘误,所以今天重新发布一篇修订版,修正了代码当中的一些细节问题。在上一篇漫画中,小灰介绍了冒泡排序的思路和几种变化:漫画:什么是冒泡排序?那么,鸡尾酒排序又是何方神圣呢?我们这一期将会详细讲述。
什么是冒泡排序?冒泡排序的英文Bubble Sort,是一种最基础的交换排序。 大家一定都喝过汽水,汽水中常常有许多小小的气泡,哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻,所以小气泡可以一点一点向上浮动。
在上一篇漫画中,小灰介绍了一道有趣的智力题:漫画:有趣的扔鸡蛋问题那么,如何利用动态规划来求出扔鸡蛋问题的通解? 换句话说,有M层楼 / N个鸡蛋,要找到鸡蛋摔不碎的临界点,需要尝试几次?
扔鸡蛋问题,有2个鸡蛋,从100层楼上往下扔,以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎,在第10层摔碎了,那么鸡蛋不会摔碎的临界点就是9层。
什么是拜占庭将军问题?在很久很久以前,拜占庭是东罗马帝国的首都。那个时候罗马帝国国土辽阔,为了防御目的,因此每个军队都分隔很远,将军与将军之间只能靠信使传递消息。
发出一个固定金额的红包,由若干个人来抢,需要满足哪些规则?所有人抢到金额之和等于红包金额,不能超过,也不能少于。每个人至少抢到一分钱。要保证所有人抢到金额的几率相等。
给定一个正整数,实现一个方法来求出离该整数最近的大于自身的“换位数”。什么是换位数呢?就是把一个整数各个数位的数字进行全排列,从而得到新的整数。例如53241和23541。
国际象棋中的皇后,可以横向、纵向、斜向移动。如何在一个8X8的棋盘上放置8个皇后,使得任意两个皇后都不在同一条横线、竖线、斜线方向上?让我们来举个栗子,下图的绿色格子是一个皇后在棋盘上的“封锁范围”,其他皇后不得放置在这些格子: 下图的绿色格子是两个皇后在棋盘上的“封锁范围”,其他皇后不得放置在这些格子: 那么,如何遵循规则,同时放置这8个皇后呢?让我们来看看小灰的回答。
整个优惠券中心分为前端和后端,小灰所负责的是后端RPC接口的开发。接口中包含“查券”和“领券”两个方法,项目大体结构如下。
如何每隔一段时间让抢购按钮自动被点击呢?很简单,原生Javascript当中有一个定时器函数 setInterval,该函数有两个参数,第一个参数是想要执行的回调函数,第二个参数是触发执行的间隔时间(单位毫秒),抢月饼脚本简单的实现。
机器学习按照方式不同主要分为三大类,有监督学习(Supervised learning)、无监督学习(Unsupervised learning)以及半监督学习(Semi-supervised learning)。
架构师英文architect,这个词源于建筑学。软件工程当中的架构师和建筑工程当中建筑师有许多相通之处,都是负责“产品”宏观的架构设计。 在一个团队里,架构师充当了技术Leader的角色,不仅要完成项目的整体设计和规划,还要带领技术团队一起解决实际问题,攻克技术难点,使得软件的设计、开发、测试、发布流程得以顺利完成。
为什么这样写呢?我们来解释几个关键点: 1.要想让一个类只能构建一个对象,自然不能让它随便去做new操作,因此Signleton的构造方法是私有的。 2.instance是Singleton类的静态成员,也是我们的单例对象。它的初始值可以写成Null,也可以写成new Singleton()。至于其中的区别后来会做解释。 3.getInstance是获取单例对象的方法。
如果是没有商品名称的全量查询怎么办?总不可能把数据库里的所有记录全查出来吧,而且还要支持不同字段的排序。 所以,只能提前在内存中存储有序的全量商品集合,每一种排序方式都保存成独立的集合,每次请求的时候按照请求的排序种类,返回对应的集合。
题目: 有一座高度是10级台阶的楼梯,从下往上走,每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。 比如,每次走1级台阶,一共走10步,这是其中一种走法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。
题目:实现一个栈,带有出栈(pop),入栈(push),取最小元素(getMin)三个方法。要保证这三个方法的时间复杂度都是O(1)。
题目:一个无序数组里有99个不重复正整数,范围从1到100,唯独缺少一个整数。如何找出这个缺失的整数?