数据结构题库之数组(七)

(1)静态链表既有顺序存储的优点,又有动态链表的优点。所以,它存取表中第i个元素的时间与i无关。
(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了,以后不能增加.
(3)静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。
以上错误的是()

[v_act](1),(2)
(1)
(1),(2),(3)
(2) [/v_act]

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given[100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is[1, 2, 3, 4]. Return its length:4.

Your algorithm should run in O(n) complexity.

class Solution {
public:
    int longestConsecutive(vector &num) {
        unordered_set myset(num.begin(),num.end());
        int res=1;
        for(int current:num)
        {
            if(myset.find(current)==myset.end()) continue;
             
            myset.erase(current);
            int prev=current-1,post=current+1;
            while(myset.find(prev)!=myset.end())
            {
                myset.erase(prev--);
            }
            while(myset.find(post)!=myset.end())
            {
                myset.erase(post++);
            }
            res=max(res,post-prev-1);
        }
         
        return res;
    }
};

若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为()(1<=i<=n+1)

[v_act]O(0)
O(1)
O(n)
O(n2) [/v_act]

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

/*
 * 最优解:从后往前处理,不需要开辟额外空间
 * Runtime: 0 ms.Your runtime beats 45.38 % of java submissions.
 */
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, index = m + n - 1;
    while (i >= 0 && j >= 0)
        nums1[index--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
    while (j >= 0)
        nums1[index--] = nums2[j--];
}
/*
i从A的末尾,j从B末尾开始,两两比较,大的放在末端。
比如A[4,5,7] B[1,2,6],。
7比6大,A[5]处放置7,然后i前移。
再次比较5 和6,6放在A[4]处。
如此类推如果A穷尽,把B元素依次放进A的前几个位置,如果B穷尽,正好结束。
*/
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        if(m==0){
            for(int k=0;k=0&&i>=0){
                if(A[i]>B[j])
                    A[s--]=A[i--];
                else
                    A[s--]=B[j--];
                }
            if(i==-1){
                for(;j>=0;j--)
                    A[j]=B[j];
            }
        }
        
    }
}

比较两个数组,要求从数组最后一个元素开始逐个元素向前比较,如果2个数组长度不等,则只比较较短长度数组个数元素。请编程实现上述比较,并返回比较中发现的不相等元素的个数

比如:
数组{1,3,5}和数组{77,21,1,3,5}按题述要求比较,不相等元素个数为0
数组{1,3,5}和数组{77,21,1,3,5,7}按题述要求比较,不相等元素个数为3
• 要求实现函数: int array_compare(int len1, int array1[], int len2, int array2[])
【输入】 int len1:输入被比较数组1的元素个数;
int array1[]:输入被比较数组1;
int len2:输入被比较数组2的元素个数;
int array2[]:输入被比较数组2;
【输出】 无
【返回】 不相等元素的个数,类型为int
• 示例
1) 输入:int array1[] = {1,3,5},int len1 = 3,int array2[] = {77,21,1,3,5},int len2 = 5
函数返回:3
2) 输入:int array1[] = {1,3,5},int len1 = 3,int array2[] = {77,21,1,3,5,7},int len2 = 6
函数返回:0

#include 
#incldue 
#include  
int array_compare(int len1,int array1[],int len2,int array2[]){
    int count=0;
    int n=len1

编程题,比较一个数组的元素是否为回文数组。

/*whether a string is or not  plalindrome. if true, return 1, otherwise return 0.*/
 
int is_plalindrome(const char *src)
{
    const char *end = src + (strlen(src) - 1);
 
    while(src <= end)
    {
        if (*src++ != *end--)
        {
            /* code */
            return 0;
        }
 
    }
 
    return 1;
}

给定一个数组 input[] ,如果数组长度 n 为奇数,则将数组中最大的元素放到 output[] 数组最中间的位置,如果数组长度 n 为偶数,则将数组中最大的元素放到 output[] 数组中间两个位置偏右的那个位置上,然后再按从大到小的顺序,依次在第一个位置的两边,按照一左一右的顺序,依次存放剩下的数。

例如:input[] = {3, 6, 1, 9, 7} output[] = {3, 7, 9, 6,

input[] = {3, 6, 1, 9, 7, 8} output[] = {1, 6, 8, 9, 7, 3}

函数接口 void sort(int input[], int n, int output[])

#include "iostream"
using namespace std;
void bubblesort(int data[], int n)
{
    int temp = 0;
    for (int i = 0; i < n; i++ )
    {
        for (int j = i + 1; j < n; j++)
        {
            if (data[i] < data[j])
            {
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
    }
}
 
void sort(int input[], int n, int output[])
{
    int *sort_input = new int[n];
    for (int i = 0; i < n; i++)
    {
        sort_input[i] = input[i];
    }
    bubblesort(sort_input, n);
    if (1 == n % 2)
    {
        int mid = n / 2;
        int k = 0;
        output[mid] = sort_input[k++];
        for (int j = 1; j <= n / 2; j++)
        {
            output[mid - j] = sort_input[k++];
            output[mid + j] = sort_input[k++];
        }
    }
    else
    {
        int mid = n / 2;
        int k = 0;
        output[mid] = sort_input[k++];
        for (int j = 1; j < n / 2; j++)
        {
            output[mid - j] = sort_input[k++];
            output[mid + j] = sort_input[k++];
        }
        output[0] = sort_input[k++];
 
    }
 
    delete sort_input;
}
void main()
{
    int input1[] = {3, 6, 1, 9, 7};
    int output1[5];
    memset(output1, 0, 5 * sizeof(int));
    int input2[] = {3, 6, 1, 9, 7, 8} ;
    int output2[6];
    memset(output2, 0, 6 * sizeof(int));
    sort(input1, 5, output1);
    sort(input2, 6, output2);
    for (int k = 0; k < 5; k++)
        printf("%d", output1[k]);
    printf("\n");
    for (k = 0; k < 6; k++)
        printf("%d", output2[k]);
    printf("\n");
}

操作系统任务调度问题。

操作系统任务分为系统任务和用户任务两种。其中,系统任务的优先级 < 50,用户任务的优先级 >= 50且 <= 255。优先级大于 255的为非法任务,应予以剔除。现有一任务队列 task[],长度为 n,task中的元素值表示任务的优先级,数值越小,优先级越高。函数 scheduler 实现如下功能,将 task[] 中的任务按照系统任务用户任务依次存放到 system_task[] 数组和 user_task[] 数组中 (数组中元素的值是任务在 task[] 数组中的下标),并且优先级高的任务排在前面,优先级相同的任务按照入队顺序排列(即先入队的任务排在前面),数组元素为-1表示结束。 例如:task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99} system_task[] = {0, 3, 1, 7, -1} user_task[] = {4, 8, 2, 6, -1} 函数接口 void scheduler(int task[], int n, int system_task[], int user_task[])

#include "iostream"
using namespace std;
void change(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void bubblesort(int data[], int n, int index[]) //冒泡排序并记录排序后下标
{
    int temp = 0;
    for (int j = 0; j < n; j++)
        index[j] = j;
    for (int i = 0; i < n; i++ )
    {
        for (int j = i + 1; j < n; j++)
        {
            if (data[i] > data[j])
            {
                change(&data[i], &data[j]);
                change(&index[i], &index[j]);
            }
        }
    }
}
void scheduler(int task[], int n, int system_task[], int user_task[])
{
    int *sort_task = new int[n];
    int *index = new int[n];
    for (int i = 0; i < n; i++)
    {
        sort_task[i] = task[i];
    }
    bubblesort(sort_task, n, index);
    i = 0;
    while (sort_task[i] < 50)
    {
        system_task[i] = index[i];
        i++;
    }
    system_task[i] = -1;
    for (int m = 0; m <= i; m++)
    {
        printf("%d ", system_task[m]);
    }
    printf("\n");
    int k = 0;
    while (sort_task[i] > 50 && sort_task[i] <= 255)
    {
        user_task[k++] = index[i++];
    }
    user_task[k] = -1;
    for (int l = 0; l <= k; l++)
    {
        printf("%d ", user_task[l]);
    }
    printf("\n");
    delete sort_task;
    delete index;
}
void main()
{
    int task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99};
    int n = sizeof(task) / sizeof(int);
    int *system_task = new int[n];
    int *user_task = new int[n];
    scheduler(task, n, system_task, user_task);
}

德州扑克问题 :一副牌中发五张扑克牌给你:让你判断数字的组成:

有以下几种情况:

1:四条:即四张一样数值的牌(牌均不论花色)2:三条带 一对

3:三条带两张不相同数值的牌

4:两对

5:顺子 包括 10,J,Q,K,A

6:什么都不是
7:只有一对

编程实现以上功能。

#include "stdio.h"
void sort(int data[], int n)
{
    int temp = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (data[i] < data[j])
            {
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
    }
}
void test(int a[], int len)
{
    int *b = new int[len];
    int count = 0;
    bool temp = false;
    for (int i = 0; i < len; i++)
    {
        b[i] = a[i];
    }
    sort(b, 5);
    for (i = 0; i < len - 1; i++)
    {
        if (b[i] == b[i + 1])
            count++;
    }
    switch (count)
    {
    case 0:
        if (b[0] - b[4] == 4 && b[0] - b[3] == 3 && b[0] - b[2] == 2 && b[0] - b[1] == 1)
        {
            printf("顺子");
        }
        else
            printf("什么都不是");
        break;
    case 1:
        printf("只有一对");
        break;
    case 2:
        for (i = 0; i < 3; i++)
        {
            if (b[i] == b[i + 2])
            {
                printf("三条带两张不相同数值的牌");
                temp = true;
                break;
            }
        }
        if (!temp)
        {
            printf("两对");
        }
        break;
    case 3:
        if (b[1] == b[3])
            printf("四条:即四张一样数值的牌");
        else
            printf("三条带一对");
        break;
    }
}
main()
{
    int a[5] = {3, 3, 3, 3, 12};
    test(a, 5);
    return 0;
}

编程实现删除数组中的重复元素

#include 
using namespace std;
int de(int a[], int n)
{
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[j] == a[i])
            {
                for (int k = j; k < n - 1; k++)
                    a[k] = a[k + 1];
                n--;
            }
    for ( i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}
 
int main ()
{
    int a[10];
    int m = 10;
    for (int l = 0; l < 10; l++)
        cin >> a[l];
    de(a, m);
    return 0;
}

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A =[1,1,1,2,2,3],

Your function should return length =5, and A is now[1,1,2,2,3].

在一个有8个int数据的数组中,随机给出数组的数据,找出最大和第二大元素一定需要进行()次比较:

[v_act]8
9
10
11 [/v_act]

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构题库之数组(七)

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多