M-x shell and M-x eshell are two major mode we use daily.
however, in the shell mode, it is not easy to switch to dired mode.
but in M-x eshell mode, command “dired .” will open dired mode for current path
Here is leetcode’s new hard level question:
https://leetcode.com/problems/count-of-smaller-numbers-after-self/
The basic idea is using two for to loop though to counter smaller number on its left.
Solution1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | public List<Integer> countSmaller(int[] nums) { List<Integer> result = new ArrayList<>(); result.add(0); for(int i = nums.length - 2;i>=0;i--) { int target = nums[i]; int count = 0; for(int j=i+1;j<=nums.length-1;j++) { if(nums[j]<=target) count++; } result.add(count); } Collections.reverse(result); return result; } |
Solution 2:
Solution 1 is using two loops to go though to compare.
This solution is faster the second loop using tree.
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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | package leetcodetest; import java.util.ArrayList; import java.util.Collections; import java.util.List; /** * * @author wudi */ public class CountSmaller2 { public class xTreenode { public xTreenode left = null; public xTreenode right = null; int count = 1; int val; public xTreenode(int x) { val = x; } } public int add(xTreenode root,int x) { int count = 0; while(true) { if(x <= root.val) { root.count++; if(root.left == null){ root.left = new xTreenode(x); break; } root = root.left; } else { count += root.count; if(root.right == null) { root.right = new xTreenode(x); break; } root = root.right; } } return count; } public List<Integer> countSmaller(int[] nums) { List<Integer> result = new ArrayList<>(); if(nums == null || nums.length == 0) return result; xTreenode root = new xTreenode(nums[nums.length - 1]); result.add(0); for(int i=nums.length - 2;i>=0;i--) { int count = add(root,nums[i]); result.add(count); } Collections.reverse(result); return result; } public static void main(String[] args) { int[] nums = {2,0,1}; CountSmaller2 c = new CountSmaller2(); System.out.println(c.countSmaller(nums)); } } |