Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return -1 instead.
Given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.
开始我们很容易想到的方法是：
此时的时间复杂度是O(n^3),稍作改动记录一下sum, 可以使时间复杂度变为O(n^2)：
变成：
因为数组里的所有数值都是正的，所以算数组0到1位的和即s = 0， t= 1时候如果比7小，第一位的和即s = 1， t = 1的时候就不用看了；同理因为0到2位的和比7小，1到2位的和就不用算了：
所以我们总结了窗口类指针的模板, 重点是根据题目的不同改变需要满足的条件。这个优化有以下特点：
这种方法的时间复杂度是O(2n)即O(n), 因为每个元素最多被访问两次：
固定了i，知道遇到第一个j使得和大于等于s，记录下来：
public class Solution {
/**
* @param nums: an array of integers
* @param s: an integer
* @return: an integer representing the minimum size of subarray
*/
public int minimumSize(int[] nums, int s) {
// write your code here
int j = 0, i = 0;
int sum =0;
int ans = Integer.MAX_VALUE;
for(i = 0; i < nums.length; i++) {
while(j < nums.length && sum < s) {
sum += nums[j];
j ++;
}
if(sum >=s) {
ans = Math.min(ans, j - i);
}
sum -= nums[i];
}
if(ans == Integer.MAX_VALUE)
ans = -1;
return ans;
}
}Given a string, find the length of the longest substring without repeating characters.
For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3.
For “bbbbb” the longest substring is “b”, with the length of 1.
用hash记录下走过的characters
public class Solution {
/**
* @param s: a string
* @return: an integer
*/
//方法一：
public int lengthOfLongestSubstring(String s) {
int[] map = new int[256]; // map from character‘s ASCII to its last occured index
int j = 0;
int i = 0;
int ans = 0;
for (i = 0; i < s.length(); i++) {
while (j < s.length() && map[s.charAt(j)]==0) {
map[s.charAt(j)] = 1;
ans = Math.max(ans, j-i + 1);
j ++;
}
map[s.charAt(i)] = 0;
}
return ans;
}
}Given a string source and a string target, find the minimum window in source which will contain all the characters in target.
If there is no such window in source that covers all characters in target, return the emtpy string “”.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in source.
Clarification
Should the characters in minimum window has the same order in target?
Not necessary.
Example
For source = “ADOBECODEBANC”, target = “ABC”, the minimum window is “BANC”
public class Solution {
//方法一:
int initTargetHash(int []targethash, String Target) {
int targetnum =0 ;
for (char ch : Target.toCharArray()) {
targetnum++;
targethash[ch]++;
}
return targetnum;
}
boolean valid(int []sourcehash, int []targethash) {
for(int i = 0; i < 256; i++) {
if(targethash[i] > sourcehash[i])
return false;
}
return true;
}
public String minWindow(String Source, String Target) {
// queueing the position that matches the char in T
int ans = Integer.MAX_VALUE;
String minStr = "";
int[] sourcehash = new int[256];
int[] targethash = new int[256];
initTargetHash(targethash, Target);
int j = 0, i = 0;
for(i = 0; i < Source.length(); i++) {
while( !valid(sourcehash, targethash) && j < Source.length() ) {
sourcehash[Source.charAt(j)]++;
j++;
}
if(valid(sourcehash, targethash) ){
if(ans > j - i ) {
ans = Math.min(ans, j - i );
minStr = Source.substring(i, j );
}
}
sourcehash[Source.charAt(i)]--;
}
return minStr;
}
}其中valid函数可以优化，即加上一个count使得时间上O(256n)变成O(n);
我考虑用两个hashset：一个target_hash, 一个source_hash，实现下看看。
Given a string s, find the length of the longest substring T that contains at most k distinct characters.
For example, Given s = “eceba”, k = 3,
T is “eceb” which its length is 4.
j不用退的情况，考虑我们的模板。
public class Solution {
/**
* @param s : A string
* @return : The length of the longest substring
* that contains at most k distinct characters.
*/
public int lengthOfLongestSubstringKDistinct(String s, int k) {
// write your code here
int maxLen = 0;
// Key: letter; value: the number of occurrences.
Map<Character, Integer> map = new HashMap<Character, Integer>();
int i, j = 0;
char c;
for (i = 0; i < s.length(); i++) {
while (j < s.length()) {
c = s.charAt(j);
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
if(map.size() ==k)
break;
map.put(c, 1);
}
j++;
}
maxLen = Math.max(maxLen, j - i);
c = s.charAt(i);
if(map.containsKey(c)){
int count = map.get(c);
if (count > 1) {
map.put(c, count - 1);
} else {
map.remove(c);
}
}
}
return maxLen;
}
}bfs一层一层啊，动规也是一层一层啊
3.他们思考的思路是怎么样的？
Find the kth smallest number in at row and column sorted matrix.
Example
Given k = 4 and a matrix:
[
[1 ,5 ,7],
[3 ,7 ,8],
[4 ,8 ,9],
]
return 5
堆得push和pop是log(n)时间的操作，top即求min/max是O(1)时间的操作
堆有很多种实现方式，priority_queue是常用的一种，还有斐波那契堆之类的。
class Pair {
public int x, y, val;
public Pair(int x, int y, int val) {
this.x = x;
this.y = y;
this.val = val;
}
}
class PairComparator implements Comparator {
public int compare(Pair a, Pair b) {
return a.val - b.val;
}
}
public class Solution {
/**
* @param matrix: a matrix of integers
* @param k: an integer
* @return: the kth smallest number in the matrix
*/
public int kthSmallest(int[][] matrix, int k) {
// write your code here
int[] dx = new int[]{0, 1};
int[] dy = new int[]{1, 0};
int n = matrix.length;
int m = matrix[0].length;
boolean[][] hash = new boolean[n][m];
PriorityQueue minHeap = new PriorityQueue(k, new PairComparator());
minHeap.add(new Pair(0, 0, matrix[0][0]));
for(int i = 0; i < k - 1; i ++){
Pair cur = minHeap.poll();
for(int j = 0; j < 2; j ++){
int next_x = cur.x + dx[j];
int next_y = cur.y + dy[j];
Pair next_Pair = new Pair(next_x, next_y, 0);
if(next_x < n && next_y < m && !hash[next_x][next_y]){
hash[next_x][next_y] = true;
next_Pair.val = matrix[next_x][next_y];
minHeap.add(next_Pair);
}
}
}
return minHeap.peek().val;
}
}
You can swap elements in the array
Example
In n=2 arrays [[9,3,2,4,7],[1,2,3,4,8]], the 3rd largest element is 7.
In n=2 arrays [[9,3,2,4,8],[1,2,3,4,2]], the 1st largest element is 9, 2nd largest element is 8, 3rd largest element is 7 and etc.
堆
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
class Node {
public int value, from_id, index;
public Node(int _v, int _id, int _i) {
this.value = _v;
this.from_id = _id;
this.index = _i;
}
}
public class Solution {
/**
* @param arrays a list of array
* @param k an integer
* @return an integer, K-th largest element in N arrays
*/
public int KthInArrays(int[][] arrays, int k) {
// Write your code here
Queue queue = new PriorityQueue(k, new Comparator() {
public int compare(Node o1, Node o2) {
if (o1.value > o2.value)
return -1;
else if (o1.value < o2.value)
return 1;
else
return 0;
}
});
int n = arrays.length;
int i;
for (i = 0; i < n; ++i) {
Arrays.sort(arrays[i]);
if (arrays[i].length > 0) {
int from_id = i;
int index = arrays[i].length - 1;
int value = arrays[i][index];
queue.add(new Node(value, from_id, index));
}
}
for (i = 0; i < k; ++i) {
Node temp = queue.poll();
int from_id = temp.from_id;
int index = temp.index;
int value = temp.value;
if (i == k - 1)
return value;
if (index > 0) {
index --;
value = arrays[from_id][index];
queue.add(new Node(value, from_id, index));
}
}
return -1;
}
}Given two integer arrays sorted in ascending order and an integer k. Define sum = a + b, where a is an element from the first array and b is an element from the second one. Find the kth smallest sum out of all possible sums.
Given [1, 7, 11] and [2, 4, 6].
For k = 3, return 7.
For k = 4, return 9.
For k = 8, return 15.
class Pair {
public int x, y, sum;
public Pair(int x, int y, int val) {
this.x = x;
this.y = y;
this.sum = val;
}
}
class PairComparator implements Comparator {
public int compare(Pair a, Pair b) {
return a.sum - b.sum;
}
}
public class Solution {
/**
* @param A an integer arrays sorted in ascending order
* @param B an integer arrays sorted in ascending order
* @param k an integer
* @return an integer
*/
public int kthSmallestSum(int[] A, int[] B, int k) {
int[] dx = new int[]{0, 1};
int[] dy = new int[]{1, 0};
boolean[][] hash = new boolean[A.length][B.length];
PriorityQueue minHeap = new PriorityQueue(k, new PairComparator());
minHeap.add(new Pair(0, 0, A[0] + B[0]));
for(int i = 0; i < k - 1; i ++){
Pair cur = minHeap.poll();
for(int j = 0; j < 2; j ++){
int next_x = cur.x + dx[j];
int next_y = cur.y + dy[j];
Pair next_Pair = new Pair(next_x, next_y, 0);
if(next_x < A.length && next_y < B.length && !hash[next_x][next_y]){
hash[next_x][next_y] = true;
next_Pair.sum = A[next_x] + B[next_y];
minHeap.add(next_Pair);
}
}
}
return minHeap.peek().sum;
}
}求矩阵/数组的第k大
1.定期整理自己做过的题目，Note
2.学会反思:
它属于哪一类？(归类)
和它同类的题目有什么相似之处？（集体特征）
这些题目思考的思路是怎么样的？（这个题属于哪一类）
本节要点概览：
九章算法高级班笔记1.透析热门互联网公司 FollowUp面试题
原文：https://www.cnblogs.com/jiuzhangsuanfa/p/9895673.html