完全二叉树的节点个数

问题描述

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

说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 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;
    }
};

分隔链表

问题描述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list

思路

借助了两个vector。

• 若是链表为空：直接返回nullptr即可。
• 链表不为空：遍历链表的过程中，将节点值小于x的存到一个vector中，将值大于等于x的存到一个vector中。
• 利用两个vector生成两个链表。

• 根据不同情况将两个链表拼接起来。

  小于x的链表为空，那么返回大于x链表的头节点即可
  大于等于x的链表为空，那么返回小于x链表的头节点即可
  两个都不空，将大于等于x的链表拼接到小于x的链表的后面
  两个链表都为空，即链表为空，在最开始特判过了。

题解

class Solution {
public:
    vector<int> tmp1;
    vector<int> tmp2;
    ListNode *head1;
    ListNode *head2;
    ListNode *ret;
    ListNode *buildList(vector<int> vec, ListNode *&node) {
        int n = vec.size();
        ListNode *p = nullptr;
        for (int i = 0; i < n; i++) {
            if (p == nullptr) {
                p = new ListNode(vec[i]);
                node = p;
            } else {
                p->next = new ListNode(vec[i]);
                p = p->next;
            }
        }
        return node;
    }

    ListNode *partition(ListNode *head, int x) {
        if (head == nullptr)
            return nullptr;
        ListNode *cur = head;
        while (cur != nullptr) {
            if (cur->val < x) tmp1.push_back(cur->val);
            else tmp2.push_back(cur->val);
            cur = cur->next;
        }
        int n1=tmp1.size();
        int n2 =tmp2.size();
        if(n1!=0) head1=buildList(tmp1,head1);
        if(n2!=0) head2=buildList(tmp2,head2);
        if(n1==0&&n2!=0) ret = head2;
        else if(n2==0&&n1!=0) ret =  head1;
        else {
            ListNode *tail=head1;
            while (tail->next!= nullptr){
                tail=tail->next;
            }
            tail->next=head2;
            ret = head1;
        }
        return ret;
    }
};