1. 同构字符串

image-20200730113921873

思路一：调用 api

遍历字符串 s 和字符串 t 中的每一个元素，如果每个元素第一次出现的位置都相同，则两个字符串为同构字符串（不推荐）

1
2
3
4
5
6
7
8
class Solution {
    public boolean isIsomorphic(String s, String t) {
        for (int i = 0; i < s.length(); i++) {
            if (s.indexOf(s.charAt(i)) != t.indexOf(t.charAt(i))) return false;
        }
        return true;
    }
}

思路二：HashMap 建立映射关系

两个字符串同构的含义就是字符串 s 可以唯一的映射到 t ，同时 t 也可以唯一的映射到 s

使用 HashMap，存入两个字符串中相映射的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
egg 和 add 同构，就意味着下边的映射成立
e -> a
g -> d
也就是将 egg 的 e 换成 a, g 换成 d, 就变成了 add

同时倒过来也成立
a -> e
d -> g
也就是将 add 的 a 换成 e, d 换成 g, 就变成了 egg

foo 和 bar 不同构，原因就是映射不唯一
o -> a
o -> r
其中 o 映射到了两个字母

作者：windliang
链接：https://leetcode-cn.com/problems/isomorphic-strings/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-42/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isIsomorphic(String s, String t) {
        // 需要同时验证 s->t、t->s
        return isIsomorphicHelper(s, t) && isIsomorphicHelper(t, s);
    }

    public boolean isIsomorphicHelper(String s, String t) {
        HashMap<Character, Character> map = new HashMap<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (!map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), t.charAt(i));
            } else {
                if (map.get(s.charAt(i)) != t.charAt(i)) return false;
            }
        }
        return true;
    }
}

2. 反转链表

image-20200730134355893

法一：迭代法

设置一个指针 cur 指向当前节点，设置一个指针 pre 指向当前节点的前一个节点

遍历链表：

  • 用临时变量 next 保存当前节点的下一个节点
  • 当前节点下一个节点 = pre
  • cur 变成 pre
  • next 变成 cur
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
  • 时间复杂度：O*(*n)
  • 空间复杂度：O(1)

法二：递归法

稍微有点复杂，可以参考以下回答

image-20200730135834374 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

/*
作者：LeetCode
链接：https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

3. 存在重复元素 II

image-20200903164806929

思路：滑动窗口

用散列表来维护这个 k 大小的滑动窗口。

在之前的方法中，我们知道了对数时间复杂度的 搜索 操作是不够的。在这个方法里面，我们需要一个支持在常量时间内完成 搜索，删除，插入 操作的数据结构，那就是散列表。这个算法的实现跟方法二几乎是一样的。

遍历数组，对于每个元素做以下操作：
在散列表中搜索当前元素，如果找到了就返回 true。
在散列表中插入当前元素。
如果当前散列表的大小超过了 kk， 删除散列表中最旧的元素。
返回 false。

作者：LeetCode
链接：https://leetcode-cn.com/problems/contains-duplicate-ii/solution/cun-zai-zhong-fu-yuan-su-ii-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; ++i) {
        if (set.contains(nums[i])) return true;
        set.add(nums[i]);
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }
    }
    return false;
}

4. 用队列实现栈

image-20200730151552931

思路：使用双队列

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

    private Queue<Integer> q1;		// 输入队列
    private Queue<Integer> q2;		// 输出队列

    /** Initialize your data structure here. */
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        q1.offer(x);
        while (!q2.isEmpty()) {
            q1.offer(q2.poll());
        }
        Queue temp = q1;
        q1 = q2;
        q2 = temp;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return q2.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return q2.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q2.isEmpty();
    }
}

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