力扣labuladong一刷day2共7题

力扣labuladong一刷day2共8题 | 26. 删除有序数组中的重复项 83. 删除排序链表中的重复元素

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

题目链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
思路：快慢指针，因为要删除重复元素，慢指针只有在快指针与前一个元素不等时才往前走一步，收集一个唯一元素。

class Solution {
  public int removeDuplicates(int[] nums) {
        if (nums.length == 1) return 1;
        int slow = 0, k = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                k++;
                nums[++slow] = nums[i];
            }
        }
        return k;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

二、83. 删除排序链表中的重复元素

题目链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
思路：和上一题类似，也是快慢指针，只不过是在链表里操作。

class Solution {
   public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode root = new ListNode(-1, head);
        ListNode slow = head, fast = head;
        while (fast != null) {
            if (slow.val != fast.val) {
                slow.next = fast;
                slow = slow.next;
            }
            fast = fast.next;
        }
        slow.next = null;
        return root.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

三、27. 移除元素

题目链接：https://leetcode.com/problems/remove-element/
思路：快慢指针，快指针元素与要删除的元素不相等就用快指针覆盖慢指针，如果相等就只需要快指针前进。

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

四、283. 移动零

题目链接：https://leetcode.cn/problems/move-zeroes/
思路：和前面的删除元素是一样的，只不过把0都删除以后再把数组后面的元素都改成0.

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[slow++] = nums[i];
            }
        }
        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

五、167. 两数之和 II - 输入有序数组

题目链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/
思路：要求两数之和等于target，可以采用类似于二分查找的方法，left=0，right=nums.length-1.sum>tagert right–，sum

class Solution {
   public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length-1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left+1, right+1};
            }else if (sum < target) {
                left++;
            }else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

六、344. 反转字符串

题目链接：https://leetcode.cn/problems/reverse-string/
思路：左右指针。

class Solution {
   public void reverseString(char[] s) {
        int left = 0, right = s.length-1;
        while (left < right) {
            char c = s[left];
            s[left] = s[right];
            s[right] = c;
            left++;
            right--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

七、5. 最长回文子串

题目链接：https://leetcode.cn/problems/longest-palindromic-substring/
思路：寻找最长的回文子串，利用回文子串的特性，应该基于任意一个点从中间向两端扩散寻找，扩散时分为奇数和偶数进行扩散。

class Solution {
   public String longestPalindrome(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            String s1 = f1(s, i, i);
            String s2 = f1(s, i, i+1);
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }
    String f1(String s, int l, int r) {
        while (l >= 0 && r <= s.length()-1 && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return s.substring(l+1, r);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19