企业官网建设流程全解析

1、数组中的最长连续子序列

给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）

Python

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # max increasing subsequence # @param arr int整型一维数组 the array # @return int整型 # class Solution: def MLS(self , arr: List[int]) -> int: # write code here r = 0 arr = set(arr) for num in arr: if num - 1 in arr: # 如果 num - 1 在数组中，那么 num 一定不是最长子序列的 head，所以跳过这个数 continue cur_num = num cur_len = 1 while cur_num + 1 in arr: cur_num += 1 cur_len += 1 r = max(r, cur_len) return r

Golang

使用 Go 的话，解题思路就不一样了，因为 Go 里边没有内置类似集合这种数据结构，进行处理之前最好是先排序再进行处理。

package main import ( "fmt" "sort" ) /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * max increasing subsequence * @param arr int整型一维数组 the array * @return int整型 */ func MLS(arr []int) int { // write code here if len(arr) == 0 { return 0 } sort.Ints(arr) max := 1 count := 1 for i := 1; i < len(arr); i++ { if arr[i] -1 == arr[i-1] { count++ max = maxs(max, count) }else if arr[i] == arr[i-1] { continue } else { count = 1 } } return max } func maxs(x, y int) int { if x > y { return x } return y } func main() { arr := []int{4, 3, 1, 5} max := MLS(arr) fmt.Println(max) }

2、最长无重复子数组

给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组。

Python

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param arr int整型一维数组 the array # @return int整型 # class Solution: def maxLength(self , arr: List[int]) -> int: # write code here maxlen = 0 stack = [] for num in arr: if num in stack: # 如果新的数在 stack 里边，那么将 num 及 num 之前的数都删除（确保 stack 是子数组且无重复元素） stack = stack[stack.index(num) + 1:] stack.append(num) maxlen = max(maxlen,len(stack)) return maxlen

Golang

package main /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param arr int整型一维数组 the array * @return int整型 */ func maxLength( arr []int ) int { // write code here if len(arr) == 0 { return 0 } maxLen := 0 var tmpArr []int for _, a := range arr { index := findIndex(tmpArr, a) if index != -1 { tmpArr = tmpArr[index+1:] } tmpArr = append(tmpArr, a) maxLen = max(len(tmpArr), maxLen) } return maxLen } func findIndex(arr []int, x int) int { for index, i := range arr { if i == x { return index } } return -1 } func max(x, y int) int { if x > y { return x } return y }

3、判断链表中是否有环

下面的解法主要是利用有环链表的特点：如果有环，快慢指针终究会在某个节点相遇。

Python

# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # # @param head ListNode类 # @return bool布尔型 # class Solution: def hasCycle(self , head: ListNode) -> bool: if not head: return False s = head t = head while t and t.next: # 当快节点还可以继续往下走的时候 s = s.next # 慢节点往下走一步 t = t.next.next # 快节点往下走两步 if s == t: # 如果在某个时候有碰到 return True # 表示有环 return False

Golang

package main import "fmt" type ListNode struct { val int Next *ListNode } func hasCycle( head *ListNode ) bool { slow := head fast := head if slow == nil || slow.Next == nil { return false } for { slow = slow.Next fast = fast.Next if fast == nil { // 只需要判断快指针是否到末尾（快指针没到末尾的话，慢指针肯定没到末尾） return false } fast = fast.Next if fast == nil { return false } if fast == slow { // 快慢指针相遇，有环 return true } } } func InitListNode(head *ListNode) *ListNode { head = &ListNode{} head.Next = &ListNode{ val: 3, Next: nil, } node1 := head.Next node1.Next = &ListNode{ val: 2, Next: nil, } node2 := node1.Next node2.Next = &ListNode{ val: 0, Next: nil, } node3 := node2.Next node3.Next = &ListNode{ val: -4, Next: nil, } node3.Next = node1 return head } func main() { var head *ListNode head = InitListNode(head) isCycle := hasCycle(head) fmt.Println(isCycle) // true }

4、合并两个排序的链表

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。链表一直是我的软肋，下次有疑惑可以多看看这个例子了。

Python

# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param pHead1 ListNode类 # @param pHead2 ListNode类 # @return ListNode类 # class Solution: def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode: # write code here if not pHead1: return pHead2 if not pHead2: return pHead1 v_head = ListNode(-1) # 由于 tmp 的指针在循环过程中不断变化，所以需要创建虚拟 head 节点来记住真正 head 节点的位置 tmp = v_head # tmp 作为临时链表节点会不断切换 head while pHead1 and pHead2: # 每次将数值更小的链表的头结点追加到 tmp 链表 if pHead1.val < pHead2.val: tmp.next = pHead1 pHead1 = pHead1.next else: tmp.next = pHead2 pHead2 = pHead2.next tmp = tmp.next # 每次追加完节点后，重置临时链表的头到新追加的节点 # 到这里的时候，其中一个链表已经遍历完毕，将另外一个链表直接追加到 tmp 链表后面 if pHead1 is None: tmp.next = pHead2 else: tmp.next = pHead1 # 虚拟节点的下一个节点才是真正的合并链表的 head return v_head.next

Golang

package main type ListNode struct{ Val int Next *ListNode } /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类 */ func Merge( pHead1 *ListNode , pHead2 *ListNode ) *ListNode { // write code here if pHead1 == nil { return pHead2 } if pHead2 == nil { return pHead1 } v_head := &ListNode{} tmp := v_head for pHead1 != nil && pHead2 != nil { if pHead1.Val < pHead2.Val { tmp.Next = pHead1 pHead1 = pHead1.Next } else { tmp.Next = pHead2 pHead2 = pHead2.Next } tmp = tmp.Next } if pHead1 != nil { tmp.Next = pHead1 } if pHead2 != nil { tmp.Next = pHead2 } return v_head.Next }

5、连续子数组的最大和

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

Python

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param array int整型一维数组 # @return int整型 # # -*- coding:utf-8 -*- class Solution: def FindGreatestSumOfSubArray(self, array): # write code here if not array: return 0 s = 0 m = array[0] # 初始默认最大值就是第一个元素 for i in array: s += i if s > m: # 如果某个时候的 sum 大于 max，则重置 max 的值 m = s if s < 0: # 如果某个时候的 sum 比初始的 s = 0 还小， s = 0 # 则从后续元素开始重新查找最大值的子数组 return m

Golang

package main import ( "bufio" "fmt" "os" "strconv" ) func main() { var num int fmt.Scan(&num) var arr []int scanner := bufio.NewScanner(os.Stdin) for scanner.Scan() { tmp, _ := strconv.Atoi(scanner.Text()) arr = append(arr, tmp) } s := 0 m := arr[0] for _, v := range arr { s += v if s > m { m = s } if s < 0 { s = 0 } } fmt.Println(m) }

6、最大数

给定一个长度为n的数组nums，数组由一些非负整数组成，现需要将他们进行排列并拼接，每个数不可拆分，使得最后的结果最大，返回值需要是string类型，否则可能会溢出。

这里其实就是简单的冒泡排序就行，只不过是要把更大的数排到更靠前边。

# # 最大数 # @param nums int整型一维数组 # @return string字符串 # class Solution: def solve(self , nums ): nums = [str(x) for x in nums] for i in range(len(nums)): for j in range(len(nums)-i-1): a = str(nums[j]) b = str(nums[j+1]) # 每次把相邻的两个字符串正反拼接，转成整数比较大小后确认是否交换位置 if int("".join([b, a])) > int("".join([a, b])): nums[j], nums[j+1] = nums[j+1], nums[j] if nums[0] == '0': return '0' return "".join(nums)

7、链表的奇偶重排

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。注意是节点的编号而非节点的数值。

解题思路：对于原始链表，每个节点都是奇数节点或偶数节点。头节点是奇数节点，头节点的后一个节点是偶数节点，相邻节点的奇偶性不同。因此可以将奇数节点和偶数节点分离成奇数链表和偶数链表，然后将偶数链表连接在奇数链表之后，合并后的链表即为结果链表。

Python

# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # class Solution: def oddEvenList(self , head: ListNode) -> ListNode: # write code here if not head: return head odd = head even = head.next even_head = even # 记住偶链表的头（因为最后要将偶链表拼接到奇链表的末尾） while even and even.next: odd.next = even.next # 奇链表 odd = odd.next even.next = odd.next # 偶链表 even = even.next odd.next = even_head # 将奇偶链表前后连起来 return head

Golang

package main import . "nc_tools" /* * type ListNode struct{ * Val int * Next *ListNode * } */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ func oddEvenList( head *ListNode ) *ListNode { // write code here if head == nil || head.Next == nil { return head } odd := head even := head.Next evenHead := head.Next for even != nil && even.Next != nil{ odd.Next = even.Next odd = odd.Next even.Next = odd.Next even = even.Next } odd.Next = evenHead return head }

8、买卖股票的最好时机

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天

2.如果不能获取到任何利润，请返回0

3.假设买入卖出均无手续费

Python

贪心算法：每第 i 天都计算一下如果当天卖出的话，所能获得的最大收益。

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param prices int整型一维数组 # @return int整型 # class Solution: def maxProfit(self , prices: List[int]) -> int: # write code here if not prices: return 0 max_profit = 0 min_price = prices[0] for price in prices: min_price = min(min_price, price) # 第 i 天及之前的最低价格 max_profit = max(max_profit, price - min_price) # 第 i 天卖出的话所能获得的最大收益 return max_profit

Golang

package main import ( "bufio" "fmt" "os" "strconv" "strings" ) func main() { var num int fmt.Scan(&num) var intArr []int var line string reader := bufio.NewReader(os.Stdin) line, _ = reader.ReadString('\n') line = strings.TrimSpace(line) arr := strings.Split(line, " ") for _, v := range arr { tmp, _ := strconv.Atoi(v) intArr = append(intArr, tmp) } minPrice := intArr[0] maxProfit := 0 for _, price := range intArr { minPrice = min(minPrice, price) maxProfit = max(maxProfit, price-minPrice) } fmt.Println(maxProfit) } func min(x, y int) int { if x > y { return y } return x } func max(x, y int) int { if x > y { return x } return y }

9、最长公共前缀

给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

哈哈，我的第一想法竟然是 os.path.commonprefix(strs)，而且还通过了用例，这就比较尴尬了：

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param strs string字符串一维数组 # @return string字符串 # class Solution: def longestCommonPrefix(self , strs: List[str]) -> str: # write code here import os return os.path.commonprefix(strs)

不过题目显然是想让我们自己写

Python

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param strs string字符串一维数组 # @return string字符串 # class Solution: def longestCommonPrefix(self , strs: List[str]) -> str: # write code here if not strs: return '' min_len = min([len(x) for x in strs]) common_prefix = "" for i in range(min_len): if len(set([x[i] for x in strs])) == 1: common_prefix += strs[0][i] else: break return common_prefix

Golang

package main /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param strs string字符串一维数组 * @return string字符串 */ func longestCommonPrefix(strs []string) string { // write code here if len(strs) == 0 { return "" } if len(strs) == 1 { return strs[0] } minLen := len(strs[0]) for _, str := range strs { if len(str) < minLen { minLen = len(str) } } commonPrefix := "" for i := 0; i < minLen; i++ { ch := strs[0][i] for _, v := range strs { if v[i] != ch { return commonPrefix } } commonPrefix += string(ch) } return commonPrefix }

10、链表环入口

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表。

这个也需要先判断环，

Python

# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def EntryNodeOfLoop(self, pHead): # write code here fast = pHead slow = pHead if slow is None or slow.next is None: return None while fast and slow: slow = slow.next fast = fast.next if fast is None: return None fast = fast.next if fast is None: return None if slow == fast: break slow = pHead if slow == fast: return slow while slow != fast: slow = slow.next fast = fast.next return slow

Golang

package main func EntryNodeOfLoop(pHead *ListNode) *ListNode { slow := pHead fast := pHead if slow == nil || slow.Next == nil { return nil } for { slow = slow.Next fast = fast.Next if fast == nil { return nil } fast = fast.Next if fast == nil { return nil } if fast == slow { break } } slow = pHead if slow == fast { return slow } for { fast = fast.Next slow = slow.Next if fast == slow { return slow } } }