DSA-Learning
Learning Source
https://www.techinterviewhandbook.org/grind75
String
1.Reverse String
leetcode:https://leetcode.com/problems/reverse-string
**Desciption:**Write a function that reverses a string. The input string is given as an array of characters s
idea:
step1: set two pointer(start index, end index)
step2: By setting the temporary variable, swap the front and back elements until the middle one is reached
Code:
class Solution {
public void reverseString(char[] s) {
int i = 0;
int j = s.length-1;
if(j == 0){
System.out.print("");
}
while(i<j){
char temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
}
2. Reverse String 2
**leetcode:**https://leetcode.com/problems/reverse-string-ii
Description:
Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.
If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.
Idea:
Step1: because the problem need to change the range between k character and 2k characters, we traverse the string and increase the index by 2k
Step2: if left characters less than k characters, it means the current index + k will larger than the length of string, so reverse the whole left string
Step3: if there are less than 2k but greater than or equal to k characters, then reverse the first k characters. it menas if the current index plus k won’t exceed the length of string, just reverse the first k character. the range of the reverse is(i, i+k-1)
Code:
class Solution {
public String reverseStr(String s, int k) {
int length = s.length()-1;
char[] result = s.toCharArray();
// traverse the string and set the index increased by 2k each time
for(int i=0; i<=length; i = i+2*k){
// if the left characters more than k characters(so the current index + k, it will less or equal than length of string), reverse first k
if (i+k<=length){
reverse(result, i, i+k-1);
continue;
}
// if left characters less than k characters, reverse all
if(i+k > length){
reverse(result, i, length);
continue;
}
}
return new String(result);
}
public void reverse(char[]s, int i, int j){
while(i<j){
char temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
}
return the array to string
new String(character);
3. Replace Space to %20 in the String
**leetcode:https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
Description:
Please implement a function that replaces each space in the string s with “%20”.
Idea:
Solution1:
Step1: build a new empty string
Step2: traverse the string, if the characetr is space. then add the new string with %20, if it’s not the space, add it to the new string
Code:
class Solution {
public String replaceSpace(String s) {
String string1 = "";
for(int i=0; i<s.length(); i++){
if (s.charAt(i) == ' '){
string1 = string1 + "%20";
}
if(s.charAt(i) != ' ')
string1 = string1 + s.charAt(i);
}
return string1;
}
}
in the '' , it only exits character;
in the "", it exits string;
Solution2:
Step1: expand double space(because we need to replace " " to “%20”, so add two space after the string) of the space in the string: creating the new string, if the character of the string is space, add three space to the new string.
Step2: create two pointer. the first one to point the end of original string.
then add the new string to the original string, the second pointer point to end of expanded string.
Step3: if the first pointer == space, then the second pointer will replace the character with %20 by decreasing the index. if the first pointer isn’t equal to space, then make the character that scond pointer pointed equal to the character that first pointer pointed.
Step4: leftmove the first pointer and second pointer, until first pointer equal to the start of the string.
Code:
class Solution {
public String replaceSpace(String s) {
String add = "";
// expand the string
for(int i=0; i<s.length(); i++){
if (s.charAt(i) == ' '){
add += " ";
}
}
// set the first pointer point to the end of original string
int fisrtpointer = s.length()-1;
// expand string and set the second pointer point to the end of the new string
s+=add;
int secondpointer = s.length()-1;
char[] result =s.toCharArray();
while(fisrtpointer>=0){
if(result[fisrtpointer]==' '){
// replace the space with %20, by self decreasing the index; becasue x--, will decrease the value after the operation
result[secondpointer--]= '0';
result[secondpointer--]='2';
result[secondpointer]='%';
}
else{
result[secondpointer]=result[fisrtpointer];
}
fisrtpointer--;
secondpointer--;
}
return new String(result);
}
}
4. Reverse Words in a String
**leetcode:**https://leetcode.com/problems/reverse-words-in-a-string/
Description:
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Idea:
Solution1:
Step1: remove extra space of the string
Step2: reverse the whole string, and then reverse each word in the string
Step3: use two pointer to implement the reverse specified range
Step4: in the remove extra space method, first use loop to get the index after all space at the begainning. then use loop to traverse from the end, to get the index before all space at the end of the string.
To remove duplicate space inside the string, traverse the element and use new string to store the character isn’t space, or if the character is space, but the last element in the new string isn’t space, then store the space.(it ensures in the new string, there are no continuously space.)
Step 5: set two pointer to get the range of each word in the string, at the beginning, two pointes point to 0 and 1 seperately. then traverse the string(until the first point exceed the string), if the next element is space, then use scend pointer to get the index. then reverse the word in the range(first index, second index -1). make first index equal to second index+1, and second index point to next element.
Code:
class Solution {
public String reverseWords(String s) {
if (s.length() == 0){
return s;
}
char[] result = trim(s).toCharArray();
int length = result.length;
reverse(result,0,length-1);
// reverse each word
int start = 0;
int end = 1;
while(start < length){
while(end < length && result[end]!=' '){
end++;
}
reverse(result,start,end-1);
start = end +1;
end = start + 1;
}
return new String(result);
}
public String trim(String s){
int start = 0;
int end = s.length()-1;
String string1 ="";
// remove all space in the begainning of the string
while(start<=end && s.charAt(start) ==' '){
start++;
}
//remove all space at the end of the string
while (start<=end && s.charAt(end) ==' '){
end--;
}
//remove the extra space in the string
while(start<=end){
if (s.charAt(start) != ' '){
string1 += s.charAt(start);
}
// when the character is space, but the end character of the result string is not space, then store it
else if(s.charAt(start) == ' ' && string1.charAt(string1.length()-1) != ' '){
string1 += s.charAt(start);
}
start++;
}
return string1;
}
public void reverse(char[]s, int i, int j){
while(i<j){
char temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
}
Solution2:
Use new char array to store the character one by one
Step1: create new char array and make the size of it as the original array’s length +1
Step2: traverse the string from the end of the string, and use firtst pointer to get the index that before all space after the word.
Step3: then use the second pointer to record this index, continue traverse until the character is space. then traverse characters between two pointers one by one through putting them to the new array. and add one space in the world.
Step4: delete the last element of the array, because we will add one more space in the last word.
Code:
class Solution {
public String reverseWords(String s) {
char[] sa = s.toCharArray();
char[] result = new char[sa.length+1];
// set the index for result array
int index = 0;
// set first pointer
int i = sa.length -1;
while(i>=0){
// avoid space
while(i>=0 && sa[i] == ' '){
i--;
}
// set second pointer
int second = i;
while(i>=0 && sa[i] !=' '){
i--;
}
for (int j = i+1; j<=second; j++){
result[index++] = sa[j];
if (j==second){
result[index++] = ' ';
}
}
}
// because we add one more space in the end of the array
return new String(result,0,index-1);
}
}
5. Left roate the String
leetcode: https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof
Description:
The left rotation operation of a string is to transfer several characters in front of the string to the end of the string. Please define a function to implement the function of left rotation of strings. For example, input the string “abcdefg” and the number 2, the function will return the result “cdefgab” obtained by left-rotating two places.
Idea:
Solution1:
Step1: create new string, and split the original string according to the number, then combine them
this solution will cost more Space complexity
Code:
class Solution {
public String reverseLeftWords(String s, int n) {
String string1 ="";
for(int i =n; i<s.length(); i++){
string1 = string1 + s.charAt(i);
}
for(int i=0; i<n; i++){
string1 += s.charAt(i);
}
return string1;
}
}
Solution2:
Step1: Reverse the substring before the specific number
Step2: Reverse the substring after the number
Step3: Reverse the whole string
Code:
class Solution {
public String reverseLeftWords(String s, int n) {
char[] result = s.toCharArray();
reverse(result,0,n-1);
reverse(result,n,s.length()-1);
reverse(result,0,s.length()-1);
return new String(result);
}
public void reverse(char[]s, int i, int j){
while(i<j){
char temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
}
6. Implement strStr()
leetcode: https://leetcode.com/problems/implement-strstr/
Description:
Implement strStr().
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().
Idea:
Solution1:
Step1: use loop to traverse the original string, and get the substring from the current index to the current index + the length of needed string, if equal, then return current index, otherwise, return -1;
Code:
class Solution {
public int strStr(String haystack, String needle) {
for(int i=0; i<haystack.length(); i++){
if(i+needle.length() <= haystack.length()){
if(haystack.substring(i,i+needle.length()).equals(needle)){
return i;
}
}
}
return -1;
}
}
Solution2: KMP Algorithm
(1)KMP Algorithm is used to match string;
(2)The idea of it is that when there is a string mismatch, you can know a part of the text content that has been matched before, you can use this information to avoid doing the matching from scratch. Use next Array to record these content. (Next array is a Prefix Table).
(3)Prefix: all substrings starts with first character that don’t include last character in the string.
Suffix: all substrings ends with the last character that don’t include first character in the string.
Example:
abcd
prefix: a,ab,abc
suffix: d,cd,bcd
(4) build the Prefix Table: find the longest length of (prefix = suffix)
Example: the string is aabaaf
a: 0
aa: 1(prefix=a, suffix =a)
aab:0(prefix=a,aa; suffix =b,ab)
aaba:1(prefix:a,aa,aab ; suffix: a,ba,aba; so the a=a, length is 1)
aabaa: 2 (prefix:a,aa,aab,aaba; suffix:a,aa,baa,abaa; so aa =aa, the length is 2)
aabaaf: 0
The Prefix Table of aabaaf is :
aabaaf
010120
(5) when find the confict character(two character isn’t same), we find the longest length of (prefix = suffix) of the character before this character. Then, set the number of this length as the new start index of match
(6) Get the prefix Array
Step1:initialization, set two pointer(one for the end of suffix, one for the prefix and record the length of (suffix = prefix)), initialize the array
Step2: when the two characters that two pointer pointed are not equal, make the prefix index return to the character that they are equal, if can’t find the same character until the begining of the string, then make index as the beginning of the string.
Step3: if two characters are equal, then make the suffix and prefix pointers point to next
Step4: Update the array, give the array with current length of prefix.
public void GetArray(String s){
int j=0; //set the prefix pointer
int i=1; //set the suffix pointer
int[] next = new int[s.length()];
char[] result = s.toCharArray();
for(;i<s.length();i++){
while(j>0 && result[j]!=result[i]){
j = next[j-1];
}
if(result[i] == result[j]){
j++;
}
next[i]=j;
}
}
Step1: build the prefix Table Array of KMP for the needle string
Step2: Compare the needle string with original string with prefix table
Code:
class Solution {
public int strStr(String haystack, String needle) {
if (needle.length() == 0){
return 0;
}
char[] s1 = haystack.toCharArray();
char[] s2 = needle.toCharArray();
// the prefix table array
int[] result = new int[needle.length()];
// build the prefix table array for needle string
// set two pointers, j is prefix pointer(it also used to record the length of (prefix = suffix)) and i is suffix pointer
int j= 0;
for(int i=1; i<s2.length;i++){
// if two character aren't equal, move back the j, until the character it pointed equal to the i pointed or it back to the begining of the string
while(j>0 && s2[j]!=s2[i]){
j = result[j-1];
}
// j also record the length, and when two characters are euqal, move two pointers to the next(i has moved in the loop)
if(s2[i] == s2[j]){
j++;
}
result[i]=j;
}
// compare the original string and the needle string
// set the pointer for needle
int first = 0;
for (int second = 0; second < s1.length; second++){
// compare the needle and original string
while(first>0 && s1[second] != s2[first]){
first = result[first-1];
}
if(s1[second] == s2[first]){
first++;
}
// when compare all the needle string, and because now the first is equal to the length of needle, so get the index by minius it.
if(first == s2.length){
return (second-first+1);
}
}
return -1;
}
}
7. Repeated Substring Pattern
leetcode: https://leetcode.com/problems/repeated-substring-pattern/
Description:
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Idea:
Step1: us KMP to get the prefix table of the string.
Step2: The length of the string - the longest length(suffix == prefix) of the string = the repeated substring’s length
Step3: If the length of string % the repeated substring’s length =0, it menas the original strings consists of the substring.
Code:
class Solution {
public boolean repeatedSubstringPattern(String s) {
if (s.length()==0){
return false;
}
char[] sc = s.toCharArray();
int j = 0;
int length = s.length();
int[] result = new int[s.length()+1];
for(int i =1; i<sc.length; i++){
while(j>0 && sc[i] != sc[j]){
j = result[j-1];
}
if(sc[i] == sc[j]){
j++;
}
result[i] = j;
}
if(result[length-1] > 0 && length%(length-result[length-1]) == 0){
return true;
}
return false;
}
}
Array
1. Basic of Array
(1)The start index of the array is 0;
(2)The memory space of array is continously.
(3)An array is a collection of data of the same type stored in a contiguous memory space.
(4) when add or delete the element in the array, we need to move elements after the element.
(5)we can only cover value of the element instead of deleting it.
2.Binary Search
leetcode: https://leetcode.com/problems/binary-search/
Description:
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
Idea: the defination of the interval is important, each interval is defined with same rule([ ]or[ ):include the right bound or not), each operation in the while loop need consider the defination of interval.
Step1: Because the nums is sorted, if the target less than the first element in the nums or the target bigger than the last one, it doesn’t exist in the string
Step2: set the right,left and mid bound. make the mid bound = right + (left-right)/2
Step3: if the target bigger than middle, make the right bound index to the middle pointer +1, otherwise, make the left bound index to middle index -1;
Code:
class Solution {
public int search(int[] nums, int target) {
// because the nums is sorted, if the target less than the first element in the nums or the target bigger than the last one, it doesn't exist in the string
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
// set the left bound and right bound
int i=0;
int j=nums.length-1;
// set the mid pointer, because it's sorted, so if the middle one bigger than target, then make the left bound equal to middle-1, otherwise make the right bound to the middle+1;
while(i<=j){
int mid = i + (j-i)/2;
if(nums[mid] == target){
return mid;
}
else if(target < nums[mid]){
j = mid-1;
}
else if(target > nums[mid]){
i = mid+1;
}
}
// this target doesn't exist in the nums
return -1;
}
}
3.Remove Element
leetcode: https://leetcode.com/problems/remove-element/
Description:
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Idea:
Step1: set two pointers, first one to traverse the nums array, and use second one to recod the non-val element and use them to cover the val element.
Step2: because we don’t need to deal with the extra elements after covering, and the second pointer also record the length of non-value elements in the string. just use the index to get the non-val nums array.
Code:
class Solution {
public int removeElement(int[] nums, int val) {
// set two pointers, and make the second pointer point to the non-val element, and use second to record current length of non-val
int first = 0;
int second = 0;
// because it don't need to deal with the extra elements when after cover the val element, so just use first pointer to traverse the nums, and use second pointer to record the value and the length
for(; first<nums.length; first++){
if(nums[first] != val){
// use second pointer to cover and record length by self-increasing
nums[second++] = nums[first];
}
}
return second;
}
}
4.Squares of a Sorted Array
leetcode: https://leetcode.com/problems/squares-of-a-sorted-array/
Description:
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Idea:
solution1: Brute Force
traverse the nums and square each element, than sort the nums
Code:
class Solution {
public int[] sortedSquares(int[] nums) {
// get square of each element
for(int i=0; i<nums.length; i++){
nums[i] = nums[i]*nums[i];
}
// sort array
Arrays.sort(nums);
return nums;
}
}
solution 2: two pointers
Step1: create new array to store the sorted square value
Step2: set two pointer(one for start, one for end), because only square of negative may larger than last positive one and one index for new array, and store it from the end to keep the sort of the array.
Step3: if the square of start larger than the square of the end one, then store teh bigger one to the new array. at the same time, just increase the first index to compare the next element with the element that the second pointer pointed. Otherwise, do the opposite operations.
Code:
class Solution {
public int[] sortedSquares(int[] nums) {
// create new array to store the sorted square value
int[] result = new int[nums.length];
// set two pointer(one for start, one for end), because only square of negative may larger than last positive one
// and one index for new array, and store it from the end to keep the sort of the array
int first = 0;
int second = nums.length-1;
int index = result.length-1;
while(first <= second){
// if the square of start larger than the square of the end one, then store teh bigger one to the new array. at the same time, just increase the first index to compare the next element with the element that the second pointer pointed
if(nums[first]*nums[first] > nums[second]*nums[second]){
result[index--] = nums[first]*nums[first];
first++;
}
// the opposite situation
else{
result[index--] = nums[second]*nums[second];
second--;
}
}
return result;
}
}
6. Minimum Size Subarray Sum
leetcode: https://leetcode.com/problems/minimum-size-subarray-sum/
Description:
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Idea:
solution1: Brute Force(Time exceed)
Step1: set a variable to record the length of elements that meet the requirement
Step2: traverse the nums and sum the elements until the sum larger than the target and compare the length of these element with current length, make the result point to the min one.
Step3:if the variable equal to the initial value,it means no substring meet the requirement, return 0; otherwise return the length.
Code:
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result = Integer.MAX_VALUE;
for(int i=0; i<nums.length; i++){
int sum =0;
for(int j=i; j<nums.length; j++){
sum += nums[j];
if(sum>=target){
result = Math.min(result,(j-i+1));
}
}
}
return result == Integer.MAX_VALUE ? 0:result;
}
}
solution 2: Sliding Window
(1) Idea: change the start and end index of the subsequence dynamic to get the result that meet the requirement(it’s the process that continous searching the range)
(2) Key Points: set the content of the window; how to set and move the start and end index;
(3) Just use one loop, and use the index of the loop as the end index of the sliding window.
In this Problem:
Step1: the content of the window is the subarray that meet sum >=target
Step2: when the meet the requirement, move the left bound index to next element to Narrow the scope
Step3: the index in the loop as fast index, it will control the right bound of the window, and move itself with the loop.
Code:
class Solution {
public int minSubArrayLen(int target, int[] nums) {
// set the variable to record the length
int result = Integer.MAX_VALUE;
// set the sum and slowindex to control the move the left bound of the range
int sum = 0;
int slowindex = 0;
// traverse the nums and make the index as the right bound of the array
for(int i=0; i<nums.length; i++){
sum += nums[i];
// compare the sum and target
while(sum>=target){
// get the current length of these elements meet the requirement and compare it with the length the result stored
result = Math.min(result,(i-slowindex+1));
// remove the left bound by self incresing, and get the sum of new range, if it also meet the requirement, check the length again, other wise change the right bound index to get the new range.
sum -= nums[slowindex++];
}
}
// check is there no subarray meet the requirement
return result == Integer.MAX_VALUE ? 0:result;
}
}
//Integer. MAX_VALUE represents the maximum positive integer value that can be represented in 32 bits (i.e., 2147483647 ).
//so that ensure if the sub array exists, it's length less than Integer. MAX_VALUE
7. Spiral Matrix II
leetcode: https://leetcode.com/problems/spiral-matrix-ii/
Description:
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.
Idea:
solution1:
Step1: set two index for the round(one for row and the other for column), and index of the number of times to loop
Step2: the number of the rounds we need take is n/2. if the number is odd, we need to assign the value to the array central, if the number if even, when all rounds finished, all the elements will be assigned.
Step3: set two index of loop and set the same interval rule of the loop for each side of the square, for example, in each side only include from the first element to penultimate element, and left the last element for next side(as the first element)
Code:
class Solution {
public int[][] generateMatrix(int n) {
//initialize the result array
int[][] result = new int[n][n];
//set the bound index for round
int bound_i = 0, bound_j =0;
//set the index to reocrd the number of times it has looped
int loop = 0;
//to give each element value with self-increase it
int count = 1;
// set two index for the loop
int i,j;
//n/2 means the number of times it needed
while(loop < n/2){
//make two loop index point to the correct bound of the current round
i=bound_i;
j=bound_j;
//upper side, and just move the column index to assign the value to all element in this row
//each side don't deal with the last element and left them as the first element for the next side
for(j=bound_j; j<n-1-loop; j++){
result[i][j] = count++;
}
//right side, just move row index, and because the last loop has move the column index to the right index.
for(i=bound_i; i<n-1-loop; i++){
result[i][j] = count++;
}
//bottom side, move it back to the start bound of this round
for(;j>bound_j; j--){
result[i][j] = count++;
}
//left side
for(;i>bound_i; i--){
result[i][j] = count++;
}
//narrowing the bound to next round
bound_i++;
bound_j++;
loop++;
}
if (n%2 == 1){
result[n/2][n/2] = count++;
}
return result;
}
}
Hash Table
1.Basic of Hash table
Hashtable
(1) It’s a data structure that use index to access the element directly.(array)
(2) It can solve the problem that determine whether one element is in the set or not. (the time complexity is O(1))
Hash Function
It’s map the needle to the index of Hash table
Example: Initialize student names into hash table
Process: use hashcode(it can convert different data types to the number) to covert the name to the number
if the number obtained by Hashcode is larger than the size of hashtable, to ensure the number will in the hashtable, we could get the modulus of the number with hashtable size. (Hashcode(name)%hashtable.size)
Hash Collisions
Hash collisions means if the different names map to the same index of the hashtable
Solutions:
(1) Separate Chaining: create the linkede list and store the collision elements in to the linked list, so we can use the index to distungish the exact element.
(2)Linear probing(the hashtable size need larger than the data size): when find there is a collision, placing the new key into the closest following empty cell.
Structure of Hash
(1)Array
(2)Hashset: make elements in the set is unique
//define hashset
Set<data type> variale = new HashSet<>();
//add elements to set
set.add(x);
//check does the element exist in the set
set.contains();
(3)HashMap
//define hashmap
Map<key data type, value:data type> variable = new HashMap<>();
//associate key and value in the map
Hash_Map.put(key, value)
//check whether a particular key is being mapped into the HashMap or not
Hash_Map.containsKey(key_element)
//returns the value associated with the key_element in the map;
Hash_Map.get(key_element)
Array
2. Valid Anagram
leetcode: https://leetcode.com/problems/valid-anagram/
Description:
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Idea:
solution1: use sorted api
Code:
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] sa = s.toCharArray();
char[] ta = t.toCharArray();
Arrays.sort(sa);
Arrays.sort(ta);
//return new String(ta).equals(new String(sa));
return Arrays.equals(sa,ta);
}
}
**solution 2: **
Step1: use array(simple hash table) to record each alphabet and the corresponding occurrences
Step2: record first string with the array, and then decrease value of the each index when record the second string
Step3: if all element’s value is 0 in the array, it means two strings are anagram.
Code:
class Solution {
public boolean isAnagram(String s, String t) {
//if two string's length is not equal, return false
if (s.length() != t.length()) {
return false;
}
//create a array with the size is 26(alphabet is 26 letters)
int[] result = new int[26];
//record each letter and the corresponding times with increase
for(char x:s.toCharArray()){
//get index by calculate ASCII
result[x - 'a'] += 1;
}
//record the other string, with decrease
for(char y:t.toCharArray()){
result[y - 'a'] -= 1;
}
//verify each element's value of the array
for(int i:result){
if(i!=0){
return false;
}
}
return true;
}
}
result[x - 'a']
//calculate the ASCII value
Set
3. Intersection of Two Arrays
leetcode: https://leetcode.com/problems/intersection-of-two-arrays/
Description:
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
Idea:
solution:
Step1: set two set, first set to ensure the first nums array’s element is unique, and second set to ensure the elements in the result set is unique.
Step2: check the second nums array’s element is whether contained in the result set or not
Step3: convert the set to array and output aray
Code:
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
//set two set to make the unique element
Set<Integer> record = new HashSet<>();
Set<Integer> result = new HashSet<>();
//unique the first array
for(int i:nums1){
record.add(i);
}
//if the second array's element in the first set, record it, and use set to ensure the result is unique
for(int j:nums2){
if(record.contains(j)){
result.add(j);
}
}
//output as array
int index=0;
int[] ResArray = new int[result.size()];
for(int i:result){
ResArray[index++] = i;
}
return ResArray;
}
}
set.contains(x);
//to verify does this element exist in the set
4.Happy Number
leetcode: https://leetcode.com/problems/happy-number/
Description:
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
- Starting with any positive integer, replace the number by the sum of the squares of its digits.
- Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
- Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
Idea:
solution
Step1: build the get sum method, get the number on each digit of a number by taking the modulo, and divid the original number with 10 to remove the last digit.
Step2: use set to store each sum of n, and make n = sum round by round(or use recursion), until n=1, or there exists same sum in the result
Step3: verify n is 1 or not
Code:
//recursion
class Solution {
Set<Integer> result = new HashSet<>();
public boolean isHappy(int n) {
if(n<=0){
return false;
}
if(n==1){
return true;
}
if(result.contains(n)){
return false;
}
result.add(n);
n = getSum(n);
return isHappy(n);
}
public int getSum(int n){
int sum = 0;
while(n!=0){
sum += (n%10)*(n%10);
n=n/10;
}
return sum;
}
}
//non-recursion
class Solution {
public boolean isHappy(int n) {
Set<Integer> result = new HashSet<>();
if(n<=0){
return false;
}
while(n!=1 && !result.contains(n)){
result.add(n);
n = getSum(n);
}
return n==1;
}
public int getSum(int n){
int sum = 0;
while(n > 0){
sum += (n%10)*(n%10);
n=n/10;
}
return sum;
}
}
Map
5. Two Sum
leetcode: https://leetcode.com/problems/two-sum/
Description:
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Idea:
solution1: brute force
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i=0; i<nums.length; i++){
for (int j=i+1; j<nums.length; j++){
if(nums[i] + nums[j] == target){
result[0]=i;
result[1]=j;
return result;
}
}
}
return null;
}
}
Solution 2: Hashmap
Step1: create a hash map and set the nums’ element as key, the index as value
Step2: traverse the nums array, and use target-current element, to check is the second element’s whether as the key in the map, if map contains this element, then return current index, and the this key’s corresponding value(the value is assigned by index), the value is second element’s index
Setp3: continue add elements to the map
Code:
class Solution {
public int[] twoSum(int[] nums, int target) {
//record two index of the result
int[] result = new int[2];
//if the nums array is empty or elements it has lees than two
if(nums.length==1 || nums==null){
return result;
}
//set the map, and the type of key and value is integer
Map<Integer,Integer> record = new HashMap<>();
for (int i=0; i<nums.length; i++){
//get the number of second element
int second = target - nums[i];
//make the number of each element as key of the map, so verify is the second element in the map or not
if(record.containsKey(second)){
//first index
result[0]=i;
//because the value in the map is the index, so through key get the index of second element
result[1]=record.get(second);
}
//add element to the map
record.put(nums[i], i);
}
return result;
}
}
6.4Sum II
leetcode: https://leetcode.com/problems/4sum-ii/
Description:
Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
Idea:
solution
This problem allows repeatead combination
Step1: create one map, record possible sum of array A and B, record the number of each combination
Step2: if combination of sum array C and D meet 0-sum(a,b), and this combination in the map1, then get the value of the combination in the map
Step3:beacasue repeated situation is allowed, so add all times of one combination to the result
Code:
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
//create map to record sum and the number of times the combination appeared
Map<Integer,Integer> record = new HashMap<>();
//record the result
int count=0;
//use map to record all combinations and numbers of Array A and Array B
for(int i:nums1){
for(int j:nums2){
int sum =i+j;
//if this combination has exists in the map, then get the value of this key and plus 1
if(record.containsKey(sum)){
record.put(sum,record.get(sum)+1);
}
//if this is a new combination, make the value as 1
else{
record.put(sum,1);
}
}
}
//traverse and calculate all combinations of Array C and D, if the number that (0- sum(arrayA[i]+arrayB[j]) in the map(it means the sum of the whole ocmbination is 0), then make the result add the all times the combination appeared
for(int i:nums3){
for(int j:nums4){
if(record.containsKey(0-i-j)){
count += record.get((0-i-j));
}
}
}
return count;
}
}
Time Complexity: O(n^2)
7. Ransom Note
leetcode: https://leetcode.com/problems/ransom-note/
Description:
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
Idea:
solution
Step1:create the array with the size is 26(all letters), use it to record all elements and corresponding number of their Occurrence
Step2: record the magzine firstly and record the number with increase, record the ransomNote secondly and record hte number with decrease.
Step3: becasue the elements of ransomNote should be included in the magazine, so if the number of same element’s<0, means there exists difference.
Code:
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
//because 26 letters,so create array(26) to record the number of times that each letter appeared
int[] result = new int[26];
//record all element and coressponding times by increasing
for(char x:magazine.toCharArray()){
result[x-'a'] +=1;
}
//record all element of ransomNote and coressponding times by decreasing
for(char x:ransomNote.toCharArray()){
result[x-'a'] -=1;
}
//becasue the elements of ransomNote should be included in the magazine, so if the number of same element's<0, means there exists difference
for(int i:result){
if(i<0){
return false;
}
}
return true;
}
}
8. 3Sum
leetcode: https://leetcode.com/problems/3sum/
Description:
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets
Idea:
**solution:two poiners **
Step1: sort the array(to the verify the sum), and create the array list
Step2: use first index to traverse the nums, because this nums array has been sorted, if current element it pointed bigger than 0, it means another two element will >0, the sum of theme can’t meet the requirement, return the current result. At the same time, if this element is equal to it’s next element, we skip next element to avoid the repeated combiantion in the result.
Step3: to set two pointers to get the bound of another two elements. Because the array is sorted, so if the sum >0, we need to move the right index to it’s previous poisiton to make the sum smaller. if sum< 0 , then move the left pointer to the next.
Step4: if the sum =0, record this combination, and use while loop to skip the continous same element of the left and right side to avoid repeated combinations in the result. Then, narrowing the bound to search next combination.
Code:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//sort the array, so more easier to adjust the index range by verifing the sum
Arrays.sort(nums);
//create list to store result array
List<List<Integer>> result = new ArrayList<>();
//use the first index to traverse array
for(int i=0; i<nums.length; i++){
//because the array ahs been sorted, and the sum should be 0, if the current element and next element both >0, it can't meet the quirement
if(nums[i]>0){
return result;
}
//avoid repeated result
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
//set two pointer to get all possible combination
int l_index=i+1;
int r_index = nums.length-1;
while(l_index < r_index){
int sum = nums[i] + nums[l_index] + nums[r_index];
//sum>0
if(sum>0){
r_index--;
}
//sum<0
else if(sum<0){
l_index++;
}
//sum ==0
else{
//add current combination array to list
result.add(Arrays.asList(nums[i], nums[l_index], nums[r_index]));
//avoid repeated result(if current index meet the rquirement, and next element is same, skip it)
while(l_index<r_index && nums[l_index] == nums[l_index+1]){
l_index++;
}
while(l_index<r_index && nums[r_index] == nums[r_index-1]){
r_index--;
}
//remove left and right index to adjust the range
l_index++;
r_index--;
}
}
}
return result;
}
}
9. 4Sum
leetcode: https://leetcode.com/problems/4sum/
Description:
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < na,b,c, anddare distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Idea:
**solution:two poiners **
Step1: sort the array(to the verify the sum), and create the array list
Step2: use first index and second index to traverse the nums, because this nums array has been sorted, if current element it pointed bigger than 0, it means another two element will >0, the sum of theme can’t meet the requirement, return the current result. At the same time, if this element is equal to it’s next element, we skip next element to avoid the repeated combiantion in the result.
Step3: to set two pointers to get the bound of another two elements. Because the array is sorted, so if the sum >0, we need to move the right index to it’s previous poisiton to make the sum smaller. if sum< 0 , then move the left pointer to the next.
Step4: if the sum =0, record this combination, and use while loop to skip the continous same element of the left and right side to avoid repeated combinations in the result. Then, narrowing the bound to search next combination.
Code:
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
//sort the array, so more easier to adjust the index range by verifing the sum
Arrays.sort(nums);
//create list to store result array
List<List<Integer>> result = new ArrayList<>();
//use the first index to traverse array
for(int i=0; i<nums.length; i++){
//avoid repeated result
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for(int j= i+1; j<nums.length; j++){
if (j>i+1 && nums[j] == nums[j - 1]) {
continue;
}
//set two pointer to get all possible combination
int l_index=j+1;
int r_index = nums.length-1;
while(l_index < r_index){
// because the number is 10^9, use long data type, make varibale * 1L to use the variable as long type
long sum = nums[i]*1l + nums[j] + nums[l_index] + nums[r_index];
//sum>target
if(sum>target){
r_index--;
}
//sum<target
else if(sum<target){
l_index++;
}
//sum ==target
else{
//add current combination array to list
result.add(Arrays.asList(nums[i], nums[j],nums[l_index], nums[r_index]));
//avoid repeated result(if current index meet the rquirement, and next element is same, skip it)
while(l_index<r_index && nums[l_index] == nums[l_index+1]){
l_index++;
}
while(l_index<r_index && nums[r_index] == nums[r_index-1]){
r_index--;
}
//remove left and right index to adjust the range
l_index++;
r_index--;
}
}
}
}
return result;
}
}
sum of more elements: can also use this method, and add loop to it
Linked List
-
Basic of Linkedlist
1. Type of Linked List
(1) Singly linked lists
Linkedlist has two part, one part for data, the other one is used to store the pointer of next node. no next node for the last node, so the pointer stored in the last node is null.
(2)Doubly linked list
doubly linked list has two pointer domain, the first one point to the previous node, and the second point to the next node. So it can search forward and backward
(3) Circular linked list
circular linked is the linkedlist is a circule, the last node’s pointer point to the first node
2. The store of linked list
The nodes in the linked list are not continuously distributed in the memory, but scattered at a certain address in the memory. The allocation mechanism depends on the memory management of the operating system.
3.Construction of List
public class ListNode {
//field
// the value of node
int val;
// the next node
ListNode next;
// the constructor of list(no argument)
public ListNode() {
}
// the constructor of list(one argument)
public ListNode(int val) {
this.val = val;
}
// the constructor of list(two argument)
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
4. Operation of linked list
4.1 delete
set pointer of the previous node of the delete node skip the delete node and point to the next node. because java have it’s garbage collection system.
if the delete node is head, then move the head index to next element; head=head.next
(1) add dummy node, so the we don’t need to change head node
ListNode dummy = new ListNode(-1,head)
//make the dummy node's pointer point to the original head node
(2)make head node point to the next element. head=head.next
while (head != null && head.val == val) {
head = head.next;
}
4.2 insert node
find the insert node’s poisition and set pointer of the previous node of it point to the insert node, and make the pointer of the insert node points to the original next node.
5.Method
//length
list.size();
//get the element with index
list.get(index);
//remove the element
list.remove(element);
//return the boolean value that is the element in the list or not
list.contains();
2.Remove Linked List Elements
leetcode: https://leetcode.com/problems/remove-linked-list-elements/
Description:
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
Idea:
**solution 1: move head node **
Step1: if the head node is target node, then delete it by removing head to it’s next unit the new head node isn’t the target
Step2: create temporary index to traverse the list when the current node isn’t null and the next node of current node isn’t null. if one element is the target, then make the current index point to the next next node.
Code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
//if the list is null
if(head == null){
return head;
}
//when the head is target, make the next node as head.
while(head != null && head.val == val){
head = head.next;
}
//set the index to traverse the list
ListNode current = head;
while(current != null){
//when the next node isn't null, and this node is targe，make current node point to next next node
while(current.next != null && current.next.val == val){
current.next =current.next.next;
}
//if the current's next node isn't target, move it to the next
current =current.next;
}
return head;
}
}
Solution 2: Use Dummy Node
Step1: create a new node, and make the next node of it point to the original head node.
Step2: because now the head is new virtual node, so we don’t need to consider the head node again.
Step3; set the current node start from the head node, just search the list, if the element’s val == target, then make the current node point to next next node.
Code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
//if the list is null
if(head == null){
return head;
}
//set the dummy node and make it as new head by making it point to original node
ListNode dummy = new ListNode(-1, head);
//set the index to traverse the list
ListNode current = dummy;
while(current != null){
//when the next node isn't null, and this node is targe，make current node point to next next node
while(current.next != null && current.next.val == val){
current.next =current.next.next;
}
//if the current's next node isn't target, move it to the next
current =current.next;
}
//dummy's next node is real list
return dummy.next;
}
}
3. Design Linked List
leetcode: https://leetcode.com/problems/design-linked-list/
Description:
Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.
Implement the MyLinkedList class:
MyLinkedList()Initializes theMyLinkedListobject.int get(int index)Get the value of theindexthnode in the linked list. If the index is invalid, return-1.void addAtHead(int val)Add a node of valuevalbefore the first element of the linked list. After the insertion, the new node will be the first node of the linked list.void addAtTail(int val)Append a node of valuevalas the last element of the linked list.void addAtIndex(int index, int val)Add a node of valuevalbefore theindexthnode in the linked list. Ifindexequals the length of the linked list, the node will be appended to the end of the linked list. Ifindexis greater than the length, the node will not be inserted.void deleteAtIndex(int index)Delete theindexthnode in the linked list, if the index is valid.
Idea:
**solution **
Step1: create the class of ListNode, include field and constructors
Step2: define the field and define the size of list and make the first node is dummy node in the MyLinkedList.
Step3: in the get method, if the target index <0 or the index >=the size of the list, it means the target index isn’t in the list. create the current index and start from the dummy node, travser unitl make the current node move to the target node, because the head is dummy node, so make the loop end until the target index
Step4: in the addAtHead method, set the index from the dummy node to traverse the list, then set newnode point to the original head node firstly, because if make dummy node point to newnode firstly, then the new node can’t point to original head node.
Step5: in the addAtTail method, traverse the list, until the current element’s next node is null, then add the new node.
Step6: in the addAtIndex method, because it starts from dummy node, so the index > size, it can’t add element, but when it equal to the size, it can add the new element by making the last node point to new node.
when need add the element, we need to make the current index move to the previous node of targe.make the new node point to the original next node firstly in case it cna’t find the next node
Step7: In the deleteAtIndex method, when it equal to size , there is no next target element to delete.when need delete the element, we need to make the current index move to the previous node of target
Code:
class ListNode {
int val;
ListNode next;
ListNode(){}
ListNode(int val) {
this.val=val;
}
ListNode(int val, ListNode next) {
this.val = val; this.next = next;
}
}
class MyLinkedList {
int size;
ListNode dummy;
public MyLinkedList() {
size = 0;
//set the listnode and include the dummy node
dummy = new ListNode(0);
}
public int get(int index) {
//if index <0 or the index >=the size of the list
if (index < 0 || index >= size) {
return -1;
}
//set the index to traverse the list
ListNode current = dummy;
//travser unitl make the current node move to the target node, because the head is dummy node, so make the loop end until the target index
while(index>=0){
current = current.next;
index--;
}
return current.val;
}
public void addAtHead(int val) {
//we set the dummy node as virtual head in the field
//set the index to traverse the list
ListNode current = dummy;
ListNode newnode = new ListNode(val);
//set newnode point to the original head node firstly//because if make dummy node point to newnode firstly, then the new node can't point to original head node
newnode.next = current.next;
current.next = newnode;
size++;
}
public void addAtTail(int val) {
//set the index to traverse the list
ListNode current = dummy;
ListNode newnode = new ListNode(val);
//get the last node's poisition
while(current.next != null){
current = current.next;
}
//make the last node point to the new node, and new node will point to null.
current.next = newnode;
size++;
}
public void addAtIndex(int index, int val) {
//because it starts from dummy node, so the index > size, it can't add element, but when it equal to the size, it can add the new element by making the last node point to new node
if(index < 0 || index > size){
return;
}
ListNode newnode = new ListNode(val);
//set the index to traverse the list
ListNode current = dummy;
//when need add the element, we need to make the current index move to the previous node of target
while(index>0){
current = current.next;
index--;
}
//make the new node point to the original next node firstly in case it cna't find the next node
newnode.next = current.next;
current.next = newnode;
size++;
}
public void deleteAtIndex(int index) {
// when it equal to size , there is no next target element to delete
if(index < 0 || index >= size){
return;
}
//set the index to traverse the list
//when need delete the element, we need to make the current index move to the previous node of target
ListNode current = dummy;
while(index > 0){
current = current.next;
index--;
}
current.next = current.next.next;
size--;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
4. Reverse Linked List
leetcode: https://leetcode.com/problems/reverse-linked-list/
Description:
Given the head of a singly linked list, reverse the list, and return the reversed list.
Idea:
**solution **
Step1: set three index, the first one is used to traverse the list and the second one is used to record result, the third one is used to store the next node in the loop as temporary node.
Step2: when the node of traversal is not null, use the temporary node to store the next node of current node(so that can continue traverse). make the next node of current node points to the previous node, so that reverse the side of linked list.
make the previous node point to current node to record result. make the current node point to temporary node to continue traversal.
Code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
//set the index to traverse;
ListNode current = head;
//set the previous node to record result
ListNode previous = null;
//set the temp node to store the original next node
ListNode temp = null;
//until the end
while(current != null){
//temp to record the next node in the loop
temp = current.next;
//reverse the side of node
current.next = previous;
previous = current;
//make the index point to temp to continue traverse
current = temp;
}
return previous;
}
}
5. Swap Nodes in Pairs
leetcode: https://leetcode.com/problems/swap-nodes-in-pairs/
Description:
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)
Idea:
**solution **
Step1: set the dummy node, and set the current node = dummy, to traverse the list
Step2: assume the head as the first node.
Step3: set the temp node, and make it point to head.next.next node. because we need to store this node so that we can link the first node of two nodes(need to be swapped) to this node after the swap.
Step3: make current node point to the head.next(the second node of two nodes), then make the head.next.next to head(now, head.next is second node, so head.next.next need to point to the first node) to complete swap. then make head.next(after swap, the first node’s next node) point to temp to keep link after swap
Step4: make current to head and move head to next to continue traversal.
Step5: return dummy.next(the real list is after dummy node)
Code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode dummy = new ListNode(0,head);
ListNode current = dummy;
ListNode temp;
while(current.next!=null && current.next.next != null ){
//set temporart node = head.next.next, so that we can know and link to the next node after swap two nodes
temp = head.next.next;
//Point the next node of the current node to the second node of the two nodes that need to be swapped
current.next = head.next;
//swap two nodes
head.next.next = head;
//after swap, link the fisrt node of two nodes that need to be swapped to the next node.
head.next = temp;
//move the current node to traverse
current = head;
//move the head to traverse;
head = head.next;
}
//get the real list
return dummy.next;
}
}
6. Remove Nth Node From End of List
leetcode: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
Description:
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Idea:
**solution **
Step1: set the dummy node, and set two pointer, fast pointer is used to traverse and control the range(because it’s the nth node from end), slow pointer is used to point target
Step2: because the nth node from the end, First move the fast pointer to the corresponding position, and then start to move the slow pointer, so that when the fast pointer moves to null, the slow pointer will point to the target
Step3: set the previous node, and in the loop, make it equal to slow pointer firstly, then make slow node move to next node, so the previous node will be the previous node of target
Step4: skip the target node, and make previous node’s next node equal to target node’s next node
Step5: return real list(dummy.next)
Code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//set two pointer, fast pointer is used to traverse and control the range(because it's the nth node from end), slow pointer is used to point target
ListNode dummy = new ListNode(-1,head);
ListNode slow = dummy;
ListNode fast = dummy;
// because the nth node from the end, First move the fast pointer to the corresponding position, and then start to move the slow pointer, so that when the fast pointer moves to null, the slow pointer just points to the target
//move fast node to corresponding position
while(n-->0){
fast = fast.next;
}
//set the previous node to record the previous node of the target
ListNode previous = null;
//traverse the left list, when the fast is null, slow will be the target, and use previous to record the previous node of slow
while(fast!=null){
fast = fast.next;
previous = slow;
slow = slow.next;
}
//skip the target node
previous.next = slow.next;
return dummy.next;
}
}
7. Intersection of Two Linked Lists LCCI
leetcode: https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
Description:
Given two (singly) linked lists, determine if the two lists intersect. Return the inter secting node. Note that the intersection is defined based on reference, not value. That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.
Idea:
**solution **
Step1: create the hashset to record unique elements of one list
Step2: create index to traverse two list, in the first list, add all elements to set. in the loop of second list, check the node of list exists in the set or not, if exists return the node.
Step3: if no intersection, return null.
Code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//create index to traverse two list
ListNode a = headA;
ListNode b = headB;
//create the set to record node
Set<ListNode> record = new HashSet<>();
//add node to set
while(a != null){
record.add(a);
a = a.next;
}
//if the node in b exists in the set, it means there exists intersect
while(b != null){
if(record.contains(b)){
return b;
}
b = b.next;
}
return null;
}
}
8. Linked List Cycle II
leetcode: https://leetcode.com/problems/linked-list-cycle-ii/
Description:
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
Idea:
**solution **
Step1: create slow and fast pointers, make fast pointer move two elements each time, and slow pointer move one element each time
Step2: use loop until the fast pointer point to null, but if there is a cycle, the fast pointer never point to null. At the same time, the slow index and fast index will meet in the cycle.
Step3: when ensure there is a cycle, set two new index, one pointer start from the list, the other one start from the node they meet. when they meet again, the node is the entrance of cycle.
Code:
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
//set two pointer and make them start from the head
ListNode fast = head;
ListNode slow = head;
//use fast index to traverse until it points to null
while(fast != null && fast. next != null){
//fast move two elements firstly, then slow index move one element each time
fast = fast.next.next;
slow = slow.next;
//if they exists cycle, they will meet in the cycle
if(fast == slow){
//find the entrance node of the cycle.
//set two pointer,, one form the meet node, the other one from the start
ListNode index1 = slow;
ListNode index2 = head;
//when they meet, that's the entrance
while(index1 != index2){
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
Stack and Queue
1. Basic
The stack is Last In First Out(LIFO)
Queue is First in First out(FIFO)
1.1.Operation of Stack
//add the element in the stack
stack.push(x);
//remove the element in the stack
stack.pop(x);
//verify is the stack is empty
stack.isEmpty();
//returns the element at the top of the Stack else returns NULL if the Stack is empty.
stack.peek();//the element retrieved does not get deleted or removed from the Stack.
1.2 Operation of Queue
//add the element in the queue
queue.offer(x);
//returns and removes the element at the front end of the container
queue.poll(x);
//verify is the queue is empty
queue.isEmpty();
//returns the element at the top of the queue else returns NULL if the queue is empty.
queue.peek();//the element retrieved does not get deleted or removed from the queue.
//return size
queue.size();
1.3 Deque
(1) It’s the linked list
(2) It supports insert and remove the element from two side of the queue.
Deque<Integer> deque = new LinkedList<>();
(3)operation
//get the first element
deque.peekFirst();
//get the last element
deque.peekLast();
//add the first element
deque.addFirst(e);
//add the last element
deque.addLast(e);
//remove first or last element
deque.removeFirst();
deque.removeLast();
1.4 Priority Queue
//create the priority queue
//use comparator to make internal elements are ascending, the first element is biggest
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
//descending
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
2.Implement Queue using Stacks
leetcode: https://leetcode.com/problems/implement-queue-using-stacks/
Description:
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
Idea:
**solution **
Step1: create two stack, one for in, one for out
Step2: push all elements to stack1, and then when pop element, add all stack1’s elements to stack2. It will change the Fisrt in Last out to First In First out, because stack pop the element from the top of the stack.
Step3: the same operations of peek method
Code:
class MyQueue {
//define two stack, one for in, the other for out
Stack<Integer> StackIn;
Stack<Integer> StackOut;
public MyQueue() {
//create two stack instance;
StackIn = new Stack<>();
StackOut = new Stack<>();
}
public void push(int x) {
//add elements into the Stack(IN)
StackIn.push(x);
}
public int pop() {
//extract elements from StackIN and add them to the StackOut to implement FIFO
if(StackOut.isEmpty()){
//extract all StackIn elements and put them to the outStack
while(!StackIn.isEmpty()){
StackOut.push(StackIn.pop());
}
}
return StackOut.pop();
}
public int peek() {
//get StackOut elements from StackIn
if(StackOut.isEmpty()){
while(!StackIn.isEmpty()){
StackOut.push(StackIn.pop());
}
}
return StackOut.peek();
}
//if two stack are both empty
public boolean empty() {
return StackIn.isEmpty() && StackOut.isEmpty() ;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
3.Implement Stack using Queues
leetcode: https://leetcode.com/problems/implement-stack-using-queues/
Description:
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
Idea:
**solution **
Step1: create the queue, when do the push operation, reverse the order of the elements in the queue so that it is in the same order as the stack.
Step2: do other operations directly, because the order has changed when adding elements.
Code:
class MyStack {
Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {
int size= queue.size()-1;
queue.offer(x);
//make the last in element, first out
//add all elements except the last add node, and push them to the back of the queue and remove them in the original poisition
while(size-->=0){
queue.offer(queue.poll());
}
}
//because the order of all elements have been changed when add, so do following operation directly.
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
4.Valid Parentheses
leetcode: https://leetcode.com/problems/valid-parentheses/
Description:
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Analysis:
Situation1: there are extra brackets in the left
Situation2: no extra brackets but the type of brackets inside isn’t matched
Situation3: there are extra brackets in the right
Idea:
**solution **
Step1: traverse the brackets and we only record the half of rackets into stack, and when they match the corresponding brackets in the string, then pop the element
Step2: Stack is FILO, so the top element is the corresponding bracket of the cloest element
Step3: there are 3 situations
Situation1: If the whole string has been traversed, but the stack isn’t empty, it means there are extra left brackets.
Situation2: when traverse is doing, but the stack is empty, it means there are extra right brackets.
Situation3: when traverse is doing, but the element in the stack can’t match element of the string, return false;
Code:
class Solution {
public boolean isValid(String s) {
//set the stack to record the corresponding brackets
Stack <Character> result = new Stack<>();
//traverse the string to get each bracket
for (int i=0; i<s.length(); i++){
//record the corresponding brackets
if(s.charAt(i) == '('){
result.push(')');
}
else if(s.charAt(i) == '['){
result.push(']');
}
else if(s.charAt(i) == '{'){
result.push('}');
}
//Stack is FILO, so the top element is the corresponding bracket of the cloest element
//if the element is not the left part of the bracket, then compare the current element with top element of stack.
else if(result.isEmpty() || result.peek() != s.charAt(i)){
return false;
}
// if match remove the corresponding racket in the stack
else{
result.pop();
}
}
//verify the stack is empty or not, if it's not empty it means there are extra brackets exists.
return result.isEmpty();
}
}
5.Remove All Adjacent Duplicates In String
leetcode: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/
Description:
You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.
We repeatedly make duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.
Idea:
**solution1 **
Step1: set the stack to record result
Step2: Stack is FILO, so if the top element is the equal to current element in the traversal, it means they are adjanct duplicates, pop the elment in the stack. otherwise, push this element to the stack.
Step3: because Stack is FILO, so we need to reverse elements in the stack. create a string to record reversed stack’s element.
Code:
class Solution {
public String removeDuplicates(String s) {
//create the stack to record the result
Stack<Character> result = new Stack<>();
//traverse the string
for(int i=0; i<s.length(); i++){
//if the current element isn't equal to the top element of the stack, add it to stack
if(result.isEmpty() || s.charAt(i) !=result.peek()){
result.push(s.charAt(i));
}
//if they are equal, we need to remove the elment in the stack
else{
result.pop();
}
}
//create the string and reverse element's order of the stack
String string1= "";
while(!result.isEmpty()){
string1 = result.pop() + string1;
}
return string1;
}
}
**solution2 **
Step1: set two pointer, the fast used to traverse the string, the slow one used to store the result
Step2: use fast index’s element to cover the slow’s index’s element. if the slow’s element = previous one, then it will back to previous, and because it will be cover next fast’index element, so it will remove two duplicates together.
Step3: get the substring and the index from 0 to the slow index.
Code:
class Solution {
public String removeDuplicates(String s) {
char[] result = s.toCharArray();
int slow = 0;
int fast = 0;
while(fast<result.length){
//use fast index's element to cover the slow's index's element.
result[slow] = result[fast];
//because it will be cover next fast'index element, so it will remove two duplicates together.
//if the slow's element = previous one, then it will back to previous
if(slow>0 && result[slow] == result[slow-1]){
slow--;
}
else{
slow++;
}
fast++;
}
//get the substring and the index from 0 to the slow index.
return new String(result,0,slow);
}
}
6.Evaluate Reverse Polish Notation
leetcode: https://leetcode.com/problems/evaluate-reverse-polish-notation/
Description:
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, and /. Each operand may be an integer or another expression.
Note that division between two integers should truncate toward zero.
It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.
Idea:
**solution **
Step1: set the stack to record result
Step2: when the element in the string isn’t operator, add them to stack, if the current element is operation, do the operation according to the operator
Step3: because the operation only take two cloest previous elements before the opeator, so use stack.pop() twice to get two elements and remove them at the same time, push the result of them to the stack.
Step4: when the operation is / or -, it means we need to get the correct order of elements. create two temporary variables to record the two previous elments separately. them use them do the operation and push the result to the stack.
Code:
class Solution {
public int evalRPN(String[] tokens) {
//use stack to record result
Stack<Integer> result = new Stack<>();
//traverse the string
for(int i=0; i<tokens.length; i++){
//because we need to get correct order of two elements, so use temporary variables to store them.
if(tokens[i].equals("/")){
int temp1 = result.pop();
int temp2 = result.pop();
result.push(temp2/temp1);
}
//pop two top elements to complete the operation and remove them.
else if(tokens[i].equals("+")){
result.push(result.pop()+result.pop());
}
//same situation as /
else if(tokens[i].equals("-")){
int temp1 = result.pop();
int temp2 = result.pop();
result.push(temp2-temp1);
}
//same situation like +
else if(tokens[i].equals("*")){
result.push(result.pop()*result.pop());
}
else{
//if the current element isn't operator, convert the string to int and add the element to the stack
result.push(Integer.valueOf(tokens[i]));
}
}
//get the result, only one element in the stack
return result.peek();
}
}
//convert the string data type to integer data type
Integer.valueOf(tokens[i]);
7.Sliding Window Maximum
leetcode: https://leetcode.com/problems/sliding-window-maximum/
Description:
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Idea:
**solution **
Step1: Set the Deque to record the maximum of each window, and create array to store them. this queue is a monotonic queue.
Step2: traverse the nums array
Step3: if the current element>=the last element of the queue, remove the last element(the queue will have new tail), until the queue is empty or the current element< the new tail of the queue. If the current element < the last element of the queue, add it to the tail.
Step4: Because add the smaller element to the tail, so the first element of the queue is biggest.
Step5: if the right bound larger than the window, return the first element of queue to the array(record the index of it).
Step6: If the index of first element < the left bound of window, it means it isn’t in the window, then remove it.
Code:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//create the array to record the maximum of each window
//n-k+1 is the nummber of windows in the nums array
int[] result = new int[nums.length-k+1];
//create the deque to record the compare the elements in the window
LinkedList<Integer> deque = new LinkedList<>();
//set left bound of the window
int left = 0;
//set the right bound of the window
for(int right=0; right<nums.length; right++){
//get the current element, when it larger than the tail element, remove tail until it < tail
//because the stack stores the index of element, so we need compare the nums[i], nums[index]
while(!deque.isEmpty() && nums[right] >= nums[deque.peekLast()]){
deque.removeLast();
}
//if current element < tail element, add them to the tail
deque.addLast(right);
//it means the right index move to the right bound of the window
if(right>=k-1){
//if the first element's index < left bound, it means it isn't in the window, remove the element
if(deque.peekFirst()<left){
deque.removeFirst();
}
//because add the element to the tail,so the first element in the stack is the maximum
result[left++] = nums[deque.getFirst()];
}
}
return result;
}
}
8.Top K Frequent Elements
leetcode: https://leetcode.com/problems/top-k-frequent-elements/
Description:
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Idea:
**solution **
**Step1: **First use hashmap to record each element and their corresponding frequency.
Step2: create the priority queue and use comparator to build the ascending queue.(the Max heap), so the first element of the queue is the biggest.
Step3: add all element’s and corrsponding frequency to the queue.
Step4: get kth elements of the queue from the first element.
Code:
class Solution {
public int[] topKFrequent(int[] nums, int k) {
int[] result = new int[k];
Map<Integer, Integer> map = new HashMap<>();
//use map to record the element and corresponding frequence
for(int i=0; i<nums.length; i++){
if(map.containsKey(nums[i])){
map.put(nums[i],map.get(nums[i])+1);
}else{
map.put(nums[i],1);
}
}
//max heap
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
//store elements to queue
for (int key : map.keySet())
queue.add(new int[]{key, map.get(key)});
//Take the largest k elements in the heap
int index=0;
//because the queue is ascending order, so just poll kth elements.
while(k-->0){
result[index++] = queue.poll()[0];
}
return result;
}
}
Binary Tree
Baisc of Binary Tree
1. Type of Binary Tree
1.1 Full Binary Tree
a tree in which every node other than the leaves has two children.
1.2 Complete Binary Tree
Except nodes is not full in the bottom layer, and all nodes should fill the left side firstly(it means left child must has node when the right child has node)
Example:
1.3 Binary Search Tree
In the binary search tree, each node has value, and left child always less than it’s parent node, and the right child always larger than it’s parent node.
1.4 Adelson-Velsky and Landis(AVL)
The properties：
(1) if the tree is empty, it meet the requirement
(2) the height difference of left sub tree and right sub tree should less than 1. |left.height-right.height|<=1
Example:
In the third tree, the left subtree’s height is 2, but the right substree is 0, then the difference is 2. so it isn’t AVL
Methods for storing binary trees
1.Node and Reference: explicit
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
2.Array: Implicit Binary Tree
Assume the root node’s index is 0, then if node has an index i, the left child’s index is 2i+1, the right child’s index is 2i+2, their parent’s index can be expressed as (i-1)/2
Tree Traversal
the traversal order is changed about parent node.
1.Inorder traversal
The Order of Inorder traversal is: left node -> parent node->right node
2.Preorder Traversal
The Order of Preorder traversal is: parent node -> left node->right node
3.Postorder Traversal
The Order of Postorder traversal is: left node->right node -> parent node
4.Deep First Search(DFS)
Preorder, Inorder, Postorder Traversal
(Recursion or iteration)
5. Breadth First Search(BFS)
Level Order Traversal (iteration)
Example:
Inorder: 5412678
Preorder:1425768
Postorder:1247865
Leetcode Problems
1. Binary Tree Preorder Traversal
leetcode: https://leetcode.com/problems/binary-tree-preorder-traversal/
Description:
Given the root of a binary tree, return the preorder traversal of its nodes’ values.
Idea:
the order of prerder is parent node- left node-right node(start from the root)
**Step1: **create the method and use recursion to traverse the whole tree.
**Step2: **add parent node firstly, then move the parent node to it’s left child,then in the recurison, when left subtree finished, make the node move to the right child and traverse the right substree.
Code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
//create the result list
List<Integer> result = new ArrayList<Integer>();
preorder(root,result);
return result;
}
public void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
//in the preorder, firstly add the parent node from the root.
result.add(root.val);
//then add the left child secondly, at the same time, in the recursion, we move the root to it's left child
preorder(root.left, result);
//then add the right child thirdly, at the same time, in the recursion, we move the root to it's left child
preorder(root.right, result);
}
}
2. Binary Tree Inorder Traversal
leetcode: https://leetcode.com/problems/binary-tree-inorder-traversal/
Description:
Given the root of a binary tree, return the inorder traversal of its nodes’ values.
Idea:
the order of prerder is left node->parent node->right node(start from the root’s left node)
**Step1: **create the method and use recursion to traverse the whole tree.
**Step2: **move the node to it’s left child and add it’s left child firstly unitl the left subtree finished, then add the parent node, then traverse the right child until the right subtree finished.
Code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
//create the result list
List<Integer> result = new ArrayList<Integer>();
inorder(root,result);
return result;
}
public void inorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
//in the inorder, firstly add the left child and start from the root's left child.
inorder(root.left, result);
//now root has move to the left child, add the value of root
result.add(root.val);
//then visit the right child of tree.
inorder(root.right, result);
}
}
3.Binary Tree Postorder Traversal
leetcode: https://leetcode.com/problems/binary-tree-postorder-traversal/submissions/
Description:
Given the root of a binary tree, return the postorder traversal of its nodes’ values.
Idea:
the order of prerder is left node->right node->parent node(start from the root’s left node)
**Step1: **create the method and use recursion to traverse the whole tree.
**Step2: **move the node to it’s left child and add it’s left child firstly unitl the left subtree finished, then then traverse the right child until the right subtree finished. Finally, add the parent node.
Code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
//create the result list
List<Integer> result = new ArrayList<Integer>();
postorder(root,result);
return result;
}
public void postorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
//in the inorder, firstly add the left child and start from the root's left child.
postorder(root.left, result);
//then visit the right child of tree.
postorder(root.right, result);
//visit the parent node finally.
result.add(root.val);
}
}
4.Binary Tree Level Order Traversal
leetcode: https://leetcode.com/problems/binary-tree-level-order-traversal/
Description:
Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
Idea:
use array list to store the result. use queue to record elements of each layer.
**Step1: ** if the node is null, add it to queue.
**Step2: ** create the list and record the size of the queue, pop all elements of the queue to the list firstly(get this layers’ elements). create a node to record each poped node of the queue. then verify this temporary node’s left and right child is equal to null or not, if the node has child, then add child to the queue.
Step3: store the list of this layer’e element to the array.
Code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//create list array to store the result
List<List<Integer>> result = new ArrayList<List<Integer>>();
//if root is null, the tree is empty
if(root == null){
return result;
}
//create the queue to record elements of each layer
Queue<TreeNode> queue = new LinkedList<TreeNode>();
//record the root
queue.offer(root);
//when the queue is empty, it means the last element has been visited
while(!queue.isEmpty()){
//create list to record the all elements of current layer
List<Integer> Lay_list = new ArrayList<Integer>();
//to record this layer's size
int size = queue.size();
//get each element of this layer, and add next layer's elements to the queue
for(int i=0; i<size; i++){
//use temporay node to record each node of this layer
TreeNode temp = queue.poll();
//get current layer's elements
Lay_list.add(temp.val);
//get next layer's elements through each node of current layer
if(temp.left!=null){
queue.offer(temp.left);
}
if(temp.right!=null){
queue.offer(temp.right);
}
}
//store the each layer to the result list
result.add(Lay_list);
}
return result;
}
}