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 1ba99ac

Browse filesBrowse files
qilingitqilingit
committed
Merge branch 'master' of https://github.com/jinshendan/Leetcode 
2 parents 25a9462 + 2c55aa0 commit 1ba99ac
Copy full SHA for 1ba99ac

File tree

Expand file treeCollapse file tree

20 files changed

+684
-0
lines changed
Filter options
Expand file treeCollapse file tree

20 files changed

+684
-0
lines changed

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

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

‎June-LeetCoding-Challenge/05-Random-Pick-With-Weight/Random-Pick-With-Weight.cs

Copy file name to clipboard
+80Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
// Solution: Binary search
2+
// Runtime: 208 ms, faster than 95.23% of C# online submissions for Random Pick with Weight.
3+
// Memory Usage: 47.2 MB, less than 5.10% of C# online submissions for Random Pick with Weight.
4+
public class Solution
5+
{
6+
private int sum = 0; //sum of all integers of array w
7+
private int[] arr; //new Array, its index means index, its value means weight
8+
private Random random = new Random();
9+
public Solution(int[] w)
10+
{
11+
arr = new int[w.Length];
12+
for (var i = 0; i < w.Length; i++)
13+
{
14+
sum += w[i];
15+
arr[i] = sum;
16+
}
17+
}
18+
19+
//Binary search
20+
public int PickIndex()
21+
{
22+
//Generate a random value between 0 and sum
23+
var randomValue = random.Next(0, sum) + 1;
24+
int left = 0, right = arr.Length - 1;
25+
while (left <= right)
26+
{
27+
int mid = left + (right - left) / 2;
28+
if (arr[mid] == randomValue)
29+
return mid;
30+
else if (arr[mid] > randomValue)
31+
right = mid - 1;
32+
else
33+
left = mid + 1;
34+
}
35+
36+
return left;
37+
}
38+
}
39+
40+
41+
// Solution: Linear search
42+
// Runtime: 400 ms, faster than 37.10% of C# online submissions for Random Pick with Weight.
43+
// Memory Usage: 47 MB, less than 5.10% of C# online submissions for Random Pick with Weight.
44+
public class Solution
45+
{
46+
private int sum = 0; //sum of all integers of array w
47+
private int[] arr; //new Array, its index means index, its value means weight
48+
private Random random = new Random();
49+
public Solution(int[] w)
50+
{
51+
arr = new int[w.Length];
52+
for (var i = 0; i < w.Length; i++)
53+
{
54+
sum += w[i];
55+
arr[i] = sum;
56+
}
57+
}
58+
59+
//Linear search
60+
public int PickIndex()
61+
{
62+
//Generate a random value between 0 and sum
63+
var randomeValue = random.Next(0, sum);
64+
65+
for (int i = 0; i < arr.Length; i++)
66+
{
67+
if (randomeValue < arr[i])
68+
{
69+
return i;
70+
}
71+
}
72+
return 0;
73+
}
74+
}
75+
76+
/**
77+
* Your Solution object will be instantiated and called as such:
78+
* Solution obj = new Solution(w);
79+
* int param_1 = obj.PickIndex();
80+
*/

‎June-LeetCoding-Challenge/15-Search-In-A-Binary-Search-Tree/Search-In-A-Binary-Search-Tree.kt

Copy file name to clipboard
+16Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class SearchinaBinarySearchTreeKotlin700 {
2+
fun searchBST(root: TreeNode?, `val`: Int): TreeNode? {
3+
return when {
4+
root == null -> null
5+
root.`val` == `val` -> root
6+
root.`val` < `val` -> searchBST(root.right, `val`)
7+
root.`val` > `val` -> searchBST(root.left, `val`)
8+
else -> null
9+
}
10+
}
11+
12+
class TreeNode(var `val`: Int) {
13+
var left: TreeNode? = null
14+
var right: TreeNode? = null
15+
}
16+
}

‎June-LeetCoding-Challenge/16-Validate-IP-Address/Validate-IP-Address.kt

Copy file name to clipboard
+76Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
class ValidateIPAddressKotlin468 {
2+
fun validIPAddress(IP: String): String {
3+
if (IP.isEmpty() || IP.length < 6) {
4+
return "Neither"
5+
}
6+
val str5 = IP.substring(0, 6)
7+
return when {
8+
str5.contains(".") -> {
9+
val strArray4 = IP.split(".")
10+
if (strArray4.size == 4) {
11+
strArray4.forEach {
12+
if (!isIpV4(it)) {
13+
return "Neither"
14+
}
15+
}
16+
"IPv4"
17+
} else {
18+
"Neither"
19+
}
20+
}
21+
str5.contains(":") -> {
22+
val strArray8 = IP.split(":")
23+
if (strArray8.size == 8) {
24+
strArray8.forEach {
25+
if (!isIpV6(it)) {
26+
return "Neither"
27+
}
28+
}
29+
"IPv6"
30+
} else {
31+
"Neither"
32+
}
33+
}
34+
else -> "Neither"
35+
}
36+
}
37+
38+
private val validIpV4String = "0123456789"
39+
40+
private fun isIpV4(string: String): Boolean {
41+
if (string.length in 1..3) {
42+
string.forEach {
43+
if (!validIpV4String.contains(it, ignoreCase = true)) {
44+
return false
45+
}
46+
}
47+
if (string.toInt() !in 0..255) {
48+
return false
49+
}
50+
if (string[0] == '0' && string.length > 1) {
51+
return false
52+
}
53+
return true
54+
}
55+
return false
56+
}
57+
58+
private val validIpV6String = "0123456789abcdef"
59+
60+
private fun isIpV6(string: String): Boolean {
61+
if (string.length in 1..4) {
62+
string.forEach {
63+
if (!validIpV6String.contains(it, ignoreCase = true)) {
64+
return false
65+
}
66+
}
67+
return true
68+
}
69+
return false
70+
}
71+
}
72+
73+
fun main() {
74+
val str = "2001:0db8:85a3:0:0:8A2E:0370:7334:"
75+
println(str.split(":").size)
76+
}

‎June-LeetCoding-Challenge/17-Surrounded-Regions/Surrounded-Regions.kt

Copy file name to clipboard
+124Lines changed: 124 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,124 @@
1+
class SurroundedRegionsKotlin130 {
2+
fun solve(board: Array<CharArray>) {
3+
if (board.isEmpty()) {
4+
return
5+
}
6+
val maxX = board.size
7+
val maxY = board[0].size
8+
val dp = Array(maxX) { IntArray(maxY) { 0 } }
9+
for (index in board[0].indices) {
10+
if (board[0][index] == 'O') {
11+
dfs(board, dp, 0, index, maxX, maxY)
12+
}
13+
if (board[maxX - 1][index] == 'O') {
14+
dfs(board, dp, maxX - 1, index, maxX, maxY)
15+
}
16+
}
17+
for (index in board.indices) {
18+
if (board[index][0] == 'O') {
19+
dfs(board, dp, index, 0, maxX, maxY)
20+
}
21+
if (board[index][maxY - 1] == 'O') {
22+
dfs(board, dp, index, maxY - 1, maxX, maxY)
23+
}
24+
}
25+
for (i in 1..board.size - 2) {
26+
for (j in 1..board[0].size - 2) {
27+
if (board[i][j] == 'O' && dp[i][j] == 0) {
28+
board[i][j] = 'X'
29+
}
30+
}
31+
}
32+
}
33+
34+
private val deltaX = intArrayOf(0, 0, 1, -1)
35+
private val deltaY = intArrayOf(1, -1, 0, 0)
36+
37+
private fun dfs(
38+
board: Array<CharArray>,
39+
dp: Array<IntArray>,
40+
x: Int,
41+
y: Int,
42+
maxX: Int,
43+
maxY: Int
44+
) {
45+
if (dp[x][y] == 0 && board[x][y] == 'O') {
46+
dp[x][y] = 1
47+
for (index in deltaX.indices) {
48+
val nextX = x + deltaX[index]
49+
val nextY = y + deltaY[index]
50+
if (inBoardMinus1(nextX, nextY, maxX, maxY)) {
51+
dfs(board, dp, nextX, nextY, maxX, maxY)
52+
}
53+
}
54+
}
55+
}
56+
57+
private fun inBoardMinus1(x: Int, y: Int, maxX: Int, maxY: Int) = x > 0 && y > 0 && x < maxX - 1 && y < maxY - 1
58+
/*
59+
fun solve(board: Array<CharArray>) {
60+
if (board.isEmpty()) {
61+
return
62+
}
63+
val maxX = board.size
64+
val maxY = board[0].size
65+
val dp = Array(maxX) { IntArray(maxY) { 0 } }
66+
val queue: Queue<Pair<Int, Int>> = LinkedList()
67+
for (index in board[0].indices) {
68+
if (board[0][index] == 'O') {
69+
queue.offer(Pair(0, index))
70+
}
71+
if (board[maxX - 1][index] == 'O') {
72+
queue.offer(Pair(maxX - 1, index))
73+
}
74+
}
75+
for (index in board.indices) {
76+
if (board[index][0] == 'O') {
77+
queue.offer(Pair(index, 0))
78+
}
79+
if (board[index][maxY - 1] == 'O') {
80+
queue.offer(Pair(index, maxY - 1))
81+
}
82+
}
83+
val deltaX = intArrayOf(0, 0, 1, -1)
84+
val deltaY = intArrayOf(1, -1, 0, 0)
85+
while (queue.isNotEmpty()) {
86+
val current = queue.poll()
87+
val x = current.first
88+
val y = current.second
89+
if (dp[x][y] == 0 && board[x][y] == 'O') {
90+
dp[x][y] = 1
91+
for (index in deltaX.indices) {
92+
val nextX = x + deltaX[index]
93+
val nextY = y + deltaY[index]
94+
if (inBoardMinus1(nextX, nextY, maxX, maxY)) {
95+
queue.offer(Pair(nextX, nextY))
96+
}
97+
}
98+
}
99+
}
100+
for (i in 1..board.size - 2) {
101+
for (j in 1..board[0].size - 2) {
102+
if (board[i][j] == 'O' && dp[i][j] == 0) {
103+
board[i][j] = 'X'
104+
}
105+
}
106+
}
107+
}
108+
109+
private fun inBoardMinus1(x: Int, y: Int, maxX: Int, maxY: Int) = x > 0 && y > 0 && x < maxX - 1 && y < maxY - 1
110+
111+
*/
112+
}
113+
114+
fun main() {
115+
val solution = SurroundedRegionsKotlin130()
116+
val testArray = arrayOf(
117+
charArrayOf('X', 'X', 'X', 'X'),
118+
charArrayOf('X', 'O', 'O', 'X'),
119+
charArrayOf('X', 'X', 'O', 'X'),
120+
charArrayOf('X', 'O', 'X', 'X')
121+
)
122+
solution.solve(testArray)
123+
println()
124+
}

‎June-LeetCoding-Challenge/17-Surrounded-Regions/Surrounded-Regions.py

Copy file name to clipboard
+46Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
class Solution:
2+
def solve(self, board: List[List[str]]) -> None:
3+
"""
4+
Do not return anything, modify board in-place instead.
5+
"""
6+
if board:
7+
for i in range(len(board)):
8+
if board[i][0]=='O':
9+
self.bfs(board,i,0)
10+
if board[i][len(board[0])-1]=='O':
11+
self.bfs(board,i,len(board[0])-1)
12+
for j in range(len(board[0])):
13+
if board[0][j]=='O':
14+
self.bfs(board,0,j)
15+
if board[len(board)-1][j]=='O':
16+
self.bfs(board,len(board)-1,j)
17+
for i in range(len(board)):
18+
for j in range(len(board[0])):
19+
if board[i][j]=='O':
20+
board[i][j]='X'
21+
if board[i][j]=='2':
22+
board[i][j]='O'
23+
24+
def bfs(self,board,i,j):
25+
q = [[i,j]]
26+
while q!=[]:
27+
pos = q.pop(0)
28+
a = pos[0]
29+
b = pos[1]
30+
board[a][b] = '2'
31+
if 0<=a+1<len(board):
32+
if board[a+1][b]=='O':
33+
board[a+1][b]='2'
34+
q.append([a+1,b])
35+
if 0<=a-1<len(board):
36+
if board[a-1][b]=='O':
37+
board[a-1][b]='2'
38+
q.append([a-1,b])
39+
if 0<=b+1<len(board[0]):
40+
if board[a][b+1]=='O':
41+
board[a][b+1] = '2'
42+
q.append([a,b+1])
43+
if 0<=b-1<len(board[0]):
44+
if board[a][b-1]=='O':
45+
board[a][b-1] = '2'
46+
q.append([a,b-1])

‎June-LeetCoding-Challenge/18-H-Index-II/H-Index-II.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 HIndexIIKotlin275 {
2+
fun hIndex(citations: IntArray): Int {
3+
if (citations.isEmpty()) {
4+
return 0
5+
}
6+
var left = 0
7+
var right = citations.size
8+
while (left + 1 < right) {
9+
val mid = left + (right - left) / 2
10+
when {
11+
citations[citations.size - mid] >= mid -> left = mid
12+
else -> right = mid
13+
}
14+
}
15+
return when {
16+
citations[citations.size - right] >= right -> right
17+
left == 0 -> 0
18+
citations[citations.size - left] >= left -> left
19+
else -> -1
20+
}
21+
}
22+
}

0 commit comments

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