【笔试真题--OPPO笔试编程 | 2022.9.2 | 后端开发】

1.给定一个数组 元素个数<6 元素值域[0-9] 求数组元素组成的最大值

举例：[3,4]
输出：43
思路：字符串拼接

public  int maxDigit (int[] digits) {
	Arrays.sort(digits);
	String s="";
	for (int i = digits.length-1; i >=0; i--) {
		s+=digits[i];
	}
	return Integer.valueOf(s);
}

2. 合并无序链表 将两个无序链表合并成一个新的升序链表并返回

举例：{3,4,1},{5,6,2}
输出：{1,2,3,4,5,6 }
思路：

分析：做这道题其实我们可以分成两个步骤

• 第一步：把两个无序链表都变成有序链表
• 第二步：把两个有序链表合并成一个有序链表

class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
}

public class Oppo02 {
    public static ListNode combineTwoDisorder(ListNode node1, ListNode node2) {
        //单个链表变成有序链表
        sortList(node1);
        sortList(node2);
        //合并两个有序链表
        return combine(node1, node2);
    }
    //1.无序链表变成有序链表
    public static ListNode sortList(ListNode head) {
        int temp;
        ListNode curNode = head;
        while (curNode != null) {
            ListNode nextNode = curNode.next;
            while (nextNode != null) {
                if (nextNode.val < curNode.val) {
                    temp = nextNode.val;
                    nextNode.val = curNode.val;
                    curNode.val = temp;
                }
                nextNode = nextNode.next;
            }
            curNode = curNode.next;
        }
        return head;
    }
    //2.合并有序链表
    public static ListNode combine(ListNode node1, ListNode node2) {
        if (node1 == null) {
            return node2;
        } else if (node2 == null) {
            return node1;
        } else if (node1.val < node2.val) {
            node1.next = combine(node1.next, node2);
            return node1;
        } else {
            node2.next = combine(node1, node2.next);
            return node2;
        }
    }
}

3. 旅游问题动态规划 n个景点 每天只能玩1-2个景点 不走回头路 有多少种玩法

思路：这道题其实就是爬楼梯的动态规划

	public long tourismRoutePlanning(int scenicspot) {
        long[] dp = new long[scenicspot + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= scenicspot; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[scenicspot];
    }