Skip to content

Commit 69070b0

Browse files
krahetskrahets
committed
First commit.
0 parents  commit 69070b0

File tree

251 files changed

+8688
-0
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

251 files changed

+8688
-0
lines changed

‎README.md

Lines changed: 190 additions & 0 deletions
Large diffs are not rendered by default.

‎java/include/ListNode.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package include;
2+
3+
import java.util.List;
4+
5+
/**
6+
* Definition for a singly-linked list node.
7+
*/
8+
public class ListNode {
9+
public int val;
10+
public ListNode next;
11+
12+
public ListNode(int x) {
13+
val = x;
14+
}
15+
16+
public static ListNode arrToLinkedList(int[] arr) {
17+
ListNode dum = new ListNode(0);
18+
ListNode head = dum;
19+
for (int val : arr) {
20+
head.next = new ListNode(val);
21+
head = head.next;
22+
}
23+
return dum.next;
24+
}
25+
26+
public static ListNode getListNode(ListNode head, int val) {
27+
while (head != null && head.val != val) {
28+
head = head.next;
29+
}
30+
return head;
31+
}
32+
}

‎java/include/PrintUtil.java

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package include;
2+
3+
import java.util.*;
4+
5+
public class PrintUtil {
6+
// Print a linked list
7+
public static void printLinkedList(ListNode head) {
8+
List<String> list = new ArrayList<>();
9+
while (head != null) {
10+
list.add(String.valueOf(head.val));
11+
head = head.next;
12+
}
13+
System.out.println(String.join(" -> ", list));
14+
}
15+
16+
// Print a binary tree (90º counter-clockwise rotated)
17+
public static void printTree(TreeNode root) {
18+
printTreeHelper(root, 0);
19+
}
20+
21+
private static void printTreeHelper(TreeNode root, int level) {
22+
if (root == null)
23+
return;
24+
printTreeHelper(root.right, level + 1);
25+
System.out.println(" ".repeat(4 * level) + "->" + root.val);
26+
printTreeHelper(root.left, level + 1);
27+
}
28+
}

‎java/include/TreeNode.java

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package include;
2+
3+
import java.util.*;
4+
5+
/**
6+
* Definition for a binary tree node.
7+
*/
8+
public class TreeNode {
9+
public int val;
10+
public TreeNode left;
11+
public TreeNode right;
12+
13+
public TreeNode(int x) {
14+
val = x;
15+
}
16+
17+
public static TreeNode arrToTree(Integer[] arr) {
18+
TreeNode root = new TreeNode(arr[0]);
19+
Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
20+
int i = 1;
21+
while(!queue.isEmpty()) {
22+
TreeNode node = queue.poll();
23+
if(arr[i] != null) {
24+
node.left = new TreeNode(arr[i]);
25+
queue.add(node.left);
26+
}
27+
i++;
28+
if(arr[i] != null) {
29+
node.right = new TreeNode(arr[i]);
30+
queue.add(node.right);
31+
}
32+
i++;
33+
}
34+
return root;
35+
}
36+
37+
public static List<Integer> treeToList(TreeNode root) {
38+
List<Integer> list = new ArrayList<>();
39+
if(root == null) return list;
40+
Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
41+
while(!queue.isEmpty()) {
42+
TreeNode node = queue.poll();
43+
if(node != null) {
44+
list.add(node.val);
45+
queue.add(node.left);
46+
queue.add(node.right);
47+
}
48+
else {
49+
list.add(null);
50+
}
51+
}
52+
return list;
53+
}
54+
55+
public static TreeNode getTreeNode(TreeNode root, int val) {
56+
if (root == null)
57+
return null;
58+
if (root.val == val)
59+
return root;
60+
TreeNode left = getTreeNode(root.left, val);
61+
TreeNode right = getTreeNode(root.right, val);
62+
return left != null ? left : right;
63+
}
64+
}

‎java/sfo_03_find_duplicate_numbers_in_an_array_s1/sfo_03_find_duplicate_numbers_in_an_array_s1.java

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
/*
2+
* File: sfo_03_find_duplicate_numbers_in_an_array_s1.java
3+
* Created Time: 2021-12-09
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
package sfo_03_find_duplicate_numbers_in_an_array_s1;
8+
9+
import include.*;
10+
import java.util.*;
11+
12+
// ===== Solution Code =====
13+
class Solution {
14+
public int findRepeatNumber(int[] nums) {
15+
Set<Integer> dic = new HashSet<>();
16+
for(int num : nums) {
17+
if(dic.contains(num)) return num;
18+
dic.add(num);
19+
}
20+
return -1;
21+
}
22+
}
23+
24+
public class sfo_03_find_duplicate_numbers_in_an_array_s1 {
25+
public static void main(String[] args) {
26+
// ======= Test Case =======
27+
int[] nums = { 2, 3, 1, 0, 2, 5, 3 };
28+
// ====== Driver Code ======
29+
Solution slt = new Solution();
30+
int res = slt.findRepeatNumber(nums);
31+
System.out.println(res);
32+
}
33+
}

‎java/sfo_03_find_duplicate_numbers_in_an_array_s2/sfo_03_find_duplicate_numbers_in_an_array_s2.java

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
/*
2+
* File: sfo_03_find_duplicate_numbers_in_an_array_s2.java
3+
* Created Time: 2021-12-09
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
package sfo_03_find_duplicate_numbers_in_an_array_s2;
8+
9+
import include.*;
10+
import java.util.*;
11+
12+
// ===== Solution Code =====
13+
class Solution {
14+
public int findRepeatNumber(int[] nums) {
15+
int i = 0;
16+
while(i < nums.length) {
17+
if(nums[i] == i) {
18+
i++;
19+
continue;
20+
}
21+
if(nums[nums[i]] == nums[i]) return nums[i];
22+
int tmp = nums[i];
23+
nums[i] = nums[tmp];
24+
nums[tmp] = tmp;
25+
}
26+
return -1;
27+
}
28+
}
29+
30+
public class sfo_03_find_duplicate_numbers_in_an_array_s2 {
31+
public static void main(String[] args) {
32+
// ======= Test Case =======
33+
int[] nums = { 2, 3, 1, 0, 2, 5, 3 };
34+
// ====== Driver Code ======
35+
Solution slt = new Solution();
36+
int res = slt.findRepeatNumber(nums);
37+
System.out.println(res);
38+
}
39+
}

‎java/sfo_04_find_a_number_in_2d_matrix_s1/sfo_04_find_a_number_in_2d_matrix_s1.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
/*
2+
* File: sfo_04_find_a_number_in_2d_matrix_s1.java
3+
* Created Time: 2021-12-09
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
package sfo_04_find_a_number_in_2d_matrix_s1;
8+
9+
import include.*;
10+
import java.util.*;
11+
12+
// ===== Solution Code =====
13+
class Solution {
14+
public boolean findNumberIn2DArray(int[][] matrix, int target) {
15+
int i = matrix.length - 1, j = 0;
16+
while(i >= 0 && j < matrix[0].length)
17+
{
18+
if(matrix[i][j] > target) i--;
19+
else if(matrix[i][j] < target) j++;
20+
else return true;
21+
}
22+
return false;
23+
}
24+
}
25+
26+
public class sfo_04_find_a_number_in_2d_matrix_s1 {
27+
public static void main(String[] args) {
28+
// ======= Test Case =======
29+
int[][] matrix = {
30+
{ 1, 4, 7, 11, 15 },
31+
{ 2, 5, 8, 12, 19 },
32+
{ 3, 6, 9, 16, 22 },
33+
{ 10, 13, 14, 17, 24 },
34+
{ 18, 21, 23, 26, 30 }
35+
};
36+
int target = 5;
37+
// ====== Driver Code ======
38+
Solution slt = new Solution();
39+
boolean res = slt.findNumberIn2DArray(matrix, target);
40+
System.out.println(res);
41+
}
42+
}

‎java/sfo_05_replace_spaces_s1/sfo_05_replace_spaces_s1.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/*
2+
* File: sfo_05_replace_spaces_s1.java
3+
* Created Time: 2021-12-09
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
package sfo_05_replace_spaces_s1;
8+
9+
import include.*;
10+
import java.util.*;
11+
12+
// ===== Solution Code =====
13+
class Solution {
14+
public String replaceSpace(String s) {
15+
StringBuilder res = new StringBuilder();
16+
for(Character c : s.toCharArray())
17+
{
18+
if(c == ' ') res.append("%20");
19+
else res.append(c);
20+
}
21+
return res.toString();
22+
}
23+
}
24+
25+
public class sfo_05_replace_spaces_s1 {
26+
public static void main(String[] args) {
27+
// ======= Test Case =======
28+
String s = "We are happy.";
29+
// ====== Driver Code ======
30+
Solution slt = new Solution();
31+
String res = slt.replaceSpace(s);
32+
System.out.println(res);
33+
}
34+
}

‎java/sfo_06_print_a_linked_list_in_reverse_order_s1/sfo_06_print_a_linked_list_in_reverse_order_s1.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/*
2+
* File: sfo_06_print_a_linked_list_in_reverse_order_s1.java
3+
* Created Time: 2021-12-09
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
package sfo_06_print_a_linked_list_in_reverse_order_s1;
8+
9+
import include.*;
10+
import java.util.*;
11+
12+
// ===== Solution Code =====
13+
class Solution {
14+
ArrayList<Integer> tmp = new ArrayList<Integer>();
15+
public int[] reversePrint(ListNode head) {
16+
recur(head);
17+
int[] res = new int[tmp.size()];
18+
for(int i = 0; i < res.length; i++)
19+
res[i] = tmp.get(i);
20+
return res;
21+
}
22+
void recur(ListNode head) {
23+
if(head == null) return;
24+
recur(head.next);
25+
tmp.add(head.val);
26+
}
27+
}
28+
29+
public class sfo_06_print_a_linked_list_in_reverse_order_s1 {
30+
public static void main(String[] args) {
31+
// ======= Test Case =======
32+
ListNode head = ListNode.arrToLinkedList(new int[] { 1, 3, 2 });
33+
// ====== Driver Code ======
34+
Solution slt = new Solution();
35+
int[] res = slt.reversePrint(head);
36+
System.out.println(Arrays.toString(res));
37+
}
38+
}

‎java/sfo_06_print_a_linked_list_in_reverse_order_s2/sfo_06_print_a_linked_list_in_reverse_order_s2.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
/*
2+
* File: sfo_06_print_a_linked_list_in_reverse_order_s2.java
3+
* Created Time: 2021-12-09
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
package sfo_06_print_a_linked_list_in_reverse_order_s2;
8+
9+
import include.*;
10+
import java.util.*;
11+
12+
// ===== Solution Code =====
13+
class Solution {
14+
public int[] reversePrint(ListNode head) {
15+
LinkedList<Integer> stack = new LinkedList<Integer>();
16+
while(head != null) {
17+
stack.addLast(head.val);
18+
head = head.next;
19+
}
20+
int[] res = new int[stack.size()];
21+
for(int i = 0; i < res.length; i++)
22+
res[i] = stack.removeLast();
23+
return res;
24+
}
25+
}
26+
27+
public class sfo_06_print_a_linked_list_in_reverse_order_s2 {
28+
public static void main(String[] args) {
29+
// ======= Test Case =======
30+
ListNode head = ListNode.arrToLinkedList(new int[] { 1, 3, 2 });
31+
// ====== Driver Code ======
32+
Solution slt = new Solution();
33+
int[] res = slt.reversePrint(head);
34+
System.out.println(Arrays.toString(res));
35+
}
36+
}

‎java/sfo_07_reconstruct_binary_tree_s1/sfo_07_reconstruct_binary_tree_s1.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
/*
2+
* File: sfo_07_reconstruct_binary_tree_s1.java
3+
* Created Time: 2021-12-09
4+
* Author: Krahets (krahets@163.com)
5+
*/
6+
7+
package sfo_07_reconstruct_binary_tree_s1;
8+
9+
import include.*;
10+
import java.util.*;
11+
12+
// ===== Solution Code =====
13+
class Solution {
14+
int[] preorder;
15+
HashMap<Integer, Integer> dic = new HashMap<>();
16+
public TreeNode buildTree(int[] preorder, int[] inorder) {
17+
this.preorder = preorder;
18+
for(int i = 0; i < inorder.length; i++)
19+
dic.put(inorder[i], i);
20+
return recur(0, 0, inorder.length - 1);
21+
}
22+
TreeNode recur(int root, int left, int right) {
23+
if(left > right) return null; // 递归终止
24+
TreeNode node = new TreeNode(preorder[root]); // 建立根节点
25+
int i = dic.get(preorder[root]); // 划分根节点、左子树、右子树
26+
node.left = recur(root + 1, left, i - 1); // 开启左子树递归
27+
node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
28+
return node; // 回溯返回根节点
29+
}
30+
}
31+
32+
public class sfo_07_reconstruct_binary_tree_s1 {
33+
public static void main(String[] args) {
34+
// ======= Test Case =======
35+
int[] preorder = { 3, 9, 20, 15, 7 };
36+
int[] inorder = { 9, 3, 15, 20, 7 };
37+
// ====== Driver Code ======
38+
Solution slt = new Solution();
39+
TreeNode res = slt.buildTree(preorder, inorder);
40+
PrintUtil.printTree(res);
41+
}
42+
}

0 commit comments

Comments
 (0)