220817笔试（速腾聚创）

题目一

给定一个无序数组arr,其中元素可正、可负、可0。给定一个整数k，求arr所有子数组中累加和为k的最长连续子数组长度。

// 哈希
class Solution {public int maxlenEqualK (int[] arr, int k) {if (arr == null || arr.length == 0) {return 0;}int len = Integer.MIN_VALUE;int sum = 0;// map<sum, i>存储从arr[0]到arr[i]的累加和Map<Integer, Integer> map = new HashMap<>();map.put(0, -1);// 处理边界值// arr[i + 1, ..., j] = kfor (int i = 0; i < arr.length; i++) {sum += arr[i];// 只记录第一次的位置，因为要求最长数组if (!map.containsKey(sum)) {map.put(sum, i);}// 判断是否需要更新lenif(map.containsKey(sum - k)){len = Math.max(len, i - map.get(sum - k));}}return len;}
}

若子数组可以是不连续的

// 递归
class Solution {int res = 0;public int maxlenEqualK (int[] arr, int k) {Arrays.sort(arr);dfs(arr, k, 0, 0, 0);return res;}private void dfs(int[] arr, int k, int start, int len, int tmp) {// len != 0 是为了防止k = 0，题目说明至少存在一个合法的连续子数组if (tmp == k && len != 0) {res = Math.max(res, len);return;}for (int i = start; i < arr.length && tmp + arr[i] <= k; i++) {len++;tmp += arr[i];dfs(arr, k, start + 1, len, tmp);len--;tmp -= arr[i];}}
}

题目二

栈的逆序，采用递归方法

// 数组代表栈
class ReverseStack {public int[] reverseStackRecursively(int[] stack, int top) {if (top == 0) {return stack;}// 获得栈底元素top--;int last = getLast(stack, top);stack = reverseStackRecursively(stack, top);// 放入栈顶stack[top] = last;return stack;}public static int getLast(int[] stack, int top){int tmp = stack[top];// 若为栈底则返回栈底元素if (top == 0){return tmp;}top--;int last = getLast(stack, top);// 其余元素入栈stack[top] = tmp;return last;}
}// Stack栈
class ReverseStack {public Stack<Integer> reverse(Stack<Integer> stack) {if (stack.isEmpty()) {return;}int tmp = getBottom(stack);reverse(stack);stack.push(tmp);return stack;}public static int getBottom(Stack<Integer> stack) {int tmp = stack.pop();if (stack.isEmpty()) {return tmp;}int last = getBottom(stack);stack.push(tmp);return last;}
}

220817笔试（速腾聚创）

题目一

给定一个无序数组arr,其中元素可正、可负、可0。给定一个整数k，求arr所有子数组中累加和为k的最长连续子数组长度。

// 哈希
class Solution {public int maxlenEqualK (int[] arr, int k) {if (arr == null || arr.length == 0) {return 0;}int len = Integer.MIN_VALUE;int sum = 0;// map<sum, i>存储从arr[0]到arr[i]的累加和Map<Integer, Integer> map = new HashMap<>();map.put(0, -1);// 处理边界值// arr[i + 1, ..., j] = kfor (int i = 0; i < arr.length; i++) {sum += arr[i];// 只记录第一次的位置，因为要求最长数组if (!map.containsKey(sum)) {map.put(sum, i);}// 判断是否需要更新lenif(map.containsKey(sum - k)){len = Math.max(len, i - map.get(sum - k));}}return len;}
}

若子数组可以是不连续的

// 递归
class Solution {int res = 0;public int maxlenEqualK (int[] arr, int k) {Arrays.sort(arr);dfs(arr, k, 0, 0, 0);return res;}private void dfs(int[] arr, int k, int start, int len, int tmp) {// len != 0 是为了防止k = 0，题目说明至少存在一个合法的连续子数组if (tmp == k && len != 0) {res = Math.max(res, len);return;}for (int i = start; i < arr.length && tmp + arr[i] <= k; i++) {len++;tmp += arr[i];dfs(arr, k, start + 1, len, tmp);len--;tmp -= arr[i];}}
}

题目二

栈的逆序，采用递归方法

// 数组代表栈
class ReverseStack {public int[] reverseStackRecursively(int[] stack, int top) {if (top == 0) {return stack;}// 获得栈底元素top--;int last = getLast(stack, top);stack = reverseStackRecursively(stack, top);// 放入栈顶stack[top] = last;return stack;}public static int getLast(int[] stack, int top){int tmp = stack[top];// 若为栈底则返回栈底元素if (top == 0){return tmp;}top--;int last = getLast(stack, top);// 其余元素入栈stack[top] = tmp;return last;}
}// Stack栈
class ReverseStack {public Stack<Integer> reverse(Stack<Integer> stack) {if (stack.isEmpty()) {return;}int tmp = getBottom(stack);reverse(stack);stack.push(tmp);return stack;}public static int getBottom(Stack<Integer> stack) {int tmp = stack.pop();if (stack.isEmpty()) {return tmp;}int last = getBottom(stack);stack.push(tmp);return last;}
}