Posted Updated LeetCode / Easya minute read (About 187 words)

88. Merge Sorted Array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

采用双指针，从结尾开始遍历两个数组。
比较后按倒叙插入第一个数组。

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

Posted Updated LeetCode / Easya minute read (About 136 words)

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

采用哈希表储存遍历过的数值及下标，查表如果有键则返回其下标及当前下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        int[] ans = new int[2];
        
        for (int i = 0; i < nums.length; i++){
            int result = target - nums[i];
            if ( map.containsKey(result) ){
                ans[0] = map.get(result);
                ans[1] = i;
                return ans;
            }
            else{
                map.put(nums[i], i);
            }
        }
        return ans;
    }
}

Posted Updated LeetCode / Medium / 复习a minute read (About 146 words)

189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

环型替换，先求出数列长度和轮转次数的最大公约数m。
然后依次替换数列中的每个值。

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
//Rotate Array

class Solution {
    public void rotate(int[] nums, int k) {
        if (k != 0){
            int m = gcd(nums.length,k);
        
            for (int n = 0; n < m; n++ ) {
                int i = n + k;
                i %= nums.length;

                int temp = nums[n];
                while( true ){
                    int tempI = nums[i];
                    nums[i] = temp;
                    temp = tempI;
                
                    i += k;
                    i %= nums.length;
                
                    if (i == n){
                        nums[n] = temp;
                        break;
                    }
                }
            }
        }
    }
    
    private int gcd(int a, int b){
        int max = a;
        int min = b;
        if (max == min){
            return min;
        }
        
        if ( a < b ){
            max = b;
            min = a;
        }
        
        return gcd(max - min, min);
    }
}

Posted Updated LeetCode / Easya minute read (About 118 words)

977. Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

采取双指针，同时比较两侧的正负及大小。

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
class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int i = nums.length-1;
        int[] ans = new int[nums.length];
        
        while (left <= right) {
            if ( nums[left] < 0 ){
                if ( (-nums[left]) < nums[right] ){
                    ans[i] = nums[right] * nums[right];
                    right--;
                }
                else {
                    ans[i] = nums[left] * nums[left];
                    left++;
                }
                i--;
            }
            else{
                if ( nums[left] < nums[right] ){
                    ans[i] = nums[right] * nums[right];
                    right--;
                }
                else{
                    ans[i] = nums[left] * nums[left];
                    left++;
                }
                i--;
            }
        }
        return ans;
    }
}

Posted Updated a few seconds read (About 23 words)

测试一下

我想测试一下这篇文章能否正常的发送

标题
结尾
斜体

Follow

Recents

Archives

Links

×