main.go - master - netmann/test-leetcode

main.go
431 строка13 KB
Alexxtn105
Buy and sell
07 окт 2024, 23:19
07 окт 2024, 23:1903388ed
package main

import (
	"fmt"
	"sort"
)

func main() {
	taskNumber := 189
	runTask(taskNumber)
}

func runTask(taskNumber int) {
	switch taskNumber {
	case 26:
		nums := []int{1, 1, 2}
		removeDuplicates(nums)
		nums = []int{1, 2}
		removeDuplicates(nums)
		nums = []int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}
		removeDuplicates(nums)
		nums = []int{}
		removeDuplicates(nums)
		nums = []int{1}
		removeDuplicates(nums)
	case 27:
		nums := []int{3, 2, 2, 3}
		val := 3
		removeElement(nums, val)
	case 80:
		nums := []int{1, 1, 1, 2, 2, 3} //Output: 5, nums = [1,1,2,2,3,_]
		removeDuplicates2(nums)

		nums = []int{0, 0, 1, 1, 1, 1, 2, 3, 3} //Output: 7, nums = [0,0,1,1,2,3,3,_,_]
		removeDuplicates2(nums)

		//nums = []int{1, 2}
		//removeDuplicates2(nums)
		//
		//nums = []int{1}
		//removeDuplicates2(nums)

		nums = []int{}
		removeDuplicates(nums)
	case 88:
		nums1 := []int{1, 2, 3, 0, 0, 0}
		m := 3
		nums2 := []int{2, 5, 6}
		n := 3
		merge(nums1, m, nums2, n)
		nums1 = []int{1}
		m = 1
		nums2 = []int{}
		n = 0
		merge(nums1, m, nums2, n)
		nums1 = []int{0}
		m = 0
		nums2 = []int{1}
		n = 1
		merge(nums1, m, nums2, n)
	case 121:
		prices := []int{7, 1, 5, 3, 6, 4}
		fmt.Println(maxProfit(prices)) //Output 5

		prices = []int{7, 6, 4, 3, 1}
		fmt.Println(maxProfit(prices)) //Output 0

	case 169:
		nums := []int{3, 2, 3}
		fmt.Println(majorityElement(nums))
		nums = []int{1, 2, 1, 3, 1, 4, 1, 5}
		fmt.Println(majorityElement(nums))
	case 189:
		nums := []int{1, 2, 3, 4, 5, 6, 7} //Output: [5,6,7,1,2,3,4]
		k := 3
		rotate(nums, k)
		nums = []int{-1, -100, 3, 99} //Output: [3,99,-1,-100]
		k = 2
		rotate(nums, 2)
	default:
		fmt.Println("Select existing task number!")
	}
}

//region Task 122. Best Time to Buy and Sell Stock II
/*
122. Best Time to Buy and Sell Stock II
Medium
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
*/

//endregion
//region Task 121. Best Time to Buy and Sell Stock
/*
121. Best Time to Buy and Sell Stock
Easy
Topics
Companies
You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.



Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
*/
func maxProfit(prices []int) int {
	minPrice := prices[0]

	maxProfit := 0

	//бежим по всем ценам
	for _, price := range prices {
		//если текущая цена меньше минимальной, обновляем
		if price < minPrice {
			minPrice = price //новая минимальная цена

			//иначе считаем профит - текущая цена минус минимальная, если текущий профит больше имеющегося, обновляем
		} else if profit := price - minPrice; profit > maxProfit {
			maxProfit = profit
		}
	}
	return maxProfit

}

//endregion
//region Task 189. Rotate Array
/*
189. Rotate Array
Medium
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.


Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
*/

func rotate(nums []int, k int) {
	//берем длину массива
	n := len(nums)
	//чтобы k не выходил за пределы
	k %= n
	//переворачиваем весь
	reverse(nums, 0, n-1)
	//переворачиваем k элементов
	reverse(nums, 0, k-1)
	//переворачиваем от k до конца
	reverse(nums, k, n-1)
	//выводим
	fmt.Println(nums)
}

// реверс элементов массива
func reverse(nums []int, start int, end int) {
	for start < end {
		nums[start], nums[end] = nums[end], nums[start]
		start++
		end--
	}
}

//endregion
//region Task 169. Majority Element
/*
Easy

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3
Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109


Follow-up: Could you solve the problem in linear time and in O(1) space?
------------------------------------------------------------------------

Решение  (https://habr.com/ru/articles/167177/):
Алгоритм Бойера-Мура — тех самых Бойера и Мура, что придумали намного более известный алгоритм поиска подстроки — проще всего представить следующим образом: на вечеринке собрались N людей, и на каждом по одному элементу из массива. Когда встречаются двое, у которых элементы разные, они присаживаются это обсудить. В конце концов останутся стоять только люди с одинаковыми элементами; очевидно, это тот самый элемент, который встречался больше N/2 раз.
*/
func majorityElement(nums []int) int {
	confidence := 0 // количество людей, не нашедших пары и оставшихся стоять
	candidate := 0  // последний человек, не нашедший пару - возможно, его элемент встречается чаще всего

	// проходим по массиву и усаживаем пары с разными элементами
	for i := 0; i < len(nums); i++ {
		// если до сих пор все сидят, то следующему пока придётся постоять
		if confidence == 0 {
			candidate = nums[i]
			confidence++
		} else if candidate == nums[i] {
			confidence++
		} else {
			confidence--
		}
	}
	//if confidence>0 {
	//	return candidate
	//}	else {
	//	return nil
	//}
	return candidate

	//вариант с мапой
	//cnt:=0
	//myMap := make(map[int]int)
	//for i := 0; i < len(nums); i++ {
	//	myMap[nums[i]]++
	//}
	//
	////ищем максимум
	//if len(myMap) == 1 {
	//	return nums[0]
	//}
	//
	//myMax := myMap[0]
	//for val, cnt := range myMap {
	//	if cnt > myMax {
	//		myMax = cnt
	//	}
	//}
	//
	//fmt.Println(myMap)
	//fmt.Println(cnt)
	//return cnt
}

//endregion
//region Task 26. Remove Duplicates from Sorted Array
/*
Easy
https://leetcode.com/problems/remove-duplicates-from-sorted-array/?envType=study-plan-v2&envId=top-interview-150
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.
*/

func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		//fmt.Println(0)
		//fmt.Println(nums)
		return 0
	}

	k := 1
	for i := 0; i < len(nums)-1; i++ {
		if nums[i] != nums[i+1] {
			nums[k] = nums[i+1]
			k++
		}
	}

	//fmt.Println(k)
	//fmt.Println(nums)
	return k
}

//endregion
// region Task 27. Remove Element
/*
Easy
https://leetcode.com/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to valbek, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.

Учитывая целочисленный массив nums и целое значение val, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в nums, которые не равны val.

Учтите, что количество элементов в nums, которые не равны val, равно k, чтобы их приняли, вам нужно выполнить следующие действия:

Измените массив nums таким образом, чтобы первые k элементов в nums содержали элементы, которые не равны val. Остальные элементы nums не важны, так же как и размер nums.
Верните k.
*/
func removeElement(nums []int, val int) int {

	//[3,2,2,3]
	//3
	k := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] != val {
			//просто свапаем местами
			nums[k], nums[i] = nums[i], nums[k]
			k++
		}
	}

	return k
}

//endregion
// region Task 80. Remove Duplicates from Sorted Array II
/*
Medium
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/?envType=study-plan-v2&envId=top-interview-150

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
*/
func removeDuplicates2(nums []int) int {
	k := 1
	povtorCnt := 0
	for i := 0; i < len(nums)-1; i++ {
		if nums[i] == nums[i+1] {
			if povtorCnt == 0 {
				nums[k] = nums[i+1]
				k++
			}
			povtorCnt++

		} else if nums[i] != nums[i+1] {
			nums[k] = nums[i+1]
			povtorCnt = 0
			k++
		}
	}

	fmt.Println(k)
	fmt.Println(nums)
	return k
}

//endregion
//region Task 88. Merge Sorted Array
/*
Easy
https://leetcode.com/problems/merge-sorted-array/submissions/?envType=study-plan-v2&envId=top-interview-150

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
*/
// task_88_merge Challenge 88
func merge(nums1 []int, m int, nums2 []int, n int) {

	//region вариант 1
	for i := 0; i < n; i++ {
		nums1[m+i] = nums2[i]
	}
	sort.Ints(nums1)
	//endregion

	//region Вариант 2
	////создаем слайс с хвостиком массива 1
	//e := nums1[m : m+n]
	//
	////заполняем полученный слайс величинами второго массива
	//for i, v := range nums2 {
	//	e[i] = v
	//}
	//
	////сортируем базовый массив
	//sort.Ints(nums1)
	//endregion

	fmt.Println(nums1)
}

//endregion