LeetCode 121 448
121. Best Time to Buy and Sell Stock （参考讨论区）
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
要使收益最大化，前后差值即为前后的收益，对收益进行累加，当累加和出现负值时重置为 0 然后继续累加，用 maxi 保存累加过程中的最大值。
1class Solution {
2 public int maxProfit(int[] prices) {
3 int cur = 0, maxi = 0;
4 for (int i=1; i<prices.length; i++) {
5 cur += prices[i] - prices[i-1];
6 if (cur < 0) cur = 0;
7 maxi = cur > maxi ? cur : maxi;
8 }
9 return maxi;
10 }
11}
448. Find All Numbers Disappeared in an Array
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
第一种方法，也是我最快想到的方法。设置一个数组 base 作为散列表，用作构建给定数组 nums 的值到索引的映射，如果 nums 有一个元素为 16，则 base 的第 16 个位置就置为 1，否则为 0 。按照这个思路遍历数组 nums，那么接下来检查数组 base 中哪些位置为 0 就可以了，为 0 的位置说明 nums 中没有出现值为这个位置的数，这些位置的索引就是结果。但很显然，这种做法是不满足题意的
1//Runtime: 4 ms
2//Memory Usage: 47.7 MB
3class Solution {
4 public List<Integer> findDisappearedNumbers(int[] nums) {
5 int [] base = new int [nums.length+1];
6 for (int num : nums) {
7 base[num] = 1;
8 }
9
10 ArrayList<Integer> result = new ArrayList<Integer>();
11 for (int i=1; i<base.length; i++) {
12 if (base[i] == 0) result.add(i);
13 }
14 // System.out.println()
15 return result;
16 }
17}
这是我想到的第二种方法，先对给定数组 nums 进行排序，那么 [7, 2, 3, 1, 5, 2, 4] 就会变成 [1, 2, 2, 3, 4, 5, 7]。接下来检查从 1 到 7 有哪些值没有出现，1 出现了检查 2， 2 出现了检查 3， 由此类推直到 6，6没有出现所以把 6 存入 result 列表，7 出现了，结束。如果 n 为 9，但遍历完数组只检查到 7 的话，就说明 8，9 都没有出现，将他们加入到 result 列表中。
1//Runtime: 23 ms
2//Memory Usage: 48.1 MB
3
4class Solution {
5 public List<Integer> findDisappearedNumbers(int[] nums) {
6 Arrays.sort(nums); // 排序
7 int cur = 1;
8 ArrayList<Integer> result = new ArrayList<>(); // 保存未出现的数
9 for (int i=0; i<nums.length; i++) {
10 if (nums[i] == cur) {
11 cur += 1;
12 } else if (nums[i] > cur) {
13 while (nums[i] > cur) {
14 result.add(cur);
15 cur += 1;
16 }
17 cur += 1;
18 }
19 }
20 while (nums.length >= cur) {
21 result.add(cur);
22 cur += 1;
23 }
24 // System.out.println(Arrays.toString(nums));
25 return result;
26 }
27}
这是第三种方法，参考的讨论区，思路是：每次都将数组中的值对应的那个位置的值变成对应的负值。
比如给定数组 [7, 2, 3, 1, 5, 2, 4] ，第一个数是 7，那么就把第 7 个位置也就是索引为 6 的位置的值取反，nums 变成： [7, 2, 3, 1, 5, 2, -4]
第二个数是 2，那么把第二个位置也就是索引为 1 的位置的值取反，nums 变成 [7, -2, 3, 1, 5, 2, -4]
注意，索引不能是负数，索引取值的绝对值作为索引；因为存在重复出现的数，两次取反的话就回到正值了，索引取反是在绝对值的基础上取反，保证出现的值对应的位置都是负值。
1//Runtime: 6 ms
2//Memory Usage: 47.6 MB
3class Solution {
4 public List<Integer> findDisappearedNumbers(int[] nums) {
5 for (int i=0; i<nums.length; i++) { // 出现过的数对应的位置都设置为负值
6 int idx = Math.abs(nums[i])-1;
7 nums[idx] = -Math.abs(nums[idx]);
8 }
9
10 ArrayList<Integer> result = new ArrayList<>();
11 for (int i=0; i<nums.length; i++) { // 检查仍然为正数的位置作为结果输出
12 if (nums[i] > 0) {
13 result.add(i+1);
14 }
15 }
16 return result;
17 }
18}