Commit9114e28

committed

[Function add]

1. Add leetcode solutions with amazon tag.

1 parent9a69639 commit9114e28Copy full SHA for 9114e28

File tree

+87

-0

lines changed

+87

-0

lines changed

Lines changed: 25 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -139,4 +139,29 @@ class Solution {`
`139`	`139`	`}`
`140`	`140`	`}`
`141`	`141`	`}`
	`142`	+```
	`143`	`+`
	`144`	`+###Amazon session`
	`145`	`+* Method 1: binary search`
	`146`	+```Java
	`147`	`+class Solution {`
	`148`	`+public int search(int[] nums, int target) {`
	`149`	`+if(nums == null \|\| nums.length == 0) return -1;`
	`150`	`+return binarySearch(nums, 0, nums.length - 1, target);`
	`151`	`+}`
	`152`	`+private int binarySearch(int[] nums, int low, int high, int target){`
	`153`	`+if(low > high) return -1;`
	`154`	`+int mid = low + (high - low) / 2;`
	`155`	`+if(nums[mid] == target) return mid;`
	`156`	`+else if(nums[mid] >= nums[low]){ // left side is in order`
	`157`	`+if(target >= nums[low] && target < nums[mid]){`
	`158`	`+return binarySearch(nums, low, mid - 1, target);`
	`159`	`+}else return binarySearch(nums, mid + 1, high, target);`
	`160`	`+}else{ // right side is in order`
	`161`	`+if(target > nums[mid] && target <= nums[high])`
	`162`	`+return binarySearch(nums, mid + 1, high, target);`
	`163`	`+return binarySearch(nums, low, mid - 1, target);`
	`164`	`+}`
	`165`	`+}`
	`166`	`+}`
`142`	`167`	```

Lines changed: 31 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -48,4 +48,35 @@ Explanation: T is "aa" which its length is 2.`
`48`	`48`	`return max;`
`49`	`49`	`}`
`50`	`50`	`}`
	`51`	+```
	`52`	`+`
	`53`	`+###AmazonSession`
	`54`	`+*Method1: sliding window`
	`55`	+```Java
	`56`	`+classSolution {`
	`57`	`+publicintlengthOfLongestSubstringKDistinct(Strings,intk) {`
	`58`	`+int slow=0, fast=0;`
	`59`	`+int result=0;`
	`60`	`+char[] arr= s.toCharArray();`
	`61`	`+Map<Character,Integer> map=newHashMap<>();`
	`62`	`+while(fast< arr.length){`
	`63`	`+map.put(arr[fast], map.getOrDefault(arr[fast],0)+1);`
	`64`	`+if(map.size()<= k){`
	`65`	`+result=Math.max(result, fast- slow+1);`
	`66`	`+}elseif(map.size()> k){`
	`67`	`+while(map.size()> k){`
	`68`	`+char c= arr[slow];`
	`69`	`+int freq= map.get(c);`
	`70`	`+if(freq==1){`
	`71`	`+map.remove(c);`
	`72`	`+}else map.put(c, freq-1);`
	`73`	`+slow++;`
	`74`	`+}`
	`75`	`+result=Math.max(result, fast- slow+1);`
	`76`	`+}`
	`77`	`+fast++;`
	`78`	`+}`
	`79`	`+return result;`
	`80`	`+}`
	`81`	`+}`
`51`	`82`	```

Lines changed: 31 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -94,3 +94,34 @@ class Solution {`
`94`	`94`	`}`
`95`	`95`	`}`
`96`	`96`	```
	`97`	`+`
	`98`	`+###Amazon session`
	`99`	`+* Method 1: Sort`
	`100`	+```Java
	`101`	`+class Solution {`
	`102`	`+public int[][] merge(int[][] intervals) {`
	`103`	`+if(intervals == null \|\| intervals.length <= 1) return intervals;`
	`104`	`+Arrays.sort(intervals, (a, b)->{`
	`105`	`+return a[0] == b[0] ? a[1] - b[1]: a[0] - b[0];`
	`106`	`+});`
	`107`	`+int len = intervals.length;`
	`108`	`+List<int[]> result = new ArrayList<>();`
	`109`	`+int start = intervals[0][0];`
	`110`	`+int end = intervals[0][1];`
	`111`	`+for(int i = 1; i < len; i++){`
	`112`	`+if(intervals[i][0] <= end){`
	`113`	`+end = Math.max(intervals[i][1],end);`
	`114`	`+}else{`
	`115`	`+result.add(new int[]{start, end});`
	`116`	`+start = intervals[i][0];`
	`117`	`+end = Math.max(intervals[i][1],end);`
	`118`	`+}`
	`119`	`+}`
	`120`	`+result.add(new int[]{start, end});`
	`121`	`+return result.toArray(new int[result.size()][2]);`
	`122`	`+}`
	`123`	`+}`
	`124`	+```
	`125`	`+`
	`126`	`+###Reference`
	`127`	`+1.[Algorithm \| Interval Schedule](https://seanforfun.github.io/algorithm/2019/05/03/IntervalScheduleWithGreedy.html)`

Comments

(0)