LeetCode-Java-Summary

Posted on | In

ArrayList

constructor and iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;  
class TestCollection1{  
 public static void main(String args[]){  
  ArrayList<String> list=new ArrayList<String>();//Creating arraylist  
  list.add("Ravi");//Adding object in arraylist  
  list.add("Vijay");  
  list.add("Ravi");  
  list.add("Ajay");  
  //Traversing list through Iterator  
  Iterator itr=list.iterator();  
  while(itr.hasNext()){  
   System.out.println(itr.next());  
  }  
  for(String str:list)
    System.out.println(str);
 }  
}

(only haveadd(Element e) and addAll(Collection c), not addFirst(Element e))

List and ArrayList

List is an interface, but ListArray is a class

List 不能被构造，即不能创建实例对象，但是可以为List接口创建一个指向自己的引用，而ArrayList实现类的实例对象则充当了这个指向List接口的对象引用

接口和抽象类都不能被实例化

ListArray extend and implement List

1
List list; //correct, list=null
1
List list = new List(); //wrong
1
2
List list = new ArrayList(); //correct
// 创建了一个ArrayList的对象后把他上溯到了List，此时他是一个List对象，有些ArrayList有但是List没有的属性和方法，他就不能再用了
1
2
ArrayList list = new ArrayList();
//创建ArrayList的对象，并保留了ArrayList的所有属性

The Key of the question:

Why using List list = new ArrayList() , rather than ArrayList alist = new ArrayList(), just use the interface, easy to change the implements.

List have many implement classes, you could change it to what you want. Just to change this line in your code. Maybe List list = new LinkedList();

ArrayList and LinkedList

ArrayList和LinkedList都实现了List接口的类，他们都是元素的容器，用于存放对象的引用

他们都可以对存放的对象进行增删查改的操作，还可以进行排序

除了对List接口的实现，他们还实现了其他的接口，由此造就了他们之间的差异

ArrayList

内部使用数组的形式实现了存储，实现了Random接口，利用数组对元素进行访问，因此对元素的随机访问速度非常快

  • 因为是数组，所以ArrayList在初始化的时候，有初始大小10，插入新元素的时候，会判断是否需要扩容，扩容的步长是0.5倍原容量，扩容方式是利用数组的复制，因此有一定的开销；
  • ArrayList在进行元素插入的时候，需要移动插入位置之后的所有元素，位置越靠前，需要位移的元素越多，开销越大，相反，插入位置越靠后的话，开销就越小了，如果在最后面进行插入，那就不需要进行位移；

add(int index, E element)

Inserts the specified element at the specified position in this list.

LinkedList

内部使用双向链表的结构实现存储，LinkedList有一个内部类作为存放元素的单元，有3个属性，用来存放元素本身和前后2个单元的引用，另外LinkedList内部还有一个header属性，用来标识起始位置，LinkedList的第一个单元和最后一个单元都会指向header，因此形成了一个双向的链表结构。

LinkedList是采用双向链表实现的。所以它也具有链表的特点，每一个元素（结点）的地址不连续，通过引用找到当前结点的上一个结点和下一个结点，即插入和删除效率较高，只需要常数时间，而get和set则较为低效。

LinkedList的方法和使用和ArrayList大致相同，由于LinkedList是链表实现的，所以额外提供了在头部和尾部添加/删除元素的方法，也没有ArrayList扩容的问题了。另外，ArrayList和LinkedList都可以实现栈、队列等数据结构，但LinkedList本身实现了队列的接口，所以更推荐用LinkedList来实现队列和栈。

public void addFirst(E e)

Inserts the specified element at the beginning of this list.

public void addLast(E e)

Appends the specified element to the end of this list.

This method is equivalent to add(E).

Conclude

在需要频繁读取集合中的元素时，使用ArrayList效率较高，而在插入和删除操作较多时，使用LinkedList效率较高

StringBuffer

1
public StringBuffer append(char c)
1
public StringBuffer reverse()
1
public String toString()

Stack

1
Stack<> stack = new Stack<>();

Iterate through stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.*;
public class MyClass {
    public static void main (String[] args)
	{
		// if we use Stack, output will be [1, 2, 3]
		Stack<Integer> stack = new Stack<>();
		// if we use Deque, output will be [3, 2, 1]
		// Deque<Integer> stack = new ArrayDeque<>();
		stack.push(1);
		stack.push(2);
		stack.push(3);
		/* Using Iterator */
		// 1. Using Iterator to iterate through Stack
		Iterator<Integer> itr = stack.iterator();
		// hasNext() returns true if the stack has more elements
		while (itr.hasNext())
		{
			// next() returns the next element in the iteration
			System.out.println(itr.next());
		}	
		// 2. Using enhanced for loop (uses Iterator internally)
		for (Integer item: stack) {
			System.out.println(item);
		}
		/* Java 8 and above */
	}
}

Array length

length – arrays ( int[], double[], String[])

length() – String related object ( String, StringBuilder, etc)

size() – Collection Object (ArrayList, Set, etc)

Array initial

1
2
3
double[] myList;   // preferred way.
or
double myList[];   // works but not preferred way.

iter items

1
2
3
for (double element: myList) {
         System.out.println(element);
      }

StringBuilder

StringBuilder objects are like String objects, except that they can be modified. Internally, these objects are treated like variable-length arrays that contain a sequence of characters. At any point, the length and content of the sequence can be changed through method invocations.

1
2
3
4
// creates empty builder, capacity 16
StringBuilder sb = new StringBuilder();
// adds 9 character string at beginning
sb.append("Greetings");

StringBuilder append(float f) / (int i) / (long lng) / (Object obj) / (String s)

StringBuilder delete(int start, int end)

StringBuilder deleteCharAt(int index)

StringBuilder insert() StringBuilder replace() StringBuilder reverse() String toString()

String

String Trim

public String trim()

It returns a copy of this string with leading and trailing white space removed, or this string if it has no leading or trailing white space.

1
2
"   Welcome to Tutorialspoint.com   " ==>
"Welcome to Tutorialspoint.com"

String contains

1
2
3
4
public boolean contains(CharSequence sequence)
{
   return indexOf(c.toString()) > -1;
}

String replace

1
2
public String replace(char oldChar, char newChar)  
public String replace(CharSequence target, CharSequence replacement)

char to String

1
2
3
4
5
6
7
8
9
1. String stringValueOf = String.valueOf('c'); // most efficient
2. String stringValueOfCharArray = String.valueOf(new char[]{x});
3. String characterToString = Character.toString('c');
4. String characterObjectToString = new Character('c').toString();
   // Although this method seems very simple, 
   // this is less efficient because the concatenation
   // expands to new StringBuilder().append(x).append("").toString();
5. String concatBlankString = 'c' + "";
6. String fromCharArray = new String(new char[]{x});

String subString

1
public String substring(int begIndex)
1
public String substring(int begIndex, int endIndex)

HashSet

Important Methods in HashSet:

  1. boolean add(E e) : add the specified element if it is not present, if it is present then return false.
  2. void clear() : removes all the elements from set.
  3. boolean contains(Object o) : return true if element is present in set.
  4. boolean remove(Object o) : remove the element if it is present in set.
  5. Iterator iterator() : return an iterator over the element in the set.

How HashSet internally work?

All the classes of Set interface internally backed up by Map. HashSet uses HashMap for storing its object internally. You must be wondering that to enter a value in HashMap we need a key-value pair, but in HashSet we are passing only one value.

Then how is it storing in HashMap?

Actually the value we insert in HashSet acts as key to the map Object and for its value java uses a constant variable. So in key-value pair all the keys will have same value.

Operator Priority

Operators Precedence
postfix expr++ expr--
unary ++expr --expr +expr -*expr* ~ !
multiplicative * / %
additive + -
shift << >> >>>
relational < > <= >= instanceof
equality == !=
bitwise AND &
bitwise exclusive OR ^
bitwise inclusive OR ` `
logical AND &&
logical OR ` `
ternary ? :
assignment `= += -= *= /= %= &= ^= = <<= >>= >>>=`

Queue

Interface Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Java orogram to demonstrate working of Queue
// interface in Java
import java.util.LinkedList;
import java.util.Queue;
 
public class QueueExample
{
  public static void main(String[] args)
  {
    Queue<Integer> q = new LinkedList<>();
 
    // Adds elements {0, 1, 2, 3, 4} to queue
    for (int i=0; i<5; i++)
     q.add(i);
 
    // Display contents of the queue.
    System.out.println("Elements of queue-"+q);
 
    // To remove the head of queue.
    int removedele = q.remove();
    System.out.println("removed element-" + removedele);
 
    System.out.println(q);
 
    // To view the head of queue
    int head = q.peek();
    System.out.println("head of queue-" + head);
 
    // Rest all methods of collection interface,
    // Like size and contains can be used with this
    // implementation.
    int size = q.size();
    System.out.println("Size of queue-" + size);
  }
}

1.boolean offer(E e)

Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. When using a capacity-restricted queue, this method is generally preferable to add(E)), which can fail to insert an element only by throwing an exception.

Parameters:

e - the element to add

Returns:

true if the element was added to this queue, else false

2.E remove()

Retrieves and removes the head of this queue. This method differs from poll) only in that it throws an exception if this queue is empty.

  • Returns:

    the head of this queue

3.E poll()

Retrieves and removes the head of this queue, or returns null if this queue is empty.

Returns:

the head of this queue, or null if this queue is empty

Modifier and Type Method and Description
boolean add(E e)Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
E element()Retrieves, but does not remove, the head of this queue.
boolean offer(E e)Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
E peek()Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
E poll()Retrieves and removes the head of this queue, or returns null if this queue is empty.
E remove()Retrieves and removes the head of this queue.

Integer

Integer.MAX_VALUE = 2147483647

= -2147483647

Integer.MAX_VALUE + 1 == Integer.MIN_VALUE

2147483647+2 = -2147483647

2147483647+3 = -2147483646

Comparable, Comparator

Java provides two interfaces to sort objects using data members of the class:

  1. Comparable
  2. Comparator

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// A Java program to demonstrate use of Comparable
import java.io.*;
import java.util.*;
 
// A class 'Movie' that implements Comparable
class Movie implements Comparable<Movie>
{
    private double rating;
    private String name;
    private int year;
 
    // Used to sort movies by year
    public int compareTo(Movie m)
    {
        return this.year - m.year;
    }
 
    // Constructor
    public Movie(String nm, double rt, int yr)
    {
        this.name = nm;
        this.rating = rt;
        this.year = yr;
    }
 
    // Getter methods for accessing private data
    public double getRating() { return rating; }
    public String getName()   {  return name; }
    public int getYear()      {  return year;  }
}
 
// Driver class
class Main
{
    public static void main(String[] args)
    {
        ArrayList<Movie> list = new ArrayList<Movie>();
        list.add(new Movie("Force Awakens", 8.3, 2015));
        list.add(new Movie("Star Wars", 8.7, 1977));
        list.add(new Movie("Empire Strikes Back", 8.8, 1980));
        list.add(new Movie("Return of the Jedi", 8.4, 1983));
 
        Collections.sort(list);
 
        System.out.println("Movies after sorting : ");
        for (Movie movie: list)
        {
            System.out.println(movie.getName() + " " +
                               movie.getRating() + " " +
                               movie.getYear());
        }
    }
}

We can implement the Comparable interface with the Movie class, and we override the method compareTo() of Comparable interface.

1
2
3
4
5
Movies after sorting : 
Star Wars 8.7 1977
Empire Strikes Back 8.8 1980
Return of the Jedi 8.4 1983
Force Awakens 8.3 2015

extends and implements

Java Extends: When you want to extend a subclass to be extended in inheritance that we use Java extends.

Java Implements: When an implement an interface, we use the keyword implement.

Java Extends vs Implements: In short, extends is for extending a class and implements are for implementing an interface.

As Java doesn’t support multiple interfaces and this problem overcomes by using multiple interfaces.