# Bài tập CTDL-GT
## 1. [BT2](https://www.hackerrank.com/domains/java?filters%5Bsubdomains%5D%5B%5D=java-introduction)
### Bài 1: [Welcome to Java!](https://www.hackerrank.com/challenges/welcome-to-java/problem?isFullScreen=true)
```java
public class Solution {
public static void main(String[] args) {
System.out.println("Hello, World.");
System.out.println("Hello, Java.");
}
}
```
### Bài 2: [Java Stdin and Stdout I](https://www.hackerrank.com/challenges/java-stdin-and-stdout-1/problem)
```java
public class Solution {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int a = scan.nextInt();
int b = scan.nextInt();
int c = scan.nextInt();
System.out.println(a);
System.out.println(b);
System.out.println(c);
}
}
```
### Bài 3: [Java If-Else](https://www.hackerrank.com/challenges/java-if-else/problem)
```java
public class Solution {
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) {
int N = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
if(N % 2 != 0)
System.out.println("Weird");
else {
if(2 <= N && N <= 5) {
System.out.println("Not Weird");
}
else {
if(6 <= N && N <= 20) {
System.out.println("Weird");
}
else
System.out.println("Not Weird");
}
}
scanner.close();
}
}
```
### Bài 4: [Java Stdin and Stdout II](https://www.hackerrank.com/challenges/java-stdin-stdout/problem)
```java
public class Solution {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int i = scan.nextInt();
double d = scan.nextDouble();
String s = scan.nextLine();
s = scan.nextLine();
// Write your code here.
System.out.println("String: " + s);
System.out.println("Double: " + d);
System.out.println("Int: " + i);
}
}
```
### Bài 5: [Java Output Formatting](https://www.hackerrank.com/challenges/java-output-formatting/problem)
```java
public class Solution {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("================================");
for(int i=0;i<3;i++){
String s1=sc.next();
int x=sc.nextInt();
System.out.printf("%-15s%03d\n", s1, x);
}
sc.close();
System.out.println("================================");
}
}
```
### Bài 6: [Java Loops I](https://www.hackerrank.com/challenges/java-loops-i/problem)
```java
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bufferedReader.readLine().trim());
for(int i = 1; i <= 10; i++)
System.out.printf("%d x %d = %d\n", N, i, N * i);
bufferedReader.close();
}
}
```
### Bài 7: [Java Loops II](https://www.hackerrank.com/challenges/java-loops/problem)
```java
class Solution{
public static void main(String []argh){
Scanner in = new Scanner(System.in);
int t=in.nextInt();
for(int i=0;i<t;i++){
int a = in.nextInt();
int b = in.nextInt();
int n = in.nextInt();
int temp = 1;
for(int j = 1; j <= n; j++)
{
a += b * temp;
System.out.print(a + " ");
temp *= 2;
}
System.out.println();
}
in.close();
}
}
```
### Bài 8: [Java Datatypes](https://www.hackerrank.com/challenges/java-datatypes/problem)
```java
class Solution{
public static void main(String []argh)
{
Scanner sc = new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++)
{
try
{
long x=sc.nextLong();
System.out.println(x+" can be fitted in:");
if(x>=-128 && x<=127)System.out.println("* byte");
if(x>=Short.MIN_VALUE && x<=Short.MAX_VALUE)System.out.println("* short");
if(x>=Integer.MIN_VALUE && x<=Integer.MAX_VALUE)System.out.println("* int");
if(x>=Long.MIN_VALUE && x<=Long.MAX_VALUE)System.out.println("* long");
//Complete the code
}
catch(Exception e)
{
System.out.println(sc.next()+" can't be fitted anywhere.");
}
}
}
}
```
### Bài 9: [Java End-of-file](https://www.hackerrank.com/challenges/java-end-of-file/problem)
```java
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner sc = new Scanner(System.in);
int cnt = 0;
while(sc.hasNext())
{
++cnt;
String s = sc.nextLine();
System.out.println(cnt + " " + s);
}
}
}
```
### Bài 10: [Java Static Initializer Block](https://www.hackerrank.com/challenges/java-static-initializer-block/problem)
```java
public static Scanner sc = new Scanner(System.in);
public static int B;
public static int H;
public static boolean flag;
static {
B = sc.nextInt();
H = sc.nextInt();
try {
if(B > 0 && H > 0)
flag = true;
else
{
flag = false;
throw new Exception("Breadth and height must be positive");
}
}
catch(Exception e) {
System.out.println(e);
}
}
```
### Bài 11: [Java Int to String](hackerrank.com/challenges/java-int-to-string/problem)
```java
String s = "" + n;
```
### Bài 12: [Java Date and Time](https://www.hackerrank.com/challenges/java-date-and-time/problem)
```java
class Result {
public static String findDay(int month, int day, int year) {
Calendar cal = Calendar.getInstance();
cal.set(year, month - 1, day);
int dayOfWeek = cal.get(Calendar.DAY_OF_WEEK);
// return "" + dayOfWeek;
if(dayOfWeek == 1)
return "SUNDAY";
if(dayOfWeek == 2)
return "MONDAY";
if(dayOfWeek == 3)
return "TUESDAY";
if(dayOfWeek == 4)
return "WEDNESDAY";
if(dayOfWeek == 5)
return "THURSDAY";
if(dayOfWeek == 6)
return "FRIDAY";
return "SATURDAY";
}
}
```
### Bài 13: [Java Currency Formatter](https://www.hackerrank.com/challenges/java-currency-formatter/problem)
```java
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
double payment = scanner.nextDouble();
scanner.close();
// Write your code here.
NumberFormat f1 = NumberFormat.getCurrencyInstance(Locale.US);
NumberFormat f2 = NumberFormat.getCurrencyInstance(new Locale("en", "IN"));
NumberFormat f3 = NumberFormat.getCurrencyInstance(Locale.CHINA);
NumberFormat f4 = NumberFormat.getCurrencyInstance(Locale.FRANCE);
String us = f1.format(payment);
String india = f2.format(payment);
String china = f3.format(payment);
String france = f4.format(payment);
System.out.println("US: " + us);
System.out.println("India: " + india);
System.out.println("China: " + china);
System.out.println("France: " + france);
}
}
```
## 2. [BT3](https://www.hackerrank.com/domains/algorithms?filters%5Bsubdomains%5D%5B%5D=warmup)
### Bài 1: [Solve Me First](https://www.hackerrank.com/challenges/solve-me-first/problem)
```java
public class Solution {
static int solveMeFirst(int a, int b) {
// Hint: Type return a+b; below
return a + b;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a;
a = in.nextInt();
int b;
b = in.nextInt();
int sum;
sum = solveMeFirst(a, b);
System.out.println(sum);
}
}
```
### Bài 2: [Simple Array Sum](https://www.hackerrank.com/challenges/simple-array-sum/problem)
```java
public static int simpleArraySum(List<Integer> ar) {
int sum = 0;
for(int i = 0; i < ar.size(); i++)
sum += ar.get(i);
return sum;
}
```
### Bài 3: [Compare the Triplet](https://www.hackerrank.com/challenges/compare-the-triplets/problem)
```java
public static List<Integer> compareTriplets(List<Integer> a, List<Integer> b) {
int Alice = 0;
int Bob = 0;
for(int i = 0; i < 3; i++)
{
int f1 = a.get(i);
int f2 = b.get(i);
if(f1 > f2)
Alice++;
else if(f1 < f2)
Bob++;
}
List<Integer> ans = new ArrayList<>();
ans.add(Alice);
ans.add(Bob);
return ans;
}
}
```
### Bài 4: [A Very Big Sum](https://www.hackerrank.com/challenges/a-very-big-sum/problem)
```java
public static long aVeryBigSum(List<Long> ar) {
long ans = 0;
for(int i = 0; i < ar.size(); i++)
ans += ar.get(i);
return ans;
}
```
### Bài 5: [Diagonal Difference](https://www.hackerrank.com/challenges/diagonal-difference/problem)
```java
public static int diagonalDifference(List<List<Integer>> arr) {
// Write your code here
int f1 = 0;
int f2 = 0;
int n = arr.size();
for(int i = 0; i < n; i++) {
f1 += arr.get(i).get(i);
f2 += arr.get(i).get(n - i - 1);
}
return Math.abs(f1 - f2);
}
```
### Bài 6: [Plus Minus](https://www.hackerrank.com/challenges/plus-minus/problem)
```java
public static void plusMinus(List<Integer> arr) {
// Write your code here
int positive = 0;
int negative = 0;
int zero = 0;
int n = arr.size();
for(int i = 0; i < n; i++)
{
int temp = arr.get(i);
if(temp > 0)
positive++;
else if(temp == 0)
zero++;
else
negative++;
}
double raPos = (double) positive / n;
double raNeg = (double) negative / n;
double raZe = (double) zero / n;
System.out.printf("%.6f\n%.6f\n%.6f", raPos, raNeg, raZe);
}
```
### Bài 7: [Staircase](https://www.hackerrank.com/challenges/staircase/problem)
```java
public static void staircase(int n) {
String ans = "";
String temp = "" + n;
temp += "s\n";
temp = "%" + temp;
for(int i = 1; i <= n; i++) {
ans += "#";
System.out.printf(temp, ans);
}
}
```
### Bài 8: [Mini-Max Sum](https://www.hackerrank.com/challenges/mini-max-sum/problem)
```java
public static void miniMaxSum(List<Integer> arr) {
// Write your code here
Collections.sort(arr);
long sum = 0;
for(int x : arr)
sum += x;
System.out.printf("%d %d", sum - arr.get(arr.size() - 1), sum - arr.get(0));
}
```
### Bài 9: [Birthday Cake Candles](https://www.hackerrank.com/challenges/birthday-cake-candles/problem)
```java
public static int birthdayCakeCandles(List<Integer> candles) {
int cnt = 0;
int max = 0;
for(int x : candles)
if(x > max) {
max = x;
cnt = 1;
}
else if(x == max)
++cnt;
return cnt;
}
```
### Bài 10: [Time Conversion](https://www.hackerrank.com/challenges/time-conversion/problem)
```java
public static String timeConversion(String s) {
int hour = Integer.valueOf(s.substring(0, 2));
if (s.contains("AM")) {
if (hour == 12) {
hour = 0;
}
} else {
if (hour != 12) {
hour += 12;
}
}
return String.format("%02d%s", hour, s.substring(2, s.length() - 2));
}
```
## 3. [BT4](https://docs.google.com/document/d/1RgwRO_6J3RXtw3Zj4mIfEAJ3Q2HorNfQ3qx6_ge5tgs/edit)
### Bài 2: [Array - DS](https://www.hackerrank.com/challenges/arrays-ds)
```java
public static List<Integer> reverseArray(List<Integer> a) {
List<Integer> b = new ArrayList<>();
for(int i = (int) a.size() - 1; i >= 0; i--) {
b.add(a.get(i));
}
return b;
}
```
### Bài 3: [2D Array - DS](https://www.hackerrank.com/challenges/2d-array)
```java
public static int hourglassSum(List<List<Integer>> arr) {
int[][] a = new int[6][6];
for(int i = 0; i < 6; i++)
for(int j = 0;j < 6; j++)
a[i][j] = arr.get(i).get(j);
int maxx = Integer.MIN_VALUE;
for(int i = 0; i <= 3; i++)
for(int j = 0; j <= 3; j++){
int sum = a[i][j] + a[i][j + 1] + a[i][j + 2] +
a[i + 1][j + 1] + a[i + 2][j] + a[i + 2][j + 1] + a[i + 2][j + 2];
if(maxx < sum)
maxx = sum;
}
return maxx;
}
```
### Bài 4: [Sherlock and Array](https://www.hackerrank.com/challenges/sherlock-and-array)
```java
public static String balancedSums(List<Integer> arr) {
int n = arr.size();
int[] f = new int[n + 1];
for(int i = 1; i <= n; i++)
f[i] = f[i - 1] + arr.get(i - 1);
for(int i = 1; i <= n ; i++)
if(f[i - 1] - f[0] == f[n] - f[i])
return "YES";
return "NO";
}
```
### Bài 5: [Closest Numbers](https://www.hackerrank.com/challenges/closest-numbers)
```java
public static List<Integer> closestNumbers(List<Integer> arr) {
Collections.sort(arr);
List<Integer> answer = new ArrayList<>();
int minn = Integer.MAX_VALUE;
for (int i = 1; i < arr.size(); i++) {
if (minn > arr.get(i) - arr.get(i - 1)) {
minn = arr.get(i) - arr.get(i - 1);
answer.removeAll(answer);
answer.add(arr.get(i - 1));
answer.add(arr.get(i));
} else if(minn == arr.get(i) - arr.get(i - 1)) {
answer.add(arr.get(i - 1));
answer.add(arr.get(i));
}
}
return answer;
}
```
### Bài 6: [Pairs](https://www.hackerrank.com/challenges/pairs)
```java
public static int pairs(int k, List<Integer> arr) {
int ans = 0;
HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
Collections.sort(arr);
mp.put(arr.get(0), 1);
for (int i = 1; i < arr.size(); i++) {
if (mp.get(arr.get(i) - k) != null) {
ans += mp.get(arr.get(i) - k);
}
if (mp.get(arr.get(i)) == null) {
mp.put(arr.get(i), 1);
} else {
mp.put(arr.get(i), mp.get(arr.get(i)) + 1);
}
}
return ans;
}
```
### Bài 7: ThreeSum
```java
import java.util.Arrays;
import java.util.Scanner;
public class Solution {
private static boolean containsDuplicates(long[] a) {
for (int i = 1; i < a.length; i++)
if (a[i] == a[i-1]) return true;
return false;
}
private static long count(long[] a) {
int n = a.length;
Arrays.sort(a);
if (containsDuplicates(a)) {
throw new IllegalArgumentException("array contains duplicate integers");
}
long count = 0;
for (int i = 0; i < n; i++) {
int k = n - 1;
for (int j = i + 1; j < n; j++) {
while (k >= 0 && a[k] > -(a[i] + a[j])) {
k--;
}
if(k < 0) {
break;
}
if (k > j && a[i] + a[j] == -a[k]) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
sc.close();
System.out.println(count(a));
}
}
```
## 4. [BT linked-list](https://docs.google.com/document/d/1uDeCCEFVt2tHRsqInU5MSh-YTb-cpNRWTuKBMhbYrdE/edit)
### Bài 1: [Print the Elements of a Linked List](https://www.hackerrank.com/challenges/print-the-elements-of-a-linked-list/problem)
```java
static void printLinkedList(SinglyLinkedListNode head) {
while (head.next != null) {
System.out.println(head.data);
head = head.next;
}
System.out.println(head.data);
}
```
### Bài 2: [Insert a Node at the Tail of a Linked List](https://www.hackerrank.com/challenges/insert-a-node-at-the-tail-of-a-linked-list/problem)
```java
static SinglyLinkedListNode insertNodeAtTail(SinglyLinkedListNode head, int data) {
if (head == null) {
head = new SinglyLinkedListNode(data);
} else {
SinglyLinkedListNode temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new SinglyLinkedListNode(data);
}
return head;
}
```
### Bài 3: [Insert a node at the head of a linked list](https://www.hackerrank.com/challenges/insert-a-node-at-the-head-of-a-linked-list/problem)
```java
static SinglyLinkedListNode insertNodeAtHead(SinglyLinkedListNode llist, int data) {
if (llist == null) {
llist = new SinglyLinkedListNode(data);
} else {
SinglyLinkedListNode tmp = new SinglyLinkedListNode(data);
tmp.next = llist;
llist = tmp;
}
return llist;
}
```
### Bài 4: [Insert a node at a specific position in a linked list](https://www.hackerrank.com/challenges/insert-a-node-at-a-specific-position-in-a-linked-list/problem)
```java
public static SinglyLinkedListNode insertNodeAtPosition(SinglyLinkedListNode llist, int data, int position) {
SinglyLinkedListNode head = llist;
for (int i = 0; i < position - 1; i++) {
head = head.next;
}
SinglyLinkedListNode tmp = head.next;
head.next = new SinglyLinkedListNode(data);
head.next.next = tmp;
return llist;
}
```
### Bài 5: [Delete a Node](https://www.hackerrank.com/challenges/delete-a-node-from-a-linked-list/problem)
```java
public static SinglyLinkedListNode deleteNode(SinglyLinkedListNode llist, int position) {
if (position == 0) {
return llist.next;
}
SinglyLinkedListNode temp = llist;
for (int i = 0; i < position - 1; i++) {
temp = temp.next;
}
SinglyLinkedListNode tmp = temp.next.next;
temp.next = new SinglyLinkedListNode(0);
temp.next = tmp;
return llist;
}
```
### Bài 6: [Print in Reverse](https://www.hackerrank.com/challenges/print-the-elements-of-a-linked-list-in-reverse/problem)
```java
public static void reversePrint(SinglyLinkedListNode llist) {
SinglyLinkedListNode tmp = llist;
List<Integer> ans = new ArrayList<Integer>();
while (tmp.next != null) {
ans.add(tmp.data);
tmp = tmp.next;
}
ans.add(tmp.data);
Collections.reverse(ans);
for (int i : ans) {
System.out.println(i);
}
}
```
### Bài 7: [Reverse a linked list](https://www.hackerrank.com/challenges/reverse-a-linked-list)
```java
public static SinglyLinkedListNode reverse(SinglyLinkedListNode llist) {
SinglyLinkedListNode tmp = llist;
List<Integer> ans = new ArrayList<Integer>();
while (tmp.next != null) {
ans.add(tmp.data);
tmp = tmp.next;
}
ans.add(tmp.data);
Collections.reverse(ans);
SinglyLinkedListNode res = llist;
for (int i : ans) {
res.data = i;
res = res.next;
}
return llist;
}
```
### Bài 8: [Compare two linked lists](https://www.hackerrank.com/challenges/compare-two-linked-lists/problem)
```java
static boolean compareLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
SinglyLinkedListNode tmp1 = head1, tmp2 = head2;
while (tmp1 != null && tmp2 != null) {
if (tmp1.data != tmp2.data) {
return false;
}
tmp1 = tmp1.next;
tmp2 = tmp2.next;
}
if (tmp1 != null || tmp2 != null) {
return false;
}
return true;
}
```
### Bài 9: [Merge two sorted linked lists](https://www.hackerrank.com/challenges/merge-two-sorted-linked-lists/problem)
```java
static SinglyLinkedListNode mergeLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
SinglyLinkedListNode tmp = new SinglyLinkedListNode(0);
SinglyLinkedListNode cur = tmp;
while (head1 != null && head2 != null) {
if (head1.data <= head2.data) {
if ( cur.data == 0) {
cur.data = head1.data;
} else {
cur.next = new SinglyLinkedListNode(head1.data);
cur = cur.next;
}
head1 = head1.next;
} else {
if (cur.data == 0) {
cur.data = head2.data;
} else {
cur.next = new SinglyLinkedListNode(head2.data);
cur = cur.next;
}
head2 = head2.next;
}
}
while (head1 != null) {
cur.next = new SinglyLinkedListNode(head1.data);
cur = cur.next;
head1 = head1.next;
}
while (head2 != null) {
cur.next = new SinglyLinkedListNode(head2.data);
cur = cur.next;
head2 = head2.next;
}
return tmp;
}
```
### Bài 10: [Get Node Value](https://www.hackerrank.com/challenges/get-the-value-of-the-node-at-a-specific-position-from-the-tail/problem)
```java
public static int getNode(SinglyLinkedListNode llist, int positionFromTail) {
// Write your code here
int cnt = 0;
SinglyLinkedListNode tmp = llist;
while (tmp != null) {
++cnt;
tmp = tmp.next;
}
tmp = llist;
cnt -= positionFromTail;
for (int i = 0; i < cnt - 1; i++) {
tmp = tmp.next;
}
return tmp.data;
}
```
## 5. [BT5](https://docs.google.com/document/d/1L6IC7R0TYiSZOYG2wXhCMah4WD4VSnSLdfLf1ilcvfs/edit)
### Bài 2: [Java List](https://www.hackerrank.com/challenges/java-list/problem)
```java
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
ArrayList<Integer> arr = new ArrayList<>();
for (int i = 1; i <= N; i++) {
int x = sc.nextInt();
arr.add(x);
}
int Q = sc.nextInt();
while (Q-- != 0) {
String s = sc.next();
if (s.equals("Insert")) {
int x = sc.nextInt();
int y = sc.nextInt();
arr.add(x, y);
} else {
int x = sc.nextInt();
arr.remove(x);
}
}
for (int x : arr) {
System.out.print(x + " ");
}
}
```
### Bài 3: [Java Arraylist](https://www.hackerrank.com/challenges/java-arraylist/problem)
```java
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
ArrayList< ArrayList <Integer> > arr = new ArrayList<>();
for (int i = 1; i <= N; i++) {
ArrayList<Integer> tmp = new ArrayList<>();
int d = sc.nextInt();
while (d-- != 0) {
int x = sc.nextInt();
tmp.add(x);
}
arr.add(tmp);
}
int q = sc.nextInt();
while (q-- != 0) {
int x = sc.nextInt();
int y = sc.nextInt();
x--;
y--;
if (x >= arr.size()) {
System.out.println("ERROR!");
continue ;
}
if (y >= arr.get(x).size()) {
System.out.println("ERROR!");
continue ;
}
System.out.println(arr.get(x).get(y));
}
}
```
### Bài 4: [Balanced Brackets](https://www.hackerrank.com/challenges/balanced-brackets)
```java
public static String isBalanced(String s) {
Stack <Character> st = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
st.push(s.charAt(i));
continue ;
}
if (st.empty()) {
return "NO";
}
if (st.peek() == '{' && s.charAt(i) != '}') {
return "NO";
}
if (st.peek() == '(' && s.charAt(i) != ')') {
return "NO";
}
if (st.peek() == '[' && s.charAt(i) != ']') {
return "NO";
}
st.pop();
}
if (!st.empty()) {
return "NO";
}
return "YES";
}
```
### Bài 5: [Equal Stacks](https://www.hackerrank.com/challenges/equal-stacks)
```java
public static int getSum(List<Integer> d) {
int sum = 0;
for (int x : d) {
sum += x;
}
return sum;
}
public static int getLastElement(List<Integer> d) {
int size = d.size();
return d.get(size - 1);
}
public static List<Integer> removeLastElement(List<Integer> d) {
int size = d.size();
d.remove(size - 1);
return d;
}
public static int equalStacks(List<Integer> h1, List<Integer> h2, List<Integer> h3) {
Collections.reverse(h1);
Collections.reverse(h2);
Collections.reverse(h3);
while (h1.size() != 0 && h2.size() != 0 && h3.size() != 0) {
int x = getSum(h1);
int y = getSum(h2);
int z = getSum(h3);
int minn = Math.min(x, Math.min(y, z));
while (x > minn) {
x -= getLastElement(h1);
h1 = removeLastElement(h1);
}
while (y > minn) {
y -= getLastElement(h2);
h2 = removeLastElement(h2);
}
while (z > minn) {
z -= getLastElement(h3);
h3 = removeLastElement(h3);
}
if (x == minn && y == minn & z == minn) {
return x;
}
}
return 0;
}
```
### Bài 6: [Simple Text Editor](https://www.hackerrank.com/challenges/simple-text-editor)
```java
import java.io.*;
import java.util.*;
public class Solution {
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
if (st.hasMoreTokens()) {
str = st.nextToken("\n");
} else {
str = br.readLine();
}
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
public static void main(String[] args) {
FastReader sc = new FastReader();
Stack<String> stack = new Stack<>();
String s = "";
int Q = sc.nextInt();
while (Q-- != 0) {
int query = sc.nextInt();
switch (query) {
case 1: {
stack.push(s);
String temp = sc.next();
s += temp;
break;
}
case 2: {
int n = s.length() - sc.nextInt();
stack.push(s);
s = s.substring(0, n);
break;
}
case 3: {
int k = sc.nextInt();
System.out.print(s.charAt(k - 1) + "\n");
break;
}
case 4: {
s = stack.pop();
break;
}
}
}
}
}
```
### Bài 7: [Queue Using Two Stacks](https://www.hackerrank.com/challenges/queue-using-two-stacks)
```java
public class Solution {
private static void move(Stack<Integer> src, Stack<Integer> des) {
while (!src.isEmpty()) {
des.push(src.pop());
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int query = sc.nextInt();
Stack<Integer> input = new Stack<>();
Stack<Integer> output = new Stack<>();
while (query-- > 0) {
int type = sc.nextInt();
if (type == 1) {
input.push(sc.nextInt());
continue;
}
if (output.isEmpty()) {
move(input, output);
}
if (type == 2) {
output.pop();
continue;
}
System.out.print(output.peek() + "\n");
}
sc.close();
}
}
```
## 6. [BT6](https://docs.google.com/document/d/1dkLn_S_Wd8qCnB_aoQHVef9Yciy1cdRXvIvRRHJuIQY/edit)
### Bài 2: [Intro to Tutorial Challenges](https://www.hackerrank.com/challenges/tutorial-intro)
```java
public static int introTutorial(int V, List<Integer> arr) {
int r = arr.size() - 1;
int l = 0;
while (l <= r) {
int mid = l + (r - l) / 2;
int k = arr.get(mid);
if (k == V) {
return mid;
}
if (k > V) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return -1;
}
```
### Bài 3: [Insertion Sort - Part 1](https://www.hackerrank.com/challenges/insertionsort1)
```java
public static void insertionSort1(int n, List<Integer> arr) {
for (int i = n - 2; i >= 0; i--) {
int a = arr.get(i);
int b = arr.get(i + 1);
if (a > b) {
arr.set(i + 1, a);
for (Integer p : arr) {
System.out.print(p + " ");
}
System.out.println();
arr.set(i, b);
}
}
for (Integer p : arr) {
System.out.print(p + " ");
}
}
```
### Bài 4: [Insertion Sort - Part 2](https://www.hackerrank.com/challenges/insertionsort2)
```java
public static void insertionSort2(int n, List<Integer> arr) {
for (int i = 1; i < n; i++) {
for (int j = i - 1; j >= 0; j--) {
int a = arr.get(j);
int b = arr.get(j + 1);
if (a > b) {
arr.set(j, b);
arr.set(j + 1, a);
}
}
for (int j = 0; j < n; j++) {
System.out.print(arr.get(j) + " ");
}
System.out.println();
}
}
```
### Bài 5: [Correctness Invariant](https://www.hackerrank.com/challenges/correctness-invariant)
```java
public class Solution {
public static void insertionSort(int[] A){
for (int i = 1; i < A.length; i++){
int value = A[i];
int j = i - 1;
while (j >= 0 && A[j] > value){
A[j + 1] = A[j];
A[j] = value;
j = j - 1;
}
}
printArray(A);
}
static void printArray(int[] ar) {
for (int n: ar){
System.out.print(n+" ");
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] ar = new int[n];
for (int i = 0; i < n; i++){
ar[i] = in.nextInt();
}
insertionSort(ar);
}
}
```
### Bài 6: [Counting Sort 1](https://www.hackerrank.com/challenges/countingsort1)
```java
public static List<Integer> countingSort(List<Integer> arr) {
int[] cnt = new int[100];
for (Integer p : arr) {
cnt[p]++;
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < 100; i++) {
ans.add(cnt[i]);
}
return ans;
}
```
### Bài 7:
Trong hai thuật toán sắp xếp Chọn (Insertion sort) và Chèn/Xen vào (Selection Sort), dữ liệu đầu vào không nên lưu trong LinkedList (danh sách liên kết). Bởi vì việc update trong LinkedList rất phức tạp.
## 7. [BT7](https://docs.google.com/document/d/1KndwwmFgUGY6Smj7b1L75YPX0sB2hgbWRWmqdRh5kXQ/edit)
### Bài 2: [Computing the GCD](https://www.hackerrank.com/challenges/functional-programming-warmups-in-recursion---gcd)
```java
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
while (b != 0) {
int c = a % b;
a = b;
b = c;
}
System.out.print(a);
}
```
### Bài 3: [Java Sort](https://www.hackerrank.com/challenges/java-sort)
```java
private static class StudentComparator implements Comparator<Student> {
@Override
public int compare(Student x, Student y) {
if (Double.compare(x.getCgpa(), y.getCgpa()) == 0) {
if (x.getFname().equals(y.getFname())) {
return Integer.compare(x.getId(), y.getId());
}
return x.getFname().compareTo(y.getFname());
}
return -Double.compare(x.getCgpa(), y.getCgpa());
}
}
```
### Bài 4: [Quicksort 1 - Partition](https://www.hackerrank.com/challenges/quicksort1)
```java
public static List<Integer> quickSort(List<Integer> arr) {
int pivot = arr.get(0);
List<Integer> right = new ArrayList<>();
List<Integer> ans = new ArrayList<>();
for (int i = 1; i < arr.size(); i++) {
if (arr.get(i) > pivot) {
right.add(arr.get(i));
} else {
ans.add(arr.get(i));
}
}
ans.add(pivot);
for (int x : right) {
ans.add(x);
}
return ans;
}
```
### Bài 5: [Quicksort In-Place](https://www.hackerrank.com/challenges/quicksort3)
```java
public class Solution {
public static void Quicksort(List<Integer> arr, int low, int high) {
if(low >= high)
return ;
int i = low;
for(int j = low; j < high; j++) {
if(arr.get(j) <= arr.get(high)) {
Collections.swap(arr, i, j);
i++;
}
}
Collections.swap(arr, i, high);
for(int x : arr)
System.out.print(x + " ");
System.out.println();
Quicksort(arr, low, i - 1);
Quicksort(arr, i + 1, high);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<Integer> arr = new ArrayList<>();
for(int i = 0; i < n; i++) {
int x = sc.nextInt();
arr.add(x);
}
Solution.Quicksort(arr, 0, arr.size() - 1);
}
}
```
### Bài 6: [Find the Median](https://www.hackerrank.com/challenges/find-the-median)
```java
class Result {
private static void shuffle(List<Integer> arr, int left, int right) {
Random rand = new Random();
for (int i = left; i <= right; i++) {
int pos = rand.nextInt(right - left + 1) + left;
int a = arr.get(i);
arr.set(i, arr.get(pos));
arr.set(pos, a);
}
}
public static int findMedian(List<Integer> arr, int median, int low, int high) {
shuffle(arr, low, high);
int patrition = arr.get(high);
if (median == 1 && arr.size() == 1) {
return patrition;
}
int i = low;
for (int j = low; j < high; j++) {
if (arr.get(j) <= patrition) {
Collections.swap(arr, i, j);
i++;
}
}
Collections.swap(arr, i, high);
int left = i - low + 1;
if (median > left) {
return findMedian(arr, median - left, i + 1, high);
}
if (median < left) {
return findMedian(arr, median, low, i - 1);
}
return patrition;
}
}
```
## 8. [BT8](https://docs.google.com/document/d/1UVgzgppsNKqBvgIuoZ0rryy9a7vwi8CnH_8osfYnDVk/edit)
### Bài 2: [Java String Reverse](https://www.hackerrank.com/challenges/java-string-reverse/problem)
```java
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String A = sc.next();
StringBuilder tmp = new StringBuilder();
tmp.append(A);
tmp.reverse();
String B = String.valueOf(tmp);
if (A.equals(B)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
sc.close();
}
```
### Bài 3: [Jesse and Cookies](https://www.hackerrank.com/challenges/jesse-and-cookies/problem)
```java
public static int cookies(int k, List<Integer> A) {
Queue<Integer> q = new PriorityQueue<>(A);
int cnt = 0;
while (q.size() >= 2 && q.peek() < k) {
int a = q.poll();
int b = q.poll();
cnt++;
q.add(a + 2 * b);
}
if (q.peek() < k) {
return -1;
}
return cnt;
}
```
### Bài 4: [Java Priority Queue](https://www.hackerrank.com/challenges/java-priority-queue/problem)
```java
class Student {
int id;
String name;
double cgpa;
public Student(int id, String name, double cgpa) {
this.id = id;
this.name = name;
this.cgpa = cgpa;
}
public int getId() {
return id;
}
public String getName() {
return name;
}
public double getCgpa() {
return cgpa;
}
}
class StudentComparator implements Comparator<Student> {
@Override
public int compare(Student x, Student y) {
int a = Double.compare(x.getCgpa(), y.getCgpa());
// System.err.println("Compare: " + x.getCgpa() + " " + y.getCgpa() + " " + a);
if (a == 0) {
int b = x.getName().compareTo(y.getName());
if (b == 0) {
return Integer.compare(x.getId(), y.getId());
}
return b;
}
return -a;
}
}
class Priorities {
public List<Student> getStudents(List<String> event) {
Comparator cmp = new StudentComparator();
Queue<Student> q = new PriorityQueue<>(10, cmp);
for (String p : event) {
StringTokenizer st = new StringTokenizer(p);
String type = st.nextToken();
if (type.equals("SERVED")) {
q.poll();
continue;
}
String name = st.nextToken();
double cgpa = Double.parseDouble(st.nextToken());
int id = Integer.parseInt(st.nextToken());
// System.err.println(id + " " + name + " " + cgpa);
q.add(new Student(id, name, cgpa));
}
List<Student> tmp = new ArrayList<>();
while(!q.isEmpty()) {
tmp.add(q.poll());
}
return tmp;
}
}
```
### Bài 5: [Counting Sort 2](https://www.hackerrank.com/challenges/countingsort2)
```java
public static List<Integer> countingSort(List<Integer> arr) {
int cnt[] = new int[100];
for (Integer p : arr) {
cnt[p]++;
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < 100; i++) {
while (cnt[i]-- > 0) {
ans.add(i);
}
}
return ans;
}
```
### Bài 6: [Find the Running Median](https://www.hackerrank.com/challenges/find-the-running-median)
```java
public static List<Double> runningMedian(List<Integer> a) {
int n = a.size();
Queue<Integer> max = new PriorityQueue<>(n / 2 + 1, Collections.reverseOrder());
Queue<Integer> min = new PriorityQueue<>(n / 2 + 1);
List<Double> ans = new ArrayList<>();
for (int i = 1; i <= n; i++) {
int x = a.get(i - 1);
if (!min.isEmpty() && x > min.peek()) {
min.add(x);
} else {
max.add(x);
}
while (max.size() - min.size() > 1) {
int k = max.poll();
min.add(k);
}
while (min.size() - max.size() >= 1) {
int k = min.poll();
max.add(k);
}
if (i % 2 == 0) {
ans.add((double) (max.peek() + min.peek()) / 2);
} else {
ans.add((double) max.peek());
}
}
return ans;
}
```
## 9. [BT9](https://docs.google.com/document/d/1Hbt-7VW7wEVPQVrkawt9fvdcciIyIFTot7dfV19sIP4/edit)
### Bài 2: [Java Map](https://www.hackerrank.com/challenges/phone-book)
```java
class Solution {
public static void main(String []args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();
Map<String, Integer> map = new HashMap<>();
for (int i=0;i<n;i++) {
String name = in.nextLine();
int phone = in.nextInt();
map.put(name, phone);
in.nextLine();
}
while (in.hasNext()) {
String s=in.nextLine();
if (map.containsKey(s)) {
System.out.println(s + "=" + map.get(s));
} else {
System.out.println("Not found");
}
}
}
}
```
### Bài 3: [Java HashSet](https://www.hackerrank.com/challenges/java-hashset)
```java
HashSet<String> hashSet = new HashSet<>();
for (int i = 0; i < t; i++) {
hashSet.add(pair_left[i] + " " + pair_right[i]);
System.out.println(hashSet.size());
}
```
### Bài 4: [Tree: Inorder Traversal](https://www.hackerrank.com/challenges/tree-inorder-traversal)
```java
public static void inOrder(Node root) {
if (root.left != null) {
inOrder(root.left);
}
System.out.print(root.data + " ");
if (root.right != null) {
inOrder(root.right);
}
}
```
### Bài 5: [Tree: Preorder Traversal](https://www.hackerrank.com/challenges/tree-preorder-traversal)
```java
public static void preOrder(Node root) {
System.out.print(root.data + " ");
if (root.left != null) {
preOrder(root.left);
}
if (root.right != null) {
preOrder(root.right);
}
}
```
### Bài 6: [Tree: Level Order Traversal](https://www.hackerrank.com/challenges/tree-level-order-traversal)
```java
public static void levelOrder(Node root) {
Queue<Node> pq = new LinkedList<>();
pq.add(root);
while (!pq.isEmpty()) {
Node p = pq.poll();
System.out.print(p.data + " ");
if (p.left != null) {
pq.add(p.left);
}
if (p.right != null) {
pq.add(p.right);
}
}
}
```
### Bài 7: [Closest Numbers](https://www.hackerrank.com/challenges/closest-numbers)
```java
static List<Integer> tmp = new ArrayList<>();
private static void mergeSort(List<Integer> arr, int low, int high) {
if (low >= high) {
return;
}
int mid = low + (high - low) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
tmp.clear();
int i = low;
int j = mid + 1;
while (i <= mid && j <= high) {
int a = arr.get(i);
int b = arr.get(j);
if (a <= b) {
tmp.add(a);
i++;
continue;
}
tmp.add(b);
j++;
}
while (i <= mid) {
tmp.add(arr.get(i++));
}
while (j <= high) {
tmp.add(arr.get(j++));
}
int pos = 0;
for (int k : tmp) {
arr.set(pos + low, k);
pos++;
}
}
public static List<Integer> closestNumbers(List<Integer> arr) {
mergeSort(arr, 0, arr.size() - 1);
List<Integer> answer = new ArrayList<>();
int minn = Integer.MAX_VALUE;
for (int i = 1; i < arr.size(); i++) {
if (minn > arr.get(i) - arr.get(i - 1)) {
minn = arr.get(i) - arr.get(i - 1);
answer.removeAll(answer);
answer.add(arr.get(i - 1));
answer.add(arr.get(i));
}
else if (minn == arr.get(i) - arr.get(i - 1)) {
answer.add(arr.get(i - 1));
answer.add(arr.get(i));
}
}
return answer;
}
```
## 10. [BT10](https://docs.google.com/document/d/1xHE6AQypBX5E16t6hjAJ4yxA5WGc9apgu1bholitmgI/edit)
### Bài 2: [Tree: Height of a Binary Tree](https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree)
```java
public static int height(Node root) {
int ans = 0;
if (root.left != null) {
ans = Math.max(ans, height(root.left) + 1);
}
if (root.right != null) {
ans = Math.max(ans, height(root.right) + 1);
}
return ans;
}
```
### Bài 3: [Binary Search Tree : Insertion](https://www.hackerrank.com/challenges/binary-search-tree-insertion)
```java
public static Node insert(Node root,int data) {
if (root == null) {
return new Node(data);
}
Node cur = root;
if (data < cur.data) {
cur.left = insert(cur.left, data);
} else {
cur.right = insert(cur.right, data);
}
return cur;
}
```
### Bài 4: [Binary Search Tree : Lowest Common Ancestor](https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor)
```java
private static List<Integer> findAncestor(Node root, int v) {
List<Integer> ancestor = new ArrayList<>();
Node p = root;
while (p.data != v) {
ancestor.add(p.data);
if(v < p.data) {
p = p.left;
} else {
p = p.right;
}
}
ancestor.add(v);
return ancestor;
}
public static Node lca(Node root, int v1, int v2) {
// Write your code here.
List<Integer> ancestor1 = findAncestor(root, v1);
List<Integer> ancestor2 = findAncestor(root, v2);
int length = Math.min(ancestor1.size(), ancestor2.size());
int LCA = root.data;
for (int i = length - 1; i >= 0; i--) {
int a = ancestor1.get(i);
int b = ancestor2.get(i);
if (a == b) {
LCA = a;
break;
}
}
return new Node(LCA);
}
```
### Bài 5: [Is This a Binary Search Tree?](https://www.hackerrank.com/challenges/is-binary-search-tree)
```java
List<Integer> list = new ArrayList();
void inOrder(Node root) {
if (root.left != null) {
inOrder(root.left);
}
list.add(root.data);
if (root.right != null) {
inOrder(root.right);
}
}
boolean checkBST(Node root) {
inOrder(root);
System.err.println(list);
for (int i = 1; i < list.size(); i++) {
if (list.get(i - 1) >= list.get(i)) {
return false;
}
}
return true;
}
```
### Bài 6: [Self Balancing Tree](https://www.hackerrank.com/challenges/self-balancing-tree)
```java
private static Node leftRotation(Node root) {
Node nRoot = root.right;
Node tmp = root;
tmp.right = nRoot.left;
nRoot.left = tmp;
return nRoot;
}
private static Node rightRotation(Node root) {
Node nRoot = root.left;
Node tmp = root;
tmp.left = nRoot.right;
nRoot.right = tmp;
return nRoot;
}
private static int getHeight(Node root) {
if (root == null) {
return -1;
}
return root.ht;
}
private static int setHeight(Node root) {
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
private static Node update(Node root) {
if (root == null) {
return root;
}
if (root.left != null) {
root.left.ht = setHeight(root.left);
}
if (root.right != null) {
root.right.ht = setHeight(root.right);
}
root.ht = setHeight(root);
return root;
}
static Node insert(Node root,int val)
{
if (root == null) {
root = new Node();
root.val = val;
root.ht = setHeight(root);
return root;
}
Node cur = root;
if (root.val > val) {
cur.left = insert(cur.left, val);
} else {
cur.right = insert(cur.right, val);
}
int balance = getHeight(cur.left) - getHeight(cur.right);
if (balance < -1) { //Right
if (getHeight(cur.right.left) > getHeight(cur.right.right)) { //Left
cur.right = rightRotation(cur.right);
update(cur.right);
}
cur = leftRotation(cur);
}
if (balance > 1) { //Left
if (getHeight(cur.left.right) > getHeight(cur.left.left)) {//Right
cur.left = leftRotation(cur.left);
update(cur.left);
}
cur = rightRotation(cur);
}
update(cur);
return cur;
}
```
## 11. [BT11](https://docs.google.com/document/d/1j5jlpHyo9YmT8oX9WWHI3KNeeZdkogY7O6-U5Xv46lc/edit)
### Bài 2:
[Page1](https://i.imgur.com/TJmYNaD.jpg)
[Page2](https://i.imgur.com/sR5WFht.jpg)
[Page3](https://i.imgur.com/1U5WquV.jpg)
[Page4](https://i.imgur.com/bosuXNu.jpg)
### Bài 3: Vẽ
### Bài 4: [Pairs](https://www.hackerrank.com/challenges/pairs)
```java
public static int pairs(int k, List<Integer> arr) {
int ans = 0;
HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
Collections.sort(arr);
mp.put(arr.get(0), 1);
for (int i = 1; i < arr.size(); i++) {
if (mp.get(arr.get(i) - k) != null) {
ans += mp.get(arr.get(i) - k);
}
if (mp.get(arr.get(i)) == null) {
mp.put(arr.get(i), 1);
} else {
mp.put(arr.get(i), mp.get(arr.get(i)) + 1);
}
}
return ans;
}
```
### Bài 5: [Mising Numbers](https://www.hackerrank.com/challenges/missing-numbers)
#### a. Hash Map: O($n \times \log$)
```java
public static List<Integer> missingNumbers(List<Integer> arr, List<Integer> brr) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int a : arr) {
if (!hashMap.containsKey(a)) {
hashMap.put(a, 1);
} else {
hashMap.put(a, hashMap.get(a) + 1);
}
}
List<Integer> ans = new ArrayList<>();
for(int b : brr) {
if(hashMap.get(b) == null || hashMap.get(b) == 0) {
ans.add(b);
hashMap.put(b, -1);
} else {
hashMap.put(b, hashMap.get(b) - 1);
}
}
Collections.sort(ans);
return ans;
}
```
#### b. Sorting: O($n \times \log(n)$)
```java
public static List<Integer> missingNumbers(List<Integer> arr, List<Integer> brr) {
// Write your code here
Collections.sort(arr);
Collections.sort(brr);
List<Integer> ans = new ArrayList<>();
int a = 0;
for (int b : brr) {
if (!ans.isEmpty() && ans.get(ans.size() - 1) == b) {
continue;
}
while(a < arr.size() && arr.get(a) < b) {
a++;
}
if(a == arr.size() || arr.get(a) != b) {
ans.add(b);
continue;
}
a++;
}
return ans;
}
```
#### c. Counting Sort: O($n$)
```java
public static List<Integer> missingNumbers(List<Integer> arr, List<Integer> brr) {
List<Integer> ans = new ArrayList<>();
int min = Collections.min(brr);
for (int i = 0; i < arr.size(); i++) {
arr.set(i, arr.get(i) - min);
}
for (int i = 0; i < brr.size(); i++) {
brr.set(i, brr.get(i) - min);
}
int cnt[] = new int[101];
for (int a : arr) {
if (a < 0 || a > 100) {
continue;
}
cnt[a]++;
}
boolean[] notHave = new boolean[101];
for (int b : brr) {
if (cnt[b] == 0) {
notHave[b] = true;
}
cnt[b]--;
}
for (int i = 0; i < 101; i++) {
if (notHave[i]) {
ans.add(i + min);
}
}
return ans;
}
```
### Bài 6: [Find the Running Median](https://www.hackerrank.com/challenges/find-the-running-median)
```java
class Pair implements Comparator<Pair>, Comparable<Pair> {
public int value;
public int pos;
public Pair(){
}
public Pair(int value, int pos) {
this.value = value;
this.pos = pos;
}
@Override
public int compare(Pair pair, Pair otherPair) {
int a = Integer.compare(pair.value, otherPair.value);
if (a == 0) {
return Integer.compare(pair.pos, otherPair.pos);
}
return a;
}
@Override
public int compareTo(Pair otherPair) {
return compare(this, otherPair);
}
}
class Result {
public static List<Double> runningMedian(List<Integer> a) {
Pair median = null;
TreeSet<Pair> treeSet = new TreeSet<>();
List<Double> ans = new ArrayList<>();
for (int i = 1; i <= a.size(); i++) {
int value = a.get(i - 1);
Pair pair = new Pair(value, i);
boolean toLeft = false;
if (median == null) {
median = pair;
} else {
toLeft = median.compareTo(pair) > 0;
}
treeSet.add(pair);
int size = treeSet.size();
if (size % 2 == 0) {
Pair cur = null;
if (toLeft) {
cur = treeSet.lower(median);
} else {
cur = median;
median = treeSet.higher(median);
}
ans.add(1.0 * (median.value + cur.value) / 2);
} else {
if (toLeft) {
median = treeSet.lower(median);
}
ans.add(1.0 * median.value);
}
}
return ans;
}
}
```
## 12. [BT12](https://docs.google.com/document/d/1i9zGreLuArwE_oTD0GggaoBBgvT4M7PION6DgEGL9dI/edit)
### Bài 1: [Connected Cells in a Grid](https://www.hackerrank.com/challenges/connected-cell-in-a-grid)
```java
class Result {
private static int encode(int row, int col, int width) {
return row * width + col;
}
private static int decodeRow(int code, int width) {
return code / width;
}
private static int decodeCol(int code, int width) {
return code % width;
}
private static int[][] value;
private static boolean[][] visit;
private static Queue<Integer> q = new LinkedList<>();
private static int[] dx = new int[] {-1, 0, 0, 1, -1, -1, 1, 1};
private static int[] dy = new int[] { 0, -1, 1, 0, 1, -1, 1, -1};
private static int BFS(int start, int height, int width) {
int size = height * width;
q.add(start);
int ans = 0;
while (!q.isEmpty()) {
int index = q.poll();
int row = decodeRow(index, width);
int col = decodeCol(index, width);
if (visit[row][col]) {
continue;
}
ans++;
visit[row][col] = true;
for (int k = 0; k < dx.length; k++) {
int nRow = row + dx[k];
int nCol = col + dy[k];
if (nRow < 0 || nRow >= height) {
continue;
}
if (nCol < 0 || nCol >= width) {
continue;
}
if (visit[nRow][nCol]) {
continue;
}
if (value[nRow][nCol] == 0) {
continue;
}
q.add(encode(nRow, nCol, width));
}
}
return ans;
}
public static int connectedCell(List<List<Integer>> matrix) {
int height = matrix.size();
int width = matrix.get(0).size();
visit = new boolean[height][width];
value = new int[height][width];
for (int row = 0; row < height; row++) {
for (int col = 0; col < width; col++) {
value[row][col] = matrix.get(row).get(col);
}
}
int ans = 0;
for (int row = 0; row < height; row++) {
for (int col = 0; col < width; col++) {
if (value[row][col] == 0) {
continue;
}
if (visit[row][col]) {
continue;
}
int index = encode(row, col, width);
ans = Math.max(ans, BFS(index, height, width));
}
}
return ans;
}
}
```
### Bài 2: [Breadth First Search: Shortest Reach](https://www.hackerrank.com/challenges/bfsshortreach)
```java
class Result {
public static List<Integer> bfs(int n, int m, List<List<Integer>> edges, int s) {
Integer[] f = new Integer[n];
List[] adj = new List[n];
for (int i = 0; i < n; i++) {
adj[i] = new ArrayList<Integer>();
}
for (List<Integer> p : edges) {
int u = p.get(0) - 1;
int v = p.get(1) - 1;
adj[u].add(v);
adj[v].add(u);
}
Arrays.fill(f, -1);
f[s - 1] = 0;
Queue<Integer> q = new LinkedList<>();
q.add(s - 1);
boolean[] inqueue = new boolean[n];
while (!q.isEmpty()) {
int u = q.poll();
inqueue[u] = false;
for (Object object : adj[u]) {
int v = (Integer) object;
if (f[v] == -1 || f[v] > f[u] + 6) {
f[v] = f[u] + 6;
if (!inqueue[v]) {
inqueue[v] = true;
q.add(v);
}
}
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (f[i] != 0) {
ans.add(f[i]);
}
}
return ans;
}
}
```
## 13. [BT13](https://docs.google.com/document/d/1OfgrTdhYsVXJMdyC9yCIWiBXZ6_-dYCuQYtSXSZPVlU/edit)
### Bài 1: Vẽ
[Page1](https://i.imgur.com/DLCHlXa.jpg)
[Page2](https://i.imgur.com/NID97YC.jpg)
[Page3](https://i.imgur.com/hLK4nzi.jpg)
### Bài 2: [Prim's (MST) : Special Subtree](https://www.hackerrank.com/challenges/primsmstsub/problem)
```java
class Cost implements Comparable<Cost> {
int cost;
int v;
public Cost() {
}
public Cost(int cost, int v) {
this.cost = cost;
this.v = v;
}
@Override
public int compareTo(Cost c) {
if (cost < c.cost) return -1;
if (cost > c.cost) return 1;
if (v < c.v) return -1;
if (v > c.v) return 1;
return 0;
}
}
class Result {
static PriorityQueue<Cost> pq = new PriorityQueue<>();
public static int prims(int n, List<List<Integer>> edges, int start) {
int[] f = new int[n];
Arrays.fill(f, -1);
f[start - 1] = 0;
int[][] weight = new int[n][n];
for(int i = 0; i < n; i++) {
Arrays.fill(weight[i], -1);
}
for(List<Integer> p : edges) {
int u = p.get(0) - 1;
int v = p.get(1) - 1;
int w = p.get(2);
if (weight[u][v] == -1 || weight[u][v] > w) {
weight[u][v] = w;
weight[v][u] = w;
}
}
int ans = 0;
pq.add(new Cost(0, start - 1));
while (!pq.isEmpty()) {
Cost cur = pq.poll();
int u = cur.v;
int cost = cur.cost;
if (f[u] != cost) {
continue;
}
ans += f[u];
f[u] = 0;
for (int v = 0; v < n; v++) {
if (weight[u][v] == -1) {
continue;
}
if (f[v] == -1 || f[v] > weight[u][v]) {
f[v] = weight[u][v];
pq.add(new Cost(f[v], v));
}
}
}
return ans;
}
}
```
### Bài 3: [Dijkstra: Shortest Reach 2](https://www.hackerrank.com/challenges/dijkstrashortreach/problem)
```java
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
class Cost implements Comparable<Cost> {
int cost;
int v;
public Cost() {
}
public Cost(int cost, int v) {
this.cost = cost;
this.v = v;
}
@Override
public int compareTo(Cost c) {
return Integer.compare(cost, c.cost);
}
}
class Result {
static PriorityQueue<Cost> pq = new PriorityQueue<>();
static List<Cost>[] adj;
public static List<Integer> shortestReach(int n, int s) {
int[] f = new int[n];
Arrays.fill(f, -1);
f[s - 1] = 0;
pq.clear();
for (int i = 0; i < n; i++) {
Collections.sort(adj[i]);
}
pq.add(new Cost(0, s - 1));
while (!pq.isEmpty()) {
Cost cur = pq.poll();
int u = cur.v;
int cost = cur.cost;
if (f[u] != cost) {
continue;
}
for (Cost c : adj[u]) {
int v = c.v;
int w = c.cost;
if (f[v] == -1 || f[v] > w + f[u]) {
f[v] = w + f[u];
pq.add(new Cost(f[v], v));
}
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (i + 1 != s) {
ans.add(f[i]);
}
}
return ans;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
int t = Integer.parseInt(st.nextToken());
for (int tItr = 0; tItr < t; tItr++) {
st = new StringTokenizer(bufferedReader.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
Result.adj = new List[n];
for(int i = 0; i < n; i++) {
Result.adj[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(bufferedReader.readLine());
int u = Integer.parseInt(st.nextToken()) - 1;
int v = Integer.parseInt(st.nextToken()) - 1;
int w = Integer.parseInt(st.nextToken());
Result.adj[u].add(new Cost(w, v));
Result.adj[v].add(new Cost(w, u));
}
int s = Integer.parseInt(bufferedReader.readLine().trim());
List<Integer> result = Result.shortestReach(n, s);
for (int i = 0; i < result.size(); i++) {
bufferedWriter.write(String.valueOf(result.get(i)));
if (i != result.size() - 1) {
bufferedWriter.write(" ");
}
}
bufferedWriter.newLine();
}
bufferedReader.close();
bufferedWriter.close();
}
}
```
### Bài 4: [Kruskal (MST): Really Special Subtree](https://www.hackerrank.com/challenges/kruskalmstrsub/problem)
```java
class Edge implements Comparable<Edge>{
public int u, v, w;
public Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(w, other.w);
}
}
class Result {
static int root(int u, int[] par) {
return (par[u] < 0) ? u : (par[u] = root(par[u], par));
}
static boolean merge(int u, int v, int[] par) {
if ((u = root(u, par)) == (v = root(v, par))) {
return false;
}
if (par[u] > par[v]) {
int temp = u;
u = v;
v = temp;
}
par[u] += par[v];
par[v] = u;
return true;
}
public static int kruskals(int gNodes, List<Integer> gFrom, List<Integer> gTo, List<Integer> gWeight) {
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < gFrom.size(); i++) {
int u = gFrom.get(i);
int v = gTo.get(i);
int w = gWeight.get(i);
edges.add(new Edge(u, v, w));
}
Collections.sort(edges);
int[] par = new int[gNodes + 1];
Arrays.fill(par, -1);
int ans = 0;
for (int i = 0; i < edges.size(); i++) {
int u = edges.get(i).u;
int v = edges.get(i).v;
int w = edges.get(i).w;
if (merge(u, v, par)) {
ans += w;
}
}
return ans;
}
}
```
Sign in with Wallet
Connect another wallet