大一下安卓考核
对于反转链表，我们从头结点出发，每次让对应节点的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();
}
}
这道题是道滑动窗口，窗口大小是不确定的，大小在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;
}
}
这道题属于贪心类算法。刚看到这道题以为要用动归，写了很久也没有思路。其实只要求和相邻两天股票价格之差大于零的数就可以了，因为最终利润是可以分解的，比如[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;
}
}
这道题其实和合并两个链表差不多，多加一个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;
}
}