数组

发表于 | 分类于

Leetcode

283. Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

解题思路

将后面的非0元素往前挪，在nums中，使得[0, k)中的元素均为非0元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void moveZeroes(int[] nums) {
        int k = 0;
        
        for(int i = 0; i < nums.length; ++i){
            if(nums[i] != 0){
                if(i != k){
                    swap(nums, i, k);
                }
                ++k;	//k在成为非0元素的索引后，向前挪
            }
        }
    }
    
    private void swap(int []nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

27. Remove Element

Given an array and a value, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:

1
2
3
Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.

解题思路

类似于上题，将非val元素往前挪

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0;  // (k, nums.length)为val数组
        
        for(int i = 0; i < nums.length; ++i){
            if(nums[i] != val){
                if(i != k){
                    swap(nums, i, k);
                }
                ++k;
            }
        }
        return k;
    }
    
    private void swap(int []nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example:

1
2
3
4
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the new length.

解题思路

nums[k]为非重复数组的最后一个元素
遍历数组，每次两两比较，当前元素索引i若是与i-1不同，令nums[k]=nums[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length < 2){
            return nums.length;
        }
        
        int k = 1;  //下一个非重复元素的索引
        for(int i = 1; i < nums.length; ++i){
            if(nums[i] != nums[k-1]){
                nums[k++] = nums[i];
            }
        }
        
        return k;
    }
}

80. Remove Duplicates from Sorted Array II

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.

解题思路

与前一道题目相似

[0, k)数组中为最多2次重复的元素
在遍历整个数组的时候，只需要当前的i元素不得于i-2的元素
这时将其放入前面

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 < 3){
            return nums.length;
        }
        int k = 2;	//索引k指向为下一个不重复的元素
        for(int i = 2; i < nums.length; ++i){
            if(nums[i] != nums[k-2]){
                nums[k++] = nums[i];
            }
        }
        
        return k;
    }
}

75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

解题思路

因为数组中的元素只有0,1和2，可以借助三路快排的思路

另一种简单的解题思路是：计数排序，适用于元素种类少的数组

1
0 ---> 1  <---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
class Solution {
    public void sortColors(int[] nums) {
        int i = 0;
        int p0 = -1;	//用p0和i维护0和1元素的位置
        int p2 = nums.length;
        
        
        while(i < p2){
            if(nums[i] == 2){
                swap(nums, --p2, i);	//在2放在末尾后, i指向的元素重新判断
            }
            else if(nums[i] == 1){	//对于1不处理，只增加数组的指针
                ++i;
            }
            else{
                swap(nums, ++p0, i++);	//i指向的是已排序后的1的末尾
            }
        }
    }
    
    private void swap(int []A, int i, int j){
        int t = A[i];
        A[i] = A[j];
        A[j] = t;
    }
}

88.Merge Sorted Array

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

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

解题思路

由后往前插入元素

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 merge(int[] nums1, int m, int[] nums2, int n) {
        int k = n + m - 1;
        m = m - 1;
        n = n - 1;
        
        while(m >= 0 && n >= 0){
            if(nums1[m] > nums2[n]){
                nums1[k--] = nums1[m--];
            }
            else{
                nums1[k--] = nums2[n--];
            }
        }
        
   
        while(n >= 0){
            nums1[k--] = nums2[n--];
        }
    }
}

215.Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

解题思路

快排partition思路

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
class Solution {
    public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        int lo = 0;
        int hi = nums.length - 1;
        
        while(lo < hi){
            int pos = partition(nums, lo, hi);
            if(pos == k){
                break;
            }
            else if(pos < k){
                lo = pos + 1;
            }
            else{
                hi = pos - 1;
            }
        }
        
        return nums[k];
    }
    
    private int partition(int []A, int lo, int hi){
        int i = lo;
        int j = hi + 1;
        int pivot = A[i];
        while(true){
            while(i < hi && A[++i] < pivot){}
            while(j > lo && A[--j] > pivot){}
            if(i >= j){
                break;
            }
            swap(A, i, j);
        }
        swap(A, lo, j);
        
        return j;
    }
    
    private void swap(int []A, int i, int j){
        int t = A[i];
        A[i] = A[j];
        A[j] = t;
    }
}

167. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

解题思路

对撞指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int lo = 0;
        int hi = numbers.length - 1;
        
        while(lo < hi){
            int sum = numbers[lo] + numbers[hi];
            if(sum == target){
                break;
            }
            else if(sum < target){
                ++lo;
            }
            else{
                --hi;
            }
        }
        
        int []A = new int []{lo+1, hi+1};
        
        return A;
    }
}

125. Valid Palindrome

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

For example,
“A man, a plan, a canal: Panama” is a palindrome.
“race a car” is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

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

解题思路

对撞指针，这类问题要注意索引的边界

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
class Solution {
    public boolean isPalindrome(String s) {
        int lo = 0;
        int hi = s.length() - 1;
        String ss = s.toLowerCase();
        
        while(lo < hi){
            while(lo < hi && !isAlpha(ss.charAt(lo))){ ++lo; }
            while(lo < hi && !isAlpha(ss.charAt(hi))){ --hi; }
            if(lo < hi){
                char c1 = ss.charAt(lo++);
                char c2 = ss.charAt(hi--);
                if(c1 != c2){
                    return false;
                }
            }
        }
        
        return true;
    }
    
    private boolean isAlpha(char c){
        return (c <= 'z' && c >= 'a') || (c <= 'Z' && c >= 'A') || (c <= '9' && c >= '0');
    } 
}

344. Reverse String

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = “hello”, return “olleh”.

解题思路

对撞指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public String reverseString(String s) {
        char []chars = s.toCharArray();
        int lo = 0;
        int hi = chars.length - 1;
        
        while(lo < hi){
            char t = chars[lo];
            chars[lo++] = chars[hi];
            chars[hi--] = t;
        }
        
        return new String(chars);
    }
}

345. Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = “hello”, return “holle”.

Example 2:
Given s = “leetcode”, return “leotcede”.

Note:
The vowels does not include the letter “y”.

解题思路

对撞指针，

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
class Solution {
    public String reverseVowels(String s) {
        char []chars = s.toCharArray();
        int lo = 0;
        int hi = chars.length-1;
        
        while(true){
            while(lo < hi && !isVowel(chars[lo])){ ++lo; }
            while(lo < hi && !isVowel(chars[hi])){ --hi; }
            if(lo >= hi){
                break;    
            }
            swap(chars, lo++, hi--);
        }
        
        return new String(chars);
    }
    
    private void swap(char []C, int i, int j){
        char t = C[i];
        C[i] = C[j];
        C[j] = t;
    }
    
    private boolean isVowel(char c){
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
            || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
    }
}

11. Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

解题思路

对撞指针，求sum = Min(nums[i], nums[j]) * (j - i) 的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxArea(int[] height) {
        int lo = 0;
        int hi = height.length - 1;
        int max = -1;
        
        while(lo < hi){
            int h = height[lo] < height[hi] ? height[lo++] : height[hi--];  //木桶效应, 
            int sum = h * (hi - lo + 1);    //由于上面缩短了distance(i, j), 补上+1
            max = max < sum ? sum : max;
            
        }
        
        return max;
    }
}

209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

解题思路

双索引技术
滑动窗口，求连续最短的连续子数组，要求数组和大于等于s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int l = 0;     //滑动窗口 [l, r]
        int r = -1;
        int k = nums.length + 1;    //滑动窗口大小
        int sum = 0;
        
        while(l < nums.length){	
            if(r + 1 < nums.length && sum < s){
                sum += nums[++r];
            }
            else{
                sum -= nums[l++];
            }
            
            if(sum >= s){
                k = (k < (r-l+1)) ? k : (r-l+1);
            }
        }
        
        return (k == nums.length + 1 ) ? 0 : k;
    }
}

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

解题思路

滑动窗口，注意左右边界的判定条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int lengthOfLongestSubstring(String s) {
        char []chars = s.toCharArray();
        int []visited = new int[256];
        
        int l = 0;
        int r = -1;
        int k = 0;
        
        while(l < chars.length){
            
            if(r + 1 < chars.length && visited[chars[r+1]] == 0){
                ++visited[chars[++r]];
            }
            else{
                --visited[chars[l++]];
            }
            k = k < (r-l+1) ? (r-l+1) : k;
        }
        
        return k;
    }
}

438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

1
2
3
4
5
6
7
8
9
Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

1
2
3
4
5
6
7
8
9
10
Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
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
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<Integer>();
        
        int []visited = new int[256];
        for(int i = 0; i < p.length(); ++i){
            ++visited[p.charAt(i)];
        }
        
        int start = 0;  //滑动窗口的起点，并且有start <= i
        for(int i = 0; i < s.length(); ++i){
            char c = s.charAt(i);
            --visited[c];
            //while循环找出可以确保visited[c] >= 0
            //并且当visited < 0时，将start重新设置为窗口起点
            while(visited[c] < 0){
                ++visited[s.charAt(start)];
                ++start;
            }
            
            if((i-start+1) == p.length()){
                res.add(start);
            }
        }
        
        return res;
    }
}