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 f227ed6

Browse filesBrowse files
duoxoudduoxoud
authored
Merge pull request #2 from AlgoStudyGroup/master
Pull changes from main repo
2 parents 38df940 + 31c9988 commit f227ed6
Copy full SHA for f227ed6

File tree

Expand file treeCollapse file tree

58 files changed

+2457
-0
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
Expand file treeCollapse file tree

58 files changed

+2457
-0
lines changed

‎May-LeetCoding-Challenge/15-Maximum-Sum-Circular-Subarray/Maximum-Sum-Circular-Subarray.scala

Copy file name to clipboard
+18Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
object Solution {
2+
def maxSubarraySumCircular(A: Array[Int]): Int = maxSubArrayFrom(A ++ A, 0, A(0))
3+
4+
def maxSubArrayFrom(nums: Array[Int], from: Int, knownMaxSum: Int): Int = {
5+
if (from == nums.length) knownMaxSum
6+
else {
7+
var sum = nums(from)
8+
var maxSum = sum
9+
var i = from + 1
10+
while (i < nums.length / 2 + i && sum > 0) {
11+
sum += nums(i)
12+
maxSum = maxSum max sum
13+
i += 1
14+
}
15+
maxSubArrayFrom(nums, i, knownMaxSum max maxSum)
16+
}
17+
}
18+
}

‎May-LeetCoding-Challenge/16-Odd-Even-Linked-List/Odd-Even-Linked-List.java

Copy file name to clipboardExpand all lines: May-LeetCoding-Challenge/16-Odd-Even-Linked-List/Odd-Even-Linked-List.java
+21Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,3 +24,24 @@ public ListNode oddEvenList(ListNode head) {
2424
return head;// 1 2 4 5
2525
}
2626
}
27+
28+
class Solution2 {
29+
public ListNode oddEvenList(ListNode head) {
30+
// we separate the list to odd list and event list, and we combine these two list
31+
if(head == null) return null;
32+
33+
ListNode odd = head;
34+
ListNode even = head.next;
35+
ListNode evenHead = even;
36+
37+
while(even != null && even.next != null) {
38+
odd.next = even.next;
39+
odd = odd.next;
40+
even.next = odd.next;
41+
even = even.next;
42+
}
43+
44+
odd.next = evenHead;
45+
return head;
46+
}
47+
}

‎May-LeetCoding-Challenge/16-Odd-Even-Linked-List/Odd-Even-Linked-List.scala

Copy file name to clipboardExpand all lines: May-LeetCoding-Challenge/16-Odd-Even-Linked-List/Odd-Even-Linked-List.scala
+21Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,3 +24,24 @@ object Solution {
2424

2525
}
2626
}
27+
28+
//nothing special ... but i HATE "null" in scala's code !!!
29+
object Solution2 {
30+
31+
def oddEvenList(head: ListNode): ListNode = {
32+
if (head == null || head.next == null) head
33+
else {
34+
val evenListHead = head.next
35+
def reLinkList(odd: ListNode, even: ListNode): Unit = {
36+
if (even == null || even.next == null) odd.next = evenListHead
37+
else {
38+
odd.next = even.next
39+
even.next = odd.next.next
40+
reLinkList(odd.next, even.next)
41+
}
42+
}
43+
reLinkList(head, evenListHead)
44+
head
45+
}
46+
}
47+
}

‎May-LeetCoding-Challenge/17-Find-All-Anagrams-In-A-String/Find-All-Anagrams-In-A-String.cpp

Copy file name to clipboard
+53Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
class Solution {
2+
public:
3+
bool check(vector<int>& diff){
4+
for (int i = 0; i < 26; i++)
5+
if (diff[i] != 0) return false;
6+
return true;
7+
}
8+
9+
vector<int> findAnagrams(string s, string p) {
10+
int n = s.length();
11+
int m = p.length();
12+
13+
if (m > n) return vector<int>();
14+
15+
vector<int> diff(26, 0);
16+
for (int i = 0; i < m; i++) {
17+
diff[s[i] - 'a']++;
18+
diff[p[i] - 'a']--;
19+
}
20+
21+
vector<int> ans;
22+
if (check(diff)) ans.push_back(0);
23+
24+
25+
for (int i = m; i < n; i++){
26+
diff[s[i] - 'a']++;
27+
diff[s[i-m]-'a']--;
28+
if (check(diff)) ans.push_back(i - m + 1);
29+
}
30+
31+
return ans;
32+
}
33+
};
34+
35+
class Solution2 {
36+
public:
37+
vector<int> findAnagrams(string s, string p) {
38+
vector<int> res, m(256, 0);
39+
int left = 0, right, count = p.size(), n = s.size();
40+
41+
if (count > n) return res;
42+
for (char &c : p) ++m[c];
43+
for (right = 0 ; right < p.size()-1 ; ++right)
44+
count -= m[s[right]]-- >= 1;
45+
46+
while (right < n) {
47+
count -= m[s[right++]]-- >= 1;
48+
if (count == 0) res.push_back(left);
49+
count += m[s[left++]]++ >= 0;
50+
}
51+
return res;
52+
}
53+
};

‎May-LeetCoding-Challenge/17-Find-All-Anagrams-In-A-String/Find-All-Anagrams-In-A-String.java

Copy file name to clipboard
+105Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
/*
2+
* Use a int[26] to store char count,
3+
* compare between p count and each s substring count.
4+
*/
5+
class Solution {
6+
public List<Integer> findAnagrams(String s, String p) {
7+
List<Integer> res = new ArrayList<>();
8+
if (s.length() - p.length() < 0) {
9+
return res;
10+
}
11+
int[] pCount = transform(p.toCharArray(), 0, p.length());
12+
char[] sArray = s.toCharArray();
13+
int[] strCount = transform(sArray, 0, p.length());
14+
if (Arrays.equals(strCount, pCount))
15+
res.add(0);
16+
for (int i = 0; i < s.length() - p.length(); i++) {
17+
if (moveAndCompare(sArray, strCount, i, i + p.length(), pCount))
18+
res.add(i + 1);
19+
}
20+
return res;
21+
}
22+
23+
public int[] transform(char[] s, int begin, int end) {
24+
int[] count = new int[26];
25+
for (int i = begin; i < end; i++) {
26+
char c = s[i];
27+
int idx = c - 'a';
28+
count[idx] += 1;
29+
}
30+
return count;
31+
}
32+
33+
public boolean moveAndCompare(char[] str, int[] strCount, int toRemove, int toAdd, int[] pCount) {
34+
int toRemoveIdx = str[toRemove] - 'a';
35+
strCount[toRemoveIdx] -= 1;
36+
int toAddIdx = str[toAdd] - 'a';
37+
strCount[toAddIdx] += 1;
38+
return Arrays.equals(strCount, pCount);
39+
}
40+
}
41+
42+
class Solution2 {
43+
boolean isAnagram (String a, String b) {
44+
int[] arrayA = new int[26];
45+
int[] arrayB = new int[26];
46+
47+
for (int i = 0; i < a.length(); i++) {
48+
arrayA[a.charAt(i) - 'a']++;
49+
}
50+
51+
for (int j = 0; j < b.length(); j++) {
52+
arrayB[b.charAt(j) - 'a']++;
53+
}
54+
55+
for (int k = 0; k < 26; k++) {
56+
if(arrayA[k] != arrayB[k]) return false;
57+
}
58+
return true;
59+
}
60+
61+
public List<Integer> findAnagrams(String s, String p) {
62+
List<Integer> res = new ArrayList<>();
63+
//List<String> listSubString = new ArrayList<>();
64+
String subString = null;
65+
for (int i = 0; i < s.length() - p.length() + 1; i++) {
66+
subString = s.substring(i, p.length() + i);
67+
if(isAnagram(subString, p)) res.add(i);
68+
}
69+
70+
return res;
71+
}
72+
}
73+
74+
// Sliding windows solution
75+
class Solution3 {
76+
private boolean checkDiff(int[] diff){
77+
for (int i = 0; i < diff.length; i++)
78+
if (diff[i] != 0) return false;
79+
80+
return true;
81+
}
82+
83+
public List<Integer> findAnagrams(String s, String p) {
84+
List<Integer> res = new ArrayList<>();
85+
int sLength = s.length(), pLength = p.length();
86+
if(sLength < pLength || s == null) return res;
87+
88+
int[] diff = new int[26];
89+
90+
for(int i = 0; i < pLength; i++) {
91+
diff[p.charAt(i) - 'a']--;
92+
diff[s.charAt(i) - 'a']++;
93+
}
94+
if(checkDiff(diff)) res.add(0);
95+
96+
//sliding window
97+
for (int i = pLength; i < sLength; i++) {
98+
diff[s.charAt(i) - 'a']++;
99+
diff[s.charAt(i - pLength) - 'a']--;
100+
if(checkDiff(diff)) res.add(i - pLength + 1);
101+
}
102+
103+
return res;
104+
}
105+
}

‎May-LeetCoding-Challenge/17-Find-All-Anagrams-In-A-String/Find-All-Anagrams-In-A-String.kt

Copy file name to clipboard
+72Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
class FindAllAnagramsinaStringKotlin438 {
2+
fun findAnagrams(s: String, p: String): List<Int> {
3+
if (s.isEmpty() || s.length < p.length) {
4+
return emptyList()
5+
}
6+
val result = mutableListOf<Int>()
7+
val hashArray = IntArray(26)
8+
for (index in p.indices) {
9+
++hashArray[p[index] - 'a']
10+
}
11+
var left = 0
12+
var count = 0
13+
/*
14+
0 1 2 3 4
15+
S: b a b a e ...
16+
P: a b b
17+
for
18+
a b e
19+
P 1 2 0
20+
0 1 1 0 count = 1
21+
1 0 1 0 count = 2
22+
2 0 0 0 count = 3 left = 0 OK
23+
3 0 1 0 count = 2 left = 1 NOT
24+
4 1 1 -1 count = 1 left = 2 NOT
25+
*/
26+
27+
for (index in s.indices) {
28+
if (--hashArray[s[index] - 'a'] >= 0) {
29+
++count
30+
}
31+
if (index >= p.length) {
32+
if (hashArray[s[left++] - 'a']++ >= 0) {
33+
--count
34+
}
35+
}
36+
if (count == p.length) {
37+
result.add(left)
38+
}
39+
}
40+
return result
41+
}
42+
/*
43+
fun findAnagrams(s: String, p: String): List<Int> {
44+
if (s.isEmpty() || s.length < p.length) {
45+
return emptyList()
46+
}
47+
val result = mutableListOf<Int>()
48+
val hashArray = IntArray(26)
49+
for (index in p.indices) {
50+
++hashArray[p[index] - 'a']
51+
--hashArray[s[index] - 'a']
52+
}
53+
if (hashArray.count { it == 0 } == 26) {
54+
result.add(0)
55+
}
56+
for (index in 1..s.length - p.length) {
57+
++hashArray[s[index - 1] - 'a']
58+
--hashArray[s[index + p.length - 1] - 'a']
59+
if (hashArray.count { it == 0 } == 26) {
60+
result.add(index)
61+
}
62+
}
63+
return result
64+
}
65+
*/
66+
}
67+
68+
fun main() {
69+
val solution = FindAllAnagramsinaStringKotlin438()
70+
println(solution.findAnagrams("cbaebabacd", "abc")) // 0,6
71+
println(solution.findAnagrams("abab", "ab")) // 0,1,2
72+
}

‎May-LeetCoding-Challenge/17-Find-All-Anagrams-In-A-String/Find-All-Anagrams-In-A-String.py

Copy file name to clipboard
+39Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
class Solution:
2+
def findAnagrams(self, s: str, p: str) -> List[int]:
3+
sl = len(s)
4+
droite, taille = len(p), len(p)
5+
if (sl < droite):
6+
return []
7+
res = []
8+
window = dict()
9+
need = dict()
10+
for c in p:
11+
need[c] = need.get(c, 0) + 1
12+
tmp = s[0]
13+
gauche = 0
14+
droite = gauche + taille
15+
for c in s[:droite]:
16+
window[c] = window.get(c, 0) + 1
17+
if (window == need):
18+
res.append(0)
19+
while (droite < sl):
20+
debut = s[gauche]
21+
value = window.get(debut)
22+
if (value <= 1):
23+
del window[debut]
24+
else:
25+
window[debut] -= 1
26+
tmp = s[droite]
27+
if (tmp not in need):
28+
window.clear()
29+
gauche += 1
30+
droite = gauche + taille
31+
for c in s[gauche:droite]:
32+
window[c] = window.get(c, 0) + 1
33+
else:
34+
window[tmp] = window.get(tmp, 0) + 1
35+
gauche += 1
36+
droite = gauche + taille
37+
if (window == need):
38+
res.append(gauche)
39+
return res

‎May-LeetCoding-Challenge/17-Find-All-Anagrams-In-A-String/Find-All-Anagrams-In-A-String.scala

Copy file name to clipboard
+34Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
// for small & simple dataset, exception: "memory limit exceeded" when s & p are both too long O((n - m) * m)
2+
object Solution1 {
3+
def findAnagrams(s: String, p: String): List[Int] = {
4+
val sortedP = p.sorted
5+
(0 to s.length - sortedP.length).filter(index => isAnagram(s.substring(index, index + sortedP.length), sortedP)).toList
6+
}
7+
8+
def isAnagram(textA: String, sortedTextB: String): Boolean = textA.length == sortedTextB.length && textA.sorted == sortedTextB
9+
}
10+
11+
// solution with O(n + m) complexity
12+
object Solution2 {
13+
import scala.collection.mutable._
14+
def findAnagrams(s: String, p: String): List[Int] = {
15+
val diffMap = HashMap.empty[Char, Int]
16+
// initiate diffMap
17+
p.foreach(updateMap(diffMap, _, 1))
18+
19+
// -1 if char exist in diffMap, remove key if value == 0
20+
// +1 if char exit the subString's left bound , remove key if value == 0
21+
(0 until s.length).toList.filter(index => {
22+
if (index >= p.length) updateMap(diffMap, s(index - p.length), 1)
23+
updateMap(diffMap, s(index), -1)
24+
diffMap.isEmpty
25+
}).map(_ - p.length + 1)
26+
}
27+
28+
def updateMap(map: HashMap[Char, Int], char: Char, incrementer: Int): Unit =
29+
map.get(char) match {
30+
case Some(number) if number + incrementer == 0 => map -= char
31+
case Some(number) => map += (char -> (number + incrementer))
32+
case None => map += (char -> incrementer)
33+
}
34+
}

0 commit comments

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