关于图形的题目一般归属到hard里面，需要打开思路
默认小顶堆，
new PriorityQueue<Integer>((a, b) -> b - a);// store num <= median
，这个是大顶堆
PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){
@Override
public int compare(ListNode o1,ListNode o2){
if (o1.val<o2.val)
return -;
else if (o1.val==o2.val)
return ;
else
return ;
}
});
动态规划的动作，初始状态的定义，状态的缓存，状态之间的动作关系。
130. Surrounded Regions
注意使用m*n表示数组的行数跟列数
X X X X
X O O X
X X O X
X O X X
完成后
X X X X
X X X X
X X X X
X O X X
思路：这个利用原来的传染方法，一旦发现边缘地带有O，利用深度搜索方法将O切换成为*，然后再执行一次遍历。
309. Best Time to Buy and Sell Stock with Cooldown
动态规划问题，这个定义了三个状态，状态0，是停盘状态， 状态1是购买后的状态，状态2是卖出后的状态
定义三个数组，数组下标i表示的是第i次操作。
//这里给出代码
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= ) return ;
int[] s0 = new int[prices.length];
int[] s1 = new int[prices.length];
int[] s2 = new int[prices.length];
s0[] = ;//停盘
s1[] = -prices[];// 买
s2[] = Integer.MIN_VALUE;// 卖
for (int i = ; i < prices.length; i++) {
s0[i] = Math.max(s0[i - ], s2[i - ]);
s1[i] = Math.max(s0[i - ] - prices[i], s1[i - ]);
s2[i] = Math.max(s2[i - ], s1[i - ] + prices[i]);
}
return Math.max(s0[prices.length - ], s2[prices.length - ]);
}
}
28. Implement strStr()
KMP算法的实现
这个是简单的版本
public class Solution {
public int strStr(String haystack, String needle) {
char[] has = haystack.toCharArray();
char[] nee = needle.toCharArray();
if (nee.length == ) {
return ;
}
int[] next = getNext(nee);
int i = ;
int j = ;
while (i < has.length) {
if (has[i] == nee[j]) {
i++;
j++;
if (j == nee.length) return i - nee.length;
} else {
if (j != ) {
j = next[j - ];
} else {
i++;
}
}
}
return -;
}
public int[] getNext(char[] arr) {
int[] next = new int[arr.length];
next[] = ;
int i = ;
int len = ;
while (i < arr.length) {
if (arr[i] == arr[len]) {
len++;
next[i] = len;
i++;
} else {
if (len == ) {
next[i] = ;
i++;
} else {
len = next[len - ];
}
}
}
return next;
}
}
214. Shortest Palindrome
给定一个字符串，加上最小的得到一个回文的字符串
也是利用到KMP的算法
public String shortestPalindrome(String s) {
String temp = s + "#" + new StringBuilder(s).reverse().toString();
int[] table = getTable(temp);
//get the maximum palin part in s starts from 0
return new StringBuilder(s.substring(table[table.length - ])).reverse().toString() + s;
}
一道树的题目
思路:原来是要个构建二叉树进递归实现，现在换成了三个数组的实现，第一个数组按照需求将数据依次存入，第二个数组用来缓存是否出现了，第三个素组用来存储父节点，然后对于连续两个同一结点的，就是4层树，但是输入形式是113,212，224等代表不同的东西
public static int sum(){
ArrayList list = new ArrayList();
Scanner scanner= new Scanner(System.in);
int inputData = ;
while(scanner.hasNext()){
inputData =scanner.nextInt();
if(inputData == ){
break;
}
list.add(inputData);
}
int resu = ;
int[] sarr = new int[]; //
int[] hasvalue = new int[];
for (int k = ; k < ; k++) {
hasvalue[k] = -;
}
for (int i = ; i < list.size(); i++) {
int temp = (int)list.get(i);
int lev = (temp / ) - ;
int ind = (temp % ) / - ;
int val = temp % ;
int index = (int) (Math.pow(, lev) + ind - );
if (lev > ) {
int faindex = (int) (Math.pow(, lev - ) - + ind / );
sarr[index] = sarr[faindex] + val;
hasvalue[index] = ;
} else {
sarr[index] = val;
hasvalue[index] = ;
}
}
int[] fa = new int[];
fa[] = ;
int faTemp = ;
for (int j = ; j < ; j += ) {
fa[j] = faTemp;
fa[j + ] = faTemp;
faTemp++;
}
for (int i = ; i < ; i += ) {
if (hasvalue[i] == - && hasvalue[i + ] == -) {
resu += sarr[fa[i]];
}
}
for (int j = ; j < ; j++) {
if (hasvalue[j] > ){
resu += sarr[j];
}
}
return resu;
}
给定不同颜色，1-9，给你一串气球，随便剪，剪完之后每一个子串都不重复，这个可以采用递归法，但是时间有一定的限制。最好的方法是动态规划。
我当时采用的是尾递归的方法，存在两种可改进的地方，一是如果从当前的子串进行切分的时候，如果不满足条件，没有进行break的操作。二，对于重复的出现的字符串没有加Map进行缓存做了过多次的判断
//这个是正统的动态规划问题
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = ;
if (sc.hasNext()) {
n = sc.nextInt();
}
int[] a = new int [n + ];
int[] dp = new int [n + ];
int[] cut = new int[];
for (int i = ; i <= n; i++) {
a[i] = sc.nextInt();
}
dp[] = ;
for(int i = ; i <= n; i++){
for (int k = ; k < ; k++) {
cut[k] = ;
}
for(int j = ; j < i; j++){
cut[a[i - j]]++; //从某个地方开始切分，我这边记录下出现的缓存
if(cut[a[i - j]] > )// 已经从这个地方切过了再往前去也没有什么更好的办法了的，就停止了
break;
dp[i] = (int) ((dp[i] + dp[i - j - ]) % maxn);
}
}
System.out.println(Arrays.toString(dp));
}
//还是这个方法比厉害
360附件题目，分金子，也是个很不错的动态规划问题
A、B两伙马贼得到金子，输入一个长度为n的数组字符串，问如果A先选，那么求A最后能得到的最大的收入是多少
//也是一道动态规划的题目，dp是一个二维数组，其中dp[i][i + a]表示从第i到 i + a个子数组中A先选的到金额数目，sum就显得很有用了，还是画图进行考虑，看看两边从哪个选能得到相对更大的数
for (int ca = ; ca < T; ca++) {
int n = ;
n = scanner.nextInt();
int[] arr = new int[];
for (int j = ; j <= n; j++) {
arr[j] = scanner.nextInt();
}
int[] sum = new int[];
sum[] = ;
for (int k = ; k <= n; k++) {
sum[k] = sum[k - ] + arr[k];
}
int [][] dp = new int[][];
for(int a = ; a < n ; a++) {
for(int j = ; j < n ; j++) {
for(int i = ; i <= n - j ; i++){
dp[i][i + j] = Math.max(sum[i + j - ] - sum[i - ] - dp[i][i + j - ] + arr[i + j], sum[i + j] - sum[i] - dp[i + ][i + j] + arr[i]);
}
}
System.out.println("Case " + ca + ":" + dp[][n] + " " + (sum[n] - dp[][n]) );
}
42. Trapping Rain Water
就是看能放下多少的雨水
一个outofbox的方法，可以从左边到右边left得到leftmax与rightmax，选取一方低的，得到相关的差值,保证水不会冲另外一方流出去
140. Word Break II
更新下backtrack的方法，从前面往后进行递归，动态规划用于缓存后面的子串的结果
同时，String.startsWith()方法,需要注意
//回溯法的升级版本
public class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
return DFSHelp(s, wordDict, new HashMap<String, LinkedList<String>>());
}
public List<String> DFSHelp(String s, List<String> wordDict, HashMap<String, LinkedList<String>> map) {
if (map.containsKey(s)) {
return map.get(s);
}
LinkedList<String> res = new LinkedList<String>();
if (s.length() == ) {
res.add("");
return res;
}
for (String word : wordDict) {
if (s.startsWith(word)) {
List<String> sublist = DFSHelp(s.substring(word.length()), wordDict, map);
for (String sub : sublist) {
res.add(word + (sub.isEmpty() ? "" : " ") + sub);
}
}
}
map.put(s, res);
return res;
}
}
212. Word Search II
给定一个二维数组，数组中的每一个位置为一个字符，给定一个字符串数组，输出其中可以被字符进行组成的字符串，两个字符之间必须是邻居
思路：构建单词查找树，进行DFS，设置访问标记, Trie树的一个应用
//深度搜索
public class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> resu = new LinkedList<String>();
TrieNode root = makeTrieNode(words);
for (int i = ; i < board.length; i++) {
for (int j = ; j < board[].length; j++) {
dfs(board, root, i, j, resu);
}
}
return resu;
}
public void dfs (char[][] board, TrieNode root, int i, int j, List<String> resu) {
char c = board[i][j];
if (c == '#' || root.next[c - 'a'] == null) {
return;
}
root = root.next[c - 'a'];
if (root.word != null) {
resu.add(root.word);
root.word = null;//de-duplicate
}
board[i][j] = '#';
if (i > ) dfs(board, root, i - , j, resu);
if (j > ) dfs(board, root, i, j - , resu);
if (i < board.length - ) dfs(board, root, i + , j, resu);
if (j < board[].length - ) dfs(board, root, i, j + , resu);
board[i][j] = c;
}
public TrieNode makeTrieNode (String[] words) {
TrieNode root = new TrieNode();
for (String s : words) {
TrieNode p = root;
for (char c : s.toCharArray()) {
int i = c - 'a';
if (p.next[i] == null) {
p.next[i] = new TrieNode();
}
p = p.next[i];
}
p.word = s;
}
return root;
}
class TrieNode {
TrieNode[] next = new TrieNode[];
String word;
}
}
10. Regular Expression Matching
字符匹配问题，采用动态规划的方法，’.’表示的是匹配一个字符，‘*’表示的是匹配前面任意多个字符，判断初始字符串s含有通配符的字符串p是否相等
public class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
boolean[][] dp = new boolean[s.length()+][p.length()+];
dp[][] = true;
for (int i = ; i < p.length(); i++) {
if (p.charAt(i) == '*' && dp[][i-]) {
dp[][i+] = true;
}//这个地方是为了去掉前面为0 的影响,这个时候i为0，也就是s串还没有开始匹配
}
for (int i = ; i < s.length(); i++) {
for (int j = ; j < p.length(); j++) {
if (p.charAt(j) == '.') {
dp[i+][j+] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
dp[i+][j+] = dp[i][j];
}
if (p.charAt(j) == '*') {
if (p.charAt(j-) != s.charAt(i) && p.charAt(j-) != '.') {
dp[i+][j+] = dp[i+][j-];
} else {
dp[i+][j+] = (dp[i+][j] || dp[i][j+] || dp[i+][j-]);
}
}
}
}
return dp[s.length()][p.length()];
}
}
76. Minimum Window Substring
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.
给定两个字符串，S如果包含T，返回的是S中包含T的最小长度的子串，如果不包含返回“”，
思路：O(n)时间复杂度，用两个HashMap进行缓存。根据start不段进行更新操作
下面给出的是用一个的方法
public String minWindow(String s, String t) {
HashMap<Character,Integer> map = new HashMap();
for(char c : s.toCharArray())
map.put(c,);
for(char c : t.toCharArray()) {
if(map.containsKey(c))
map.put(c,map.get(c)+);
else
return "";
}
int start =, end=, minStart=,minLen = Integer.MAX_VALUE, counter = t.length();
while(end < s.length()) {
char c1 = s.charAt(end);
if(map.get(c1) > )
counter--;
map.put(c1,map.get(c1)-);
end++;
while(counter == ) {
if(minLen > end-start) {
minLen = end-start;
minStart = start;
}
char c2 = s.charAt(start);
map.put(c2, map.get(c2)+);
if(map.get(c2) > )
counter++;
start++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart,minStart+minLen);
}
128. Longest Consecutive Sequence
给定一个数组，输出连续不断的最长的子序列的长度。
思路：out of box ， 给定一个Map缓存即可，其长度，每当过来一个数，判断n - 1，作为left，n+1作为right，那么长度为 left + right + 1，同时更新n-left，与n+right
329. Longest Increasing Path in a Matrix
这个就是采用递归，之一注意递归条件，i<0 或者 i>length, j <0或者j >length或者对当前的值进行比较。
295. Find Median from Data Stream
找到数据流中的中位数
思路：两个堆
PriorityQueue pq = new PriorityQueue<Integer>((a, b) -> b - a);// 大顶堆
PriorityQueue pq = new PriorityQueue<Integer>;// 默认小顶堆
PriorityQueue pq = new PriorityQueue<Integer>((a, b) -> a - b);// 小顶堆
41. First Missing Positive
给一个无序的数组，要求返回第一个丢失的正数。
思路：将正数i放在数组的第i-1的位置上，然后再遍历得到。
84. Largest Rectangle in Histogram
要求，输入一组数组，输出得到最大的矩形面积，用stack进行index的缓存，当height[i] > stack.peek(),进行入栈动作，否则进行面积的计算 i- 1 - satck.peek();此处 i为stack.pop()
239. Sliding Window Maximum
315. Count of Smaller Numbers After Self
要求，给定一个数组，从右边开始，统计出右边数中比它本身还要小的数
思路：采用BST进行二叉树的构建，时间复杂度为NlongN，要小心的处理好插入节点当前循环的逻辑
//递归的构造树的时候，需要处理好当前结点的位置关系
public class Solution {
public List<Integer> countSmaller(int[] nums) {
Integer [] ans = new Integer[nums.length];
Node root = null;
for (int i = nums.length - ; i >= ; i--) {
root = insertNode(nums[i], root, ans, i, );
}
return Arrays.asList(ans);
}
public Node insertNode(int num, Node root, Integer[] ans, int i, int preNum) {
if (root == null) {
root = new Node(num, );
ans[i] = preNum;
} else if (root.val == num) {
root.dup++;
ans[i] = preNum + root.sum;
} else if (root.val > num) {
root.sum++;
root.left = insertNode(num, root.left, ans, i, preNum);
} else {
root.right = insertNode(num, root.right, ans, i, preNum + root.sum + root.dup);
}
return root;
}
class Node {
Node left, right;
//sum 表示左边树的个数，dup表示当前结点重复的个数，val表示当前结点的值
int val, sum, dup = ;// sum to count left node nums
public Node (int v, int s) {
val = v;
sum = s;
}
}
}
297. Serialize and Deserialize Binary Tree
要求：对一个二叉树进行序列化和反序列化，中间结果为String
思路： 利用递归的方法，采用前序遍历，不足的地方补”X”,利用StirngBuilder进行缓存
在反序列化的时候用Queue进行数据的缓存。Queue的底层实现是linkedlist
239. Sliding Window Maximum
给定滑动窗口，取出滑动窗口里面元素的最大值。这个采用双向队列的方式进行,一定要明白这个双向队列里面放的是数组元素的下标，
思路： 1.移除滑动窗口左面的下标
2.从后面进行判断，对下标记中index如果小于当前nums[i],就移除
3.对返回结果进行修改
Deque<Integer> dequ = new ArrayDeque<Integer>();
dequ.pollLast()
dequ.peekLast()
23. Merge k Sorted Lists
这个暂时采用优先队列来做，但是我可以只维护其中数组数量大小的队列，新定义一个数据结构。
149. Max Points on a Line
判断经过同一条直线的最大的点的数量,根据公式进行推导
用 Since a is a rational, there exists y0 and x0, y0/x0=(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a
这两个数进行判定
//这个地方值得学习的是取两个数的最大公约数
//以及针对两个变量，加上 x和 y的缓存
private int generateGCD(int a,int b){
if (b == ) return a;
else return generateGCD(b,a%b);
}
146. LRU Cache
要求：实现一个缓存，给定capacity容量大小的限定
思路：本来打算用队列来实现，其实是错误的，容量不足时，需要删除最后一个，其中读和插入操作都会影响优先级别。
这个地方采用的是双链表加HashMap进行缓存的结构,注意回顾双链表的删除结点操作以及追加到头结点后面的操作。
4. Median of Two Sorted Arrays
要求：两个有序数组，输出两个数组合并以后的中位数。
思路：从中位数的定义出发，找出两个数组的下标 i和j的关系，如果是奇数个，返回的max_left，如果是偶数个，返回max_left 与 min_right的平均数。
44. Wildcard Matching
要求：实现通配符。这里面的？匹配一个字符， *匹配任意一个子串，同时也包括0。
与10. Regular Expression Matching正则表达式匹配相对应
//通配符，匹配，解决了,这块也可以写成动态规划的形式
// dp[i + 1][j + 1] = dp[i][j + 1],*匹配多个
//dp[i + 1][j + 1] = dp[i + 1][j], *匹配为空
public class Solution {
public boolean isMatch(String str, String pattern) {
int s = 0, p = 0, match = 0, starIdx = -1;
while (s < str.length()){
// advancing both pointers
if (p < pattern.length() && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
s++;
p++;
}
// * found, only advancing pattern pointer
else if (p < pattern.length() && pattern.charAt(p) == '*'){
starIdx = p;//记录
match = s;
p++;
}
// last pattern pointer was *, advancing string pointer
else if (starIdx != -1){
p = starIdx + 1;//
match++;
s = match;
}
//current pattern pointer is not star, last patter pointer was not *
//characters do not match
else return false;
}
//check for remaining characters in pattern
while (p < pattern.length() && pattern.charAt(p) == '*')
p++;
return p == pattern.length();
}
}
Sunday算法的实现，优于与kmp算法
两个都是字符串比较算法，Sunday在处理重复元素的时，时间复杂度比kmp要差
public static int SundaySearch(){
GetNext();
System.out.println(Arrays.toString(_next));
int destLen = dest.length();
int patternLen = pattern.length();
if (destLen == ) return -;
for (int i = ; i <= destLen - patternLen;){
int j = i;//dest[j]
int k = ;//pattern[k]
for (; k < patternLen && j < destLen && dest.charAt(j) == pattern.charAt(k); j++, k++)
;//do nothing
if (k == patternLen)//great! find it!
return i;
else{
if (i + patternLen < destLen) {
i += (patternLen - _next[dest.charAt(i + patternLen)]);
}
else
return -;
}
}
return -;
}
public static void GetNext(){
int len = pattern.length();//get the length
for (int i = ; i < ; i++)
_next[i] = -;
for (int i = ; i < len; i++)
_next[pattern.charAt(i)] = i;
}
alibaba的一道时间间隔内，限制访问次数的题目
// 在单位时间间隔内，限制访问次数。
static String[] demo(int M, int N, List<String> listlog) throws ParseException {
// M 是时间间隔 N是限制次数
SimpleDateFormat formatter = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
List<String> resu = new ArrayList<String>();
Map<String, LinkedList<String>> mapqu = new HashMap<String, LinkedList<String>>();
for (int i = ; i < listlog.size(); i++) {
String temp = listlog.get(i);
String [] parm = getPam(temp);
String name = parm[];
if ( resu.contains(name)) {
continue;
}
if (mapqu.containsKey(name)) {
LinkedList<String> qu = mapqu.get(name);
qu.add(temp);
if (qu.size() > N) {
String be = qu.poll();
Date bt = formatter.parse(be.substring(, ));
Date da = formatter.parse(temp.substring(, ));
int min = (int) ((da.getTime() - bt.getTime()) / / );
if (min < M) {
resu.add(name);
continue;
}
}
} else {
LinkedList<String> qu = new LinkedList<String>();
qu.add(temp);
mapqu.put(name, qu);
}
}
String [] re = new String[resu.size()];
for (int i = ; i < resu.size(); i++) {
re[i] = resu.get(i);
}
return re;
}
public static String[] getPam(String s) {
return s.split("#");
}
122. Best Time to Buy and Sell Stock II
只要明白a[i + 1] - a[i] + a[i] - a[i - 1] = a[i + 1] - a[i - 1];即可
309. Best Time to Buy and Sell Stock with Cooldown
定义了三个状态， 三个数组进行状态的缓存
123. Best Time to Buy and Sell Stock III
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
现在函数要求只有两次的购买机会
//这里的动态规划买的只是比我便宜的时候，我来买
public int maxProfit(int[] prices) {
if (prices == null || prices.length < ) return ;
int[] hold1 = new int[prices.length];
int[] hold2 = new int[prices.length];
int[] res1 = new int[prices.length];
int[] res2 = new int[prices.length];
hold1[] = -prices[];
hold2[] = Integer.MIN_VALUE;
res1[] = ;
res2[] = ;
for (int i = ; i < prices.length; i++) {
hold1[i] = Math.max(hold1[i - ], - prices[i]);
res1[i] = Math.max(res1[i - ], hold1[i - ] + prices[i]);
hold2[i] = Math.max(hold2[i - ], res1[i - ] - prices[i]);
res2[i] = Math.max(res2[i - ], hold2[i- ] + prices[i]);
}
return Math.max(res1[prices.length - ], res2[prices.length - ]);
}
188. Best Time to Buy and Sell Stock IV
要求：Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
最多交易k次：
public class Solution {
public int maxProfit(int k, int[] prices) {
if (k >= prices.length / ) {
return getMax(prices);
}
int[][] hold = new int[prices.length][k + ];
int[][] unhold = new int[prices.length][k + ];
hold[][] = -prices[];
for (int i = ; i < prices.length; i++) {
hold[i][] = Math.max(hold[i - ][], -prices[i]);
}
for (int j = ; j <= k; j++) {
hold[][j] = -prices[];
}
for (int i = ; i < prices.length; i++) {
for (int j = ; j <= k; j++) {
hold[i][j] = Math.max(hold[i - ][j], unhold[i - ][j] - prices[i]);
unhold[i][j] = Math.max(unhold[i - ][j], hold[i - ][j - ] + prices[i]);
}
}
return Math.max(hold[prices.length-][k], unhold[prices.length - ][k]);
}
public int getMax(int[] prices) {
int result = ;
for (int i = ; i < prices.length; i++) {
if (prices[i] - prices[i - ] > ) {
result += prices[i] - prices[i - ];
}
}
return result;
}
}
链表反转问题
只是需要两个额外的Node结点即可。
数组中出现次数大于n / 2的，投票处理
*Arrays.copyOf(result, index)不包含index
pow（x, n）
对n减半，对x进行平方，递归调用
231. Power of Two
判断一个数是不是2的次方
public boolean isPowerOfTwo(int n) {
if( n<=){
return false;
}
return (n&(n-))==;
}
是不是3的次方
public boolean isPowerOfThree(int n) {
if(n>)
while(n%==) n /= ;
return n==;
}
是不是 4的次方
public boolean isPowerOfFour(int num) {
while (num> && (num&)==)
num>>=;
return num==;
}
链表快排java版本
这个双指针的问题，注意q指针每次都先行一步
public static void quickSort(ListNode head, ListNode tail) {
if (head != tail) {
ListNode partion = getPartion (head, tail);
quickSort(head, partion);
quickSort(partion.next, tail);
}
}
public static ListNode getPartion(ListNode beg, ListNode end) {
int key = beg.val;
ListNode p = beg;
ListNode q = beg.next;// quick
while (q != end) {
if (q.val < key) {
p = p.next;
swap(p, q);
}
q = q.next;
}
swap(beg, p);
return p;
}
public static void swap(ListNode p, ListNode q) {
int temp = p.val;
p.val = q.val;
q.val = temp;
}
![7大排序算法详解+java实现[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)