三步问题 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:

 输入：n = 3 
 输出：4
 说明: 有四种走法
示例2:

 输入：n = 5
 输出：13
提示:

n范围在[1, 1000000]之间
通过次数25,579提交次数71,896

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/three-steps-problem-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

经典的爬楼梯问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int waysToStep(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        long one = 1, two = 2, three = 4;

        long res = 0;
        for (int i = 4; i <= n; i++) {
            res = (one + two + three) % 1000000007;
            one = two;
            two = three;
            three = res;
        }
        return (int)res;
    }
}

展开全文 >>

绘制直线 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
绘制直线。有个单色屏幕存储在一个一维数组中，使得32个连续像素可以存放在一个 int 里。屏幕宽度为w，且w可被32整除（即一个 int 不会分布在两行上），屏幕高度可由数组长度及屏幕宽度推算得出。请实现一个函数，绘制从点(x1, y)到点(x2, y)的水平线。

给出数组的长度 length，宽度 w（以比特为单位）、直线开始位置 x1（比特为单位）、直线结束位置 x2（比特为单位）、直线所在行数 y。返回绘制过后的数组。

示例1:

 输入：length = 1, w = 32, x1 = 30, x2 = 31, y = 0
 输出：[3]
 说明：在第0行的第30位到第31为画一条直线，屏幕表示为[0b000000000000000000000000000000011]
示例2:

 输入：length = 3, w = 96, x1 = 0, x2 = 95, y = 0
 输出：[-1, -1, -1]
通过次数1,970提交次数3,652

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/draw-line-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目的意思

用一维数组来存储所有像素值：

  • length是结果数组的长度是length；
  • w是当前屏幕宽度，单位是像素。除以32就是一行用多少个int表示；
  • 高度就是length*32 / w，实际计算没啥用。y+1别超过这个值就可以；
  • 题目要求在第y行画一条直线（0开始计数）。像素位置是从x1到x2；
  • 图像的坐标是左上角为原点，水平向右x递增，水平向下是y递增；
    所以，题目中的示例改一改就是这样的：

length = 3, w = 32, x1 = 18, x2 = 28, y = 2

只用1个int，表示一个高度为3，宽度为32的屏幕，绘制的位置第2行（0开始计数）是从18到28

1
2
3
4
5
6
7
8
0000 0000 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0011 1111 1111 1000
                      ^            ^   
                     x1           x2
结果中第一个数字在数组中的位置是 gIndex=y * (w / 32) + (w / 32 - 1);
新添加数字时gIndex--;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int[] drawLine(int length, int w, int x1, int x2, int y) {
        if (w == 0) return new int[]{0};
        int[] screen = new int[w];
        for (int i = x1; i <= x2; i++) {
            screen[i] = 1;
        }
        int index = 0;
        int[] res = new int[length];


        int val = 0;
        int bitPow = 1;
        int gIndex = y * (w / 32) + (w / 32 - 1);


        while (index < w) {
            val += screen[w - index - 1] * bitPow;
            bitPow *= 2;
            index++;
            if (index % 32 == 0) {
                res[gIndex--] = val;
                val = 0;
                bitPow = 1;
            }
        }
        return res;
    }
}


位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] drawLine(int length, int w, int x1, int x2, int y) {
        int[] ret = new int[length];
        // 注意根据所在行数计算偏移量
        int offset = y * w / 32;
        // 首位数字下标
        int head = x1 / 32 + offset;
        // 末位数字下标
        int rear = x2 / 32 + offset;
        // 把涉及到的数全部置 -1 也就是 0b11111111111111111111111111111111
        for (int i = head; i <= rear; i++)
            ret[i] = -1;
        // 调整首位数字
        ret[head] = ret[head] & -1 >>> x1 % 32;
        // 调整末位数字
        ret[rear] = ret[rear] & Integer.MIN_VALUE >> x2 % 32;
        return ret;
    }
}

作者：1ujin
链接：https://leetcode-cn.com/problems/draw-line-lcci/solution/java-wei-yun-suan-shuang-bai-by-1ujin/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

作者：1ujin 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

检查平衡性 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。

示例 1:
给定二叉树 [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
      1
     / \
    2   2
   / \
  3   3
 / \
4   4
返回 false 。
通过次数22,150提交次数38,867

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-balance-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return getDepth(root) == -1 ? false : true;
    }

    public int getDepth(TreeNode root) {
        if (root == null) return 0;
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        return 1 + Math.max(left, right);
    }
}

展开全文 >>

滑动窗口的最大值 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

 

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
示例 2：

输入：nums = [1], k = 1
输出：[1]
示例 3：

输入：nums = [1,-1], k = 1
输出：[1,-1]
示例 4：

输入：nums = [9,11], k = 2
输出：[11]
示例 5：

输入：nums = [4,-2], k = 2
输出：[4]
 

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
通过次数96,586提交次数196,790

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[]{};
        if (k > nums.length) return new int[]{};

        int end = 0;
        int index = 0;

        int[] res = new int[nums.length - k + 1];
        Deque<Integer> maxQueue = new LinkedList<>();

        maxQueue.offer(nums[0]);
        for (int i = 1; i < k; i++) {
            while (!maxQueue.isEmpty() && maxQueue.peekLast() < nums[i]) {
                maxQueue.pollLast();
            }
            maxQueue.offerLast(nums[i]);
        }
        res[index++] = maxQueue.peekFirst();

        end = k;                                                                              //定位到第一个窗口的末尾
        for (int i = 1; end < nums.length; i++, end++) {
            if (nums[i - 1] == maxQueue.peekFirst()) {
                maxQueue.pollFirst();
            }
            end = i + k - 1;
            while (!maxQueue.isEmpty() && maxQueue.peekLast() < nums[end]) {
                maxQueue.pollLast();
            }
            maxQueue.offerLast(nums[end]);
            res[index++] = maxQueue.peekFirst();
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

分块+预处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] prefixMax = new int[n];
        int[] suffixMax = new int[n];
        for (int i = 0; i < n; ++i) {
            if (i % k == 0) {
                prefixMax[i] = nums[i];
            }else {
                prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            if (i == n - 1 || (i + 1) % k == 0) {
                suffixMax[i] = nums[i];
            } else {
                suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
            }
        }

        int[] ans = new int[n - k + 1];
        for (int i = 0; i <= n - k; ++i) {
            ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

单调队列(第二次做)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] nums, int size) {
        int n = nums.length;
        
        ArrayList<Integer> res = new ArrayList<>();
        if(size==0||n<size||n==0)return res;
        LinkedList<Integer> queue = new LinkedList<>();
        LinkedList<Integer> maxQueue = new LinkedList<>();
        
        for(int i=0;i<size;i++){
            queue.offer(nums[i]);
            while(!maxQueue.isEmpty()&&maxQueue.peekLast()<nums[i]){
                maxQueue.pollLast();
            }
            maxQueue.offer(nums[i]);
        }
        
        for(int i=0;i<n-size+1;i++){
            res.add(maxQueue.peek());
            int del = queue.poll();
            if(maxQueue.peek()==del){
                maxQueue.poll();
            }
            
            int r = i + size;
            if(r>=n)break;
            queue.offer(nums[r]);
            while(!maxQueue.isEmpty()&&maxQueue.peekLast()<nums[r]){
                maxQueue.pollLast();
            }
            maxQueue.offer(nums[r]);
        }

        return res;
    }
}

展开全文 >>

动物收容所

动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat。允许使用Java内置的LinkedList数据结构。

enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。

dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。

示例1:

1
2
3
4
5
 输入：
["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [], [], []]
 输出：
[null,null,null,[0,0],[-1,-1],[1,0]]

示例2:

1
2
3
4
5
 输入：
["AnimalShelf", "enqueue", "enqueue", "enqueue", "dequeueDog", "dequeueCat", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [[2, 1]], [], [], []]
 输出：
[null,null,null,null,[2,1],[0,0],[1,0]]

说明:

收纳所的最大容量为20000

通过次数5,893 提交次数9,950

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/animal-shelter-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class AnimalShelf {

    LinkedList<int[]> dogQueue = null;
    LinkedList<int[]> catQueue = null;

    public AnimalShelf() {
        dogQueue = new LinkedList<>();
        catQueue = new LinkedList<>();
    }

    public void enqueue(int[] animal) {
        if (animal[1] == 0) catQueue.add(animal);
        else dogQueue.add(animal);
    }

    public int[] dequeueAny() {
        if (catQueue.size() > 0 && dogQueue.size() > 0)
            return catQueue.peek()[0] < dogQueue.peek()[0] ? catQueue.poll() : dogQueue.poll();
        else if (catQueue.size() > 0) return catQueue.poll();
        else if (dogQueue.size() > 0) return dogQueue.poll();
        return new int[]{-1, -1};
    }

    public int[] dequeueDog() {
        return dogQueue.size() > 0 ? dogQueue.poll() : new int[]{-1, -1};
    }

    public int[] dequeueCat() {
        return catQueue.size() > 0 ? catQueue.poll() : new int[]{-1, -1};
    }
}

/**
 * Your AnimalShelf object will be instantiated and called as such:
 * AnimalShelf obj = new AnimalShelf();
 * obj.enqueue(animal);
 * int[] param_2 = obj.dequeueAny();
 * int[] param_3 = obj.dequeueDog();
 * int[] param_4 = obj.dequeueCat();
 */

展开全文 >>

化栈为队

实现一个MyQueue类，该类用两个栈来实现一个队列。

示例：

1
2
3
4
5
6
7
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 操作）。

通过次数13,789 提交次数19,324

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class MyQueue {


    Deque<Integer> stack1 = null;
    Deque<Integer> stack2 = null;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        stack1.push(x);
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return !stack2.isEmpty() ? stack2.pop() : -1;
    }

    /**
     * Get the front element.
     */
    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return !stack2.isEmpty() ? stack2.peek() : -1;
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return !(stack1.size() + stack2.size() > 0);
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

展开全文 >>

栈的最小值 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
请设计一个栈，除了常规栈支持的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.
通过次数15,116提交次数25,013

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class MinStack {

    Deque<Integer> stack = null;
    Deque<Integer> stackMin = null;

    public MinStack() {
        stack = new LinkedList<>();
        stackMin = new LinkedList<>();
    }

    public void push(int x) {
        stack.push(x);
        if (stackMin.isEmpty()) {
            stackMin.push(x);
        } else {
            if (x < stackMin.peek()) stackMin.push(x);
            else stackMin.push(stackMin.peek());
        }

    }

    public void pop() {
        if (!stack.isEmpty()) {
            stack.pop();
            stackMin.pop();
        }
    }

    public int top() {
        if (!stack.isEmpty()) {
            return stack.peek();
        }
        return -1;
    }

    public int getMin() {
        if (!stackMin.isEmpty()) {
            return stackMin.peek();
        }
        return -1;
    }
}

/**
 * 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();
 */

展开全文 >>

三合一 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
三合一。描述如何只用一个数组来实现三个栈。

你应该实现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]
通过次数5,736提交次数10,619

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/three-in-one-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class TripleInOne {

    private int[] stack = null;
    private int index1 = 0, index2 = 0, index3 = 0;
    private int stackSize = 0;

    public TripleInOne(int stackSize) {
        this.stack = new int[stackSize * 3];
        this.index1 = 0;
        this.index2 = stackSize;
        this.index3 = stackSize * 2;
        this.stackSize = stackSize;
    }

    public void push(int stackNum, int value) {

        switch (stackNum) {
            case 0:
                if (index1 < stackSize) {
                    stack[index1++] = value;
                }
                break;
            case 1:
                if (index2 < stackSize * 2) {
                    stack[index2++] = value;
                }
                break;
            case 2:
                if (index3 < stackSize * 3) {
                    stack[index3++] = value;
                }
                break;
        }
    }

    public int pop(int stackNum) {
        switch (stackNum) {
            case 0:
                if (index1 > 0) {
                    return stack[--index1];
                }
                break;
            case 1:
                if (index2 > stackSize) {
                    return stack[--index2];
                }
                break;
            case 2:
                if (index3 > stackSize * 2) {
                    return stack[--index3];
                }
                break;
        }
        return -1;
    }

    public int peek(int stackNum) {
        int res = -1;
        switch (stackNum) {
            case 0:
                if (index1 > 0) {
                    res = stack[--index1];
                    index1++;
                    return res;
                }
                break;
            case 1:
                if (index2 > stackSize) {
                    res = stack[--index2];
                    index2++;
                    return res;
                }
                break;
            case 2:
                if (index3 > stackSize * 2) {
                    res = stack[--index3];
                    index3++;
                    return res;
                }
                break;
        }
        return res;
    }

    public boolean isEmpty(int stackNum) {
        switch (stackNum) {
            case 0:
                if (index1 > 0) {
                    return false;
                } else {
                    return true;
                }
            case 1:
                if (index2 > stackSize) {
                    return false;
                } else {
                    return true;
                }
            case 2:
                if (index3 > stackSize * 2) {
                    return false;
                } else {
                    return true;
                }
        }
        return false;
    }
}

/**
 * Your TripleInOne object will be instantiated and called as such:
 * TripleInOne obj = new TripleInOne(stackSize);
 * obj.push(stackNum,value);
 * int param_2 = obj.pop(stackNum);
 * int param_3 = obj.peek(stackNum);
 * boolean param_4 = obj.isEmpty(stackNum);
 */

展开全文 >>

栈排序 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：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]范围内。
通过次数7,504提交次数13,799

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-of-stacks-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

如果新加入的元素大于栈顶元素，先把栈顶元素放进辅助栈，把大的元素放好后再拿回来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class SortedStack {

  private Deque<Integer> tempStack = null;
    private Deque<Integer> minStack = null;

    public SortedStack() {
        tempStack = new LinkedList<>();
        minStack = new LinkedList<>();
    }

    public void push(int val) {
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        } else {
            while (!minStack.isEmpty() && val > minStack.peek()) {
                tempStack.push(minStack.pop());
            }
            minStack.push(val);
            while (!tempStack.isEmpty()) {
                minStack.push(tempStack.pop());
            }
        }
    }

    public void pop() {
        if (!minStack.isEmpty()) {
            minStack.pop();
        }
    }

    public int peek() {
        if (!minStack.isEmpty()) {
            return minStack.peek();
        }
        return -1;
    }

    public boolean isEmpty() {
        return !(minStack.size() > 0);
    }
}

/**
 * Your SortedStack object will be instantiated and called as such:
 * SortedStack obj = new SortedStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.isEmpty();
 */

惰性更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

class SortedStack {
    //原始栈
    Deque<Integer> stack = new LinkedList<>();
    //辅助栈
    Deque<Integer> tmp = new LinkedList<>();
    public SortedStack() {

    }
    
    public void push(int val) {
        int max = stack.isEmpty() ? Integer.MAX_VALUE : stack.peek();
        int min = tmp.isEmpty() ? Integer.MIN_VALUE : tmp.peek();
        //比较原始栈与辅助栈栈顶值，使其满足 辅助栈 <= val <= 原始栈
        while(true){
            if(val > max){
                tmp.push(stack.pop());
                max = stack.isEmpty() ? Integer.MAX_VALUE : stack.peek();
            }
            else if(val < min){
                stack.push(tmp.pop());
                min = tmp.isEmpty() ? Integer.MIN_VALUE : tmp.peek();
            }
            else{
                stack.push(val);
                break;
            }
        }
    }
    
    public void pop() {
        //将辅助栈元素push回原始栈
        while (!tmp.isEmpty()){
            stack.push(tmp.pop());
        }
        if (!stack.isEmpty())
            stack.pop();
    }
    
    public int peek() {
        //将辅助栈元素push回原始栈
        while (!tmp.isEmpty()){
            stack.push(tmp.pop());
        }
        return stack.isEmpty() ? -1 : stack.peek();
    }
    
    public boolean isEmpty() {
        return stack.isEmpty() && tmp.isEmpty();
    }
}

参考文献

作者：lava-4来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

回文链表 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
编写一个函数，检查输入的链表是否是回文的。

示例 1：

输入： 1->2
输出： false 
示例 2：

输入： 1->2->2->1
输出： true 
 

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

通过次数21,183提交次数45,007

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        ListNode pre = head;
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null) {
            pre = slow;
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                break;
            }
        }
        reverseList(pre);                                   //将链表后半部分反转

        ListNode re = pre.next;
        slow = head;
        while (re != null) {
            if (slow.val == re.val) {
                slow = slow.next;
                re = re.next;
            } else {
                return false;
            }
        }

        reverseList(pre);                                   //将链表后半部分转回去

        return true;
    }

    public void reverseList(ListNode node) {
        ListNode pre = node;
        ListNode cur = node.next;

        while (cur != null) {
            ListNode nex = cur.next;
            ListNode temp = null;
            if (nex != null) {
                temp = nex.next;
                cur.next = pre.next;
                if (pre.next.equals(cur)) cur.next = null;  //第一个节点，如果next指向自身会死循环
                nex.next = cur;
                pre.next = nex;
                cur = temp;
            } else {                                        //最后一个节点没有后继节点了，直接把它连接到pre
                if (cur != pre.next) {                      //只有两个节点时不出错
                    cur.next = pre.next;
                    pre.next = cur;
                }
                break;
            }
        }
    }
}

官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }        

        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

作者：LeetCode-Solution来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走