王道线性表例题实现

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

王道线性表例题实现

作者：

我是高情商 , 2024-08-02 21:57:24 , 所有人可见 , 阅读 2

#include <iostream>
#include <vector>
using namespace std;

void search(vector<int>& nums, int x) {
    int n = nums.size();
    int l = 0, r = n - 1;

    while (l <= r) {
        int mid = l + (r - l) / 2;

        if (nums[mid] == x) {
            if (mid + 1 < n) { // 确保 mid+1 不越界
                swap(nums[mid], nums[mid + 1]);
            }
            return;
        } else if (nums[mid] > x) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    // 插入排序
    nums.resize(n + 1);
    int j = n;
    while (j > 0 && nums[j - 1] > x) {
        nums[j] = nums[j - 1];
        j--;
    }
    nums[j] = x;
}

int main() {
    vector<int> a = {1, 2, 3, 4, 6, 7};
    search(a, 2);
    for (int x : a)
        cout << x << ' ';
    cout << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
queue<int>q;
//与右旋左旋字符串等题目原理相同，相整体翻转再局部翻转
void left_move(vector<int>&nums,int p)
{
    int n=nums.size();
    reverse(nums.begin(),nums.end());//整体逆序
    //分部逆序
    reverse(nums.begin(),nums.begin()+n-p);
    reverse(nums.begin()+n-p,nums.end());
}
//队列模拟
void left_move2(vector<int>&nums,int p)
{

    for(int i=0;i<nums.size();i++)
    {
        q.push(nums[i]);
    }
    while (p--)
    {
        int x=q.front();
        q.push(x);
        q.pop();
    }
}
int main()
{
     int p;
     cin>>p;
     vector<int> a = {1, 2, 3, 4, 5,6};
     left_move2(a,p);
     while(q.size())
     {
         cout<<q.front()<<" ";
         q.pop();
     }
     cout<<endl;
     return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int middle(int a[],int b[],int n)
{
   //找到比较的第n个数
   int i=0,j=0,cnt=0;
   while(i<n&&j<n)
   {
       if(a[i]<=b[j])i++;
       else j++;
       cnt++;
       if(cnt==n-1)return min(a[i],b[j]);

   }
}

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
      int cnt=0,val=0;
      //剩下的一个一定是主元素
      for (int i = 0; i < nums.size(); i ++ )
      {
          if(!cnt)val=nums[i],cnt++;
          else if(val==nums[i])cnt++;
          else cnt--;
      }
      return val;
    }
};

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <unordered_set>
using namespace std;
int firstMissingPositive(vector<int>& nums) {
    unordered_set<int>hashset;
    int n=nums.size();
    for(int x:nums)
    {
        hashset.insert(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(hashset.find(i)==hashset.end())
        {
            return i;
        }
    }
    return n+1;
}
int main()
{
     vector<int> nums = {3, 4, -1, 1};
    cout << firstMissingPositive(nums) << endl;
    return 0;
}

单链表
1.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node{
    int val;
    Node*next;
    Node(int x):val(x),next(NULL){};
};
//递归写法
Node*remove(Node*head,int x)
{
    if(head==NULL)return NULL;
    if(head->val==x)
    {
        return remove(head->next,x);//相当于略过这个节点
    }
    head->next=remove(head->next,x);
    return head;
}
//迭代写法
Node*remove2(Node*head,int x)
{
    Node*dummy=new Node(-1);
    dummy->next=head;
    Node*cur=dummy;
    while(cur->next!=NULL)
    {
        if(cur->next->val==x)
        {
            cur->next=cur->next->next;
        }
        else
        {
            cur=cur->next;
        }
    }
    return dummy->next;
}
Node* createlist(int arr[],int n){
    Node*dummy=new Node(-1);
    Node*tail=dummy;
    for(int i=0;i<n;i++)
    {
        Node*node=new Node(arr[i]);
        tail->next=node;
        tail=node;
    }
    return dummy->next;
}
void print(Node*head)
{
    for(Node*p=head;p;p=p->next)
    {
        cout<<p->val<<" ";
    }
    cout<<endl;
}


int main()
{
    int a[]={2,6,4,1,2};
    int n=sizeof(a)/sizeof(int);
    Node*head=createlist(a,n);
    head=remove2(head,2);
    print(head);
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include<stack>
using namespace std;
struct Node{
    int val;
    Node*next;
    Node(int x):val(x),next(NULL){};
};
Node* createlist(int arr[],int n){
    Node*dummy=new Node(-1);
    Node*tail=dummy;
    for(int i=0;i<n;i++)
    {
        Node*node=new Node(arr[i]);
        tail->next=node;
        tail=node;
    }
    return dummy->next;
}
//迭代法
void reverse_print(Node*head)
{ 
    stack<int>st;
    for(Node*p=head;p;p=p->next)
    {
        st.push(p->val);
    }
    while(st.size())
    {
        cout<<st.top()<<" ";
        st.pop();
    }
}
//递归法
void reverse_print2(Node*head)
{ 
    if(head==NULL)return;
    reverse_print(head->next);
    cout<<head->val<<" ";
}

int main()
{
    int a[]={1,2,3,4,5,6};
    int n=sizeof(a)/sizeof(int);
    Node*head=createlist(a,n);
    reverse_print2(head);
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include<stack>
using namespace std;
struct Node{
    int val;
    Node*next;
    Node(int x):val(x),next(NULL){};
};
Node* createlist(int arr[],int n){
    Node*dummy=new Node(-1);
    Node*tail=dummy;
    for(int i=0;i<n;i++)
    {
        Node*node=new Node(arr[i]);
        tail->next=node;
        tail=node;
    }
    return dummy->next;
}
Node*delete_min(Node*head)
{
    Node*dummy=new Node(-1);
    dummy->next=head;
    Node*cur=head;
    Node*pre=dummy;
    Node*min=head;
    Node*min_pre=dummy;
    //找最小节点
    while(cur!=NULL)
    {
        if(cur->val<min->val)
        {
            min=cur;
            min_pre=pre;
        }
        pre=cur;
        cur=cur->next;
    }
    min_pre->next=min->next;
    return dummy->next;
}
//只用两个指针，快慢指针
Node*delete_min2(Node*head)
{
    Node*dummy=new Node(-1);
    dummy->next=head;
    Node*min_pre=dummy;
    Node*min=dummy->next;
    for(Node*cur=dummy;cur->next;cur=cur->next)
    {
        if(cur->next->val<min->val)
        {
            min_pre=cur;
            min=cur->next;
        }
    }
    min_pre->next=min->next;
    return dummy->next;
}
void print(Node*head)
{
    for(Node*p=head;p;p=p->next)
    {
        cout<<p->val<<" ";
    }
    cout<<endl;
}
int main()
{
    int a[]={1,2,3,4,5,6};
    int n=sizeof(a)/sizeof(int);
    Node*head=createlist(a,n);
    head=delete_min2(head);
    print(head);
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include<stack>
using namespace std;
struct Node{
    int val;
    Node*next;
    Node(int x):val(x),next(NULL){};
};
Node* createlist(int arr[],int n){
    Node*dummy=new Node(-1);
    Node*tail=dummy;
    for(int i=0;i<n;i++)
    {
        Node*node=new Node(arr[i]);
        tail->next=node;
        tail=node;
    }
    return dummy->next;
}
Node*reverse_list(Node*head)
{
    Node*pre=NULL;
    Node*cur=head;
    Node*temp=NULL;
    while(cur)
    {
        temp=cur->next;
        cur->next=pre;
        pre=cur;
        cur=temp;
    }
    return pre;//注意链表头变了，要返回pre
}
void print(Node*head)
{
    for(Node*p=head;p;p=p->next)
    {
        cout<<p->val<<" ";
    }
    cout<<endl;
}
int main()
{
    int a[]={1,2,3,4,5,6};
    int n=sizeof(a)/sizeof(int);
    Node*head=createlist(a,n);
    head=reverse_list(head);
    print(head);
}

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(NULL) {}
};

Node* createlist(int arr[], int n) {
    Node* dummy = new Node(-1);
    Node* tail = dummy;
    for (int i = 0; i < n; i++) {
        Node* node = new Node(arr[i]);
        tail->next = node;
        tail = node;
    }
    return dummy->next;
}

Node* sort_list(Node* head) {
    // 直接插入排序写法
    Node* dummy = new Node(-1);//dummy不能指向head否则会断链
    Node* cur = head;
    while (cur) {
        Node* temp = cur->next;
        Node* pre = dummy;

        // 找到插入位置
        while (pre->next && pre->next->val < cur->val) {
            pre = pre->next;
        }

        // 插入当前节点
        cur->next = pre->next;
        pre->next = cur;

        // 继续处理下一个节点
        cur = temp;
    }
    Node* sortedList = dummy->next;
    delete dummy;  // 释放虚拟头结点的内存
    return sortedList;
}

void print(Node* head) {
    for (Node* p = head; p; p = p->next) {
        cout << p->val << " ";
    }
    cout << endl;
}

int main() {
    int a[] = {3, 4, 5, 6, 1, 2};
    int n = sizeof(a) / sizeof(int);
    Node* head = createlist(a, n);
    head = sort_list(head);
    print(head);
    return 0;
}

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(NULL) {}
};

Node* createlist(int arr[], int n) {
    Node* dummy = new Node(-1);
    Node* tail = dummy;
    for (int i = 0; i < n; i++) {
        Node* node = new Node(arr[i]);
        tail->next = node;
        tail = node;
    }
    return dummy->next;
}

Node*del_list(Node*head,int l,int r)
{
    Node*dummy=new Node(-1);
    dummy->next=head;
    Node*pre=dummy;
    Node*cur=head;
    while(cur)
    {
        if(cur->val>=l&&cur->val<=r)
        {
            pre->next=cur->next;
            cur=cur->next;
        }
        else
        {
            pre=cur;
            cur=cur->next;
        }
    }
    return dummy->next;
}

void print(Node* head) {
    for (Node* p = head; p; p = p->next) {
        cout << p->val << " ";
    }
    cout << endl;
}

int main() {
    int a[] = {3, 4, 5, 6, 1, 2};
    int n = sizeof(a) / sizeof(int);
    Node* head = createlist(a, n);
    head = del_list(head,2,5);
    print(head);
    return 0;
}

class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        auto a=headA;
        auto b=headB;
        while(a!=b)
        {
            if(a)a=a->next;
            else a=headB;
            if(b)b=b->next;
            else b=headA;
        }
        return b;
    }
};

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(NULL) {}
};
Node* createlist(int arr[], int n) {
    Node* dummy = new Node(-1);
    Node* tail = dummy;
    for (int i = 0; i < n; i++) {
        Node* node = new Node(arr[i]);
        tail->next = node;
        tail = node;
    }
    return dummy->next;
}
void*min_delete(Node*head)
{
    Node*dummy=new Node(-1);
    dummy->next=head;
    //只要dummy->next也就是头不为空，就一直删
    while(dummy->next)
    {
    Node*pre=dummy;
    Node*cur=dummy->next;//cur要从dummy->next开始头结点可能被删掉
    //每次循环找一个最小值
    while(cur->next)
    {
        if(cur->next->val<pre->next->val)
        {
            pre=cur;//记录当前最小值的前一个位置
        }
        cur=cur->next;
    }
    cout<<pre->next->val<<" ";
    pre->next=pre->next->next;
    }
}
void print(Node* head) {
    for (Node* p = head; p; p = p->next) {
        cout << p->val << " ";
    }
    cout << endl;
}

int main() {
    int a[] = {1, 2, 3, 2, 2, 3, 5, 7, 2};
    int n = sizeof(a) / sizeof(int);
    Node* head = createlist(a, n);
    min_delete(head);
    return 0;
}

0 评论

App 内打开