Skip to content

Commit 114245b

Browse files
haoelhaoel
authored
Merge branch 'master' into sudesh
2 parents 5fd14ec + ec39844 commit 114245b

4 files changed

Lines changed: 196 additions & 1 deletion

File tree

‎README.md‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@ LeetCode
1010
| # | Title | Solution | Difficulty |
1111
|---| ----- | -------- | ---------- |
1212
|1573|[Number of Ways to Split a String](https://leetcode.com/problems/number-of-ways-to-split-a-string/) | [C++](./algorithms/cpp/NumberOfWaysToSplitString/NumberOfWaysToSplitString.cpp)|Medium|
13+
|1376|[Time Needed to Inform All Employees](https://leetcode.com/problems/time-needed-to-inform-all-employees/) | [C++](./algorithms/cpp/timeNeededToInformAllEmployees/TimeNeededToInformAllEmployees.cpp)|Medium|
1314
|1207|[Unique Number of Occurrences](https://leetcode.com/problems/unique-number-of-occurrences/) | [C++](./algorithms/cpp/uniqueNumberOfOccurrences/Unique-Number-of-Occurrences.cpp)|Easy|
1415
|1170|[Compare Strings by Frequency of the Smallest Character](https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/) | [C++](./algorithms/cpp/compareStringsByFrequencyOfTheSmallestCharacter/CompareStringsByFrequencyOfTheSmallestCharacter.cpp)|Easy|
1516
|1071|[Greatest Common Divisor of Strings](https://leetcode.com/problems/greatest-common-divisor-of-strings/) | [C++](./algorithms/cpp/greatestCommonDivisorOfStrings/GreatestCommonDivisorOfStrings.cpp)|Easy|
@@ -29,7 +30,7 @@ LeetCode
2930
|983|[Minimum Cost For Tickets](https://leetcode.com/problems/minimum-cost-for-tickets/) | [C++](./algorithms/cpp/minimumCostForTickets/MinimumCostForTickets.cpp)|Medium|
3031
|982|[Triples with Bitwise AND Equal To Zero](https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero/) | [C++](./algorithms/cpp/triplesWithBitwiseANDEqualToZero/TriplesWithBitwiseAndEqualToZero.cpp)|Hard|
3132
|981|[Time Based Key-Value Store](https://leetcode.com/problems/time-based-key-value-store/) | [C++](./algorithms/cpp/timeBasedKeyValueStore/TimeBasedKeyValueStore.cpp)|Medium|
32-
|980|[Unique Paths III](https://leetcode.com/problems/unique-paths-iii/) | [C++](./algorithms/cpp/uniquePaths/UniquePaths.III.cpp)|Hard|
33+
|980|[Unique Paths III](https://leetcode.com/problems/unique-paths-iii/) | [C++](./algorithms/cpp/uniquePaths/UniquePaths.III.cpp),[Python](./algorithms/python/uniquePaths/uniquePathsIII.py)|Hard|
3334
|979|[Distribute Coins in Binary Tree](https://leetcode.com/problems/distribute-coins-in-binary-tree/) | [C++](./algorithms/cpp/distributeCoinsInBinaryTree/DistributeCoinsInBinaryTree.cpp)|Medium|
3435
|978|[Longest Turbulent Subarray](https://leetcode.com/problems/longest-turbulent-subarray/) | [C++](./algorithms/cpp/longestTurbulentSubarray/LongestTurbulentSubarray.cpp),[Python](./algorithms/python/LongestTurbulentSubarray/maxTurbulenceSize.py)|Medium|
3536
|977|[Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/) | [C++](./algorithms/cpp/squaresOfASortedArray/SquaresOfASortedArray.cpp), [Python](./algorithms/python/SquaresOfSortedArray/sortedSquares.py)|Easy|
@@ -55,6 +56,7 @@ LeetCode
5556
|844|[Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/description/) | [C++](./algorithms/cpp/backspaceStringCompare/BackspaceStringCompare.cpp)|Easy|
5657
|837|[Most Common Word](https://leetcode.com/problems/most-common-word/) | [C++](./algorithms/cpp/mostCommonWord/MostCommonWord.cpp)|Easy|
5758
|830|[Positions of Large Groups](https://leetcode.com/problems/positions-of-large-groups/) | [Python](./algorithms/python/PositionsOfLargeGroups/largeGroupPositions.py)|Easy|
59+
|820|[Short Encoding of Words](https://leetcode.com/problems/short-encoding-of-words/) | [C++](./algorithms/cpp/shortEncodingOfWords/ShortEncodingOfWords.cpp)|Medium|
5860
|804|[Unique Morse Code Words](https://leetcode.com/problems/unique-morse-code-words/description/) | [C++](./algorithms/cpp/uniqueMorseCodeWords/UniqueMorseCodeWords.cpp)|Easy|
5961
|771|[Jewels and Stones](https://leetcode.com/problems/jewels-and-stones/description) | [C++](./algorithms/cpp/jewelsAndStones/JewelsAndStones.cpp)|Easy|
6062
|747|[Largest Number At Least Twice of Others](https://leetcode.com/problems/largest-number-at-least-twice-of-others/) | [Python](./algorithms/python/LargestNumberAtLeastTwiceOfOthers/dominantIndex.py)|Easy|

‎algorithms/cpp/shortEncodingOfWords/ShortEncodingOfWords.cpp‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
// Source : https://leetcode.com/problems/short-encoding-of-words/
2+
// Author : Hao Chen
3+
// Date : 2020-10-02
4+
/*****************************************************************************************************
5+
*
6+
* Given a list of words, we may encode it by writing a reference string S and a list of indexes A.
7+
*
8+
* For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#"
9+
* and indexes = [0, 2, 5].
10+
*
11+
* Then for each index, we will recover the word by reading from the reference string from that index
12+
* until we reach a "#" character.
13+
*
14+
* What is the length of the shortest reference string S possible that encodes the given words?
15+
*
16+
* Example:
17+
*
18+
* Input: words = ["time", "me", "bell"]
19+
* Output: 10
20+
* Explanation: S = "time#bell#" and indexes = [0, 2, 5].
21+
*
22+
* Note:
23+
*
24+
* 1 <= words.length <= 2000.
25+
* 1 <= words[i].length <= 7.
26+
* Each word has only lowercase letters.
27+
*
28+
******************************************************************************************************/
29+
class Solution {
30+
public:
31+
static bool comp(string a,string b){
32+
return a.size() < b.size();
33+
}
34+
int minimumLengthEncoding(vector<string>& words) {
35+
sort(words.begin(),words.end(),comp);
36+
int ans = 0;
37+
int count = 0;
38+
unordered_map<string,int> M;
39+
for(int i = 0 ; i < words.size() ; i++){
40+
string temp = "";
41+
for(int k = words[i].size() - 1 ; k >= 0 ; k--){
42+
temp = words[i][k] + temp;
43+
M[temp]++;
44+
}
45+
}
46+
for(int i = 0 ; i < words.size() ; i++){
47+
ans = ans + words[i].size();
48+
count++;
49+
if(M[words[i]] > 1){
50+
ans = ans - words[i].size();
51+
count--;
52+
M[words[i]]--;
53+
}
54+
}
55+
return ans + count;
56+
}
57+
};

‎algorithms/cpp/timeNeededToInformAllEmployees/TimeNeededToInformAllEmployees.cpp‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
// Source : https://leetcode.com/problems/time-needed-to-inform-all-employees/
2+
// Author : Shreya Vanga
3+
// Date : 2020-10-02
4+
5+
/***************************************************************************************
6+
*
7+
* A company has n employees with a unique ID for each employee from 0 to n - 1.
8+
* The head of the company has is the one with headID.
9+
*
10+
* Each employee has one direct manager given in the manager array where manager[i] is
11+
* the direct manager of the i-th employee, manager[headID] = -1. Also it's guaranteed
12+
* that the subordination relationships have a tree structure.
13+
*
14+
* The head of the company wants to inform all the employees of the company of an urgent
15+
* piece of news. He will inform his direct subordinates and they will inform their
16+
* subordinates and so on until all employees know about the urgent news.
17+
*
18+
* The i-th employee needs informTime[i] minutes to inform all of his direct subordinates
19+
* (i.e After informTime[i] minutes, all his direct subordinates can start spreading the news).
20+
*
21+
* Return the number of minutes needed to inform all the employees about the urgent news.
22+
*
23+
* Example:
24+
*
25+
* Given: n = 1, headID = 0, manager = [-1], informTime = [0]
26+
* Return: 0
27+
*
28+
* Given: n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1]
29+
* Return: 21
30+
*
31+
***************************************************************************************/
32+
33+
34+
35+
36+
37+
class Solution {
38+
public:
39+
vector<int>visited;
40+
long long int dfs(vector<vector<int>>& adj, vector<int>& informTime, int src, int n)
41+
{
42+
long long int count = 0;
43+
for(int i=0;i<adj[src].size();i++)
44+
{
45+
count = max(count,dfs(adj, informTime, adj[src][i], n));
46+
}
47+
return (informTime[src]+count);
48+
}
49+
int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
50+
vector<vector<int>>adj(n);
51+
for(int i=0;i<manager.size();i++)
52+
{
53+
if(manager[i] != -1)
54+
adj[manager[i]].push_back(i);
55+
}
56+
long long int time;
57+
visited.resize(n,0);
58+
visited[headID] = 1;
59+
time= dfs(adj, informTime, headID, n);
60+
return time;
61+
}
62+
};

‎algorithms/python/uniquePaths/uniquePathsIII.py‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
# 980. Unique Paths III
2+
# On a 2-dimensional grid, there are 4 types of squares:
3+
4+
# 1 represents the starting square. There is exactly one starting square.
5+
# 2 represents the ending square. There is exactly one ending square.
6+
# 0 represents empty squares we can walk over.
7+
# -1 represents obstacles that we cannot walk over.
8+
# Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.
9+
10+
11+
12+
# Example 1:
13+
14+
# Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
15+
# Output: 2
16+
# Explanation: We have the following two paths:
17+
# 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
18+
# 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
19+
# Example 2:
20+
21+
# Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
22+
# Output: 4
23+
# Explanation: We have the following four paths:
24+
# 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
25+
# 2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
26+
# 3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
27+
# 4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
28+
# Example 3:
29+
30+
# Input: [[0,1],[2,0]]
31+
# Output: 0
32+
# Explanation:
33+
# There is no path that walks over every empty square exactly once.
34+
# Note that the starting and ending square can be anywhere in the grid.
35+
36+
37+
# Note:
38+
39+
# 1 <= grid.length * grid[0].length <= 20
40+
41+
class Solution:
42+
ans = 0
43+
def findPathNum(self, i, j, grid: List[List[int]], curLen, pLen)->None:
44+
if(grid[i][j]==2):
45+
if(pLen-1==curLen):
46+
self.ans+=1
47+
return
48+
elif (grid[i][j]==-1):
49+
return
50+
curLen+=1
51+
grid[i][j]=-1
52+
if(i-1>=0):
53+
self.findPathNum(i-1, j, grid, curLen, pLen)
54+
if(j-1>=0):
55+
self.findPathNum(i, j-1, grid, curLen, pLen)
56+
if(i+1<len(grid)):
57+
self.findPathNum(i+1, j, grid, curLen, pLen)
58+
if(j+1<len(grid[0])):
59+
self.findPathNum(i, j+1, grid, curLen, pLen)
60+
grid[i][j]=0
61+
62+
63+
def uniquePathsIII(self, grid: List[List[int]]) -> int:
64+
pathLen = 0
65+
start = (0, 0)
66+
for i in range(len(grid)):
67+
for j in range(len(grid[0])):
68+
if(grid[i][j]!=-1):
69+
pathLen+=1
70+
if(grid[i][j]==1):
71+
start = (i, j)
72+
self.findPathNum(start[0], start[1], grid, 0, pathLen)
73+
return self.ans
74+

0 commit comments

Comments
 (0)