leetcode 刷题记

Construct Binary Tree from Preorder and Inorder Traversal 思路：1.先序第一个值简历root 2.找到左子树和右子树，递归构建 问题：内存溢出64 Minimum Path Sum 思路： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]) (i > 0,j > 0) dp[i][j] = dp[i][j-1] + grid[i][j]) (i == 0) dp[i][j] = dp[i-1][j] + grid[i][j]) (j == 0) 注意：条件的初始化和递归公式的精确性表达 二维vector 初始化： vector<vector<int> > ways(m, vector<int> (n, 1)); int minPathSum(vector<vector<int>>& grid) { if (grid.size() == 0) { return 0; } int rows = grid.size(); int cols = grid[0].size(); vector<vector<int>> sumgrid; for (int i = 0; i < rows; i++) { vector<int> row(cols, 0); sumgrid.push_back(row); } for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (i == 0 && j == 0) { sumgrid[i][j] = grid[i][j]; } else if (i == 0) { sumgrid[i][j] = sumgrid[i][j - 1] + grid[i][j]; } else if (j == 0) { sumgrid[i][j] = sumgrid[i- 1][j] + grid[i][j]; } else { sumgrid[i][j] = min(sumgrid[i - 1][j], sumgrid[i][j - 1]) + grid[i][j]; } } } return sumgrid[rows - 1][cols - 1]; } 216 Combination Sum III 思路：回溯 void combination(vector<vector<int>> &result, vector<int> ans, int k, int n) { if (ans.size() == k && n == 0) { result.push_back(ans); **return;** } if (ans.size() < k) { for (int i = ans.empty() ? 1 : ans.back() + 1; i <= 9; i++) { if (n - i < 0) { break; } **ans.push_back(i); combination(result, ans, k, n - i); ans.pop_back();** } } } vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> result; vector<int> ans; combination(result, ans, k, n); return result; }