链表数组字符串双指针

LeetCode

发布日期: 2019-04-15

文章字数: 1.7k

阅读时长: 7 分

阅读次数:

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

题目描述

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

解题思路

使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

如果两个指针指向元素的和 sum == target，那么得到要求的结果；
如果 sum > target，移动较大的元素，使 sum 变小一些；
如果 sum < target，移动较小的元素，使 sum 变大一些。

public int[] twoSum(int[] numbers, int target) {
    int i = 0, j = numbers.length - 1;
    while (i < j) {
        int sum = numbers[i] + numbers[j];
        if (sum == target) {
            return new int[]{i + 1, j + 1};
        } else if (sum < target) {
            i++;
        } else {
            j--;
        }
    }
    return null;
}

633. 平方数之和

题目描述

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2 + b^2 = c。

示例1:

输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5

示例2:

输入: 3
输出: False

解题思路

双指针，小的是 0 ，大的是 sqrt(c)

public boolean judgeSquareSum(int c) {
    int i = 0, j = (int) Math.sqrt(c);
    while (i <= j) {
        int powSum = i * i + j * j;
        if (powSum == c) {
            return true;
        } else if (powSum > c) {
            j--;
        } else {
            i++;
        }
    }
    return false;
}

345. 反转字符串中的元音字母

题目描述

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

示例 1:

输入: "hello"
输出: "holle"

示例 2:

输入: "leetcode"
输出: "leotcede"

说明:
元音字母不包含字母”y”。

解题思路

构造一个HashSet来存放元音字母

private final static HashSet<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));

public String reverseVowels(String s) {
    int i = 0, j = s.length() - 1;
    char[] result = new char[s.length()];
    while (i <= j) {
        char ci = s.charAt(i);
        char cj = s.charAt(j);
        if (!vowels.contains(ci)) {
            result[i++] = ci;
        } else if (!vowels.contains(cj)) {
            result[j--] = cj;
        } else {
            result[i++] = cj;
            result[j--] = ci;
        }
    }
    return new String(result);
}

680. 验证回文字符串 Ⅱ

题目描述

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: "aba"
输出: True

示例 2:

输入: "abca"
输出: True
解释: 你可以删除c字符。

注意:

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

解题思路

设置一个辅助函数，判断常规的回文字符串。

public boolean validPalindrome(String s) {
    int i = -1, j = s.length();
    while(++i < --j){
        if(s.charAt(i) != s.charAt(j)){
            return (isPalindrome(s,i,j-1) || isPalindrome(s,i+1,j));
        }
    }
    return true;

}

private boolean isPalindrome(String s, int i, int j){
    while(i < j){
        if (s.charAt(i++) != s.charAt(j--))
            return false;
    }
    return true;
}

88. 合并两个有序数组

题目描述

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

解题思路

从后往前遍历，不然会覆盖没有用过的值
考虑其中一个数组已经遍历完，就把nums1剩下的值全置为没有被遍历完的那个数组的值

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1;
    int l = m + n - 1;
    while(i >= 0 || j >= 0){
        if (i < 0)
            nums1[l--] = nums2[j--];
        else if (j < 0)
            nums1[l--] = nums1[i--];
        else if(nums1[i]>=nums2[j])
            nums1[l--] = nums1[i--];
        else
            nums1[l--] = nums2[j--];
    }
}

141. 环形链表

题目描述

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

解题思路

一个快指针，一次移动两个节点；一个慢指针，一次移动一个节点。如果有环，这两个指针肯定会相遇。

另外要注意 while循环的条件，快指针要做双重判断。

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null)
        return false;
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow !=null && fast != null && fast.next != null){
        if(slow == fast)
            return true;
        slow = slow.next;
        fast = fast.next.next;
    }
    return false;
}

524. 通过删除字母匹配到字典里最长单词

题目描述

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

示例 1:

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

输出: 
"apple"

示例 2:

输入:
s = "abpcplea", d = ["a","b","c"]

输出: 
"a"

说明:

所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。

解题思路

通过双指针查看字典中的一个字符串是不是给定字符串的子序列
通过compareTo在同样长度下，找到字典顺序更小的那个

public String findLongestWord(String s, List<String> d) {
    String longestWord = "";
    for (String str : d){
        int l1 = longestWord.length();
        int l2 = str.length();
        if (isSubsequence(s, str)){
            if (l2 > l1 || (l2 == l1) && str.compareTo(longestWord)<0)
                longestWord = str;
        }
    }
    return longestWord;
}

private boolean isSubsequence(String s, String target){
    int i = 0, j = 0;
    while (i < s.length() && j < target.length()){
        if (s.charAt(i) == target.charAt(j))
            j++;
        i++;
    }
    return j == target.length();
}