- 665. Non-decreasing Array
- Input: [4,2,3]
- Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array. 递增
思路: 贪心思想, 找异常值, 存在两个以上则返回 false. 如果当前的值比前一的值小, 并且也比前两的值小, 此时只需更改当前值, 而不更改前两个值.
更改规则是用前一的值代替当前值.
两种情况
例如: 2 2 1 -》 2 2 2
0 2 1 -》 0 1 1
- bool checkPossibility(vector<int>& nums) {
- int cnt = 0; // 如果存在两个以上的异常值则直接返回 false
- for(int i = 1; i <nums.size() && cnt<=1 ; i++){
- if(nums[i-1]> nums[i]){ // 存在异常值
- cnt++;
- if(i-2<0 || nums[i-2] <= nums[i])nums[i-1] = nums[i]; //i-2 处理第一个边界值, 这种 || 技巧经常用到
- else nums[i] = nums[i-1]; //have to modify nums[i]
- }
- }
- return cnt<=1;
- }
- 669. Trim a Binary Search Tree
- Input:
- 3
- / 0 4
- 2
- /
- 1
- L = 1
- R = 3
- Output:
- 3
- /
- 2
- /
- 1
- The code works as recursion.
- If the root value in the range [L, R]
- we need return the root, but trim its left and right subtree;
- else if the root value <L
- because of binary search tree property, the root and the left subtree are not in range;
- we need return trimmed right subtree.
- else
- similarly we need return trimmed left subtree.
- Without freeing memory
- class Solution {
- public:
- TreeNode* trimBST(TreeNode* root, int L, int R) {
- if (root == NULL) return NULL;
- if (root->val <L) return trimBST(root->right, L, R);
- if (root->val> R) return trimBST(root->left, L, R);
- root->left = trimBST(root->left, L, R);
- root->right = trimBST(root->right, L, R);
- return root;
- }
- };
总结: 树的遍历 bfs, 一般结构:
当前 root
////////////////////////////
中间逻辑, 比如深一层的遍历
///////////////////////////
对当前 root 进行操作, 例如左右边子树的赋值操作
来源: http://www.bubuko.com/infodetail-2874365.html