8000 Merge pull request #2 from AlgoStudyGroup/master · xulongjun/Leetcode@f227ed6 · GitHub
[go: up one dir, main page]
Skip to content

Commit f227ed6

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

File tree

58 files changed

+2457
-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.

58 files changed

+2457
-0
lines changed

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

Lines 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
 DDA9
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

Lines 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

Lines 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

Lines 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

Lines 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

Lines 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< 10000 code class="diff-text syntax-highlighted-line addition">+
*/
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(&qu 10000 ot;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

Lines 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

Lines 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