386. Lexicographical Numbers
The basic idea is to find the next number to add.
Take 45 for example: if the current number is 45, the next one will be 450 (450 == 45 * 10)(if 450 <= n), or 46 (46 == 45 + 1) (if 46 <= n) or 5 (5 == 45 / 10 + 1)(5 is less than 45 so it is for sure less than n).We should also consider n = 600, and the current number = 499, the next number is 5 because there are all "9"s after "4" in "499" so we should divide 499 by 10 until the last digit is not "9".It is like a tree, and we are easy to get a sibling, a left most child and the parent of any node.
class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> ans = new ArrayList<>();
int cur = 1;
for (int i = 1; i <= n; i++){
ans.add(cur);
if (cur * 10 <= n){
cur = cur * 10;
}
else if (cur % 10 != 9 && cur + 1 <= n){
cur++;
}
else{
while ( (cur / 10) % 10 == 9){
cur /= 10;
}
cur = cur / 10 + 1;
}
}
return ans;
}
}
739.Daily Temperatures
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] next = new int[101];
Arrays.fill(next, Integer.MAX_VALUE);
int n = temperatures.length;
int[] ans = new int[n];
for (int i = n - 1; i >= 0; i--){
int cur = temperatures[i];
next[cur] = Math.min(next[cur], i);
int min_diff = Integer.MAX_VALUE;
for (int j = cur + 1; j <= 100; j++){
if (next[j] != Integer.MAX_VALUE){
min_diff = Math.min(min_diff, next[j] - i);
}
}
ans[i] = min_diff == Integer.MAX_VALUE ? 0 : min_diff;
}
return ans;
}
}
689 Maximum Sum of 3 Non-Overlapping Subarrays
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int[] sums = new int[nums.length - k + 1];
int sum = 0;
for (int i = 0; i < nums.length; i++){
sum += nums[i];
if (i >= k) sum -= nums[i - k];
if (i >= k - 1) sums[i - k + 1] = sum;
}
System.out.println("sums: " + Arrays.toString(sums));
int[] left = new int[sums.length];
int best = 0;
for (int i = 0; i < sums.length; i++){
if (sums[i] > sums[best]){
best = i;
}
left[i] = best;
}
System.out.println("left: " + Arrays.toString(left));
int[] right = new int[sums.length];
best = sums.length - 1;
for (int i = sums.length - 1; i >= 0; i--){
if (sums[i] >= sums[best]) best = i;
right[i] = best;
}
System.out.println("right: " + Arrays.toString(right));
int[] ans = {-1, -1, -1};
for (int b = k; b < sums.length - k; b++){
int a = left[b - k], c = right[b + k];
if (ans[0] == -1 || sums[a] + sums[b] + sums[c] > sums[ans[0]] + sums[ans[1]] + sums[ans[2]]){
ans[0] = a;
ans[1] = b;
ans[2] = c;
}
}
return ans;
}
}
565. Array Nesting
class Solution {
public int arrayNesting(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; i++){
if (nums[i] != Integer.MAX_VALUE){
int start = nums[i], count = 0;
while (start != Integer.MAX_VALUE){
int temp = start;
start = nums[start];
count++;
nums[temp] = Integer.MAX_VALUE;
}
ans = Math.max(ans, count - 1);
}
}
return ans;
}
}
467 Unique Substrings in Wraparound String
public class Solution {
public int findSubstringInWraproundString(String p) {
// count[i] is the maximum unique substring end with ith letter.
// 0 - 'a', 1 - 'b', ..., 25 - 'z'.
int[] count = new int[26];
// store longest contiguous substring ends at current position.
int maxLengthCur = 0;
for (int i = 0; i < p.length(); i++) {
if (i > 0 && (p.charAt(i) - p.charAt(i - 1) == 1 || (p.charAt(i - 1) - p.charAt(i) == 25))) {
maxLengthCur++;
}
else {
maxLengthCur = 1;
}
int index = p.charAt(i) - 'a';
count[index] = Math.max(count[index], maxLengthCur);
}
// Sum to get result
int sum = 0;
for (int i = 0; i < 26; i++) {
sum += count[i];
}
return sum;
}
}
135 Candy
two array
class Solution {
public int candy(int[] ratings) {
if (ratings == null || ratings.length == 0) return 0;
int n = ratings.length;
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(left, 1);
Arrays.fill(right, 1);
for (int i = 1; i < n; i++){
if (ratings[i] > ratings[i - 1]){
left[i] = left[i - 1] + 1;
}
}
for (int i = n - 2; i >= 0; i--){
if (ratings[i] > ratings[i + 1]){
right[i] = right[i + 1] + 1;
}
}
int ans = 0;
for (int i = 0; i < n; i++){
ans += Math.max(left[i], right[i]);
}
return ans;
}
}
one array
class Solution {
public int candy(int[] ratings) {
if (ratings == null || ratings.length == 0) return 0;
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
for (int i = 1; i < n; i++){
if (ratings[i] > ratings[i - 1]){
candies[i] = candies[i - 1] + 1;
}
}
int ans = candies[n - 1];
for (int i = n - 2; i >= 0; i--){
if (ratings[i] > ratings[i + 1]){
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
ans += candies[i];
}
return ans;
}
}
667 Beautiful Arrangement II
class Solution {
public int[] constructArray(int n, int k) {
int left = 1, right = n;
int[] ans = new int[n];
for (int i = 0; i < n; i++){
ans[i] = k % 2 == 1 ? left++ : right--;
if (k > 1){
k--;
}
}
return ans;
}
}
419 Battleships in a Board
class Solution {
public int countBattleships(char[][] board) {
if (board == null || board.length == 0) return 0;
int count = 0;
for (int i = 0; i < board.length; i++){
for (int j = 0; j < board[0].length; j++){
if (board[i][j] == '.') continue;
if (i > 0 && board[i - 1][j] == 'X') continue;
if (j > 0 && board[i][j - 1] == 'X') continue;
count++;
}
}
return count;
}
}