头像

itdef

www.cnblogs.com/itdef


访客:96422

离线:8分钟前



itdef
2小时前

题目描述

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,
两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,
那么将他们的值相加作为节点合并后的新值,
否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
         3
        / \
       4   5
      / \   \ 
     5   4   7
注意: 合并必须从两个树的根节点开始。


算法1

还是使用树的遍历
如果两边均有节点 则节点值相加
如果只有一个节点 记录到答案中
(这里在递归遍历中返回处理结果会比较好,由于我采取的是答案直接放到第一颗树,导致使用了丑陋的指向指针的指针,仅做演示,不做推荐)
如果两边都没节点了 回溯

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:


void dfs(TreeNode** t1, TreeNode** t2) {
    //t1作为答案返回
    if (*t1 == NULL && *t2 == NULL) return;

    if (*t1 != NULL && *t2 == NULL) return;
    //t1没有节点 t2有 转移到t1上
    if (*t1 == NULL && *t2 != NULL) { *t1 = *t2; return; }

    if (*t1 != NULL && *t2 != NULL) {
        (*t1)->val += (*t2)->val;
    }
    dfs(&((*t1)->left), &((*t2)->left));
    dfs(&((*t1)->right), &((*t2)->right));
}

void printTree(TreeNode* t1)
{
    if (t1 == NULL) return;

    cout << t1->val << " ";

    printTree(t1->left);
    printTree(t1->right);
}


TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
    dfs(&t1,&t2);

    printTree(t1);

    return t1;
}


};




itdef
2小时前

题目描述

给定长度为N的数列A,然后输入M行操作指令。

第一类指令形如“C l r d”,表示把数列中第l~r个数都加d。

第二类指令形如“Q X”,表示询问数列中第x个数的值。

对于每个询问,输出一个整数表示答案。

输入格式
第一行包含两个整数N和M。

第二行包含N个整数A[i]。

接下来M行表示M条指令,每条指令的格式如题目描述所示。

输出格式
对于每个询问,输出一个整数表示答案。

每个答案占一行。

数据范围
1≤N,M≤105,
|d|≤10000,
|A[i]|≤1000000000
输入样例:
10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2
输出样例:
4
1
2
5

算法1

相比树状数组,线段树更简单明了 区域处理 区域求和
不必搞差分前缀等处理。
不过用树状数组 更能锻炼思维了.
线段树代码

C++ 代码

/*数据范围
1≤N, M≤105,
| d | ≤10000,
| A[i] | ≤1000000000
输入样例:
10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2
输出样例:
4
1
2
5

*/

#include <iostream>
#include <string>

using namespace std;



const int N = 1000007;
int arr[N];
int n; int q;


struct Node {
    int l;
    int r;
    long long sum, lazy;

    //该节点范围下所有节点增加x
    void update(long long x) {
        sum += (r - l + 1)*x;
        lazy += x;
    }
}tree[N*4];


void pushup(int x) {
    tree[x].sum = tree[x * 2].sum + tree[x * 2 + 1].sum;
}

void pushdown(int x)
{
    long long lazyval = tree[x].lazy;
    if (lazyval) {
        tree[x*2].update(lazyval);
        tree[x * 2 + 1].update(lazyval);
        tree[x].lazy = 0;
    }
}



void build(int x, int l, int r) {
    tree[x].sum = 0; tree[x].lazy = 0;
    tree[x].l = l; tree[x].r = r;
    if (l == r) {
        tree[x].sum = arr[l];
    }
    else {
        int mid = (l + r) / 2;
        build(x * 2, l, mid);
        build(x * 2+1, mid+1,r );
        pushup(x);
    }
}


void update(int x, int l, int r, int val)
{
    int L = tree[x].l; int R = tree[x].r;

    if (l <= L && r >= R) {
        tree[x].update(val);
    }
    else {
        pushdown(x);
        int mid = (L + R) / 2;
        if (l <= mid) update(x * 2, l, r, val);
        if (r > mid) update(x * 2 + 1, l, r, val);
        pushup(x);
    }
}

long long query(int x, int l, int r)
{
    int L = tree[x].l; int R = tree[x].r;
    if (l <= L && r >= R) {
        return tree[x].sum;
    }
    else {
        pushdown(x);
        int mid = (L + R) / 2;
        long long ans = 0;
        if (l <= mid) ans += query(x * 2, l, r);
        if (r > mid) ans += query(x * 2 + 1, l, r);

        return ans;
    }

    return 0;
}




int main()
{
    //cin >> n >> q;
    scanf("%d%d",&n,&q);

    for (int i = 1; i <= n; i++) {
        //cin >> arr[i];
        scanf("%d",&arr[i]);
    }
    build(1, 1, n);

    for (int i = 1; i <= q; i++) {
        //接收每次询问
        char type[2]; int l, r, val;
        scanf("%s%d",type,&l);

        if (type[0] == 'C') {
            //cin >> l >> r >> val;
            scanf("%d%d",&r,&val);
            update(1, l, r, val);
        }
        else {
            //cin >> l;
            //cout << query(1, l, l) << endl;
            printf("%lld\n", query(1, l, l));
        }
    }

    return 0;
}



新鲜事 原文

itdef
4小时前
对数据结构感兴趣而不是数学。 但是为了生活还得学习。 接下来不知道是学习数论呢?还是学习微积分 线代和概率?


新鲜事 原文

itdef
1天前
终于把线段树模板 背下能默写调对了。哎,真不容易


新鲜事 原文

itdef
1天前
啥时候acwing 也来个 ac多少题,去年至今提交XXX次。 让我自我感动下,hh
图片



itdef
1天前

题目描述

给定一个二叉树,我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。


示例 1:
输入:[0,0,null,0,0]
输出:1

111.png
解释:如图所示,一台摄像头足以监控所有节点。

示例 2:
输入:[0,0,null,0,null,0,null,null,0]
输出:2

222.png
解释:需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

提示:
给定树的节点数的范围是 [1, 1000]。
每个节点的值都是 0。

算法1

开始以为是树型DP 在考虑起始数值的时候发现要自根想叶子转移
叶子节点的状态肯定是要求被覆盖但是不会在叶子节点放置摄像机
而是在叶子节点的根上放置能够覆盖更多的点。
再列举了集中树的结构发现 均是如此,发现此题不是DP而是树的遍历和贪心

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
//1 表示已被覆盖
//2 表示需要被覆盖
//3 表示放置摄像机

int ans = 0;
int dfs(TreeNode* root)
{
    if (root == NULL) return 1;

    int l = dfs(root->left);
    int r = dfs(root->right);

    if (l == 1 && r == 1) return 2;
    if (l == 2 || r == 2) {
        ans++;
        return 3;
    }
    if( l==3 || r== 3) return 1;

    return -1;
}

int minCameraCover(TreeNode* root) {

    int r = dfs(root);
    if (r == 2) ans++;
    return ans;
}

};




itdef
2天前

题目描述

给你一个字符串 s ,请你拆分该字符串,并返回拆分后唯一子字符串的最大数目。

字符串 s 拆分后可以得到若干 非空子字符串 ,这些子字符串连接后应当能够还原为原字符串。
但是拆分出来的每个子字符串都必须是 唯一的 。

注意:子字符串 是字符串中的一个连续字符序列。

 

示例 1:

输入:s = "ababccc"
输出:5
解释:一种最大拆分方法为 ['a', 'b', 'ab', 'c', 'cc'] 。
像 ['a', 'b', 'a', 'b', 'c', 'cc'] 这样拆分不满足题目要求,
因为其中的 'a' 和 'b' 都出现了不止一次。
示例 2:

输入:s = "aba"
输出:2
解释:一种最大拆分方法为 ['a', 'ba'] 。
示例 3:

输入:s = "aa"
输出:1
解释:无法进一步拆分字符串。
 

提示:

1 <= s.length <= 16

s 仅包含小写英文字母


算法1

DFS尝试从短至长尝试每种分割
使用哈希记录使用过的分割 避免切分出相同的单词

C++ 代码

class Solution {
public:
unordered_set<string>dict;
int ans = -1;

void dfs(string s)
{
    if (s.empty()) {
        ans = max((int)dict.size(), ans);
        return;
    }

    for (int len = 1; len <= s.size(); len++) {
        string split = s.substr(0, len);
        if (dict.count(split) == 0) {
            dict.insert(split);
            dfs(s.substr(len ));
            dict.erase(split);
        }
    }
}

int maxUniqueSplit(string s) {
    dfs(s);
    return ans;
}
};



itdef
2天前

题目描述

给你一个字符串 text ,该字符串由若干被空格包围的单词组成。
每个单词由一个或者多个小写英文字母组成,并且两个单词之间至少存在一个空格。
题目测试用例保证 text 至少包含一个单词 。

请你重新排列空格,使每对相邻单词之间的空格数目都 相等 ,
并尽可能 最大化 该数目。
如果不能重新平均分配所有空格,请 将多余的空格放置在字符串末尾 ,
这也意味着返回的字符串应当与原 text 字符串的长度相等。

返回 重新排列空格后的字符串 。

 

示例 1:

输入:text = "  this   is  a sentence "
输出:"this   is   a   sentence"
解释:总共有 9 个空格和 4 个单词。
可以将 9 个空格平均分配到相邻单词之间,相邻单词间空格数为:9 / (4-1) = 3 个。
示例 2:

输入:text = " practice   makes   perfect"
输出:"practice   makes   perfect "
解释:总共有 7 个空格和 3 个单词。
7 / (3-1) = 3 个空格加上 1 个多余的空格。多余的空格需要放在字符串的末尾。
示例 3:

输入:text = "hello   world"
输出:"hello   world"
示例 4:

输入:text = "  walks  udp package   into  bar a"
输出:"walks  udp  package  into  bar  a "
示例 5:

输入:text = "a"
输出:"a"
 

提示:

1 <= text.length <= 100
text 由小写英文字母和 ' ' 组成
text 中至少包含一个单词


算法1

双指针分离单词和统计空格
然后构造答案

C++ 代码

class Solution {
public:
    string reorderSpaces(string text) {
    int l = 0; int r = 0; int space = 0;
    vector<string> words;
    while (l < text.size() && r < text.size()) {
        while (l < text.size()&& text[l] == ' ') { space++; l++; }
        if (l >= text.size()) break;
        r = l;
        while (r < text.size()&& text[r] != ' ') r++;
        string s = text.substr(l, r - l );
        words.push_back(s);
        l = r;
    }

    int spaPerWord = 0;

    if(words.size()>1)
        spaPerWord = space / (words.size() - 1);

    string ans;
    for (int i = 0; i < words.size(); i++) {
        ans += words[i];
        if (i == words.size() - 1) break;
        for (int j = 0; j < spaPerWord; j++) {
            ans += " ";
        }
    }

    int leftSpace = space - spaPerWord * (words.size() - 1);
    for (int j = 0; j < leftSpace; j++) {
        ans += " ";
    }
    return ans;
}
};





itdef
2天前

题目描述

给你一个正整数数组 arr ,请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中 所有奇数长度子数组的和 。

 

示例 1:

输入:arr = [1,4,2,5,3]
输出:58
解释:所有奇数长度子数组和它们的和为:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
示例 2:

输入:arr = [1,2]
输出:3
解释:总共只有 2 个长度为奇数的子数组,[1] 和 [2]。它们的和为 3 。
示例 3:

输入:arr = [10,11,12]
输出:66
 

提示:

1 <= arr.length <= 100
1 <= arr[i] <= 1000


算法1

考虑到前缀和 然后 如果起点终点之差为偶数也就是长度为奇数
累计相加即可

C++ 代码

class Solution {
public:
    int a[150];
    int sumOddLengthSubarrays(vector<int>& arr) {
        arr.insert(arr.begin(),0);
        for(int i = 1; i < arr.size();i++){
            a[i] = a[i-1]+arr[i];
        }
        int sum =0;
        for(int i = 1;i< arr.size();i++){
            for(int j = i;j < arr.size();j++){
                if( (j-i+1)%2 != 0 ){
                    sum += a[j]-a[i-1];    
                }   

            }
        }

        return sum;
    }
};





itdef
2天前

题目描述

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),
使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

 

例如:

输入: 原始二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13


算法1

还是树的遍历 根据搜索二叉树的性质
右节点值最大 根其次 左子树值最小
所有先更新右节点 更新当前的总和
再更新跟节点 再更新左节点

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sum =0;
    void dfs(TreeNode* root)
    {
        if(root==NULL) return;
        dfs(root->right);
        sum += root->val;   root->val = sum;
        dfs(root->left);
    }

    TreeNode* convertBST(TreeNode* root) {
        dfs(root);
        return root;
    }
};