leetcode1-300.docx

//单调栈的典型用途是用于找到数组中下一个比自身大的元素 (the next greater element, NGE), 可以在一次遍

历就获得所有元素的NGE.

//Permutations题递归函数process()里传的是i; 其他的递归+回溯题目传的都是j

//删除链表中节点的常用方式

h1.next = h1.next.next; //the one after the h1 need to be removed

“粉红色”的题目为有没搞懂的地方.

最长公共子序列：dp

最长公共子串： 可用 dp

最长递增子序列：dp

结。

由于回溯问题本身时间复杂度就很高，所以能用空间换时间就尽量使用空间。

总结

做题的时候，建议 先画树形图 ，画图能帮助我们想清楚递归结构，想清楚如何剪枝。拿题目中的示例，

想一想人是怎么做的，一般这样下来，这棵递归树都不难画出。

在画图的过程中思考清楚：

分支如何产生；

题目需要的解在哪里？是在叶子节点、还是在非叶子节点、还是在从根节点到叶子节点的路径？

哪些搜索会产生不需要的解的？例如：产生重复是什么原因，如果在浅层就知道这个分支不能产生需要的

结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？

Jump Game:

理解本质，nums[i] + i 的值才是决定是否能跳到下一个位置的关键因素，而不是单一的 nums[i] !!

当我们不熟悉的时候，怎么想到用动态规划来解决这个问题呢？我们需要从问题本身出发，寻找一些有用

的信息，例如本题中：

(i, j)位置只能从(i - 1, j)和(i, j - 1)走到，这样的条件就是在告诉我们这里转移是「无后效性」的，f(i, j)和任

何的 f(i', j') (i' > i, j' > j)无关。

动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的

统计方案数的问题，它们都存在一定的递推性质。前者的递推性质还有一个名字，叫做 「最优子结构」

——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。

快排:

我对滑动窗口的理解

先找到一个可行解，再优化这个可行解。

优化到不能优化，产生出一个可能的最优解。

继续找新的可行解，再优化这个可行解

……

在所有可能的最优解中，找出最优解。

1. Two Sum

Easy

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use

the same element twice.

if (arr == null || arr.length < 2) {

return new int[] { -1, -1 };

}

HashMap<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < arr.length; i++) {

int value = target - arr[i];

if (map.containsKey(value)) {

return new int[] { map.get(value), i };

}

map.put(arr[i], i);

}

HashMap<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < arr.length; i++) {

map.put(arr[i], i);

}

for (int i = 1; i < arr.length; i++) {

int value = target - arr[i];

if (map.containsKey(value) && map.get(value) != i) {

return new int[] { i, map.get(value) };

}

You are given two non-empty linked lists representing two non-negative integers. The digits are stored

in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a

linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

class Solution {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

if (l1 == null && l2 == null) {

return null;

}

ListNode head = null;

ListNode cur = null;

int carry = 0;

int num2 = l2 == null ? 0: l2.val;

l2 = l2 == null ? null : l2.next;

head = cur = new ListNode(sum % 10);

} else {

cur.next = new ListNode(sum % 10);

cur = cur.next;

}

}

if (carry > 0) {

}

3. Longest Substring Without Repeating Characters

public int lengthOfLongestSubstring(String s) {

if (s == null || s.length() == 0) {

return 0;

}

int len = s.length();

int max = Integer.MIN_VALUE;

char[] c = s.toCharArray();

for (int i = 0; i < len; i++) {

HashSet<Character> set = new HashSet<>();

int count = 1;

set.add(c[i]);

count++;

} else {

max = Math.max(max, count);

//i = i + 1; //注意, 这里不能再更新i了

}

return max;

}

}

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

public double findMedianSortedArrays(int[] arr1, int[] arr2) {

if (arr1.length == 0 && arr2.length == 0) {

return Double.MIN_VALUE;

}

int len1 = arr1.length;

int len2 = arr2.length;

int[] help = new int[len1 + len2];

Merge(arr1, arr2, help, len1, len2);

if (help.length % 2 == 1) {

return help[(help.length - 1) / 2];