包含给定元素的最长排序子数组

发布于 2025-01-11 09:22:05 字数 428 浏览 0 评论 0原文

我最近申请了一份前端开发工作，测试问题之一是编写一个接受整数数组和整数 0 <= n 的函数。 arr.length 并返回包含 array[n] 的最长排序子数组。并且该函数必须是递归的。

示例：

array = [3, 1, 4, 7, 9, -3]
function(array, 0) => [3]

function(array, 1) => [1,4,7,9]

function(array, 2) => [1,4,7,9]

function(array, 3) => [1,4,7,9]

function(array, 4) => [1,4,7,9]

function(array, 5) => [-3]

我有 30 分钟的时间，但无法想出答案。

原文

I applied recently to a Front-End Dev job and one of the test questions was to write a function that takes in an array of integers and an integer 0 <= n < arr.length and returns the longest sorted subarray that contains array[n]. And the function has to be recursive.

Example:

array = [3, 1, 4, 7, 9, -3]
function(array, 0) => [3]

function(array, 1) => [1,4,7,9]

function(array, 2) => [1,4,7,9]

function(array, 3) => [1,4,7,9]

function(array, 4) => [1,4,7,9]

function(array, 5) => [-3]

I had 30 minutes and couldn't come up with an answer.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

清音悠歌 2025-01-18 09:22:05

这是我第一次真正的工作测试，我压力太大了，我看不到它！

感谢@kcsquared 的想法，我只需要火花来点燃这个想法！

import java.util.Arrays;

public class Solution {
    public static int[] longestSortedSubArray(int[] arr, int pos) {
        int left = checkLeft(arr, pos);
        int right = checkRight(arr, pos);
        int[] result = Arrays.copyOfRange(arr, left, right + 1);
        return result;
    }

    public static int checkLeft(int[] arr, int pos) {
        int left = pos;
        if (pos - 1 >= 0 && arr[pos - 1] < arr[pos]) {
            left = pos - 1;
        }
        if (left == pos)
            return left;
        return checkLeft(arr, left);
    }

    public static int checkRight(int[] arr, int pos) {
        int right = pos;
        if (pos + 1 < arr.length && arr[pos + 1] > arr[pos]) {
            right = pos + 1;
        }
        if (right == pos)
            return right;
        return checkRight(arr, right);
    }

}

It was my first ever real job test and I was so stressed that I couldn't see it!!!!

Thanks @kcsquared for the idea, I just needed the spark to ignite the idea!

import java.util.Arrays;

public class Solution {
    public static int[] longestSortedSubArray(int[] arr, int pos) {
        int left = checkLeft(arr, pos);
        int right = checkRight(arr, pos);
        int[] result = Arrays.copyOfRange(arr, left, right + 1);
        return result;
    }

    public static int checkLeft(int[] arr, int pos) {
        int left = pos;
        if (pos - 1 >= 0 && arr[pos - 1] < arr[pos]) {
            left = pos - 1;
        }
        if (left == pos)
            return left;
        return checkLeft(arr, left);
    }

    public static int checkRight(int[] arr, int pos) {
        int right = pos;
        if (pos + 1 < arr.length && arr[pos + 1] > arr[pos]) {
            right = pos + 1;
        }
        if (right == pos)
            return right;
        return checkRight(arr, right);
    }

}

回复收藏 0 原文

~没有更多了~