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

简介: 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

2

0.(6)

0.(012)

0.2


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


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


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


示例 1:

5b9243e41528c71944e0f9436d8c249f.jpeg

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

输出:[1,2,5]


示例 2:

f43c3f1fdb51738ae73ac8543c9b4e9b.jpeg

输入: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

目录
打赏
0
0
0
0
74
分享
相关文章
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
39 10
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
62 10
|
2月前
|
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
49 7
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
47 5
|
5月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
69 0
|
5月前
|
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
49 0
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
58 0
|
9月前
|
C++之deque容器(构造、赋值、大小、插入与删除、存取、排序)
C++之deque容器(构造、赋值、大小、插入与删除、存取、排序)
102 1
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等