Welcome to lc_doc’s documentation!

Questions

2. Add two numbers

Lets write it down the example

  • (2 -> 2 -> 3)
  • (5 -> 6 -> 4)

seems like we can use one loop to iterate through the two link list at the same time but in case of different length of link lists, we need to check if node is Null each time when we jump to the next node

  • (2 -> 4 -> 3)
  • (5 -> 6 -> 4)

In the second situation when the sum of two digits is greater than 10, we just need the reminder of the sum and use a variable to carry digit 1 to the next node or nodes, lets call this variable carry.

  • (2 -> 2 -> 6)
  • (5 -> 6 -> 4)

In the third situation, when the we need to add new node even if we have reached the end of both linked list since the sum is of the last digits is more than 10. So for the loop, we can add one more criteria to check the variable carry is true or false. So when we reach the end of both linked list, if check is true, we create a new node and add one to the value of the node.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
/* Definition for singly-linked list. */
struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        bool carry = false;
        ListNode* result_p;
        ListNode* current_node;

        ListNode ln(0);
        result_p = &ln;
        current_node = &ln;

        ListNode* new_node_p;
        while(l1 || l2 || carry)
        {
            int sum = 0;
            sum = (l1 ? l1 -> val : 0) + (l2 ? l2 -> val: 0);
            if (carry) sum++;

            l1 = l1? l1->next: NULL;
            l2 = l2? l2->next: NULL;

            carry = (sum >= 10);
            current_node->next = new ListNode(sum % 10);
            current_node = current_node->next;
            int i = 2;
            int_p = &i;
        }
        // cout << "starting node: " << result_p->val << endl;
        return ln.next;
    }
};

While debugging, I found I cannot just create a new node in the while loop without using “new” key word. You can see the note here Dynamic Allocation

3. Longest Substring Without Repeating Characters

Sliding window with hash table

When I see substring problems what I would usually try is called sliding window. It uses two indexes representing the start and the end of a subtring. When they iterate through the target string, it is like a window sliding through the target string and the string inside of the window is what we are interested in.The contraint of the indexes are starting index should not be greater than of ending index.

Let’s assume that the starting index is j and ending index is i. The goal is to find the longest substring with unique characters. So, if we can not find any character in the window the same as the character indexed by i, we should expand the window include the character indexed by i. What if we find a character in the window the same as the character indexed by i, that means we have find the longest substring with current starting index j. If it is the longest substring we have ever seen, we update the result. After the comparison, we need to move j to duplicated character and go one step further, because if j is on or before the character, the subtring would be two same characters and it would be invalide.

In order to make the look up in substring fast, we can use a hash table to store the characters as keys and their locations or index as values. With hashtable, the lookup would be decreased to O(1) a constant.

Here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public:
      int lengthOfLongestSubstring(string s) {

          int i = 0, j = 0, max_length = 0;
          unordered_map<char, int> prev_char_map;
          while (i < s.length())
          {

              if (prev_char_map.find(s[i]) != prev_char_map.end())
              {
                  j = max(prev_char_map[s[i]] + 1, j) ;
              }
              max_length = max(max_length, i - j + 1);
              prev_char_map[s[i]] = i;
              i ++;
          }
          return max_length;
      }
  };

Here is what I found during implementing the code. We don’t need to delete the entry in the table hash table so that it always reflect the current substring, if we find an entry in the hash table, that means we have seen this character but if the value of the character in less than j, that means that character is not in the current substring anymore so that we can just ignore it and updated its value to the new index, which is i.

With that algorithm implemented, i would iterate through the string s one time and j, worst case senario would also iterate through the string s one time. The worst case is ‘aaaaaaaaaaaaa’. So the time complexity would be O(n). As for the space complexity, we need a hash table to store the character we have seen so far so that it wounl be O(min(len(s), m). m is the length of all possible characters.

Sliding window with array

If we can have the assumption on the characters such as that they are ASCII characters, we don’t need a hash table, instead we just need to use array with the size of 256.

6. ZigZag Conversion

Let’s write this example down. If we use the index of the string s instead of the characters. We can get the following example

0     6     12     …
1   5 7   11 13   17  
2 4   8 10   14 16    
4     9     15      

The distances betwenn two horizontally adjacent node

  • 1st row: 6, 6, 6, 6 ….
  • 2nd row: 4, 2, 4, 2, 4, 2 …
  • 3rd row: 2, 4, 2, 4, 2, 4 …
  • 4th row: 6, 6, 6, 6, 6, 6 …

This example give me some idea but I am still not clear what the pattern is. So I want more rows, we can have examples like this

0       8       16
1     7 9     15 17
2   6   10   14   18
3 5     11 13     19
4       12       20

The distances betwenn two horizontally adjacent nodes are

  • 1st row: 8, 8, 8, 8 ….
  • 2nd row: 6, 2, 6, 2 ….
  • 3rd row: 4, 4, 4, 4 ….
  • 4th row: 2, 6, 2, 6 ….
  • 5th row: 8, 8, 8, 8 ….

Now we have some ideas of the patterns:

  1. for the first and the last row, the distance is a constant: . If total row number is fixed, this number is fixed. Lets call this DistanceSum.
  2. For the rows that are in between the first and last rows, the neighbor number has two different distances. Those two distances take turns to apply to the index horizontally. The first distance is . The second distance is

Now if we generalize the two situations, we can get: every row uses two distances, one: , the other one: . But if we encounter 0 as distance, we change it to DistanceSum. Or you can also say switch it to another oposite distance.

Now we have the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;

class Solution {
public:
string convert(string s, int numRows) {
    int s_length = s.length();
    if (s_length == 0) return "";
    string result;
    int i = 0;
    int distance_sum = numRows * 2 - 2;
    if (distance_sum == 0) return s;
    for (int row = 0; row < numRows; row ++)
    {
        int distance = row * 2;
        cout << "------------row #: " << row << "-----------" << endl;
        int location = row;
        int i = 0;
        while(location < s_length)
        {
            cout << "Found valid index: " << location << ". ";
            result += s[location];
            distance = distance_sum - distance;
            if (distance == 0) distance = distance_sum;
            cout << "Add distance: " << distance << endl;
            location += distance;

       }
    }
    return result;
}
};

int main()
{
   Solution sol;
   string str = sol.convert("0123456789", 4);
   cout << "The result is " << str << endl;
   return 0;
}

11 Container With Most Water

Brute Force

When we look at the problem, I would think that this is a sliding window problem. The first idea of course is the brutal force way. Have a start index i and end index j. Iterating i and j like a sliding window on top of the vector. Everytime you will get the area value. The height of the container is going to be the min between height[i] and height[j]. The width is the j - i. The time complexity would be and the storage complexity is O(1) because you will only need to store the maximum value in a variable.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
     public:
         int maxArea(vector<int>& height) {
             int v_len = height.size();
             int max_volume = 0;
             for (int i = 0; i < v_len; i++)
             {
                 for (int j = 0; j < i; j ++)
                 {
                     // cout << "========= j: " << j <<  ", i: " << i << "============" <<endl;
                     int volume = get_volume(height, j, i);
                     // cout << "volume: " << volume << endl;
                     if (volume > max_volume) max_volume = volume;
                 }
             }
             return max_volume;
         }
         int get_volume(vector<int>& height, int start_indx, int end_indx)
         {
             int distance = end_indx - start_indx;
             int start_height = height[start_indx];
             int end_height = height[end_indx];
             // cout << "Start height: " << start_height << "end height" << end_height << endl;
             return ((start_height >= end_height)?end_height:start_height) * distance;
         }
     };

C++ Notes

Dynamic Allocation

Guess the output:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;

void main()
{
        int* a;
        for(int i = 0; i < 2; i ++)
        {
            int b = 0;
            a = &b;
            cout << "The address of the integer is " << a << endl;
        }

        cout << "-------------------------------------" << endl;
        int* c;
        for(int i = 0; i < 2; i ++)
        {
            c = new int(0);
            cout << "The address of the integer is " << c << endl;
        }
}

When you are creating an variable/object in for loop, because they are local, they are created in stack. When one loop is done, it will be removed from stack. If you are using “new” key word, you are creating the varible in heap, which will be removed at the end of the program unless you explicitly deallocate it, which is what you should do. Here is the detail of dynamic memory allocation .

So, as you know, the result of the code above is

1
2
3
4
5
The address of the integer is 00DEFCF0
The address of the integer is 00DEFCF0
-------------------------------------
The address of the integer is 012CF5F8
The address of the integer is 012CF658

Algorithms

Questions to ask

Don’t be smart ass. Always ask questions.

Are we only using ASCII code

A lot of time when we are using ASCII code, we can use an array of size 256 to represent attributes of a character. For example, the location or index of the character in a string. It is like a hash table, with key value pair. See question 3. Longest Substring Without Repeating Characters: Sliding window with hash table.

Indices and tables