[公开]编外聘用人员支出经费中标公告

015/MyLeetCode

/22. Generate Parentheses/GenerateParentheses.java
package com.qwen2015.leetcode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
* Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
* <p>
* For "(()", the longest valid parentheses substring is "()", which has length = 2.
* <p>
* For ")()())", the longest valid parentheses substring is "()()", which has length = 4.
* <p>
* Example 1:
* <p>
* Input: "(()"
* Output: 2
* Explanation: The longest valid parentheses substring is "()".
* <p>
* Example 2:
* <p>
* Input: ")()())"
* Output: 4
* Explanation: The longest valid parentheses substring is "()()".
* <p>
* Example 3:
* <p>
* Input: ""
* Output: 0
* Explanation: The longest valid parentheses substring is "".
* <p>
* Note:
* <p>
* s consists of parentheses only.
*
* @author Qwen
* @version 1.0
* @date 2019/8/9 16:57
*/
public class LongestValidParentheses {

/**
* 使用栈
*
* @param s
* @return
*/
public int longestValidParentheses(String s) {
// 使用栈存储字符的下标
Stack<Integer> stack = new Stack<>();
stack.push(-1);

int length = s.length();
int max = 0;
for (int i = 0; i < length; i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
// 如果栈顶元素为'('，则弹出，否则不弹出
if (!stack.isEmpty() && stack.peek() != -1) {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
max = Math.max(max, i - stack.peek());
}
} else {
stack.push(i);
}
}
}
return max;
}

/**
* 使用队列
*
* @param s
* @return
*/
public int longestValidParentheses1(String s) {
int length = s.length();
if (length == 0) {
return 0;
}
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
int max = 0;
for (int i = 1; i < length; i++) {
if (s.charAt(i) == ')') {
int top = queue.peek();
if (top != -1 && s.charAt(top - 1) == '(') {
queue.poll();
queue.offer(i);
max = Math.max(max, i - queue.peek() + 1);
} else {
queue.offer(i);
}
}
}
return max;
}
}

/28. Implement strStr()/ImplementStrStr.java
package com.qwen2015.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
* Implement strStr()
* <p>
* Implement 'strStr()'.
* <p>
* Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
* <p>
* Example 1:
* <p>
* Input: haystack = "hello", needle = "ll"
* Output: 2
* <p>
* Example 2:
* <p>
* Input: haystack = "aaaaa", needle = "aaa"
* Output: 0
* <p>
* Note:
* <p>
* haystack and needle consist of only lower-case letters.
* needle is a non-empty string.
* <p>
* Follow up:
* <p>
* If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
*
* @author Qwen
* @version 1.0
* @date 2019/8/10 14:21
*/
public class ImplementStrStr {

public int strStr(String haystack, String needle) {
if (haystack == null || needle == null) {
return -1;
}
if (haystack.length() == 0) {
return 0;
}

return indexOf(haystack, needle);
}

private int indexOf(String haystack, String needle) {
if (haystack == null || needle == null || haystack.length() == 0 || needle.length() == 0) {
return -1;
}
int hLen = haystack.length();
int nLen = needle.length();
if (nLen > hLen) {
return -1;
}
int j = 0;
for (int i = 0; i < hLen - nLen + 1; i++) {
j = i;
while (j < hLen && needle.charAt(j) == haystack.charAt(i)) {
j++;
i++;
}
if (j == hLen) {
return i - j;
}
}
return -1;
}

public static void main(String[] args) {
String haystack = "hello";
String needle = "ll";
int index = new ImplementStrStr().strStr(haystack, needle);
System.out.println(index);