52Heartz's Blog

分享科技与生活

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/valid-palindrome/

题目难度：Easy

题目

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

1
2
Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

1
2
Input: "race a car"
Output: false

分析

只考虑字母和数字。忽略大小写。

解答1[Java]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isPalindrome(String s) {
        char[] charMap = new char[256];
        for (int i = 0; i < 10; i++) {
            // numeric - don't use 0 as it's reserved for illegal chars
            charMap['0' + i] = (char) (1 + i);
        }
        for (int i = 0; i < 26; i++) {
            //alphabetic, ignore cases, continue from 11
            charMap['a' + i] = charMap['A' + i] = (char) (11 + i);
        }

        for (int start = 0, end = s.length() - 1; start < end; ) {
            if (charMap[s.charAt(start)] == 0) {
                start++;
            } else if (charMap[s.charAt(end)] == 0) {
                end--;
            } else if (charMap[s.charAt(start++)] != charMap[s.charAt(end--)]) {
                return false;
            }
        }
        return true;
    }
}

思路

先打一个表。

注意：通过 charMap['A'] 这种方式访问数组元素的时候，Java 会自动把 [] 中的字符转换为 int 型。

解答2[Java]：

1
2
3
4
5
6
7
public class Solution {
    public boolean isPalindrome(String s) {
        String actual = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
        String rev = new StringBuffer(actual).reverse().toString();
        return actual.equals(rev);
    }
}

使用正则表达式和 Java 的类库。先把所有字母都转换成小写，反转字符串然后对比。

其他

发现 Java 的连等赋值好像比非连等赋值性能要更好一些。

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/kth-largest-element-in-an-array/

题目难度：Medium

解答1[Java]：

1
2
3
4
5
6
7
8
import java.util.Arrays;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        Arrays.sort(nums);
        return nums[len-k];
    }
}

但是这个实现依赖了 Java 的库，并不是一个通用的解法。

解答2

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
//move the k largest elements to the left part of array
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums.length == 1)
            return nums[0];

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int pivotPos = partition(nums, left, right);
            if (pivotPos - left + 1 < k) {
                k = k - (pivotPos - left + 1);// shrink k value
                left = pivotPos + 1;// move left to pivotPos + 1
            } else if (pivotPos - left + 1 > k) {
                right = pivotPos - 1;// shrink right by 1 at least
            } else {
                return nums[pivotPos];
            }
        }
        return 0;
    }

    // make elements value between [0, leftBound] are all >= pivot
    private int partition(int[] array, int left, int right) {
        int pivotIndex = left + (right - left) / 2;
        int pivot = array[pivotIndex];
        swap(array, pivotIndex, right);

        int leftBound = left;
        int rightBound = right - 1;
        while (leftBound <= rightBound) {
            if (array[leftBound] >= pivot) {
                leftBound++;
            } else if (array[rightBound] < pivot) {
                rightBound--;
            } else {
                swap(array, leftBound++, rightBound--);
            }
        }
        swap(array, leftBound, right);
        return leftBound;
    }

    private void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}

要理解这个算法需要对快速排序算法有所了解。

每次 partition 之后，pivotPos 左边的元素都是大于 pivotPos的，右边的都是小于 PivotPos的，根据 pivotPos的index 和 k 的关系就能确定如果要继续寻找是在 pivotPos 左边寻找还是右边寻找。

参考资料

  1. 深入理解Java PriorityQueue

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/merge-sorted-array/

题目难度：Easy

题目

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

1
2
3
4
5
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

解答1[Java]

思路

新建一个数组，然后把待合并的数组的元素依次填充到新数组中。

实现

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
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] result = new int[m + n];
        int index = 0;
        int i = 0;
        int j = 0;
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                result[index++] = nums1[i++];
            } else {
                result[index++] = nums2[j++];
            }
        }

        if (i == m) {
            while (j < n) {
                result[index++] = nums2[j++];
            }
        }
        if (j == n) {
            while (i < m) {
                result[index++] = nums1[i++];
            }
        }

        for (int k = 0; k < result.length; k++) {
            nums1[k] = result[k];
        }

    }
}

复杂度分析

空间复杂度为 $O(m+n)$。

时间复杂度为 $O(m+n)$。

解答2[Java]

思路

既然数组1后边有多余的位置，就从后面开始填充，从后向前，原地合并。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        
        // 数组2如果还有剩余元素，说明数组1已经全部归位了
        // 数组2如果没有剩余元素，则数组2已经全部归位了，数组1前边的元素不需要动
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

复杂度分析

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/sort-colors/

题目难度：Medium

解答1[Java]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public void sortColors(int[] nums) {
        int zero = -1;
        int two = nums.length;
        int temp;

        for (int i = 0; i < two;) {
            if (nums[i] == 1)
                i++;
            else if (nums[i] == 2) {
                temp = nums[--two];
                nums[two] = nums[i];
                nums[i] = temp;
            } else {
                temp = nums[++zero];
                nums[zero] = nums[i];
                nums[i++] = temp;
            }
        }
    }
}

三路快排的思路

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

题目难度：Medium

解答1[Java]：

1
2
3
4
5
6
7
8
9
class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int n : nums)
            if (i < 2 || n > nums[i - 2])
                nums[i++] = n;
        return i;
    }
}

补充解答：修改版

1
2
3
4
5
6
7
int removeDuplicates(vector<int>& nums,int k) {
    if(nums.size()<k) return nums.size(); // if array size is less than k then return the same
    int i,j;
     for(i=k,j=k ; i<nums.size();i++)
         if(nums[j-k]!=nums[i]) nums[j++]=nums[i];
     return j;
}

这个解答，可以适用于保留最多不超过 K 个相同的元素。

和第一种解法的思路相似，j-k 就是 lookback，向后看。第一种解法是 nums[i-2]，往后看两位。现在是往后看 k 位。

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/remove-duplicates-from-sorted-array/

题目难度：Easy

解答1[Java]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;

        int head = 0;
        int tail = 0;
        for (; tail < nums.length; tail++) {
            if (nums[head] != nums[tail]) {
                nums[++head] = nums[tail];
            }
        }

        return head + 1;
    }
}

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/move-zeroes/

题目难度：Easy

解答1[Java]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.ArrayList;
class Solution {
    public void moveZeroes(int[] nums) {
        ArrayList<Integer> nonZeroElements = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nonZeroElements.add(Integer.valueOf((nums[i])));
            }
        }

        for (int i = 0; i < nonZeroElements.size(); i++) {
            nums[i] = nonZeroElements.get(i).intValue();
        }

        for (int i = nonZeroElements.size(); i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(n)$

解答2[Java]：

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

        for (int i = k; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

第 6 到 10 行有一个判断：

1
2
3
4
5
if (k != i) {
    nums[k++] = nums[i];
} else {
    k++;
}

这个判断其实可以不要，因为只要遇到第一个 0 元素之后，后边的判断就是多余的了。不如改为直接赋值。加上了判断就一定会判断 n 次，但是如果直接赋值，多余的赋值操作的次数是少于 n 次的，所以开销更小。

所以 5-11 行可以直接改为：

1
2
3
4
if (nums[j] != val) {
    nums[i] = nums[j];
    i++;
}

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(1)$

对末尾加零的操作优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void moveZeroes(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                if (k != i) {
                    nums[k++] = nums[i];
                    nums[i] = 0;         // 优化的部分
                } else {
                    k++;
                }
            }
        }
    }
}
0%