Shopee虾皮0401-笔试

本来时间是7:00-9:00，但鼠鼠8:05才进来，单选多选直接一通连蒙带骗10分钟整完，主要做了三道编程题：100 100 93

1.lc61旋转链表，mid原题，这次赶时间直接用了golang，golang内置的list非常适合首尾移位操作，加个虚拟头节点避免麻烦事（AC）

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背包如何把拿了哪些物品列出而不是只列最大价值。大佬牛子们请多多指导！也希望可以再拿些面试机会练练手