20 有效的括号
思路1:栈
遇到左括号则入栈，遇到右括号则 出 栈顶元素，看是否与栈顶括号匹配，若不匹配返回false。最后检查栈是否为空，空则返回true，否则返回false。
总而言之：判断括号的有效性可以使用「栈」这一数据结构来解决。
遍历给定的字符串 s。当我们遇到一个左括号时，将这个左括号入栈。
当遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 s 无效，返回 False。
！！为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。
在遍历结束后，如果栈中没有左括号，说明我们将字符串 s 中的所有左括号闭合，返回 True，否则返回 False。
！！！注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回False，省去后续的遍历判断过程。
自己：
class Solution {
public boolean isValid(String s) {
Stack<String> st=new Stack<>();
for(char c:s.toCharArray()){
if(c=='('||c=='{'||c=='['){
st.push(String.valueOf(c));//String.valueOf方法：char->string
}
else{
if(st.empty()){
return false;
}
else{
String top=st.peek();
st.pop();
if( (c==')'&&top.equals("(") ) || (c=='}'&&top.equals("{") ) || (c==']'&&top.equals("[")) ){
continue;
}
else{
return false;
}
}
}
}
return st.empty()?true:false;
}
}
别人：
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};//!!!
Deque<Character> stack = new LinkedList<Character>();//!!!
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);//!!!
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}
同样的思路，发现linklist也可以用来实现栈，也有push pop peek方法，一般都不用Stack！记住！
class Solution {
private static final Map<Character,Character> map = new HashMap<Character,Character>(){{
put('{','}'); put('[',']'); put('(',')');
}};
public boolean isValid(String s) {
//LinkedList<Character> stack = new LinkedList<Character>() {{ add('?'); }};
//不需要添加？啦，但是要知道这是一种常用的初始化方式
LinkedList<Character> stack = new LinkedList<Character>();
for(Character c : s.toCharArray()){
if(map.containsKey(c)) stack.addLast(c);
else if(stack.size()==0 || map.get(stack.removeLast()) != c) return false;
}
return stack.size() == 0;
}
}
看看别人的简洁代码！！太nb了！！不用哈希表！
class Solution {
public boolean isValid(String s) {
Stack<Character>stack = new Stack<Character>();//!!
for(char c: s.toCharArray()){
if(c=='(')stack.push(')');
else if(c=='[')stack.push(']');
else if(c=='{')stack.push('}');
else if(stack.isEmpty()||c!=stack.pop())return false;//妙
}
return stack.isEmpty();
}
}
21 合并两个有序链表
思路1:双指针
/**
* 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 dummyhead=new ListNode(),pre=dummyhead;
while(l1!=null && l2!=null){
if(l1.val<l2.val){
pre.next=l1;
l1=l1.next;
}
else if(l1.val>l2.val){
pre.next=l2;
l2=l2.next;
}
else{ //其实也可以不用特意写出==的情况
pre.next=l1;
l1=l1.next;
pre=pre.next;
pre.next=l2;
l2=l2.next;
}
pre=pre.next;
}
if(l1!=null){
pre.next=l1;
}
if(l2!=null){
pre.next=l2;
}
return dummyhead.next;
}
}
思路2:递归
/**
* 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) {
if(l1==null){
return l2;
}
else if(l2==null){
return l1;
}
if(l1.val<l2.val){
l1.next=mergeTwoLists(l1.next,l2);
return l1;
}
else{
l2.next=mergeTwoLists(l1,l2.next);
return l2;
}
}
}
22 括号生成
思路1：利用dfs生成所有可能的括号组合，每生成一个就判断是否有效
13% 90% 很烂的样子。。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans=new ArrayList<>();
StringBuilder path=new StringBuilder();
dfs(n,n,path,ans);
return ans;
}
void dfs(int left,int right,StringBuilder path,List<String> ans){
if(left==0&&right==0){
String s=String.valueOf(path);
if(isValid(s)){
ans.add(s);
}
else return;
}
if(left>0){
path.append("(");
dfs(left-1,right,path,ans);
path.deleteCharAt(path.length()-1);//加完还要减回去
}
if(right>0){
path.append(")");
dfs(left,right-1,path,ans);
path.deleteCharAt(path.length()-1);//加完还要减回去
}
}
boolean isValid(String s){
LinkedList<Character> stack=new LinkedList();
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='('){
stack.push('(');
}
else{
if(stack.size()==0){
return false;
}
else{
stack.pop();
}
}
}
if(stack.size()!=0)
return false;
else
return true;
}
}
思路2:dfs+剪枝
体会一下别人的代码，加入了适当的剪枝
注意这里的判断条件： if(count1 >= count2){...}
保证生成的组合必然都是有效！
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<String>();
generate(res, "", 0, 0, n);
return res;
}
//count1统计“(”的个数，count2统计“)”的个数
public void generate(List<String> res , String ans, int count1, int count2, int n){
if(count1 > n || count2 > n) return;
if(count1 == n && count2 == n) res.add(ans);
if(count1 >= count2){
String ans1 = new String(ans);
generate(res, ans+"(", count1+1, count2, n);
generate(res, ans1+")", count1, count2+1, n);
}
}
}
模仿思路写的
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans=new ArrayList<>();
StringBuilder path=new StringBuilder();
dfs(0,0,n,path,ans);
return ans;
}
void dfs(int left,int right,int n,StringBuilder path,List<String> ans){
if(left==n&&right==n){
ans.add(String.valueOf(path));
return;
}
if(left>=right&&left<n){
path.append("(");
dfs(left+1,right,n,path,ans);
path.deleteCharAt(path.length()-1);//加完还要减回去
}
if(left>right&right<n){
path.append(")");
dfs(left,right+1,n,path,ans);
path.deleteCharAt(path.length()-1);//加完还要减回去
}
}
}
class Solution {
List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
dfs(n, n, "");
return res;
}
private void dfs(int left, int right, String curStr) {
if (left == 0 && right == 0) { // 左右括号都不剩余了，递归终止
res.add(curStr);
return;
}
if (left > 0) { // 如果左括号还剩余的话，可以拼接左括号
dfs(left - 1, right, curStr + "(");
}
if (right > left) { // 如果右括号剩余多于左括号剩余的话，可以拼接右括号
dfs(left, right - 1, curStr + ")");
}
}
}
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
if (n == 0) {
return res;
}
StringBuilder path = new StringBuilder();
dfs(path, n, n, res);
return res;
}
/**
* @param path 从根结点到任意结点的路径，全程只使用一份
* @param left 左括号还有几个可以使用
* @param right 右括号还有几个可以使用
* @param res
*/
private void dfs(StringBuilder path, int left, int right, List<String> res) {
if (left == 0 && right == 0) {
// path.toString() 生成了一个新的字符串，相当于做了一次拷贝，这里的做法等同于「力扣」第 46 题、第 39 题
res.add(path.toString());
return;
}
// 剪枝（如图，左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝，注意这个细节）
if (left > right) {
return;
}
if (left > 0) {
path.append("(");
dfs(path, left - 1, right, res);
path.deleteCharAt(path.length() - 1);
}
if (right > 0) {
path.append(")");
dfs(path, left, right - 1, res);
path.deleteCharAt(path.length() - 1);
}
}
}
23 合并k个升序链表
思路1:k个指针
每次取k个指针中最小的值，然后指针后移。直到指针都为null。
(思考一下，这其实就是小顶堆呀，没想到！！)
但是代码不会写 而且感觉很复杂 但实际并不复杂
别人写的
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
while (true) {
ListNode minNode = null;
int minPointer = -1;
for (int i = 0; i < k; i++) {
if (lists[i] == null) {
continue;
}
if (minNode == null || lists[i].val < minNode.val) {
minNode = lists[i];
minPointer = i;
}
}
if (minPointer == -1) {
break;
}
tail.next = minNode;
tail = tail.next;
lists[minPointer] = lists[minPointer].next;
}
return dummyHead.next;
}
}
思路2：堆、优先队列
用容量为K的最小堆优先队列，把链表的头结点都放进去，然后出队当前优先队列中最小的，挂上链表，然后让出队的那个节点的下一个入队，再出队当前优先队列中最小的，直到优先队列为空。
ps: java优先队列默认是小顶堆，可以自己传入排序方法。大顶堆传相反的排序方法就好了。
一开始纠结空指针在队列里怎么办，因为想着队列大小恒定为k，也无法比较值。
但是你为什么要让空指针入队呢，因为队列大小并不恒为k。它容量应该是逐渐减小，而且我们只需要堆顶元素。
ps:优先队列常用方法
peek()//返回队首元素
poll()//返回队首元素，队首元素出队列
add()//添加元素
size()//返回队列元素个数
isEmpty()//判断队列是否为空，为空返回true,不空返回false
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
ListNode dummyHead = new ListNode(0);
ListNode curr = dummyHead;
PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {//!!!
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
for (ListNode list : lists) {
if (list == null) {
continue;
}
pq.add(list);
}
while (!pq.isEmpty()) {
ListNode nextNode = pq.poll();
curr.next = nextNode;
curr = curr.next;
if (nextNode.next != null) {
pq.add(nextNode.next);
}
}
return dummyHead.next;
}
}
思路3：顺序合并
看链接的前置知识和方法1
https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode-solutio-2/
思路4:分治
实际是对思路3的优化
没理解
看链接的最底部：两两合并
https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/4-chong-fang-fa-xiang-jie-bi-xu-miao-dong-by-sweet/
代码没看没实现
class Solution {
public ListNode mergeKLists(ListNode[] lists){
if(lists.length == 0)
return null;
if(lists.length == 1)
return lists[0];
if(lists.length == 2){
return mergeTwoLists(lists[0],lists[1]);
}
int mid = lists.length/2;
ListNode[] l1 = new ListNode[mid];
for(int i = 0; i < mid; i++){
l1[i] = lists[i];
}
ListNode[] l2 = new ListNode[lists.length-mid];
for(int i = mid,j=0; i < lists.length; i++,j++){
l2[j] = lists[i];
}
return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head = null;
if (l1.val <= l2.val){
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
return head;
}
}
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int left, int right) {
if (left == right) return lists[left];
int mid = left + (right - left) / 2;
ListNode l1 = merge(lists, left, mid);
ListNode l2 = merge(lists, mid + 1, right);
return mergeTwoLists(l1, l2);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}
32 最长有效括号
注意：题目要求找出最长有效（格式正确且连续）括号子串的长度。一开始只想到用栈找出格式正确的括号对数，忽略了要一直连续的条件。（栈多用于解决括号问题）
那么既然可以利用栈确定匹配正确的括号对，那么我们怎么求出最长有效（格式正确且连续）括号子串的长度？
思路：
将匹配的()都赋值为1，最后计算最长的连续1的长度
trick：将(的下标入栈,不用将(入栈，因为栈里面都是(
一句话总结：先找到所有可以匹配的索引号，然后找出最长连续数列！
44% 50%
class Solution {
public int longestValidParentheses(String s) {
LinkedList<Integer> stack=new LinkedList<>();
char[] ss=s.toCharArray();
for(int i=0;i<ss.length;i++){
if(ss[i]=='('){
stack.push(i);//将(的下标入栈
}
else{
if(stack.size()==0){
ss[i]='0';
}
else{
ss[i]='1';
ss[stack.peek()]='1';
stack.pop();
}
}
}
//计算连续1的数目
int len=0,max=0;
for(int i=0;i<ss.length;i++){
if(ss[i]=='1'){
len++;
}
else if(ss[i]!='1'){//其实ss里面可能还有没匹配的'(' 但没关系，只要它不是1就好
max=Math.max(max,len);//要小心如果最后没有进入到这里，就可能没更新max
len=0;
}
}
return Math.max(max,len);
}
}
计算连续1的代码可以这样修改，这样绝对会更新max
//计算连续1的数目
int len=0,max=0;
for(int i=0;i<ss.length;i++){
if(ss[i]!='1'){
len=0;
continue;
}
len++;
max=Math.max(max,len);
}
return max;
ps:String.valueOf方法:可以将char等类型->string
思路2:倒序
没看懂 没实现
对字符串遍历，进行括弧有效性验证，记录最大的有效长度。同样的方式，倒序再来一次，取最大值。时间复杂度 2*s.length；速度极快，10ms超越100%的人群
public int longestValidParentheses(String s) {
char[] chars = s.toCharArray();
return Math.max(calc(chars, 0, 1, chars.length, '('), calc(chars, chars.length -1, -1, -1, ')'));
}
private static int calc(char[] chars , int i , int flag,int end, char cTem){
int max = 0, sum = 0, currLen = 0,validLen = 0;
for (;i != end; i += flag) {
sum += (chars[i] == cTem ? 1 : -1);
currLen ++;
if(sum < 0){
max = max > validLen ? max : validLen;
sum = 0;
currLen = 0;
validLen = 0;
}else if(sum == 0){
validLen = currLen;
}
}
return max > validLen ? max : validLen;
}
思路3:dp
动态规划，dp[i]表示以i结尾的最长有效括号长度
https://leetcode-cn.com/problems/longest-valid-parentheses/solution/dong-tai-gui-hua-si-lu-xiang-jie-c-by-zhanganan042/
讲解得非常清楚(代码没看 没实现)
注意下这段话：(加入了自己的理解)
情况2: s[i−1]==')' 这种情况下，如果前面有和s[i]组成有效括号对的字符，即形如((....))，这样的话，就要求s[i−1]位置必然是有效的括号对(意味着dp[i-1]>0)，否则s[i]绝对无法和前面对字符组成有效括号对,也就意味着dp[i]==0。如果s[i−1]位置是有效的，也就是dp[i-1]>0，这时，我们只需要找到和s[i]配对对位置，并判断其是否是
(即可。和其配对对位置为：i−dp[i−1]−1。
这样的话，即使s[i-1]不是有效子字符串的一部分，也没关系。递推关系可以判断。
下面的代码也没看
class Solution(object):
def longestValidParentheses(self, s):
length = len(s)
if length == 0:
return 0
dp = [0] * length
for i in range(1,length):
#当遇到右括号时，尝试向前匹配左括号
if s[i] == ')':
pre = i - dp[i-1] -1;
#如果是左括号，则更新匹配长度
if pre>=0 and s[pre] == '(':
dp[i] = dp[i-1] + 2
#处理独立的括号对的情形 类似()()、()(())
if pre>0:
dp[i] += dp[pre-1]
return max(dp);
ps:动态规划题目分析的 4 个步骤：
- 确定状态
1.研究最优策略的最后一步
2.化为子问题 - 转移方程
1.根据子问题定义得到 - 初始条件和边界情况
- 计算顺序
