• 【无标题】


    双指针

    leetcode26删除有序数组中的重复项

    给你一个 升序排列 的数组 nums ,请你** 原地** 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致

    示例 1:

    输入:nums = [1,1,2]
    输出:2, nums = [1,2,_]
    解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
    示例 2:

    输入:nums = [0,0,1,1,1,2,2,3,3,4]
    输出:5, nums = [0,1,2,3,4]
    解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

    提示:

    1 <= nums.length <= 3 * 104
    -104 <= nums[i] <= 104
    nums 已按 升序 排列

    class Solution {
        public int removeDuplicates(int[] nums) {
            int i = 1, j = 1;
            while (j < nums.length) {
                //想好i指针移动的条件是什么
                if (nums[j] != nums[j - 1]) {
                    nums[i] = nums[j];
                    i++;
                }
                j++;
            }
            return i;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    leetcode283移动零

    给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

    请注意 ,必须在不复制数组的情况下原地对数组进行操作。

    示例 1:

    输入: nums = [0,1,0,3,12]
    输出: [1,3,12,0,0]
    示例 2:

    输入: nums = [0]
    输出: [0]

    提示:

    1 <= nums.length <= 104
    -231 <= nums[i] <= 231 - 1

    class Solution {
        public void moveZeroes(int[] nums) {
            int i = 0, j = 0;
            //换成末尾是0,所以前面不为0的就要交换
            while (j < nums.length) {
                if (nums[j] != 0) {
                    int tmp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = tmp;
                    i++;
                }
                j++;
            }
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    leetcode80删除有序数组中的重复项2

    给你一个有序数组 nums ,请你** 原地** 删除重复出现的元素,使得出现次数超过两次的元素只出现两次 ,返回删除后数组的新长度。

    不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    示例 1:

    输入:nums = [1,1,1,2,2,3]
    输出:5, nums = [1,1,2,2,3]
    解释:函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
    
    • 1
    • 2
    • 3

    示例 2:

    输入:nums = [0,0,1,1,1,1,2,3,3]
    输出:7, nums = [0,0,1,1,2,3,3]
    解释:函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。
    
    • 1
    • 2
    • 3

    提示:

    • 1 <= nums.length <= 3 * 104
    • -104 <= nums[i] <= 104
    • nums 已按升序排列
    class Solution {
        public int removeDuplicates(int[] nums) {
            int i = 2, j = 2;
            while (j < nums.length) {
                if (nums[i - 2] != nums[j]) {
                    nums[i] = nums[j];
                    i++;
                }
                j++;
            }
            return i;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    leetcode1047删除字符串所有相邻重复项

    给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母,并删除它们。

    在 S 上反复执行重复项删除操作,直到无法继续删除。

    在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

    示例:

    输入:"abbaca"
    输出:"ca"
    解释:
    例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。
    
    • 1
    • 2
    • 3
    • 4

    提示:

    1. 1 <= S.length <= 20000
    2. S 仅由小写英文字母组成。
    class Solution {
        public String removeDuplicates(String s) {
            StringBuffer stack = new StringBuffer();
            int top = -1;
            //在一个栈中玩消消乐
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (top >= 0 && stack.charAt(top) == ch) {
                    stack.deleteCharAt(top);
                    --top;
                } else {
                    stack.append(ch);
                    ++top;
                }
            }
            return stack.toString();
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    leetcode344反转字符串

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

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

    示例 1:

    输入:s = ["h","e","l","l","o"]
    输出:["o","l","l","e","h"]
    
    • 1
    • 2

    示例 2:

    输入:s = ["H","a","n","n","a","h"]
    输出:["h","a","n","n","a","H"]
    
    • 1
    • 2

    提示:

    • 1 <= s.length <= 105
    • s[i] 都是 ASCII 码表中的可打印字符
    class Solution {
        public void reverseString(char[] s) {
            for(int i = 0, j = s.length - 1; i < j; i++, j--) {
                char tmp = s[i];
                s[i] = s[j];
                s[j] = tmp;
            }
            // System.out.println(s);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    leetcode11盛最多水的容器

    给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0)(i, height[i])

    找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

    返回容器可以储存的最大水量。

    **说明:**你不能倾斜容器。

    示例 1:

    img

    输入:[1,8,6,2,5,4,8,3,7]
    
    • 1
    输入:[1,8,6,2,5,4,8,3,7]
    输出:49 
    解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
    
    • 1
    • 2
    • 3

    示例 2:

    输入:height = [1,1]
    输出:1
    
    • 1
    • 2

    提示:

    • n == height.length
    • 2 <= n <= 105
    • 0 <= height[i] <= 104
    class Solution {
        public int maxArea(int[] height) {
            int i = 0, j = height.length - 1;
            int ans = 0;
            while (i < j) {
                int area = Math.min(height[i], height[j]) * (j - i);
                ans = Math.max(ans, area);
                if (height[i] < height[j]) {
                    i++;
                } else {
                    j--;
                }
            }
            return ans;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    leetcode42接雨水

    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

    示例 1:

    img

    输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
    输出:6
    解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 
    
    • 1
    • 2
    • 3

    示例 2:

    输入:height = [4,2,0,3,2,5]
    输出:9
    
    • 1
    • 2

    提示:

    • n == height.length
    • 1 <= n <= 2 * 104
    • 0 <= height[i] <= 105
    class Solution {
        public int trap(int[] height) {
            int ans = 0;
            int i = 0, j = height.length - 1;
            int iMax = 0, jMax = 0;
            //对于 i<n0≤i<n,下标 i 处能接的雨水量等于min(leftMax[i],rightMax[i])−height[i]
            //leftMax表示i左边最最大值,rightMax表示i右边最大值
            while (i < j) {
                iMax = Math.max(iMax, height[i]);
                jMax = Math.max(jMax, height[j]);
                if (height[i] < height[j]) {
                    ans += iMax - height[i];
                    i++
                } else {
                    ans += jMax - height[j];
                    j--;
                }
            }
            return ans;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

  • 相关阅读:
    代码随想录-015-剑指Offer206. 反转链表
    有趣且重要的JS知识合集(17)矩形框交互算法
    vue中部分知识比较
    中文编程入门(Lua5.4.6中文版)第十二章 Lua 协程 参考《愿神》游戏
    k8spod就绪检查失败
    华资软件一面
    Linux—软件管理
    算法竞赛进阶指南0x35高斯消元与线性空间
    BootStrap日历插件
    面试官问我new Vue阶段做了什么?
  • 原文地址:https://blog.csdn.net/m0_37852301/article/details/125421643