1. 有效的括号 leetcode .cn/problems/valid-parentheses/description/" rel="nofollow">题目链接
题目要求:给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 代码及思路 经典的使用栈来解决的问题 遇到左括号将对应的右括号入栈,遇到右括号则与栈顶元素进行比较,若不同则直接返回false,相同则弹出栈顶元素 最后栈为空,表明完全匹配,返回true 代码
class Solution { public boolean isValid ( String s) { if ( s. length ( ) % 2 != 0 ) return false ; Deque< Character> cache= new LinkedList< > ( ) ; for ( int i= 0 ; i< s. length ( ) ; i++ ) { char c= s. charAt ( i) ; if ( c== '(' ) { cache. push ( ')' ) ; } else if ( c== '[' ) { cache. push ( ']' ) ; } else if ( c== '{' ) { cache. push ( '}' ) ; } else if ( c== ')' ) { if ( cache. isEmpty ( ) || c!= cache. pop ( ) ) return false ; } else if ( c== ']' ) { if ( cache. isEmpty ( ) || c!= cache. pop ( ) ) return false ; } else if ( c== '}' ) { if ( cache. isEmpty ( ) || c!= cache. pop ( ) ) return false ; } } return cache. isEmpty ( ) ; }
}
2. 滑动窗口最大值 leetcode .cn/problems/sliding-window-maximum/" rel="nofollow">题目链接
题目要求:给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 使用一个单调递增的双向队列解决问题 遍历数组元素,在每一次遍历中当窗口大小大于k时,将队列最初元素出栈 循环将小于当前元素的队尾元素出栈 当达到窗口大小后开始记录窗口最大值,即为队列队首元素 注意队列中存储的是元素的下标值 代码
class Solution { public int [ ] maxSlidingWindow ( int [ ] nums, int k) { Deque< Integer> cache= new LinkedList< > ( ) ; int [ ] res= new int [ nums. length- k+ 1 ] ; int j= 0 ; for ( int i= 0 ; i< nums. length; i++ ) { while ( ! cache. isEmpty ( ) && i- k+ 1 > cache. getFirst ( ) ) { cache. pollFirst ( ) ; } while ( ! cache. isEmpty ( ) && nums[ i] > nums[ cache. getLast ( ) ] ) { cache. pollLast ( ) ; } cache. offer ( i) ; if ( i- k+ 1 >= 0 ) res[ j++ ] = nums[ cache. getFirst ( ) ] ; } return res; }
}
3. 字符串解码 leetcode .cn/problems/decode-string/description/" rel="nofollow">题目链接
题目要求:给定一个经过编码的字符串,返回它解码后的字符串。 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。 此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。 代码及思路 使用栈解决问题,分别使用一个栈存储数字和之前的字符串 遇到‘[’将数字和当前字符串入栈,遇到’]'则将之前的数字和字符串取出和当前的字符串做拼接 代码
class Solution { public String decodeString ( String s) { Stack< Integer> numbers= new Stack< > ( ) ; Stack< String> strs= new Stack< > ( ) ; int num= 0 ; String cur= "" ; for ( int i= 0 ; i< s. length ( ) ; i++ ) { char c= s. charAt ( i) ; if ( c>= '0' && c<= '9' ) { num= num* 10 + c- '0' ; } else if ( c== '[' ) { numbers. push ( num) ; num= 0 ; strs. push ( cur) ; cur= "" ; } else if ( c== ']' ) { StringBuilder temp= new StringBuilder ( strs. pop ( ) ) ; int len= numbers. pop ( ) ; for ( int j= 0 ; j< len; j++ ) { temp. append ( cur) ; } cur= temp. toString ( ) ; } else { cur= cur+ c; } } return cur; }
}
4. 回文链表 leetcode .cn/problems/palindrome-linked-list/description/" rel="nofollow">题目链接
题目要求:给你一个单链表的头节点 head ,请你判断该链表是否为 回文链表。如果是,返回 true ;否则,返回 false 。 代码及思路 使用栈解决,先遍历链表将所有节点的值压入栈中 再次从头遍历链表,每次将节点值与栈顶元素相比较 代码
class Solution { public boolean isPalindrome ( ListNode head) { if ( head== null ) return true ; if ( head. next== null ) return true ; ListNode cur= head; Stack< Integer> cache= new Stack< > ( ) ; while ( cur!= null ) { cache. push ( cur. val) ; cur= cur. next; } cur= head; while ( cur!= null ) { int num= cache. pop ( ) ; if ( cur. val!= num) return false ; cur= cur. next; } return true ; }
}
5. 每日温度 leetcode .cn/problems/daily-temperatures/description/" rel="nofollow">题目链接
题目要求:给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。 代码及思路 使用一个单调递减栈来存储温度的下标值 遍历温度数组,然后循环找出栈中小于当前温度的温度下标值,更新answer数组 将当前温度的下标入栈 代码
class Solution { public int [ ] dailyTemperatures ( int [ ] temperatures) { int [ ] answers= new int [ temperatures. length] ; Stack< Integer> cache= new Stack< > ( ) ; for ( int i= 0 ; i< temperatures. length; i++ ) { while ( ! cache. isEmpty ( ) && temperatures[ i] > temperatures[ cache. peek ( ) ] ) { int j= cache. pop ( ) ; answers[ j] = i- j; } cache. push ( i) ; } return answers; }
}