整理字符串

给你一个由大小写英文字母组成的字符串 s 。

一个整理好的字符串中,两个相邻字符 s[i] 和 s[i + 1] 不会同时满足下述条件:

0 <= i <= s.length - 2
s[i] 是小写字符,但 s[i + 1] 是相同的大写字符;反之亦然 。

请你将字符串整理好,每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除,直到字符串整理好为止。

请返回整理好的 字符串 。题目保证在给出的约束条件下,测试样例对应的答案是唯一的。

注意:空字符串也属于整理好的字符串,尽管其中没有任何字符。

示例 1:

输入:s = “leEeetcode”
输出:”leetcode”
解释:无论你第一次选的是 i = 1 还是 i = 2,都会使 “leEeetcode” 缩减为 “leetcode” 。

示例 2:

输入:s = “abBAcC”
输出:””
解释:存在多种不同情况,但所有的情况都会导致相同的结果。例如:
“abBAcC” –> “aAcC” –> “cC” –> “”
“abBAcC” –> “abBA” –> “aA” –> “”

示例 3:

输入:s = “s”
输出:”s”

提示:

1 <= s.length <= 100
s 只包含小写和大写英文字母

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

class Solution {
public:

    string makeGood(string s) {
        if (s.empty() || s.length() == 1)return s;
        const char* cs = s.c_str();
        char* css = (char*)calloc(s.length()+1, 1);
        memcpy(css, cs, s.length());
        int index = 0;
        int length = s.length();
        while (index < length) {
            if (abs(css[index] - css[index + 1]) == 32) {
                memmove(css + index, css + index + 2, length - index - 2);
                css[length - 1] = 0;
                css[length - 2] = 0;
                length -= 2;
                index = index == 0 ? index : index - 1;
                continue;
            }
            index++;
        }
        return string(css);
    }
};
Posted in leetcode | Leave a comment

二叉树的右视图

给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

1 <—
/ \
2 3 <—
\ \
5 4 <—

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

class Solution {
public:
    int high;
    int currentHigh;
    set<TreeNode*> visited;

    void trv(TreeNode* root, vector<int>& sln, stack<TreeNode*>& sk) {
        if (root == NULL)return;
        visited.insert(root);

        if (currentHigh >= high) {
            sln.emplace_back(root->val);
            high++;
        }
        sk.push(root);
        currentHigh++;
        
        if (root->right != NULL)return trv(root->right, sln, sk);
        else if (root->left != NULL)return trv(root->left, sln, sk);
        else {
            sk.pop();
            currentHigh--;
            if (sk.empty())return;
            TreeNode* tp = move(sk.top());
            if (tp == NULL)return;
            while (tp->left == NULL || find(visited.begin(), visited.end(), tp->left) != visited.end()) {
                sk.pop();
                currentHigh--;
                if (sk.empty())return;
                tp = move(sk.top());
            }
            return trv(tp->left, sln, sk);

        }
    }

    vector<int> rightSideView(TreeNode* root) {
        stack<TreeNode*> sk;
        vector<int> sln;
        high = 0;
        currentHigh = 0;
        trv(root, sln, sk);
        return sln;
    }
};
Posted in leetcode | Leave a comment

最大连续1的个数

给定一个二进制数组, 计算其中最大连续1的个数。

示例 1:

输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1,所以最大连续1的个数是 3.

注意:

输入的数组只包含 0 和1。
输入数组的长度是正整数,且不超过 10,000。

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

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int max = 0;
        int numssize = nums.size();
        int localcounter = 0;
        for (int i = 0; i < numssize; i++) {
            if (nums[i] == 1) {
                localcounter++;
            }
            else {
                max = max > localcounter ? max : localcounter;
                localcounter = 0;
            }
        }
        max = max > localcounter ? max : localcounter;
        return max;
    }
};
Posted in leetcode | Leave a comment

统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。

如果某个 连续 子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例 1:

输入:nums = [1,1,2,1,1], k = 3
输出:2
解释:包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

示例 2:

输入:nums = [2,4,6], k = 1
输出:0
解释:数列中不包含任何奇数,所以不存在优美子数组。

示例 3:

输入:nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出:16

提示:

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

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

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int sum = 0;
        int numssize=nums.size();
        vector<int> oddindex;
        oddindex.emplace_back(-1);

        for (int i = 0; i < numssize; i++) {
            if (nums[i] % 2 != 0)oddindex.emplace_back(i);
        }
        oddindex.emplace_back(numssize);
        int oddindexsize=oddindex.size();
        if (k > oddindex.size() - 2)return 0;

        for (int i = 0; i < oddindexsize - 1 - k; i++) {
            sum += (oddindex[i + 1] - oddindex[i]) * (oddindex[i + k + 1] - oddindex[i + k]);
        }

        return sum;
    }
};
Posted in leetcode | Leave a comment

寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。

数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

示例 1:

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素,你的函数应该返回其索引 2。

示例 2:

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1,其峰值元素为 2;
或者返回索引 5, 其峰值元素为 6。

说明:

你的解法应该是 O(logN) 时间复杂度的。

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

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if (nums.size() == 1)return 0;

        int bg = 0;
        int nd = nums.size() - 1;
        int mid = bg + (nd - bg) / 2;
        while (mid != bg) {
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1])return mid;
            if (nums[mid + 1] > nums[mid - 1]) {
                bg = mid;
                mid = bg + (nd - bg) / 2;
            }
            else {
                nd = mid;
                mid = bg + (nd - bg) / 2;
            }
        }
        if (nums[mid] > nums[mid + 1])return mid;
        else return mid + 1;
    }
};

二分法也能用在无序线性容器中,在于,只要往大的一方走必定存在解

Posted in leetcode | Leave a comment

克隆图

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

图中的每个节点都包含它的值 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