for Robot Artificial Inteligence

59. number of islands [어려움]

30 Jul 2020 | Daily Algorithms

  • I saw many people post DFS solutions but fewer BFS ones. So I wrote one below. Each time when I see a ‘1’, I increment the counter and then erase all connected ‘1’s using a queue.

BFS methods

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(); // row
        int n = m ? grid[0].size() : 0; // column
        int islands = 0;
        int offsets[] = {0,1,0,-1,0};
        for(int i =0; i<m;i++)
        {
            for(int j=0; j<n; j++)
            {
                if(grid[i][j]=='1')
                {
                    islands++;
                    grid[i][j] = '0';
                    queue<pair<int,int>> todo;
                    todo.push({i,j});
                    while(!todo.empty())
                    {
                        pair<int,int> p = todo.front();
                        todo.pop();
                        for(int k =0; k<4; k++)
                        {
                            int r = p.first + offsets[k];
                            int c = p.second + offsets[k+1];
                            if(r>=0 && r<m && c>=0 && c<n && grid[r][c]=='1')
                            {
                                grid[r][c] = '0';
                                todo.push({r,c});
                            }
                        }
                    }

                }
            }
        }
        return islands;
    }
};

DFS

  • Or I can erase all the connected ‘1’s using DFS
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = m ? grid[0].size() : 0, islands = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    islands++;
                    eraseIslands(grid, i, j);
                }
            }
        }
        return islands;
    }
private:
    void eraseIslands(vector<vector<char>>& grid, int i, int j) {
        int m = grid.size(), n = grid[0].size();
        if (i < 0 || i == m || j < 0 || j == n || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        eraseIslands(grid, i - 1, j);
        eraseIslands(grid, i + 1, j);
        eraseIslands(grid, i, j - 1);
        eraseIslands(grid, i, j + 1);
    }
};

Comment  Read more

58. Valid Parenthesis String[중간]

30 Jul 2020 | Daily Algorithms

  • Since * can be used as 3 kinds of char, if we do backtrack the complexity can blow up if the string is ***…. We need to find **a non-trivial method.(Nontrivial is a favorite word among programmers and computer people for describing any task that is not quick and easy to accomplish. It may mean “extremely” difficult and time consuming.)

  • Without * , we can just use a number to indicate the unmatch (, ( will increment it and ) will decrement it. We don’t want this number less than 0 all the time and it should be 0 when all the string has been matched.

  • When * is introduced, the number becomes a range, indicating the number of possible unmatched ( found. One * just expand the range by 1. And we can use the same principle to check if the criteria above is within the range.


class Solution {
public:
    bool checkValidString(string s) {
        int lower = 0, upper = 0;
        for(auto c : s )
        {
            if(c=='(')
            {
                lower++;
                upper++;
            }
            else if( c == ')')
            {
                lower--;
                upper--;
            }
            else // enconuter '*'
            {
                lower--;
                upper++;
            }
            lower = max(lower,0);
            if(upper<0) // unmatched ')' found in the middle of string
                return false;
        }
        return lower == 0;

    }
};

Comment  Read more

57. Product of Array Except Self[문제 이해 어려움]

24 Jul 2020 | Daily Algorithms

  • 이 문제는 배열의 각 인덱스에서 자신을 제외한 나머지 숫자들의 곱을 넣어주는 문제입니다.
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> fromBegin(n);
        fromBegin[0]=1;
        vector<int> fromLast(n);
        fromLast[0]=1;

        for(int i=1;i<n;i++){
            fromBegin[i]=fromBegin[i-1]* nums[i-1];
            fromLast[i]=fromLast[i-1]* nums[n-i];
        }

        vector<int> res(n);
        for(int i=0;i<n;i++){
            res[i]=fromBegin[i]* fromLast[n-1-i];
        }
        return res;
    }
};

Comment  Read more

56. Contiguous Array[어려움]

20 Jul 2020 | Daily Algorithms 

int findMaxLength(vector<int>& nums) {
       int sum=0;
       unordered_map<int,int> m;
       unsigned int longestContArray = 0;

        for(int i=0;i<nums.size();i++){
           sum += (nums[i]==0)?-1:1;

           auto it = m.find(sum); // 이것이 else if(it==m.end)하고 연관이 있다.

           if(sum == 0){
              if(longestContArray < i+1)
               longestContArray = i+1;
           }
           else if(it != m.end()){ // 만약 있으면 it의 값이 m의 end까지
              if(longestContArray < i-it->second)
               longestContArray = i-it->second;
           }
           else if(it == m.end()) // 만약 없으면 it이 m.end까
                m.insert({sum,i});
       }
        return longestContArray;
    }

Process

  1. Starting from left of array and keep adding elements to a variable sum
  2. Add -1 for 0 and 1 for 1
  3. Now, every time sum becomes zero, we know all the elements from beginning of array have been neutralized , meaning we have got equal number of ones and zeroes, let this occurs at index i, so longestContArray = i+1 (‘coz w’re dealing with indices)
  4. But we are not done yet!, consider the case : [1,1,0,1,1]
    • In this case sum will never become zero,
    • but there exists a subarray of length 2, having equal 0 & 1
    • let’s see the value of sum at index : 1 and 3
    • Ohh!! sum = 2 for both indices
    • what does this mean???
    • This means that if we get the same sum value for two indices i and j, then all the elements within the range [i,j) or (i,j] have been neutralized
    • What datastructure can remember the sum and index
    • Ofcourse ! Map, so we use a map to store the sum and index values,
    • if sum == 0 then we have already solved the cases
    • but if sum!=0 and this sum doesn’t already exist in the map, then store it with it’s corresponding index
    • but if sum !=0 and sum already exists in the map then, depending on whether i - m[sum] > LongestContArray, update LongestContArray
    • Note we need to store a unique sum value only once, after that whenever we encounter the same sum again our interval length is going to increase only and that is what we want
    • ex- [1,0,1,0,1] we get sum = 1 three times we store sum = 1 for index = 0 only and never update it as we want longest length

Comment  Read more

55. Last Stone Weight

20 Jul 2020 | Daily Algorithms

priority_queue

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq(begin(stones),end(stones)); // 즉 오름차순으로 정렬(112478)

        while(pq.size()>1)
        {
            int x = pq.top();
            pq.pop();
            int y = pq.top();
            pq.pop();
            if(x>y)
                pq.push(x-y);
        }
        return pq.empty() ? 0 : pq.top();

    }
};

Comment  Read more