Posted Updated LeetCode / Medium / 复习2 minutes read (About 264 words)

923. 3Sum With Multiplicity

Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 109 + 7.

首先遍历元素，根据元素的值和出现次数建立哈希表。
然后再哈希表中选择三个元素，如果和等于target，则计算三个元素出现次数的乘积。
最后除以重复计算的次数。
由于数值较大，因此中途计算应该采用长整型long。

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
51
52
53
54
55
class Solution {
    public int threeSumMulti(int[] arr, int target) {
        //enumberate every element and put them into the map
        HashMap<Integer, Long> map = new HashMap<Integer, Long>();
        long count = 0;
        
        for ( int num : arr ){
            if (!map.containsKey(num)){
                map.put(num, (long)1);
            }
            else{
                map.put(num, map.get(num)+1);
            }
        }
        
        //traverse whole elements and select three numbers
        
        for ( int a : map.keySet() ){
            long totalA = map.get(a);
            for (int b : map.keySet()){
                long totalB = map.get(b);
                if ( a == b ){
                    if (totalB < 2){
                        continue;
                    }
                    totalB = totalB - 1;
                }

                int c = target - a - b;
                if ( map.containsKey(c) ){
                    long totalC = map.get(c);
                    long total = 0;
                    if ( a == b && b == c ){
                        total = totalA * totalB * ( totalC - 2 ) ;
                    }
                    else if ( b == c || a == c ){
                        total = totalA * totalB * ( totalC - 1 ) ;
                    }
                    else{
                        total = totalA * totalB * totalC;
                    }
                    if ( total > 0 ){
                        count += total;
                    }

                }
            }
        }
        count/=6;
        int ans = (int) (count % 1000000007);
            
        return ans;
    }
}

242. Valid Anagram
Posted Updated LeetCode / Easya minute read (About 163 words)

242. Valid Anagram

Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Solution

两数组相等时，直接遍历两个数组并记录各个字符出现的数量。
一个数组遍历时用做加法，另一个做减法。
如果最后每个字符出现的数量均为0，则返回真。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length()!=t.length()){
            return false;
        }
        int[] dic = new int[26];
        for (int i = 0; i < s.length(); i++){
            dic[s.charAt(i)-'a']++;
            dic[t.charAt(i)-'a']--;
        }
        
        for(int num : dic){
            if ( num != 0 ){
                return false;
            }
        }
        return true;
    }
}
387. First Unique Character in a String
Posted Updated LeetCode / Easy2 minutes read (About 240 words)

387. First Unique Character in a String

Problems

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Solution

遍历，数组统计记录出现次数。
如果数组未记录过，则将其index添加进列表中保存。

遍历列表，如果数组统计结果为1，则返回对应的index。
否则返回-1。

Code 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int firstUniqChar(String s) {
        List<Integer> arr = new ArrayList<>();
        int[] bin = new int[26];
        
        for(int i = 0; i < s.length(); i++){
            if(bin[s.charAt(i) - 'a'] == 0) arr.add(i);
            bin[s.charAt(i) - 'a']++;
        }
        
        for(int i = 0; i < arr.size(); i++){
            if(bin[s.charAt(arr.get(i)) - 'a'] == 1) return arr.get(i);  
        }
        
        return -1;
    }
}

Solution

遍历，建立哈希表，记录出现次数。
再次遍历，如果出现次数为1，则返回下标。

Code 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int firstUniqChar(String s) {
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();
        for ( int i = 0; i < s.length(); i++ ){
            char curChar = s.charAt(i);
            if ( !map.containsKey(curChar) ){
                map.put(curChar, 1);
            }
            else{
                map.put(curChar, map.get(curChar)+1);
            }
        }
        
        for ( int i = 0; i < s.length(); i++ ){
            char curChar = s.charAt(i);
            if ( map.get(curChar) == 1 ){
                return i;
            }
        }
        return -1;
    }
}
Posted Updated LeetCode / Easy / 复习a few seconds read (About 86 words)

118. Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal’s triangle.

动态规划，直接按照杨辉三角形的定义计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> generate(int numRows) {
        ArrayList<List<Integer>> ans = new ArrayList<List<Integer>>(numRows);

        for (int i = 0; i < numRows ; i++){
            List<Integer> arr = new ArrayList<Integer>(i+1);
  
            for (int j = 0; j <= i; j++){
                if ( j == 0 || j == i ){
                    arr.add(1);
                }
                else{
                    arr.add(ans.get(i-1).get(j-1)+ans.get(i-1).get(j));
                }
            }
            ans.add(arr);
        }
        return ans;
    }
}

Posted Updated LeetCode / Medium / 复习2 minutes read (About 346 words)

11. Container With Most Water

问题
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.

双指针在首尾，二者容量取决于两者中较小的一个。
贪心算法，保留两个指针上较大的元素，移动较小一边的指针。
由于指针移动时距离只会减小，因此当新的元素比上一个更大时才有可能比之前的容量更大。
遍历一次找到最大容量。
时间复杂度：O(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
class Solution {
    public int maxArea(int[] height) {
        int best = 0;
        
        int i = 0;
        int j = height.length - 1;
        
        while ( i < j ){
            int product = 0;
            if (height[i] < height[j]){
                product = height[i] * ( j -i );
                i++;
            }
            else{
                product = height[j] * ( j -i );
                j--;
            }
            if ( product > best){
                best = product;
            }
        }
        return best;
    }
}

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 / Mediuma minute read (About 186 words)

167. Two Sum II - Input Array Is Sorted

问题描述
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

由于是有序数列，因此可以采用双指针。
左右两侧和不等于目标时，根据大小结果移动左右指针。

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 int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
        int[] ans = new int[2];
        
        while( i < j ){
            int diff = target - numbers[j];
            if ( diff == numbers[i]){
                ans[0] = i+1;
                ans[1] = j+1;
                return ans;
            }
            else if ( diff < numbers[i] ) {
                j--;
            }
            else{
                i++;
            }
        }
        return ans;
    }
}

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 / Medium / 复习3 minutes read (About 388 words)

31. Next Permutation

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

从数组末尾开始遍历第i个元素。
如果后一项小于前一项，则排序关系正确。
反之则将i与遍历过的部分中比i大的第一个数字交换。
然后对已遍历的部分排序。

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
class Solution {
    public void nextPermutation(int[] nums) {
        int flag = 0;   //标记，如果没有下一个排列时，排序数组。
        if (nums.length != 1){
            int i = nums.length -2;
            while (i >= 0){
                if (nums[i + 1] <= nums[i]) {   //从尾部开始，比较元素是否是大到小
                    i--;
                    continue;
                }
                else {  //排序关系不正确时
                    for (int j = nums.length-1;j>i;j--){
                        if (nums[j] <= nums[i]){
                            continue;
                        }
                        int temp = nums[j]; //将i元素和遍历过的元素中第一个比nums[i]大的交换。
                        nums[j] = nums[i];
                        nums[i] = temp;
                        Arrays.sort(nums,i+1,nums.length);  //排序i之后的数组。
                        flag = 1;
                        break;
                    }
                    break;
                }
            }
            if (flag == 0 ){    //如果全部从大到小，则排序整个数组。
                Arrays.sort(nums);
            }  
        }
    }
}

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);
    }
}

Follow

Recents

Archives

Links

×