Day 130, #282 #286 Expression Add Operators, Walls and Gates

Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples: 

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

---------------------------------------------------------------------------
COME_BACK
#1 这种for循环内的写法可以简化没有符合时的情况
如1234
1 _ 234
12_34
123_4
1234
-----------
from 1_234:
1_2_34
1_23_4
1_234
........

如果遇到“*”，则返回之前的操作（因为之前的运算符和值都已经存好）
1 + 2 * 3,之前 1 + 2已经算出为3，之前的运算符为+，值为2。然后此时 总值- 2 + 2 * 3
cur为当前的总值，op为之前运算符，val为上一步计算的值

class Solution {
public:
    int target;
    void dfs(vector<string> &rt,string num,int index,string sofar,long cur,string op,long val) {
        if (index == num.length() && target == cur) {
            rt.push_back(sofar);
        }
        
        for (int i = index; i < num.length(); i++) {
            string s = num.substr(index,i + 1 - index);
            if (s != to_string(stol(s))) continue;
            int now = stol(s);
            dfs(rt,num,i + 1,sofar + "+" + s,cur + now,"+",now);
            dfs(rt,num,i + 1,sofar + "-" + s,cur - now,"-",now);
            if (op == "-") {
                dfs(rt,num,i + 1,sofar + "*" + s,cur + val - val * now,op,val * now);
            }else if (op == "+") {
                dfs(rt,num,i + 1,sofar + "*" + s,cur - val + val * now,op,val * now);
            }else {
                dfs(rt,num,i + 1,sofar + "*" + s,val * now,op,val * now);
            }
        }
    }

    vector<string> addOperators(string num, int target) {
        vector<string> rt;
        this->target = target;
        
        for (int i = 1; i <= num.length(); i++) {
            string s = num.substr(0,i);
            if (s != to_string(stol(s))) continue;
            dfs(rt,num,i,s,stol(s),"",stol(s));
        }
        
        return rt;
    }
};

Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

------------------------------------------------------------------------
找出所有的gate，然后同时bfs

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size();
        if (m == 0) return;
        int n = rooms[0].size();
        queue<pair<int,int>> que;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    que.push(make_pair(i,j));
                }
            }
        }
        
        int size = que.size();
        int dis = 1;
        while (!que.empty()) {
            int row = que.front().first;
            int col = que.front().second;
            size--;
            que.pop();
           
            if (row + 1 < m && rooms[row + 1][col] > dis) {
                rooms[row + 1][col] = dis;
                que.push(make_pair(row + 1,col));
            }
            if (row - 1 >= 0 && rooms[row - 1][col] > dis) {
                rooms[row - 1][col] = dis;
                que.push(make_pair(row - 1,col));
            }
            if (col + 1 < n && rooms[row][col + 1] > dis) {
                rooms[row][col + 1] = dis;
                que.push(make_pair(row,col + 1));
            }
            if (col - 1 >= 0 && rooms[row][col - 1] > dis) {
                rooms[row][col - 1] = dis;
                que.push(make_pair(row,col - 1));
            }
            
            if (size == 0) {
                size = que.size();
                dis++;
            }
        }
    }
};