当前位置：首页 > news >正文

3G大一下安卓考核题解

news 2025/4/29 7:42:02

大一下安卓考核

反转链表

在这里插入图片描述

对于反转链表，我们从头结点出发，每次让对应节点的next指向前一个结点然后向后移动，重复这个过程即可。不过想要完成这个操作，我们还需要两个结构体指针分别保存下一个结点和前一个结点，这里就是通过cur的不断往前移动,改变链表next指向反转整个链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode *cur = head;struct ListNode *next = NULL, *pf = NULL;while(cur){next = cur -> next;cur -> next = pf;pf = cur;cur = next;}return pf;
}

用栈实现队列

这道题思路不难想，将数据先放入栈中然后进行队列操作时，再将栈中数据移到另一个栈中，这样就可以满足队列先进先出的原则了。C语言没有内置的栈，所以需要自己手搓一个。

typedef struct {int* stk;int stkSize;int capacity;
} Stack;Stack* initStack(int capacity) {Stack* stack = (Stack*)malloc(sizeof(Stack));stack->stk = (int*)malloc(sizeof(int) * capacity);stack->stkSize = 0;stack->capacity = capacity;return stack;
}void push(Stack* obj, int x) { obj->stk[obj->stkSize++] = x; }void pop(Stack* obj) { obj->stkSize--; }int Stackpeek(Stack* obj) { return obj->stk[obj->stkSize - 1]; }bool stackEmpty(Stack* obj) { return obj->stkSize == 0; }
void Free(Stack* obj) { free(obj->stk); }typedef struct {Stack* inStack;Stack* outStack;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* ret = malloc(sizeof(MyQueue));ret->inStack = initStack(100);ret->outStack = initStack(100);return ret;
}
void inOut(MyQueue* obj) {while (!stackEmpty(obj->inStack)) {push(obj->outStack, Stackpeek(obj->inStack));pop(obj->inStack);}
}void myQueuePush(MyQueue* obj, int x) { push(obj->inStack, x); }int myQueuePop(MyQueue* obj) {if (stackEmpty(obj->outStack)) {inOut(obj);}int x = Stackpeek(obj->outStack);pop(obj->outStack);return x;
}int myQueuePeek(MyQueue* obj) {if (stackEmpty(obj->outStack)) {inOut(obj);}return Stackpeek(obj->outStack);
}bool myQueueEmpty(MyQueue* obj) {return stackEmpty(obj->inStack) && stackEmpty(obj->outStack);
}void myQueueFree(MyQueue* obj) {Free(obj->inStack);Free(obj->outStack);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/

随机链表的复制

在这里插入图片描述

这道题可以用递归也可以用迭代，递归比较简单，直接构建即可。迭代法很巧妙，对每个节点，都在后面构造一个相同的节点，对val和next进行赋值，构建完成后让复制节点random指向原节点指向的random节点的下一个节点。

/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {public Node copyRandomList(Node head) {if (head == null) {return null;}for (Node node = head; node != null; node = node.next.next) {Node nodeNew = new Node(node.val);nodeNew.next = node.next;node.next = nodeNew;}for (Node node = head; node != null; node = node.next.next) {Node nodeNew = node.next;nodeNew.random = (node.random != null) ? node.random.next : null;}Node headNew = head.next;for (Node node = head; node != null; node = node.next) {Node nodeNew = node.next;node.next = node.next.next;nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;}return headNew;}
}

字符串解码

在这里插入图片描述

这道题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应。当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；当 c 为字母时，在 res 尾部添加 c；当 c 为 [ 时，将当前 multi 和 res 入栈；当 c 为 ] 时，stack 出栈，再拼接字符串

class Solution {public String decodeString(String s) {StringBuilder res = new StringBuilder();int multi = 0;LinkedList<Integer> stack_multi = new LinkedList<>();LinkedList<String> stack_res = new LinkedList<>();for(Character c : s.toCharArray()) {if(c == '[') {stack_multi.addLast(multi);stack_res.addLast(res.toString());multi = 0;res = new StringBuilder();}else if(c == ']') {StringBuilder tmp = new StringBuilder();int cur_multi = stack_multi.removeLast();for(int i = 0; i < cur_multi; i++) tmp.append(res);res = new StringBuilder(stack_res.removeLast() + tmp);}else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");else res.append(c);}return res.toString();}
}

长度为k子数组中的最大和

这道题是道滑动窗口，窗口大小是不确定的，大小在1到n之间，如果直接暴力是O(n^2)会超时，所以需要用到滑动窗口。这种类型的滑动窗口也有对应的模板，就是每次求和然后添加到哈希表中检测去重，遍历的时候维护一个左指针即可。

class Solution {public long maximumSubarraySum(int[] nums, int k) {long ans = 0, temp = 0;HashMap<Integer, Integer> cnt = new HashMap<>();for (int i = 0; i < nums.length; i++) {temp += nums[i];if (cnt.containsKey(nums[i])) {cnt.put(nums[i], cnt.get(nums[i]) + 1);} else {cnt.put(nums[i], 1);}int left = i - k + 1;if (left < 0) {continue;}if (cnt.size() == k) {ans = Math.max(ans, temp);}int out = nums[left];temp -= out;if (cnt.get(out) > 1) {cnt.put(out, cnt.get(out) - 1);} else {cnt.remove(nums[left]);}}return ans;}
}

买卖股票的最佳时机 II

在这里插入图片描述

这道题属于贪心类算法。刚看到这道题以为要用动归，写了很久也没有思路。其实只要求和相邻两天股票价格之差大于零的数就可以了，因为最终利润是可以分解的，比如[7,1,5,3,6,4]，就是(5 - 1) + (6 - 3)，有了这个思路这道题就很简单了

class Solution {public int maxProfit(int[] prices) {int sum = 0;for(int i = 1; i < prices.length; i++){if(prices[i] - prices[i - 1] > 0){sum += prices[i] - prices[i - 1];}}return sum;}
}

接⾬⽔

在这里插入图片描述

这是一道单调栈的题，这里以列为单位求每列能接的雨水进行求解，主要就是找到该列左右最高的柱子，取左右两柱子最短的高度和该列取差即是该列能存储的雨水，那么就可以用单调栈维护一个递减数列，栈头就是最高的柱子

class Solution {public int trap(int[] height) {int l = height.length;int[] left = new int[l];int[] right = new int[l];left[0] = 0;right[l - 1] = 0;for(int i = 1; i < l; i++){left[i] = Math.max(left[i - 1], height[i - 1]);}for(int i = l - 2; i >= 0; i--){right[i] = Math.max(right[i + 1], height[i + 1]);}int ans = 0;for(int i = 0; i < l; i++){if(Math.min(left[i], right[i]) - height[i] > 0){ans += Math.min(left[i], right[i]) - height[i];}}return ans;}
}

合并k个升序链表

在这里插入图片描述

这道题其实和合并两个链表差不多，多加一个for循环而已，每次将前面合并过的链表和新链表进行两两合并即可

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists.length  == 0){return null;}ListNode merged = lists[0];for(int i = 1; i < lists.length; i++){merged = merge(merged, lists[i]);}return merged;}public ListNode merge(ListNode l1, ListNode l2){ListNode dummyHead = new ListNode(0);ListNode cur = dummyHead;while(l1 != null && l2 != null){if(l1.val < l2.val){cur.next = l1;l1 = l1.next;}else{cur.next = l2;l2 = l2.next;}cur = cur.next;}cur.next = l1 == null ? l2 : l1;return dummyHead.next;}
}