import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; int[] dp1= new int[n]; int[] dp2 = new int[n]; for(int i=0;i<n;i++) { ...

class Solution { public: /** dp[i][j]以i，j结尾的最少操作数 dp[i][j]可以通过dp[i-1][j],dp[i][j-1], dp[i-1][j-1] 三种状态得到 */ int editDistance(string str1, string str2) { // write code here int len1 = str1.size(); int len2 = str2.size(); vector<vector&lt...

class Solution { public: /** 滚动数组 dp[i]:以i结尾的最长上升子序列 dp[i] = max(dp[j]+1,dp[i]) */ int LIS(vector<int>& arr) { // write code here int len = arr.size(); if(len==0) return 0; vector<int> dp(len, 1); for(int i=1; i<l...

class Solution { public: /** dp[i]:前i个字符编码 的结果 当nums[i]==0时不能单独存在只能依附nums[i-1] 当1<=nums[i-1]<=2 时 因为必须依附，反而减少，为dp[i-2] 否则组成不了 返回0 当nums[i]!=0, 可以不用依附。 当nums[i-1]+ nums[i] <= 26且nums[i-1]!=0 可以依附也可以不依附 dp[i] = dp[i-1] + dp[i-2] 否则 不能依附...

定义三个访问数组，列不能重复访问，正斜线不能重复访问， 反斜线不能重复访问。 其中正斜线用行下标减列下标唯一表示 总计2*N-1个，因为有负数结果，所以平移N-1位存储。 反斜线由行下标加列下标表示，也是2*N-1个。 class Solution { public: int N; int res=0; int Nqueen(int n) { // write code here if(n==1) return 1; N = n; // 写成了 int N = n， 全局变量已经声明了，又定义了一次，一直结果不对 ...

常规的dfs+记忆数组模板做法 class Solution { public: vector<int> order = {-1,0,1,0,-1}; // 递归方向 int rows; int cols; int solve(vector<vector<int> >& matrix) { int res=0; // write code here rows = matrix.size(); cols = matrix[0].size(); ...

class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { // write code here unordered_map<int, int> mp; for(int i=0; i<numbers.size(); i++){ int tmp = target - numbers[i]; if(mp.find(tmp) != mp.end())...

普通二叉树查找最近公共祖先 公共祖先 --- 后序遍历 递归左子树 和 递归右子树 如果找到指定需要的节点值p,q, 就返回该节点值，代表该子树有该值 如果没有找到在另一个子树中查找。 如果在两个子树中都找则代表为父亲节点直接返回 class Solution { public: int lowestCommonAncestor(TreeNode* root, int p, int q) { // write code here return order(root, p, q)->val; } TreeNode* order(Tre...

class Solution { public: /** 层次遍历 */ bool isCompleteTree(TreeNode* root) { // write code here if(root==NULL) return true; queue<TreeNode*> qu; qu.push(root); while(!qu.empty()){ TreeNode* tmp = qu.front(); qu.pop(...

1. 递归 class Solution { public: /** 中序遍历 保存中序遍历的前一个节点值 进行比较 */ TreeNode *pre = NULL; bool isValidBST(TreeNode* root) { bool flag = true; if(root==NULL) return true; bool left = isValidBST(root->left); if(pre && pre->val > root->...

分析： 最简单的是循环遍历O(n) 二分查找，O(log2n) 最左边和最右边为无穷小，当任意一个位置i上的值小于相邻i+1时，则左边必然存在峰值。 当任意一个位置i上的值大于相邻i+1时，右边必存在峰值。 class Solution { public: // 左右边为无穷小，所以 当前位 大于临近坐标 int findPeakElement(vector<int>& nums) { // 索引logn 二分查找 int len = nums.size(); int low=0, high=len-1; w...

class Solution { public: int search(vector<int>& nums, int target) { int len = nums.size(); int left=0, right=len-1; while(left <= right){ mid = left+(right-left >> 1); // +-大于位移运算的优先级 左移*2 if(nums[mid] == target) return mid; ...

class Solution { public: static bool cmp(int a, int b){ //高位位置排 string s_a = to_string(a); // 组合数最大用string判断 string s_b = to_string(b); return s_a+s_b > s_b+s_a; } string solve(vector<int>& nums) { // write code here string ans; ...

最长括号子串分为两种形式..()()()和...((...)) dp[i] :代表以i结尾的最长括号子串 ...（）dp[i]=dp[i-2]+2 当是s[i-1]='(' ...((..)) dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2 当s[i-dp[i-1]-1]='(' class Solution { public: int longestValidParentheses(string s) { int maxans = 0, n = s.length(); vector<int> dp(n, 0); ...