Shopee虾皮0401-笔试
本来时间是7:00-9:00，但鼠鼠8:05才进来，单选多选直接一通连蒙带骗10分钟整完，主要做了三道编程题：100 100 93
1.lc61旋转链表，mid原题，这次赶时间直接用了golang，golang内置的list非常适合首尾移位操作，加个虚拟头节点避免麻烦事
package main
import "container/list"
type ListNode struct {
Val int
Next *ListNode
}
/**
* Note: 类名、方法名、参数名已经指定，请勿修改
*
*
* 旋转链表
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
func Rotate(head *ListNode, k int) *ListNode {
// write code here
nodeList := list.New()
p := head
for p != nil {
nodeList.PushBack(p)
p = p.Next
}
listLen := nodeList.Len()
k = k % listLen
for i := 0; i < k; i++ {
ele := nodeList.Back()
nodeList.MoveToFront(ele)
}
//虚拟头
phead := &ListNode{
Val: 0,
Next: nil,
}
p = phead
for nodeList.Len() > 0 {
ele := nodeList.Front()
nodeList.Remove(ele)
nextNode := ele.Value.(*ListNode)
p.Next = nextNode
p = p.Next
}
p.Next = nil
return phead.Next
}
2.小写字母翻转，保持单词相对位置不变，其余非小写字母位置不变，如“Shoppee 1a3c abc”，应翻转为"Seepph 1c3a cba"，先用空格分割，再对单个单词进行处理。Java内置的String类封装的各种方法比较方便，并且拼接时注意使用StringBuilder提高性能（AC）
class Solution {
/**
* Note: 类名、方法名、参数名已经指定，请勿修改
* <p>
* <p>
* 反转字符串中的小写字母，并且保证单个单词的顺序不变，其他字符的位子不变
*
* @param original_str string字符串
* @return string字符串
*/
public String reverses(String original_str) {
// write code here
String[] strings = original_str.split(" ");
StringBuilder builder = new StringBuilder();
for (String str : strings) {
builder.append(getReverseLowStr(str));
builder.append(" ");
}
builder.deleteCharAt(builder.length() - 1);
return builder.toString();
}
private String getReverseLowStr(String str) {
StringBuilder sb = new StringBuilder();
StringBuilder strBuilder = new StringBuilder(str);
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch >= 'a' && ch <= 'z') {
sb.append(ch);
}
}
sb.reverse();
String s = sb.toString();
int point = 0;
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch >= 'a' && ch <= 'z') {
strBuilder.setCharAt(i, s.charAt(point));
point++;
}
}
return strBuilder.toString();
}
}
3.lol英雄价格数组，原始点券有限，问最多能买多少个英熊，注意返回买了哪些点卷，返回购买的点卷数组。不能重复买，这JB一眼01背包，这不直接双层dp？外层物品，内层倒序容量。正准备用双层dp秒，结果想了想，dp解决01背包只能求个数，他让我把具体哪个列出来，搞得鼠鼠我头大，时间剩的不多了，后面转念一想，干脆回溯爆搜算了，也是用golang省了写题时间，这B语言写工程有种吃shi的感觉，写个算法题倒可以少写不少东西（93%，代码没问题，应该是后7%超时了，欢迎大家指导剪枝方式）
package main
import "fmt"
/**
* Note: 类名、方法名、参数名已经指定，请勿修改
*
*
* 根据价格列表和当前点券数，计算出能买到的最多英雄
* @param costs int整型 一维数组 英雄点券价格列表
* @param coins int整型 拥有的点券
* @return int整型一维数组
*/
var result []int
var max int
var record []int
func solution(costs []int, coins int) []int {
// write code here
result = make([]int, 0)
record = make([]int, 0)
max = 0
n := len(costs)
backtrack(0, n, costs, coins, 0)
return record
}
func backtrack(index int, n int, costs []int, coins int, now int) {
if index >= n || now >= coins {
if now <= coins {
if len(result) > max {
max = len(result)
record = make([]int, 0)
for i := 0; i < len(result); i++ {
record = append(record, result[i])
}
}
} else {
if len(result)-1 > max {
max = len(result) - 1
record = make([]int, 0)
for i := 0; i < len(result)-1; i++ {
record = append(record, result[i])
}
}
}
return
}
//0算上，1不算
for i := 0; i < 2; i++ {
if i == 0 {
now += costs[index]
result = append(result, costs[index])
backtrack(index+1, n, costs, coins, now)
result = result[:len(result)-1]
now -= costs[index]
} else {
backtrack(index+1, n, costs, coins, now)
}
}
}
func main() {
arr := make([]int, 0)
arr = append(arr, 2)
arr = append(arr, 1)
arr = append(arr, 3)
arr = append(arr, 4)
arr = append(arr, 5)
res := solution(arr, 10)
fmt.Println(res)
}
今天的笔试大家参加了吗，欢迎大家来多多交流，特别是第三题，对于暴力回溯的剪枝方式以及dp解决01背包如何把拿了哪些物品列出而不是只列最大价值。大佬牛子们请多多指导！
查看10道真题和解析