Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 25a9462

Browse filesBrowse files
qilingitqilingit
committed
Merge remote-tracking branch 'upstream/master'
2 parents 2198582 + c286c26 commit 25a9462
Copy full SHA for 25a9462

File tree

58 files changed

+1704
-1
lines changed
Filter options

Some content is hidden

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

58 files changed

+1704
-1
lines changed

‎June-LeetCoding-Challenge/01-Invert-Binary-Tree/Invert-Binary-Tree.cpp

Copy file name to clipboard
+28Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
class Solution {
2+
public:
3+
void dfs(TreeNode* r1, TreeNode** r2){
4+
if (r1 == NULL) return;
5+
*r2 = new TreeNode(r1->val);
6+
dfs(r1->left, &((*r2)->right));
7+
dfs(r1->right, &((*r2)->left));
8+
}
9+
10+
TreeNode* invertTree(TreeNode* root) {
11+
TreeNode* root2 = NULL;
12+
dfs(root, &root2);
13+
return root2;
14+
}
15+
};
16+
17+
class Solution {
18+
public:
19+
TreeNode* invertTree(TreeNode* root) {
20+
if(!root) return nullptr;
21+
auto left = (root->left)?invertTree(root->left):nullptr;
22+
auto right = (root->right)?invertTree(root->right):nullptr;
23+
root->left = right;
24+
root->right = left;
25+
return root;
26+
}
27+
28+
};

‎June-LeetCoding-Challenge/01-Invert-Binary-Tree/Invert-Binary-Tree.cs

Copy file name to clipboard
+13Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
public class Solution {
2+
public TreeNode InvertTree(TreeNode root) {
3+
if (root != null)
4+
{
5+
InvertTree(root.left);
6+
InvertTree(root.right);
7+
TreeNode temps = root.left;
8+
root.left=root.right;
9+
root.right= temps;
10+
}
11+
return root;
12+
}
13+
}

‎June-LeetCoding-Challenge/01-Invert-Binary-Tree/Invert-Binary-Tree.java

Copy file name to clipboard
+27Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* public class TreeNode {
4+
* int val;
5+
* TreeNode left;
6+
* TreeNode right;
7+
* TreeNode() {}
8+
* TreeNode(int val) { this.val = val; }
9+
* TreeNode(int val, TreeNode left, TreeNode right) {
10+
* this.val = val;
11+
* this.left = left;
12+
* this.right = right;
13+
* }
14+
* }
15+
*/
16+
class Solution {
17+
public TreeNode invertTree(TreeNode root) {
18+
if(root!=null){
19+
TreeNode tmp = root.left;
20+
root.left = root.right;
21+
root.right = tmp;
22+
root.left = invertTree(root.left);
23+
root.right = invertTree(root.right);
24+
}
25+
return root;
26+
}
27+
}

‎June-LeetCoding-Challenge/01-Invert-Binary-Tree/Invert-Binary-Tree.kt

Copy file name to clipboard
+22Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
class InvertBinaryTreeKotlin226 {
2+
fun invertTree(root: TreeNode?): TreeNode? {
3+
invert(root)
4+
return root
5+
}
6+
7+
private fun invert(root: TreeNode?) {
8+
if (root == null) {
9+
return
10+
}
11+
val temp = root.left
12+
root.left = root.right
13+
root.right = temp
14+
root.left?.let { invert(it) }
15+
root.right?.let { invert(it) }
16+
}
17+
18+
class TreeNode(var `val`: Int) {
19+
var left: TreeNode? = null
20+
var right: TreeNode? = null
21+
}
22+
}

‎June-LeetCoding-Challenge/01-Invert-Binary-Tree/Invert-Binary-Tree.scala

Copy file name to clipboard
+40Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
class Question01 {
2+
3+
class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
4+
var value: Int = _value
5+
var left: TreeNode = _left
6+
var right: TreeNode = _right
7+
}
8+
9+
//space complexity O(1)
10+
object Solution {
11+
def invertTree(root: TreeNode): TreeNode = {
12+
def recursiveInvert(root: TreeNode): Unit = {
13+
if (root != null) {
14+
val tmp = root.left
15+
root.left = root.right
16+
root.right = tmp
17+
recursiveInvert(root.left)
18+
recursiveInvert(root.right)
19+
}
20+
}
21+
recursiveInvert(root)
22+
root
23+
}
24+
}
25+
26+
//space complexity 0(n)
27+
object Solution2 {
28+
def invertTree(root: TreeNode): TreeNode = recursiveInvert(root)
29+
30+
def recursiveInvert(root: TreeNode): TreeNode = {
31+
if (root == null) null
32+
else {
33+
val tmp = root.left
34+
root.left = recursiveInvert(root.right)
35+
root.right = recursiveInvert(tmp)
36+
root
37+
}
38+
}
39+
}
40+
}

‎June-LeetCoding-Challenge/02-Delete-Node-In-A-Linked-List/Delete-Node-In-A-Linked-List.cpp

Copy file name to clipboard
+7Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
class Solution {
2+
public:
3+
void deleteNode(ListNode* node) {
4+
node->val = node->next->val;
5+
node->next = node->next->next;
6+
}
7+
};

‎June-LeetCoding-Challenge/02-Delete-Node-In-A-Linked-List/Delete-Node-In-A-Linked-List.kt

Copy file name to clipboard
+11Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
class DeleteNodeinaLinkedListKotlin237 {
2+
fun deleteNode(node: ListNode?) {
3+
val next = node!!.next!!
4+
node.`val` = next.`val`
5+
node.next = next.next
6+
}
7+
8+
class ListNode(var `val`: Int) {
9+
var next: ListNode? = null
10+
}
11+
}

‎June-LeetCoding-Challenge/02-Delete-Node-In-A-Linked-List/Delete-Node-In-A-Linked-List.scala

Copy file name to clipboard
+15Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
class Question02 {
2+
3+
class ListNode(var _x: Int = 0) {
4+
var next: ListNode = null
5+
var x: Int = _x
6+
}
7+
8+
object Solution {
9+
def deleteNode(node: ListNode): Unit = {
10+
node.x = node.next.x
11+
node.next = node.next.next
12+
}
13+
}
14+
}
15+

‎June-LeetCoding-Challenge/02-Delete-Node-In-A-Linked-List/Delete-Node-in-a-Linked-List.java

Copy file name to clipboard
+14Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* public class ListNode {
4+
* int val;
5+
* ListNode next;
6+
* ListNode(int x) { val = x; }
7+
* }
8+
*/
9+
class Solution {
10+
public void deleteNode(ListNode node) {
11+
node.val = node.next.val;
12+
node.next = node.next.next;
13+
}
14+
}

‎June-LeetCoding-Challenge/02-Delete-Node-In-A-Linked-List/Delete-Node-in-a-Linked-List.js

Copy file name to clipboard
+15Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* function ListNode(val) {
4+
* this.val = val;
5+
* this.next = null;
6+
* }
7+
*/
8+
/**
9+
* @param {ListNode} node
10+
* @return {void} Do not return anything, modify node in-place instead.
11+
*/
12+
var deleteNode = function(node) {
13+
node.val = node.next.val;
14+
node.next = node.next.next;
15+
};

‎June-LeetCoding-Challenge/03-Two-City-Scheduling/Two-City-Scheduling.cpp

Copy file name to clipboard
+21Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
// Time Complexity O(n^2), space complexity O(n^2)
2+
class Solution {
3+
public:
4+
int twoCitySchedCost(vector<vector<int>>& costs) {
5+
int N = costs.size();
6+
if (N == 0) return 0;
7+
int n = N / 2;
8+
9+
vector<vector<int>> dp(N+1, vector<int>(n+1, 0));
10+
for (int i = 1; i <= N; i++) dp[i][0] = dp[i-1][0] + costs[i-1][1];
11+
12+
13+
for (int i = 1; i <= N; i++)
14+
for (int j = 0; j <= min(n, i); j++){
15+
dp[i][j] = dp[i-1][j-1] + costs[i-1][0];
16+
if (i-1 >= j)
17+
dp[i][j] = min(dp[i][j], dp[i-1][j] + costs[i-1][1]);
18+
}
19+
return dp[N][n];
20+
}
21+
};

‎June-LeetCoding-Challenge/03-Two-City-Scheduling/Two-City-Scheduling.cs

Copy file name to clipboard
+27Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
public class Helper {
2+
public int a;
3+
public int b;
4+
public int diff {get {return b-a;}}
5+
}
6+
7+
public class Solution {
8+
public int TwoCitySchedCost(int[][] costs) {
9+
var helpers = new List<Helper>();
10+
for(int i = 0; i < costs.Length; i++)
11+
{
12+
helpers.Add(new Helper(){
13+
a = costs[i][0],
14+
b = costs[i][1],
15+
});
16+
}
17+
helpers = helpers.OrderBy(h => h.diff ).ToList();
18+
19+
int result = 0;
20+
for(int i = 0; i < helpers.Count; i++)
21+
{
22+
var helper = helpers[i];
23+
result += i < helpers.Count/2 ? helper.b : helper.a;
24+
}
25+
return result;
26+
}
27+
}

‎June-LeetCoding-Challenge/03-Two-City-Scheduling/Two-City-Scheduling.kt

Copy file name to clipboard
+60Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
class TwoCitySchedulingKotlin1029 {
2+
3+
fun twoCitySchedCost(costs: Array<IntArray>): Int {
4+
costs.sortWith(Comparator { ints1, ints2 -> compareValues(ints1[0] - ints1[1], ints2[0] - ints2[1]) })
5+
val half = costs.size / 2
6+
var sum = 0
7+
costs.forEachIndexed { index, ints ->
8+
sum += when {
9+
index < half -> ints[0]
10+
else -> ints[1]
11+
}
12+
}
13+
return sum
14+
}
15+
/*
16+
fun twoCitySchedCost(costs: Array<IntArray>): Int {
17+
val half = costs.size.shr(1)
18+
val dp = Array(half + 1) { IntArray(half + 1) }
19+
for (index in 1 until dp.size) {
20+
dp[0][index] = dp[0][index - 1] + costs[index - 1][0]
21+
}
22+
for (i in 1 until dp.size) {
23+
dp[i][0] = dp[i - 1][0] + costs[i - 1][1]
24+
for (j in 1 until dp.size) {
25+
dp[i][j] = minOf(
26+
dp[i - 1][j] + costs[i + j - 1][1],
27+
dp[i][j - 1] + costs[i + j - 1][0]
28+
)
29+
}
30+
}
31+
return dp[half][half]
32+
}
33+
*/
34+
}
35+
36+
fun main() {
37+
val solution = TwoCitySchedulingKotlin1029()
38+
// 110
39+
println(
40+
solution.twoCitySchedCost(
41+
arrayOf(
42+
intArrayOf(10, 20),
43+
intArrayOf(30, 200),
44+
intArrayOf(400, 50),
45+
intArrayOf(30, 20)
46+
)
47+
)
48+
)
49+
// 130
50+
println(
51+
solution.twoCitySchedCost(
52+
arrayOf(
53+
intArrayOf(10, 20),
54+
intArrayOf(30, 200),
55+
intArrayOf(400, 50),
56+
intArrayOf(30, 200)
57+
)
58+
)
59+
)
60+
}

‎June-LeetCoding-Challenge/03-Two-City-Scheduling/Two-City-Scheduling.scala

Copy file name to clipboard
+10Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
class Question03 {
2+
// sort by difference O(n2)
3+
object Solution {
4+
def twoCitySchedCost(costs: Array[Array[Int]]): Int = {
5+
costs.sortBy(t => t(0) - t(1)).zipWithIndex.foldLeft(0) {
6+
case (acc, (t, index)) => acc + (if (index < costs.length / 2) t(0) else t(1))
7+
}
8+
}
9+
}
10+
}

‎June-LeetCoding-Challenge/04-Reverse-String/Reverse-String.cpp

Copy file name to clipboard
+11Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
class Solution {
2+
public:
3+
void reverseString(vector<char>& s) {
4+
int n = s.size();
5+
for (int i = 0; i < n / 2; i++){
6+
char t = s[i];
7+
s[i] = s[n - i - 1];
8+
s[n - i- 1] = t;
9+
}
10+
}
11+
};

‎June-LeetCoding-Challenge/04-Reverse-String/Reverse-String.cs

Copy file name to clipboard
+30Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
public class Solution {
2+
3+
public void ReverseString(char[] s) {
4+
int left = 0;
5+
int right = s.Length-1;
6+
while (left < right)
7+
{
8+
char temp = s[left];
9+
s[left] = s[right];
10+
s[right] = temp;
11+
left++;
12+
right--;
13+
}
14+
}
15+
16+
public void ReverseString2(char[] s) {
17+
helper(s, 0, s.Length-1);
18+
}
19+
20+
public void helper(char[] s, int left, int right)
21+
{
22+
if (left < right)
23+
{
24+
char temp = s[left];
25+
s[left] = s[right];
26+
s[right] = temp;
27+
helper(s, left+1, right-1);
28+
}
29+
}
30+
}

‎June-LeetCoding-Challenge/04-Reverse-String/Reverse-String.js

Copy file name to clipboard
+16Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
/**
2+
* @param {character[]} s
3+
* @return {void} Do not return anything, modify s in-place instead.
4+
*/
5+
var reverseString = function(s) {
6+
var i = 0;
7+
var j = s.length-1;
8+
while(i<j){
9+
let tmp = s[i];
10+
s[i]=s[j];
11+
s[j]=tmp;
12+
i++;
13+
j--;
14+
}
15+
return s;
16+
};

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.