package main

import "fmt"

func rotate(nums []int, k int) {

k %= len(nums)

nums = append(nums[len(nums)-k:], nums[:len(nums)-k]...)

fmt.Println(nums)

}

func rotate2(nums []int, k int) {

k %= len(nums)

reverse(nums[:len(nums)-k])

reverse(nums[len(nums)-k:])

reverse(nums)

fmt.Println(nums)

}

func reverse(nums []int) {

i,j := 0,len(nums)-1

for i < j{

nums[i], nums[j] = nums[j], nums[i]

i++

j--

}

}

func main() {

nums := []int{1,2,3,4,5,6,7}

rotate(nums, 5)

nums = []int{1,2,3,4,5,6,7}

rotate2(nums, 5)

}

`栈是一种特殊的线性表，具有和线性表的特点，同时也有特殊性：元素遵循“先进后出”的特点，也就是只能从栈顶插入或删除元素。同样可以用顺序存储和链式存储两种方式实现，分别称为顺序栈和链栈。栈结构可以用来实现表达式求值、括号匹配等。

栈的特点可以看成是一个桶，往桶里面装东西，取东西都是从上面进行的，最先放进去的要最后才能取出来`

`hash碰撞解决方式，拉链法 与开放定址法相比，拉链法有如下几个优点： ①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短； ②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况； ③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间； ④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。 （3）拉链法的缺点 　拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。`

package main

import "fmt"

func main() {

fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))

}

func twoSum(nums []int, target int) []int {

var result []int

maps := map[int]int{}

for index, num := range nums {

if _, ok := maps[target - num]; ok{

result = append(result, index, maps[target - num])

return result

}

maps[num] = index

}

return result

}

//给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

//

// 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

//

// 示例:

//

// 给定 nums = [2, 7, 11, 15], target = 9

//

//因为 nums[0] + nums[1] = 2 + 7 = 9

//所以返回 [0, 1]

//

// Related Topics 数组 哈希表

//leetcode submit region begin(Prohibit modification and deletion)

func twoSum(nums []int, target int) []int {

}

//leetcode submit region end(Prohibit modification and deletion)

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：

[-1, 0, 1],

[-1, -1, 2]

package main

import "fmt"

func main() {

fmt.Println(threeSum([]int{-1, 0, 1, 2, -1, -4}))

}

func threeSum(nums []int) [][]int {

if len(nums) < 3 { return [][]int{} }

QuickSort(nums) // 快排 O(n log n), 本地修改

ret := make([][]int, 0, 0)

for i := 0; i < len(nums) - 1; i++ {

l, r := i + 1, len(nums) - 1

if nums[i] > 0 || nums[i] + nums[l] > 0 { break } // 优化掉不可能的情况

if i > 0 && nums[i] == nums[i-1] { continue } // i 去重

for l < r {

if l > i + 1 && nums[l] == nums[l-1] { // l 去重

l++; continue

}

if r < len(nums) - 2 && nums[r] == nums[r+1] { // r 去重

r--; continue

}

if nums[i] + nums[l] + nums[r] > 0 { //

r--

} else if nums[i] + nums[l] + nums[r] < 0 {

l++

} else {

ret = append(ret, []int{nums[i], nums[l], nums[r]})

l++; r--

}

}

}

return ret

}

func QuickSort(array []int) {

if len(array) < 2 { return }

pivot := array[0]

l, r := 0, len(array) - 1

for i := 1; i <= r; {

if array[i] < pivot { //

array[l], array[i] = array[i], array[l]

l++; i++

} else {

array[r], array[i] = array[i], array[r]

r--

}

}

QuickSort(array[:l])

QuickSort(array[l + 1:])

}

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"

输出: true

示例 2:

输入: "()[]{}"

输出: true

示例 3:

输入: "(]"

输出: false

示例 4:

输入: "([)]"

输出: false

示例 5:

输入: "{[]}"

输出: true

package main

import "fmt"

func main() {

//s:= "({((())))"

s:= "(((())))"

isValid := isValid(s)

fmt.Println(isValid)

}

func isValid(s string) bool {

dict := map[byte]byte{'(':')','{':'}','[':']'}

var stack []byte

for _,v := range s{

if len(stack) > 0{

if byte(v) == dict[stack[len(stack)-1]]{

stack = stack[:len(stack)-1]

continue

}

}

stack = append(stack, byte(v))

fmt.Println(stack)

}

return len(stack)<1

}