121.买卖股票的最佳时机

✒解题思路：

  1. 暴力法
  2. 官方解法，设置一个min存储历史最小值，max存储最大值，遍历数组，当遇见更小值时更新min，当prices[i]-min>max时更新max
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProfit(int[] prices) {
		if (prices.length < 1) {
			return 0;
		}
		int max = 0;
		int min = prices[0];
		for (int i = 1; i < prices.length; i++) {
			if (min > prices[i]) {
				min = prices[i];
			} else if (prices[i] - min > max){
				max = prices[i] - min;
			}
		}
		return max;
    }
}

944.删列造序（统计有多少降序的）

✒解题思路：

  1. 遍历每一列，只要上一行大于下一行，表示降序，删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int minDeletionSize(String[] A) {
		int D = 0;
		for (int i = 0; i < A[0].length(); i++) {
			for (int j = 0; j < A.length - 1; j++) {
				if (A[j].charAt(i) > A[j + 1].charAt(i)) {
					D++;
					break;
				}
			}
		}
		return D;
    }
}

1071.字符串的最大公因子

✒解题思路（大佬）：

  1. 当str1 + str2 = str2 + str1时表示存在公因子，否则不存在
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
	public String gcdOfStrings(String str1, String str2) {
		if (!(str1 + str2).equals(str2 + str1)) {
			return "";
		}
		return str1.substring(0, gcd(str1.length(), str2.length()));
	}

	public int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}
}

53.最大子序和（Kadane’s Algorithm）

✒解题思路：

  1. （同42）从头开始遍历数组，用sum保存部分和，max存储最大和，当sum小于nums[i]的值，舍弃sum，令sum=nums[i]，从当前开始遍历，比较max与sum的大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
	public int maxSubArray(int[] nums) {
		int sum = nums[0];
		int max = nums[0];
		for (int i = 1; i < nums.length; i++) {
			if (sum + nums[i] < nums[i]) {
				sum = nums[i];
			} else {
				sum += nums[i];
			}
			if (max < sum) {
				max = sum;
			}
		}
		return max;
	}
}