又是一个愉快的周五，继续刷题ing~
最小栈
题目：设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
前言：这里先认个怂，这道题我思路不行。 我一直承认与非科班的短板还有工作以来急功近利的心态。至于这种很少见的数据结构（除了数组，集合，map之外的数据结构）链表和树都还是在LeetCode上学的。Queue队列是前一段时间树的遍历了解的。而这道题用到的栈。讲真我在这道题之前连单词都不会写。一开始我试图用自己的思路来解题，唯一这种类型先入后出的也就是队列。所以在尽量用Queue来解题，卡在了getMin这块。最终还是直接决定看解析了。现在不会，看了解析我会了不就行了么？还好网上那么多好心的大大出各种解析，解释和思路讲解。讲的很透彻和明白，尤其是有一个大大提供了多思路的讲解，每一种都让我豁然开朗，这里再次表达感谢。
思路：这才是真正的解题思路。简单说一下这道题很多种做法可以做。首先Java提供的栈Stack。它本身已经有了前三个方法的实现，也就是这道题如果用了这个Stack只要实现最后一个最小值就可以了。当然也可以不用这个Stack，但是这种思路后面说。先说用Stack实现最小值
首先一种最简单的办法：用空间换时间。这里只要求常熟时间内检索到最小元素的栈。并没有对空间有要求。我们完全可以使用两个栈，一个是正常的栈，另一个是专门记录最小值的栈。这样取最小值只需要一步，简单的多。直接上代码：
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> min;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack();
min = new Stack();
}
public void push(int x) {
stack.push(x);
//最小值这个栈不为空
if(!min.isEmpty()){
//当新push的比最小栈中的首元素大就把这个push到最小栈中
if(min.peek()>=x){
min.push(x);
}
}else{
min.push(x);
}
}
public void pop() {
//这里有个坑，不能直接比较，不然两个Integer得判断equals
int x =stack.pop();
if(min.peek()==x){
min.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
其实这个是最容易理解的了，也很简单，但是大佬在这个基础上改良优化了一下。这个是很明显的用空间换时间。能不能只用一个栈就完成这个需求？真的非常佩服大佬的思路广而且闲（绝对是褒义词，喜欢钻研的意思）这一个简单 题不断优化，提供多种不同思路。咱们继续说这个题上一版的优化版。如果用一个栈，则需要一个常量来表示最小值。但是会出现一种状态，每次这个常量表示的都是最小值。但是这个最小值上一个最小值记录找不到了。如果这个最小值出栈了就gg了、所以重点是要保存最小值的同时保存第二小的值。这样不管怎么出栈都不会gg。
然后大佬的思路是在push最小值的时候，把之前最小值也压入栈。这样就算是最小值出栈了，我们还能知道第二小的（也就是现在的最小的）。说起来很复杂但是只要理解原理了还是很简单的。我这里直接上代码了。
class MinStack {
private Stack<Integer> stack;
//因为这个min取值万一push进来的都大于初始值就会出错。所以直接min赋值最大值。
private int min = Integer.MAX_VALUE;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack();
}
public void push(int x) {
if(min>=x){
//把之前最小的push进去。
stack.push(min);
//把min改成最小值
min=x;
}
stack.push(x);
}
public void pop() {
int x =stack.pop();
//说明最小值被pop了，min应该等于第二小的。并且顺便把第二小的也pop出去。
if(min==x){
min = stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
再然后大神还提供了几个思路，一个是取巧的减法。这个就是保存的数据是每一个值和最小值的差。然后如果遇到比这个最小值还小的数字这个差就会是负数。同时更新最小值min的值。这样每次取出值的时候判断正负就好了。如果是负的，我们用最小值减去这个负数得到的就是第二小的值了。
其实想想也知道，这个方法运行起来跟上一个比不用往栈中插入额外的数据。但是每次取出值都要加以判断。具体哪个比较好还真不好说。而且因为保存差值，可能会溢出，所以要用long存，不能用int存。
class MinStack {
//涉及到运算，可能会溢出，所以这里用long
private Stack<Long> stack;
//因为这个min取值万一push进来的都大于初始值就会出错。所以直接min赋值最大值。
private long min;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack();
}
public void push(int x) {
if(stack.isEmpty()){
min = x;
stack.push(x-min);
}else{
stack.push(x-min);
if(x<min){
//新插入的数据是负的。并且替换min值
min = x;
}
}
}
public void pop() {
//因为这个是不用有返回值的，所以直接弹出去就行了。管他数据对不对呢
long x =stack.pop();
//说明最小值被pop的是最小值。
if(x<0){
min = min-x;
}
}
public int top() {
//如果是负数这个出栈的值是min
if(stack.peek()<0){
return (int)min;
}else{
return (int)(stack.peek()+min);
}
}
public int getMin() {
return (int)min;
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
最后一个是没采用java的Stack自己链表实现的方法。这个其实道理不难，而且思路也简单。但是因为是自己建造底层数据结构所以代码多点。
原理就是链表，并且在每一个节点除了存储节点本身的值还存储最小值。所以每次获取最小值只要知道当前节点的最小值就可以了。 也是一种用空间换时间的做法。直接上代码：
class MinStack {
class Node{
int node;
int min;
Node next;
Node(int val,int min){
this.node = val;
this.min = min;
next =null;
}
}
private Node node;
/** initialize your data structure here. */
public MinStack() {
}
//这块区别于常用的链表，每次新push的节点要放在头部。所以是把node往后挂
public void push(int x) {
if(node==null){
node = new Node(x,x);
}else{
Node n = new Node(x,Math.min(x,node.min));
n.next = node;
node = n;
}
}
public void pop() {
//把头节点拿走。因为之前存的时候每一个节点都有当前数据的最小值，所以根本不用考虑最小值
if(node!=null){
node = node.next;
}
}
public int top() {
return node.node;
}
public int getMin() {
return node.min;
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
然后这道题终于结束了，整整用了半天，理大佬思路，一点点按照理解写代码。再一次次执行，最后写下来。虽然时间耽误挺多但是真的觉得学到了很多东西。顺便心得就是做题一定要踏下心来慢慢的分析琢磨，越着急思路越不清晰。下一题吧。
LeetCode遇到需要会员才能做的题了。好蓝瘦，不能白嫖了~
相交链表
题目：编写一个程序，找到两个单链表相交的起始节点。
思考：反正如图所示吧，单纯的找到焦点还是很简单的，暴力双循环吧。但是真的太low，人家都说了要尽量满足O(n)时间复杂度和O（1）内存了。所以还是想想怎么取巧吧。
真遗憾，我没想出来满足要求的解题方法。因为我觉得这个题不取巧谁都能做，所以我也没暴力法写出来。直接看了解析。然后有一次被别人的思路所震惊。
思路：直接说方法吧。思路就是两个指针分别遍历链表A,B。A遍历完接着遍历B。B遍历完接着遍历A。这两个指针的交叉点就是链表的交点。可能我这么说很难理解，我这里用图表示
所以这个题的解就是两个链表互相加一下，然后一直遍历到，直到两个链表相等的节点就是相交点，如果遍历完了也没有相交点说明就是不相交的两个链表。
思路理解了代码很容易实现的：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null || headB==null){
return null;
}
ListNode ha = headA;
ListNode hb = headB;
//A+B只加一次，必须有个标，不然就循环追尾了
boolean flag1 = true;
boolean flag2 = true;
while(ha!=null){
if(ha==hb){
return ha;
}else{
if(ha.next == null && flag1){
//已经追加一次就要把标改状态。
ha = headB;
flag1 = false;
}else{
ha = ha.next;
}
if(hb.next == null && flag2){
hb = headA;
flag2 = false;
}else{
hb = hb.next;
}
}
}
return null;
}
}
然后我看到了另一种写法，思路是一样的，我这里是用flag判断只追加一次的。还有一种思路就是判断条件是A==B，不管是A+B或者B+A，在走完一遍的时候最终会归于null。所以那么判断也可以。只要理解就行。我刚刚也改了那种方法运行了一下，两个方式其实性能差不多。选择能理解的喜欢的就好。
两数之和二
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
思路：这道题我做过，我不知道他和两数之和1 有什么区别，除了下标是从1开始。反正做是第一时间做出来了，怎么优化还得慢慢来。先把第一版贴上来
class Solution {
public int[] twoSum(int[] numbers, int target) {
int [] result = new int[2];
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0;i<numbers.length;i++){
//有答案则直接返回。这两个数对找到了.这有个优化点，就是因为升序排列，而且不会有重复，所以说两个加数中较大的那个肯定比target/2大。因为有负数问题，所以是大于等于
if(numbers[i]>=target/2 && map.containsKey(target-numbers[i])){
result[0] = map.get(target-numbers[i]);
result[1] = i+1;
return result;
}else{
//没有把这个数和下标存进map。因为下标不是从0开始，所以存i+1。
map.put(numbers[i],i+1);
}
}
return null;
}
}
我觉得我已经绞尽脑汁的优化了，但是性能还是不行。其实能理解：因为可能是上面这种遍历的方法本身就有问题，所以我换个思路试试。
实在没思路忍不住看了题解，然后豁然开朗。真的，一看就会。一点不夸张。差的就是那个思维模式。哎，其实就是双指针法。最大最小相加跟给定的比较。大了右指针往左移。小了左指针往右移。知道正好找到那两个数为止。就这么简单粗暴。因为题目已经说了肯定有一对是可以的。所以我也没做判断。再说溢出问题。其实这个不用考虑。不然你拿点数据测试一下就行了。因为这个溢出后结果肯定是不对的。然后开始挪位。最后肯定是挪到不溢出的地方了。直接上代码吧
class Solution {
public int[] twoSum(int[] numbers, int target) {
int [] result = new int[2];
int left= 0;
int right =numbers.length-1;
while(true){
//这两个数相加比给定的大。则最大值往小
if(numbers[left]+numbers[right]>target){
right--;
}else if(numbers[left]+numbers[right]<target){//这两个数相加比给定值小，则最小值往大
left++;
}else{
result[0] = left+1;
result[1] = right+1;
return result;
}
}
}
}
好了，今天的三道题就到这，其实学习的乐趣不在于学会了怎么怎么样，而在于懂了的那一刻的成就感和自豪感。我是正在试图入门的算法小白，每天进步一点点~
如果稍微帮到你了记得点个喜欢点个关注呦~也祝大家工作顺顺利利！周末愉快！
