int minFallingPathSum2(vector<vector<int>>& A) { int row = A.size(); if(row == 0) return 0; if(row == 1) return A[0][0]; int col = A[0].size(); vector<vector<int>> dp(row+1,vector<int> (col+1,INT32_MAX)); for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ if(i==0...

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如，给定三角形： [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。   如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算***很加分。  使用二维数组的dp动态规划 dp[i][j]表示走到第i行j列的最小路径和 则转移方程 dp[i][j] = min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]; 因为只能上一层的左和右两个元素可以走到[i...

给定一个未排序的整数数组，找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。  时间复杂度为O(n)，则只能用空间复杂度去换取，可以使用hash表去 找左右值是否存在 class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> s(nums.begin(), nums.end()); int maxLen ...

使用 dp[i][j] 存储走到i,j时 总可能的路径数 因为只可以向下向右走，则任意点的路径数为dp[i][j] = dp[i-1][j] + dp[i][j-1]; dp初始化最上面一排和最左面一排，因为只可以向右走和向下走，所以初始化路径数都为1，其它为0 class Solution { public: int uniquePaths(int m, int n) { int dp[m][n]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++) { if( i==0 || j==0) dp[i][j] = 1; else dp[i][j] ...

文章目录    53. 最大子序和 198. 打家劫舍 322. 零钱兑换     53. 最大子序和 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。  DP法 // 使用dp[i] 记录到第i个元素的最大子序列和 class Solution { public: int maxSubArray(vector<int>& nums) { if(nums.size() == 0) retur...

定义在函数体内的内置类型的对象(局部变量)，如果没有显示初始化，则其值是未定义的，访问它是危险的int a2[10];  如果使用static修饰(局部静态变量)，则会自动初始化成默认值0 static int a4[10];  或者手动初始化，初始化个数小于数组长度的，剩余元素会自动初始化成默认值0 int a3[10] = {1};  全局变量的内置类型会自定初始化为默认值0，int a[10];  memset 初始化数组的误区   memset 是按字节对内存块进行初始化的函数，用来给某一块内存空间进行赋值的；  memset 作用是在一段内存块中填充某个给定的值，它是对较大的结构体或...

文章目录    698. 划分为k个相等的子集 130. 被围绕的区域 137 只出现一次的数字II 473 515. 在每个树行中找最大值 98. 验证二叉搜索树 109. 有序链表转换二叉搜索树     698. 划分为k个相等的子集 给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。 示例 1： 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出： True 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。  1 <= k <= len(nums) ...

os.getcwd() 获取当前工作目录，即当前python脚本工作的目录路径 os.chdir("dirname") 改变当前脚本工作目录；相当于shell下cd os.curdir 返回当前目录: ('.') os.pardir 获取当前目录的父目录字符串名：('..') os.makedirs('dirname1/dirname2') 可生成多层递归目录 os.removedirs('dirname1') 若目录为空，则删除，并递归到上一级目录，如若也为空，则删除，依此类推 os.mkdir('dirname') 生成单级目录；相当于shell中mkdir dirna...

文章目录   113 路径总和 II 129. 求根到叶子节点数字之和 124. 二叉树中的最大路径和 404- 左叶子之和(easy) 513. 找树左下角的值()    113 路径总和 II  class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector<int>> res; vector<int> tmp; if(!root) return res; if(root->val==sum &...

Sort  默认使用less排序，从小到大排序，可以自定义排序方法   less() //从小到大排序 < grater() //从大到小排序 > less_equal() // <= gtater_equal()// >=  >从大到小排序 <从小到大排序 static bool cmp2(int a,int b){ return a > b;} // >从大到小排序 <从小到大排序  Priority_queue priority_queue< int, vector<int>, cmp> pq; 三个参数 数据...

文章目录   347-前 K 个高频元素 根据字符出现频率排序 692. 前K个高频单词 973 最接近0的点  1046. 最后一块石头的重量 215. 数组中的第K个最大元素     347-前 K 个高频元素  topk （前k大）用小根堆，维护堆大小不超过 k 即可。每次压入堆前和堆顶元素比较，如果比堆顶元素还小，直接扔掉，否则压入堆。检查堆大小是否超过 k，如果超过，弹出堆顶。复杂度是 nlogk 避免使用大根堆，因为你得把所有元素压入堆，复杂度是 nlogn，而且还浪费内存。如果是海量元素，那就挂了。  [注意]  求前 k 大，用小根堆，求前 k 小，用大根堆。面试的时候如果说反...

279-完全平方数 #include <iostream> #include <vector> #include <queue> using namespace std; class Solution { public: int numSquares(int n) { int res = 0; if(n <= 0) return 0; queue< pair<int,int> > q; // 如果访问过了，就放弃第二次访问 vector<bool> visited(n+1,false); q.push(make_pa...