[4/25, 2:43 PM] Abdelrauf: int

## Pseudo code conventions ****** | Keywords | Description| | --- | ----- | | --- | Comment | | | | | | tabs | to show blocks | | | | | | <- | assigment | | | | | | +,-,*, mod, /, and, xor, or | math and bitwise operators | | | | | | ( ) | grouping parenthesis to prevent ambiguity | | | | | | power(base,x) | math power | | | | | | ** | math power that follows python associativity right to left) | | | | | | exp(value) | e^(value) | | | | | | types: int, float, string, bool, Array, String, Map, Stack, Queue,.. | | | | | | | true, false | bool type values | | | | | | var_name <- value | type inferenced from value. For example: `a <-1` means it will assume a: int | | | | | | nums1: Array\[type=int, size=n, sorted\] | nums1 is sorted array of n int elements | | | | | | nums1: Array\[type=int, size=n\] | nums1 is array of n int elements initialized with 0 | | | | | | str:String | str is String type. | | | | | | #{var_name} | get the length of Array, String, Stack, Queue | | | | | | array_name\[i\] | access i-th element of array | | | | | | array_name\[m..k\] | the slice of array from m to k. note: k-th excluded | | | | | | &&, | | , !=, == or =, >= , <=, <, > | comparison and condition | | chain | | if, while, for | loop and branching | | | | | | break, break label | |continue, continue label | continue skip in the loop| |if(condition, True case, False case expression) | short if , or ternary operator for i in 4..7 | loop i from 4 till 7, 7-th excluded \[4,7\)| | for x in array | x gets value by iterating array | | var: type | variable or argument declaration| |max, min, abs, random_number | builtin functions with the same meaning| | max a, b | maximum of a and b | | min a, b | minimum of a and b | |abs x| absolute value of x| |random_number| get random number| | function_name(x: type, ...) -> return_type | function with function_name that accepts x and returns return_type | function_name var1, ... | calling function_name with var1 argument | return ... | return result from function| |type UserTypeName| custom type| |Constructor()| custom type constructor |Method1(x: type,..) | method names start with capital leter| |var.Method1 x|calling Method1 with argument x| |map_name.Contains x| check x key if exists in map `map.Contains(x:any)->bool`| |stack_name.Push x| pushes x into Stack stack_name | |string_name.Append x| append into String type| |x <- stack_name.Pop | pop from Stack stack_name and store into x| |map1:Map[keyType=int, ValueType=int] | declaration of map| |map1 <- {key1 -> value1, key2 ->value2, ...} | Map initialization | ## Pseudo codes ### Arrays/String #### 1) [Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array) ``` merge(nums1: Array[type=int, size=m+n, sorted], m: int, nums2: Array[type=int, size=n, sorted], n: int) -> None place <- m+n-1 i <- m-1 j <- n-1 while i>=0 and j>=0 if nums2[j]>nums1[i] nums1[place] <- nums2[j] j <- j-1 else nums1[place] <- nums1[i] i <- i-1 place <- place - 1 while j>=0 nums1[place] <- nums2[j] j <- j-1 place <- place - 1 ``` #### 2) [Remove element](https://leetcode.com/problems/remove-element) - a) ``` removeElement(self, nums: Array[type=int, size=n], val: int) -> int for i in 0..n if vec[i] != val vec[p] <- vec[i] p <- p + 1 return p ``` - b) ``` removeElement(self, nums: Array[type=int, size=n], val: int) -> int place <- n - 1 for i in n-1..-1 if nums[i] == val nums[i] <- nums[place] place <- place - 1 return place+1 ``` #### 3) [Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array) ``` removeDuplicates( nums: Array[int, size = n, sorted]) -> int p <- 1 for i in 1..n if nums[i] != nums[p-1] nums[p] <- nums[i] p <- p+1 return p ``` #### 4) [Remove Duplicates from Sorted Array 2](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii) ``` removeDuplicates( nums: Array[int, size = n, sorted]) -> int p <- 2 for i in 2..n if nums[i] != nums[p-2] nums[p] <- nums[i] p <- p+1 return p ``` #### 5) [Majority element](https://leetcode.com/problems/majority-element/) ``` majorityElement(nums: Array[int, size=n]) -> int major <- nums[0] count <- 1 for i in 0..n count <- count + if(major=nums[i], 1, -1) if count<0 major <- nums[i] count <- 1 return major ``` #### 6) [Rotate Array](https://leetcode.com/problems/rotate-array) ``` reverse( nums: Array[int, size=n]) -> None i <- 0 j <- n-1 --- #{nums} - 1 while i<j swap nums[i], nums[j] i <- i + 1 j <- j - 1 rotate( nums: Array[int, size=n], k: int) -> None end <- #{nums} newK <- k mod #{nums} reverse nums reverse nums[0..newK] reverse nums[newK..end] ``` #### 7) [Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/) ``` maxProfit(prices: Array[int, size=n]) -> int diff <- 0 buy <- max int --- maximumum value for i in 0..n diff <- max diff, (prices[i] - buy) buy <- min buy, prices[i] return diff; ``` #### 8) [Best Time to Buy and Sell Stock 2](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii) - a) ``` maxProfit(prices: Arrayist[int, size=n]) -> int total<- 0 for i in 1..n if prices[i] > prices[i - 1] diff <- prices[i] - prices[i - 1] total <- total + diff return total ``` - b) ``` maxProfit(prices: Arrayist[int, size=n]) -> int diff <- 0 last_min <- prices[0] total <- 0 for i in 1..n if prices[i] < prices[i-1] diff <- prices[i-1] - last_min total <- total + diff last_min <- prices[i] --- renew minimum diff <- prices[n-1] - last_min total <- total + diff return total ``` #### 9) [Jump Game](https://leetcode.com/problems/jump-game) ``` canJump(nums: Array[int, size=n]) -> bool i <- 0 max_jump_steps <- 0 while true end_of <- (n - 1 - i) max_jump_steps <- max nums[i], (max_jump_steps - 1) if max_jump_steps >= end_of return true if max_jump_steps == 0 return false i <- i + 1 return false ``` #### 10) [Jump Game 2](https://leetcode.com/problems/jump-game-ii) - a) ``` jump(self, nums: Array[int, size=n]) -> int max_jump_steps <- 0 jump_count <- 0 remain_steps <- 1 for i in 0..n-1 max_jump_steps <- max nums[i], (max_jump_steps - 1) remain_steps <- remain_steps - 1 if remain_steps <= 0 remain_steps <- max_jump_steps jump_count <- jump_count + 1 return jump_count ``` - b) ``` jump(self, nums: Array[int, size=n]) -> int max_jump_index <- 0 jump_count <- 0 current <- 0 for i in 0..n max_jump_index <- max (i + nums[i]), max_jump_index if max_jump_index >= n - 1 return jump_count + 1 if i == current current <- max_jump_index jump_count <- jump_count + 1 return -1 ``` #### 11) [H-Index](https://leetcode.com/problems/h-index) ``` --- ``` #### 12) [Insert-Delete-GetRandom O(1)](https://leetcode.com/problems/insert-delete-getrandom-o1) ``` type RandomizedSet stack_arr: Stack[int] map_index: Map[int -> int] Constructor() --- do nothing or reserve/increase capacity Insert(val: int) -> bool if map_index.Contains val = False return false stack_arr.Push val map_index[val] <- #{stack_arr}-1 return true Remove(val: int) -> bool if map_index.Contains val = False return false last_el <- stack_arr[#{stack_arr}-1] if last_el != val index <- map_index[val] map_index[last_el] <- index stack_arr[index] <- last_el --- erase the last element from stack_arr and map map_index.Remove val; stack_arr.Pop return true GetRandom() -> int random_index <- random_number mod #{values} return values[random_index]; ``` #### 13) [Product Except self Without division operator](https://leetcode.com/problems/product-of-array-except-self) ``` productExceptSelf(nums: Array[int, size=n]) -> Array[int, size=n] result: Array[int, size=n] x <- 1 y <- 1 for i in 0..n result[i] <- x x <- x * nums[i] for i in n-1..-1 result[i] <- y * result[i] y <- y * nums[i] return result ``` #### 14) [Gas Station](https://leetcode.com/problems/gas-station) - a) ``` canCompleteCircuit(gas: Array[int, size=n], cost: Array[int, size=n]) -> int total_cost <- 0 total_gas <- 0 last_index <- 0 tank <- 0 for i in 0..n total_cost <- total_cost + cost[i] total_gas <- total_gas + gas[i] tank <- tank + (gas[i] - cost[i]) if tank < 0 last_index <- i + 1 tank <- 0 if total_gas < total_cost return -1 return last_index ``` - b) ``` canCompleteCircuit(gas: Array[int, size=n], cost: Array[int, size=n]) -> int tank <- 0 j <- 0 first <- false first_attempt_index <- (-1) last_index <- (-1) for i in 0..2*n j <- i mod n diff <- gas[j] - cost[j] tank <- tank + diff if last_index==-1 && diff>=0 last_index <- j tank <- diff if i>=n && first_attempt_index<=j break if !first first <- true first_attempt_index <- j if tank<0 last_index <- (-1) return last_index ``` #### 15) [Candy](https://leetcode.com/problems/candy) - a) ``` candy(ratings: Array[int, size=n]) -> int up_count <- 0 down_count <- 0 peak_count <- 0 total <- 1 for i in 1..n-1 if ratings[i - 1] < ratings[i] down_count <- 0 up_count <- up_count + 1 peak_count <- up_count + 1 total <- total + peak_count else if ratings[i - 1] == ratings[i] down_count <- 0 up_count <- 0 peak_count <- 0 total <- total + 1 else down_count <- down_count + 1 up_count <- 0 total <- total + down_count + if(peak_count <= down_count, 1, 0) return total ``` - b) ``` candy(ratings: Array[int, size=n]) -> int candies: Array[int, size=n] --- assumes candies' all elements are 0 for i in 1..n if ratings[i] > ratings[i - 1] candies[i] <- candies[i-1] + 1 total <- ratings[n-1] for i in n-2..-1 if ratings[i] > ratings[i + 1] candies[i] <- max candies[i], (candies[i+1] + 1) total <- total + candies[i] return total + n ``` #### 16) [Trapping rain water](https://leetcode.com/problems/trapping-rain-water) - a) ``` trap( height: Array[int, size=n]) -> int if n < 1 return 0 --- forward collect water trapped --- between max smaller and max larger last_max <- height[0] in_between_area <- 0 trapped_rain <- 0 for i in 1..n if height[i] >= last_max trapped_rain <- trapped_rain + in_beetween_area last_max <- height[i] in_beetween_area <- 0 else in_beetween_area <- in_beetween_area + (last_max - height[i]) --- now collect reverse way --- but without considering equal comparision unlike the first one last_max <- height[n - 1] in_between_area <- 0 for i in n-2..-1 if height[i] > last_max trapped_rain <- trapped_rain + in_beetween_area last_max <- height[i] in_beetween_area <- 0 else in_beetween_area <- in_beetween_area + (last_max - height[i]) return trapped_rain ``` - b) ``` trap( height: Array[int, size=n]) -> int if n < 1 return 0 first_max <- height[0] last_max <- height[n-1] first_between_area <- 0 trapped_rain <- 0 last_beetween_area <- 0 for i in 1..n if height[i] >= first_max trapped_rain <- trapped_rain + first_between_area first_max <- height[i] first_between_area <- 0 else first_between_area <- first_between_area + (first_max - height[i]) if height[n-1-i] > last_max trapped_rain <- trapped_rain + last_beetween_area last_max <- height[n-1-i] last_beetween_area <- 0 else last_beetween_area <- last_beetween_area + (last_max - height[n-1-i]) return trapped_rain ``` - c) ``` trap( height: Array[int, size=n]) -> int left <- 0 right <- n - 1 left_max <- height[left] right_max <- height[right] water <- 0 while left < right if left_max < right_max left <- left + 1 left_max <- max left_max, height[left] water <- water + left_max - height[left] else right <- right - 1 right_max <- max right_max, height[right] water <- water + right_max - height[right] return water ``` #### 17) [Roman-to-Integer](https://leetcode.com/problems/roman-to-integer) ``` mapper: Map[keyType=char, valueType=int] mapper <- { 'I' -> 1, 'V' -> 5, 'X' -> 10, 'L' -> 50, 'C' -> 100, 'D' -> 500, 'M' -> 1000 } romanToInt( s: String ) -> int number <- 0 prev <- 0 for i in 0..#{s} x <- mapper[s[i]] number <- number + x --- adjust before placement if prev==1 && (x==5 || x==10) number <- number - prev - prev else if prev==10 && (x==50 || x==100) number <- number - prev - prev else if prev==1 && (x==5 || x==10) number <- number - prev - prev prev <- x return number; ``` #### 18) [Integer-to-Roman](https://leetcode.com/problems/integer-to-roman) - a) ``` intToRoman( num: int ) -> String str: String ones: Array[type=String] tens: Array[type=String] hrns: Array[type=String] ths: Array[type=String] ones <- {"","I","II","III","IV","V","VI","VII","VIII","IX"} tens <- {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"} hrns <- {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"} ths <- {"","M","MM","MMM"} str.Append ths[num/1000] str.Append hrns[(num mod 1000)/100] str.Append tens[(num mod 100)/10] str.Append ones[num mod 10] return str ``` - b) ``` intToRoman( num: int ) -> String str: String mertebe: Array[type=char] beshlik: Array[type=char] mertebe <- {' ', 'I', 'X', 'C', 'M'}; beshlik <- {' ', 'V', 'L', 'D'}; h <- 1000 i <- 0 m <- 4 while h>0 c <- num/h num <- num mod h x <- mertebe[m] if c==4 str.Append x str.Append beshlik[m] else if c==9 str.Append x str.Append mertebe[m+1] else if c>=5 str.Append beshlik[m] for i in 0..c-5 str.Append x else for i in 0..c str.Append x h <- h/10 m <- (m - 1) return str ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.