406. Minimum Size Subarray
同向双指针
https://www.lintcode.com/problem/minimum-size-subarray-sum/description?_from=ladder&&fromId=4
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
if(nums==null || nums.length ==0){
return -1;
}
int sum = 0;
int res = Integer.MAX_VALUE;
for(int l =0,r=0;r<nums.length;r++){
sum +=nums[r];
while(sum>=s){
res = Math.min(res,r-l+1);
sum = sum -nums[l];
l++;
}
}
return res==Integer.MAX_VALUE?-1:res;
}
}
384. Longest Substring Without Repeating Characters
同向双指针
public class Solution {
/**
* @param s: a string
* @return: an integer
*/
public int lengthOfLongestSubstring(String s) {
// write your code here
if(s==null || s.length()==0){
return 0;
}
Set<Character> set = new HashSet<>();
int left =0;
int right =0;
int ans = Integer.MIN_VALUE;
while(left<s.length() && right<s.length()){
while(right<s.length() && !set.contains(s.charAt(right))){
set.add(s.charAt(right));
ans = Math.max(ans,right-left+1);
right++;
}
set.remove(s.charAt(left));
left++;
}
return ans == Integer.MIN_VALUE ? -1 : ans;
}
}
32. Minimum Window Substring
同向双指针
https://www.lintcode.com/problem/minimum-window-substring/description
public class Solution {
/**
* @param source : A string
* @param target: A string
* @return: A string denote the minimum window, return "" if there is no such a string
*/
public String minWindow(String source , String target) {
// write your code here
if(source==null || source.length()==0){
return source;
}
Map<Character,Integer> map = new HashMap<>();
for(int i=0;i<target.length();i++){
char c = target.charAt(i);
if(map.containsKey(c)){
map.put(c,map.get(c)+1);
}else{
map.put(c,1);
}
}
int i=0;
int j =0;
String res= "";
int min = Integer.MAX_VALUE;
int countT = target.length();
int countS = 0;
//while 循环不要加 j<source.length 的条件
while(i<source.length()){
while(j<source.length() && countS<countT){
char c = source.charAt(j);
if(map.containsKey(c)){
if(map.get(c)>0) countS++;
map.put(c,map.get(c)-1);
}
j++;
}
if(countS>=countT){
if(j-i<min){
min = j-i;
res = source.substring(i,j);
}
}
char cc = source.charAt(i);
if(map.containsKey(cc)){
if(map.get(cc)>=0) countS--;
map.put(cc,map.get(cc)+1);
}
i++;
}
return res;
}
}
386. Longest Substring with At Most K Distinct Characters
同向双指针
public class Solution {
/**
* @param s: A string
* @param k: An integer
* @return: An integer
*/
public int lengthOfLongestSubstringKDistinct(String s, int k) {
// write your code here
if(s==null || s.length()==0 || k==0){
return 0;
}
int l = 0;
int r = 0;
int ans = 0;
int sum = 0;
int[] cnt = new int[256];
for(r=0;r<s.length();r++){
cnt[s.charAt(r)]++;
if(cnt[s.charAt(r)]==1){
sum++;
}
while(sum>k){
cnt[s.charAt(l)]--;
if(cnt[s.charAt(l)]==0){
sum--;
}
l++;
}
ans = Math.max(ans,r-l+1);
}
return ans;
}
}
465. Kth Smallest Sum In Two Sorted Arrays
heap
class Pair{
int x;
int y;
int sum;
Pair(int x, int y,int sum){
this.x = x;
this.y = y;
this.sum = 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) {
// write your code here
if (A == null || A.length == 0) {
return 0;
}
if (B == null || B.length == 0) {
return 0;
}
if (k == 0) {
return 0;
}
Comparator<Pair> comparator = new Comparator<Pair>(){
@Override
public int compare(Pair o1,Pair o2){
return o1.sum-o2.sum;
}
};
PriorityQueue<Pair> minHeap = new PriorityQueue<Pair>(comparator);
boolean[][] visit = new boolean[A.length][B.length];
minHeap.add(new Pair(0,0,A[0]+B[0]));
visit[0][0] = true;
int[] dx = {0,1};
int[] dy = {1,0};
for(int i=1;i<k;i++){
Pair center = minHeap.poll();;
for(int j = 0;j<2;j++){
if(center.x + dx[j]>A.length-1 || center.y + dy[j]>B.length-1 || visit[center.x+dx[j]][center.y+dy[j]]){
continue;
}
minHeap.add(new Pair(center.x+dx[j],center.y+dy[j],A[center.x+dx[j]]+B[center.y+dy[j]]));
visit[center.x+dx[j]][center.y+dy[j]] = true;
}
}
return minHeap.peek().sum;
}
}
401. Kth Smallest Number in Sorted Matrix
heap
class Pair {
private int x;
private int y;
private int val;
public Pair(int x, int y, int val) {
this.x = x;
this.y = y;
this.val = val;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = 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
if (matrix == null || matrix.length == 0 || matrix.length * matrix[0].length < k) {
return -1;
}
Comparator<Pair> comparator = new Comparator<Pair>() {
@Override
public int compare(Pair o1, Pair o2) {
return o1.getVal() - o2.getVal();
}
};
int r = matrix.length;
int c = matrix[0].length;
PriorityQueue<Pair> minHeap = new PriorityQueue<>(comparator);
boolean[][] visited = new boolean[r][c];
minHeap.add(new Pair(0, 0, matrix[0][0]));
visited[0][0] = true;
for (int i = 1; i <= k - 1; i++) {
Pair cur = minHeap.poll();
if (cur.getX() + 1 < r && !visited[cur.getX() + 1][cur.getY()]) {
minHeap.add(new Pair(cur.getX() + 1, cur.getY(), matrix[cur.getX() + 1][cur.getY()]));
visited[cur.getX() + 1][cur.getY()] = true;
}
if (cur.getY() + 1 < c && !visited[cur.getX()][cur.getY() + 1]) {
minHeap.add(new Pair(cur.getX(), cur.getY() + 1, matrix[cur.getX()][cur.getY() + 1]));
visited[cur.getX()][cur.getY() + 1] = true;
}
}
return minHeap.peek().getVal();
}
}
543. Kth Largest in N Arrays
heap
https://www.lintcode.com/problem/kth-largest-in-n-arrays/description?_from=ladder&&fromId=4
class Node{
int value;
int fromId;
int index;
public Node(int value,int fromId,int index){
this.value = value;
this.fromId = fromId;
this.index = index;
}
}
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
if(arrays==null || arrays.length==0 ||k<=0){
return 0;
}
Comparator<Node> comparator = new Comparator<Node>(){
@Override
public int compare(Node o1,Node o2){
return o2.value - o1.value;
}
};
PriorityQueue<Node> maxHeap = new PriorityQueue<Node>(comparator);
int n = arrays.length;
//sort and put first column into heap
for(int i =0;i<n;i++){
Arrays.sort(arrays[i]);
if(arrays[i].length>0){
int fromId = i;
int index = arrays[i].length-1;
int value = arrays[i][index];
maxHeap.add(new Node(value,fromId,index));
}
}
for(int i=1;i<k;i++){
Node curr = maxHeap.poll();
if(curr.index>0){
curr.index--;
maxHeap.add(new Node(arrays[curr.fromId][curr.index],curr.fromId,curr.index));
}
}
return maxHeap.peek().value;
}
}