移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

思路

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

BF

两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组

public int removeElement(int[] nums, int val) {
    int size = nums.length;
    for (int i = 0; i < size; i++) {
        if (nums[i] == val) {
            for (int j = i + 1; j < size; j++) {
                nums[j - 1] = nums[j];
            }
            i--;
            size--;
        }
    }
    return size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

如果不加i--的话，遇见两个要移除的数在一起的话会出现错误

双指针

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

过程如下：

public int removeElement(int[] nums, int val) {
    int fast = 0;
    int slow;

    for (slow = 0; fast < nums.length; fast++) {
        if (nums[fast] != val){
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：
输入：[“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]

示例 2：
输入：[“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]

思路

双指针

public void reverseString2(char[] s) {
    for (int i = 0, j = s.length - 1; i < s.length / 2; i++, j--) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
}
1
2
3
4
5
6
7

按位异或

public void reverseString(char[] s) {
    for (int i = 0, j = s.length - 1; i < s.length / 2; i++, j--) {
        s[i] ^= s[j];
        s[j] ^= s[i];
        s[i] ^= s[j];
    }
}
1
2
3
4
5
6
7

什么是按位异或

替换空格

比较简单，遇见空格直接替换，通过stringbuffer里的方法进行的！

public String replaceSpace(String s) {
    StringBuilder sb = new StringBuilder();
    for(int i = 0 ; i < s.length(); i++){
        char c = s.charAt(i);
        if(c == ' ') sb.append("%20");
        else sb.append(c);
    }
    return sb.toString();
}
1
2
3
4
5
6
7
8
9

这题不用双指针了，太麻烦了！

翻转字符串里的单词

给你一个字符串 s ，颠倒字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = “the sky is blue”
输出：“blue is sky the”
示例 2：

输入：s = " hello world " 输出：“world hello”
解释：颠倒后的字符串中不能存在前导空格和尾随空格。
示例 3：

输入：s = “a good example”
输出：“example good a”
解释：如果两个单词间有多余的空格，颠倒后的字符串需要将单词间的空格减少到仅有一个。

思路

package com.caq.string;

import java.util.Arrays;

public class ReverseString3 {

    public static void main(String[] args) {
        String s = "hello  world !  ";
        ReverseString3 re = new ReverseString3();
        String s3 = re.reverseWors(s);
        System.out.println(s3);
    }

    /**
     * 1.去除首尾以及中间多余空格
     * 2.反转整个字符串
     * 3.反转单词
     */
    public String reverseWors(String s) {
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    /**
     * 移除空格
     *
     * @param s
     * @return
     */
    private StringBuilder removeSpace(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        return sb;
    }

    /**
     * 反转字符串
     * 反转数组就是最基本的双指针
     * 这里反转字符串借助StringBuilder完成
     */
    public void reverseString(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }

    /**
     * 反转字母
     * 怎么反转的呢，一组一组的去反转
     *
     * @param sb
     */
    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
//            对空格不进行反转，选择跳过
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            //对字母进行再次反转
            //这里的end-1是因为end的索引是从1开始的，不减1到后面会越界
            reverseString(sb, start, end - 1);
            /**
             * 注意这里是意思是反转完第一组单词后，进行第二组单词的反转
             * 此时要给start指针和end指针重新赋值，start指针的赋值为end+1，也就是跳过了空字符串的情况
             * 上一步经过反转的end指针的位置是end-1
             */
            start = end + 1;
            end = start + 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
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

反转链表

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

双指针法

public ListNode reverseList(ListNode head) {

    ListNode prev = null;
    ListNode cur = head;
    ListNode temp = null;

    while (cur != null) {
        temp = cur.next;
        cur.next = prev;
        prev = cur;
        cur = temp;
    }
    
    //返回后的头节点
    return prev;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

递归法

public ListNode reverseList2(ListNode head) {
    return reverse(null, head);
}

//递归
private ListNode reverse(ListNode prev, ListNode cur) {
    if (cur == null) {
        return prev;//这里是为了最后的反转
    }
    ListNode temp = null;
    temp = cur.next;
    cur.next = prev;
    return reverse(cur,temp);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2：

输入：head = [1], n = 1 输出：[] 示例 3：

输入：head = [1,2], n = 1 输出：[1]

思路

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了

代码

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;
        while (n-- > 0) {
            fast = fast.next;
        }
        // 记住 待删除节点slow 的上一节点
        ListNode prev = null;
        while (fast != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next;
        }
        // 上一节点的next指针绕过 待删除节点slow 直接指向slow的下一节点
        prev.next = slow.next;
        // 释放 待删除节点slow 的next指针, 这句删掉也能AC
        slow.next = null;

        return dummy.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三数之和

思路

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

时间复杂度：O(n^2)。

暴力思路

三层for循环

public class TheSumOfThreeNumbers {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        ArrayList<List<Integer>> arrayList = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (sum == 0){
                        arrayList.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    }
                }
            }
        }
        arrayList.forEach(x -> System.out.println(x));

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

不太行，因为[-1,0,1],[0,1,-1]]算是重复的啦，换位置也不行

双指针

看明白之后，可以debug很好理解！

public static List<List<Integer>> threeSum(int[] nums) {
        ArrayList<List<Integer>> result = new ArrayList<>();//存放结果集，格式为[[],[],[]....]
        Arrays.sort(nums); //对目标数据进行排序

        if (nums == null || nums.length < 3) {
            return result;
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return result;      //临界条件的一些判断,如果排序后的第一个数都大于0那么三数之后不可能为0
            }
            /**
             * 加上i > 0是因为第一个数没和前一个数比较，会出现数组越界
             * 为i-1是因为，i是增加的，它要和后面的数比较看是否相等
             */
            if (i > 0 && nums[i] == nums[i - 1]) { //
                continue;   //这里是对i的去重
            }
            int left = i + 1;   //左指针
            int right = nums.length - 1;    //右指针
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;    //和大于0，说明加的太大了，只能让right左移
                } else if (sum < 0) {
                    left++; //和小于0，说明加的太小了，只能让left右移
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));//等于0，加入结果集
                    while (right > left && nums[left] == nums[left + 1]) left++;//对右指针去重
                    while (right > left && nums[right] == nums[right - 1]) right--;//对左指针去重
                    right--;//往左移动
                    left++;//往右移动
                }
            }
        }
        return result;

    }
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

四数之和

题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

思路

四数之后，和三数之后一个思路，都是使用双指针法，基本解法就是在三数之和的基础上再套一层for循环

使用四个指针(a

保存使得nums[a]+nums[b]+nums[c]+nums[d]==target的解。偏大时d左移，偏小时c右移。c和d相遇时，表示以当前的a和b为最小值的解已经全部求得。b++,进入下一轮循环b循环，当b循环结束后。a++，进入下一轮a循环。 即(a在最外层循环，里面嵌套b循环，再嵌套双指针c,d包夹求解)。

准备工作：

因为要使用双指针的方法，排序是必须要做

解决重复解：

上面的解法存在重复解的原因是因为移动指针时可能出现重复数字的情况。所以我们要确保移动指针后， 对应的数字要发生改变才行哦。

public List<List<Integer>> fourSum(int[] nums, int target) {
        //存放结果集
        List<List<Integer>> result = new ArrayList<>();

        //使用双指针必须排序
        Arrays.sort(nums);

        //控制第一层循环
        for (int i = 0; i < nums.length; i++) {

            // nums[i] > target 直接返回, 返回为空，因为第一个数都大于目标值的话后面相加不可能等于target
            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }

            //对第一个指针进行一个去重的操作
//            这里的i>0是为了预防数组越界
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }

            //控制第二层循环
            for (int j = i + 1; j < nums.length; j++) {

                //对第二个指针进行去重的操作
                if (j > i + 1 && nums[j - 1] == nums[j]) {
                    continue;
                }

                //第三个指针的位置
                int left = j + 1;

                //第四个指针的位置
                int right = nums.length - 1;

                //控制第三个和第四个指针碰头，另外两个指针不动
                while (right > left) {
                    //计算是否等于目标值
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];

                    //如果target小于sum，第四个指针左移，因为第三个指针已经是数组中倒数第三小的了
                    if (sum > target) {
                        right--;
                        //如果target大于sum，移动第三个指针，因为第四个指针已经是数组中最大值了
                    } else if (sum < target) {
                        left++;
                        //如果target等于sum，那么返回数组中的数对应的索引下标，并把它们当成集合的形式传到结果集中
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

                        //找到结果之后还要对三、四指针进行去重操作
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        //如果不重复那就三、四指针正常移动
                        left++;
                        right--;
                    }
                }
            }
        }
        //返回结果集
        return result;
    }
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