第一页总结
- 链表
- 反转
- 206. 反转链表
- 25. K 个一组翻转链表
- 双指针
- 21. 合并两个有序链表
- 141. 环形链表
- dfs和回溯
- 200. 岛屿数量
- 46. 全排列
- 二叉树
- 102. 二叉树的层序遍历
- 236. 二叉树的最近公共祖先
- 字符串
- 3. 无重复字符的最长子串
- 5. 最长回文子串
- 数组
- 双指针
- 1.两数之和
- 15. 三数之和
- 【二分】33. 搜索旋转排序数组
- 88. 合并两个有序数组
- 排序
- 补充题4. 手撕快速排序
- 215. 数组中的第K个最大元素
- 动归
- 121. 买卖股票的最佳时机
- 贪心
- 动归
- 53. 最大子数组和
- 栈
- 有效的括号
- 方法一：不用hashMap，只用栈
- 方法二：用hashmap+栈
字节题目
链表
反转
206. 反转链表
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
递归思路：
每一个子递归都将当前节点下一个节点的下一个节点指向当前节点，当前节点的下一个节点置空。 递归终止条件：head为空或head.next为空。
复杂度分析
- 时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
- 空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next=null;
return newHead;
}
}
迭代思路：用pre和cur两个指针遍历链表
复杂度分析
- 时间复杂度：O(n)，其中 n 是链表的长度，需要遍历链表一次。
- 空间复杂度：O(1)
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
25. K 个一组翻转链表
25. K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
递归思路：k个一组翻转链表，对于每一组来说就是反转前n。所以可以采用递归的思想，首先找到下一个要翻转前n的节点，再翻转当前head的前n个节点，最后递归的反转后续链表并连接起来。
时间复杂度分析：
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode p = head;
// 找到下一个要反转前n的head
for(int i=0;i<k;i++){
if(p==null){
return head;
}
p=p.next;
}
// 反转前N
ListNode newHead = reverseN(head,k);
head.next = reverseKGroup(p,k);
return newHead;
}
/**
反转前N
*/
ListNode successor = null;
private ListNode reverseN(ListNode head, int n){
// 找到第一个不用反转的节点
if(n==1){
successor = head.next;
return head;
}
ListNode newHead = reverseN(head.next, n-1);
head.next.next = head;
head.next = successor;
return newHead;
}
}
迭代：
时间复杂度：O(n)，其中 n 为链表的长度。head 指针会在 O(⌊n/k⌋)个节点上停留，每次停留需要进行一次 O(k)的翻转操作。
空间复杂度：O(1).
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode hair = new ListNode(0);
hair.next = head;
ListNode pre = hair;
while (head != null) {
ListNode tail = pre;
// 查看剩余部分长度是否大于等于 k
for (int i = 0; i < k; ++i) {
tail = tail.next;
if (tail == null) {
return hair.next;
}
}
ListNode nex = tail.next;
ListNode[] reverse = myReverse(head, tail);
head = reverse[0];
tail = reverse[1];
// 把子链表重新接回原链表
pre.next = head;
tail.next = nex;
pre = tail;
head = tail.next;
}
return hair.next;
}
public ListNode[] myReverse(ListNode head, ListNode tail) {
ListNode prev = tail.next;
ListNode p = head;
while (prev != tail) {
ListNode nex = p.next;
p.next = prev;
prev = p;
p = nex;
}
return new ListNode[]{tail, head};
}
}
双指针
相关题目：双指针秒杀七道链表题目
21. 合并两个有序链表
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路：比较两个链表的大小，将更小的接到p指针。
复杂度分析
时间复杂度：O(n+m)，其中 n和 m分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。
空间复杂度：O(1)。我们只需要常数的空间存放若干变量。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
while(list1!=null && list2!=null){
if(list1.val<list2.val){
p.next = list1;
list1 = list1.next;
}else{
p.next = list2;
list2 = list2.next;
}
p = p.next;
}
if(list1!=null){
p.next = list1;
}
if(list2!=null){
p.next = list2;
}
return dummy.next;
}
}
141. 环形链表
141. 环形链表
判断链表是否有环
思路：通过快慢指针，如果相遇则有环。
复杂度分析
时间复杂度：O(N)，其中N是链表中的节点数。
当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 NNN 轮。空间复杂度：O(1)。我们只使用了两个指针的额外空间。
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null){
return false;
}
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null){
slow = slow.next;
fast=fast.next.next;
// 快慢指针相遇则有环
if(fast==slow){
return true;
}
}
return false;
}
}
dfs和回溯
200. 岛屿数量
labuladong题解
200. 岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
解题思路：遍历二维矩阵，遇到陆地则岛屿数+1，且通过dfs淹没其相邻的陆地。
复杂度分析
- 时间复杂度：O(MN)，其中 M 和 N分别为行数和列数。
- 空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN。
class Solution {
public int numIslands(char[][] grid) {
int cnt = 0;
// 遍历二维矩阵，找陆地、淹陆地
for(int i=0; i<grid.length;i++){
for(int j=0;j<grid[i].length;j++){
if(grid[i][j]=='1'){
// 找到陆地，岛屿数++
cnt++;
// 淹没与其相邻的陆地
dfs(grid, i, j);
}
}
}
return cnt;
}
/**
通过dfs淹没相邻陆地
*/
private void dfs(char[][] grid, int i, int j){
// 边界
if(i<0 || i>=grid.length || j<0 || j>=grid[0].length){
return ;
}
// 已淹没
if(grid[i][j]=='0'){
return ;
}
// 把i，j淹没，并递归淹没与其相邻的陆地
grid[i][j] = '0';
dfs(grid, i-1, j);
dfs(grid, i+1, j);
dfs(grid, i, j-1);
dfs(grid, i, j+1);
}
}
46. 全排列
46. 全排列
思路：遍历回溯树，每个合法答案都在叶子节点，遍历一遍树，把叶子节点的答案都收集起来就得到所有全排列的结果。
用路径来存当前已经做的选择，选择列表就是nums中未使用过的，结束条件就是遍历到了叶子节点也就是路径的大小和nums大小相同了。
回溯的过程就是在选择列表中做选择，然后递归，再撤销选择。
时间复杂度 : O(n×n!)，其中 nnn 为序列的长度。
空间复杂度：O(n)，其中 n 为序列的长度。除答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，这里可知递归调用深度为 O(n)。
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
int n = nums.length;
// 通过是否使用过 决定可选择列表
boolean[] used = new boolean[n];
// 记录路径
List<Integer> track = new LinkedList<>();
backtrack(nums,track,used);
return res;
}
public void backtrack(int[] nums, List<Integer> track, boolean[] used){
// 结束条件：已经走到叶子节点
if(track.size()==nums.length){
res.add(new LinkedList(track));
return ;
}
// 选择列表：nums中排除已经用过的
for(int i = 0;i<nums.length;i++){
// 已使用过 不能选择
if(used[i]){
continue;
}
// 做选择
used[i] = true;
track.add(nums[i]);
// 继续遍历
backtrack(nums, track, used);
// 撤销选择
used[i] = false;
track.removeLast();
}
}
}
二叉树
102. 二叉树的层序遍历
102. 二叉树的层序遍历
思路：通过队列来实现二叉树的层序遍历，通过while循环判断队列是否为空控制二叉树从上到下的遍历，根据当前队列的size用for循环控制每一层从左到右的遍历。
时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。
空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
if(root==null){
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// while循环控制从上向下遍历
while(!queue.isEmpty()){
int size = queue.size();
// for循环控制该层从左到右遍历
List<Integer> curRes = new ArrayList<>();
for(int i=0;i<size;i++){
TreeNode node = queue.poll();
curRes.add(node.val);
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
result.add(curRes);
}
return result;
}
}
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。p和q一定存在于二叉树中。
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
思路：找p和q的公共祖先，就是找以root为根的二叉树中寻找p或q的节点。如果root为p或q直接返回root，接着递归的遍历左右子树，如果在左右子树分别找到了p和q则返回root，如果p和q都没在以root为根的节点找到则返回null，如果p和q存在一个则返回那个节点。
复杂度分析：
- 时间复杂度：O(N)，其中 N是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。
- 空间复杂度：O(N) ，其中 N是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)。
class Solution {
//定义：在以 root 为根的二叉树中寻找值为 p 或 q 的节点
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}
// base case: 找到p或q
if(root.val==p.val || root.val==q.val){
return root;
}
// 从root的左右子树找
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 情况一：分别在左右子树找到了p和q
if(left!=null && right!=null){
return root;
}
return left==null?right:left;
}
}
字符串
3. 无重复字符的最长子串
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长
子串的长度。
思路：采用滑动窗口的思想，通过窗口存储窗口内字符出现的个数，扩张窗口就讲window对应的key+1，当遇到字符个数大于1时收缩窗口，直到字符个数等于1时更新答案。
时间复杂度：O(N)
空间复杂度：O(1)，字符的 ASCII 码范围为 0~127，哈希表最多使用 O(128)=O(1)大小的额外空间。
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
HashMap<Character,Integer> window = new HashMap<>();
int maxLen = 0;
int left=0,right=0;
while(right<n){
// 扩张窗口
Character c = s.charAt(right);
right++;
// 更新窗口数据
window.put(c, window.getOrDefault(c,0)+1);
// 有重复数据时收缩窗口
while(window.get(c)>1){
Character d = s.charAt(left);
left++;
// 更新窗口数据
if(window.containsKey(d)){
window.put(d, window.get(d)-1);
}
}
// 更新结果
maxLen = Math.max(maxLen, right-left);
}
return maxLen;
}
}
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
方法一：双指针 中心扩展法
遍历字符串，分别找s[i] 和s[i] 和 s[i+1]为中心的回文串，找到最长的。
寻找回文串的方法：从中间向两边扩散。
时间复杂度：O(n^2)。
空间复杂度：O(1)。
class Solution {
public String longestPalindrome(String s) {
String res = "";
for(int i=0;i<s.length();i++){
// 以i为中心的最长回文串
String s1 = findPalindrome(s,i,i);
// 以i，i+1为中心的最长回文串
String s2 = findPalindrome(s,i,i+1);
// 找到最长
res = s1.length()>res.length()?s1:res;
res = s2.length()>res.length()?s2:res;
}
return res;
}
/**
从中间向两边扩散寻找回文串
*/
public String findPalindrome(String s, int l, int r){
while(l>=0 && r<s.length() && s.charAt(l)==s.charAt(r)){
l--;
r++;
}
// 找到以l，r为中心的最长回文串
return s.substring(l+1,r);
}
}
数组
双指针
拓展：一个方法团灭nSum问题
1.两数之和
1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
思路：用map维护数组值和下标的映射关系，遍历数组的过程中如果map包含target-nums[i]则返回对应下标，没有则将当前遍历的值put到map中。
复杂度：
- 时间复杂度 O(n)
- 空间复杂度 O(n)
class Solution {
public int[] twoSum(int[] nums, int target) {
// 维护值和下标的映射
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
int need = target-nums[i];
if(map.containsKey(need)){
return new int[]{map.get(need),i};
}
map.put(nums[i],i);
}
return new int[]{-1,-1};
}
}
15. 三数之和
解题思路：排序+双指针，并且在遍历的过程中去重
时间复杂度：O(N^2)
空间复杂度：O(logN)。我们忽略存储答案的空间，额外的排序的空间复杂度为 O(logN)。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
for(int i=0;i<n;i++){
int left = i+1;
int right = n-1;
while(left<right){
int leftValue = nums[left];
int rightValue = nums[right];
int sum = nums[i]+leftValue+rightValue;
if(sum==0){
// 找到可行解
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
res.add(list);
while(left<right && nums[right]==rightValue){
right--;
}
while(left<right && nums[left]==leftValue){
left++;
}
}else if(sum>0){
while(left<right && nums[right]==rightValue){
right--;
}
}else if(sum<0){
while(left<right && nums[left]==leftValue){
left++;
}
}
}
while(i+1<n && nums[i]==nums[i+1]){
i++;
}
}
return res;
}
}
【二分】33. 搜索旋转排序数组
33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值互不相同 。
给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
思路：对有序的数组可以直接用二分查找，虽然这个有序数组被旋转了一次，但是左右两半一定会有一部分是有序的，所以只有找到有序的那一半还是可以用二分。
时间复杂度： O(logn)。
空间复杂度： O(1) 。
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int left=0,right=n-1;
while(left<=right){
int mid = (right-left)/2+left;
// 找到答案
if(nums[mid]==target){
return mid;
}
// 左半部分有序 [left,mid)
if(nums[mid]>=nums[left]){
if(target>=nums[left] && target<nums[mid]){
right = mid-1;
}else{
left = mid+1;
}
}else{
// 右半部分有序(mid,right]
if(target>nums[mid] && target<=nums[right]){
left = mid+1;
}else{
right = mid-1;
}
}
}
return -1;
}
}
88. 合并两个有序数组
88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
思路：从后往前遍历数组，这样可以避免nums1的数据被覆盖。遍历过程中如果nums2已经遍历完说明都已经插入到相应的位置，未遍历完如果nums1遍历完则直接插nums2，如果nums1未遍历完则与nums1比大小谁大插谁。
时间复杂度：O(m+n)。
空间复杂度：O(1)。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int l1 = m-1;
int l2 = n-1;
// 从后往前遍历
for(int i=m+n-1; i>=0;i--){
// nums2已全部插入
if(l2<0){
return ;
}
// 情况1 ：nums1已经插完，则无脑插nums2；nums1没插完，如果nums2大就插
if(l1>=0 && nums1[l1]<nums2[l2] || l1<0){
nums1[i] = nums2[l2];
l2--;
}else{
nums1[i] = nums1[l1];
l1--;
}
}
}
}
排序
补充题4. 手撕快速排序
912. 排序数组
给你一个整数数组 nums，请你将该数组升序排列。
采用快排来做：快排的思想就是找到一个分区点，使其左边的数都小于他，右边的数都大于他，这样这个分区点就排好序了，然后再递归的排序分区点左半部分和右半部分。
分区的过程就是先随机找一个分区点，然后通过游标i将数组分为已排序区[lo,i-1]和未排序区两部分[i,hi-1]，遍历未排序区，如果小于分区点的值则和i交换置于已排序区的尾部。
最后再把分区点和i交换，让分区点到正确的位置上。
**时间复杂度：O(nlogn)
空间复杂度：O(h)。**其中 h 为快速排序递归调用的层数。我们需要额外的 O(h) 的递归调用的栈空间，由于划分的结果不同导致了快速排序递归调用的层数也会不同，最坏情况下需 O(n)的空间，最优情况下每次都平衡，此时整个递归树高度为logn，空间复杂度为 O(logn)。
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
private void quickSort(int[] nums, int lo, int hi){
// base case
if (lo>=hi){
return ;
}
// 分区
int p = randomizedPartition(nums, lo, hi);
// 递归的排序左半部分和右半部分
quickSort(nums,lo,p-1);
quickSort(nums,p+1,hi);
}
private int randomizedPartition(int[] nums, int lo, int hi){
// 随机选择分区点
int i = new Random().nextInt(hi-lo+1)+lo;
swap(nums, i, hi);
return partition(nums,lo,hi);
}
/**
将数组分区，找到一个分区点使得左半部分都小于分区点，右半部分都大于分区点
*/
private int partition(int[] nums, int lo, int hi){
// 数组的最后一个元素作为分区点
int pivot = nums[hi];
int i=lo;
// [lo,i] 已处理区域 [i,hi]未处理区域
for(int j=lo;j<=hi-1;j++){
if(nums[j]<pivot){
swap(nums, i, j);
// 处理一个了，已处理区域向前移动
i++;
}
}
// 把分区点换到对应位置
swap(nums,i,hi);
return i;
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
215. 数组中的第K个最大元素
215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
方法一：用小顶堆
遍历一遍数组，把元素放到小顶堆，当堆内元素大于k时删除堆顶元素，这样最后剩下的就是k个最大元素，堆顶就是第k个最大元素
二叉堆插入和删除的时间复杂度和堆中的元素个数有关，在这里我们堆的大小不会超过 k，所以插入和删除元素的复杂度是 O(logK)，再套一层 for 循环，总的时间复杂度就是 O(NlogK)。
空间复杂度：O(logn)
class Solution {
public int findKthLargest(int[] nums, int k) {
// 小顶堆
PriorityQueue<Integer> pq = new PriorityQueue<>();
int n = nums.length;
for(int i=0;i<n;i++){
pq.offer(nums[i]);
// 堆的元素大于k，则删除堆顶元素
if(pq.size()>k){
pq.poll();
}
}
// pq中剩下的就是nums中k个最大元素，堆顶元素就是k个最大元素
return pq.peek();
}
}
动归
121. 买卖股票的最佳时机
【只交易一次 所以很简单】
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
贪心
最好的结果就是在最低点买入，在收益最高的时候卖出。
做法就是在遍历数据的时候，更新最低价，更新前i天的最高利润。
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public int maxProfit(int[] prices) {
int minCost = Integer.MAX_VALUE;
int maxProfit = 0;
for(int i=0;i<prices.length;i++){
// 找最低价格
minCost = Math.min(minCost, prices[i]);
// 找最高收益
maxProfit = Math.max(maxProfit, prices[i]-minCost);
}
return maxProfit;
}
}
动归
dp[i][j] 表示天数 [0, i] 区间里，下标 i 这一天状态为 j 的时候能够获得的最大利润。
base case：dp[i][0] = 0 dp[i][1] = -prices[i]，没买就是0，买了就是当天股价的相反数
转移方程：
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
复杂度分析：
时间复杂度：O(N)，遍历股价数组可以得到最优解；
空间复杂度：O(N)，状态数组的长度为 N。
还可以把dp[i][j]压缩成一维数组，使状态数组的长度为2，空间复杂度为O(1)。
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
// dp[i][0或1] 第i天买入的 获得最大利润
int[][] dp = new int[n][2];
// 转移方程
// dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
// dp[i][1] = max(dp[i-1][1], -prices[i])
// base case dp[i][0] = 0 dp[i][1] = -prices[i];
for(int i=0;i<n;i++){
// base case
if(i==0){
// 不持股为0
dp[i][0] = 0;
// 持股为当天股价的相反数，因为只交易一次
dp[i][1] = -prices[i];
continue;
}
// 转移方程
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
}
return dp[n-1][0];
}
}
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
定义一个dp[i] 表示以i结尾的连续子数组的和为dp[i]，每个dp[i] 有两个选择，接着前面的 和自己一个人。
复杂度分析：
时间复杂度：O(N)，；
空间复杂度：O(N)，状态数组的长度为 N。
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
// dp[i] 以i结尾的最大和
int[] dp = new int[n];
dp[0] = nums[0];
for(int i=1;i<n;i++){
// 自己作为起始， 续上前面的
dp[i] = Math.max(nums[i], dp[i-1]+nums[i]);
}
return Arrays.stream(dp).max().getAsInt();
}
}
可以状态压缩下
复杂度分析：
时间复杂度：O(N)
空间复杂度：O(1)
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int maxAns=nums[0];
int preSum = 0;
for(int i=0;i<n;i++){
preSum = Math.max(nums[i], preSum+nums[i]);
maxAns = Math.max(maxAns, preSum);
}
return maxAns;
}
}
栈
有效的括号
方法一：不用hashMap，只用栈
思路：用栈存左括号，如果遇到右括号则判断栈顶是否为其对应的左括号。
时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public boolean isValid(String s) {
if(s.length()%2!=0){
return false;
}
Stack<Character> stack = new Stack<>();
for(int i=0;i<s.length();i++){
Character c = s.charAt(i);
if(c=='(' || c=='[' || c=='{'){
stack.push(c);
}else{
if(stack.isEmpty()){
return false;
}
Character top = stack.pop();
if(!(top=='(' && c==')' || top=='[' && c==']' || top=='{' && c=='}' )){
return false;
}
}
}
return stack.isEmpty();
}
}
方法二：用hashmap+栈
思路：首先用map存括号对，key为右括号用于匹配；用栈存左括号；遍历字符串遇左括号入栈，遇右括号则判断栈不为空且栈顶元素和当前key对应value匹配。
时间复杂度：O(n)
空间复杂度：O(n+6)。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，本题中字符串只包含 6种括号，∣Σ∣=6。相加即可得到总空间复杂度。
class Solution {
public boolean isValid(String s) {
int n = s.length();
if(n%2!=0){
return false;
}
// 存左括号
Stack<Character> stack = new Stack<>();
// 存括号对
HashMap<Character,Character> pairs = new HashMap<>(){{
put(')','(');
put(']','[');
put('}','{');
}};
for(Character c : s.toCharArray()){
if(pairs.containsKey(c)){
// 说明是右括号
if(stack.isEmpty() || stack.peek()!=pairs.get(c)){
return false;
}
stack.pop();
}else{
// 说明是左括号，直接入栈
stack.push(c);
}
}
return stack.isEmpty();
}
}
