剑指 Offer II 051. 节点之和最大的路径
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。
示例：
思路：
这个路径，可以是左子结点 根结点 右子结点。可以不包括root结点！！
不是简单的走完所有的路，求和！
要判断左右子树结点和是否有利于和最大，所以比较这是不是一个比0大的，起正向作用的。
注意，返回值是什么，走到空指针的时候，返回值应该是0，而不是max_num。以及走完一条路，返回的是根节点加左右子树中大的路径和。
代码：
一开始思路错误，求的所有的和，想改前缀和也不对。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int dfs(TreeNode* root,int& max_num){ if(root == nullptr) return 0; int left = max(0,dfs(root->left,max_num)); int right = max(0,dfs(root->right,max_num)); max_num = max(root->val + left + right,max_num); return root->val + max(left,right); } int maxPathSum(TreeNode* root) { int max_num = INT_MIN; dfs(root,max_num); return max_num; } // int dfs(TreeNode* root,int sums,int max_num) // { // i++; // if(root == nullptr) // { // // printf("%d ",sum); // return sum; // } // sum = dfs(root->left,sum,max_num); // sum = dfs(root->right,sum,max_num); // // if(root->left == nullptr && root->right == nullptr) // // { // sum[i] += root->val; // // if() // max_num = max(max_num,sum); // // } // printf("%d",max_num); // return sum; // } // int maxPathSum(TreeNode* root) { // // int vector<int> sums; // int sum = 0; // int max_num = 0; // // sums[0] = 0; // return dfs(root,sum,max_num); // } };
剑指 Offer II 008. 和大于等于 target 的最短子数组
题目描述：
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例：
思路：
直接滑动窗口，o（n）复杂度。
应该优化用前缀和加二分查找。
代码：
滑动窗口：
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int min_size = 99999999; int len = nums.size(); int right = 0; int left = 0; long long sum = 0; while(right < len) { sum += nums[right]; while(sum >= target) { min_size = min(min_size,right-left+1); // sum += nums[right]; sum -= nums[left]; left++; } right++; } return min_size < 99999999 ? min_size : 0; } };
前缀和+二分
class Solution { public: int bin_search(vector<int>& nums, int s, int e, int tar) { int l = s, r = e; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] >= tar) { r = mid; } else { l = mid + 1; } } if (nums[r] < tar) return -1; return r; } int minSubArrayLen(int target, vector<int>& nums) { for (int i = 1; i < nums.size(); ++i) { nums[i] += nums[i - 1]; } int sd = 0; int ans = INT_MAX; for (int i = 0; i < nums.size(); ++i) { // 需要在后续前缀和数组中搜索的值 if (i == 0) { sd = target; } else { sd = nums[i - 1] + target; } // 寻找第一个大于等于 sd 的值的位置 int idx = bin_search(nums, i, nums.size() - 1, sd); if (idx < 0) { break; } else { ans = min(ans, idx - i + 1); } } return ans == INT_MAX ? 0 : ans; } };
剑指 Offer II 016. 不含重复字符的最长子字符串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。
直接滑动窗口+set
// #include <algorithm> class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.length(); if(n == 1) return 1; if(n == 0) return 0; set<char> window; int max_size = 1; //这是一个窗口 int right = 0,left = 0; while(right < n) { if(window.count(s[right])) { window.erase(s[left]); left++; } else { window.insert(s[right]); max_size = max(int(window.size()),max_size); right++; } } return max_size; } };
