Ink's Blog

Less is more

「剑指 Offer」面试题 7:用两个栈实现队列

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 队列特点是先进先出,栈的特点是先进后出,所以我们需要两个栈来达到负负为正的效果,即元素先进入第一个栈,再进入第二个栈,然后再出来,最终的顺序仍然是先进先出。 import java.util.Stack;public class Solution { Stack<Integer&g......

「剑指 Offer」面试题 6:重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1, 2, 4, 7, 3, 5, 6, 8} 和中序遍历序列 {4, 7, 2, 1, 5, 3, 8, 6},则重建出如下图所示的二叉树并返回它的头结点。 首先了解一下二叉树:有一个根结点,根结点下面最多有两个子结点,分别是左右子结点,二叉输的遍历......

「剑指 Offer」面试题 5:从尾到头打印链表

输入一个链表的头结点,从尾到头反过来打印出每个结点的值。 想要遍历一个链表,那么必然是从头开始依次遍历,现在要实现的是从尾到头,顺序反过来了,我们可以想一想有没有数据结构跟这种情况很类似呢?从头到尾变成从尾到头,是不是一种典型的后进先出的形式?可以使用栈来轻松地解决这道题。 /*** public class ListNode {* int val;* ......

「剑指 Offer」面试题 4:替换空格

实现一个函数,把字符串中的每个空格替换成 %20。例如输入 We are happy.,则输出 We%20are%20happy.。 这个题目很简单,不用 replace 函数来做直接进行替换有两种方式。第一种是从前往后依次遍历,每次遇到空格把空格替换成 %20,然后把空格后面的元素全部后移 2 位,这样的时间复杂度是 O(n²)。第二种方式是从后往前遍历,首先计算出替换后字符串的长度,......

「剑指 Offer」面试题 3:二维数组中的查找

题目:完成一个函数,输入一个二维数组和一个整数,判断数组中是否含有该整数。这个二维数组的结构是,每一行从左到右递增,每一列从上到下递增。 思路数组的结构是从上到下递增从左到右递增,我们可以从右上角开始往左下角移动: 若当前值与目标值相等,说明这个值存在,over 若当前值比目标值大,由于从上到下递增,所以所在列的值都会比目标值大,左移一列 若当前值比目标值小,由于从左到右递增,所以所......

「剑指 Offer」面试题 2:实现 Singleton 模式

题目:设计一个类,我们只能生成该类的一个实例。 什么是 Singleton?单例模式的定义很简单:提供一个全局可以访问的唯一变量。 那么为什么需要单例模式呢?对于某些类创建时需要消耗很多资源,例如数据库连接、日志类、配置类等全局都需要的并且占用很多资源的类,我们就希望节能减排多次利用,这个时候就应当采用单例模式。 那么我们如何实现一个类可以被全局访问到并且具有唯一变量呢?首先这个类需要提......

「剑指 Offer」刷题笔记

准备用一个月时间在牛客网上刷完剑指 Offer,每天两道题,立此贴为证,别被打脸哦,下个月 23 号来检验成果,我希望看到完整的笔记链接! 面试题 02:实现 Singleton 模式面试题 03:二维数组中的查找面试题 04:替换空格面试题 05:从尾到头打印链表面试题 06:重建二叉树面试题 07:用两个栈实现队列面试题 08:旋转数组的最小数字面试题 09:斐波那契数列面试题 10......

Spark 部署要点

写完一个 Spark 应用程序以后,如何把它部署到集群上运行呢,这个部署的过程是怎样的呢,这里我主要以 Yarn 集群为主来讲解。 基本术语让我们先了解一下 Spark 中常用的一些基本术语: 术语 含义 Application 用户创建的 Spark 应用,会在集群中形成 driver 进程和 executor 进程。 Application jar 包含用户 Spa......

Designing Data-Intensive Applications 读书笔记(II)

数据模型和查询语言

...

ReentrantReadWriteLock 使用

ReentrantReadWriteLock 提供了读写锁机制可以方便我们更好实现并发场景,首先明确读写锁地特征:读锁与读锁不互斥,写锁与读锁互斥,写锁与写锁互斥。 依据此,我们就可以应用在这样地场景下:如果多个线程可以并行跑,那么我们就可以给它们都分配读锁;如果某个线程必须阻塞其他所有线程开跑,那我们就给它设置写锁。 用一个例子来讲解一下,现在共有四个线程,其中三个可以并行跑,一个必须阻塞......