只出现一次的数字 III

问题描述

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]

注意：
结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-iii

思路

• 首先将数组进行排序

• 遍历一次数组

  首尾两个元素进行特判,看头元素是否不等于第二个元素，看尾元素是否不等于倒数第二个元素
  对于中间元素，看起是否不等于前一个元素，或者不等于后一个元素

题解

class Solution {
public:
    vector<int> singleNumber(vector<int> &nums) {
        vector<int> B;
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size() - 1; i++) {
            if (nums[i] != nums[i + 1] && nums[i] != nums[i - 1]) {
                B.push_back(nums[i]);
            }
        }
        if (nums[0] != nums[1]) {
            B.push_back(nums[0]);
        }
        if (nums[nums.size() - 2] != nums[nums.size()-1])
        {
            B.push_back(nums[nums.size()-1]);
        }
        return B;
    }
};

完全二叉树的节点个数

问题描述

给出一个完全二叉树，求出该树的节点个数。

说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例:

输入: 
    1
   / \
  2   3
 / \  /
4  5 6

输出: 6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-complete-tree-nodes

思路

基本思路就是用深度优先搜索遍历一次二叉树

题解

/**
 * 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:
    vector<int> res;
    int count=0;
    int countNodes(TreeNode* root) {
        dfs(root);
        return count;
    }
    void dfs(TreeNode *node){
        if(node== nullptr) return ;
        count++;
        if(node->left!= nullptr) dfs(node->left);
        if(node->right!= nullptr) dfs(node->right);
    }
};

翻转字符串里的单词 II

问题描述

给定一个字符串，逐个翻转字符串中的每个单词。

示例：
输入: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
输出: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

注意：
单词的定义是不包含空格的一系列字符
输入字符串中不会包含前置或尾随的空格
单词与单词之间永远是以单个空格隔开的
进阶：使用 O(1) 额外空间复杂度的原地解法。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-words-in-a-string-ii

思路

• 以空格为分隔，将每个单词提取出来。
• 按照单词之间的倒序顺序，但是单词内部的正常顺序，将单词存到ret中。
• 最后，返回ret即可。

题解

class Solution {
public:
    void reverseWords(vector<char> &s) {
        vector<char> ret;
        string tmp;
        vector<string> tmp1;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != ' ') {
                tmp += s[i];
            } else if (s[i] == ' ') {
                tmp1.push_back(tmp);
                tmp = "";
            }
        }
        tmp1.push_back(tmp);
        reverse(tmp1.begin(), tmp1.end());
        for (int i = 0; i < tmp1.size(); i++) {
            for (int j = 0; j < tmp1[i].length(); j++) {
                ret.push_back(tmp1[i][j]);
            }
            if (i != tmp1.size() - 1) {
                ret.push_back(' ');
            }
        }
        s=ret;
    }
};

翻转字符串里的单词

问题描述

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：
输入: "the sky is blue"
输出: "blue is sky the"

示例 2：
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 
进阶：
请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-words-in-a-string

思路

基本思路和之前做过的简化路径是一样的，只是这个更简单一些。
简化路径 https://www.irene.ink/archives/163/

题解

class Solution {
public:
    string reverseWords(string s) {
        string ret;
        int n=s.size();
        if(n==0) return ret;
        string tmp;
        stack<string> stack1;
        for(int i=0;i<n;i++){
            if(s[i]==' '){
                if(tmp!=""){
                    stack1.push(tmp);
                } 
                tmp="";
            } else{
                tmp+=s[i];
            }
        }
        if(tmp!=""){
            stack1.push(tmp);
            tmp="";
        }
        while (!stack1.empty()){
            ret+=stack1.top();
            ret+=" ";
            stack1.pop();
        }
        ret=ret.substr(0,ret.size()-1);
        return ret;
    }
};

搜索旋转排序数组 II

问题描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

进阶:
这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii

思路

用了一个很笨的方法。

遍历数组，用flag标记是否能找到目标值。

题解

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int flag=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==target){
                flag=1;
                break;
            }
        }
        if(flag==0){
            return false;
        }
        return true;
    }
};