LeetCode Day4
2020, Jan 30
LeetCode 38 Count and Say
https://leetcode.com/problems/count-and-say/
Firstly, I have to say the question is hard to understand.We can just use the hashmap to solve it, but I use two index while.
public String countAndSay(int n) {
String result = "11";
if (n == 1) {
return "1";
} else if (n == 2) {
return result;
}
while (n > 2) {
n--;
//转换为char数组处理字符
char[] array = result.toCharArray();
result = "";
int j = 0;
for (int i = 1; i < array.length; i++) {
//双指针判断慢指针和快指针元素不同时,计数并”读出来“
if (array[i] != array[j]) {
result += (i - j) + "" + array[i - 1];
j = i;
}
//对于末尾的元素特特殊处理
if (i == array.length - 1 && array[i] == array[j]) {
result += (i - j + 1) + "" + array[i];
}
}
}
return result;
}
I try another methor by using recursion.
public static String countAndSay(int n) {
if (n == 1) {
return "1";
}
String newString = countAndSay(n - 1);
StringBuilder builder = new StringBuilder();
char pre = newString.charAt(0);
int count = 0;
for (int i = 0; i < newString.length(); i++) {
if (newString.charAt(i) == pre) {
count++;
} else {
builder.append(count).append(pre);
pre = newString.charAt(i);
count = 1;
}
if (i == newString.length() - 1) {
builder.append(count).append(pre);
}
}
return builder.toString();
}
LeetCode 53 Maximum Subarray
https://leetcode.com/problems/maximum-subarray/
We hava lots of solutions:
public int maxSubArray(int[] nums) {
int maxSum = nums[0], currentSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
private static int maxSub(int[] origin) {
int maxSum = origin[0];
for (int i = 1; i < origin.length; i++) {
if (origin[i - 1] > 0) {
origin[i] += origin[i - 1];
}
maxSum = Math.max(maxSum, origin[i]);
}
return maxSum;
}