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

2023-05-29 94

版权

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

简介： 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语言）

热门文章

最新文章

相关课程

相关电子书