| 面试+算法之数组：多数元素、两数之和、三数之和、股票交易最大利润、连续元素最大求和、未出现的最小正整数、排序数组求某元素的索引位置、不重复的元素 | 您所在的位置：网站首页 › psp自动关机问题 › 面试+算法之数组：多数元素、两数之和、三数之和、股票交易最大利润、连续元素最大求和、未出现的最小正整数、排序数组求某元素的索引位置、不重复的元素 |
|
概述 算法是一个程序员的核心竞争力，也是面试最重要的考查环节。本文整理一些与数组相关的基础算法题。 注：题目均搜集自网络，仅做汇总整理备忘录用。 考题多数元素给定一个大小为n的数组，找到其中的多数元素和出现次数。多数元素：在数组中出现次数大于 ⌊n/2⌋ 的元素。 假定：数组非空且总是存在多数元素。 要求：时间复杂度为O(n)、空间复杂度为O(1) public static int getMajority(int[] nums) { int count = 0; int result = 0; for (int item : nums) { if (item == result) { count += 1; } else { if (count == 0) { result = item; count = 1; } else { count -= 1; } } } return result;}两数之和从给定的数组nums里面找到满足条件的两个数，使其和为目标值target。返回满足条件的一组结果即可，返回索引值。 分析：结果存在多种情况，题目要求只返回一种： public static int[] twoSum(int[] nums, int target) { int[] answer = new int[2]; int n = nums.length; for (int i = 0; i t) { break; } if (nums[j] == t) { answer[1] = j + 1; break; } } if (answer[1] != 0) { break; } } return answer;}如果需要返回全部满足条件的组合呢？ 组合总和给定一个无重复元素的数组nums和目标数 target，找出nums中所有可以使数字和为target的组合。 注：nums中的数字可以无限制重复被选取，组合不能重复。 public static List combinationSum(int[] nums, int target) { List resultList = new ArrayList(); List result = new ArrayList(); Arrays.sort(nums); dfs(nums, resultList, result, 0, target); return resultList;}private static void dfs(int[] nums, List resultList, List result, int start, int target) { if (target >= 0) { if (target == 0) { resultList.add(new ArrayList(result)); } else { for (int i = start; i 三数之和股票交易的最大利润 给定一个非负整数元素组成的数组，其中的元素值表示股票的每日价格，求能获得的股票交易最大利润。 注：股票交易必须先买入，后卖出；可以多次买入卖出；只有卖出后才能获取到利润。 示例： 输入：[3, 5, 4, 3, 1, 4] 输出：5 public static int maxProfit(int[] prices) { int temp = 0; // 终止条件为length-1,防止数组越界 for (int i = 0; i prices[i]) { temp = temp + prices[i + 1] - prices[i]; } } return temp;}连续元素的最大和给定一个包含负数的整数数组，求连续元素的最大求和。 public static int maxSubArray(int[] nums) { int maxSum = nums[0]; int curSum = 0; for (int n : nums) { curSum += n; if (curSum > maxSum) { maxSum = curSum; } if (curSum 给你一个未排序的整数数组 nums ，找出其中未出现的最小正整数。public static int firstMissingPositive(int[] nums) { int ls = nums.length; int index = 0; while (index 给定一个升序排列的整数数组nums，目标值target。找出给定目标值在数组中的开始位置和结束位置；如果数组中不存在目标值 target，返回[-1, -1]。注：元素可能不存在，也可能出现不止2次。 public static int[] searchRange(int[] nums, int target) { int[] result = new int[2]; result[0] = floor(nums, target); result[1] = ceil(nums, target); return result;}private static int floor(int[] nums, int target) { int left = -1; int right = nums.length - 1; while (left = 0 && nums[right - 1] == target) { return right - 1; } else { return -1; }} 不重复的元素给定一个包含若干重复元素的数组，找出第一个未重复的元素。 分析：存在重复2次或以上的情况；存在多个元素未重复的情况。 public static int singleNumber(int[] nums) { Arrays.sort(nums); int res = 0; int i = 0; for (int j = 1; j 给定一个有序数组，和目标值target，将target插入到数组中，返回其索引值。分析：数组可能包括负数，可能存在重复值，目标值也可能与数组元素重复。 public static int searchInsert(int[] nums, int target) { int left = 0, right = nums.length - 1; if (target nums[right]) { return nums.length; } while (left nums[mid]) { left = mid + 1; } else { return mid; } } return left;}数组元素可组成的最大数给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。注：输出结果可能非常大，返回一个字符串。 示例： 输入：[3, 30, 34, 5, 9] 输出：9534330 public static String largest(int[] nums) { int n = nums.length; for (int i = 0; i 给定一个非负整数数组，最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。目标：使用最少的跳跃次数到达数组的最后一个位置。 public static int jump(int[] nums) { int end = 0; int steps = 0; int maxPosition = 0; // 不能等于length-1 for (int i = 0; i 给定一个数组nums和目标值target，原地移除所有数值等于target的元素，返回移除后数组的新长度。注：不能使用额外的数组空间，必须仅使用 O(1) 额外空间并原地修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 public static int removeElement(int[] nums, int target) { int len = nums.length; for (int i = 0; i 给定一个数组，数组每个元素值表示其高度值，单位值为1，每两个元素间隔单位值为1。为简化问题，假设水的宽度为单位1。求能盛水的最大体积。示例： 输入：[1, 8, 6, 2, 5, 4, 8, 3, 7] 输出：49 public static int maxArea(int[] height) { int ret = 0; int temp; int j = height.length - 1; for (int i = 0; i height[j]) { j--; } else { i++; } } return ret;}参考
|
| CopyRight 2018-2019 实验室设备网 版权所有 |