1
Leetcode-array
source link: https://brantou.github.io/2017/07/16/leetcode-array/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
type Interval struct {
Start int
End int
}
1 best time to buy and sell stock
func maxProfit(prices []int) int {
if len(prices) < 1 {
return 0
}
var mp int
min_p := prices[0]
for _, price := range prices {
if price-min_p > mp {
mp = price - min_p
}
if price < min_p {
min_p = price
}
}
return mp
}
2 best time to buy and sell stock II
func maxProfit(prices []int) int {
if len(prices) < 1 {
return 0
}
var mp, pre_p, buy_p int
var status string // buy sell
for index, price := range prices {
if index == 0 {
pre_p = price
buy_p = price
status = "buy"
continue
}
if price > pre_p && status == "sell" {
buy_p = pre_p
status = "buy"
}
if pre_p > price && status == "buy" {
mp += pre_p - buy_p
status = "sell"
}
pre_p = price
}
if pre_p > buy_p && status == "buy" {
mp += pre_p - buy_p
}
return mp
}
3 plus one
func plusOne(digits []int) []int {
var carry int
carry = 1
for index := len(digits) - 1; index >= 0; index -= 1 {
if carry+digits[index] == 10 {
carry = 1
digits[index] = 0
} else {
digits[index] += carry
carry = 0
}
if carry == 0 {
break
}
}
if carry == 1 {
return append([]int{1}, digits...)
}
return digits
}
4 pascal's triangle
func generate(numRows int) [][]int {
pt_arr := make([][]int, 0)
if numRows < 1 {
return pt_arr
}
pt_arr = append(pt_arr, []int{1})
if numRows == 1 {
return pt_arr
}
pt_arr = append(pt_arr, []int{1, 1})
if numRows < 3 {
return pt_arr
}
for i := 3; i <= numRows; i += 1 {
pt := make([]int, i)
pre_pt := pt_arr[i-2]
var pre int
for index, _ := range pre_pt {
if index == 0 {
pt[index] = pre_pt[index]
pre = pre_pt[index]
continue
}
if index == len(pre_pt)-1 {
pt[index] = pre + pre_pt[index]
pt[index+1] = pre_pt[index]
continue
}
pt[index] = pre + pre_pt[index]
pre = pre_pt[index]
}
pt_arr = append(pt_arr, pt)
}
return pt_arr
}
func main() {
fmt.Println(generate(3))
}
5 pascal's triangle II
func getRow(rowIndex int) []int {
rowIndex += 1
pt_row := make([]int, rowIndex)
if rowIndex < 1 {
return pt_row
}
pt_row[0] = 1
if rowIndex == 1 {
return pt_row
}
pt_row[1] = 1
for i := 3; i <= rowIndex; i += 1 {
ptr := pt_row[0:i]
pre_ptr := pt_row[0 : i-1]
var pre int
for index, _ := range pre_ptr {
if index == 0 {
pre = pre_ptr[index]
continue
}
if index == len(pre_ptr)-1 {
ptr[index+1] = pre_ptr[index]
ptr[index] = pre + pre_ptr[index]
continue
}
pre_num := pre_ptr[index]
ptr[index], pre = pre+pre_num, pre_num
}
}
return pt_row
}
func main() {
fmt.Println(getRow(4))
}
6 array partition I
func min(a, b int) int {
if a > b {
return b
} else {
return a
}
}
func arrayPairSum(nums []int) int {
sort.Ints(nums)
var p_sum int
for index := 0; index < len(nums); index += 2 {
p_sum += min(nums[index], nums[index+1])
}
return p_sum
}
7 find all numbers disappeared in an array
func findDisappearedNumbers(nums []int) []int {
if len(nums) < 1 {
return nums
}
dis_nums := make([]int, 0)
var pre, pre_index int
for index, num := range nums {
if index+1 != num && num != 0 {
pre = num
pre_index = index
break
}
}
if pre == 0 {
return dis_nums
}
for i := 0; i < len(nums); i += 1 {
if nums[pre-1] != pre && nums[pre-1] != 0 {
nums[pre-1], pre = pre, nums[pre-1]
continue
}
if nums[pre-1] == 0 {
nums[pre-1] = pre
}
nums[pre_index] = 0
for index, num := range nums {
if index+1 != num && num != 0 {
pre = num
pre_index = index
break
}
}
}
nums[pre-1] = pre
for index, num := range nums {
if index+1 != num {
dis_nums = append(dis_nums, index+1)
}
}
return dis_nums
}
func findDisappearedNumbers(nums []int) []int {
marks := make([]int, 0)
for _, num := range nums {
marks[num-1] = 1
}
dis_nums := make([]int, 0)
for index, mark := range marks {
if mark == 0 {
dis_nums = append(dis_nums, index+1)
}
}
return dis_nums
}
func main() {
fmt.Println(findDisappearedNumbers([]int{4,3,2,7,8,2,3,1}))
}
8 two sum
func twoSum(nums []int, target int) []int {
indices := make([]int, 0)
for i := 0; i < len(nums); i += 1 {
fir := nums[i]
for j := i+1; j < len(nums); j +=1 {
secd := nums[j]
if fir + secd == target {
indices = append(indices, i)
indices = append(indices, j)
break
}
}
}
return indices
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
var carry int
var sum_head, sum_curr *ListNode
for {
if l1 == nil && l2 == nil {
if carry > 0 {
sum_node := &ListNode{
Val: carry,
Next: nil,
}
if sum_head != nil {
sum_curr.Next = sum_node
sum_curr = sum_node
} else {
sum_head = sum_node
sum_curr = sum_node
}
}
break
}
var sum int
if l1 != nil && l2 != nil {
sum = l1.Val + l2.Val + carry
l1, l2 = l1.Next, l2.Next
} else if l2 == nil {
sum = l1.Val + carry
l1 = l1.Next
} else if l1 == nil {
sum = l2.Val + carry
l2 = l2.Next
}
if sum > 9 {
carry = 1
sum -= 10
} else {
carry = 0
}
sum_node := &ListNode{
Val: sum,
Next: nil,
}
if sum_head != nil {
sum_curr.Next = sum_node
sum_curr = sum_node
} else {
sum_head = sum_node
sum_curr = sum_node
}
}
return sum_head
}
type ListNode struct {
Val int
Next *ListNode
}
func make_list(vals []int) *ListNode{
var lst, lst_c *ListNode
for _, val := range vals {
node := &ListNode{
Val: val,
Next: nil,
}
if lst != nil {
lst_c.Next = node
lst_c = node
} else {
lst = node
lst_c = node
}
}
return lst
}
func print_list(lst *ListNode) {
var str string
for {
if lst == nil {
break
}
str += fmt.Sprintf("%d,", lst.Val)
lst = lst.Next
}
str = strings.Trim(str, ",")
fmt.Printf("[%s]", str)
}
func main() {
l1 := make_list([]int{2,4,3})
l2 := make_list([]int{5,6,4})
sum_lst := addTwoNumbers(l1,l2)
print_list(sum_lst)
}
9 two sum II - input array is sorted
func twoSum(nums []int, target int) []int {
indices := make([]int, 0)
for i := 0; i < len(nums); i += 1 {
fir := nums[i]
for j := i + 1; j < len(nums); j += 1 {
secd := nums[j]
if fir+secd == target {
indices = append(indices, i+1)
indices = append(indices, j+1)
break
}
}
}
return indices
}
10 remove duplicates from sorted array
func removeDuplicates(nums []int) int {
if (len(nums)) <2 {
return len(nums)
}
pre := nums[0]
size := 1
for _, num := range nums {
if pre != num {
pre = num
nums[size] = num
size++
}
}
return size
}
11 remove duplicates from sorted array II
func removeDuplicates(nums []int) int {
if (len(nums)) < 3 {
return len(nums)
}
size := 2
pp_num := nums[0]
p_num := nums[1]
nums_size := len(nums)
for i := 2; i < nums_size; i++ {
if nums[i] == p_num && p_num == pp_num {
continue
}
pp_num = p_num
p_num = nums[i]
nums[size] = nums[i]
size++
}
return size
}
12 remove element
func removeElement(nums []int, val int) int {
var size int
for index, num := range nums {
if index == 0 {
if num == val {
size = 0
} else {
size = 1
}
continue
}
if num != val {
nums[size] = num
size += 1
}
}
return size
}
13 majority element
func majorityElement(nums []int) int {
num_M := make(map[int]int)
for _, num := range nums {
time := num_M[num]
num_M[num] = time + 1
}
var mt_num, max_times int
for num, time := range num_M {
if time > max_times {
mt_num = num
max_times = time
}
}
return mt_num
}
14 DONE shortest unsorted continuous subarray
- State "DONE" from "STARTED" [2017-07-17 Mon 23:32]
func findUnsortedSubarray(nums []int) int {
n_nums := make([]int, len(nums))
copy(n_nums, nums)
sort.Ints(n_nums)
var start, end int
for index, _ := range nums {
if nums[index] != n_nums[index] {
start = index
break
}
}
for index := len(nums) - 1; index >= 0; index -= 1 {
if nums[index] != n_nums[index] {
end = index + 1
break
}
}
return end - start
}
15 reshape the matrix
func matrixReshape(nums [][]int, r int, c int) [][]int {
if len(nums) < 1 || len(nums[0]) < 1 {
return [][]int{}
}
or := len(nums)
oc := len(nums[0])
if or*oc != r*c {
return nums
}
f_nums := make([]int, 0)
for index, _ := range nums {
row := nums[index]
f_nums = append(f_nums, row...)
}
n_nums := make([][]int, r)
for i := 0; i < r; i += 1 {
row := make([]int, c)
for j := 0; j < c; j += 1 {
row[j] = f_nums[i*c+j]
}
n_nums[i] = row
}
return n_nums
}
16 search insert position
func searchInsert(nums []int, target int) int {
for index, num := range nums {
if num == target {
return index
}
if num > target {
return index
}
}
return len(nums)
}
17 merge sorted array
func merge(nums1 []int, m int, nums2 []int, n int) {
if m == 0 {
for i := 0; i < n; i += 1 {
nums1[i] = nums2[i]
}
return
}
if n == 0 {
return
}
n1_index := m - 1
n2_index := n - 1
index := m + n - 1
for {
if n1_index < 0 || n2_index < 0 {
break
}
if nums1[n1_index] > nums2[n2_index] {
nums1[index] = nums1[n1_index]
n1_index -= 1
index -= 1
} else {
nums1[index] = nums2[n2_index]
n2_index -= 1
index -= 1
}
}
if n2_index >= 0 {
for i := 0; i <= n2_index; i += 1 {
nums1[i] = nums2[i]
}
}
return
}
18 maximum product of three numbers
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func maximumProduct(nums []int) int {
sort.Ints(nums)
size := len(nums)
return max(nums[size-1]*nums[size-2]*nums[size-3], nums[0]*nums[1]*nums[size-1])
}
19 maximum average subarray I
func findMaxAverage(nums []int, k int) float64 {
var max_average float64
for index := 0; index <= len(nums)-k; index += 1 {
var sub_sum int
for j := 0; j < k; j += 1 {
sub_sum += nums[index+j]
}
average := float64(sub_sum) / float64(k)
if index == 0 {
max_average = average
continue
}
if max_average < average {
max_average = average
}
}
return max_average
}
20 move zeroes
func moveZeroes(nums []int) {
for index, num := range nums {
if num == 0 {
continue
}
for j := index; 0 < j; j -= 1 {
if nums[j-1] == 0 {
nums[j-1], nums[j] = nums[j], nums[j-1]
} else {
break
}
}
}
return
}
func main() {
nums := []int{0, 1, 0, 3, 12}
moveZeroes(nums)
fmt.Println(nums)
}
21 can place flowers
func canPlaceFlowers(flowerbed []int, n int) bool {
if len(flowerbed) < 1 && n > 0 {
return false
}
if n == 0 {
return true
}
if len(flowerbed) < n {
return false
}
if len(flowerbed) == 1 {
if flowerbed[0] == 0 && n == 1 {
return true
} else {
return false
}
}
for index, _ := range flowerbed {
if flowerbed[index] == 1 {
continue
}
switch index {
case 0:
if flowerbed[index+1] == 0 {
flowerbed[index] = 1
n -= 1
}
case len(flowerbed) - 1:
if flowerbed[index-1] == 0 {
flowerbed[index] = 1
n -= 1
}
default:
if flowerbed[index-1] == 0 && flowerbed[index+1] == 0 {
flowerbed[index] = 1
n -= 1
}
}
if n < 1 {
return true
}
}
return false
}
22 contains duplicate
func containsDuplicate(nums []int) bool {
num_M := make(map[int]bool)
for _, num := range nums {
num_M[num] = true
}
return len(nums) > len(num_M)
}
23 contains duplicate II
func containsNearbyDuplicate(nums []int, k int) bool {
num_M := make(map[int]bool)
for index, num := range nums {
if index > k {
delete(num_M, nums[index-k-1])
}
if num_M[num] {
return true
}
num_M[num] = true
}
return false
}
24 contains duplicate III
func abs(x int) int {
if x < 0 {
return -x
} else {
return x
}
}
func getQuot(i, w int) int {
if i < 0 {
return (i+1)/w - 1
} else {
return i / w
}
}
func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
if t < 0 {
return false
}
num_M := make(map[int]int)
w := t + 1
for index, num := range nums {
quot := getQuot(num, w)
if _, ok := num_M[quot]; ok {
return true
}
if pre_num, ok := num_M[quot-1]; ok && abs(num-pre_num) < w {
return true
}
if pre_num, ok := num_M[quot+1]; ok && abs(num-pre_num) < w {
return true
}
num_M[quot] = num
if index >= k {
delete(num_M, getQuot(nums[index-k], w))
}
}
return false
}
25 k-diff pairs in an array
func findPairs(nums []int, k int) int {
sort.Ints(nums)
var base_index, pair_size int
for {
for i := base_index + 1; i < len(nums); i += 1 {
if nums[i]-nums[base_index] > k {
break
}
if nums[i]-nums[base_index] == k {
pair_size += 1
break
}
}
old_bi := base_index
for i := base_index + 1; i < len(nums); i += 1 {
if nums[i]-nums[base_index] > 0 {
base_index = i
break
}
}
if old_bi == base_index {
break
}
if base_index == len(nums)-1 {
break
}
}
return pair_size
}
26 best time to buy and sell stock II
func maxProfit(prices []int) int {
if len(prices) < 1 {
return 0
}
var mp, pre_p, buy_p int
var status string // buy sell
for index, price := range prices {
if index == 0 {
pre_p = price
buy_p = price
status = "buy"
continue
}
if price > pre_p && status == "sell" {
buy_p = pre_p
status = "buy"
}
if pre_p > price && status == "buy" {
mp += pre_p - buy_p
status = "sell"
}
pre_p = price
}
if pre_p > buy_p && status == "buy" {
mp += pre_p - buy_p
}
return mp
}
27 DONE maximum subarray
- State "DONE" from "WAITING" [2017-07-18 Tue 23:30]
func maxSubArray(nums []int) int {
if len(nums) < 1 {
return 0
}
size := len(nums)
max_sum := nums[0]
pre_sum := nums[0]
for i := 1; i < size; i += 1 {
if pre_sum > 0 {
pre_sum = nums[i] + pre_sum
} else {
pre_sum = nums[i]
}
if pre_sum > max_sum {
max_sum = pre_sum
}
}
return max_sum
}
28 missing number
func missingNumber(nums []int) int {
var sum int
for _, num := range nums {
sum += num
}
size := len(nums)
return size*(size+1)/2 - sum
}
29 max consecutive ones
func findMaxCntecutiveOnes(nums []int) int {
var cnt, max_cnt int
for _, num := range nums {
if num == 0 {
if cnt > max_cnt {
max_cnt = cnt
}
cnt = 0
}
if num == 1 {
cnt += 1
}
}
if cnt > max_cnt {
max_cnt = cnt
}
return max_cnt
}
30 rotate array
func reverse(nums []int) {
size := len(nums)
mid := size / 2
for i := 0; i < mid; i += 1 {
nums[i], nums[size-i-1] = nums[size-i-1], nums[i]
}
}
func rotate(nums []int, k int) {
size := len(nums)
if size == 1 {
return
}
k = k % size
reverse(nums[0 : size-k])
reverse(nums[size-k : size])
reverse(nums)
}
func main() {
arr := []int{1,2,3,4,5,6,7}
rotate(arr, 3)
fmt.Println(arr)
}
31 find peak element
func findPeakElement(nums []int) int {
if len(nums) < 1 {
return -1
}
if len(nums) == 1 {
return 0
}
var pe int
size := len(nums)
for i := 0; i < size; i += 1 {
switch i {
case 0:
if nums[0] > nums[1] {
return 0
}
case size - 1:
if nums[size-1] > nums[size-2] {
return size - 1
}
default:
if nums[i-1] < nums[i] && nums[i] > nums[i+1] {
return i
}
}
}
return -1
}
32 maximum product subarray
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func min(a, b int) int {
if a > b {
return b
} else {
return a
}
}
func maxProduct(nums []int) int {
if len(nums) < 1 {
return 0
}
size := len(nums)
maxp_sub_arr := make([]int, size)
ng_maxp_sub_arr := make([]int, size)
maxp_sub_arr[0] = nums[0]
if maxp_sub_arr[0] < 0 {
ng_maxp_sub_arr[0] = maxp_sub_arr[0]
} else {
ng_maxp_sub_arr[0] = 1
}
for i := 1; i < size; i += 1 {
if nums[i] == 0 {
continue
}
if maxp_sub_arr[i-1] == 0 {
maxp_sub_arr[i] = nums[i]
if nums[i] < 0 {
ng_maxp_sub_arr[i] = maxp_sub_arr[i]
} else {
ng_maxp_sub_arr[i] = 1
}
}
if nums[i] > 0 {
maxp_sub_arr[i] = max(nums[i]*maxp_sub_arr[i-1], nums[i])
ng_maxp_sub_arr[i] = nums[i] * ng_maxp_sub_arr[i-1]
}
if nums[i] < 0 {
maxp_sub_arr[i] = nums[i] * ng_maxp_sub_arr[i-1]
ng_maxp_sub_arr[i] = min(nums[i]*maxp_sub_arr[i-1], nums[i])
}
}
maxp := maxp_sub_arr[0]
for _, subp := range maxp_sub_arr {
if subp > maxp {
maxp = subp
}
}
return maxp
}
func main() {
fmt.Println(maxProduct([]int{2,3,-2,4,0,-3,-4}))
}
33 minimum size subarray sum
func minSubArrayLen(s int, nums []int) int {
if len(nums) < 0 {
return 0
}
var sub_sum, msub_arl, sub_arl int
size := len(nums)
msub_arl = size + 1
for index, num := range nums {
if sub_sum+num < s {
sub_sum += num
sub_arl += 1
continue
}
if sub_sum+num >= s {
for {
if sub_arl < 1 {
break
}
del_num := nums[index-sub_arl]
sub_sum -= del_num
sub_arl -= 1
if sub_sum+num < s {
sub_sum += num
sub_arl += 1
break
}
}
if sub_arl+1 < msub_arl {
msub_arl = sub_arl + 1
}
}
}
if msub_arl == size+1 {
msub_arl = 0
}
return msub_arl
}
func main() {
fmt.Println(minSubArrayLen(15, []int{5,1,3,5,10,7,4,9,2,8}))
}
34 array nesting
func arrayNesting(nums []int) int {
anl_arr := make([]int, len(nums))
var max_anl int
for _, num := range nums {
if anl_arr[num] > 0 {
continue
}
var anl int
next_num := num
for {
anl_arr[next_num] = 1
anl += 1
next_num = nums[next_num]
if next_num == num {
break
}
}
if anl > max_anl {
max_anl = anl
}
}
return max_anl
}
func main() {
fmt.Println(arrayNesting([]int{5,4,0,3,1,6,2}))
}
35 triangle
func min(a, b int) int {
if a < b {
return a
} else {
return b
}
}
func minimumTotal(triangle [][]int) int {
pre_nums := triangle[0]
trg_size := len(triangle)
for i := 1; i < trg_size; i += 1 {
nums := triangle[i]
n_size := len(nums)
for j, _ := range nums {
switch j {
case 0:
nums[0] += pre[0]
case n_size - 1:
nums[n_size-1] += pre_nums[n_size-2]
default:
nums[j] += min(pre_nums[j-1], pre_nums[j])
}
}
pre_nums = nums
}
min_total := pre_nums[0]
for _, num := range pre_nums {
if num < min_total {
min_total = num
}
}
return min_total
}
36 subsets
func subsets(nums []int) [][]int {
if len(nums) < 1 {
return [][]int{[]int{}}
}
sub_sets := subsets(nums[1:])
sets := sub_sets
num := nums[0]
for _, set := range sub_sets {
nset := append([]int{num}, set...)
sets = append(sets, nset)
}
return sets
}
37 subsets II
type Item struct {
Num int
Count int
}
func subsetsWithDup(nums []int) [][]int {
num_M := make(map[int]int)
for _, num := range nums {
num_M[num] += 1
}
items := make([]*Item, 0)
for num, count := range num_M {
item := &Item{
Num: num,
Count: count,
}
items = append(items, item)
}
return subsets(items)
}
func subsetsHelper(item *Item, sub_sets [][]int) [][]int {
sets := sub_sets
for _, set := range sub_sets {
var _count int
for {
if _count == item.Count {
break
}
set = append([]int{item.Num}, set...)
sets = append(sets, set)
_count += 1
}
}
return sets
}
func subsets(items []*Item) [][]int {
if len(items) < 1 {
return [][]int{[]int{}}
}
return subsetsHelper(items[0], subsets(items[1:]))
}
38 search in rotated sorted array
func search(nums []int, target int) int {
start, end := 0, len(nums)-1
for start <= end {
mid := start + (end-start)/2
if nums[mid] == target {
return mid
}
if start == end {
break
}
if (nums[start] <= nums[mid] && (target < nums[start] || nums[mid] < target)) ||
(nums[mid] <= nums[end] && (target >= nums[mid] && nums[end] >= target)) {
start = mid + 1
continue
}
if (nums[start] <= nums[mid] && (target >= nums[start] && nums[mid] >= target)) ||
(nums[mid] <= nums[end] && (target < nums[mid] || nums[end] < target)) {
end = mid - 1
continue
}
}
return -1
}
39 search in rotated sorted array II
func search(nums []int, target int) bool {
start, end := 0, len(nums)-1
for start <= end {
if nums[start] == nums[end] {
if nums[start] == target {
return true
}
dup_num := nums[start]
for {
if start == end || nums[start] != dup_num {
break
}
start++
}
for {
if start == end || nums[end] != dup_num {
break
}
end--
}
}
mid := start + (end-start)/2
if nums[mid] == target {
return true
}
if start == end {
break
}
if (nums[start] <= nums[mid] && (target < nums[start] || nums[mid] < target)) ||
(nums[mid] <= nums[end] && (target >= nums[mid] && nums[end] >= target)) {
start = mid + 1
continue
}
if (nums[start] <= nums[mid] && (target >= nums[start] && nums[mid] >= target)) ||
(nums[mid] <= nums[end] && (target < nums[mid] || nums[end] < target)) {
end = mid - 1
continue
}
}
return false
}
40 search a 2d matrix
func searchMatrix(matrix [][]int, target int) bool {
length := len(matrix)
if length < 1 {
return false
}
start, end := 0, length-1
width := len(matrix[0])
for start <= end {
if start == end {
break
}
mid := start + (end-start)/2
if matrix[mid][0] > target {
end = mid - 1
} else if matrix[mid][0] < target {
if target > matrix[mid][width-1] {
start = mid + 1
} else {
start = mid
break
}
} else {
return true
}
}
return binary_search(matrix[start], target) != -1
}
func binary_search(nums []int, target int) int {
start, end := 0, len(nums)-1
for start <= end {
mid := start + (end-start)/2
if nums[mid] > target {
end = mid - 1
} else if nums[mid] < target {
start = mid + 1
} else {
return mid
}
}
return -1
}
41 sort colors
func sortColors(nums []int) {
colors := make([]int, 3)
for _, num := range nums {
colors[num] += 1
}
var base int
for color, count := range colors {
for count > 0 {
nums[base] = color
count--
base++
}
}
return
}
42 set matrix zeroes
func setZeroes(matrix [][]int) {
length := len(matrix)
if length < 1 {
return
}
width := len(matrix[0])
row_M := make(map[int]bool, length)
col_M := make(map[int]bool, width)
for i := 0; i < length; i++ {
for j := 0; j < width; j++ {
if matrix[i][j] == 0 {
row_M[i] = true
col_M[j] = true
}
}
}
if len(row_M) > 0 {
for row, _ := range row_M {
for i := 0; i < width; i++ {
matrix[row][i] = 0
}
}
}
if len(col_M) > 0 {
for col, _ := range col_M {
for i := 0; i < length; i++ {
matrix[i][col] = 0
}
}
}
return
}
43 unique paths
func uniquePaths(m int, n int) int {
if m < 2 {
return m
}
matrix := make([][]int, 2)
matrix[0] = make([]int, n)
matrix[1] = make([]int, n)
for i := 0; i < n; i++ {
matrix[0][i] = 1
}
matrix[1][0] = 1
pre_row := matrix[0]
curr_row := matrix[1]
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
curr_row[j] = curr_row[j-1] + pre_row[j]
}
pre_row, curr_row = curr_row, pre_row
}
return pre_row[n-1]
}
44 unique paths II
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
m := len(obstacleGrid)
if m < 1 {
return 0
}
n := len(obstacleGrid[0])
if n < 1 {
return 0
}
if obstacleGrid[0][0] == 1 {
return 0
}
matrix := make([][]int, 2)
matrix[0] = make([]int, n)
matrix[1] = make([]int, n)
for i := 0; i < n; i++ {
if obstacleGrid[0][i] == 1 {
break
}
matrix[0][i] = 1
}
if m > 1 && obstacleGrid[1][0] == 0 {
matrix[1][0] = 1
}
pre_row := matrix[0]
curr_row := matrix[1]
for i := 1; i < m; i++ {
for j := 0; j < n; j++ {
if obstacleGrid[i][j] == 0 {
if j > 0 {
curr_row[j] = curr_row[j-1] + pre_row[j]
} else {
curr_row[j] = pre_row[j]
}
} else {
curr_row[j] = 0
}
}
pre_row, curr_row = curr_row, pre_row
}
return pre_row[n-1]
}
45 spiral matrix
func spiralOrder(matrix [][]int) []int {
m := len(matrix)
if m < 1 {
return []int{}
}
n := len(matrix[0])
row_start := 0
row_end := m
col_start := 0
col_end := n
so_arr := make([]int, 0, m*n)
for {
for i := col_start; i < col_end; i++ {
so_arr = append(so_arr, matrix[row_start][i])
}
row_start += 1
if row_start == row_end {
break
}
for i := row_start; i < row_end; i++ {
so_arr = append(so_arr, matrix[i][col_end-1])
}
col_end -= 1
if col_start == col_end {
break
}
for i := col_end - 1; i >= col_start; i-- {
so_arr = append(so_arr, matrix[row_end-1][i])
}
row_end -= 1
if row_start == row_end {
break
}
for i := row_end - 1; i >= row_start; i-- {
so_arr = append(so_arr, matrix[i][col_start])
}
col_start += 1
if col_start == col_end {
break
}
}
return so_arr
}
46 spiral matrix II
func generateMatrix(n int) [][]int {
if n == 0 {
return [][]int{}
}
matrix := make([][]int, n)
for i := 0; i < n; i++ {
matrix[i] = make([]int, n)
}
row_start := 0
row_end := n
col_start := 0
col_end := n
num := 1
for {
for i := col_start; i < col_end; i++ {
matrix[row_start][i] = num
num += 1
}
row_start += 1
if row_start == row_end {
break
}
for i := row_start; i < row_end; i++ {
matrix[i][col_end-1] = num
num += 1
}
col_end -= 1
if col_start == col_end {
break
}
for i := col_end - 1; i >= col_start; i-- {
matrix[row_end-1][i] = num
num += 1
}
row_end -= 1
if row_start == row_end {
break
}
for i := row_end - 1; i >= row_start; i-- {
matrix[i][col_start] = num
num += 1
}
col_start += 1
if col_start == col_end {
break
}
}
return matrix
}
47 merge intervals
func merge(intervals []Interval) []Interval {
size := len(intervals)
if size < 2 {
return intervals
}
sort.Slice(intervals,
func(i, j int) bool {
return intervals[i].Start < intervals[j].Start
})
merge_intervals := make([]Interval, 0)
interval := intervals[0]
for i := 1; i < size; i++ {
if interval.End >= intervals[i].Start {
if interval.End < intervals[i].End {
interval.End = intervals[i].End
}
} else {
merge_intervals = append(merge_intervals, interval)
interval = intervals[i]
}
}
if interval.Start != intervals[0].Start {
merge_intervals = append(merge_intervals, interval)
}
if len(merge_intervals) < 1 {
merge_intervals = append(merge_intervals, interval)
}
return merge_intervals
}
48 jump game
class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.size() < 2) {
return true;
}
if (nums[0]==0) {
return false;
}
deque<int> position_deq;
set<int> position_set;
position_deq.push_back(0);
position_set.insert(0);
while (position_deq.size()>0) {
int position = position_deq.front();
position_deq.pop_front();
if (nums[position] > 0) {
for (int i = 1; i <= nums[position]; i++) {
int new_position = position +i;
if (new_position == nums.size()-1) {
return true;
}
if (nums[new_position]>0 &&
position_set.find(new_position) != position_set.end()) {
position_deq.push_back(new_position);
}
}
}
}
return false;
}
};
func canJump(nums []int) bool {
size := len(nums)
var i, reach int
for ; i < size && i <= reach; i++ {
if i+nums[i] > reach {
reach = i + nums[i]
}
}
return i == size
}
49 search for a range
func searchRange(nums []int, target int) []int {
target_index := binary_search(nums, target)
if target_index == -1 {
return []int{-1, -1}
}
start_index := target_index
for {
s_index := binary_search(nums[:start_index], target)
if s_index == -1 {
break
}
start_index = s_index
}
end_index := target_index
for {
e_index := binary_search(nums[end_index+1:], target)
if e_index == -1 {
break
}
end_index += 1 + e_index
}
return []int{start_index, end_index}
}
func binary_search(nums []int, target int) int {
start, end := 0, len(nums)-1
for start <= end {
mid := start + (end-start)/2
if nums[mid] > target {
end = mid - 1
} else if nums[mid] < target {
start = mid + 1
} else {
return mid
}
}
return -1
}
50 rotate image
func rotate(matrix [][]int) {
if len(matrix) < 2 {
return
}
size := len(matrix)
for i := 0; i < size-1; i++ {
var tmp int
matrix[i][size-1], tmp = matrix[0][i], matrix[i][size-1]
matrix[size-1][size-i-1], tmp = tmp, matrix[size-1][size-i-1]
matrix[size-i-1][0], tmp = tmp, matrix[size-i-1][0]
matrix[0][i] = tmp
}
if size-2 > 0 {
sub_matrix := make([][]int, 0, size-2)
for i := 1; i < size-1; i++ {
sub_matrix = append(sub_matrix, matrix[i][1:size-1])
}
rotate(sub_matrix)
}
return
}
51 valid triangle number
func triangleNumber(nums []int) int {
if len(nums) < 3 {
return 0
}
sort.Ints(nums)
size := len(nums)
var count int
for i := 0; i < size-2; i++ {
for j := i + 1; j < size-1; j++ {
for k := j + 1; k < size; k++ {
if nums[i]+nums[j] <= nums[k] {
break
}
count++
}
}
}
return count
}
52 DONE task scheduler
- State "DONE" from "TODO" [2018-03-07 Wed 21:55]
func leastInterval(tasks []byte, n int) int {
if n == 0 {
return len(tasks)
}
n += 1
task_M := make(map[byte]int)
for _, tc := range tasks {
task_M[tc] += 1
}
task_num_arr := make([]int, 0)
for _, task_num := range task_M {
task_num_arr = append(task_num_arr, task_num)
}
sort.Ints(task_num_arr)
remain_tc_num := len(task_num_arr)
var interval_num int
for {
if remain_tc_num < 1 {
break
}
fmt.Println(remain_tc_num, interval_num, task_num_arr)
if remain_tc_num < n {
remain_max_tn := task_num_arr[remain_tc_num-1]
tn_index := remain_tc_num - 2
same_max_tn_num := 1
for {
if tn_index < 0 || task_num_arr[tn_index] < remain_max_tn {
break
}
same_max_tn_num += 1
tn_index -= 1
}
interval_num += (task_num_arr[remain_tc_num-1]-1)*n + same_max_tn_num
break
}
min_tn := task_num_arr[remain_tc_num-n]
tn_index := remain_tc_num - n + 1
same_min_tn_num := 1
for {
if tn_index == remain_tc_num || task_num_arr[tn_index] > min_tn {
break
}
same_min_tn_num += 1
tn_index += 1
}
interval_num += (min_tn) * n
rs_index := remain_tc_num - n
ls_index := rs_index + same_min_tn_num
fmt.Println(rs_index, ls_index, same_min_tn_num)
for {
if ls_index == remain_tc_num {
for {
if rs_index == remain_tc_num {
break
}
task_num_arr[rs_index] = task_num_arr[remain_tc_num-1]
rs_index += 1
}
break
}
task_num_arr[rs_index] = task_num_arr[ls_index] - min_tn
rs_index += 1
ls_index += 1
}
remain_tc_num -= same_min_tn_num
sort.Ints(task_num_arr)
}
return interval_num
}
func leastInterval(tasks []byte, n int) int {
if n == 0 {
return len(tasks)
}
task_M := make(map[byte]int)
for _, tc := range tasks {
task_M[tc] += 1
}
task_num_arr := make([]int, 26)
tn_index := 0
for _, task_num := range task_M {
task_num_arr[tn_index] = task_num
tn_index += 1
}
sort.Ints(task_num_arr)
var interval_num int
for {
if task_num_arr[25] <= 0 {
break
}
var tn_index int
for {
if tn_index > n {
break
}
if task_num_arr[25] == 0 {
break
}
if tn_index < 26 && task_num_arr[25-tn_index] > 0 {
task_num_arr[25-tn_index] -= 1
}
interval_num += 1
tn_index += 1
}
sort.Ints(task_num_arr)
}
return interval_num
}
package main
func main() {
fmt.Println(leastInterval([]byte("FJJAJFCHJBEGGFACIFJCJCHCADGHBFGCCAEBHJEIFDEACDBDJJCFDDJHAECDJDGGBCEGHIDHFEIBDEIECJGIDEDJCACCDIJBDHHJGBGAHEHEDEJEJCFCJGBCIIHFADGFCCFGCJBBICJJEGHCIGJIGGJGGEGBIJBHDHGFCHCDAGBHHBJCAFJGFEBFEBBAEFEHIICGJDHEFGGDEBFJJJDHEBDJIFCIEHFEGDECFEDEAIEADHGCIEGAHIGGAGFHJDFAGHBJAHBHCGFACCBIGGBCJJIEGDIJICGAJGFJFCFGJIEBGFADAIAEHFDDCBJIJHICDAGFIBEDCJGIHECEIIBBHJCFIDBFHFACAABDCAGBGFEGAAACJHHGCCBCEBEFIEEDIHGFAHBJBGHCCBGCBAEGAJGDCIGFGGAJEIDEAFAHCEDDDHIFFAFAACJDJHIFACBCACCHAJIBAIFJCIBCEEEJGFEIAAEBJHHHAHJEFEFGJDIDIFBJDAADFGBJHFADHCBAJHIFHEGBAFFACDGIIJHHCJGBADBFJDIAFFFFAEBCGHEBBAGDCCEACFGAIFBHJGCBHDAHBHHCAFICFACJIHHFBBDECJFCEAJECAEBAJFJJJHHCIEGGHJJHHHJHAGICECDGGFHDGHAEIDAHGEABFICAFBAIFGIFDABJBDFGJJAACHGFBIIJAHDFEFJBFCGEAGHEHHFIGCCGJBHFHDIBDIFHIDFGGEACAGHGHJFDFGDDCJCJGGGGHHGDEHGCBFIFCHJIAFDCFCEEDDCGBFEJCIEDBBIIIHCECJFGAIJDICGFIEIEFAGEJAIADAGJFEDIAEJICJBFBECEFGEJJIEDFCHHBGDIIFBGCFJBGJHDGCCIIEIBHBIGFHGCJDCEGFCHDACDHBCHIBAJCBDJDHFBAGGJIEFADHDBCAHFGBFHBHIJDHIBCDGAEAAIFIFBBIFAEIABGCFIAFIDHBIIBJFEBBBDCJEJJGDFFFGIHJJGDGF") 8))
}
53 DONE word search
- State "DONE" from "TODO" [2017-07-24 Mon 00:27]
struct Coord {
int x;
int y;
char letter;
int seq_num;
int dir;
};
struct CoordComp {
bool operator() (const Coord& lhs, const Coord& rhs) const {
if (lhs.x<rhs.x) {
return true;
} else if (lhs.x>rhs.x) {
return false;
} else {
return lhs.y<rhs.y;
}
}
};
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for (int i=0; i < board.size(); i++) {
for (int j=0; j < board[i].size(); j++) {
if (board[i][j]==word[0]) {
Coord coord={i,j,word[0],0,0};
stack<Coord> coord_stk;
set<Coord,CoordComp> coord_set;
coord_stk.push(coord);
coord_set.insert(coord);
while (coord_stk.size()>0) {
Coord coord = coord_stk.top();
if (coord.seq_num == word.size()-1) {
return true;
}
coord_stk.pop();
coord_set.erase(coord);
int x, y;
x = coord.x;
y = coord.y;
for (int dir=coord.dir; dir<4; dir++) {
if (dir == 0 && y > 0 && board[x][y-1]==word[coord.seq_num+1]) {
coord.dir = 1;
coord_stk.push(coord);
coord_set.insert(coord);
Coord next_coord={x,y-1,word[coord.seq_num+1],coord.seq_num+1,0};
if (coord_set.find(next_coord) == coord_set.end()) {
coord_stk.push(next_coord);
coord_set.insert(next_coord);
}
break;
}
if (dir == 1 && x > 0 && board[x-1][y]==word[coord.seq_num+1]) {
coord.dir = 2;
coord_stk.push(coord);
coord_set.insert(coord);
Coord next_coord={x-1,y,word[coord.seq_num+1],coord.seq_num+1,0};
if (coord_set.find(next_coord) == coord_set.end()) {
coord_stk.push(next_coord);
coord_set.insert(next_coord);
}
break;
}
if (dir == 2
&& y < board[x].size()-1
&& board[x][y+1]==word[coord.seq_num+1]) {
coord.dir = 3;
coord_stk.push(coord);
coord_set.insert(coord);
Coord next_coord={x,y+1,word[coord.seq_num+1],coord.seq_num+1,0};
if (coord_set.find(next_coord) == coord_set.end()) {
coord_stk.push(next_coord);
coord_set.insert(next_coord);
}
break;
}
if (dir == 3
&& x < board.size()-1
&& board[x+1][y]==word[coord.seq_num+1]) {
coord.dir = 4;
coord_stk.push(coord);
coord_set.insert(coord);
Coord next_coord={x+1,y,word[coord.seq_num+1],coord.seq_num+1,0};
if (coord_set.find(next_coord) == coord_set.end()) {
coord_stk.push(next_coord);
coord_set.insert(next_coord);
}
break;
}
}
}
}
}
}
return false;
}
};
54 TODO next permutation
func nextPermutation(nums []int) {
}
55 TODO 4sum
func fourSum(nums []int, target int) [][]int {
}
56 TODO 3sum closest
func threeSumClosest(nums []int, target int) int {
}
57 TODO 3sum
func threeSum(nums []int) [][]int {
}
58 DONE Image Smoother
- State "DONE" from "STARTED" [2017-09-20 Wed 10:27]
func imageSmoother(M [][]int) [][]int {
m := len(M)
n := len(M[0])
if m == 0 || n == 0 {
return [][]int{}
}
dirs := [][]int{
[]int{0, 1}, []int{0, -1}, []int{1, 0}, []int{-1, 0},
[]int{-1, -1}, []int{1, 1}, []int{-1, 1}, []int{1, -1}}
sM := make([][]int, m)
for i := 0; i < m; i += 1 {
ar := make([]int, n)
for j := 0; j < n; j += 1 {
sum := M[i][j]
cnt := 1
for k := 0; k < len(dirs); k += 1 {
x := i + dirs[k][0]
y := j + dirs[k][1]
if x < 0 || x > m-1 || y < 0 || y > n-1 {
continue
}
sum += M[x][y]
cnt++
}
ar[j] = sum / cnt
}
sM[i] = ar
}
return sM
}
59 DONE Longest Continuous Increasing Subsequence
- State "DONE" from [2017-09-20 Wed 22:35]
func findLengthOfLCIS(nums []int) int {
if len(nums) < 1 {
return 0
}
var length, sub_length int
pre_num := nums[0]
for _, num := range nums {
if num > pre_num {
sub_length += 1
} else {
if sub_length > length {
length = sub_length
}
sub_length = 1
}
pre_num = num
}
if sub_length > length {
length = sub_length
}
return length
}
60 DONE Non-decreasing Array
- State "DONE" from "STARTED" [2017-09-21 Thu 09:50]
func checkPossibility(nums []int) bool {
var cnt int
for i := 0; i < len(nums)-1; i += 1 {
if nums[i] > nums[i+1] {
if i == 0 || nums[i-1] <= nums[i+1] {
nums[i] = nums[i+1]
} else {
nums[i+1] = nums[i]
}
cnt += 1
}
if cnt > 1 {
return false
}
}
return true
}
61 Find All Duplicates in an Array
func findDuplicates(nums []int) []int {
marks := make([]int, len(nums))
for _, num := range nums {
marks[num-1] += 1
}
dups_nums := make([]int, 0)
for index, mark := range marks {
if mark > 1 {
dups_nums = append(dups_nums, index+1)
}
}
return dups_nums
}
62 TODO Beautiful Arrangement
func countArrangement(N int) int {
}
63 DONE Beautiful Arrangement II
- State "DONE" from "TODO" [2018-03-09 Fri 23:05]
func constructArray(n int, k int) []int {
arr := make([]int, 0)
l, h := 1, 1+k
for {
arr = append(arr, l)
arr = append(arr, h)
l += 1
h -= 1
if l == h {
arr = append(arr, l)
break
}
if l > h {
break
}
}
for i := k + 2; i <= n; i += 1 {
arr = append(arr, i)
}
return arr
}
package main
func main() {
fmt.Println(constructArray(10, 1))
fmt.Println(constructArray(10, 3))
fmt.Println(constructArray(10, 5))
fmt.Println(constructArray(10, 7))
fmt.Println(constructArray(10, 9))
}
64 TODO Degree of an Array
func findShortestSubArray(nums []int) int {
}
65 DONE Toeplitz Matrix
- State "DONE" from "TODO" [2018-03-07 Wed 22:36]
func isToeplitzMatrix(matrix [][]int) bool {
if len(matrix) < 2 {
return true
}
r_num := len(matrix)
c_num := len(matrix[0])
r_index := r_num - 1
c_index := 0
for {
if r_index == 0 && c_index == c_num {
break
}
rd_index := r_index + 1
cd_index := c_index + 1
num := matrix[r_index][c_index]
for {
if rd_index == r_num || cd_index == c_num {
break
}
if matrix[rd_index][cd_index] != num {
return false
}
rd_index += 1
cd_index += 1
}
if r_index > 0 {
r_index -= 1
} else {
c_index += 1
}
}
return true
}
66 DONE Insert Delete GetRandom O(1) - Duplicates allowed
- State "DONE" from "TODO" [2018-03-26 Mon 18:07]
package main
import (
"fmt"
"math/rand"
)
type RcPair struct {
Val int
MIndex int
}
type RandomizedCollection struct {
Nums []RcPair
NumM map[int][]int
}
/** Initialize your data structure here. */
func Constructor() RandomizedCollection {
return RandomizedCollection{
Nums: make([]RcPair, 0),
NumM: make(map[int][]int),
}
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
func (this *RandomizedCollection) Insert(val int) bool {
iArr, bExist := this.NumM[val]
if !bExist {
iArr = make([]int, 0)
}
rcPair := RcPair{
Val: val,
MIndex: len(iArr),
}
this.Nums = append(this.Nums, rcPair)
iArr = append(iArr, len(this.Nums)-1)
this.NumM[val] = iArr
return !bExist
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
func (this *RandomizedCollection) Remove(val int) bool {
if iArr, bExist := this.NumM[val]; bExist {
last_p := this.Nums[len(this.Nums)-1]
this.Nums[iArr[len(iArr)-1]] = last_p
this.NumM[last_p.Val][last_p.MIndex] = iArr[len(iArr)-1]
iArr = iArr[:len(iArr)-1]
this.Nums = this.Nums[:len(this.Nums)-1]
if len(iArr) == 0 {
delete(this.NumM, val)
} else {
this.NumM[val] = iArr
}
return true
} else {
return false
}
}
/** Get a random element from the collection. */
func (this *RandomizedCollection) GetRandom() int {
return this.Nums[rand.Intn(len(this.Nums))].Val
}
func (this *RandomizedCollection) Debug() {
fmt.Println(this.Nums)
fmt.Println(this.NumM)
}
func main() {
rc := Constructor()
rc.Insert(4)
rc.Insert(3)
rc.Insert(4)
rc.Insert(2)
rc.Insert(4)
rc.Debug()
rc.Remove(4)
rc.Debug()
rc.Remove(4)
rc.Remove(4)
rc.Debug()
}
67 DONE 第一个缺失的正数
- State "DONE" from "TODO" [2018-04-07 Sat 22:41]
func firstMissingPositive(nums []int) int {
length := len(nums)
for i := 0; i < length; i += 1 {
p := nums[i]
for p > 0 && p <= length && nums[p-1] != p {
x := nums[p-1]
nums[p-1] = p
p = x
}
}
for i := 0; i < length; i += 1 {
if nums[i] != i+1 {
return i + 1
}
}
return length + 1
}
Last Updated 2018-04-25 Wed 22:16.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK