Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

 

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".
Example 2:

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".
Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

 public boolean backspaceCompare(String s, String t) {
       return getString(s).equals(getString(t));
    }
    
    private String getString(String str) {
        int n = str.length(), count = 0;
        StringBuilder sb = new StringBuilder();
        
        for (char ch : str.toCharArray()) {
            
            if (ch != '#'){
                sb.append(ch);
            } else if(sb.length() != 0) {
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        return sb.toString();
    }

 public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;
        


        while (i >= 0 || j >= 0){
            int i1 = getNextValidindex(s, i); // i = 2(c), i1 = 2
            int j1 = getNextValidindex(t, j);// j = 0(b), j1 = 0
        //  String s= "ab##";
        //  String t = "c#d#";           
            if (i1 < 0 && j1 < 0) {
                return true;
            }
            
             if (i1 < 0 || j1 < 0) {
                return false;
            }
             if (s.charAt(i1) != t.charAt(j1) ) { // c 和 b对比，
                return false;
            }
            
            i = i1 - 1;
            j= j1 - 1;
        }
        
        return true;
        
    }
    
    private int getNextValidindex(String str, int index) {
        int backSpaceCount = 0;
        
        while (index >= 0) {
            if (str.charAt(index) == '#') {
               backSpaceCount++;
            } else if (backSpaceCount > 0) {
                backSpaceCount--;
                // 有#后的字母，
            } else  {
                break;
            }
            index--;
        }
        return index;
    }

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.


Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

class Solution {
    public int[] sortedSquares(int[] nums) {
        int i = 0, j= nums.length - 1;
        int[] res = new int[nums.length];
        int index = nums.length - 1;
        while (index >= 0) {
            if(nums[i]* nums[i] <= nums[j] * nums[j]) {
                res[index--] = nums[j] * nums[j];
                j--;
            }else {
                res[index--] = nums[i] * nums[i];
                i++;
            }
        }
        return res;
    }
}

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.
A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

 public int subarraysWithKDistinct(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }
    
    int atMost(int[] nums, int k) {
        int i = 0, res = 0;
        Map<Integer, Integer> count = new HashMap<>();
        
        for (int j = 0; j < nums.length; j++) {
            if (count.getOrDefault(nums[j], 0) == 0) {
                k--;
            }
            count.put(nums[j], count.getOrDefault(nums[j], 0) + 1);
            while (k < 0) {
                count.put(nums[i], count.get(nums[i]) - 1);
            
            if (count.get(nums[i]) == 0) {
                k++;
            }
            i++;
             
        }
            res += j - i + 1;
        }
       return res;
    }

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

 

Example 1:

Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
Example 2:

Input: nums = [1,2,3], k = 0
Output: 0

 public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k == 0) {
            return 0;
        }
        int slow = 0, fast = 0;
        int res = 0;
        int sum = 1;
        while (fast < nums.length) {
            sum *= nums[fast];
            while (slow <= fast && sum >= k){
                sum /=nums[slow++];
            }
            
            res += fast - slow + 1;
            fast++;
        }
        return res;
    }

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

 

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

    public void sortColors(int[] nums) {
        int i = 0, j = nums.length - 1;
        int zeroIndex = 0;
        while (i <= j) {
            if (nums[i] == 0) {
                 swap(i++, zeroIndex++, nums);
            } else if (nums[i] == 2) {
                 swap(i, j--, nums);
            } else {
                i++;
            }
            
        }
    }
        
        private void swap(int i, int j, int[] nums) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9
 

 public int trap(int[] height) {
    
       
        int sum = 0;
        
        for (int i = 0; i < height.length; i++) {
            if (i == 0 || i == height.length - 1) {
                continue;
            }
            int maxLeft = height[i];
            int maxRight = height[i];
            
            for (int r = i + 1; r < height.length; r++) {
                if (height[r] > maxRight) {
                    maxRight = height[r];
                }
            }
            
             for (int l = i - 1; l >= 0; l--) {
                 if (height[l] > maxLeft) {
                     maxLeft = height[l];
                }
            }
            
            int h = Math.min(maxLeft, maxRight) - height[i];
            if (h > 0) {
                sum += h;
            }
        }
        return sum;
        
    }

int length = height.length;
if (length <= 2) {
    return 0;
}
int[] maxLeft = new int[length];
int[] maxRight = new int[length];

// 记录每个柱子左边的最高高度的柱子
maxLeft[0] = height[0];
for (int i = 1; i < length; i++) {
    maxLeft[i] = Math.max(heihgt[i], maxLeft[i - 1]);
}
// 记录每个柱子右边的最高高度的柱子
maxRight[length - 1] = height[length - 1];
for (int i = length - 2; i >= 0; i--) {
    maxRight[i] = Math.max(heihgt[i], maxRight[i + 1]);
}
//求和
int sum = 0;
for (int i = 0; i < length; i++) {
    int count = Math.min(maxLeft[i], maxRight[i]) - heigth[i];
    if (count > 0) {
        sum += count;
    }
}
return sum;
}
}

public int trap(int[] height) {
if (length <= 2) {
    return 0;
}

// 作为右墙入栈，出现入栈元素（右边）比栈顶大，说明左边形成了低洼处，低洼处出栈并计算雨水量

int sum = 0;
Deque<Integer> stack = new ArrayDeque<>();
for (int right = 0; right < height.length; right++) {
    // 栈不为空，出现入栈元素（右边）比栈顶大，说明左边形成了低洼处
    while (!stack.isEmpty() && height[right] > stack.peek()) {

    }
}

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].