《剑指 Offer Go语言题解整理 》

HDU Let's go to play

Let's go to play Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other) Total Submission(s) : 773 Accepted Submission(s) : 213 Font: Times New Roman | Verdana | Georgia Font Size: ← → Problem Description Mr.Lin would like to hold a party and invite his friends to this party. He has n friends and each of them can come in a sp...阅读全文

最长重复字符串题解 golang

最长重复字符串题解 package main import ( "fmt" "strings" ) type Index map[int]int type Counter map[string]Index var c = make(Counter) func setRecord(match string, index int) { i, ok := c[match] if !ok { i = make(Index) c[match] = i return } i[index]++ } func filterOverlap() { var keys []string for k := range c { keys = append(keys, k) } for _, xkey := range...阅读全文

leetcode_1033

Golang: 思路：直接把我的题解搬上来吧 对abc进行排序，假定排完序后abc依次递增 条件1：b-a=c-b=1时，最小移动步数为0 条件2：不满足条件1， 那么看下b-a或者c-b有没有小于等于2的，有，那么最小移动步数为1 条件3：不满足条件1 2，那么最小移动步数为2 最大移动步数： 注意，这里是我不太理解的。我觉得以我对题意的理解，这题最大步数不是这么算的，比如 a=0,b=4,c=14 我可以先将a移动到7的位置，移动次数为7，移动后，位置变成[4,7,14] 再将4移动到10，移动次数为6，移动后，位置变成[7,10,14] 我认为这样的移动是符合题目给的条件的，但我此时就已经移动了13次了，而0 4 14的答案是12 题目想要我们求的最大移动步数，实际上是，max(a,b...阅读全文

HDOJ 3715 - Go Deeper 二分+2-sat判断

题意: 有这么一个过程: go(int dep, int n, int m) begin output the value of dep. if dep < m and x[a[dep]] + x[b[dep]] != c[dep] then go(dep + 1, n, m) end 其中x[]的值为0或1...c[]的值为0或1或2....现在告诉a[],b[],c[]..问这个过程最深可能是多少？ 题解 看这个过程..实际上当在m层没办法下去了.更深的层肯定也到不了了...所以满足单调性...先读入a[],b[],c[]...再二分M...构图..2-sat..tarjan判断.... Program: #include #include #inc...阅读全文

两数之和

题目描述 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 解题思路 使用hash表存储目标值与数组元素之差（key）和该数组元素的索引（value），当剩余的素组中有元素是hash表中的，则找到了一组符合题目要求的解。 具体思路 1、开始循环给定数组nums，获得其中元素的索引index、值num； 2、在Hash表中查找是否有值为num的key，若有则找到题解，若没...阅读全文

golang刷LeetCode[0002] 两数相加

题目 https://github.com/betterfor/leetcode-go/tree/master/algorithms/0002_Two_Add 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 实例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807 题解 思路 主要考的是链表这种数据结构的理解，以及链表长度不等时怎么合并链表问题。 /** * Definition for sing...阅读全文

golang刷LeetCode[0005] 最长回文子串

题目 给定一个字符串 s，找到 s 中最长的回文子串。你可以假定 s 的最大长度为1000. 示例1： 输入： babad 输出：bab 注意：aba也是有效答案 示例2： 输入：cbbd 输出：bb 题解 1、暴力法 func longestPalindrome(s string) string { var maxLen int var maxStr string for i := 0; i < len(s); i++ { for j := i + 1; j < len(s)+1; j++ { len := isPalindrome(s[i:j]) if len > maxLen { maxStr = s[i:j] maxLen = len } } } return maxStr } fu...阅读全文

面试：删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。 注意：此题对比原题有改动 示例 1: 输入: head = [4,5,1,9], val = 5输出: [4,1,9]解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.示例 2: 输入: head = [4,5,1,9], val = 1输出: [4,5,9]解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9. 说明： 题目保证链表中节点的值互不相同若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点 这题的难度定义为简单，但我觉得如果对于链表题目并不熟练的...阅读全文

golang刷LeetCode[0001] 两数之和

题目描述 给定一个整数数组 nums 和一个目标值 target ，请你在该数组中找出和未目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一种答案。但是，你不能重复利用这个数组中同样的元素。 示例： 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0，1] 题解 第一种方法 func twoSum(nums []int, target int) []int { for i := 0; i < len(nums); i++ { for j := i + 1; j < len(nums); j++ { if nums[i] + nums[j] == target { r...阅读全文

leetcode_1029

Golang: 思路：还是照抄我的题解。 这题题意很明显是贪心了，那么以什么作为尺度呢？ 毫无疑问的，应该是一个人去A点和去B点的花费之差 简单来说，我们看[1,1000]，那么这个人应该去A点，因为会便宜999元 再来看[10,20],[1,1000],那么第二个人应该去A点，第一个人去B点。因为第一个人去A去B最多便宜10元，第二个人去A去B则可能便宜999元，这就是贪心在这一题的尺度了。 代码如下： type intS [][]int func (s intS) Len() int { return len(s) } func (s intS) Less(i, j int) bool { return s[i][2] > s[j][2] } func (s intS) Swap(i, ...阅读全文

golang刷LeetCode[0006]Z字形变换

题目 将一个给定的字符串根据给定的行数，以从上到下、从左到右进行 Z 字形排序。 比如输入字符串为 “LEETCODEISHIRING” 行数为3，排列如下： L C I R E T O E S I I G E D H N 之后，需要从左到右逐行读取，结果为 “LCIRETOESIIGEDHN” 示例1： 输入：s = "LEETCODEISHIRING", numRows = 3 输出: "LCIRETOESIIGEDHN" 示例2： 输入: s = "LEETCODEISHIRING", numRows = 4 输出: "LDREOEIIECIHNTSG" 解释: L D R E O E I I E C I H N T S G 题解 1、找规律 Z 字形很容易找到规律，假如 numRow...阅读全文

leetcode_208

Golang: 思路：这题是为了解决720题所预先做的准备，前缀树这个结构，大家去看看leetcode在这题的官方题解就知道了 代码如下： type Trie struct { ending bool next [26]*Trie } /** Initialize your data structure here. */ func Constructor() Trie { return Trie{} } /** Inserts a word into the trie. */ func (this *Trie) Insert(word string) { temp:=this for _,v:=range word { nxt:=v-'a' if temp.next[nxt]==nil { ...阅读全文

leetcode_355

Golang: 思路：设计推特，搬运我的题解 这里的代码依旧有着很大优化的空间，比如按时间排序上，可以维护一个堆；对于每一个用户，我们可以只保存他/她的最近十条推特 但是不太想写了，因为比较麻烦。。。 globalId：类似timestamp时间标记 follower：记录每个用户关注的用户列表 checkFollowed表示关注关系，用户A是否关注了用户B，key为“id id”的形式，应该是可以保证唯一性的 twitter存储每个用户发过的推，但是value存的是globalId，方便以后取出来 findtwitter存储的是所有用户发的推 注意，这套代码是不满足并行与分布式的要求的。。。 代码如下： type Twitter struct { globalId int follower...阅读全文

leetcode_394

Golang: 思路：搬我的题解过来了 第一次没有看到类似"[[]]"的嵌套结构，因此写了一版只含一层的"[]"的字符串解析 于是后面看到了双层"[]"的嵌套结构后，想到了递归实现，同时想到了栈 但这里不需要栈，只需要记录与"["符号相对应的"]"出现的位置即可 于是就有了下面的这种解法 代码如下： func decodeString(s string) string { var res strings.Builder for i:=0;i'9'{ res.WriteByte(s[i]) }else{ j:=i+1 for j阅读全文

leetcode_78

Golang: 思路：递归加回溯，emmm，就是在选择第n个时，可以选择nums[n]，也可以选择空（即不填入），惭愧，这题是看了题解才理解的，太菜了。 代码如下： func subsets(nums []int) [][]int { var res [][]int if len(nums)==0 { return res } var temp []int getSubsets(&res,nums,&temp,0) return res } func getSubsets(res *[][]int,nums []int,temp *[]int,n int){ if n==len(nums) { cop:=make([]int,len(*temp)) copy(cop,*temp) *res=...阅读全文

leetcode120

Golang: 思路：这题是基础DP，想一想就出来了，但是槽点满满，题目对于相邻这个定义的解释太扯淡了。搬我的题解过来吧。 初始： [2], [3,4], [6,5,7] 第一轮过后：3+2=5，4+2=6 [2], [5,6], [6,5,7] 第二轮过后：6+5=11，[5+5=10,5+6=11,取小值10]，7+6=13 [2], [5,6], [11,10,13] 代码如下： func minimumTotal(triangle [][]int) int { if len(triangle)==1 { return triangle[0][0] } for i:=1; i阅读全文

leetcode_86

Golang: 思路：搬运我的题解 这题在第一次做的时候嫌麻烦，直接用数组解决了，时间百分百，空间百分之五，还是有些不满意的，就用双指针重新写了下，然后来到了双百效率 思路在代码里有提及，就不再详述了，简单说一下这里替换的含义 1->4->3->2->5->2, x = 3 发生替换的时候 p1 p2 p3 1->4->3->2->5->2 这里怎么替换，就是： 先从原链表里提取出p3， 然后将p3插到p1及p1后面的元素之间， 更新p1，更新p3 代码如下： func partition(head *ListNode, x int) *ListNode { if head==nil||head.Next==nil { return head } //什么时候需要替换呢？ //当我找到某个元...阅读全文