1.求两数之和（数组无序）
//方法一：暴力破解 时间o(n^2) 空间o(1)
func TwoNumSum1(nums []int, target int) []int {
for i := 0; i < len(nums)-1; i++ {
for j := i + 1; j < len(nums); j++ {
if nums[i]+nums[j] == target {
return []int{i, j}
}
}
}
return nil
}
//方法二：空间换时间 时间o(n) 空间o(n)
func TwoNumSum2(nums []int, target int) []int {
result := make([]int, 0)
realIndex := make(map[int]int)
for i, v := range nums {
if valueIndex, ok := realIndex[target-v]; ok {
return append(result, valueIndex, i)
} else {
realIndex[v] = i
}
}
return result
}
2.求电话号码的字母组合
func letterCombinations(digits string) []string {
m:=make(map[byte][]string)
m['2']=[]string{"a","b","c"}
m['3']=[]string{"d","e","f"}
m['4']=[]string{"g","h","i"}
m['5']=[]string{"j","k","l"}
m['6']=[]string{"m","n","o"}
m['7']=[]string{"p","q","r","s"}
m['8']=[]string{"t","u","v"}
m['9']=[]string{"w","x","y","z"}
var ret []string
for i:=0;i<len(digits);i++{
ret=getCombination(ret,m[digits[i]])
}
return ret
}
func getCombination(a,b []string)[]string{
if len(a)==0{
return b
}
if len(b)==0{
return a
}
var ret []string
for _,v:=range a{
for _,bv:=range b {
ret=append(ret,v+bv)
}
}
return ret
}
3.三数之和
func ThreeNumsTwo(nums []int) [][]int {
if len(nums) < 3 {
return nil
}
sort.Ints(nums)
fmt.Println(nums)
flag := false
for _, v := range nums {
if v != 0 {
flag = true
}
}
//全0的情况
if !flag {
return [][]int{{0, 0, 0}}
}
result := make([][]int, 0)
L := 0
R := len(nums) - 1
for i, v := range nums {
//当前这个元素都大于0了，后面的元素加起来不可能等于0
if nums[i] > 0 {
return result
}
// 去除重复的元素排序后相邻
if i > 0 && nums[i] == nums[i-1] {
continue
}
//每次进入重置指针
L = i + 1
R = len(nums) - 1
for L < R {
if 0 == nums[L]+nums[R]+v {
result = append(result, []int{v, nums[L], nums[R]})
//第二个元素重复的情况
for L < R && nums[L] == nums[L+1] {
L++
}
//第三个元素重复的情况
for L < R && nums[R] == nums[R-1] {
R--
}
L++
R--
} else if nums[L]+nums[R]+v < 0 {
L++
} else {
R--
}
}
}
return result
}
4.两数之和（链表）
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
head := &ListNode{
Val: 0,
}
curr := head
nextAdd := 0
for l1 != nil || l2 != nil {
x, y := 0, 0
if l1 != nil {
x = l1.Val
}
if l2 != nil {
y = l2.Val
}
sum := x + y + nextAdd
if nextAdd > 0 {
nextAdd = 0
}
val := sum % 10
nextAdd = sum / 10
node := &ListNode{
Val: val,
}
if l1 != nil {
l1 = l1.Next
}
if l2 != nil {
l2 = l2.Next
}
curr.Next = node
curr = node
}
if nextAdd != 0 {
node := &ListNode{
Val: nextAdd,
}
curr.Next = node
curr = node
}
return head.Next
}
5.合并有序数组
func merge(nums1 []int, m int, nums2 []int, n int) {
//先拼接
for i:= range nums2{
nums1[i+m]=nums2[i]
}
//再排序（冒泡）
for i:=0;i<len(nums1);i++{
for j:=i+1;j<len(nums1);j++{
if nums1[i]>nums1[j]{
temp:=nums1[i]
nums1[i]=nums1[j]
nums1[j]=temp
}
}
}
//或者直接排序 sort.Ints(nums1)
}
6.移除指定元素
更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
func removeElement(nums []int, val int) int {
k:=0
for i:=range nums{
if nums[i]!=val{//不相等，说明这个元素需要保存下来
nums[k]=nums[i]
k++
}
}
return k
}
7.删除有序数组中的重复项
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
func removeDuplicates(nums []int) int {
count:=1 //从第二个元素开始替换
for i:=0;i<len(nums)-1;i++{
//碰到不相等的情况，说明不重复元素多了一个
if nums[i]!=nums[i+1]{
nums[count]=nums[i+1];//将后面的元素覆盖数组的位置
count++ //移动到下一个位置
}
}
return count
}
8.买卖股票的最佳时机
func maxProfit(prices []int) int {
if len(prices)==0{
return 0
}
min:=math.MaxInt
max:=0
for i:=0;i<len(prices);i++{
if prices[i]<min{
min=prices[i] //记录买入最小值
}
//假设我现在卖出，获取的利润是不是最大，是就替换max
if prices[i]-min>max{
max=prices[i]-min
}
}
return int(max)
}
9.验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
func isPalindrome(s string) bool {
str1 := ""
for _, v := range s {
if (v >= 'A' && v <= 'Z') || (v >= 'a' && v <= 'z') || (v >= '0' && v <= '9') {
str1 += string(v)
}
}
r := strings.ToLower(str1)
ll := len(r)
for i := 0; i < ll/2; i++ {
if r[i] != r[ll-i-1] {
return false
}
}
return true
}
10.多数元素（众数）
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
func majorityElement(nums []int) int {
if len(nums)==0{
return 0
}
cd:=nums[0] //众数
count:=1 //次数
for i:=1;i<len(nums);i++{
//如果和当前众数相等，则+1
if nums[i]==cd{
count++
}else {
count-- //否则-1
}
//当count=0时，换一个众数
if (count<=0){
cd=nums[i]
count=1
}
}
return cd
}
