整理了一些很有趣的问题

  • get maximum subarray sum no larger than k
    • nlogn 的解法(n^2的解法我就不说了)
1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSumNoLargerThanK(int []nums,int k){
        int sum =0,maxVal=Integer.MIN_VALUE;
        TreeSet<Integer> set =new TreeSet<>();
        set.add(0);
        for(int x:nums){
            sum +=x;
            Integer it = set.ceiling(sum-k);
            if(it!=null)
                maxVal=Math.max(maxVal,sum-it);
            set.add(sum);
        }
        return maxVal;
    }
  • merge two sorted array to get maximum number
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
//special test case: 
//int[]nums1= {2,5,6,4,4,0};
//int []nums2 = {7,3,8,0,6,5,7,6,2};
public boolean greater(int[]nums1,int start1,int[]nums2,int start2){
        int m = nums1.length,n = nums2.length;
        while(start1<m && start2<n){
            if(nums1[start1]>nums2[start2])
                return true;
            else if(nums1[start1]<nums2[start2])
                return false;
            else{
                start1++;
                start2++;
            }
        }
        return start1!=m;
    }
    public int []getMaxi(int[]nums1,int[]nums2){
        int m=  nums1.length,n=nums2.length;
        int k = m+n;
        int []res=new int[k];
        int ind =0,start1=0,start2=0;
        while(ind<k){
            res[ind++]=greater(nums1,start1,nums2,start2)?nums1[start1++]:nums2[start2++];
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//we try to make the (h,k), k is the position we want to isert the number. How?, arrange the large number first.
public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]!=o2[0])
                    return Integer.compare(o2[0],o1[0]);
                else
                    return Integer.compare(o1[1],o2[1]);
            }
        });
        int n=people.length;
        List<int[]>res=new ArrayList<>();
        for(int i=0;i<n;++i){
            res.add(people[i][1],people[i]);
        }
        return res.toArray(new int[people.length][]);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//424 Longest Repeating Character Replacement
    //很有意思的地方在于不需要更新max，其实就是自动把<len 的string过滤了
    //第一次提交每次都更新了maxCnt
    public int characterReplacement(String s, int k) {
        char []ss=s.toCharArray();
        int n = ss.length,start=0,end=0,len=0,maxCnt=0;
        int []cnt = new int[26];
        while(end<n){
            maxCnt=Math.max(maxCnt,++cnt[ss[end++]-'A']);
            while(end-start-maxCnt>k){
                cnt[ss[start++]-'A']--;
            }
            len = Math.max(len,end-start);
        }
        return len;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//dp
public int longestPalindromeSubseq(String s){
	int n  = s.length();
	int [][]dp = new int[n][n];
	for(int i=n-1;i>=0;--i){
		dp[i][i]=1;
		for(int j=i+1;j<n;++j){
			if(s.charAt(i)==s.charAt(j)){
				dp[i][j]=dp[i+1][j-1]+2;
			}else{
				dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
			}
		}
	}
}