题目
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
说明:
- 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
- 你可以假定输入的先决条件中没有重复的边。
提示:
- 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
- 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
- 拓扑排序也可以通过 BFS 完成。
思路
拓扑排序过程：
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。
重复执行此过程，若无剩余点则删除的顺序即为一个答案，若有则无解。
ps：将给的参数转换成图会更快一些，懒得写了。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] indegree=new int[numCourses];
int[] res=new int[numCourses];
for (int[] prerequisite : prerequisites) {
indegree[prerequisite[0]]++;
}
boolean flag=true;
int count=0;
while (flag&&count<numCourses){
flag=false;
int i=0;
while (i<numCourses){
if (indegree[i]==0){
indegree[i]=-1;
res[count++]=i;
flag=true;
break;
}
++i;
}
for (int[] prerequisite : prerequisites) {
if (prerequisite[1]==i)indegree[prerequisite[0]]--;
}
}
if (count==numCourses)return res;
return new int[0];
}
}
|
题目
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
1
2
3
| 输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
|
示例 2:
1
2
3
| 输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
|
思路
首先的思路就是dp。写的过于复杂了一点。。
评论区带佬的代码：
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE, imax = 1, imin = 1;
for(int i=0; i<nums.length; i++){
if(nums[i] < 0){ int tmp = imax; imax = imin; imin = tmp;}
imax = Math.max(imax*nums[i], nums[i]);
imin = Math.min(imin*nums[i], nums[i]);
max = Math.max(max, imax);
}
return max;
}
}
|
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public int maxProduct(int[] nums) {
int res = Integer.MIN_VALUE;
int i = 0;
int positive=1;
int negative=1;
while (i < nums.length) {
if (nums[i] == 0) {
while (i<nums.length&&nums[i] == 0) {
++i;
res = Math.max(res,0);
}
positive=1;
negative=1;
}
if (i==nums.length)break;
if (nums[i]>0){
positive*=nums[i];
negative*=nums[i];
res=Math.max(res,positive);
}
else {
if (negative<0){
int tmp=positive;
positive=negative*nums[i];
res=Math.max(res,positive);
negative=tmp*nums[i];
}
else {
negative=positive*nums[i];
positive=1;
res=Math.max(res,negative);
}
}
++i;
}
return res;
}
}
|
题目
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
示例 2:
1
2
3
| 输入: "abca"
输出: True
解释: 你可以删除c字符。
|
注意:
- 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
思路
简单的双指针，一个指向头，一个指向尾，因为有一次删除的机会，所以第一次遇到不相等的字符时，可以left+1，或right-1；之后在遇到直接返回false。指针走位则为true。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public boolean validPalindrome(String s) {
int left=0,right=s.length()-1;
while (left<right){
if (s.charAt(left)!=s.charAt(right)){
return validPalindrome(s,left+1,right)||validPalindrome(s,left,right-1);
}
left++;right--;
}
return true;
}
public boolean validPalindrome(String s,int left,int right){
while (left<right){
if (s.charAt(left)!=s.charAt(right)){
return false;
}
left++;right--;
}
return true;
}
}
|
题目
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，‘e’，‘i’，‘o’，‘u’ ，在子字符串中都恰好出现了偶数次。
示例 1：
1
2
3
| 输入：s = "eleetminicoworoep"
输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
|
示例 2：
1
2
3
| 输入：s = "leetcodeisgreat"
输出：5
解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
|
示例 3：
1
2
3
| 输入：s = "bcbcbc"
输出：6
解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
|
提示：
- 1 <= s.length <= 5 x 10^5
- s 只包含小写英文字母。
思路
第一感觉没啥好的想法，先暴力试一下。
从后往前遍历，主要是要确定左边可以的位置。按照单个字母来看，每次左边可以的位置要么是0，要么是第一次位置的下一位。所以我们记录一下每个字母第一次出现的位置和目前字母是否为偶数即可。然后取五个字母可以的最大值作为left。大部分情况下成功。。。
5个数的奇偶一共有32种状态，记录每个状态最早出现的位置。如果子串[0，i]与字串[0,j]状态相同，那么字串[i+1,j]的状态一定是0。上面的思路错误的原因就是因为没有一起记录，是单个记录的。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| class Solution {
public int findTheLongestSubstring(String s) {
Map<Character,Integer> map=new HashMap<>(5);
map.put('a',1);map.put('e',2);map.put('i',4);
map.put('o',8);map.put('u',16);
int[] location=new int[32];
Arrays.fill(location,-1);
location[0]=0;
int status=0,res=0;
for (int i = 0; i < s.length(); i++) {
char c=s.charAt(i);
if (c=='a'||c=='e'||c=='i'||c=='o'||c=='u'){
status^=map.get(c);
}
if (location[status]==-1)location[status]=i+1;
else res=Math.max(res,i+1-location[status]);
}
return res;
}
}
错误代码：
class Solution {
public int findTheLongestSubstring(String s) {
int[][] count=new int[26][2];
int left=0;
int res=0;
for (int i = 0; i < s.length(); i++) {
char c=s.charAt(i);
if (c=='a'||c=='e'||c=='i'||c=='o'||c=='u'){
if (count[c-'a'][1]==0){
count[c-'a'][1]=i+1;
count[c-'a'][0]=i+1;
left=i+1;
}else {
if (count[c-'a'][0]==0){
count[c-'a'][0]=count[c-'a'][1];
left=Math.max(left,count[c-'a'][1]);
}
else {
if (left!=count[c-'a'][0]){
count[c-'a'][0]=0;
}else {
count[c-'a'][0]=0;
left=Math.max(count[0][0],Math.max(count['e'-'a'][0],Math.max(count['i'-'a'][0],Math.max(count['o'-'a'][0],count['u'-'a'][0]))));
}
}
}
}
res=Math.max(res,i+1-left);
}
return res;
}
}
|
题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
1
2
3
| 输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
|
示例 2：
思路
动态规划，dp[i][j]记录从i到j子串是否回文，依次找长度从2到字符串长度的回文子串，dp[i][j]=(s[i]==s[j] \and dp[i+1][j-1])。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public String longestPalindrome(String s) {
int len=s.length();
if (len<2)return s;
boolean[][] dp=new boolean[len][len];
String res=s.substring(0,1);
for (int i = 0; i < len-1; i++) {
dp[i][i]=true;
if (s.charAt(i)==s.charAt(i+1)){
dp[i][i+1]=true;
res=s.substring(i,i+2);
}
}
dp[len-1][len-1]=true;
int step=3;
while (step <= len) {
for (int i = 0; i < len - step + 1; i++) {
if (s.charAt(i) == s.charAt(i + step - 1) && dp[i + 1][i + step - 2]) {
dp[i][i + step - 1] = true;
res = s.substring(i, i + step);
}
}
++step;
}
return res;
}
}
|
题目
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
1
2
| 前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
|
返回如下的二叉树：
思路
递归，每次得到两个序列，前序的第一个元素即根结点，中序遍历以根为分界分为左右子树序列。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| (这里直接贴了官方的代码,不想写了。。)
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
int length = preorder.length;
for (int i = 0; i < length; i++) {
indexMap.put(inorder[i], i);
}
TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
return root;
}
public TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
if (preorderStart > preorderEnd) {
return null;
}
int rootVal = preorder[preorderStart];
TreeNode root = new TreeNode(rootVal);
if (preorderStart == preorderEnd) {
return root;
} else {
int rootIndex = indexMap.get(rootVal);
int leftNodes = rootIndex - inorderStart, rightNodes = inorderEnd - rootIndex;
TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes, inorder, inorderStart, rootIndex - 1, indexMap);
TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
root.left = leftSubtree;
root.right = rightSubtree;
return root;
}
}
}
|
题目
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
1
2
| 输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
|
说明：
- 如果 S 中不存这样的子串，则返回空字符串
""。
- 如果 S 中存在这样的子串，我们保证它是唯一的答案。
思路
滑动窗口，哈希表记录当前的T中字符的数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| func minWindow(s string, t string) string {
if len(s) < len(t) {
return ""
}
hash := make(map[byte]int)
for i := 0; i < len(t); i++ {
hash[t[i]]++
}
l, count, max, results := 0, len(t), len(s)+1, ""
for r := 0; r < len(s); r++ {
if _,ok:=hash[s[r]];ok {
hash[s[r]]--
if hash[s[r]] >= 0 {
count--
}
}
for l < r {
if _, ok := hash[s[l]]; ok {
if hash[s[l]] < 0 {
hash[s[l]]++
}else {
break
}
}
l++
}
if count == 0 && max > r-l+1 {
max = r - l + 1
results = s[l : r+1]
}
}
return results
}
|
题目
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
1
2
3
4
| nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
|
示例 2:
1
2
3
4
| nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
|
思路
二分，两个数组找第k大的数。先分别取两个数组第k/2个数，然后进行比较丢弃。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len=nums1.length+nums2.length;
if (len%2!=0){
return help(nums1,nums2,0,nums1.length,0,nums2.length,len/2+1);
}else return (help(nums1,nums2,0,nums1.length,0,nums2.length,len/2)+help(nums1,nums2,0,nums1.length,0,nums2.length,len/2+1))/2;
}
public double help(int[] nums1,int[] nums2,int l1,int r1,int l2,int r2,int k){
if (l1==r1)return nums2[l2+k-1];
if (l2==r2)return nums1[l1+k-1];
if (k==1) return Math.min(nums1[l1],nums2[l2]);
int mid1=Integer.MAX_VALUE;
int mid2=Integer.MAX_VALUE;
if ((k+1)/2-1<r1-l1)mid1=nums1[l1+(k+1)/2-1];
if ((k+1)/2-1<r2-l2)mid2=nums2[l2+(k+1)/2-1];
if (mid1==mid2)return mid1;
else if (mid1<mid2){
return help(nums1,nums2,l1+k/2,r1,l2,r2,k-k/2);
}else return help(nums1,nums2,l1,r1,k/2+l2,r2,k-k/2);
}
}
|
题目
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
1
2
3
4
5
6
7
8
9
10
| LRUCache cache = new LRUCache( 2 );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);
cache.put(3, 3);
cache.get(2);
cache.put(4, 4);
cache.get(1);
cache.get(3);
cache.get(4);
|
思路
Hash表+双向链表。Hash直接使用HashMap存储键到链表节点的映射，自定义简单的双向链表存储键值对。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| class LRUCache {
class ListNode{
public ListNode last;
public ListNode next;
int val;
int key;
public ListNode(int k,int v){
key=k;val=v;
}
}
private int capacity;
private Map<Integer,ListNode> map;
ListNode head=null;
ListNode tail=null;
public LRUCache(int capacity) {
this.capacity=capacity;
map=new HashMap<>();
}
public int get(int key) {
if (!map.containsKey(key))
return -1;
ListNode cur=map.get(key);
if (cur==head)return cur.val;
if (cur.last!=null){
cur.last.next=cur.next;
if (cur.next!=null){
cur.next.last=cur.last;
}else {
tail=cur.last;
}
}
cur.next=head;
head.last=cur;
head=cur;
return cur.val;
}
public void put(int key, int value) {
if (map.containsKey(key)){
map.get(key).val=value;
get(key);
return;
}
ListNode node=new ListNode(key,value);
if (head==null){
head=tail=node;
}else {
node.next=head;
head.last=node;
head=node;
}
if (map.size()==capacity){
map.remove(tail.key);
tail=tail.last;
tail.next=null;
}
map.put(key,node);
}
}
|
