C/C++每日一练(20230514) 全排列、分数转小数、排序链表去重II

2023-05-29 107 发布于吉林

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： C/C++每日一练(20230514) 全排列、分数转小数、排序链表去重II

1. 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

以下程序实现了这一功能，请你填补空白处内容：

···

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<vector<int>> res;
        vector<bool> used(nums.size());
        dfs(nums, used, res);
        return res;
    }
private:
    vector<int> stack;
    void dfs(vector<int> &nums, vector<bool> &used, vector<vector<int>> &res)
    {
        if (stack.size() == nums.size())
        {
            res.push_back(stack);
        }
        else
        {
            for (int i = 0; i < nums.size(); i++)
            {
                if (!used[i])
                {
                    _______________;
                }
            }
        }
    }
};
···

出处：

https://edu.csdn.net/practice/27810770

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<vector<int>> res;
        vector<bool> used(nums.size());
        dfs(nums, used, res);
        return res;
    }
private:
    vector<int> stack;
    void dfs(vector<int> &nums, vector<bool> &used, vector<vector<int>> &res)
    {
        if (stack.size() == nums.size())
        {
            res.push_back(stack);
        }
        else
        {
            for (int i = 0; i < nums.size(); i++)
            {
                if (!used[i])
                {
                    used[i] = true;
                    stack.push_back(nums[i]);
                    dfs(nums, used, res);
                    stack.pop_back();
                    used[i] = false;
                }
            }
        }
    }
};
string Vector2dToString(vector<vector<int>> vec2d, string sep = ",")
{
    stringstream ss;
    ss << "[";
    for (int i = 0; i < vec2d.size(); ++i) {
        ss << "[";
        copy(vec2d[i].begin(), vec2d[i].end(), ostream_iterator<int>(ss, sep.c_str()));
    ss.seekp(-(int)sep.size(), ios_base::end);
        ss << "]" << sep;
    }
    ss.seekp(-(int)sep.size(), ios_base::end);
    ss << "]";
    return ss.str();
}
int main()
{
  Solution s;
  vector<int> nums = {1,2,3};
  cout << Vector2dToString(s.permute(nums)) << endl;
  return 0;
}

输出：

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

2. 分数到小数

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

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

如果存在多个答案，只需返回任意一个。

对于所有给定的输入，保证答案字符串的长度小于 104 。

示例 1：

输入：numerator = 1, denominator = 2

输出："0.5"

示例 2：

输入：numerator = 2, denominator = 1

输出："2"

示例 3：

输入：numerator = 2, denominator = 3

输出："0.(6)"

示例 4：

输入：numerator = 4, denominator = 333

输出："0.(012)"

示例 5：

输入：numerator = 1, denominator = 5

输出："0.2"

提示：

-2^31 <= numerator, denominator <= 2^31 - 1

denominator != 0

出处：

https://edu.csdn.net/practice/27810771

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    string fractionToDecimal(int numerator, int denominator)
    {
        if (denominator == 0)
            return "";
        string ans;
        if ((numerator > 0 && denominator < 0) || (numerator < 0 && denominator > 0))
            ans = "-";
        long long num = abs(static_cast<long long>(numerator));
        long long den = abs(static_cast<long long>(denominator));
        long long quo = num / den;
        long long rem = num % den;
        ans = ans + to_string(quo);
        if (!rem)
            return ans;
        ans += ".";
        unordered_map<long long, int> u_m;
        string s = "";
        int pos = 0;
        while (rem)
        {
            if (u_m.find(rem) != u_m.end())
            {
                s.insert(u_m[rem], "(");
                s += ")";
                return ans + s;
            }
            u_m[rem] = pos++;
            s += to_string((rem * 10) / den);
            rem = (rem * 10) % den;
        }
        return ans + s;
    }
};
int main()
{
  Solution s;
  cout << s.fractionToDecimal(1, 2) << endl;
  cout << s.fractionToDecimal(2, 1) << endl;
  cout << s.fractionToDecimal(2, 3) << endl;
  cout << s.fractionToDecimal(4, 333) << endl;
  cout << s.fractionToDecimal(1, 5) << endl;
  return 0;
}

输出：

0.5

0.(6)

0.(012)

0.2

3. 删除排序链表中的重复元素 II （C语言）

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,2,3,3,4,4,5]

输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]

输出：[2,3]

提示：

链表中节点数目在范围 [0, 300] 内

-100 <= Node.val <= 100

题目数据保证链表已经按升序排列

以下程序实现了这一功能，请你填补空白处内容：

#include <stdio.h>#include <stdlib.h>structListNode{
intval;
structListNode*next;
};
structListNode*deleteDuplicates(structListNode*head)
{
structListNodedummy;
structListNode*p, *q, *prev;
prev=&dummy;
dummy.next=head;
p=q=head;
while (p!=NULL)
    {
_____________________;
    }
returndummy.next;
}
intmain(intargc, char**argv)
{
inti;
structListNode*head=NULL;
structListNode*prev=NULL;
structListNode*p;
for (i=0; i<argc-1; i++)
    {
p=malloc(sizeof(*p));
p->val=atoi(argv[i+1]);
p->next=NULL;
if (head==NULL)
        {
head=p;
prev=head;
        }
else        {
prev->next=p;
prev=p;
        }
    }
p=deleteDuplicates(head);
while (p!=NULL)
    {
printf("%d ", p->val);
p=p->next;
    }
printf("\n");
return0;
}
```

出处：

https://edu.csdn.net/practice/27810772

代码： (C语言)

#include <stdio.h>#include <stdlib.h>structListNode{
intval;
structListNode*next;
};
structListNode*deleteDuplicates(structListNode*head)
{
structListNodedummy;
structListNode*p, *q, *prev;
prev=&dummy;
dummy.next=head;
p=q=head;
while (p!=NULL)
    {
while (q!=NULL&&q->val==p->val)
        {
q=q->next;
        }
if (p->next==q)
        {
prev=p;
        }
else        {
prev->next=q;
        }
p=q;
    }
returndummy.next;
}
intmain()
{
inti;
structListNode*head=NULL;
structListNode*prev=NULL;
structListNode*p;
intnums[] = {1,2,3,3,4,4,5};
intcount=sizeof(nums) /sizeof(nums[0]);
for (i=0; i<count; i++)
    {
p= (ListNode*)malloc(sizeof(*p));
p->val=nums[i];
p->next=NULL;
if (head==NULL)
        {
head=p;
prev=head;
        }
else        {
prev->next=p;
prev=p;
        }
    }
p=deleteDuplicates(head);
while (p!=NULL)
    {
printf("%d->", p->val);
p=p->next;
    }
printf("null\n");
return0;
}

输出：

1->2->5->null

单链表的创建、打印写成函数形式：

#include <stdio.h>
#include <stdlib.h>
#define Test(nums) {\
    count = sizeof(nums) / sizeof(nums[0]);\
    head = arrayToList(nums, count);\
    printList(head);\
      head = deleteDuplicates(head);\
    printList(head);}
struct ListNode
{
    int val;
    struct ListNode *next;
};
struct ListNode *deleteDuplicates(struct ListNode *head)
{
    struct ListNode dummy;
    struct ListNode *p, *q, *prev;
    prev = &dummy;
    dummy.next = head;
    p = q = head;
    while (p != NULL)
    {
        while (q != NULL && q->val == p->val)
    {
        q = q->next;
    }
    if (p->next == q)
    {
        prev = p;
    }
    else
    {
        prev->next = q;
    }
    p = q;
    }
    return dummy.next;
}
struct ListNode *arrayToList(int* nums, int count)
{
    struct ListNode *head = NULL;
    struct ListNode *prev = NULL;
    struct ListNode *p;
    if (count == 0) return NULL;
    for (int i = 0; i < count; i++)
    {
        p = (ListNode*)malloc(sizeof(*p));
        p->val = nums[i];
        p->next = NULL;
        if (head == NULL)
        {
            head = p;
            prev = head;
        }
        else
        {
            prev->next = p;
            prev = p;
        }
    }
    return head;
}
void printList(ListNode *head)
{
  ListNode *p = head;
    while (p != NULL)
    {
        printf("%d->", p->val);
        p = p->next;
    }
    printf("null\n");
}
int main()
{
    struct ListNode *head;
    int count;
    int head1[] = {1,2,3,3,4,4,5};
  Test(head1)
    int head2[] = {1,1,1,2,3};
  Test(head2)
    return 0;
}

输出：

1->2->3->3->4->4->5->null

1->2->5->null

1->1->1->2->3->null

2->3->null

C/C++每日一练(20230514) 全排列、分数转小数、排序链表去重II

1. 全排列

2. 分数到小数

3. 删除排序链表中的重复元素 II （C语言）

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

C/C++每日一练(20230514) 全排列、分数转小数、排序链表去重II

1. 全排列

2. 分数到小数

3. 删除排序链表中的重复元素 II （C语言）

热门文章

最新文章

相关课程

相关电子书