1. 有效的括号

image-20200629174328167
我的思路：

知道要用到栈，但是实际操作的时候出现了问题！

好的思路：

  1. 建立一个堆栈

  2. 当遇到 (、[、{ 的时候，将与之对应的括号放入堆栈

    当遇到 )、]、} 时，说明栈顶一 定是与之相对应的括号，如果堆栈为空或者栈顶不是与之相对应的括号，则括号无效

  3. 最后如果堆栈为空则说明括号有效！

代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        for (char c: s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            else if (stack.isEmpty() || (c != stack.pop())) return false;
        }
        return stack.isEmpty();
    }
}

2. 合并两个有序链表

image-20200630164948870
我的思路：
  1. 设置一个头节点保存链表的头部，用于最后返回结果
  2. 依次遍历两条链表，谁的值小谁就依次跟在头节点的后面
  3. 一直遍历直到两条链表遍历完毕（l1 == null && l2 == null）
代码实现：
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0,null);
        ListNode head = node;
        while (l1 != null || l2 != null) {
            // 两条链表都未遍历完毕
            if (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    node.next = l1
                    l1 = l1.next;
                } else {
                    node.next = l2;
                    l2 = l2.next;
                }
            } else if (l1 != null) {	// l2 遍历完毕
                    node.next = l1;
                    l1 = l1.next;
            } else {					// l1 遍历完毕
                    node.next = l2;
                    l2 = l2.next;
            }
            node = node.next;
        }

        return head.next;
    }
}
更好的想法1：

大体与我的思路相同，区别在于当两条链中一条为空时，直接将 node.next 设为不空的那条链（减少不必要的循环）

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
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

/*
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
更好的想法2：
image-20200630172234489 
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
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }
}

/*
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

3. 移除元素

image-20200712175712277
思路：

当 nums[j] 与给定的值相等时，递增 j 以跳过该元素。只要 nums[j] != val，我们就复制 nums[j] 到 nums[i] 并同时递增两个索引。重复这一过程，直到 j 到达数组的末尾，该数组的新长度为 i。

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

代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

/*
作者：LeetCode
链接：https://leetcode-cn.com/problems/remove-element/solution/yi-chu-yuan-su-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

4. 删除排序数组中的重复项

image-20200630180751937
思路：

与上题一致

代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                nums[++i] = nums[j];
            }
        }
        // 返回数组的长度： i = 1，length = 2
        return i + 1;
    }
}

5. 实现 strStr()

image-20200630184748964
我的思路：

遍历字符串 haystack，当 haystack 中有元素与 needle 中第一个元素相同时，截取 haystack 中该元素后的字串判断是否与 needle 相同。

代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int strStr(String haystack, String needle) {

        if ("".equals(needle)) return 0;
        if (haystack.length() < needle.length()) return -1;

        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                if (i + needle.length() > haystack.length()) return -1; 
                if (haystack.substring(i,i + needle.length()).equals(needle)) return i;
            }
        }

        return -1;
    }
}