Let’s continue…
Problem Statement:
Divide Two Integers
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.
Example 1:
Input: dividend = 10, divisor = 3 Output: 3
Example 2:
Input: dividend = 7, divisor = -3 Output: -2
Note:
- Both dividend and divisor will be 32-bit signed integers.
- The divisor will never be 0.
- Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.
Solution:
Solution is found here: https://leetcode.com/problems/divide-two-integers/discuss/13407/Detailed-Explained-8ms-C%2B%2B-solution
This is a problem which aims at testing your understanding about how integers are stored in a modern computer. In this problem, since we cannot use *, /, or %, so we can utilize bit operations.
The general idea is like we first convert both the dividend and divisor to positive numbers, then the quotient should be the number of maximum times when the dividend can subtract divisor without becoming a negative number.
As for the sign, we can simply save the sign when we convert the numbers to positive numbers, before we return the final result, we can judge whether the final answer should be positive or negative. The only problem we need to care about is the range of int value, which is [-2^31 ~ 2^31 – 1], which is [-2147483648 ~ 2147483647]. If we get the overflow, such as the dividend is -2^31, while the divisor is -1, or divisor is 0, then we have to return 2^31 – 1. This is a special case we need to care about.
==========================================================================
Bit operations are simple, we can improve our skills with some practice:
| Operator | Symbol | Form | Operation |
|---|---|---|---|
| left shift | << | x << y | all bits in x shifted left y bits |
| right shift | >> | x >> y | all bits in x shifted right y bits |
| bitwise NOT | ~ | ~x | all bits in x flipped |
| bitwise AND | & | x & y | each bit in x AND each bit in y |
| bitwise OR | | | x | y | each bit in x OR each bit in y |
| bitwise XOR | ^ | x ^ y | each bit in x XOR each bit in y |
I want to go through all of them before we move forward.
Note: In the following examples, we will generally be working with 4-bit binary values. This is for the sake of convenience and keeping the examples simple. In C++, the number of bits used will be based on the size of the data type (8 bits per byte).
Left shift and right shift
The bitwise left shift (<<) operator shifts bits to the left. The left operand is the expression to shift, and the right operand is an integer number of bits to shift by. So when we say 3 << 1, we are saying “shift the bits in the literal 3 left by 1 place”.
For example, consider the number 3, which is binary 0011:
3 = 0011
3 << 1 = 0110 = 6
3 << 2 = 1100 = 12
3 << 3 = 1000 = 8
As you can see, if we have sufficient bits, when we left shift 1 bit from the original integer, the integer value will double. For bitwise right shift, it is the reversed result.
Note that in the third case, we shifted a bit off the end of the number! Bits that are shifted off the end of the binary number are lost forever.
Bitwise NOT
The bitwise NOT operator (~) is perhaps the easiest to understand of all the bitwise operators. It simply flips each bit from a 0 to a 1, or vice versa. Note that the result of a bitwise NOT is dependent on what size your data type is!
Assuming 4 bits:
4 = 0100
~4 = 1011 = 11 (decimal)
Bitwise AND, OR, and XOR
Bitwise AND (&) and bitwise OR (|) work similarly to their logical AND and logical OR counterparts. However, rather than evaluating a single boolean value, they are applied to each bit! For example, consider the expression 5 | 6. In binary, this is represented as 0101 | 0110. To do (any) bitwise operations, it is easiest to line the two operands up like this:
0 1 0 1 // 5 0 1 1 0 // 6
and then apply the operation to each column of bits. If you remember, logical OR evaluates to true (1) if either the left or the right or both operands are true (1). Bitwise OR evaluates to 1 if either bit (or both) is 1. Consequently, 5 | 6 evaluates like this:
0 1 0 1 // 5 0 1 1 0 // 6 ------- 0 1 1 1 // 7
Our result is 0111 binary (7 decimal).
Bitwise AND works similarly. Logical AND evaluates to true if both the left and right operand evaluate to true. Bitwise AND evaluates to true only if both bits in the column are 1. Similarly, we can do the same thing to compound AND expressions, such as 1 & 3 &7. If all of the bits in a column are 1, the result of that column is 1.
0 0 0 1 // 1 0 0 1 1 // 3 0 1 1 1 // 7 -------- 0 0 0 1 // 1
The last operator is the bitwise XOR (^), also known as exclusive or. When evaluating two operands, XOR evaluates to true (1) if one and only one of its operands is true (1). If neither or both are true, it evaluates to 0. Consider the expression 6 ^ 3:
0 1 1 0 // 6 0 0 1 1 // 3 ------- 0 1 0 1 // 5
It is also possible to evaluate compound XOR expression column style, such as 1 ^ 3 ^ 7. If there are an even number of 1 bits in a column, the result is 0. If there are an odd number of 1 bits in a column, the result is 1.
0 0 0 1 // 1 0 0 1 1 // 3 0 1 1 1 // 7 -------- 0 1 0 1 // 5
Bitwise assignment operators
As with the arithmetic assignment operators, C++ provides bitwise assignment operators in order to facilitate easy modification of variables.
| Operator | Symbol | Form | Operation |
|---|---|---|---|
| Left shift assignment | <<= | x <<= y | Shift x left by y bits |
| Right shift assignment | >>= | x >>= y | Shift x right by y bits |
| Bitwise OR assignment | |= | x |= y | Assign x | y to x |
| Bitwise AND assignment | &= | x &= y | Assign x & y to x |
| Bitwise XOR assignment | ^= | x ^= y | Assign x ^ y to x |
For example, instead of writing x = x << 1;, you can write x <<= 1;.
============================================================================
OK, so let’s go to our code… I will add comments for the code.
Time Complexity: O(log n) n is the number of how many times we need to subtract dividend in order to make it negative.
Space Complexity: O(1)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int divide(int dividend, int divisor) { | |
| //First check whether the final result will encounter overflow | |
| if(!divisor || (dividend == INT_MIN && divisor == –1)) | |
| return INT_MAX; | |
| //We use long to store the final reslut, | |
| //because we convert the negative number to positive | |
| //If dividend is -2^31, we need to make sure that we will not have overflow | |
| long divd = labs(dividend); | |
| long divs = labs(divisor); | |
| //Save the sign, if both of them or neither of them are negative, | |
| //bit xor operation will return flase, sign will be 1. | |
| int sign = ((dividend<0)^(divisor<0))?-1:1; | |
| int finalRes = 0; | |
| while(divd>=divs){ | |
| long temp = divs; | |
| int multiple = 1; | |
| //We update temp to 2* temp every time, in oder to save time | |
| //We use the myltiple to keep track of how many times we have shifted our temp, | |
| //We use bit left shift to synchrosize the operation, for each for loop, | |
| //we can say that 2 * previous multiple divisor can be subtracted from the dividend. | |
| //multiple will add to final result | |
| while(divd>=(temp<<1)){ | |
| temp = temp<<1; | |
| multiple = multiple<<1; | |
| } | |
| //If dividend – temp is still greater than divisor, we need to calculate from multiple = 1 again. | |
| divd -= temp; | |
| finalRes += multiple; | |
| } | |
| return sign>0? finalRes:-finalRes; | |
| } | |
| }; |
Problem Statement:
Sub string with concatenation of all words
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Example 1:
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9] Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively. The output order does not matter, returning [9,0] is fine too.
Example 2:
Input:
s = "wordgoodstudentgoodword",
words = ["word","student"]
Output: []
Solution:
The general idea for this solution: We allocate two hash tables, in the first hash table counts, we store the number of all the unique words from vector words. We use every single word as the key, and the frequency of that word is the value.
Then we scan the string s, we compare each sub string, and test whether all the words in the sub string matches the number of words from the hash table counts, if it matches, then we store the first index of this sub string, if not, we move forward, and test the next sub string.
We can use the second hash table detect to do the comparing string job, whenever in the sub string we encounter a word which is from words, we store them in the detect hash table, and increase its frequency by 1, if the frequency is greater than the number of words in counts, we can safely say this sub string does not work. We can break the loop and move forward. Another situation is we cannot find a word from the sub string which is the same as the word from vector words, we can move forward as well.
Look at the picture below, we are pretty sure in this case, the length of sub string should be 6 (2 * 3), so we need to compare every sub string until the end of the string s.
Let’s see a live demo for the code:
If we have the string s and words like the picture below, we first store all the words from vector words to hash table 1 (the value is frequency of each words):
Then we compare the first sub string, since “foo” is in hash table 1, we update the hash table 2 with the new word “foo” and it occurs once, which means its frequency is less than or equal to the frequency of “foo” in hash table 1. Then we can keep moving.
We compare the second sub string, which is “foo” as well. So we update the frequency of “foo” in hash table 2, since the frequency is still equal to the frequency from table 1, and the final sub string contains less than 3 words, we keep moving.
OK, this time, it’s “foo” again, and the frequency is greater than the frequency from hash table 1, we have to break here, cause this sub string is not valid.
Let’s see the code:
Time Complexity: O(n*m) n is the number of characters in the string s, and m is the number of words in the vector words;
Space Complexity: O(m)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| vector<int> findSubstring(string s, vector<string>& words) { | |
| vector<int> indices; | |
| if(s.size() == 0 || words.size() == 0) | |
| return indices; | |
| unordered_map<string, int> counts; | |
| for(string word: words){ | |
| counts[word]++; | |
| } | |
| int len_s = s.length(), numW = words.size(), len_w = words[0].size(); | |
| for(int i = 0; i< len_s – numW*len_w + 1; i++){ | |
| unordered_map<string, int> detect; | |
| int j = 0; | |
| for(; j < numW; j++){ | |
| string tempW = s.substr(i + j*len_w, len_w); | |
| if(counts.find(tempW)!=counts.end()){ | |
| detect[tempW]++; | |
| if(detect[tempW]>counts[tempW]) | |
| break; | |
| } | |
| else | |
| break; | |
| } | |
| if(j == numW) indices.push_back(i); | |
| } | |
| return indices; | |
| } | |
| }; |
Actually, this is not the most optimal solution, currently, we iterate characters from s one by one, which is not good. We can optimize the time complexity and change it to O(n). A beautiful solution is here: https://leetcode.com/problems/substring-with-concatenation-of-all-words/discuss/13656/An-O(N)-solution-with-detailed-explanation%E3%80%82
That’s all for today…
Jun Zhang 