IVN
0%

tag题

Posted on Edited on In
Symbols count in article: 25k Reading time ≈ 23 mins.

Tag题选编

2115. Find All Possible Recipes from Given Supplies

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
public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
    Set<String> res=new HashSet<>();
    int n=recipes.length;
    Map<String, Set<String>> map=new HashMap<>();
    for (int i = 0; i < n; i++) {
        map.put(recipes[i],new HashSet<>());
        for (String s : ingredients.get(i)) {
            map.get(recipes[i]).add(s);
        }
    }
    Deque<String> q=new LinkedList<>();
    for (String supply : supplies) {
        q.offer(supply);
    }
    while(!q.isEmpty()){
        String s=q.poll();
        for (String r : map.keySet()) {
            if(map.get(r).contains(s)){
                map.get(r).remove(s);
                if(map.get(r).size()==0){
                    res.add(r);
                    q.offer(r);
                }
            }
        }
    }
    return new ArrayList<>(res);
}

1048. Longest String Chain

思路：

  • Instead of adding a character, try deleting a character to form a chain in reverse.
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
public int longestStrChain(String[] words) {
    Map<String,Integer> map=new HashMap<>();
    int n=words.length;
    for (int i = 0; i < n; i++) {
        //string,index
        map.put(words[i],i);
    }
    boolean[] visited=new boolean[n];
    PriorityQueue<int[]> q=new PriorityQueue<>((a,b)->(b[1]!=a[1]
            ? b[1]-a[1] : words[b[0]].length()-words[a[0]].length()));
    for (int i = 0; i < n; i++) {
        q.offer(new int[]{i,1});
    }
    int res=0;
    while(!q.isEmpty()){
        int[] cur=q.poll();
        int i=cur[0];
        if(visited[i]){
            continue;
        }
        visited[i]=true;
        int l=cur[1];
        res=Math.max(res,l);
        String s=words[i];
        for (int j = 0; j < s.length(); j++) {
            String sub=s.substring(0,j)+s.substring(j+1);
            if(map.containsKey(sub)){
                int idx=map.get(sub);
                if(!visited[idx]){
                    q.offer(new int[]{idx,l+1});
                }
            }
        }
    }
    return res;
}

1235. Maximum Profit in Job Scheduling

注意：

  • max有两用：代表当前job之前可以append的最大profit ,也最终代表最大profit
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
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
    convert(startTime,endTime,profit);
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[0]-b[0]));
    //end,sum
    int n=startTime.length;
    int max=0;
    for (int i = 0; i < n; i++) {
        int start=startTime[i];
        int end=endTime[i];
        int p=profit[i];
        //only pop when can be appended
        //once can be appended, all following job also can append it 
        while(!pq.isEmpty() && pq.peek()[0]<=start){
            max=Math.max(max,pq.poll()[1]);
        }
        pq.offer(new int[]{end,p+max});
    }
    while(!pq.isEmpty()){
        max=Math.max(max,pq.poll()[1]);
    }
    return max;
}

private void convert(int[] startTime, int[] endTime, int[] profit){
    List<int[]> list=new ArrayList<>();
    int n=startTime.length;
    for (int i = 0; i < n; i++) {
        list.add(new int[]{startTime[i],endTime[i],profit[i]});
    }
    Collections.sort(list,(a,b)->(a[0]-b[0]));
    for (int i = 0; i < n; i++) {
        int[] arr=list.get(i);
        startTime[i]=arr[0];
        endTime[i]=arr[1];
        profit[i]=arr[2];
    }
}

1249. Minimum Remove to Make Valid Parentheses

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
public String minRemoveToMakeValid(String s) {
    int n=s.length();
    char[] chars=s.toCharArray();
    Deque<Integer> stack=new LinkedList<>();
    //idx of (
    for (int i = 0; i < n; i++) {
        char c=chars[i];
        if(c=='('){
            chars[i]='.';
            stack.push(i);
        }else if(c==')'){
            if(!stack.isEmpty()){
                chars[stack.pop()]='(';
            }else{
                chars[i]='.';
            }
        }
    }
    StringBuilder sb=new StringBuilder();
    for (int i = 0; i < n; i++) {
        if(chars[i]!='.'){
            sb.append(chars[i]);
        }
    }
    return sb.toString();
}

1099. Two Sum Less Than K

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int twoSumLessThanK(int[] nums, int k) {
    int n= nums.length;
    Arrays.sort(nums);
    int res=-1;
    for (int i = n-1; i >= 0; i--) {
        if(nums[i]>=k){
            continue;
        }
        for (int j = i-1; j >= 0; j--) {
            if(nums[i]+nums[j]<k){
                res=Math.max(res,nums[i]+nums[j]);
                break;
            }
        }
    }
    return res;
}

993. Cousins in Binary Tree

注意定义: have the same depth with different parents.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Map<Integer,Integer> map;
int[] d=new int[2];
public boolean isCousins(TreeNode root, int x, int y) {
    map=new HashMap<>();
    dfs(root,new int[]{x,y},0);
    return d[0]==d[1] && !map.get(x).equals(map.get(y));
}

void dfs(TreeNode node, int[] arr, int cur){
    if(node.val==arr[0]){
        d[0]=cur;
    }
    if(node.val==arr[1]){
        d[1]=cur;
    }
    if(node.left!=null){
        map.put(node.left.val,node.val);
        dfs(node.left,arr,cur+1);
    }
    if(node.right!=null){
        map.put(node.right.val,node.val);
        dfs(node.right,arr,cur+1);
    }
}

696. Count Binary Substrings

https://leetcode.com/problems/count-binary-substrings/discuss/108625/JavaC%2B%2BPython-Easy-and-Concise-with-Explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int countBinarySubstrings(String s) {
    int n=s.length();
    List<Integer> list=new ArrayList<>();
    int len=1;
    for (int i = 1; i < n; i++) {
        if(s.charAt(i)==s.charAt(i-1)){
            len++;
        }else{
            list.add(len);
            len=1;
        }
    }
    list.add(len);
    int res=0;
    for (int i = 0; i < list.size()-1; i++) {
        res+=Math.min(list.get(i),list.get(i+1));
    }
    return res;
}

可以进一步优化为linear scan with constant space: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int countBinarySubstrings(String s) {
    int n=s.length();
    int prev=0;
    int cur=1;
    int res=0;
    for (int i = 1; i < n; i++) {
        if(s.charAt(i)==s.charAt(i-1)){
            cur++;
        }else{
            res+=Math.min(prev,cur);
            prev=cur;
            cur=1;
        }
    }
    res+=Math.min(prev,cur);
    return res;
}

992. Subarrays with K Different Integers

brute force: LTE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int subarraysWithKDistinct(int[] nums, int k) {
    int n=nums.length;
    int res=0;
    Set<Integer> set=new HashSet<>();
    for (int i = 0; i < n; i++) {
        set.clear();
        set.add(nums[i]);
        if(set.size()==k){
            res++;
        }
        for (int j = i+1; j < n; j++) {
            set.add(nums[j]);
            if(set.size()>k){
                break;
            }
            if(set.size()==k){
                res++;
            }
        }
    }
    return res;
}
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
public int subarraysWithKDistinct(int[] A, int K) {
        Map<Integer, Integer> window1 = new HashMap<>(), window2 = new HashMap<>();
int l1 = 0, l2 = 0, result = 0;
// At each loop we count all "good" subarrays that end at A[r].
for (int r = 0; r < A.length; ++r) {
    // Add A[r] to both windows.
    window1.put(A[r], window1.getOrDefault(A[r], 0) + 1);
    window2.put(A[r], window2.getOrDefault(A[r], 0) + 1);
    // Position the two left pointers.
    while (window1.size() > K) {
        window1.put(A[l1], window1.get(A[l1]) - 1);
        if (window1.get(A[l1]) == 0) window1.remove(A[l1]);
        l1++;
    }
    while (window2.size() >= K) {
        window2.put(A[l2], window2.get(A[l2]) - 1);
        if (window2.get(A[l2]) == 0) window2.remove(A[l2]);
        l2++;
    }
    // We now count all subarrays with exactly K distinct elements that start in A[l1, l2 - 1] and that end at A[r]. 
    // These are the subarrays we count: A[l1, r], A[l1 + 1, r], A[l1 + 2, r], ..., A[l2 - 2, r], A[l2 - 1, r].
    result += l2 - l1;  
}
return result;
}

2096. Step-By-Step Directions From a Binary Tree Node to Another

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
int depthStart=0;
StringBuilder sb=new StringBuilder();
String res=null;
public String getDirections(TreeNode root, int startValue, int destValue) {
    TreeNode p=lca(root,startValue,destValue);
    depth(p,startValue,0);
    for (int i = 0; i < depthStart; i++) {
        sb.append('U');
    }
    trace(p,destValue);
    return res;
}

void depth(TreeNode node, int val, int d){
      if(node==null){
          return;
      }
      if(node.val==val){
          depthStart=d;
          return;
      }
      depth(node.left,val,d+1);
      depth(node.right,val,d+1);
}

void trace(TreeNode node, int val){
    if(node==null){
        return;
    }
    if(node.val==val){
        res=sb.toString();
        return;
    }
    sb.append("L");
    trace(node.left,val);
    sb.deleteCharAt(sb.length()-1);
    sb.append("R");
    trace(node.right,val);
    sb.deleteCharAt(sb.length()-1);
}

TreeNode lca(TreeNode node, int p, int q){
      if(node==null || node.val==p || node.val==q){
          return node;
      }
      TreeNode l=lca(node.left,p,q);
      TreeNode r=lca(node.right,p,q);
      if(l!=null && r!=null){
          return node;
      }
      return l==null ? r : l;
}

1366. Rank Teams by Votes

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
public String rankTeams(String[] votes) {
    int len=votes[0].length();
    if(len==1){
        return votes[0];
    }
    Map<Character,int[]> map=new HashMap<>();
    for (int i = 0; i < len; i++) {
        map.put(votes[0].charAt(i),new int[len]);
    }
    for (String vote : votes) {
        for (int i = 0; i < len; i++) {
            char c=vote.charAt(i);
            map.get(c)[i]++;
        }
    }
    PriorityQueue<Character> pq=new PriorityQueue<>(new Comparator<Character>() {
        @Override
        public int compare(Character c1, Character c2) {
            for (int i = 0; i < len; i++) {
               if(map.get(c1)[i]!=map.get(c2)[i]){
                   return map.get(c2)[i]-map.get(c1)[i];
               }
            }
            return c1.compareTo(c2);
        }
    });
    for (Character c : map.keySet()) {
        pq.offer(c);
    }
    StringBuilder sb=new StringBuilder();
    while(!pq.isEmpty()){
        sb.append(pq.poll());
    }
    return sb.toString();
}

670. Maximum Swap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int maximumSwap(int num) {
    String s=String.valueOf(num);
    char[] chars=s.toCharArray();
    for (int i = 0; i < chars.length-1; i++) {
        int idx=i+1;
        char max=chars[i+1];
        for (int j = i+2; j < chars.length; j++) {
            if(chars[j]>=max){
                max=chars[j];
                idx=j;
            }
        }
        if(max>chars[i]){
            char temp=chars[idx];
            chars[idx]=chars[i];
            chars[i]=temp;
            break;
        }
    }
    String res=new String(chars);
    return Integer.valueOf(res);
}

791. Custom Sort String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public String customSortString(String order, String s) {
    int[] arr=new int[26];
    for (int i = order.length()-1; i >= 0; i--) {
        char c=order.charAt(i);
        arr[c-'a']=i;
    }
    PriorityQueue<Character> pq=new PriorityQueue<>((a,b)->(arr[a-'a']-arr[b-'a']));
    for (int i = 0; i < s.length(); i++) {
        pq.offer(s.charAt(i));
    }
    StringBuilder sb=new StringBuilder();
    while(!pq.isEmpty()){
        sb.append(pq.poll());
    }
    return sb.toString();
}

其实没必要

1293. Shortest Path in a Grid with Obstacles Elimination

反思：

  • bfs with layer确保了由近及远
  • 只有在较长路径(后出现路径)穿过的障碍更少时，才需要考虑
  • 当允许再穿过的障碍变为-1时，该路径已不可能，无需考虑
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
public int shortestPath(int[][] grid, int k) {
    int row=grid.length;
    int col=grid[0].length;
    int[][] dirs=new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    int[][] lives=new int[row][col];
    for (int[] arr : lives) {
        Arrays.fill(arr,-1);
    }
    Deque<int[]> q=new LinkedList<>();
    q.offer(new int[]{0,0,k});
    lives[0][0]=k;
    int d=0;
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            int[] cur=q.poll();
            int i=cur[0];
            int j=cur[1];
            int l=cur[2];
            if(i==row-1 && j==col-1){
                return d;
            }
            if(grid[i][j]==1){
                l--;
            }
            for (int[] dir : dirs) {
                int x=i+dir[0];
                int y=j+dir[1];
                //only slower path with more lives should be considered
                if(x>=0 && x<row && y>=0 && y<col && lives[x][y]<l){
                    lives[x][y]=l;
                    q.offer(new int[]{x,y,l});
                }
            }
        }
        d++;
    }
    return -1;
}

1864. Minimum Number of Swaps to Make the Binary String Alternating

倒推法，考察所有可能最终结果与初值的差别

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
public int minSwaps(String s) {
    int n=s.length();
    if(n==1){
        return 0;
    }
    int wrong0=0;
    int wrong1=0;
    int res=Integer.MAX_VALUE;
    //even 0, odd 1
    for (int i = 0; i < n; i++) {
        char c=s.charAt(i);
        if(c=='1' && (i&1)==0){
            wrong1++;
        }
        if(c=='0' && (i&1)==1){
            wrong0++;
        }
    }
    if(wrong0==wrong1){
        res=Math.min(res,wrong0);
    }
    //even 1, odd 0
    wrong0=0;
    wrong1=0;
    for (int i = 0; i < n; i++) {
        char c=s.charAt(i);
        if(c=='1' && (i&1)==1){
            wrong1++;
        }
        if(c=='0' && (i&1)==0){
            wrong0++;
        }
    }
    if(wrong0==wrong1){
        res=Math.min(res,wrong0);
    }
    return res==Integer.MAX_VALUE ? -1 : res;
}

2482. Difference Between Ones and Zeros in Row and Column

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[][] onesMinusZeros(int[][] grid) {
    int row=grid.length;
    int col=grid[0].length;
    int[] onesRow=new int[row];
    int[] onesCol=new int[col];
    //onesRow[i] + onesCol[j] - (col-onesRow[i]) - (row-onesCol[j])
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(grid[i][j]==1){
                onesRow[i]++;
                onesCol[j]++;
            }
        }
    }
    int[][] res=new int[row][col];
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            res[i][j]=2*onesRow[i]-col+2*onesCol[j]-row;
        }
    }
    return res;
}

1335. Minimum Difficulty of a Job Schedule

反思：

  • 初始化为-1，代表第一次处理该子问题
  • 在每个子问题中，初始化res为IntMax，保证小于任何可行结果
  • 在for循环中提前剪枝
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
int[][] dp;
public int minDifficulty(int[] nums, int d) {
    if(nums.length<d){
        return -1;
    }
    dp=new int[nums.length][d+1];
    for (int[] arr : dp) {
        Arrays.fill(arr,-1);
    }
    dfs(nums,0,d);
    return dp[0][d];
}

int dfs(int[] nums, int i, int d){
    if(dp[i][d]!=-1){
        return dp[i][d];
    }
    if(d==1){
        int max=0;
        for (int j = i; j < nums.length; j++) {
            max=Math.max(max,nums[j]);
        }
        dp[i][d]=max;
        return max;
    }
    int max=0;
    int res=Integer.MAX_VALUE;
    //[n-d+1,n-1]
    for (int j = i; j < nums.length-d+1; j++) {
        max=Math.max(max,nums[j]);
        res=Math.min(res,max+dfs(nums,j+1,d-1));
    }
    dp[i][d]=res;
    return res;
}

2256. Minimum Average Difference

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int minimumAverageDifference(int[] nums) {
    int n= nums.length;
    long[] sum=new long[n+1];//[0,i-1]
    for (int i = 0; i <n; i++) {
        sum[i+1]=sum[i]+nums[i];
    }
    long postSum=0;
    long min=Long.MAX_VALUE;
    int res=0;
    for (int i = n-1; i >= 0; i--) {
        long avg1=sum[i+1]/(i+1);
        long avg2=n-i-1==0 ? 0 : postSum/(n-i-1);
        long diff=Math.abs(avg1-avg2);
        if(diff<=min){
            res=i;
            min=diff;
        }
        postSum+=nums[i];
    }
    return res;
}

692. Top K Frequent Words

1
2
3
4
5
6
7
8
9
10
public List<String> topKFrequent(String[] words, int k) {
    Map<String,Integer> map=new HashMap<>();
    for (String word : words) {
        map.put(word,map.getOrDefault(word,0)+1);
    }
    List<String> list=new ArrayList<>(map.keySet());
    Collections.sort(list,
            (a,b)->(map.get(a)!=map.get(b) ? map.get(b)-map.get(a) : a.compareTo(b)));
    return list.subList(0,k);
}

1092. Shortest Common Supersequence

注意：

  • shortest common supersequence 转化为 longest common subsequence
  • 求出lcs后进行合并
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
public String shortestCommonSupersequence(String str1, String str2) {
    String s=lcs(str1,str2);
    int n1=str1.length();
    int n2=str2.length();
    int p1=0;
    int p2=0;
    StringBuilder sb=new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        while(p1<n1 && str1.charAt(p1)!=s.charAt(i)){
            sb.append(str1.charAt(p1));
            p1++;
        }
        while(p2<n2 && str2.charAt(p2)!=s.charAt(i)){
            sb.append(str2.charAt(p2));
            p2++;
        }
        sb.append(s.charAt(i));
        p1++;
        p2++;
    }
    while(p1<n1){
        sb.append(str1.charAt(p1));
        p1++;
    }
    while(p2<n2){
        sb.append(str2.charAt(p2));
        p2++;
    }
    return sb.toString();
}

private String lcs(String str1, String str2) {
    //longest common subsequence
    int n1=str1.length();
    int n2=str2.length();
    String[][] dp=new String[n1+1][n2+1];
    for (String[] arr : dp) {
        Arrays.fill(arr,"");
    }
    for (int i = n1-1; i >= 0; i--) {
        for (int j = n2-1; j >= 0; j--) {
            if(str1.charAt(i)==str2.charAt(j)){
                dp[i][j]=str1.charAt(i)+dp[i+1][j+1];
            }else{
                dp[i][j]= dp[i+1][j].length()>=dp[i][j+1].length()
                        ? dp[i+1][j] : dp[i][j+1];
            }
        }
    }
    return dp[0][0];
}

929. Unique Email Addresses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int numUniqueEmails(String[] emails) {
    Set<String> set=new HashSet<>();
    for (String email : emails) {
        String[] split = email.split("@");
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < split[0].length(); i++) {
            char c=split[0].charAt(i);
            if(c=='+'){
                break;
            }
            if(c=='.'){
                continue;
            }
            sb.append(c);
        }
        set.add(sb.append("@"+split[1]).toString());
    }
    return set.size();
}

645. Set Mismatch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] findErrorNums(int[] nums) {
    int n= nums.length;
    Arrays.sort(nums);
    int[] res=new int[2];
    int sum=nums[0];
    for (int i = 1; i < n; i++) {
        if(res[0]==0 && nums[i]==nums[i-1]){
            res[0]=nums[i];
        }
        sum+=nums[i];
    }
    //(1+n)*n/2
    int diff=sum-(1+n)*n/2;
    //old-new = dif => new = old - dif
    res[1]=res[0]-diff;
    return res;
}

2149. Rearrange Array Elements by Sign

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] rearrangeArray(int[] nums) {
    int n=nums.length;
    int[] res=new int[n];
    int pos=0;
    int neg=1;
    for (int i = 0; i < n; i++) {
        if(nums[i]>0){
            res[pos]=nums[i];
            pos+=2;
        }else{
            res[neg]=nums[i];
            neg+=2;
        }
    }
    return res;
}

1047. Remove All Adjacent Duplicates In String

1
2
3
4
5
6
7
8
9
10
11
12
public String removeDuplicates(String s) {
    StringBuilder sb=new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c=s.charAt(i);
        if(sb.length()>0 && sb.charAt(sb.length()-1)==c){
            sb.deleteCharAt(sb.length()-1);
        }else{
            sb.append(c);
        }
    }
    return sb.toString();
}

1209. Remove All Adjacent Duplicates in String II

brute force:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public String removeDuplicates(String s, int k) {
    StringBuilder sb=new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c=s.charAt(i);
        sb.append(c);
        //[len-k,len-1]
        if(sb.length()-k>=0){
            int len=sb.length();
            String sub= sb.substring(len-k);
            int j = 0;
            for (; j < sub.length(); j++) {
                if(sub.charAt(j)!=c){
                    break;
                }
            }
            if(j==sub.length()){
                sb.delete(len-k,len);
            }
        }
    }
    return sb.toString();
}

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/solution/

好题！

using stack straighforward:

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
public String removeDuplicates(String s, int k) {
    int n=s.length();
    StringBuilder sb=new StringBuilder();
    Deque<Integer> stack=new LinkedList<>();
    stack.push(1);
    sb.append(s.charAt(0));
    for (int i = 1; i < n; i++) {
        char c=s.charAt(i);
        if(stack.isEmpty()){
            stack.push(1);
            sb.append(c);
            continue;
        }
        int top= stack.pop();
        if(c==sb.charAt(sb.length()-1)){
            top++;
            stack.push(top);
            sb.append(c);
            if(top==k){
                sb.delete(sb.length()-k,sb.length());
                stack.pop();
            }
        }else{
            sb.append(c);
            stack.push(top);
            stack.push(1);
        }
    }
    return sb.toString();
}

only consider last:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public String removeDuplicates(String s, int k) {
    int n=s.length();
    int[] count=new int[n];
    StringBuilder sb=new StringBuilder();
    for (int i = 0; i < n; i++) {
        sb.append(s.charAt(i));
        int last=sb.length()-1;
        count[last]=1+(last>0 && sb.charAt(last)==sb.charAt(last-1) ? count[last-1] : 0);
        if(count[last]>=k){
            sb.delete(last-k+1,last+1);
        }
    }
    return sb.toString();
}

92. Reverse Linked List II

unclean 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
public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy=new ListNode();
    dummy.next=head;
    ListNode pre1=dummy;
    ListNode p1=head;//start of reverse
    int idx=1;
    while(idx<left){
        idx++;
        pre1=p1;
        p1=p1.next;
    }
    ListNode p2=p1;//end of reverse
    while(idx<right){
        p2=p2.next;
        idx++;
    }
    ListNode h3=p2.next;
    p2.next=null;
    ListNode h2=reverse(p1);
    pre1.next=h2;
    p1.next=h3;
    return dummy.next;
}

private ListNode reverse(ListNode node){
      if(node==null || node.next==null){
          return node;
      }
      ListNode next=node.next;
      ListNode h=reverse(next);
      next.next=node;
      node.next=null;
      return h;
}

https://leetcode.com/problems/reverse-linked-list-ii/discuss/2311084/JavaC%2B%2B-Tried-to-Explain-every-step

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy=new ListNode();
    dummy.next=head;
    ListNode pre=dummy;
    int idx=1;
    while(idx<left){
        idx++;
        pre=pre.next;
    }
    ListNode cur=pre.next;
    ListNode next=null;
    for(int i=0; i<right-left; i++){
        next=cur.next;
        cur.next=next.next;
        next.next=pre.next;
        pre.next=next;
    }
    return dummy.next;
}

828. Count Unique Characters of All Substrings of a Given String

直接法超时

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
int n;
int[] dp;
public int uniqueLetterString(String s) {
    n=s.length();
    dp=new int[n];
    return dp(s,0);
}

int dp(String s,int i){
    if(i==n){
        return 0;
    }
    if(i==n-1){
        return 1;
    }
    if(dp[i]!=0){
        return dp[i];
    }
    int res=dp(s,i+1);
    Map<Character,Integer> map=new HashMap<>();
    int cur=0;
    for (int j = i; j < n; j++) {
        char c=s.charAt(j);
        map.put(c,map.getOrDefault(c,0)+1);
        if(map.get(c)==1){
            cur++;
        }else if(map.get(c)==2){
            cur--;
        }
        res+=cur;
    }
    return dp[i]=res;
}

思路：

  • 当char数量有限时，不妨以char出发，考察每个char能unique存在的substring个数
  • 瞻前顾后，计算该char unique存在的区间

https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/discuss/128952/JavaC%2B%2BPython-One-pass-O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int uniqueLetterString(String s) {
    int n=s.length();
    int[][] arr=new int[26][2];//last 2nd, last 1st
    int res=0;
    for (int i = 0; i < n; i++) {
        char c=s.charAt(i);
        int idx=c-'A';
        if(arr[idx][1]==0 && arr[idx][0]==0){
            arr[idx][0]=-1;
        }else{
            res+=(arr[idx][1]-arr[idx][0])*(i-arr[idx][1]);
            arr[idx][0]=arr[idx][1];
        }
        arr[idx][1]=i;
    }
    for (int idx = 0; idx < 26; idx++) {
        res+=(arr[idx][1]-arr[idx][0])*(n-arr[idx][1]);
    }
    return res;
}

2262. Total Appeal of A String

https://leetcode.com/problems/total-appeal-of-a-string/discuss/1996390/JavaC%2B%2BPython-Easy-and-Concise-with-Explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
public long appealSum(String s) {
    int n=s.length();
    int[] arr=new int[26];
    Arrays.fill(arr,-1);
    long res=0;
    for (int i = 0; i < n; i++) {
        char c=s.charAt(i);
        int idx=c-'a';
        res+=(long)(i-arr[idx])*(n-i);
        arr[idx]=i;
    }
    return res;
}

2386. Find the K-Sum of an Array

https://leetcode.com/problems/find-the-k-sum-of-an-array/discuss/2465961/Decreasing-Subsequence-Sums

思路：

  1. to find the k-th largest, we just need to find the largest possible sum - k-th smallest
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public long kSum(int[] nums, int k) {
    int n=nums.length;
    long sum=0;
    for (int i = 0; i < n; i++) {
        sum+=nums[i]>0 ? nums[i] : 0;
        nums[i]=Math.abs(nums[i]);
    }
    Arrays.sort(nums);
    PriorityQueue<long[]> pq=new PriorityQueue<>((a,b)->((int)(b[0]-a[0])));
    pq.offer(new long[]{sum-nums[0],0});
    while(--k>0){
       long[] cur=pq.poll();
       sum=cur[0];
       int idx=(int)cur[1];
       if(idx+1<n){
           //for every num, choose or unchoose(but at least choose 1 item, otherwise will be same as the smallest, i.e. choose none)
           pq.offer(new long[]{sum-nums[idx+1],idx+1});
           pq.offer(new long[]{sum-nums[idx+1]+nums[idx],idx+1});
       }
    }
    return sum;
}

1567. Maximum Length of Subarray With Positive Product

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int getMaxLen(int[] nums) {
    int n=nums.length;
    Map<Integer,Integer> map=new HashMap<>();
    map.put(1,-1);//(start,end]
    int sum=1;
    int res=0;
    for (int i = 0; i < n; i++) {
        if(nums[i]==0){
            map.clear();
            map.put(1,i);
            sum=1;
            continue;
        }
        sum= nums[i]>0 ? sum : -sum;
        map.putIfAbsent(sum,i);
        res=Math.max(res,i-map.get(sum));
    }
    return res;
}

妙！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int getMaxLen(int[] nums) {
            int positive = 0, negative = 0;    // length of positive and negative results
    int ans = 0;
    for(int x : nums) {
        if(x == 0)  {
            positive = 0;
            negative = 0;
        }
        else if(x > 0) {
            positive++;
            negative = negative == 0 ? 0  : negative+1;
        }
        else {
            int temp = positive;
            positive = negative == 0 ? 0  : negative+1;
            negative = temp+1;
        }
        ans = Math.max(ans, positive);
    }
    return ans;
}

2163. Minimum Difference in Sums After Removal of Elements

https://leetcode.com/problems/minimum-difference-in-sums-after-removal-of-elements/discuss/1747029/Python-Explanation-with-pictures-Priority-Queue.

10^5 -> nlog(n) -> binary_search / heap

思路：

  • smallest n from [0,A], biggest n from [A+1,3n-1]
  • A: [n-1,2n-1], total n+1 possibility
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
public long minimumDifference(int[] nums) {
    //minimize first part, maximize second part
    int n=nums.length/3;
    //[n-1,2n]
    PriorityQueue<Integer> pq1=new PriorityQueue<>((a,b)->(b-a));
    long sum=0;
    long[] mins=new long[n+1];
    for (int i=0; i < n; i++) {
        sum+=nums[i];
        pq1.offer(nums[i]);
    }
    mins[0]=sum;
    for (int idx = 1; idx <=n; idx++) {
        //0: n-1
        int i=n+idx-1;
        if(nums[i]<pq1.peek()){
            sum-=pq1.poll();
            sum+=nums[i];
            pq1.offer(nums[i]);
        }
        mins[idx]=sum;
    }
    long[] maxs=new long[n+1];
    PriorityQueue<Integer> pq2=new PriorityQueue<>();
    sum=0;
    for (int i = 3*n-1; i >= 2*n; i--) {
        sum+=nums[i];
        pq2.offer(nums[i]);
    }
    maxs[n]=sum;
    for (int idx = n-1; idx >= 0; idx--) {
        //n-1: 2*n-1
        //0: n
        int i=idx+n;
        if(nums[i]>pq2.peek()){
            sum-= pq2.poll();
            sum+=nums[i];
            pq2.offer(nums[i]);
        }
        maxs[idx]=sum;
    }
    long res=Long.MAX_VALUE;
    for (int idx = 0; idx < n + 1; idx++) {
        res=Math.min(res,mins[idx]-maxs[idx]);
    }
    return res;
}

823. Binary Trees With Factors

bottom-up dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int numFactoredBinaryTrees(int[] arr) {
    Map<Integer,Long> dp=new HashMap<>();
    long res=0;
    long mod=(long)1e9+7;
    Arrays.sort(arr);
    for (int i = 0; i < arr.length; i++) {
        long cur=1;
        for (int j = 0; j < i; j++) {
            //arr[j], arr[i]/arr[j]
            if(arr[i]%arr[j]==0){
                cur+=dp.get(arr[j])*dp.getOrDefault(arr[i]/arr[j],0L)%mod;
            }
        }
        dp.put(arr[i],cur);
        res=(res+cur)%mod;
    }
    return (int)res;
}

1642. Furthest Building You Can Reach

https://leetcode.com/problems/furthest-building-you-can-reach/discuss/918515/JavaC%2B%2BPython-Priority-Queue

思路：

  • it is always optimal to use bricks if possible
  • first use up ladders
  • then try to use the smallest amount of bricks to save up a ladder
  • stop when a gap is unbreachable
    • i.e, the smallest amount required exceeds what we have
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int furthestBuilding(int[] heights, int bricks, int ladders) {
    PriorityQueue<Integer> pq=new PriorityQueue<>();
    for (int i=0; i < heights.length-1; i++) {
        int d=heights[i+1]-heights[i];
        if(d>0){
            pq.offer(d);
        }
        if(pq.size()>ladders){
            bricks-=pq.poll();
        }
        if(bricks<0){
            return i;
        }
    }
    return heights.length-1;
}