克隆图

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

图中的每个节点都包含它的值 valint) 和其邻居的列表(list[Node])。

class Node {
    public int val;
    public List<Node> neighbors;
}

测试用例格式:

简单起见,每个节点的值都和它的索引相同。例如,第一个节点值为 1(val = 1),第二个节点值为 2(val = 2),以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点(值为 1)。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

示例 1:

输入:adjList = [[2,4],[1,3],[2,4],[1,3]]
输出:[[2,4],[1,3],[2,4],[1,3]]
解释:
图中有 4 个节点。
节点 1 的值是 1,它有两个邻居:节点 2 和 4 。
节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
节点 4 的值是 4,它有两个邻居:节点 1 和 3 。

示例 2:

输入:adjList = [[]]
输出:[[]]
解释:输入包含一个空列表。该图仅仅只有一个值为 1 的节点,它没有任何邻居。

示例 3:

输入:adjList = []
输出:[]
解释:这个图是空的,它不含任何节点。

示例 4:

输入:adjList = [[2],[1]]
输出:[[2],[1]]

提示:

  1. 节点数不超过 100 。
  2. 每个节点值 Node.val 都是唯一的,1 <= Node.val <= 100
  3. 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
  4. 由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
  5. 图是连通图,你可以从给定节点访问到所有节点。
Posted in leetcode | Leave a comment

1431. 拥有最多糖果的孩子

给你一个数组 candies 和一个整数 extraCandies ,其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子,检查是否存在一种方案,将额外的 extraCandies 个糖果分配给孩子们之后,此孩子有 最多 的糖果。注意,允许有多个孩子同时拥有 最多 的糖果数目。

示例 1:

输入:candies = [2,3,5,1,3], extraCandies = 3
输出:[true,true,true,false,true]
解释:
孩子 1 有 2 个糖果,如果他得到所有额外的糖果(3个),那么他总共有 5 个糖果,他将成为拥有最多糖果的孩子。
孩子 2 有 3 个糖果,如果他得到至少 2 个额外糖果,那么他将成为拥有最多糖果的孩子。
孩子 3 有 5 个糖果,他已经是拥有最多糖果的孩子。
孩子 4 有 1 个糖果,即使他得到所有额外的糖果,他也只有 4 个糖果,无法成为拥有糖果最多的孩子。
孩子 5 有 3 个糖果,如果他得到至少 2 个额外糖果,那么他将成为拥有最多糖果的孩子。

示例 2:

输入:candies = [4,2,1,1,2], extraCandies = 1
输出:[true,false,false,false,false]
解释:只有 1 个额外糖果,所以不管额外糖果给谁,只有孩子 1 可以成为拥有糖果最多的孩子。

示例 3:

输入:candies = [12,1,12], extraCandies = 10
输出:[true,false,true]

提示:

2 <= candies.length <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/kids-with-the-greatest-number-of-candies
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

代码:


class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        auto m = max_element(candies.begin(),candies.end());

        int differece= *m-extraCandies;
        vector<bool> r(candies.size());
        std::transform(candies.begin(),candies.end(),r.begin(),[=](int i){return i>=differece? true:false;});
        return r;  
    }
};

用到的库函数

template< class ForwardIt >
ForwardIt max_element( ForwardIt first, ForwardIt last );

template< class InputIt, class OutputIt, class UnaryOperation >
OutputIt transform( InputIt first1, InputIt last1, OutputIt d_first, UnaryOperation unary_op );               

Posted in leetcode | Leave a comment

longest-mountain-in-array 数组中的最长山脉

题目描述:

我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”:

B.length >= 3
存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(注意:B 可以是 A 的任意子数组,包括整个数组 A。)

给出一个整数数组 A,返回最长 “山脉” 的长度。

如果不含有 “山脉” 则返回 0。

示例 1:

输入:[2,1,4,7,3,2,5]
输出:5
解释:最长的 “山脉” 是 [1,4,7,3,2],长度为 5。

示例 2:

输入:[2,2,2]
输出:0
解释:不含 “山脉”。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-mountain-in-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

int longestMountain(int* A, int ASize){
    int l=0;
    for (int turn=0;turn<ASize;turn++){
        //find up
        int i=turn;
        for (;i<ASize-1;i++){
            if(A[i]<A[i+1])continue;
            else break;
        }
        //find down
        int j=i;
        for (;j<ASize-1;j++){
            if(A[j+1]<A[j])continue;
            else break;
        }
        if(i==turn || i==j)continue;
        l=(l>j-turn+1?l:j-turn+1);
    }
    return l;
}

https://leetcode-cn.com/problems/longest-mountain-in-array/

Posted in leetcode | Leave a comment

博客建立了!

life-long 博客开通啦,记录想记录的事儿~

红旗镇楼
Posted in Uncategorized | Leave a comment