只出现一次的数字 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;
    }
};

搜索旋转排序数组 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;
    }
};

二叉搜索树迭代器

问题描述

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

示例：

二叉搜索树迭代器.png

BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false

提示：
next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search-tree-iterator

思路

复杂度没满足要求...

因为二叉树是搜索二叉树，所以中序遍历的顺序即为从小到大的顺序。
设置一个全局变量的指针，指向下一个最小的数。
对于bool hasNEXT（）这一函数，当指针指向vec最后一个元素的下一个时，才return false，否则返回true即可。

题解

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

class BSTIterator {
private:
    vector<int> vec;
    int location;
public:
    void inorder(TreeNode *node){
        if(node == nullptr){
            return ;
        }
        inorder(node->left);
        vec.push_back(node->val);
        inorder(node->right);
    }
    BSTIterator(TreeNode* root) {
        inorder(root);
        location=0;
    }

    /** @return the next smallest number */
    int next() {
        if(location<vec.size()){
            return vec[location++];
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        if(location>=vec.size()){
            return false;
        } else return true;
    }
};

分数到小数

作者: ireneliu
时间: 2019-07-29
分类: 数组
评论

分数到小数

问题描述

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。

如果小数部分为循环小数，则将循环的部分括在括号内。

示例 1:
输入: numerator = 1, denominator = 2
输出: "0.5"

示例 2:
输入: numerator = 2, denominator = 1
输出: "2"

示例 3:
输入: numerator = 2, denominator = 3
输出: "0.(6)"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fraction-to-recurring-decimal

思路

在小数部分如果出现两次除数相同的情况即说明是循环小数.
来源：https://leetcode-cn.com/problems/fraction-to-recurring-decimal/solution/li-yong-hashbiao-ding-wei-xun-huan-by-just_coding/

题解

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        string ret;
        if (denominator == 0) return ret;
        if (numerator == 0) return "0";
        long long num = numerator;
        long long denom = denominator;

        if (num < 0 && denom > 0 || num > 0 && denom < 0) {
            ret += "-";
        }
        num = abs(num);
        denom = abs(denom);

        ret += to_string(num / denom);
        num = num % denom;

        if (num != 0) {
            ret += ".";
        }
        map<long long, int> table;
        int index = 0;
        while (num != 0 && table.find(num) == table.end()) {
            table[num] = index++;
            num *= 10;
            ret += to_string(num / denom);
            num %= denom;
        }
        if (table.find(num) != table.end()) {
            ret += "()";
            int cur = ret.size() - 2;
            while (index-- > table[num]) {
                swap(ret[cur], ret[cur - 1]);
                --cur;
            }
        }
        return ret;
    }
};

分类数组下的文章