维新工坊

前面，我们学习了 栈的实现及其应用 ，今天我们基于栈，来实现一个简单的计算器功能。 简单计算器实现 Leetcode 224. Basic Calculator 实现一个能够对简单的表达式进行计算的基础计算器。 表达式字符串包含括号 ( 、)，加号 (+)，减号 (-)，非负整数以及空格 (‘ ‘)。 Example 1: 12Input: "1 + 1"Output: 2 Example 2: 12Input: " 2-1 + 2 "Output: 3 Example 3: 12Input: "(1+(4+5+2)-3)+(6+8)"Output: 23 使用两个栈来实现根据 栈的实现及其应用 中学到的表达式求值的解法： 编译器会使用两个栈来实现，一个栈用来保存操作数，另一个栈用来保存运算符。从左向右遍历表达式，遇到数字直接压入操作数栈，遇到操作符，就与运算符栈顶元素进行比较。 如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压 ...

前面，我们实现了两种常见的线性表 —— 顺序表 和 链表 ，本篇我们来介绍另外一种常用的线性表 —— 栈。 声明：本篇为极客时间《 数据结构与算法之美 》专栏《 栈 》这一部分的学习笔记，部分内容摘抄自专栏文章。 栈定义线性表中的一种特殊数据结构，数据只能从固定的一端插入数据或删除数据，另一端是封死的。 特点 FILO（First In Last Out）: 先进后出； 栈满还存会 “上溢”，栈空再取会 “下溢”； “上溢”：在栈已经存满数据元素的情况下，如果继续向栈内存入数据，栈存储就会出错。 “下溢”：在栈内为空的状态下，如果对栈继续进行取数据的操作，就会出错。 分类顺序栈特点 采用数组实现，数据在物理结构上保持连续性。 代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485 ...

前面，我们实现了 删除单链表倒数第 N 个节点 操作，本篇来聊聊，如何求一个链表的中间节点。 求链表的中间结点 Leetcode 876. Middle of the Linked List 给定一个非空的单链表，要求返回它的中间节点，如果中间节点有两个则返回第二个。 例如： 12Input: [1,2,3,4,5]Output: Node 3 from this list 12Input: [1,2,3,4,5,6]Output: Node 4 from this list 解法一第一种解法的思路比较容易想得到，先计算出链表的总长度，再计算出中间节点的下标，然后得遍历得到对应的节点即可。 代码12345678910111213141516171819202122232425262728293031/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; ...

前面，我们实现了 两个有序链表的合并 操作，本篇来聊聊，如何删除一个链表的倒数第 N 个节点。 删除单链表倒数第 N 个节点 Leetcode 19. Remove Nth Node From End of List 给定一个单链表，如: 1->2->3->4->5，要求删除倒数第 N 个节点，假设 N = 2，并返回头节点。 则返回结果：1->2->3->5 . 解法一这一题的难度标记为 medium，解法一比较容易想出来，我个人觉得难度不大。 思路循环两遍： 先遍历一遍，求得整个链表的长度。 再遍历一遍，当总长度 len 减去 n ，恰好等于循环的下标 i 时，就找到对应要删除的目标元素，将 prev 节点与 next 节点连接起来即可。 代码12345678910111213141516171819202122232425262728293031323334353637383940414243/** * Definition for singly-linked list. * public class ListNode { * ...

前面，我们实现了链表的 环检测 操作，本篇来聊聊，如何合并两个有序链表。 有序链表合并 Leetcode 21. Merge Two Sorted Lists 示例12Input: 1->2->4, 1->3->4Output: 1->1->2->3->4->4 使用虚假的 Head 节点定义一个临时虚假的 Head 节点，再创建一个指向 tail 的指针，以便于在尾部添加节点。 对 ListNode1 和 ListNode2 同时进行遍历，比较每次取出来的节点大小，并绑定到前面 tail 指针上去，直到最终所有的元素全部遍历完。 最后，返回 dummyNode.next ，即为新链表的 head 节点。 代码12345678910111213141516171819202122232425262728293031323334353637383940/** * Definition for singly-linked list. * public class ListNode { * int val; * ...

前面，我们实现了链表的 反转 操作，本篇来聊聊，如何检测单链表中的环。 单链表环检测 Leetcode 141. Linked List Cycle 有两种方法来解决这个问题： 使用 Hashing思路定义一个 Map，当循环遍历 Linked List 时，依次将 Node 放入 Map 中，等到循环到下一轮时，检查 Node 是否存在于 Map 中，若存在则表示有环存在。 实现12345678910111213141516171819202122232425/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public boolean hasCycle(ListNode head) { Map map ...

前面我们实现了几种常见的 链表 ，接下来，我们来聊聊如何实现 单链表 的反转。 链表反转 Leetcode 206: Reverse Linked List 示例： 12345Input: 1->2->3->4->5->NULLOutput: 5->4->3->2->1->NULLInput: NULLOutput: NULL 我们可以通过循环遍历和递归这两种方式来实现链表的反转。 遍历思路定义三个指针，分别为 prev、curr、next，然后遍历所有 node 结点，并移动这三个指针，改变 curr 结点的 next 指向，指向 prev 结点，实现 linkedList 的反转。 代码实现123456789101112131415161718192021222324/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) ...

链表定义逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储。 由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向 NULL (空)）。这种结构成为 “单向链表 “。 在单向链表的基础上，给各个结点额外配备一个指针变量，用于指向每个结点的直接前趋元素。这样的链表被称为 “双向链表” 或者 “双链表”。 当单向链表的尾部数据指向头部数据时，就构成了单向循环链表。 当双向链表的头部和尾部相互指向时，就构成了双向循环链表。 单向链表单向链表在插入元素、删除元素时，需要获取前驱元素，需要从 head 开始遍历，时间复杂度为 O (n)。 根据 index 查询对应元素，也需要从 head 开始遍历，时间复杂度为 O (n)。 代码实现12345678910111213141516171819202122232425262728293031323334353637383 ...

线性表定义将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。 线性，是指数据在逻辑结构上具有线性关系。 分类逻辑结构上相邻的数据在物理结构存储分两种形式： 数据在内存中集中存储，采用顺序表示结构，称为” 顺序存储”； 数据在内存中分散存储，采用链式表示结构，称为” 链式存储”； 顺序表定义逻辑上具有线性关系的数据按照前后的次序全部存储在一整块连续的内存空间中，之间不存在空隙，这样的存储结构称为顺序存储结构。 使用线性表的顺序存储结构生成的表，称为顺序表。 实现顺序表的存放数据的特点和数组一样，所以我们这里采用数组来实现，这里我们来用数组来简单实现 Java 中常用的 ArrayList。 接口定义： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283package one.wangwei.algorit ...

原文：链接 作者：Benjamin Winterberg 翻译：Wang Wei Java11 已于 2018/09/25 成功发布，不过目前 绝大多数人 在生产环境仍旧使用的是 Java 8。这篇以案例为主的教程涵盖了从 Java 9 到 Java 11 的绝大多数重要的语法与 API 特性。让我们开始吧！ 局部变量类型推断Java 10 引入了一个新的语言关键字 var，它可以在声明局部变量 时替换类型信息（ 局部 意味着方法体内的变量声明）。 Java 10 之前，变量的声明形式如下： 1String text = "Hello Java 9"; 现在，你可以使用 var 替换 String 。编译器将会从变量的赋值中推断出它的正确类型。在这个例子里 变量 text 即为 String 类型： 1var text = "Hello Java 10"; 不同于 Javascript 中的 var 关键字，Java 中的 var 声明的变量仍旧是静态类型。你不能再次赋予另一个与原类型不符的变量值。 12var text = "Hello Java 11";text ...