Posted Updated LeetCode / Easya few seconds read (About 83 words)

344. Reverse String

问题简述
Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

双指针，同时更新并交换两个数值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public void reverseString(char[] s) {
        int i = 0;
        int j = s.length - 1;
        
        while( i < j ) {
            char temp = s[i]; 
            s[i] = s[j];
            s[j] = temp;
            
            i++;
            j--;
        }
    }
}

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

566. Reshape the Matrix

问题概述
In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.

You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.

The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

根据数组的数学公式得出其位置，一次遍历将原数组中的数字填入。
O(r*c)

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[][] matrixReshape(int[][] mat, int r, int c) {
        
        int[][] ans = new int[r][c];

        int oldR = mat.length;
        int oldC = mat[0].length;
        
        
        if ( oldR * oldC != r * c ){
            return mat;
        }
        for (int i = 0; i < r*c ; i++ ){
            int m = i/oldC;
            int n = i%oldC;
            
            int p = i/c;
            int q = i%c;        
            ans[p][q] = mat[m][n];
        }
        return ans;
    }
}
Posted Updated LeetCode / Easya few seconds read (About 106 words)

283. Move Zeroes

问题描述
Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

双指针，i指针左侧保留大于零的元素，j指针左侧保留等于零的元素。

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

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

121. Best Time to Buy and Sell Stock

问题描述
You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

采用dp的思想，先计算一遍盈利差，再计算一遍最大收益。
空间上还可以优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxProfit(int[] prices) {
        int best = 0;
        int[] difference = new int[prices.length];
        difference[0] = 0;
        for (int i = 1; i < prices.length; i++ ){
            difference[i] = prices[i] - prices[i - 1];
            if ( difference[i] + difference[i - 1] > difference[i] ){
                difference[i] = difference[i] + difference[i - 1];
            }
            if (difference[i] > best){
                best = difference[i];
            }
        }
        return best;
    }
}


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

350. Intersection of Two Arrays II

问题描述
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any 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
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        ArrayList<Integer> arr = new ArrayList<Integer>();
        int count = 0;

        for ( int i = 0 ; i < nums1.length ; i++ ){
            if (!map.containsKey(nums1[i])){
                map.put(nums1[i],1);
            }
            else{
                map.put(nums1[i],map.get(nums1[i])+1);
            }
            
        }

        for ( int i = 0 ; i < nums2.length ; i++ ){
            if (map.containsKey(nums2[i])){
                if (map.get(nums2[i]) > 0){
                    count++;
                    arr.add(nums2[i]);
                    map.put(nums2[i],map.get(nums2[i])-1);
                }
            }
        }
        int[] ans = new int[count]; 
        
        for (int i = 0 ; i < arr.size() ; i++){
            ans[i] = arr.get(i);
        }
        return ans;
    }
}
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 / 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;
    }
}

Follow

Recents

Archives

Links

×