3.数列有序!
| 数列有序! Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 194132 Accepted Submission(s): 78855 Problem Description 有n(n<=100)个整数，已经按照从小到大顺序排列好，现在另外给一个整数x，请将该数插入到序列中，并使新的序列仍然有序。 Input 输入数据包含多个测试实例，每组数据由两行组成，第一行是n和m，第二行是已经有序的n个数的数列。n和m同时为0标示输入数据的结束，本行不做处理。 Output 对于每个测试实例，输出插入新的元素后的数列。 Sample Input 3 3 1 2 4 0 0 Sample Output 1 2 3 4 Author lcy Source C语言程序设计练习（三） |
#include <iostream>
#include <stdexcept>
#define eleType long long
using namespace std;
struct ListNode {
eleType data;
ListNode* next;
ListNode(eleType x) :data(x), next(nullptr) {}
};
class LinkedList {
private:
ListNode* head;
int size;
public:
LinkedList() :head(nullptr), size(0) {}
~LinkedList();
void insert(int index, eleType value);
void remove(int index);
ListNode* find(eleType value);
ListNode* get(int index);
void update(int index, eleType value);
void print();
void append(eleType value);
void ascInsert(eleType value);
};
LinkedList::~LinkedList() {
ListNode* curr = head;
while (curr) {
ListNode* temp = curr;
curr = curr->next;
delete temp;
}
}
void LinkedList::insert(int index, eleType value) {
if (index<0 || index>size) {
throw std::out_of_range(“invalid position”);
}
ListNode* newNode = new ListNode(value);
if (index == 0) {
newNode->next = head;
head = newNode;
}
else {
ListNode* curr = head;
for (int j = 0; j < index – 1; j++) {
curr = curr->next;
}
newNode->next = curr->next;
curr->next = newNode;
}
size++;
}
void LinkedList::remove(int index) {
if (index < 0 || index >= size) {
throw std::out_of_range(“invalid position”);
}
if (index == 0) {
ListNode* temp = head;
head = temp->next;
delete temp;
}
else {
ListNode* curr = head;
for (int j = 0; j < index – 1; j++) {
curr = curr->next;
}
ListNode* temp = curr->next;
curr->next = temp->next;
delete temp;
}
size–;
}
ListNode* LinkedList::find(eleType value) {
ListNode* curr = head;
while (curr != nullptr && curr->data != value) {
curr = curr->next;
}
return curr;
}
ListNode* LinkedList::get(int index) {
if (index < 0 || index >= size) {
throw std::out_of_range(“invalid position”);
}
ListNode* curr = head;
for (int j = 0; j < index; j++) {
curr = curr->next;
}
return curr;
}
void LinkedList::update(int index, eleType value) {
if (index < 0 || index >= size) {
throw std::out_of_range(“invalid position”);
}
get(index)->data = value;
}
void LinkedList::print() {
ListNode* curr = head;
while (curr) {
cout << curr->data;
curr = curr->next;
if (curr) {
cout << ” “;
}
else {
cout << endl;
}//如果后面还有值就打印空格 不然就打印换行
}
}
void LinkedList::append(eleType value) {
insert(size, value);
}
void LinkedList::ascInsert(eleType value) {
if (size == 0) {
insert(0, value);
return ;
}
ListNode* curr = head;
for (int i = 0; i < size; i++) {
if (value <= curr->data) {
insert(i, value);
return ;
}
curr = curr->next;
}
insert(size, value); //没有找到比它小的
}
int main() {
int n, x;
while (cin >> n >> x) {
if (!n && !x) {
break;
}
LinkedList l;
while (n–) {
int v;
cin >> v;
l.append(v);
}
l.ascInsert(x);
l.print();
}
return 0;
}
已解答
简单
相关标签
相关企业
提示
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
最高位 在链表的头部。
示例 1：
输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)
示例 2：
输入：head = [0]
输出：0
提示：
- 链表不为空。
- 链表的结点总数不超过 30。
每个结点的值不是 0 就是 1。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
int getDecimalValue(ListNode* head) {
int sum=0;
while(head){
// sum = sum*2+head->val;
sum = (sum << 1) | head->val;//炫技
head=head->next;
}
return sum;
}
};
简单
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
注意：本题相对原题稍作改动
示例：
输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：
给定的 k 保证是有效的。
面试中遇到过这道题?
1/5
是
否
通过次数
126,441/165.2K
通过率
76.5%
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
int kthToLast(ListNode* head, int k) {
ListNode* fast = head;//快指针也得在头
while(k–){
fast = fast->next;
}
ListNode* slow = head;//慢指针也得在头
while(fast){
fast = fast->next;
slow = slow->next;
}//快慢指针
return slow->val;
}
};