本周学习内容包括：数组、链表、栈、队列。
- 数组
- 支持随机访问
- 按下标访问 O(1)复杂度
- 在内存中是一段连续的存储空间
- 操作复杂度
- LookUp O(1)
- Insert O(n)
- Delete O(n)
- Append O(1)
- Prepend O(n)
- 变长数组
- 链表
- 允许存储空间不连续
- 单链表
- 插入
- 删除
- 操作复杂度
- LookUp O(n)
- Insert O(1)
- Delete O(1)
- Append O(n)
- Prepend O(1)
- 栈
- 先进后出(Last in, first out）
- 队列
- 先进先出(First in, first out)
66. 加一
import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public int[] plusOne(int[] digits) { int length = digits.length; List<Integer> list = new ArrayList<>(length * 2); int increment = 1; for (int i = length - 1; i >= 0; i--) { int result = digits[i] + increment; list.add(result % 10); increment = result / 10; } if (increment > 0) { list.add(increment); } int size = list.size(); int[] results = new int[size]; for (int i = 0; i < list.size(); i++) { results[size - i - 1] = list.get(i); } return results; } }
21. 合并两个有序链表
/** * 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 mergeTwoLists(ListNode l1, ListNode l2) { ListNode head = new ListNode(); ListNode cur = head; while(l1 != null && l2 != null) { int i1 = l1.val; int i2 = l2.val; if(i1 <= i2) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } if (l1 != null) { cur.next = l1; } if (l2 != null) { cur.next = l2; } return head.next; } }
