52Heartz's Blog

分享科技与生活

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/best-time-to-buy-and-sell-stock

题目难度：Easy

题目

You are given an array prices where prices[i] is the price of a given stock on the $i^{th}$ 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.

Example 1:

1
2
3
4
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

1
2
3
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

解答1[Java]：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice)
                minprice = prices[i];
            else if (prices[i] - minprice > maxprofit)
                maxprofit = prices[i] - minprice;
        }
        return maxprofit;
    }
}

思路

使用两个变量，一个存储截至目前最小的值，一个存储截至目前最大的利润。然后对股票价格依次遍历，每遍历到一个元素都更新当前最小值和当前最大利润，等到遍历结束时，取最大利润值即可。

相同题目

LCR 188. 买卖芯片的最佳时机 - 力扣（LeetCode）

剑指 Offer 63：剑指 Offer 63. 股票的最大利润 | 算法通关手册（LeetCode）

关联题目

Best Time to Buy and Sell Stock II - LeetCode

参考资料

  1. 剑指 Offer 63. 股票的最大利润 | 算法通关手册（LeetCode）

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/climbing-stairs

题目难度：Easy

题目

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

1
2
3
4
5
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

1
2
3
4
5
6
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

思路

如果 n == 0，那么方式为 0 种。

如果 n == 1，那么方式为 1 种。

如果 n == 2，那么方式为 2 种，一种是走两次 1 步，使用序列表示就是 [1, 1]，还有一种就是直接走 2 步，使用序列表示就是 [2]。

如果 n == 3，那么有 3 种，[1, 1, 1]、[1, 2]、[2, 1]。

实际上就是要求，找到所有和为 n 的序列，且序列中只能出现 1 和 2。只要两个序列不相同，那么就可以看作是两种不同的方式。

对于 n > 2 的情况，我们可以把问题分为，走到 n-1 和 走到 n-2 时分别有多少种方式？即，序列的最后一步我们已经确定了，[?, 1] 和 [?, 2]，我们把走到 n-1 和走到 n-2 的方式数加起来，就是走到 n 的总方式。

解答1[Java]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

思路

动态规划。

解答2[Java]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return third;
    }
}

思路

斐波那契数。

比上一个算法优化的地方在于空间复杂度由 $O(n)$ 变为 $O(1)$。

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/search-a-2d-matrix-ii

题目难度：Medium

解答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 searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0){
            return false;
        }

        int row = 0;
        int column = matrix[0].length-1;

        while(row<matrix.length&& column>=0){
            if(target == matrix[row][column]){
                return true;
            }
            else if(target > matrix[row][column]){
                row++;
            }
            else{
                column--;
            }
        }

        return false;
    }
}

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/majority-element

题目难度：Easy

解答1[Java]（Boyer-Moore Voting Algorithm）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

分析

这个算法叫做摩尔投票法（Boyer-Moore Voting Algorithm）。

选定一个数，遇到相同的就加1，不同就减1，count 变成 0 就换下一个数，因为众数占总体的一半以上，所以众数总能脱颖而出。

时空复杂度

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

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

解答2[Java]

1
2
3
4
5
6
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

分析

因为众数的数量大于 $\lfloor n/2 \rfloor$，则众数的数量最小为 $\lfloor n/2 \rfloor + 1$。

如果我们对数组进行排序，有三种情况：

① 假设众数比所有数都小，则众数将占据排序后数组的左半部分。

② 如果众数比所有数都大，则众数将占据排序后数组的右半部分。

③ 如果数组不是最大的也不是最小的，众数将占据排序后数组的中间部分。

不管哪一种情况，排序后的数组中的第 $\lfloor n/2 \rfloor + 1$ 个位置上的数一定是众数。

时空复杂度

时间复杂度：$O(nlogn)$，本算法的主要开销在排序上，因此时间复杂度就是快速排序的时间复杂度。

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

参考资料

  1. Majority Element - LeetCode Articles
  2. MisterBooo/LeetCodeAnimation 169. Majority Element

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/single-number/

题目难度：Easy

解答1[Java]：

1
2
3
4
5
class Solution {
    public int singleNumber(int[] nums) {
        
    }
}

思路

  • If we take XOR of zero and some bit, it will return that bit
    • $a \oplus 0 = a$
  • If we take XOR of two same bits, it will return 0
    • $a \oplus a = 0$
  • $a \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = b$

So we can XOR all bits together to find the unique number.

本题拓展

有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。

示例 :

输入: [1,2,2,1,3,4]
输出: [3,4]

题目再解析

根据前面找一个不同数的思路算法，在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果。

然后，因为这两个只出现一次的元素一定是不相同的，所以这两个元素的二进制形式肯定至少有某一位是不同的，即一个为 0 ，另一个为 1 ，现在需要找到这一位。

根据异或的性质 任何一个数字异或它自己都等于 0，得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位。

再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。

  • 将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个
  • 将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。

这样就解出题目。忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为O(n)。

来源：有哪些解决完之后让你拍案叫绝的算法问题？

核心思想

两个数不一样，肯定至少有一个二进制位是不一样的。我们就从不一样的二进制位中选择一个。设这两个数为A 和 B。

现在假设我们已经选择了某一个二进制位，假设我们选择的是从右向左数第2位，简称第2位。

因为除了这两个数之外其他的数都是成对出现的，所以其他的数中，第2位是0的数是成对出现的，第2位是1的数也是成对出现的。

而A和B的第2位，只有两种可能：

（1）A的第2位是1，B的第2位是0；

（2）A的第2位是0，B的第2位是1。

所以，如果我们把第2位为0的所有数都相互之间做异或运算，必然能够找出A和B中的一个数字，因为其他的数都是成对出现的，异或之后所有位都0了。

再把第2位为1的所有数都相互之间做异或运算，必然能够找出A和B中的另外一个数字。

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/4sum/

题目难度：Medium

解答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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public List<List<Integer>> fourSum(int[] num, int target) {
        ArrayList<List<Integer>> ans = new ArrayList<>();
        if (num.length < 4)
            return ans;
        Arrays.sort(num);
        for (int i = 0; i < num.length - 3; i++) {
            if (num[i] + num[i + 1] + num[i + 2] + num[i + 3] > target)
                break; // first candidate too large, search finished
            if (num[i] + num[num.length - 1] + num[num.length - 2] + num[num.length - 3] < target)
                continue; // first candidate too small
            if (i > 0 && num[i] == num[i - 1])
                continue; // prevents duplicate result in ans list
                          // already sorted, only need to check the adjacent element

            for (int j = i + 1; j < num.length - 2; j++) {
                if (num[i] + num[j] + num[j + 1] + num[j + 2] > target)
                    break; // second candidate too large
                if (num[i] + num[j] + num[num.length - 1] + num[num.length - 2] < target)
                    continue; // second candidate too small
                if (j > i + 1 && num[j] == num[j - 1])
                    continue; // prevents duplicate results in ans list
                int low = j + 1, high = num.length - 1;
                while (low < high) {
                    int sum = num[i] + num[j] + num[low] + num[high];
                    if (sum == target) {
                        ans.add(Arrays.asList(num[i], num[j], num[low], num[high]));
                        while (low < high && num[low] == num[low + 1])
                            low++; // skipping over duplicate on low
                        while (low < high && num[high] == num[high - 1])
                            high--; // skipping over duplicate on high
                        low++;
                        high--;
                    }
                    // move window
                    else if (sum < target)
                        low++;
                    else
                        high--;
                }
            }
        }
        return ans;
    }
}

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/3sum/

题目难度：Medium

解答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
class Solution {
    public List<List<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> res = new LinkedList<>();
        for (int i = 0; i < num.length - 2; i++) {
            if (i == 0 || (i > 0 && num[i] != num[i - 1])) {
                int lo = i + 1, hi = num.length - 1, sum = 0 - num[i];
                while (lo < hi) {
                    if (num[lo] + num[hi] == sum) {
                        res.add(Arrays.asList(num[i], num[lo], num[hi]));
                        while (lo < hi && num[lo] == num[lo + 1])
                            lo++;
                        while (lo < hi && num[hi] == num[hi - 1])
                            hi--;
                        lo++;
                        hi--;
                    } else if (num[lo] + num[hi] < sum)
                        lo++;
                    else
                        hi--;
                }
            }
        }
        return res;
    }
}

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/sort-characters-by-frequency

题目难度：Medium

解答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
class Solution {
    public String frequencySort(String s) {
        int[] map = new int[128];
        for (char c : s.toCharArray()) {
            map[c]++;
        }
        char[] res = new char[s.length()];
        int pos = 0;
        while (pos < s.length()) {
            char max = 0;
            for (char c = 0; c < map.length; c++) {
                if (map[c] > map[max])
                    max = c;
            }
            int repeat = map[max];
            for (int i = 0; i < repeat; i++) {
                res[pos++] = max;
                map[max]--;
            }
        }
        return new String(res);
    }
}

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/two-sum/

题目难度：Easy

题目

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[Java]：暴力枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

注意内层的 for 循环，其中的初始条件是 int j = i + 1。根据本题的条件，因为一个数最多只能匹配上一次，所以 i 前边的数据都已经遍历过了，所以可以跳过。

复杂度分析

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

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

解答1[Java]：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.HashMap;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap();

        for (int i = 0; i < nums.length; i++) {
            // 边遍历边判断，而不是先构建哈希表再判断，这种效率更高
            if (map.get(target - nums[i]) != null) {
                return new int[] { map.get(target - nums[i]), i };
            } else {
                map.put(nums[i], i);
            }
        }

        throw new IllegalArgumentException("No two sum solution");
    }
}

因为题目中说了本体有且只有一个答案，那么说明数组中的满足条件的元素一定是不重复的，不然无法保证答案唯一。既然满足条件的元素是唯一的，那么就可以使用哈希表来解决了。哈希表的键为元素的值，哈希表的值为元素的索引。

扩展：即使满足条件的元素不唯一，还是可以使用哈希表，哈希表中的值使用一个列表，保存多个索引即可。

复杂度分析

时间复杂度：$O(n)$，最坏情况下，要把整个数组遍历一遍。

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

发表于 更新于 分类于 ，

题目来源：https://leetcode.com/problems/isomorphic-strings

题目难度：Easy

解答1[Java]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] m1 = new int[256]; 
        int[] m2 = new int[256];
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (m1[s.charAt(i)] != m2[t.charAt(i)]) return false;
            m1[s.charAt(i)] = i + 1;
            m2[t.charAt(i)] = i + 1;
        }
        return true;

    }
}

思路

不直接建立字母之间的映射关系，而是把要建立映射关系的字母同时映射到另外一个数字。相当于建立了一个间接映射关系。

解答1小优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] m1 = new int[256];
        int[] m2 = new int[256];
        char[] sCharArray = s.toCharArray();
        char[] tCharArray = t.toCharArray();

        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (m1[sCharArray[i]] != m2[tCharArray[i]]) return false;
            m1[sCharArray[i]] = i + 1;
            m2[tCharArray[i]] = i + 1;
        }
        return true;

    }
}

反复调用 String 类的 charAt() 方法是比较慢的，优化之后运行总时间由 4ms 减为2ms。可能是函数调用也要占用一部分空间。而直接使用数组，除了数组的空间不需要额外的空间。

空间占用，两次调用，数值差距很大，不知道为什么。

解答2[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
class Solution {
    public boolean isIsomorphic(String s, String t) {
        char[] sString = s.toCharArray();
        char[] tString = t.toCharArray();

        int length = s.length();
        if (length != t.length())
            return false;

        char[] sMap = new char[256];
        char[] tMap = new char[256];

        for (int i = 0; i < length; i++) {
            char sChar = sString[i];
            char tChar = tString[i];

            if (sMap[sChar] == 0 && tMap[tChar] == 0) {
                sMap[sChar] = tChar;
                tMap[tChar] = sChar;
            } else if (sMap[sChar] != tChar || tMap[tChar] != sChar)
                return false;

        }
        return true;
    }
}

思路

这个算法是通过两个数组，两个数组对应两种映射关系。但是都是字符映射到字符的。

这个算法比上边使用 int 数组的算法要快。上边的算法优化之后是 2ms，但是这个算法是 1ms。

难道是因为使用 char 数组比使用 int 数组效率更高？

0%