aquawj

/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); 
  原API的含义：每次读4个字符，结果存在buf中(buf长度为4)，返回int是实际读取的字符数。正常返回4，但是剩余字符不足4时，返回的时剩余字符(如3)    
 */
## Idea
* Each time it reads 4 characters at a time from a file
* Return the actual number characters read
* Use temp buffer to store characters that every read4 generated
* Use an index to tracj the buf array current position index是buf数组的当前位置下标
* Then save temp array to buffer array

aquawj

//主函数处理异常（0， <0, 以及四位数以上（使用i来数三位的个数））
//helper辅助函数处理3位数以下（百，十，个）分情况：【0,20】【20,100】【100,999】，存在递归。先算小范围的再算大范围，这样后面的计算可以利用前面的结果
//自己写的：
class Solution {
    private final String[] LESS_THAN_20 = new String[]{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private final String[] TENS = new String[]{"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    private final String[] THOUSANDS = new String[]{"", "Thousand", "Million", "Billion"};
    public String numberToWords(int n) {
        if(n == 0) return "Zero";
        String str = "";

aquawj

预热：
//简单版本：只返回一组解即可
O(1)：用一个counter，每次遇到左括号加一；每次遇到右括号先判断counter是否为零：为零说明右括号多了，删除当前右括号，不为零说明合法，counter减一。遍历一遍以后可以看看counter是否大于零，如果是则从右数起删除多余的左括号
// 20. Valid Parentheses
// 考虑三种括号：()[]{}，必须紧跟的才算valid，比如(){}[],true; [()] 或者[(]) 都false
public class Solution {
    public boolean isValid(String s) {
        if(s.length()==0||s==null) return true;
        Stack<Character> stack=new Stack<>();
        for(Character c:s.toCharArray()){

aquawj

1,最常见两种解法 O(nlogn) time, O(n) space
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        int[] starts=new int[intervals.length];
        int[] ends=new int[intervals.length];
        for(int i=0;i<intervals.length;i++){
            starts[i]=intervals[i].start;
            ends[i]=intervals[i].end;
        }
        Arrays.sort(starts);

aquawj

1，最正常的task schedule：顺序不变，输出的是最后的时间
使用hashmap记录同一任务下次出现的位置（即冷冻多久后可以再执行）
//Input: tasks = ["A","A","A","B","B","B"], n = 2
//Output: 14
//(A--A--AB--B--B)
public class Solution {
   //if tasks cannot be reordered, output the total time needed: O(n) space
   private static int taskSchedule1(int[] tasks, int cooldown) {
       if (tasks == null || tasks.length == 0) {
           return 0;

aquawj

***********46. Permutation*******************
//1.基本解法：O(n!*n) time, O(n) stack space
//permutation的复杂度是n!级别的，中间的contains又耗费了n
//阶乘读法：factorial
class Solution {
  
  public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>(); 
    if(nums == null || nums.length == 0){
       return res;

aquawj

//情况：原数组no duplicates，每个数可以多次取
//时间：O(2^n) 2的n次方:每个数可以取可以不取，计算：cn0 + cn1 + cn2 + cn3 + ... + cnn = 2^n
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(candidates == null || candidates.length == 0){
            return res;
        }
        List<Integer> combination = new ArrayList<>();
        dfs(candidates, target, res, combination, 0);

aquawj

//1. 基本： 无重复
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return result;
        }
        List<Integer> subset = new ArrayList<>();
        dfs(nums, 0, subset, result);
        return result;

aquawj

/*给定课程数目，先修课二维数组，排出课程顺序。pre数组中，后面的元素是pre课，前面的元素是aim课
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]
4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
 */
//topological sorting O(V+E)
//BFS
//时间 O(2n^2 + 2n) ?

aquawj

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
//O(m+n) time: num of nodes + num of edges,
//O(m) space: num of nodes