aquawj

// O(mn) time, O(m+n) space
public class Solution {
    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null) return "0";
        int m = num1.length(), n = num2.length();
        int[] digits = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {//calculate product from lower digits
            for (int j = n - 1; j >= 0; j--) {
                int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j, p2 = i + j + 1;//calculate the indices where the digits will be

aquawj

121.只能卖一次
//遍历数组，找min和max profit
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int profit = 0;   //max profit from 0(starting boundary) to i day if at most buy&sell once
                         //it also means the latest day we can sell it's day i
        int min = prices[0];            //the lowest buy price from 0 to i day

aquawj

1. PQ 
// minHeap: O(nlogk) time and O(k) space
public class Solution {
    public int kthLargestElement(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return -1;
        }
       PriorityQueue<Integer> pq = new PriorityQueue<>(k);  //PQ初始化要定义容量k        
       for(int num: nums){    //记住以下模板：先add，一旦size>k了，就开始poll(),把那些小的都poll出去了
          pq.add(num);

aquawj

求交集，结果中不重复
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2]
Note:
Each element in the result must be unique.
The result can be in any order.
//hashset存第一个数组的所有元素，然后检查第二数组。一样的，set中remove，加入arraylist。最后从arraylist腾到int[]  
public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set=new HashSet<>();
        ArrayList<Integer> arr=new ArrayList<>();

aquawj

题目：非负正数，交换其中两位一次，使其变成最大的数
Input: 2736
Output: 7236
  
Input: 9973
Output: 9973

    k:  0,1,2,3,4,5,6,7,8,9
digits:[2,7,5,6]
buckets:    0     2 3 1

aquawj

//hashmap, O(n) time and space
public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        if (nums == null) {
            return 0;
        }
        HashMap<Integer, Integer> map = new HashMap<>(); //map存sum和下标
        map.put(0, -1);              
        int max = 0;      
        int sum = 0;

aquawj

class Solution {
    public int subarraySum(int[] nums, int k){
        if( nums == null || nums.length ==0){
            return 0;
        }
        int sum = 0, count = 0;
        HashMap<Integer,Integer> map = new HashMap<>(); //map存presum和其出现的次数<presum, frequency of presum>
        map.put(0, 1);
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];

aquawj

限制条件，
比如说一位数时不能为0，两位数不能大于26，其十位上的数也不能为0，当然需要用动态规划Dynamci Programming来解
注意： 问输入是否全为数字，若否则还需检测其他非法字符
Test:
"" // empty string
"0" // invalid encoding number
"&*^.abc" // invalid input char
"201" -> 1 // 0 can only be at the units of a two-digit number
"12" -> 2

aquawj

1, one pass partition
public class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        int i = 0;
        int left = 0;
        int right = nums.length - 1;
        while (i <= right) {//should be i <= right, not i < nums.length !!!eg.[2, 2]; not i < right !!!eg.[1,0];

aquawj

/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); */
## Idea 
* Based on 159
* Because of call multiple times, there are more corner cases
* First time we call, we need to save extra characters for next call
*  In the while loop, if buffPointer reaches current buffCount, it will be set as zero to be ready to read new data.
public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer