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
- A wall or an obstacle.0
- A gate.INF
- Infinity means an empty room. We use the value231 - 1 = 2147483647
to representINF
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++; } } } };
No comments:
Post a Comment