01数组与字符串

面试题 01.01. 判定字符是否唯一

难度简单229

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

使用数组统计每个字符出现的个数, 如果有出现次数大于一次的, 说明有重复字符 , 也就是! 全都不同

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isUnique(String astr) {
        int[]cnt=new int[26];
        for (char c : astr.toCharArray()) {
            cnt[c-'a']++;
        }
        for (int i : cnt) {
            if(i>1) return false;
        }
        return true;
    }
}

面试题 01.02. 判定是否互为字符重排

难度简单78

给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

全部排序然后判断是否相同即可

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        Arrays.sort(chars1);
        Arrays.sort(chars2);
        return Arrays.equals(chars1, chars2);
    }
}

面试题 01.03. URL化

难度简单82

URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）

  • 题目说的知道真实的长度, 大概的意思就是后面的有些空格是有效的, 所以本题如果直接trim(), 就WA 了

解法:

  • 提前遍历, 获取空格的个数
  • 遍历, 如果遇到空格, 就赋值%20

返回赋值的字符数组即可 (new String)

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 String replaceSpaces(String S, int length) {
        int cnt=0; // 统计空格数量
        S=S.substring(0,length);
        for (char c : S.toCharArray()) {
            if(c==' ') cnt++;
        }
        int charsLen= 2*cnt +S.length();
        char []chars=new char[charsLen];
        int i=0;
        for (char c : S.toCharArray()) {
            chars[i]=c;
            if(c==' ') {
                chars[i]='%';
                chars[++i]='2';
                chars[++i]='0';
            }
            i++;
        }
        return new String(chars);
    }
}

面试题 01.04. 回文排列

难度简单89

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。

回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。

回文串不一定是字典当中的单词。

  • 首先, 需要知道的是, 回文字符串左右对称, 也就是说至多有一个只出现一次的字符,
  • 至多有一个出现奇数次的字符 ,因此循环统计字符即可

涉及到字符串的排列, 考虑使用计数法 ( 统计每个字符出现的次数)

  • 统计出现奇数次的字符的数量, 如果奇数次的字符的数量 >1 , 说明不是某个回文字符串的排列之一
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) {
        int []cnt=new int[128];
        for (char c : s.toCharArray()) {
            cnt[c]++;
        }
        int times=0;
        for (int i : cnt) {
            if((i&1)==1){
                times++;
            }
            if(times>1){
                return false;
            }
        }
        return true;
    }
}

面试题 01.05. 一次编辑

难度中等222

字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

对应的有几种情况:

  1. 两个字符串, 长度差距>=2 ,直接return false

  2. 两个字符串长度相同 ,那么比较两个字符串, 如果不相同的字符的个数>=2 ,return false

  3. 两个字符串的长度相差==1 , 那么使用双指针, 允许两个字符串不相同的字符的个数<=2,

    image-20220813153829215image-20220813153829215

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 boolean oneEditAway(String first, String second) {
        int lf=first.length(),ls=second.length();
        if(lf<ls) return oneEditAway(second,first); // 始终保持 lf 是较长的那个字符串
        if(lf-ls>1) return false; //长度差异 >=2 , 直接false;
        if(lf-ls==0){
            char[]chars1=first.toCharArray();
            char[]chars2=second.toCharArray();
            int cnt=0;
            for (int i = 0; i < chars1.length; i++) {
                if(chars1[i]!=chars2[i]) cnt++;
            }
            return cnt<=1;
        }
        // 下面对应的是长度相差为1 的情况  lf 较长
        char[]chars1=first.toCharArray();
        char[]chars2=second.toCharArray();
        int i=0,error=0;
        while(i<ls){// 需要小于较短的那个字符串的长度
            if(chars2[i]!=chars1[i+error]){
                if(++error>1) return false;
            }else{
                i++;
            }
        }
        return true;
    }
}

面试题 01.06. 字符串压缩

难度简单144

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

  • 遍历添加, 最后比较长度即可
  • 注意 变短是需要 sb.toString().length()<len
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) {
        int len=S.length();
        int i=0,cnt=0;
        StringBuilder sb=new StringBuilder();
        while(i<len){
            cnt=0;
            char temp=S.charAt(i);
            while(i<len&&temp==S.charAt(i)){
                i++;
                cnt++;
            }
            sb.append(temp);
            sb.append(cnt);
        }
        return sb.toString().length()<len?sb.toString():S;
    }
}

面试题 01.07. 旋转矩阵

难度中等243

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

  • 方形矩阵

以矩阵的四个角为例, 分别为:

  • 左上 : A
  • 左下 : B
  • 右下 : C
  • 右上 : D

旋转的过程也就是:

  • temp=A
  • A=B
  • B=C
  • C=D
  • D=temp

  • 对于矩阵的

    循环次数

    • 当N 为偶数时候, 直接取前 n/2 行、前n/2 列的元素为起始点
    • 当N 为奇数时候, 直接取前 n/2 行、前n+1/2 列的元素为起始点
    • image-20220813162447484image-20220813162447484
    • 通过上图的N=3 的矩阵不难发现, 旋转只需要进行两次即可, 1->3->9->7 , 2->6->8->4 , i始终为0 , j = (0,1)

  • 对于矩阵的坐标, 可以看图理解

image-20220813162141312image-20220813162141312

  • 左上 : (i,j)
  • 左下 : (N-j-1,i)
  • 右下 : (N-j-1,N-i-1)
  • 左上 : (j,N-i-1)

依次赋值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void rotate(int[][] matrix) {
        //顺时针将矩阵旋转 90°
        int n = matrix.length;
        for (int i = 0; i < n /2; i++) {
            for (int j = 0; j < (n+1)/2; j++) {
                int temp =matrix[i][j];
                matrix[i][j]=matrix[n -j-1][i];//左上
                matrix[n -j-1][i]=matrix[n -i-1][n -j-1]; //左下
                matrix[n -i-1][n -j-1]=matrix[j][n -i-1];//右下
                matrix[j][n -i-1]=temp;//右上
            }
        }
    }
}

面试题 01.08. 零矩阵

难度中等73

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

  • 遍历, 遇到 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
class Solution {
    public void setZeroes(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j]==0){
                    for (int i1 = 0; i1 < matrix.length; i1++) { //赋值当前列
                        if(matrix[i1][j]!=0)
                            matrix[i1][j]=0x3f3f3f;
                    }
                    for (int j1 = 0; j1 < matrix[i].length; j1++) { //赋值当前行
                        if(matrix[i][j1]!=0)
                            matrix[i][j1]=0x3f3f3f;
                    }
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j]==0x3f3f3f){
                    matrix[i][j]=0;
                }
            }
        }
    }
}

面试题 01.09. 字符串轮转

难度简单123

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。

遍历字符串, 如果遇到了首字符相同的情况, 就比较是否相同

  • 原本的做法是

    1
    2
    3
    4
    if(s1.charAt(i)==s2.charAt(0)){
        String pre=s1.substring(idx,i);
        return (s1.substring(i)+pre).equals(s2);
    }

    这样做的缺点是, 如果遇到了字符串比较长,相同字符很多的情况, 就只能验证第一个相同的字符

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

image-20220813172936497image-20220813172936497

  • 优化版
    • isTrue提前返回 ,
    • 需要注意的是需要把isTrue的判断写在后面, 否则会遇到最后一个字符才是相同字符的情况无法通过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if(s1.equals(s2)) return true; //""  ""
        if(s1.length()!=s2.length()) return false;
        boolean isTrue=false;
        for (int i = 0; i < s1.length(); i++) {
            if(s1.charAt(i)==s2.charAt(0)){
                String pre=s1.substring(0,i);
                isTrue=(s1.substring(i)+pre).equals(s2)||isTrue;
            }
            if(isTrue) return true;
        }
        return false;
    }
}

image-20220813172958550image-20220813172958550

简易解法:

  • 长度相等 &&
  • 如果是true的话, s2+s2 必定会包含 s1
1
2
3
4
5
class Solution {
    public boolean isFlipedString(String s1, String s2) {
        return s1.length() == s2.length() && (s2 + s2).contains(s1);
    }
}

02链表

面试题 02.01. 移除重复节点

难度简单164

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

双指针, 使用一个前置pre , 用来更改链表的指向

使用Set来确定元素是否重复

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 singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        Set<Integer> set=new HashSet<>();
        ListNode res=head;
        ListNode pre = new ListNode(0);
        pre.next=head;
        while(head!=null){
            if(set.add(head.val)){ // 能添加,这个节点第一次出现
                pre=head;
            }else{ // 不能添加, 使 pre.next=head.next;
                pre.next=head.next;
            }
            head=head.next;
        }
        return res;
    }
}

面试题 02.02. 返回倒数第 k 个节点

难度简单112

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

  • 遍历全部节点, 同时添加元素, 然后返回对应下标的元素即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthToLast(ListNode head, int k) {
        List<Integer> list=new ArrayList<>();
        while(head!=null){
            list.add(head.val);
            head=head.next;
        }
        return list.get(list.size()-k);
    }
}
  • 使用双指针, 先让前面的一个指针多走 K 步, 然后两个指针同时移动, 当前面的那个指针遍历结束, 后面的指针的指向也就是 倒数第K 个节点
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int kthToLast(ListNode head, int k) {
        ListNode pre=head;
        for (int i = 0; i < k; i++)
            pre=pre.next;
        while(pre!=null&&head!=null){
            pre=pre.next;
            head=head.next;
        }
        return head.val;
    }
}

面试题 02.03. 删除中间节点

难度简单161

若链表中的某个节点，既不是链表头节点，也不是链表尾节点，则称其为该链表的「中间节点」。

假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。

例如，传入节点 c（位于单向链表 a->b->c->d->e->f 中），将其删除后，剩余链表为 a->b->d->e->f

题意很迷惑

直接让当前节点的值=下一个节点的值, 然后修改指向, 使当前节点指向下一个节点指向的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val=node.next.val;
        node.next=node.next.next;
    }
}
  • Cpp
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        *node=*node->next;
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val=node->next->val;
        node->next=node->next->next;
    }
};

面试题 02.04. 分割链表

难度中等111

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

多new 两个链表, 一个用来存储小于x 的数据 ,一个用来存储大于x 的数据

最后拼接两个链表即可

image-20220814091022450image-20220814091022450

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode cur=head;
        ListNode small=new ListNode(0);
        ListNode small_head=small;
        ListNode big=new ListNode(0);
        ListNode big_head=big;
        while(cur!=null){
            if(cur.val<x){
                small.next=new ListNode(cur.val);
                small=small.next;
            }else{
                big.next=new ListNode(cur.val);
                big=big.next;
            }
            cur=cur.next;
        }
        small.next=big_head.next;
        return small_head.next;
    }
}

面试题 02.05. 链表求和

难度中等141

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

image-20220814094107613image-20220814094107613

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.math.BigInteger;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        StringBuilder s1=new StringBuilder();
        StringBuilder s2=new StringBuilder();
        while(l1!=null){
            s1.append(l1.val);
            l1=l1.next;
        }
        while(l2!=null){
            s2.append(l2.val);
            l2=l2.next;
        }
        s1.reverse();
        s2.reverse();
        BigInteger b1=new BigInteger(s1.toString());
        BigInteger b2=new BigInteger(s2.toString());
        b1=b1.add(b2);
        ListNode op=new ListNode(b1.mod(new BigInteger("10")).intValue());
        ListNode res=op;
        b1=b1.divide(new BigInteger("10"));
        while(!b1.equals(new BigInteger("0"))){
            op.next=new ListNode(b1.mod(new BigInteger("10")).intValue());
            b1=b1.divide(new BigInteger("10"));
            op=op.next;
        }
        return res;
    }

}

面试题 02.06. 回文链表

难度简单119

编写一个函数，检查输入的链表是否是回文的。

  • 使用list 存储数值, 然后遍历判断数值是否对称, 需要O(n) 的额外空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> list=new ArrayList<>();
        while(head!=null){
            list.add(head.val);
            head=head.next;
        }
        Integer[] integers = list.toArray(new Integer[list.size()]);
        int len=integers.length;
        for (int i = 0; i < integers.length/2; i++) {
            if(!Objects.equals(integers[i], integers[len - i - 1])) return false;
        }
        return true;
    }
}
  • 快慢指针
  • 快的一次走两个节点, 慢的一次走一个节点, 当快的走不动的时候, 慢的刚刚好走到链表的中间结点, 如果是双数节点的话, 走到的是前半部分的末尾结点

算法流程:

  1. 通过快慢指针找到链表的中间结点(slow) : 节点数量为双数时就是前半部分的末尾结点, 奇数时就是链表的中间结点
  2. 翻转后半部分链表reverseListNode(ListNode endHalf)
  3. 比较两个部分的值, 如果不相同, 直接返回 false;
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
/**
 * 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 fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
//快的一次走两个节点, 慢的一次走一个节点, 当快的走不动的时候, 慢的刚刚好走到链表的中间结点, 如果是双数节点的话, 走到的是前半部分的末尾结点
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode endHalf= slow;// 后半部分
        endHalf=reverseListNode(endHalf); //翻转后半部分
        ListNode startHalf=head;// 前半部分
        while(startHalf!=slow.next){
            if(startHalf.val!= endHalf.val) return false;
            startHalf=startHalf.next;
            endHalf=endHalf.next;
        }
        return true;
    }
    
    public ListNode reverseListNode(ListNode head){ // 翻转链表, 并返回翻转后的链表的头结点, 也就是原本的链表的末尾结点
        ListNode pre=new ListNode(0);
        ListNode cur=head;
        while(cur!=null){
            ListNode temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
}
  • 需要注意的是, 我们需要判断一个链表是否是回文链表时, 通常是不希望这个链表的本身被改变的 ,因此最后最后将链表翻转回去
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 boolean isPalindrome(ListNode head) {
        // 走到中间的节点,
        if(head==null) return true;
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
//快的一次走两个节点, 慢的一次走一个节点, 当快的走不动的时候, 慢的刚刚好走到链表的中间结点, 如果是双数节点的话, 走到的是前半部分的末尾结点
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode endHalf= slow;// 后半部分
        endHalf=reverseListNode(endHalf); //翻转后半部分
        ListNode needReverse=endHalf; // 通过这个引用最后将链表翻转回去
        ListNode startHalf=head;// 前半部分
        boolean isSame=true;
        while(isSame&&startHalf!=slow.next){
            if(startHalf.val!= endHalf.val) isSame=false;
            startHalf=startHalf.next;
            endHalf=endHalf.next;
        }
        reverseListNode(needReverse);
        return isSame;
    }
    
    public ListNode reverseListNode(ListNode head){ // 翻转链表, 并返回翻转后的链表的头结点, 也就是原本的链表的末尾结点
        ListNode pre=new ListNode(0);
        ListNode cur=head;
        while(cur!=null){
            ListNode temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
}

面试题 02.07. 链表相交

难度简单251

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

image-20220814122433580image-20220814122433580

设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c ，

则有：

  • 头节点 headA 到 node 前，共有 a - c 个节点；
  • 头节点 headB 到 node 前，共有 b - c 个节点；

image-20220807164155572image-20220807164155572

注意在判断 三目运算符的 条件应该是需要是 A == null? 而不是 A.next==null?,

因为如果遇到了没有公共节点的情况, 前者就会陷入死循环,

  • 正确的情况应该是 : 如果没有公共节点, A , B会同时指向null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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) {
        ListNode A=headA;
        ListNode B=headB;
        while(A!=B){// 需要是 A==null? 而不是 A.next==null? , 因为如果遇到了没有公共节点的情况, 前者就会陷入死循环, 正确的情况应该是 : 如果没有公共节点, A , B会同时指向null
            A= A==null?headB:A.next;
            B= B==null?headA:B.next;
        }
        return A;
    }
}

面试题 02.08. 环路检测

难度中等105

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

image-20220814155741572image-20220814155741572

使用快慢指针, 它们起始都位于链表的头部。

slow 指针每次向后移动一个位置，

而 fast 指针向后移动两个位置。

  • 如果链表中存在环，则 fast指针最终将再次与slow 指针在环中相遇。

image-20220814155859788image-20220814155859788

我们假设 环的长度为 (b+c)

  • b为slow进入环中与fast相遇之前所走过的长度
  • c表示剩余的长度
  • 紫色的点表示slow与fast相遇的点

a为非环部分的长度

fig1fig1

  • 由于我们的fast 每次走的距离都是 slow的二倍

  • 那么由上图可以得出下列式子:

    • 2(a+b) = a+ n(b+c)+ b

      1
      2
      3
      4
      5
      6
      7
      8

        - 其中 `a+b` 为`slow`走过的距离
        - `a+ n(b+c)+ b`为`fast`走过的距离 , n表示`fast`已经走过的完整的圈数

      - 那么由上面的式子可以得出:

        - ```
          a=(n-1)b+nc
      

  - `a=(n-1)(b+c) + c`

    • 也就是说 , 当前位于相遇点的 slow只需要再走 c 的长度, 就可以到达入环点

因此可以得出下面的代码:

1
2
3
4
5
slow=head;
while(slow!=fast){
    slow=slow.next;
    fast=fast.next;
}
  • 这段代码也就是让slow从head开始走, fast继续从相遇的点开始走,
  • 每次都走一步, 当他们相遇时, 刚好能够到达入环点 , 此时直接return即可
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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null) return null;
        //快慢指针
        ListNode fast=head.next.next;
        ListNode slow=head.next;
        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;  // 表示遇到了null , 说明链表中不存在环
        slow=head;
        while(slow!=fast){
            slow=slow.next;
            fast=fast.next;
        }
        return fast;
    }
}

03栈与队列

面试题 03.01. 三合一

难度简单52

三合一。描述如何只用一个数组来实现三个栈。

你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标，value表示压入的值。

构造函数会传入一个stackSize参数，代表每个栈的大小。

  • 好恶心

使用二维数组存储数据, 通过HashMap 存储下标

  • 注意边界条件
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
class TripleInOne {
    Map<Integer,Integer> location=new HashMap<>();
    {
        location.put(0,0); // 前面的表示的是 栈的序号, 后面的是表示的下标
        location.put(1,0);
        location.put(2,0);
    }
    int [][]stack;
    public TripleInOne(int stackSize) {
        stack=new int[3][stackSize];
        if(stack[0].length!=0){
            stack[0][0]=0x3f3f3f;
            stack[1][0]=0x3f3f3f;
            stack[2][0]=0x3f3f3f;
        }
    }

    public void push(int stackNum, int value) {
        if(stack[0].length==0) return;
        if(location.get(stackNum)==stack[0].length) return ; // 栈满, 直接返回s
        stack[stackNum][location.get(stackNum)]=value;
        location.put(stackNum,location.get(stackNum)+1);
    }

    public int pop(int stackNum) {
        if(stack[0].length==0) return -1;
        if(location.get(stackNum)<1) return -1;
        int res=stack[stackNum][location.get(stackNum)-1];
        stack[stackNum][location.get(stackNum)-1]=0x3f3f3f; // 使用0x3f3f3f标记数字,表示这个数字为null
        location.put(stackNum,location.get(stackNum)-1);
        return res==0x3f3f3f?-1:res;
    }

    public int peek(int stackNum) {
        if(stack[0].length==0) return -1;
        if(location.get(stackNum)<1) return -1;
        int res=stack[stackNum][location.get(stackNum)-1];
        return res==0x3f3f3f?-1:res;
    }

    public boolean isEmpty(int stackNum) {
        if(stack[0].length==0) return true;
        return stack[stackNum][0]==0x3f3f3f;
    }
}

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

面试题 03.02. 栈的最小值

难度简单78

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

使用一个独立的栈用来记录, min , 思路与单调队列类似

需要注意的是push 里面的那个 x<=min.peek() , 需要是 <= , 比如下面的这个测试用例:

1
2
["MinStack","push","push","push","push","getMin","pop","getMin","pop","getMin","pop","getMin"]`
`[[],[2],[0],[3],[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 MinStack {
    Stack<Integer> stack=new Stack<>();
    Stack<Integer> min=new Stack<>();
    /** initialize your data structure here. */
    public MinStack() {
    }

    public void push(int x) {
        if(min.size()==0||x<= min.peek()){
            min.push(x);
        }
        stack.push(x);
    }

    public void pop() {
        if(stack.pop().equals(min.peek())){
            min.pop();
        }
    }

    public int top() {
        return  stack.size()==0?0:stack.peek();
    }

    public int getMin() {
        return min.size()==0?0: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();
 */

面试题 03.03. 堆盘子

难度中等47

堆盘子。设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。 进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。

当某个栈为空时，应当删除该栈。当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1.

简单模拟即可

  • 注意 cap=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
38
39
40
 class StackOfPlates {

    List<Stack<Integer>> stacks=new ArrayList<>();
    int max_Size;
    public StackOfPlates(int cap) {
        max_Size=cap;
        stacks.add(new Stack<>());
    }

    public void push(int val) {
        if(max_Size==0) return ;
        if(stacks.size()==0||stacks.get(stacks.size()-1).size()==max_Size){ // 当前栈满
            stacks.add(new Stack<>());
        }
        stacks.get(stacks.size()-1).push(val);
    }

     public int pop() {
         if(stacks.isEmpty()||stacks.get(0).size() == 0) return -1;
         int res=stacks.get(stacks.size()-1).pop();
         if(stacks.get(stacks.size()-1).isEmpty()) stacks.remove(stacks.size()-1);
         return res;
     }

    public int popAt(int index) {
        if(max_Size==0) return -1;
        if(index>=stacks.size()) return -1;
        int res=stacks.get(index).pop();
        if(stacks.get(index).size()==0) stacks.remove(index);
        return res;
    }
}

/**
 * Your StackOfPlates object will be instantiated and called as such:
 * StackOfPlates obj = new StackOfPlates(cap);
 * obj.push(val);
 * int param_2 = obj.pop();
 * int param_3 = obj.popAt(index);
 */

面试题 03.04. 化栈为队

难度简单58

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

将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于pop 和 peek 操作。

每次 pop 或 peek 时，

若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

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

    Stack<Integer> read=new Stack<>();
    Stack<Integer> write=new Stack<>();

    /** Initialize your data structure here. */
    public MyQueue() {

    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        write.push(x);
    }
    // 1 2 3     3 2 1
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(read.size()==0){
            while(write.size()!=0){
                read.push(write.pop());
            }
        }
        return read.pop();
    }

    /** Get the front element. */
    public int peek() {
        if(read.size()==0){
            while(write.size()!=0){
                read.push(write.pop());
            }
        }
        return read.peek();
    }

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

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

面试题 03.05. 栈排序

难度中等76

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class SortedStack {
    Stack<Integer> stack=new Stack<>();
    // 3 6 7 5   5 7 6 3
    public SortedStack() {

    }

    public void sort(){// 最小的位于栈顶(别的元素是无序的)  正确做法是 将栈全部排序
        Stack<Integer> buffer=new Stack<>();
        while(stack.size()!=0){
            int temp=stack.pop();
            while(!buffer.isEmpty()&&buffer.peek()>temp){ // 把辅助栈的 大于当前的元素全部弹出
                stack.push(buffer.pop());
            }
            buffer.push(temp);
        }
        while(buffer.size()!=0){
            stack.push(buffer.pop());
        }
    }

    public void push(int val) {
        stack.push(val);
        sort();
    }

    public void pop() {
        if(stack.size()==0) return ;
        stack.pop();
    }

    public int peek() {
        return stack.size()==0?-1:stack.peek();
    }

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

JAVA 双栈+惰性更新 17ms 99.38% - 栈排序 - 力扣（LeetCode）

image-20220815230111692image-20220815230111692image-20220815231802920image-20220815231802920

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. 动物收容所

难度简单45

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

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

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

简单模拟即可

  • 使用dog ,cat 记录两种动物的数量,
  • 使用Deque存储动物
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
class AnimalShelf {
    Deque<Integer[]> deque=new LinkedList<>();
    int dog=0;
    int cat=0;
    public AnimalShelf() {

    }

    public void enqueue(int[] animal) { //cat: 0 ,  dog 1
        if(animal[1] == 0 ){
            cat++;
        }else dog++;
        deque.offerLast(new Integer[]{animal[0],animal[1]});
    }

    public int[] dequeueAny() {
        if(deque.size()==0) return new int[]{-1, - 1};
        Integer[] pop = deque.pop();
        int []animal=new int[]{pop[0],pop[1]};
        if(animal[1] == 0 ){
            cat--;
        }else dog--;
        return animal;
    }

    public int[] dequeueDog() {
        if(dog<=0){
            return new int[]{-1,-1};
        }else{
            dog-- ;
            Deque<Integer[]> tmp=new LinkedList<>();
            Integer[]pop=deque.pop();
            while(pop[1]!=1){
                tmp.offerLast(pop);
                pop=deque.pop();
            }
            while(tmp.size()!=0){ // 从前面开始添加 tmp
                deque.offerFirst(tmp.pollLast());
            }
            return new int[]{pop[0],1};
        }
    }

    public int[] dequeueCat() {
        if(cat<=0){
            return new int[]{-1,-1};
        }else{
            cat-- ;
            Deque<Integer[]> tmp=new LinkedList<>();
            Integer[]pop=deque.pop();
            while(pop[1]!=0){
                tmp.offerLast(pop);
                pop=deque.pop();
            }
            while(tmp.size()!=0){ // 从前面开始添加 tmp
                deque.offerFirst(tmp.pollLast());
            }
            return new int[]{pop[0],0};
        }
    }
}

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