Leetcode

拆不散D大熊小熊

写在前面的话：
<三遍的训练方法>来做！非常非常关键，尤其对于基础弱的同学；tosth for a reason: 你为什么学?如何去学?学会如何好的学习习惯和方法!


1. 第一遍呢，对于基础弱的同学不敲键盘-。-说自己怎么不会逻辑啊各个方面，这都是借口，打开老师写的Java的solution，一个字母一个字母，键盘敲进去，人就是这样一个诚实的动物，当你真正地把，。；都拼都弄错了搞混了，你才会发现说，我第一遍真的是值了，我把语法各个API的调用给熟悉了，第一遍一定是在自己理解的复习的上课教案基础上，把老师答案一步一步的输进去。
2. 第二遍是：同学到了第二三天遗忘规律是比较快的。你迅速地在自己理解的情况下，把第二遍的代码写完；然后实在卡住了，说老师，当时QueDFS怎么写的 hash怎么运用的，你再看一遍老师写的答案；这还没完，最关键最关键在后边儿。我一直说眼勤，脑勤，还有嘴勤！这嘴勤怎么回事儿，一定大声的用英文把你自己刚刚写的code，能够一行一行地把逻辑块都解释得很清楚，分析好时间/空间复杂度。当你能够大声的说出来你的思路的时候，每个变量的物理意义的时候是吧，就是。我相信你们一定会高于内容本身，可以被给别人当老师的，你说这一遍胜似于你自己闷着头死刷题十遍以上。
3. 第三遍的是真正的让自己在五六天之后，自己复习的时候快速带过，然后呢，觉得自己不不托底的。那种敲一敲键盘是吧，迅速把这个实现，把这个功能实现。那如果有API什么又忘了是吧，打死也不用看了，自己通过Google一下，把这个填满，相信这三遍说完了之后的话，做完了之后的话，这个内容就真正的映入到你自己的血液里边儿去了，就变成你自己的东西，而不是说，老师我死刷题刷了十遍，刷11遍也学不会。原因是什么，你并没有高于这个内容本身（这就是不太好的学习习惯）




boolean b = （x % 2 == 0）一定要有（）？
boolean b = ( x == y );
                =( x - y == 0);
int a = int b =
double c = 1.0 * a / b

拆不散D大熊小熊

function 是check if a number is prime。 code 如下：

private boolean isPrime (int n) {

    for (int i =2; i*i<=n; i++) {

        if (n%i == 0) {

            return false;

        }

    }

    return true;

}

或者 public class Solution {  public boolean isPrime(int n) {
    for (int i = 2; i < n; i++) {
      if (n % i == 0) {
        return false;
      }  
    } return true;
  }
}

问题是为什么condition是 i * i <=n ?举个例子，比如我们check10的话，如果我们检查了2*5的话，还要检查5*2吗？所以到square root of n就可以了

对于一个数 n 来说，如果它不是素数，那么它一定能够被一个 <= sqrt(n)的数整除，
因为n最少可以被分解成2个数的成绩，这两个数中比较小的那个，最大的可能是 sqrt(n)

看一下for loop一共运行了多少次，应该是O(sqrt(n))错误答案：
public class Solution {
  public boolean isPrime(int n) {
    for (int i = 2; i < n; i++) {
      if (n % i == 0) {
        return false;
      } else {
        return true;
      }
    }
  }
}
老师： 如果你进不到forloop里面的话，就没有返回值了
我还是不太明白为什么要把return true放到for loop外面，不能在for loop里面用else？
use case ：√你这么写一旦n%i不为0，立刻返回true，和判断质数的原理完全不一样了。

举个最简单的例子，N = 9， 第一个i等于2，9 % 2 不为0，你这个函数直接就返回true了，然而9根本不是质数

错误原因： 逻辑上要满足n余上所有的i都不为0，才能说n是质数。然而你的写法，只要n余2不为0就直接返回true了。。。

拆不散D大熊小熊

find minimum

class soulution {

         public int min(int[] array){

                   IF （array==null || array.length==0){

                          return 0;

}

                   int m=array[0];

                   for ( int i=1; i<array.length;i++){

                         m=array<m?array:m;

}

                   return m;

}

}

规则：变量=（条件表达式）？表达式1：表达式2
解释：条件表达式为真，则表达式1的值赋值给变量；条件表达式为假，则表达式2的值赋值给变量。

加上corner case为空的判断check array是empty的情况，所以这个corner case

big O 本来的含义就是最差的时间复杂度，所以O什么的，都是最差的意思

array==null和array.length==0的区别public class Test1 {
    public static void main(String[] args) {
        int[] a1 = new int[0];
        int[] a2 = null;
        System.out.println(a1.length);//0
        System.out.println(a2.length);//NullPointerException
} }
————————————————

a1 表示给数组分配了地址，但是还没有存东西；

a2表示连地址都没有分配，就是个空的

而null是不能调用方法的，所以会报空指针异常

1. 有两个概念要清晰

   1.1.   || 的意思是 or 不是 and

   1.2    在input 是 null的时候 input.length()会出现null pointer exception

   这一行是检查corner case的两种情况，null 或者 empty

在用for-each loop 的时候，后面一定要是 array 吗？要是 array of array，for-each loop 怎么写呢？像是以后会学的其他数据类型像是 linkedList 之类的也可以用 for-each  loop 吗？

2. for - each 适用于collection, 包括 list, map, set

如果是 array of array, use following

for (int[] arr : arrays) {

    for (int I : arr) {

       do something;

    }

}

class Solution {  public int sum(int[] array) {    if (array==null || array.length==0) {      return 0;    }    int s=0;    for (int x: array){      s += x;    }    return s;  }}易错点！if (array.length == 0 || array == null)错因： 因为在你的条件里他是先判断的 array.length == 0 再判断是否为null，你把两个调换一下就好了。这里是逻辑判断的短路特性，或判断会先看第一个条件，一旦满足就不看第二个了，所以你输入null，应该先判断是不是null，不是null再判断是不是空。顺序调换之后就和你在下面写的两个判断是等价的了

拆不散D大熊小熊

public class Solution {
  public void reverse(int[] array) {
    // Write your solution here
    int i = 0;
    int j = array.length - 1;
    while(i < j){
      swap(array,i,j);
      i++;
      j--;
    }
    }

  public void swap(int[]array,int i,int j){
    int temp = array[i;
    array[i = array[j;
    array[j =temp;
  }
  }

debug的一个方法是举个简答的例子：

如

1   2  3  4

reverse只需要 两step:

4  2  3   1

4  3  2   1

解法是走4次，又变回原来的样子了

----------------------

public class Solution {
  public void reverse(int[] array) {
    // Write your solution here
    //int i = 0;
   // int j = array.length - 1;
    //while(i < j){
   for (int i = 0; i < array.length / 2; i++){
      swap(array,i,array.length - i - 1);
     // i++;
    //  j--;
    }
    }

  public void swap(int[] array,int i,int j){
    int temp = array[i;
    array[i = array[j;
    array[j =temp;
  }
  }

错误解法～～

题目：

Given an array, reverse all its elements.

Example:

array = [2, 3, 5, 7, 11]

result: [11, 7, 5, 3, 2]

Assumption: The array is not null or empty.

最一开始我的code是这样的，发现没有置换成功：

public class Solution {

  public void reverse(int[] array) {    // Write your solution here    for (int i = 0; i < array.length / 2; i++) {      swap(array[i], array[array.length - 1 - i]);    }  }    public static void swap(int a, int b) {    int k = a;    a = b;    b = k;  }  }

只有改成以下code，带入array参数，swap才能成功，为什么直接置换interger不可以？

public class Solution {  public void reverse(int[] array) {    // Write your solution here    for (int i = 0; i < array.length / 2; i++) {      swap(array, i, array.length - 1 - i);    }  }    public static void swap(int[] array, int a, int b) {    int k = array[a];    array[a = array[b];    array[b = k;  }  }java是pass by value的，你pass进去的两个值，会在swap函数运行的时候，copy一份，所以是copy的那份两个值交换了，但是原数组的值没有改变。

quote: "Java is always pass-by-value. Unfortunately, they decided to call the location of an object a "reference". When we pass the value of an object, we are passing the reference to it. " (cr: https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value)

这里是把 a,b指向的方向互换一下

for (int i = 0, j = array.length - 1; i < array.length && j >= 0; i++, j--) {    if (i >= j){        break;    }    swap(array, i, j);}
for (int i = 0, j = array.length -1; i < j; i++, j--){        swap(array, i, j);}

拆不散D大熊小熊

544. Design an accumulator
Design an accumulator, which can take a new integer using function “add”, and can return the sum of all taken integers up to now using function “sum”.
class Accumulator {
  int s = 0;
  public void add(int x) {
    s += x;
  }
  public int sum() {
    return s;
  }
}我写错了；
class Accumulator {
  public void add(int x) {
    int s = 0;
    s += x;
  }
  public int sum() {
    //int s = 0;
    sum = s;
    return sum;
  }



635. Sum of Squares

Problem: Give an array list of integer, calculate the sum of squares of all its elements.

Note: return 0 if the list is null or empty.

Example:

list = {1,2,3} → returns 14 (14=1*1+2*2+3*3)

public class Solution {
  public int sumOfSquare(List<Integer> list) {
    // Write your solution here
    if (list == null){
      return 0;
    }
    int sum = 0;
    for( int i : list){
      sum += i * i;
    }
    return sum;
  }
}
730. [Debug] areEqualCheck if the given number x and y are equal.
public class Solution {
  public boolean areEqual(int x, int y) {
    return x.equals(y);
  }
}
public class Solution {
  public boolean areEqual(int x, int y) {
    return x == y;
  }
}

732. [Debug] Reverse an array

There are bugs in the given code, please fix them.

Given an array, reverse all its elements.

Example:

array = [2, 3, 5, 7, 11]

result: [11, 7, 5, 3, 2]

Assumption: The array is not null or empty.
public class Solution {
  public void reverse(int[] array) {
    int start = 0;
    int end = array.length -1;
    while (start < end) {
      int temp = array[start];
      array[start] = array[end];
      array[end] = temp;
      start ++;
      end --;
    }
  }
}

拆不散D大熊小熊

14. Classical Binary Search


public class Solution {
  public int binarySearch(int[] array, int target) {
    // Write your solution here
    if(array == null || array.length == 0  ){
      return -1;
    }
    int left = 0;
    int right = array.length - 1;
    while (left <= right){
    int mid = (left + right)/2;
    if (array[mid == target){
      return mid;
    } else if (array[mid < target){
      left = mid + 1;

    }else{

      right = mid - 1;
    }
    }
    return -1;
    }
  }

拆不散D大熊小熊

著名的NPE问题


总结：找不到Objint[] array = null;int value = array[1];你连obj都找不着，找不到对象 因为reference是null
VS 没有钱包 Exceptions/ Errors: ArrayIndexOutOfBoundException!

int[] array = new int[]{5}：1个元素所以没有5的下标

Occupies consecutive memory and the elements in the array ... O(1)time .
int[] array = new int[3]; // {0,0,0}

int[][] array = new int[5][]; // {null,null,null,null,null}

每个低维数组没有被初始化！下标越界

Exceptions/ Errors:

ArrayIndexOutOfBoundException!

int[] array = new int[]{5}：1个元素所以没有5的下标

int value = array[5];

没有钱包=。= VS找不到obj:

NullPointerException! ：NPE

dereferece null 沿着名片找对象 但你的名片是空的： NPE

int[] array = null;

int value = array[1];

你连obj都找不着，

找不到对象 因为reference是null

int[][] array = new int[5][]; // {null,null,null,null,null}

每个低维数组没有被初始化！下标越界

int[][] array = new int[5][]; // {null, null, null,null,null}

int[] v1 = array[5]; // ArrayIndexOutOfBoundException!

???改成dict.get(i) != null && dict.get(i) > target

拆不散D大熊小熊

Java 基础：

左边的是共性，右边是每一辆的特性；

field。   static 共性不属于instance ；

Static

Members(field,methods,classes) belong to class, not object.

* what do you mean by belong to class, not instance"?属于类 class;不属于instance

无需instance； instance可能都没有创建

public class LaiOfferManager {

        public static void ipo ( ) {

                 isRich = true;

                 name //?不能 访问name （non 。static)车instance都没有 ，访问什么车主@@

        }

}

属于类的

能访问 这个name（这个field 属于instance的）这里IPO 是属于instance的

               s                     n

s            V                     V

n.s         x                     V

----------------------------------------------------

//能吧所有方法写成 s 不行没有ns instance自己的方法了=。=.

蓝色在 可以 这部分危险（一个人会改全部！因为属于类的状态 仅有一份）

用一个instance调用static method？读是很常见的吧 写X比较危险；在ns改s要三思！ 引用s最好用类名去高亮；在instance去访问 很危险

用类名. 在ns 访问s 用类名.

s调用ns。面试容易挂 ==....

EX:

public class Solution {

          public void search ( int [] array, int target) {

          ....

          }

          public static void main( String [] args) {

                     ....

                     search(myArray, myTarget);

          }

} //没有创建instance,类调用 instance 调用毛线

改：

public class Solution {

          public static void search ( int [] array, int target) {

          ...

          }

          public static void main( String [] args) {

                     ....

                     search(myArray, myTarget);

          }

}//这样就可以了（why；我让search也变成属于class s调用s ）

//instance有不同行为呀（s有局限，只能属于类， 不能属于instance）在static方法没有 this（=当前的instance）这里class一个instance都没有啊（this你想要的是instance）你自己建立一个吧： Solution s = new Solution();

public class Solution {

          public void search ( int [] array, int target) {

          ....

          }

          public static void main( String [] args) {

                     Solution s = new Solution();   //（给solution建instance）然后再调用instance

                     s.search(myArray, myTarget);

          }

}

//main这个方法属于s 所以你要main里面自己创建instance-，-没有人规定在s里面不能创建自己的属于类的instance:

main为啥java规定是static的呢？ Java运行程序他不管创建（helpyou）instance（你的事情）Java为调用entry （调用static的入口点）其他你自己创建instance;Entry不能改 main method 只能有一个//only one main method  in one class

//所有field 既可以属于类：class variable

Class variable vs. Instance variable /Class method vs. Instance method

Final

constants. "Once assigned , cannot be changed."   // final 关键字 意思 确定以后不能再修改,修饰class ，

Final class : A class that cannot be derived(inheritance)//mean 一个类不能有子类（inheritance）不能继承OOD

FInal method: A method that cannot be overridden.//不能被覆盖（我们现在的method子类不能修改这个method的行为，行为只此一份）

Final variable: A variable that once assigned, cannot be assigned again.//上面说面向对象设计;现阶段： final variable 一旦付值之后，不能修改;比如 ML模型训练出来：怕人用theta运算 :

Enforced invariance, instead of this:

// Don't change the value!

int theta = 5;

=.=: theta += 3;！！做project 时候 怕人改ML的theta,没看注释，导致分类结果差十万八千里

hhhhhhhhhIMAO 阻止猪队友：

// Don't change the value!!!!

final int theta = 5;

theta = 3 : ) no work

Soooooooo:

code review 工业界看 final。private 被人改了吗 : ) 你要去看能不能justify～你code review 有敏感性（如果final被删你要解决）在实习的时候我的teammate总是建议我把public变成private。对. 用最严的access modifier 能用final就用final 工业界的习惯提醒写代码的人。final。双向提醒（机制和人review时候）final 修饰的int。但如果修饰 reference field 女友

拆不散D大熊小熊

复习： 一个函数调用它自己（recursion，把大问题分成小问题，用小问题的解去构建大问题的解）

Recursion的三部曲： 1.subproblem。求出 recursion rule 。求出base case。

inear data structure : stack and queue FIFO?  ？？吃 可比克 和 排队

Phone call interviews ： how could we implement a queque by two stack?

分析两点： 写code 写的是什么？ 实现的是（data structure queue：class！）mergesort实现的一个算法，实现一个函数，method；

java 内存的数组 在java里面是连续存储的。地址 byte（1 int = 4 byte）Java 内存的数组所有数 在内存空间里面java里面是连续存储的。地址 byte（1 int = 4 byte）

gemmarong

感谢分享！