刷题记录 7

8.11

面试题 01.04. 回文排列 - 力扣（LeetCode）

题目跟常见的那种判断回文不太一样 还有注意字符范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean canPermutePalindrome(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int[] ch = new int[128];
        for (int i = 0; i < n; i++) {
            ch[chars[i]]++;
        }
        boolean flag = false;
        for (int i = 0; i < 128; i++) {
            int num = ch[i];
            if (num%2 == 0) continue;
            if(flag) return false;
            flag = true;
        }
        return true;
    }
}

面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

一般考虑用数组存储状态或sort排序后遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isUnique(String astr) {
        int n = astr.length();
        char[] chars = astr.toCharArray();
        Arrays.sort(chars);
        for (int i = 1; i < n; i++) {
            if(chars[i]==chars[i-1]) return false;
        }
        return true;
    }
}

class Solution {
    public boolean isUnique(String astr) {
        char[] chars = astr.toCharArray();
        boolean[] map = new boolean[26];
        for(char c : chars) {
            if(map[c - 'a']) return false;
            map[c - 'a'] = true;
        }
        return true;
    }
}

可是题目说不用额外的数据结构会很加分 思来想去就只能用位运算了吧

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isUnique(String astr) {
        int num = 0, n = astr.length();
        for (int i = 0; i < n; i++) {
            char ch = astr.charAt(i);
            int index = ch - 'a';
            if(((num>>index)&1)==1) return false;
            else num|=(1<<index);
        }
        return true;
    }
}

位运算还是不太熟练 顺便记一下面试技巧

image-20240811191711146

面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        int n = s1.length();
        if(n != s2.length()) return false;
        char[] chars = new char[26];
        for(int i=0; i<n; i++) {
            chars[s1.charAt(i)-'a']++;
        }
        for(int i=0; i<n; i++) {
            if(chars[s2.charAt(i)-'a']--==0) return false;
        }
        return true;
    }
}

面试题 01.03. URL化 - 力扣（LeetCode）

题目给的真实长度有大用处 没看懂题

image-20240811213022248

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public String replaceSpaces(String S, int length) {
        char[] str = S.toCharArray();
        int index = S.length()-1;
        for(int i = length-1; i >= 0; i--){
            if(str[i] == ' '){
                str[index--] = '0';
                str[index--] = '2';
                str[index--] = '%';
            }else {
                str[index--] = str[i];
            }
        }
        return new String(str,index+1,S.length()-1-index);
    }
}

莫名其妙的一道题 挺屎的

8.12

面试题 01.05. 一次编辑 - 力扣（LeetCode）

细节太多啦… 错了五次 每次都是一点点小bug 细节很多的时候就容易忽略bug

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 boolean oneEditAway(String first, String second) {
        int n1 = first.length(),n2 = second.length();
        if(n1 == n2) {
            boolean flag = false;
            for(int i = 0;i < n1;i++) {
                if(first.charAt(i) != second.charAt(i)) if(flag) return false; else flag=true;
            }
            return true;
        }
        else if(n1==n2+1||n2==n1+1) {
            boolean flag = false;
            char []s1,s2;
            if(n1>n2){
                s1=first.toCharArray();
                s2=second.toCharArray();
            }else {
                s1=second.toCharArray();
                s2=first.toCharArray();
            }
            int index = 0,n = Math.min(n1,n2);
            for(int i = 0;i < n;) {
                if(s2[i] != s1[index]) {
                    if(flag) return false;
                    flag=true; ++index; continue;
                }++i;++index;
            }
            return true;
        }
        return false;
    }
}

面试题 01.06. 字符串压缩 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String compressString(String S) {
        StringBuilder sb = new StringBuilder();
        char[] chars = S.toCharArray();
        int i = 0, n = S.length();
        while (i < n) {
            sb.append(chars[i]);
            int num = 0;
            char ch = chars[i];
            while(i<n&&ch==chars[i]) {
                ++i;++num;
            }
            sb.append(num);
        }
        return sb.length()<n?sb.toString():S;
    }
}

面试题 01.07. 旋转矩阵 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        if(n == 0) return;
        for (int i = 0; i < n; i++) {
            for(int j=0;j<n-1-i;j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][n-1-i];
                matrix[n-1-j][n-1-i] = temp;
            }
        }
        for (int i = 0; i < n/2; i++) {
            for(int j=0;j<n;j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-1-i][j];
                matrix[n-1-i][j] = temp;
            }
        }
    }
}

面试题 01.08. 零矩阵 - 力扣（LeetCode）

我记得还有一种不用额外空间的写法来着

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] row = new boolean[m], col = new boolean[n];
        
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) 
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
        
        for (int i = 0; i < m; i++)
            if(row[i]) Arrays.fill(matrix[i], 0);
        
        for (int i = 0; i < n; i++)
            if(col[i]) 
                for(int j = 0; j < m; j++)
                    matrix[j][i] = 0;
    }
}

想起来了 不过真的好蠢 完全没必要省这点空间

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
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flag1 = matrix[0][0] == 0,flag2 = matrix[0][0] == 0;
        
        if(!flag1) {
            for(int i = 0; i < n; i++) if(matrix[0][i] == 0) {flag1=true;break;}
        }
        if(!flag2) {
            for(int i = 0; i < m; i++) if(matrix[i][0] == 0) {flag2=true;break;}
        }

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }

        for (int i = 1; i < m; i++)
            if(matrix[i][0]==0) Arrays.fill(matrix[i], 0);

        for (int i = 1; i < n; i++)
            if(matrix[0][i]==0)
                for(int j = 0; j < m; j++)
                    matrix[j][i] = 0;

        if(flag1) {
            Arrays.fill(matrix[0], 0);
        }
        if(flag2) {
            for(int j = 0; j < m; j++){
                matrix[j][0] = 0;
            }
        }
    }
}

面试题 01.09. 字符串轮转 - 力扣（LeetCode）

暴力 26ms

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        if(s1.equals(s2)) return true;
        for(int i = 0; i < s1.length(); i++) {
            if((s1.substring(i)+s1.substring(0, i)).equals(s2)) return true;
        }
        return false;
    }
}

从后往前添加并对比 2ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        if(s1.equals(s2)) return true;
        int n = s1.length();
        StringBuilder sb1 = new StringBuilder(), sb2 = new StringBuilder();
        for(int i = 0; i < n; i++) {
            sb1.append(s1.charAt(i));
            sb2.insert(0,s2.charAt(n-1-i));
            if(sb1.toString().contentEquals(sb2)) {
                if(s1.substring(i+1).equals(s2.substring(0,n-1-i))) return true;
            }
        }
        return false;
    }
}

秀 没想到

1
2
3
4
5
class Solution {
    public boolean isFlipedString(String s1, String s2) {
        return s1.length() == s2.length() && (s1 + s1).contains(s2);
    }
}

8.13

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

// TODO 用KMP写一个

面试题 02.01. 移除重复节点 - 力扣（LeetCode）

进阶不用额外空间 时间复杂度是O(N^2) 但是有320ms这么久吗…?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = head,next = p.next,pre = p;
        while(p!=null){
            pre = p;
            next = p.next;
            while(next!=null){
                if(next.val == p.val){
                    pre.next = next.next;
                    next = next.next;
                }else {
                    pre = next;
                    next = next.next;
                }
            }
            p = p.next;
        }
        return head;
    }
}

用哈希表 4ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null || head.next == null) return head;
        Set<Integer> set = new HashSet<>();
        set.add(head.val);
        ListNode cur = head;
        while (cur.next != null) {
            if(set.add(cur.next.val)) {
                cur = cur.next;
            }else cur.next = cur.next.next;
        }
        return head;
    }
}

面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

反指 O(N+K)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int kthToLast(ListNode head, int k) {
        if (head.next == null) return head.val;
        ListNode pre = null, cur = head, next = head.next;
        while(next!=null) {
            cur.next = pre;
            pre = cur;
            cur = next;
            next = next.next;
        }cur.next = pre;
        while (--k > 0) {
            cur = cur.next;
        }
        return cur.val;
    }
}

快慢指针 O(N)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int kthToLast(ListNode head, int k) {
        if (head.next == null) return head.val;
        ListNode fast = head, slow = head;
        while(--k>0) fast = fast.next;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}

面试题 02.03. 删除中间节点 - 力扣（LeetCode）

想了半天有什么意义

1
2
3
4
5
6
7
8
9
10
class Solution {
    public void deleteNode(ListNode node) {
        while (node.next.next != null) {
            node.val = node.next.val;
            node = node.next;
        }
        node.val = node.next.val;
        node.next = null;
    }
}

哎我操我是傻逼啊

1
2
3
4
5
6
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

面试题 02.04. 分割链表 - 力扣（LeetCode）

力扣这题目有bug 一运行就报错 代码传不上去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummyBig = new ListNode(0), dummySmall = new ListNode(0);
        ListNode cur = head, small = dummySmall, big = dummyBig;
        while (cur != null) {
            if (cur.val < x) {
                small.next = cur;
                small = small.next;
            }else {
                big.next = cur;
                big = big.next;
            }
            cur = cur.next;
        }
        small.next = dummyBig.next;
        big.next = null;
        return dummySmall.next;
    }
}

面试题 02.05. 链表求和 - 力扣（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
39
40
41
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int num = 0, flag = 0;
        ListNode head = new ListNode(0),curr = head;
        while(l1!=null&&l2!=null){
            num = l1.val + l2.val + flag;
            if(num>9){
                flag = 1;
                num-=10;
            }else flag = 0;
            curr.next = new ListNode(num);
            curr = curr.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        while(l1!=null){
            num = l1.val + flag;
            if(num>9){
                flag = 1;
                num-=10;
            }else flag = 0;
            curr.next = new ListNode(num);
            curr = curr.next;
            l1 = l1.next;
        }
        while(l2!=null){
            num = l2.val + flag;
            if(num>9){
                flag = 1;
                num-=10;
            }else flag = 0;
            curr.next = new ListNode(num);
            curr = curr.next;
            l2 = l2.next;
        }
        if(flag==1){
            curr.next = new ListNode(1);
        }
        return head.next;
    }
}

正位存放也就麻烦一点 两个指针或者算完之后在造新链表 不写了

8.14

面试题 02.06. 回文链表 - 力扣（LeetCode）

反指加快慢指针 O(n) 时间复杂度和 O(1) 空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        ListNode pre = null,temp;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            temp = slow;
            slow = slow.next;
            temp.next = pre;
            pre = temp;
        }
        if(fast!=null) slow = slow.next;
        while(pre!=null && slow!=null && slow.val==pre.val) {
            pre = pre.next;
            slow = slow.next;
        }
        return slow==pre;
    }
}

面试题 02.07. 链表相交 - 力扣（LeetCode）

emmm 写过了

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

面试题 02.08. 环路检测 - 力扣（LeetCode）

emmm 也写过了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while(fast!=null&&fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow) break;
        }
        if(fast==null||fast.next==null) return null;
        slow = head;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

面试题 03.01. 三合一 - 力扣（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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class TripleInOne {

     int[] stack;
     int top1,top2,top3,stackSize;

    public TripleInOne(int stackSize) {
        stack = new int[stackSize*3];
        top1 = -1; top2 = -1; top3 = -1;
        this.stackSize = stackSize;
    }

    public void push(int stackNum, int value) {
        switch(stackNum) {
            case 0:
                if(top1<stackSize-1) stack[++top1] = value; break;
            case 1:
                if(top2<stackSize-1) stack[++top2+stackNum*stackSize] = value; break;
            case 2:
                if(top3<stackSize-1) stack[++top3+stackNum*stackSize] = value; break;
        }
    }

    public int pop(int stackNum) {
        switch(stackNum) {
            case 0:
                if(top1!=-1) return stack[top1--]; break;
            case 1:
                if(top2!=-1) return stack[top2--+stackNum*stackSize]; break;
            case 2:
                if(top3!=-1) return stack[top3--+stackNum*stackSize]; break;
        }
        return -1;
    }

    public int peek(int stackNum) {
        switch(stackNum) {
            case 0:
                if(top1!=-1) return stack[top1]; break;
            case 1:
                if(top2!=-1) return stack[top2+stackNum*stackSize]; break;
            case 2:
                if(top3!=-1) return stack[top3+stackNum*stackSize]; break;
        }
        return -1;
    }

    public boolean isEmpty(int stackNum) {
        switch (stackNum){
            case 0: return top1==-1;
            case 1: return top2==-1;
            case 2: return top3==-1;
        }
        return false;
    }
}

面试题 03.02. 栈的最小值 - 力扣（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
class MinStack {

    List<Integer> stack,min;

    public MinStack() {
        stack = new ArrayList<>();
        min = new ArrayList<>();
    }

    public void push(int x) {
        stack.add(x);
        if(min.isEmpty()){
            min.add(0);
        }else{
            min.add(stack.get(min.get(min.size()-1))>x?min.size():min.get(min.size()-1));
        }
    }

    public void pop() {
        stack.remove(stack.size()-1);
        min.remove(min.size()-1);
    }

    public int top() {
        return stack.get(stack.size()-1);
    }

    public int getMin() {
        return stack.get(min.get(min.size()-1));
    }
}
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 MinStack {

    Deque<Integer> xStack;
    Deque<Integer> minStack;


    /** initialize your data structure here. */
    public MinStack() {
        xStack=new LinkedList<>();
        minStack=new LinkedList<>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(),x));
    }

    public void pop() {
        xStack.pop();
        minStack.pop();
    }

    public int top() {
        return xStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

8.15

面试题 03.03. 堆盘子 - 力扣（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
39
40
41
42
43
44
45
class StackOfPlates {

     List<Deque> stack;
     int cap;

    public StackOfPlates(int cap) {
        stack = new ArrayList<>();
        this.cap = cap;
    }

    public void push(int val) {
        if(cap==0) return;
        Deque<Integer> deque;
        if(stack.isEmpty()){
            deque = new ArrayDeque<>();
            deque.push(val);
            stack.add(deque);
        }else{
            deque = stack.get(stack.size()-1);
            if(deque.size() == cap) {
                Deque<Integer> newDeque = new ArrayDeque<>();
                newDeque.add(val);
                stack.add(newDeque);
            }else deque.push(val);
        }
    }

    public int pop() {
        if(stack.isEmpty()) return -1;
        Deque<Integer> deque = stack.get(stack.size() - 1);
        int res = deque.pop();
        if (deque.isEmpty()) {
            stack.remove(stack.size() - 1);
        }return res;
    }

    public int popAt(int index) {
        if(index>=stack.size()) return -1;
        Deque<Integer> deque = stack.get(index);
        int res = deque.pop();
        if(deque.isEmpty()) {
            stack.remove(index);
        }return res;
    }
}

面试题 03.04. 化栈为队 - 力扣（LeetCode）

呃 好像变成最慢那档了 16ms

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
class MyQueue {
     
     Deque<Integer> pop;
     Deque<Integer> push;
     boolean flag = false;
     
    /** Initialize your data structure here. */
    public MyQueue() {
        pop = new ArrayDeque<Integer>();
        push = new ArrayDeque<Integer>();
    }

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

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

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

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return pop.isEmpty() && push.isEmpty();
    }
}

改用Stack快了许多 到第二梯队了 11ms

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
class MyQueue {

     Stack<Integer> pop;
     Stack<Integer> push;
     boolean flag = false;

    /** Initialize your data structure here. */
    public MyQueue() {
        pop = new Stack<Integer>();
        push = new Stack<Integer>();
    }

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

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

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

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return pop.isEmpty() && push.isEmpty();
    }
}

面试题 03.05. 栈排序 - 力扣（LeetCode）

816ms “回去等通知”

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 SortedStack {

     Stack<Integer> stack = new Stack<>();

    public SortedStack() {

    }

    public void push(int val) {
        if(stack.isEmpty()) {stack.push(val);return;}
        Stack<Integer> temp = new Stack<>();
        int pop;
        while(!stack.isEmpty()) {
            pop = stack.pop();
            if(pop<=val) temp.push(pop);
            else{
                stack.push(pop);
                break;
            }
        }
        stack.push(val);
        while(!temp.isEmpty()) {
            stack.push(temp.pop());
        }
    }

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

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

    public boolean isEmpty() {
        return stack.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
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();
    }
}

面试题 03.06. 动物收容所 - 力扣（LeetCode）

又是个sb题目 这系列的题目都是些傻逼题

也没说编号是自增的 浪费时间找最早动物 不想改了

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 {

     Deque<int[]> cats;
     Deque<int[]> dogs;
     Deque<int[]> any;

    public AnimalShelf() {
        cats = new LinkedList<>();
        dogs = new LinkedList<>();
        any = new LinkedList<>();
    }

    public void enqueue(int[] animal) {
        if(animal[1]==0) cats.push(animal);
        else dogs.push(animal);
        any.push(animal);
    }

    public int[] dequeueAny() {
        if(any.isEmpty()) return new int[]{-1,-1};
        int[] res = any.removeLast();
        if(res[1]==0) cats.removeLast();
        else dogs.removeLast();
        return res;
    }

    public int[] dequeueDog() {
        if(dogs.isEmpty()) return new int[]{-1,-1};
        int[] res = dogs.removeLast();
        any.remove(res);
        return res;
    }

    public int[] dequeueCat() {
        if(cats.isEmpty()) return new int[]{-1,-1};
        int[] res = cats.removeLast();
        any.remove(res);
        return res;
    }
}