本节内容

数组理论基础
704. 二分查找
27. 移除元素

二分查找的模板： https://www.yuanql.top/2023/03/30/02_leetcode/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E6%A8%A1%E6%9D%BF/

数组理论基础

文章链接：https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
题目建议：了解一下数组基础，以及数组的内存空间地址，数组也没那么简单。

704. 二分查找 ※

题目建议：大家能把 704 掌握就可以，35.搜索插入位置 和 34. 在排序数组中查找元素的第一个和最后一个位置，如果有时间就去看一下，没时间可以先不看，二刷的时候在看。

先把 704写熟练，要熟悉根据 左闭右开，左闭右闭 两种区间规则写出来的二分法。

题目链接：https://leetcode.cn/problems/binary-search/
文章讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
视频讲解：https://www.bilibili.com/video/BV1fA4y1o715

题目分析

注意
见到有顺序的数组（有些无序的数组也可以通过排序变成有序的），就要想到是否可以使用二分法，都来碰碰瓷。但是当数组中有重复数据的时候，，二分查找返回的数据将是不唯一的，所以此时要慎用二分法。

通过二分法查找数据是否在有序数组中，如果存在，则直接返回下标；如果不存在，则返回-1

终止条件：
1、找到了匹配的数值；
2、中间节点和左节点碰撞，还未找到target的数值，则跳出，返回-1。但是此时需要考虑一种特殊情况：数组的最右侧节点是target数值。

特殊情况一言以蔽之：数组的首末尾顾及不到，需要特殊处理。

方案一

class Solution {
    public int search(int[] nums, int target) {

        int left = 0, right = nums.length -1, middle = (left + right) / 2;

        while (left < middle) {
            if (nums[middle] > target) {
                right = middle;
            } else if (nums[middle] < target) {
                left = middle;
            } else {
                return middle;
            }
            middle = (left + right) / 2;
        }

        // 特殊判断，此时target在 数组的首位，即下标为0的位置
        if (nums[middle] == target) {
            return middle;
        }

        // 特殊判断，此时target在 数组的末位，即下标为`nums.length - 1`的位置
        if (nums[nums.length - 1] == target){
            return nums.length - 1;
        }

        return -1;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:43 MB,击败了60.18% 的Java用户

分析

时间复杂度：
O( log n )

空间复杂度：
O( 1 )

代码随想录

https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF

注意
求两个数据的中值的时候， ( i + j ) / 2 与 i + ( j - i ) / 2 其最终结果是一致的，但是最后面的是没有越界的风险，建议使用第二的方案求解中值。

方案一：左闭右闭

class Solution {
    public int search(int[] nums, int target) {

        int left = 0, right = nums.length - 1, middle = left + (right - left) / 2;

        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }

        while (left <= right) {
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                return middle;
            }
            middle = left + (right - left) / 2;
        }
        return -1;
    }
}

方案二：左闭右开

class Solution {
    public int search(int[] nums, int target) {

        int left = 0, right = nums.length, middle = left + (right - left) / 2;

        while (left < right) {
            if (nums[middle] > target) {
                right = middle;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                return middle;
            }
            middle = left + (right - left) / 2;
        }
        return -1;
    }
}

35. 搜索插入位置

https://leetcode.cn/problems/search-insert-position/

https://www.yuanql.top/2023/03/30/02_leetcode/35.%20%E6%90%9C%E7%B4%A2%E6%8F%92%E5%85%A5%E4%BD%8D%E7%BD%AE/

题目分析

二分法找到需要插入数据的下标

方案一

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1, middle = 0;

        while (left <= right ) {
            middle = left + (right - left) / 2;

            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }

        }
        return left;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:42.1 MB,击败了55.91% 的Java用户

分析

时间复杂度：
O( log n )

空间复杂度：
O( 1 )

34. 在排序数组中查找元素的第一个和最后一个位置

题目： https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

https://www.yuanql.top/2023/04/03/02_leetcode/34.%20%E5%9C%A8%E6%8E%92%E5%BA%8F%E6%95%B0%E7%BB%84%E4%B8%AD%E6%9F%A5%E6%89%BE%E5%85%83%E7%B4%A0%E7%9A%84%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%92%8C%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%E4%BD%8D%E7%BD%AE/

题目分析

方案一

先通过二分法找到和 target 相同的数值，然后根据 target 的数值作为中间的节点，对两边的通过二分法进行求解，来得到相关的边界。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        int left = 0, right = nums.length - 1, middle = 0, flag = 0;

        // 随便找到一个等于
        while (left <= right) {
            middle = left + (right - left) / 2;
            if (nums[middle] == target) {
                flag = 1;
                break;
            } else if (nums[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        // 此时数组中不存在 target 的数值，直接返回 [-1, -1]
        if (flag == 0) {
            return result;
        }
        // 此时数组中存在 target 的数组。
        flag = middle;
        int right_mid = middle, left_mid = middle;

        while (left <= right_mid) {
            middle = left + (right_mid - left) / 2;
            if (nums[middle] == target) {
                right_mid = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        result[0] = left;

        while (left_mid <= right) {
            middle = left_mid + (right - left_mid) / 2;
            if (nums[middle] == target) {
                left_mid = middle + 1;
            } else {
                right = middle -1;
            }
        }
        result[1] = right;

        return result;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:43.4 MB,击败了77.06% 的Java用户

分析

时间复杂度：
O( log n )

空间复杂度：
O( 1 )

27. 移除元素※

题目建议：暴力的解法，可以锻炼一下我们的代码实现能力，建议先把暴力写法写一遍。双指针法是本题的精髓，今日需要掌握，至于拓展题目可以先不看。

题目链接：https://leetcode.cn/problems/remove-element/
文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP

https://www.yuanql.top/2023/03/29/02_leetcode/27.%20%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0/

题目分析

双指针，快指针去找不与target相等的数值，慢指针用于记录需要插入的位置。

方案一

class Solution {
    public int removeElement(int[] nums, int val) {
        // 双指针
        int slow = 0, fast = 0, temp = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[fast] == val) {
                fast++;
            } else {
                nums[slow] = nums[fast];
                slow++;
                fast++;
            }
        }
        return slow;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:40.1 MB,击败了33.23% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

代码随想录

https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html

方案一：暴力求解

方案二：双指针法

class Solution {
    public int removeElement(int[] nums, int val) {
        // 快慢指针
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}

//相向双指针法
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(right >= 0 && nums[right] == val) right--; //将right移到从右数第一个值不为val的位置
        while(left <= right) {
            if(nums[left] == val) { //left位置的元素需要移除
                //将right位置的元素移到left（覆盖），right位置移除
                nums[left] = nums[right];
                right--;
            }
            left++;
            while(right >= 0 && nums[right] == val) right--;
        }
        return left;
    }
}

26. 删除有序数组中的重复项

题目链接： https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

题目分析

方案一

快慢指针，快指针判断数据是否和当前慢指针所指向的数值相等，只有不相等的时候才向后移动一位

class Solution {
    public int removeDuplicates(int[] nums) {
        int slow = 0;
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                nums[++slow] = nums[fast];
            }
        }
        return ++slow;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了26.60% 的Java用户
内存消耗:42.7 MB,击败了93.98% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

283. 移动零

官方题目链接： https://leetcode.cn/problems/move-zeroes/

题目分析

方案一

通过快慢指针将所有为零的数据移动到数值的前列，遍历完毕之后，将慢指针之后的所有数据置为0。

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow++] = nums[fast];
            }
        }
        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

结果

解答成功:
执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:44.1 MB,击败了35.43% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

844. 比较含退格的字符串

官方题目链接： https://leetcode.cn/problems/backspace-string-compare/

题目分析

从后向前遍历，慢指针一步步走，当慢指针碰到 # 的时候，快指针跳两步。然后等待慢指针，当其遇到的时候，则代表此时此数据没有被删除，在慢指针追快指针的时候，只有碰到 # ，快指针才会向前走两步，要不然会一致呆在原地不动。另外当快慢指针在一起，也没有碰到 # ，两者就携手向前，一起前进。

方案一

感觉写了一坨屎堆

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int s_slow = s.length() - 1, s_fast = s_slow, t_slow = t.length() - 1, t_fast = t_slow;

        while (true) {
            // 找出字符串 s 的退位之后的值
            while (!(s_slow == s_fast && s.charAt(s_slow) != '#')) {
                if (s.charAt(s_slow) == '#') {
                    s_fast = s_fast - 2;
                    if (s_fast < 0) {
                        break;
                    }
                }
                s_slow--;
            }
            // 找出字符串 t 的退位之后的值
            while (!(t_slow == t_fast && t.charAt(t_slow) != '#')) {
                if (t.charAt(t_slow) == '#') {
                    t_fast = t_fast - 2;
                    if (t_fast < 0) {
                        break;
                    }
                }
                t_slow--;
            }

            if (s_fast < 0 || t_fast < 0) {
                if (s_fast < 0 && t_fast < 0) {
                    return true;
                }
                return false;
            }

            if (s.charAt(s_fast) != t.charAt(t_fast)) {
                return false;
            }

            if (s_fast == 0 || t_fast == 0) {
                if (s_fast == 0 && t_fast == 0) {
                    return true;
                } else {
                    if (s_fast == 0) {
                        t_slow--;
                        t_fast--;
                        // 找出字符串 t 的退位之后的值
                        while (!(t_slow == t_fast && t.charAt(t_slow) != '#')) {
                            if (t.charAt(t_slow) == '#') {
                                t_fast = t_fast - 2;
                                if (t_fast < 0) {
                                    break;
                                }
                            }
                            t_slow--;
                        }
                        if (t_fast < 0) {
                            return true;
                        }
                        return false;
                    } else if (t_fast == 0) {
                        s_slow--;
                        s_fast--;
                        // 找出字符串 s 的退位之后的值
                        while (!(s_slow == s_fast && s.charAt(s_slow) != '#')) {
                            if (s.charAt(s_slow) == '#') {
                                s_fast = s_fast - 2;
                                if (s_fast < 0) {
                                    break;
                                }
                            }
                            s_slow--;
                        }
                        if (s_fast < 0) {
                            return true;
                        }
                        return false;
                    }
                }
            }

            s_slow--;
            s_fast--;
            t_slow--;
            t_fast--;
        }
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.7 MB,击败了45.95% 的Java用户

分析

时间复杂度：
O( n + m )

空间复杂度：
O( 1 )

尝试对重复内容进行抽取，简化代码

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int s_fast = s.length() - 1,  t_fast = t.length() - 1;

        while (true) {
            // 找出字符串 s 的退位之后的值
            s_fast = selectNum(s_fast, s);

            // 找出字符串 t 的退位之后的值
            t_fast = selectNum(t_fast, t);


            // 当两方有一方的数值小于的的时候，意味着此字符串已经没有字符了，如果另外一个还有，就必然是false
            if (s_fast < 0 || t_fast < 0) {
                if (s_fast < 0 && t_fast < 0) {
                    return true;
                }
                return false;
            }

            // 当两个字符串的末尾不相等，则直接意味着 false
            if (s.charAt(s_fast) != t.charAt(t_fast)) {
                return false;
            }

            //当字符串其中一个到达了0 的时候要特殊判断，要不然再下一步进行 减运算的时候就会报错了
            if (s_fast == 0 || t_fast == 0) {
                // 都到了0，万事大吉，直接为 true
                if (s_fast == 0 && t_fast == 0) {
                    return true;
                } else { // 不全为0 的时候就要判断了，只能求另外一个字符有足够多的退位符，当其不足够的时候，代表其长度都不同
                    if (s_fast == 0) {
                        t_fast--;
                        // 找出字符串 t 的退位之后的值
                        t_fast = selectNum(t_fast, t);

                        if (t_fast < 0) { // 此时长度相同，有足够多的退位符，剩下的都是null
                            return true;
                        }
                        return false; // 意味着另外一个字符串中还剩下字符，长度不同
                    } else if (t_fast == 0) {
                        s_fast--;
                        // 找出字符串 s 的退位之后的值
                        s_fast = selectNum(s_fast, s);

                        if (s_fast < 0) {
                            return true;
                        }
                        return false;
                    }
                }
            }
            s_fast--; // 此处字符判断完毕，向前移动一格
            t_fast--;
        }
    }

    public int selectNum(int fast, String s) {
        int slow = fast;

        while (!(slow == fast && s.charAt(slow) != '#')) {
            if (s.charAt(slow) == '#') {
                fast = fast - 2;
                if (fast < 0) {
                    break;
                }
            }
            slow--;
        }
        return fast;
    }
}

官方题解

https://leetcode.cn/problems/backspace-string-compare/solution/bi-jiao-han-tui-ge-de-zi-fu-chuan-by-leetcode-solu/

方案一：使用栈的思想，重构字符串

class Solution {
    public boolean backspaceCompare(String S, String T) {
        return build(S).equals(build(T));
    }

    public String build(String str) {
        StringBuffer ret = new StringBuffer();
        int length = str.length();
        for (int i = 0; i < length; ++i) {
            char ch = str.charAt(i);
            if (ch != '#') {
                ret.append(ch);
            } else {
                if (ret.length() > 0) {
                    ret.deleteCharAt(ret.length() - 1);
                }
            }
        }
        return ret.toString();
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/backspace-string-compare/solution/bi-jiao-han-tui-ge-de-zi-fu-chuan-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方案二

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (S.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (S.charAt(i) != T.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/backspace-string-compare/solution/bi-jiao-han-tui-ge-de-zi-fu-chuan-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

02_1_代码随想录算法训练营18期

#LeetCode #算法训练营

01、第一章数组part01

http://yuanql.top/2023/07/12/02_1_代码随想录算法训练营18期/01、第一章数组part01/

作者

Qingli Yuan

发布于

2023年7月12日

许可协议

02、第一章数组part02 上一篇

94、144、145、二叉树的前、中、后序遍历下一篇

01、第一章 数组part01

本节内容

数组理论基础

704. 二分查找 ※

题目分析

方案一

结果

分析

代码随想录

方案一：左闭右闭

方案二：左闭右开

35. 搜索插入位置

题目分析

方案一

结果

分析

34. 在排序数组中查找元素的第一个和最后一个位置

题目分析

方案一

结果

分析

27. 移除元素※

题目分析

方案一

结果

分析

代码随想录

方案一： 暴力求解

方案二： 双指针法

26. 删除有序数组中的重复项

题目分析

方案一

结果

分析

283. 移动零

题目分析

方案一

结果

分析

844. 比较含退格的字符串

题目分析

方案一

结果

分析

尝试对重复内容进行抽取，简化代码

官方题解

方案一：使用栈的思想，重构字符串

方案二

01、第一章数组part01

方案一：暴力求解

方案二：双指针法