11.栈的最小值
请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
解题
/**
* initialize your data structure here.
*/
var MinStack = function() {
this.normalStack = []; //定义一个数组，存放正常数据
this.minStack = [Infinity]; //定义辅助数组，存放最小值。 存入默认第一位元素，Infinity正无穷大值，用于第一次比较。
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.normalStack.push(x); //正常数据存放push
this.minStack.push(Math.min(this.minStack[this.minStack.length-1],x)); //每次将当前最小值数组的最后一项与当前要添加的数据进行比较，最后存入最小值。这样存放，每次最后一个都是当前存放数据内最小的那个值。如果当前存放值没有小于已有最小值，则将已有最小值再添加一遍，以便和normalStack保持相同长度，便于之后pop操作。
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
this.normalStack.pop(); //正常删减一位数据
this.minStack.pop();
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.normalStack[this.normalStack.length-1] //返回当前数组的最后一位，即top
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return this.minStack[this.minStack.length-1]; //返回当前最小值数组的最后一位，即为当前数据的最小值。
};
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/
12.化栈为队
实现一个MyQueue类，该类用两个栈来实现一个队列。
示例：
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明：
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
解题
/**
* Initialize your data structure here.
栈 先进后出
队列 先进先出
*/
var MyQueue = function() {
//默认定义两个队列 一个正常进栈队列 一个保存出栈的数据
this.stackIn = [];
this.stackOut = [];
};
/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {
//正常push 往进栈队列添加数据
this.stackIn.push(x);
};
/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function() {
//将进栈队列的数据反向加入到出栈队列 默认保留一位 即为需要pop出栈的数据。符合先进先出的队列特点
//此处将length设置为>1 是因为pop需要删除一位元素，所以首位直接不加入作为结果返回，之后导回数据也不会代入该数据
while(this.stackIn.length >1){
this.stackOut.push(this.stackIn.pop());
}
//先进的队列数据 也就是进栈队列的首位
let result = this.stackIn.pop();
//反向操作数据之后，再将剩余数据按照出栈数据的反向即为进栈数据的正向重新回到进栈队列
while(this.stackOut.length){
this.stackIn.push(this.stackOut.pop());
}
//返回结果
return result;
};
/**
* Get the front element.
* @return {number}
*/
MyQueue.prototype.peek = function() {
//获取队列第一位元素
//同样将入栈数据反向加入出栈数据
while(this.stackIn.length){
this.stackOut.push(this.stackIn.pop());
}
//队列的第一项即为出栈数据的最后一位
let result = this.stackOut[this.stackOut.length-1];
//再次将出栈数据反向导回到入栈数据
while(this.stackOut.length){
this.stackIn.push(this.stackOut.pop())
}
return result;
};
/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
//如果出栈数据和入栈数据都为空 则队列为空 ！！！！！
//此处我认为判断入栈数据stackIn的length即可以判断队列是否为空，因为每次push都是只push入栈队列，不会影响出栈队列，最后每次pop和peek都是以入栈队列数据为标准，反向添加到出栈队列数据之后每次又会将出栈队列数据清空再次导回入栈队列。所以如果入栈队列数据都为空，出栈队列数据更不可能有值。
return !this.stackIn.length && !this.stackOut.length;
};
//原理就是使用两个数组，模拟队列，队列特点，先进先出，所以每次将正常入栈数据反向导入到出栈数据，这样出栈数据就是符合先进先出的队列数据。之后等取完数据结果，再将数据反向导回到入栈数据，保持入栈数据的正常存放。
/**
* Your MyQueue object will be instantiated and called as such:
* var obj = new MyQueue()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.peek()
* var param_4 = obj.empty()
*/
13.节点间通路
节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
示例1:
输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
输出：true
//0开头 0-1 0-2 这样的话第一个节点0到target节点尾部2直接存在连线即路径
示例2:
输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
输出 true
//0开头 0-1 0-2 0-4 这样的话第一个节点0到target节点尾部4直接存在连线即路径
提示：
节点数量n在[0, 1e5]范围内。
节点编号大于等于 0 小于 n。
图中可能存在自环和平行边。
（1）自环边（self-loop）：一个顶点到这个顶点自身的边
（2）平行边（parallel-edges）：两个顶点之间存在多条边相连接。
img
解题
/**
* @param {number} n
* @param {number[][]} graph
* @param {number} start
* @param {number} target
* @return {boolean}
*/
var findWhetherExistsPath = function (n, graph, start, target) {
//如果开始值等于结尾值，说明是自环边，即存在路径
if (start === target) return true;
//创建一个set集合 将开始节点放入
const set = new Set([start]);
//用来记录set的值，如果最后遍历完数据，依旧没有找到尾部节点，则返回false
let count = 1;
//创建一个循环
while (true) {
//遍历数据 如果当前节点的首位已经放入，则判断尾位是不是要找的target值，如果是则返回true。即找到了target。
for (const item of graph) {
//这里判断item[0] 在不在set中，也就是start是不是等于item[0]，这里就是判断item[1]和target直接存不存在连线
//！！！疑惑为什么放进去item[1] 这样的话start就不是唯一可判断元素的，这种还算start到target么？？？
if (set.has(item[0])) {
if (item[1] === target) return true;
set.add(item[1])
}
}
if (set.size > count) {
count = set.size;
} else {
return false;
}
}
};
14.化栈为队
面试题 03.01. 三合一
三合一。描述如何只用一个数组来实现三个栈。
你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标，value表示压入的值。
构造函数会传入一个stackSize参数，代表每个栈的大小。
示例1:
输入：
["TripleInOne", "push", "push", "pop", "pop", "pop", "isEmpty"]
[[1], [0, 1], [0, 2], [0], [0], [0], [0]]
输出：
[null, null, null, 1, -1, -1, true]
说明：当栈为空时`pop, peek`返回-1，当栈满时`push`不压入元素。
示例2:
输入：
["TripleInOne", "push", "push", "push", "pop", "pop", "pop", "peek"]
[[2], [0, 1], [0, 2], [0, 3], [0], [0], [0], [0]]
输出：
[null, null, null, null, 2, 1, -1, -1]
提示：
0 <= stackNum <= 2
解题
/**
* @param {number} stackSize
*/
//创建一个存放三个栈的数组 之后使用stackNum来标识每个栈 同时操作对应栈的数据 size标识每个栈的大小 但是题解中并未用到这个数据！！！
var TripleInOne = function(stackSize) {
this.stack = []
this.size = stackSize
};
/**
* @param {number} stackNum
* @param {number} value
* @return {void}
*/
//判断当前stackNum下的栈是否创建 没有则赋值默认空数组 之后再将新数据push到数组中
TripleInOne.prototype.push = function(stackNum, value) {
if(!this.stack[stackNum]){
this.stack[stackNum] = []
}
if(this.stack[stackNum].length < this.size){
this.stack[stackNum].push(value)
}
};
/**
* @param {number} stackNum
* @return {number}
*/
//删除一位 判断当前stackNum下的栈是否已创建且长度合法 若符合则pop
TripleInOne.prototype.pop = function(stackNum) {
if(this.stack[stackNum] && this.stack[stackNum].length){
return this.stack[stackNum].pop()
}
return -1
};
/**
* @param {number} stackNum
* @return {number}
*/
//获取栈顶数据 判断当前stackNum下的栈是否已创建且长度合法 则返回当前数组的栈顶数据 也就是数组最后一位
TripleInOne.prototype.peek = function(stackNum) {
if(this.stack[stackNum] && this.stack[stackNum].length){
return this.stack[stackNum][this.stack[stackNum].length - 1]
}
return -1
};
/**
* @param {number} stackNum
* @return {boolean}
*/
//判断当前stackNum下的栈是否已创建或者长度是否合法
TripleInOne.prototype.isEmpty = function(stackNum) {
return !this.stack[stackNum] || !this.stack[stackNum].length
};
/**
* Your TripleInOne object will be instantiated and called as such:
* var obj = new TripleInOne(stackSize)
* obj.push(stackNum,value)
* var param_2 = obj.pop(stackNum)
* var param_3 = obj.peek(stackNum)
* var param_4 = obj.isEmpty(stackNum)
*/
15.栈排序
栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
示例1:
输入：
["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
输出：
[null,null,null,1,null,2]
示例2:
输入：
["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
输出：
[null,null,null,null,null,true]
说明:
栈中的元素数目在[0, 5000]范围内。
解题
//定义一个二维数据，一个用来存放正常数据，一个用来作为辅助栈存放最小值
var SortedStack = function() {
this.a = [[], []]
};
SortedStack.prototype.push = function(val) {
while(this.isEmpty() === false && this.peek() < val) this.a[1].push(this.a[0].pop())
this.a[0].push(val)
while(this.a[1].length) this.a[0].push(this.a[1].pop())
}
SortedStack.prototype.pop = function() {
this.a[0].pop()
};
SortedStack.prototype.peek = function() {
return this.a[0][this.a[0].length - 1] || -1
};
SortedStack.prototype.isEmpty = function() {
return this.a[0].length === 0
};
舍弃数组方法，只用栈push和pop。需保持栈从大到小顺序，pop才能删除最小值
push时，从栈中pop值，不丢，存到辅助栈。直到最小值<新值
将新值push到栈中。再将辅助栈中的值push回来
16.最小高度树
给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
解题
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
//长度为0则返回null
if(nums.length==0) return null;
//使用二分法搜索
let midIndex=Math.floor(nums.length/2);
//根元素也就是中间元素使用数据中心
let root=new TreeNode(nums[midIndex]);
//递归会一直将数据遍历完成直到length为0
//使用递归遍历二分左边数据
root.left=sortedArrayToBST(nums.slice(0,midIndex));
//使用递归遍历二分右边数据
root.right=sortedArrayToBST(nums.slice(midIndex+1));
return root;
};
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
2 4 3
5 6 4
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
解题
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
let addOne = 0 //用来存储当前相加结果是否大于10，大于10则下一位进1，否则保持不动为0
let sum = new ListNode('0') //用来存储结果，默认给一个0起始的头节点
let head = sum //将指针移动到结果链表开始处
while (addOne || l1 || l2) { //判断链表是否遍历完成 加入addOne的目的是防止链表最后两位数据相加后未将结果存储
let val1 = l1 !== null ? l1.val : 0 //遍历链表1 如果对应索引没有值 则默认赋值0
let val2 = l2 !== null ? l2.val : 0 //遍历链表2 如果对应索引没有值 则默认赋值0
let r1 = val1 + val2 + addOne //结果相加 赋值给下一节点
addOne = r1 >= 10 ? 1 : 0 //判断当前相加结果是否大于10 判断下一节点是否进1
sum.next = new ListNode(r1 % 10) //将相加结果赋值
sum = sum.next //结果链表指针后移
if (l1) l1 = l1.next //链表1指针后移
if (l2) l2 = l2.next //链表2指针后移
}
return head.next
};
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
解题
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let arr = []; //存放非重复字符串
let max = 0; //存放无重复字符最大数量
for (let i = 0; i < s.length; i ++) {
//如果之前存在，就删除，知道没有为止
if(arr.indexOf(s[i]) !== -1) {
arr.splice(0, arr.indexOf(s[i]) + 1);
}
//加入当前元素
arr.push(s[i]);
//取最大 每次更新
max = Math.max(max, arr.length);
}
//返回最大不重复个数
return max;
};
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
解题
/**
* @param {string} s
* @return {string}
*/
//次数按照 字符串 babad 做解析
var longestPalindrome = function (s) {
function isPalindrome(str) {
//判断当前字符串是否是回文字符串 比如正好截取到 aba
var len = str.length
var middle = parseInt(len / 2)
for (var i = 0; i < middle; i++) {
//则此处的 str[i]为a str[len - i - 1]也是a 即为回文串
if (str[i] != str[len - i - 1]) {
return false
}
}
return true
}
var ans = '';
var max = 0;
var len = s.length
for (var i = 0; i < len; i++) {
for (var r = i + 1; r <= len; r++) {
var tmpStr = s.substring(i, r)
//双指针遍历 将字符串所以长度的可能性都截取到去判断是否是回文串
//如果是回文串 而且当前回文串的长度大于上一次存储回文串的长度 则更新答案数据
if (isPalindrome(tmpStr) && tmpStr.length > max) {
//当前截取到的回文串即为答案 aba
ans = s.substring(i, r)
max = tmpStr.length;
}
}
}
return ans;
};
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321
示例 2：
输入：x = -123
输出：-321
示例 3：
输入：x = 120
输出：21
示例 4：
输入：x = 0
输出：0
提示：
-231 <= x <= 231 - 1
解题
/**
* @param {number} x
* @return {number}
*/
//本次以 9646324351 为输入解析
var reverse = function(x) {
//定义结果 开始累加
let rev = 0;
//遍历 当x不为0 一直循环处理
while (x !== 0) {
const digit = x % 10; //取出第一位反转的数据 9646324351%10 = 1 依次为1 5 3 4 2 3 6 4 6 9
x = ~~(x / 10); //将当前数据去除一位 x/10=964632435.1 ~位运算取反 ~~即为取整数 964632435 依次减去一位
// ~ 取反码 001 --> 110
rev = rev * 10 + digit; //此处乘以10为了将数据复位，比如第一位取到的1，之后再加应该是1digit，此时1就是十位数 10
//依次乘10 最后将数组反转
//不符合条件的返回0
if (rev < Math.pow(-2, 31) || rev > Math.pow(2, 31) - 1) {
return 0;
}
}
return rev;
};
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
示例 1：
输入：x = 121
输出：true
示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
示例 4：
输入：x = -101
输出：false
解题
/**
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function(x) {
if(x < 0){ //负数由于负号 - 限制，无法形成回文
return false;
}
if(x >= 0 && x <10){ // 0 - 9 单位数，本身也属于回文数
return true;
}
let tempArr = x.toString().split(""); //将数字转为数组
if(tempArr.join("") === tempArr.reverse().join("")){ //将数组转为字符串 再同数组反转后的字符串进行比较，
//如果一致，则为回文数
return true;
}else{
return false;
}
};
网友评论