PINNED


笔记汇总

根据知识点的类别进行整理

ISSUES


【算法】递归实现一个栈的逆序

【题目】 使用递归来完成一个栈的逆序操作。 【其他限制】 不能借助任何其他数据结构。 【分析】 递归思想原本就和栈这一数据结构密不可分,题目要求不能借助任何其他数据结构,故我们可能需要充分利用栈的已有特性。因此题目等价于“使用递归思想和栈操作来逆序一个栈”。 设想有一个函数getAndRemovTailElement(),其功能是获取并删除一个栈的栈底元素。对于一个栈,通过多次调用getAndRemovTailElement(),我们即可得到一个栈的逆序序列。那么,接下来我们需要将关注点放在如何将该逆序序列保存在原始栈中,也就是完成栈的逆序。 【解决方案】 首先,设计函数: int getAndRemovTailElement(…)。如下图所示: ![](http://matt.cn-bj.ufileos.com/5d663df3-62b3-4e3d-a569-454af0f9feef.jpg?UCloudPublicKey=TOKEN_4ec986be-e416-4390-95f9-169868f2a837&Signature=oejsYBrqLPmyxrF0MnQiEsO07Os%3D&Expires=1889010898) 其次,设计递归函数: void stackReverse(…),该函数将调用上述函数,最终完成一个栈的逆序。如下图所示: ![](http://matt.cn-bj.ufileos.com/800c8bc1-ff70-4582-b17b-d512dd91a36b.jpg?UCloudPublicKey=TOKEN_4ec986be-e416-4390-95f9-169868f2a837&Signature=YWWC9my%2BS0mr6ozkyga8LMduQP8%3D&Expires=1889010948) ```java public int getAndRemovTailElement(Stack<Integer> stack) { int result = stack.pop(); if (stack.IsEmpty()) // 递归结束条件 return result; int tail = getAndRemovTailElement(stack); // 返回栈底元素 stack.push(result);// 递归结束条件触发后,将弹出的非栈底元素入栈,保持栈原始结构 return tail; } } public void stackReverse(Stack<Integer> stack) { if (stack.IsEmpty()) // 递归结束条件 return; int tmp == getAndRemovTailElement(stack); // 去除栈底元素之后的栈 stackReverse(stack); // 递归调用,触发上一步操作 stack.push(tmp); // 原始栈逆序入栈 } ```
0个回复 • 0次浏览 • 2019-11-13 21:16

【算法】用栈实现队列

【题目】 编写一个算法,用栈实现一个队列。 【其他限制】 无。 【图示】 ![](http://matt.cn-bj.ufileos.com/0353a736-76d9-49a0-bf4f-8e7607eecd41.jpg?UCloudPublicKey=TOKEN_4ec986be-e416-4390-95f9-169868f2a837&Signature=6iFxrX0oDPNlhBbN0vHqGxKNcMU%3D&Expires=1889009621) 【分析】 栈结构的特点是先进后出,队列结构的特点是先进先出。对于一个无序整数序列,使用两个栈,经过进栈->出栈->进栈->出栈操作,刚好可以得到原始无序整数序列,如上图所示。 【解决方案】 具体思路:初始化两个栈StackPush和StackPop,前者仅负责入栈操作,后者仅负责出栈操作。需要注意,元素从StackPush压入StackPop中存在两个条件: a. StackPop非空时,禁止压入元素。 b. 必须一次性全部压入,否则一旦积压,最终的出栈顺序将被打乱。 ```java public class StackQueue{ private Stack<Integer> stackPush; private Stack<INteger> stackPop; public StackQueue() { this.stackPush = new Stack<Integer>(); this.stackPop = new Stack<Integer>(); } private void pushToStackPop(){ if(this.stackPop.isEmpty()){ while(!this.stackPush.isEmpty()){ this.stackPop.push(this.stackPush.pop()); } } } public void push(int element){ this.stackPush.push(element); pushToStackPop(); } public int poll() { if (this.StackPush.IsEmpty() && this.StackPop.IsEmpty()) throw new RuntimeException('Queue is empty.'); pushToStackPop(); return this.stackPop.pop(); } public int peek() { if (this.StackPush.IsEmpty() && this.StackPop.IsEmpty()) throw new RuntimeException('Queue is empty.'); pushToStackPop(); return this.stackPop.peek(); } } ```
0个回复 • 0次浏览 • 2019-11-13 21:00

【算法】最小栈的实现

【题目】 设计一个栈,其拥有常规的入栈、出栈操作外,需要额外具备获取最小元素的功能。 【其他限制】 获取最小元素功能的时间复杂度O(1)。 【图示】 给定一个无序整数序列: 3, 8, 5, 6, 9, 1, 0, 2. ![](http://matt.cn-bj.ufileos.com/a9d41364-e667-4bab-bd7e-da78f64abcf3.jpg?UCloudPublicKey=TOKEN_4ec986be-e416-4390-95f9-169868f2a837&Signature=%2B67I5qQfnQ5jQv0b7UK8NUYKPzc%3D&Expires=1889008838) 【分析】 1. 是否可以利用众所周知的栈结构及其入栈、出栈特性 答案是肯定的,现在的问题在于单靠一个栈结构是无法实现获取最小元素功能。 2. 算法时间复杂度和空间复杂度衡量? 题目要求的O(1)时间复杂度已是最优,同时也表明该算法需要采用空间换时间策略。在O(1)时间复杂度获取一个序列极值的数据结构:有序数组,哈希表,最大(小)堆。 我们可以尝试构造上面提及的三种数据结构来实现最小元素获取功能,但这个“构造的过程”明显会引入额外的时间复杂度。 【解决方案】 基于上述两方面分析,结合元素进栈/出栈操作,这里我们尝试采用一个辅助栈(MinStack)配合原始栈(MainStack)实现算法需要的新特性。其时间复杂度为O(1),空间复杂度为O(n)。 一个元素压入原始栈时,条件性压入辅助栈(目的是保存当前原始栈中值最小的元素);元素弹出原始栈时,同样需要条件性弹出辅助栈的栈顶元素(目的是确保辅助栈的栈顶元素是当前原始栈中值最小的元素)。 元素进栈操作 辅助栈MinStack为空。 元素首先压入原始栈MainStack,而后直接压入辅助栈MinStack。 辅助栈MinStack非空。 元素首先压入原始栈MainStack,而后判断该元素是否需要压入辅助栈MinStack。 此时分以下两种情况: a. 新入栈元素大于等于辅助栈栈顶元素。该元素不会被压入辅助栈。 b. 新入栈元素小于辅助栈栈顶元素。该元素需要被压入辅助栈。 此处有一个细节需要注意:入栈操作过程中及完成后,辅助栈中元素自底向上是一个递减序列。 具体分析请看下面图解: (1) 元素3压入原始栈,此时辅助栈为空,故需要同时将其压入辅助栈。后续元素8, 5, 6, 9压入原始栈时,辅助栈不会有任何入栈操作。 ![](http://matt.cn-bj.ufileos.com/d7f0bda3-1afa-4c50-b63d-29bdd65d7874.jpg?UCloudPublicKey=TOKEN_4ec986be-e416-4390-95f9-169868f2a837&Signature=yAmcjQr3zsNjPll6G5BGNOo%2FCnE%3D&Expires=1889008875) (2) 元素1压入原始栈,此时辅助栈非空。元素1小于辅助栈栈顶元素3,故元素1需要同时压入辅助栈。 ![](http://matt.cn-bj.ufileos.com/7fadbf87-9757-44dc-a7b5-8777548597ed.jpg?UCloudPublicKey=TOKEN_4ec986be-e416-4390-95f9-169868f2a837&Signature=9cvnMW71nBLvi3D1n8orv1tCN%2B0%3D&Expires=1889008940) (3) 元素0压入原始栈,此时辅助栈亦非空。元素0小于辅助栈栈顶元素1,故元素0需要同时压入辅助栈。 ![](http://matt.cn-bj.ufileos.com/8bf5e3f8-e1a9-4c69-bc0d-d90ac67e3bd4.jpg?UCloudPublicKey=TOKEN_4ec986be-e416-4390-95f9-169868f2a837&Signature=QfcVuuizpCfvDshzNcDsSljBUXo%3D&Expires=1889008967) 最后,尾元素2压入原始栈,因其大于辅助栈栈顶元素0,故无需压入辅助栈。至此算法的入栈操作完成。 元素出栈操作 出栈操作相对简单:首先弹出原始栈的栈顶元素,当该栈顶元素等于辅助栈的栈顶元素时,弹出辅助栈的栈顶元素,以此来保证辅助栈的栈顶元素永远是原始栈当前元素中最小的元素。 ```java public class EnhancedStack{ private Stack<Integer> mainStack; private Stack<Integer> minStack; public EnhancedStack(){ this.mainStack = new Stack<Integer>(); this.minStack = new Stack<Integer>(); } public void pushAction(int element){ this.mainStack.push(element); if(this.minStack.isEmpty()|| (!this.minStack.isEmpty() && element<this.minStack.peek())) this.minStack.push(element) } public int popAction(){ if(this.mainStack.isEmpty()) throw new RuntimeException("This stack is empty") int val = this.mainStack.pop(); if(val == this.minStack.peek()) this.minStack.pop(); return val; } public int getMinElement(){ if(this.minStack.isEmpty()) throw new RuntimeException("This stack is empty") return this.minStack.peek(); } } ```
0个回复 • 1次浏览 • 2019-11-13 20:51

【算法】栈排序

【题目】 使用一个辅助栈完成原始栈的排序:栈顶到栈底从大到小。 【其他限制】 允许使用一个辅助栈,可以申请变量,但不能使用其他数据结构。 【图示】 ![](http://matt.cn-bj.ufileos.com/bbd82409-ca4b-45e3-9756-251b30bb8760.jpg?UCloudPublicKey=TOKEN_4ec986be-e416-4390-95f9-169868f2a837&Signature=wgz8fslFv4Wa6kbCL1ny7I3c4Hg%3D&Expires=1889008144) 【分析】 类似汉诺塔问题,元素需要在原始栈和辅助栈之间来回出栈、入栈。首先将原始栈中元素出栈,然后条件性压入辅助栈,当新出栈元素不满足压入辅助栈条件时,可以考虑将辅助栈中元素出栈,重新压入原始栈,以此完成辅助栈中元素顺序的调换。 【解决方案】 假设待排序栈标价为Stack,辅助栈的标记为SortedStack.首先,Stack栈的栈顶元素(标记为curElement)出栈,然后尝试将其压入SortedStack栈,但需要遵从以下限制: SortedStack栈为空,直接压入; SortedStack栈非空,且curElement <= SortedStack.peek(),将curELement压入; SortedStack栈非空,但curElement > SortedStack.peek(),此时需要持续弹出SortedStack栈的顶元素直至元素curElement <= SortedStack栈最新的顶元素。 ```java public void sortStack(Stack<Interger> stack){ Stack<Integer> sortedSatck = new Stack<Integer>(); int curElement = 0; while(!stack.isEmpty()){ curElement = stack.pop(); while(!sortedStack.isEmpty()&& curElement>sortedStack.peek()){ //需要持续弹出SortedStack栈的顶元素直至元素curElement <= SortedStack栈最新的顶元素 stack.push(sortedStack.pop()); } sortedStack.push(curElement); //SortedStack栈为空,直接压入; //SortedStack栈非空,且curElement <= SortedStack.peek(),将curELement压入; } while(!sortedStack.isEmpty()){ stack.push(sortedStack.pop()) } } ```
0个回复 • 1次浏览 • 2019-11-13 20:36

vue-router-3.0.2源码解读(一)

在Vue项目中使用 vue-router时需要通过Vue.use(插件)来安装插件`Vue.use(VueRouter)`,对应的Vue.use的源码会调用VueRouter的install()方法。 ```javascript // index.js import { install } from './install' …… export default class VueRouter { static install: () => void; …… } VueRouter.install = install VueRouter.version = '__VERSION__' if (inBrowser && window.Vue) { window.Vue.use(VueRouter) } ``` 在Vue-router的入口index.js中,`VueRouter.install = install`,install方法被install.js导出。 // install.js ```javascript import View from './components/view' import Link from './components/link' export let _Vue export function install (Vue) { if (install.installed && _Vue === Vue) return install.installed = true _Vue = Vue const isDef = v => v !== undefined const registerInstance = (vm, callVal) => { let i = vm.$options._parentVnode if (isDef(i) && isDef(i = i.data) && isDef(i = i.registerRouteInstance)) { i(vm, callVal) } } Vue.mixin({ beforeCreate () { if (isDef(this.$options.router)) { this._routerRoot = this this._router = this.$options.router this._router.init(this) Vue.util.defineReactive(this, '_route', this._router.history.current) } else { this._routerRoot = (this.$parent && this.$parent._routerRoot) || this } registerInstance(this, this) }, destroyed () { registerInstance(this) } }) Object.defineProperty(Vue.prototype, '$router', { get () { return this._routerRoot._router } }) Object.defineProperty(Vue.prototype, '$route', { get () { return this._routerRoot._route } }) Vue.component('RouterView', View) Vue.component('RouterLink', Link) const strats = Vue.config.optionMergeStrategies // use the same hook merging strategy for route hooks strats.beforeRouteEnter = strats.beforeRouteLeave = strats.beforeRouteUpdate = strats.created } ``` install中导入了来自view和link的组件`View`和`Link`,并在68、69行赋于Vue的全局组件`'RouterView'`和`'RouterLink'`,此处用户即可使用Vue-Route自带组件<router-view>和<router-link>。 在Vue.mixin阶段的beforeCreate,Vue-route根据传递的参数中是否定义routes `````javascript const router = new VueRouter({ routes : …… //是否定义routes }) ````` 来对_routerRoot和_router进行挂载。 ```javascript this._routerRoot = this //此处this为Vue实例 this._router = this.$options.router this._router.init(this) ``` 此后通过Object.defineProperty方法响应式地对$router和$route进行赋值 ```javascript Object.defineProperty(Vue.prototype, '$router', { get () { return this._routerRoot._router } }) ``` 等价于`Vue.prototype.$router== this._routerRoot._router` ```javascript Object.defineProperty(Vue.prototype, '$route', { get () { return this._routerRoot._route } }) ``` 等价于`Vue.prototype.$route== this._routerRoot._route` 至此 Vue代码中可以调用`this.$router`和`this.$route`进行相应的处理
0个回复 • 5次浏览 • 2019-11-11 20:29