目录
1.两数之和
/*
题目：两数之和
详细：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
*/
答案：
//解题思路：两层for循环，依次相加判断是否等于目标值,第二层for循环只循环列表后面的
func twoSum(li []int, val int) []int {
r := []int{}
for k, _ := range li {
for i := k + 1; i < len(li); i++ {
if li[k]+li[i] == val {
r = []int{k, i}
return r
}
}
}
return r
}
func main() {
li := []int{3, 2, 4}
target := 6
rLi := twoSum(li, target)
fmt.Println(rLi)
}
2.回文数
/*
题目：回文数
详细：给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
解题思路1：转成字符串，反转字符串对比
解题思路2:反转数字，121反转方法：1*10的2次方+2*10的1次方+1*10的0次方
示例 1：
输入：x = 121
输出：true
示例 2：
示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
*/
答案1：
/*
解题思路1：转成字符串，反转字符串对比
*/
func reverseString(str string) string {
strRune := []rune(str)
l := len(strRune)
for i := 0; i < l/2; i++ {
strRune[i], strRune[l-i-1] = strRune[l-i-1], strRune[i]
}
return string(strRune)
}
func isPalindrome(x int) bool {
str := strconv.Itoa(x)
if reverseString(str) == str {
return true
}
return false
}
func main() {
fmt.Println(isPalindrome(122))
}
答案2:
/*
解题思路2:反转数字，121反转方法：1*10的2次方+2*10的1次方+1*10的0次方
*/
func isPalindrome2(x int) bool {
if x < 0 {
return false
}
reverX := 0
lenX := len(strconv.Itoa(x))
for i := 0; i < lenX; i++ {
a := int(math.Pow(10, float64((lenX - 1 - i))))
b := (x / int(math.Pow(10, float64(i))) % 10)
reverX += b * a
}
if reverX == x {
return true
}
return false
}
3.罗马数字转整数
题目：罗马数字转整数
详细：例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX
答案
/*
解题思路：两种情况：
1.小的在大大右边 VI,5+1=6
2.小大在大的左边 IV,-1+5=4,IVD=-1+-5+500=494
for循环当前数字的正负号由下一个数字决定，下一个数字大于当前就是负号，否则就是正号
*/
func romanToInt(s string) int {
dic := map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
ans := 0
for k := range s {
value := dic[s[k]]
if k != len(s)-1 && value < dic[s[k+1]] {
ans -= value
} else {
ans += value
}
}
return ans
}
func main() {
s := "IVD"
fmt.Println(romanToInt(s))
}
4.最长公共前缀
/*
题目：最长公共前缀
详细：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
输入：strs = ["flower","flow","flight"]
输出："fl"
*/
答案1:
/*
解题思路：公共前缀，
1.取li的第0位，遍历第0位的每一位字符
2.把每一位字符跟li的其他字符串相同下标比较
*/
func longestCommonPrefix(li []string) string {
t := true
index := 0
for k, v := range li[0] {
for i := 1; i < len(li); i++ {
//第0位比第1位长，取值报错
if k > len(li[i])-1 {
t = false
break
}
if v == rune(li[i][k]) {
continue
} else {
t = false
break
}
}
if t {
index++
} else {
break
}
}
return li[0][:index]
}
func main() {
li := []string{"abcd", "ab", "ba"}
fmt.Println(longestCommonPrefix(li))
}
答案2：
/*
解题思路：公共前缀，
1.先默认为第0位为最大前缀
2.for循环依次把第0位的和后面所有的进行位置比较
3.找到最大重复字符串的下标索引，然后截取
*/
func longestCommonPrefix(strs []string) string {
lenStr := len(strs)
if lenStr == 0 {
return ""
}
pre := strs[0]
for i := 1; i < lenStr; i++ {
stri := strs[i]
//找到最短的字符串
minStr := ""
if len(stri) < len(pre) {
minStr = stri
} else {
minStr = pre
}
//找到最大重复前缀字符串的下表索引位置
index := 0
for k := range minStr {
if stri[k] == pre[k] {
index = k + 1
} else {
break
}
}
//最大重复前缀字符串截取
pre = pre[:index]
}
return pre
}
func main() {
li := []string{"abc", "abc", "abc"}
fmt.Println(longestCommonPrefix(li))
}
5.有效的括号
/*
题目：有效的括号
详细：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
*/
答案：
/*
解题思路：利用栈的思想，先进后出。
1.匹配到一个左括号就放进栈中
2.匹配到一个右括号把栈最后一个左括号出栈，需要判断栈的最后一个元素是否为他的左括号，不是就直接false
*/
func isValid(s string) bool {
dic := map[byte]byte{')': '(', ']': '[', '}': '{'}
str := []byte{}
for _, v := range s {
if dic[byte(v)] == 0 {
//左括号，进栈
str = append(str, byte(v))
} else {
//右括号，出栈
if len(str) == 0 || str[len(str)-1] != dic[byte(v)] {
//1.防止 ()),这种情况，掉单右括号,栈已经没有了
//2.防止({)}，这种情况，括号不匹配。当前的右括号，必须匹配栈最后的一个括号为左括号
return false
}
//出栈
str = str[:len(str)-1]
}
}
//防止(()，这种情况，栈里面还有值
return len(str) == 0
}
func main() {
s := "()"
fmt.Println(isValid(s))
}
6.最大同时在线人数
/*
题目：最大同时在线人数
详细：start，end 分别代表开始面试时间戳，结束面试时间戳。面试时间为[start,end]
计算最大在线人数以及持续的时间段。如果有多个时间段，返回其中一个即可
示例:[[100,200],[900,1000],[150,300]]
输出: 2,150,200
解释: 最大同时在线人数2 人，持续时间为[150,200]
*/
答案：
/*
算法原理：
1.轮训每一个人的开始时间是否在其他人的开始时间至结束时间段内。是则在线人数+1
2.取出最大的在线人数
3.最大人数开始时间段取：最大的开始时间
4.最大人数结束时间段：取最小的结束时间段。。。范围重合时间取值
*/
func demo(lis [][]int) []int {
maxCount := 0 //在线人数
reSta := 0 //初始化为0，开始时间
reEnd := 1000 //初始化为：最后一个人的结束时间
for k := range lis {
count := 1
st := lis[k][0]
en := lis[k][1]
sta := 0
end := 0
for i := 0; i < len(lis); i++ {
if i == k {
continue
}
if st <= lis[i][0] && en >= lis[i][0] {
count += 1
sta = lis[i][0]
if lis[i][1] >= en {
end = en
} else {
end = lis[i][1]
}
}
}
if count > maxCount {
maxCount = count
}
if sta > reSta {
reSta = sta
}
if end < reEnd && end != 0 {
reEnd = end
}
}
return []int{maxCount, reSta, reEnd}
}
func main() {
li := [][]int{{100, 200}, {150, 300}, {160, 190}}
fmt.Println(demo(li))
}
7.无重复字符的最长子串
/*
题目：无重复字符的最长子串
详细：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2：
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长
示例 3：
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
*/
答案：
/*
解题思路：
1.遍历一遍字符串，依次以每个字母开头。截取 s[index:]
2.字典取值，不存在则把值存进map中，存在则清空map
3.字典数量最多的就是无重复字符串
*/
func demo(s string) (count int, str string) {
dic := make(map[byte]byte)
st := []byte{}
for i := 0; i < len(s); i++ {
s2 := s[i:]
st2 := []byte{}
for k := range s2 {
_, ok := dic[s2[k]]
if ok {
dic = make(map[byte]byte) //清空map
st2 = []byte{}
break
} else {
dic[s2[k]] = s2[k]
st2 = append(st2, s2[k])
}
if len(st2) > len(st) {
st = st2
}
}
}
return len(st), string(st)
}
func main() {
a, b := demo("abcc")
fmt.Println(a)
fmt.Println(b)
}
8.链表删除倒数第n个节点
题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点
示例1:
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
答案：
/*
解题思路：
1.先进行正删
2.再计算链表的长度，进行正删。删除的位置=链表长度-倒删位置
*/
//倒删
func demo(head *ListNode, n int) (head2 *ListNode) {
h1 := head
h2 := head
le := 1
for {
if head.next != nil {
le++
head = head.next
} else {
break
}
}
k := le - n //倒删位置
for i := 0; i < le; i++ {
if k == 0 { //0位置特殊处理
h2 = h1.next
break
}
if i == k-1 { //删除位置
h1.next = h1.next.next
break
}
if h1.next != nil {
h1 = h1.next
}
}
return h2
}
func main() {
one := ListNode{data: 1}
two := ListNode{data: 2}
three := ListNode{data: 3}
four := ListNode{data: 4}
five := ListNode{data: 5}
one.next = &two
two.next = &three
three.next = &four
four.next = &five
head := &one
node := demo(head, 2) //倒删位置
for {
if node != nil {
fmt.Println(node.data)
node = node.next
} else {
break
}
}
}