package main /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * longest common substring * @param str1 string字符串 the string * @param str2 string字符串 the string * @return string字符串 */ //方法1:暴力法；每个字符串的位置进行匹配；计算出最长的情况；O(m*n!);m是较长的；n是较短的字符串；两个字符串中的任意两个位置进行匹配 //暴力法存在重复计算的问题； //优化方法2:利用动态规划；计算出已经计算过的...

package main /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cost int整型一维数组 * @return int整型 */ func minCostClimbingStairs(cost []int) int { // write code here //采用动态规划：自下而上的方式计算值 //计算爬上最上面的成本 n := len(cost) if n == 1 { return cost[0] } if n == 2 { if cost[0] < cost[1] {...

package main /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param number int整型 * @return int整型 */ // 本质就是一个斐波那契数列;初始值不同 func jumpFloor(number int) int { // write code here if number == 1 { return 1 } if number == 2 { return 2 } //采用O(1)空间复杂度的做法 var ( a = 1 b = 2 c = 0 )...

package main /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ func recursion(i int, dp []int) int { if i == 1 || i == 2 { return 1 } if dp[i] != 0 { return dp[i] } t1 := recursion(i-1, dp) t2 := recursion(i-2, dp) dp[i] = t1 + t2 return dp[i] } ...

package main /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 递增路径的最大长度 * @param matrix int整型二维数组 描述矩阵的每个数 * @return int整型 */ //方法1：暴力法。m*n个元素 -> m*n个元素；判断每条路径是否递增； -》递增的情况下是否是最长（长度是多少） //方法2:采用dfs的方法回溯；从每个元素出发；可以抵达的最长路径是啥？长度是？ //方法3:在方法2的层面上进行优化；剔除调那些已经访问过的；不再访问的->动态规划记录当前位置的最优解；然后和当前位置...

package main /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param num int整型一维数组 * @return int整型二维数组 */ import "sort" func backtrack(res *[][]int, tmp []int, visitedFlag *map[int]map[int]bool, curSeqVisted []bool, num []int) { if len(tmp) == len(num) { ts := make([]int, len(tm...

package main /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param a int整型一维数组 * @param n int整型 * @param K int整型 * @return int整型 */ func findKth(a []int, n int, K int) int { // write code here return a[findKthMaxIndex(a, 0, n-1, K-1)] } //数组按照从大到小进行排序 func partitionInverse(nums []int, ...

package main /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param input int整型一维数组 * @param k int整型 * @return int整型一维数组 */ //堆排序； -》k大的堆 // 实现一个int的heap /* type IntHeap []int func (h IntHeap) Len() int { return len(h) } func (h IntHeap) Less(i, j int) bool { return h[i] > h[j...

//利用golang中collector的包装的heap的push和pop算法 package main /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param input int整型一维数组 * @param k int整型 * @return int整型一维数组 */ import ( "container/heap" ) // 实现一个int的heap type IntHeap []int func (h IntHeap) Len() int { return len(h)...

package main // 采用双栈法记录到当前元素为栈顶的时候，最小的元素是哪个 var stack []int = []int{} var minStack []int = []int{} //记录1中每个元素为栈顶的时候最小值分别是 func Push(node int) { // write code here stack = append(stack, node) if len(minStack) == 0 || minStack[len(minStack)-1] > node { minStack = append(minStack, node) } els...

package main import . "nc_tools" /* * type ListNode struct{ * Val int * Next *ListNode * } */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ func reverseList(h *ListNode) *ListNode { var res *ListN...

package main import . "nc_tools" /* * type ListNode struct{ * Val int * Next *ListNode * } */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead ListNode类 * @param k int整型 * @return ListNode类 */ func FindKthToTail(pHead *ListNode, k int) *ListNode { // write ...

// 两种方法；一种O(n)空间复杂度；记录每个节点是否被遍历过 // 另外一种；快慢指针; 存在环的话快慢指针一定会在环中相遇；相遇之后从这个点和开始节点出发；一次一步一定会在入口处相遇 func EntryNodeOfLoop(pHead *ListNode) *ListNode { if pHead == nil || pHead.Next == nil { return nil //空节点或者单个节点不存在环 } slow, fast := pHead, pHead for fast != nil { slow = slow.Next fast = fast.Nex...

package main /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型 */ //O(n)时间复杂度找开始变小的那个； O(logn)时间复杂度，递增有序序列。查找；找到目标值 //并归排序和二分查找很相似？ //O(n)空间复杂度 + O(nlogn)的时间复杂度； -> 并归排序 -> 递归? 循环？ //递归比循环好写 // func InversePairs(nums []int) int { // write code here ...