算法刷题5-27 找到一个数组中出现一次的数字, 其他数字出现均为偶数次

找到一个数组中出现一次的数字, 其他数字出现均为偶数次

input【1，1，2,3,3,4,4,6,7,6,7】

out: 2

算法思路：

1^1=0

0^1 =1

0^1^2^1=2

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

int main()
{
    vector <int> v1 = {1,1,3,3,4,4,2};
    int res = 0;
    for(int i= 0 ;i < v1.size();i++)
    {
        res = res^v1[i];
    }
	cout<<res;
    return res;
}

数组中值出现了一次的数字

给定一个数字arr，其中只有有两个数字出现了奇数次，其它数字都出现了偶数次，按照从小到大顺序输出这两个数。

输入描述

输入包含两行，第一行一个整数n，代表数组arr的长度，第二行n个整数，代表数组arr,arr[i]为32位整数。

输出描述

输出出现奇数次的两个数，按照从小到大的顺序。

示例1

输入

4
1 1 2 3

输出

2 3

示例2

输入

6
11 22 11 23 23 45

输出

22 45

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


int main() {
    
    vector<int> v1 ={1,1,2,3};
    vector<int> v2;
    int len = v1.size();
    map<int,int> ma1;
    for(int i=0; i < len;i++)
    {
        ma1[v1[i]]++;
    }
    map<int,int> ::iterator it = ma1.begin();
    while(it !=  ma1.end())
    {
        if(1 == it->second)
        {
            v2.push_back(it->first);
            it++;
        }
        
    }

     if(v2[0]>v2[1])
     {
              cout<<v2[0]<<" "<<v2[1]<<endl;
     }else{
              cout<<v2[1]<<" "<<v2[0]<<endl;
     }  

   
        
   //cout << "Hello World!" << endl;
}

next_permutation函数

    组合数学中经常用到排列，这里介绍一个计算序列全排列的函数：next_permutation（start,end），和prev_permutation（start,end）。这两个函数作用是一样的。

next_permutation（start,end）求的是当前排列的下一个排列，

prev_permutation（start,end）求的是当前排列的上一个排列。

至于这里的“前一个”和“后一个”，我们可以把它理解为序列的字典序的前后，严格来讲，就是对于当前序列pn，他的下一个序列pn+1满足：不存在另外的序列pm，使pn<pm<pn+1.

对于next_permutation函数，其函数原型为：

     #include <algorithm>

     bool next_permutation(iterator start,iterator end)

当前序列不存在下一个排列时，函数返回false，否则返回true

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

int main()
{
    vector<int> v1;
    v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	do  
    {  
         cout<<v1[0]<<" "<<v1[1]<<" "<<v1[2]<<" "<<v1[3]<<endl;  
    }while(next_permutation(v1.begin(),v1.end()));  
  
   return 0;
}

面试题25. 合并两个排序的链表

难度简单29收藏分享切换为英文关注反馈

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
    {
        ListNode* head = new ListNode(0);
        if(nullptr == l1 && nullptr !=l2) return l2;
        if(nullptr != l1 && nullptr ==l2) return l1;
        ListNode* p1 = head;

        while(l1 || l2)
        {
            if(!l1||(l1 && l2 &&(l1->val >= l2->val)))
            {
                p1->next = new ListNode(l2->val);
                p1=p1->next;
                l2=l2->next;
            }else if(!l2||(l1 && l2 &&(l1->val < l2->val)))
            {
                p1->next = new ListNode(l1->val);
                p1=p1->next;
                l1=l1->next;
            }
        
        }
        return head->next;

    }
};