java面试中常见的数组题目汇总（五）

public int GetNumberOfK(int [] array , int k) { if (array.length==0 || array==null) return 0; int i,n,count; n = array.length; count = 0; for (i=0; i> 1; if (a[mid] <= k) { start = mid + 1; } else { end = mid - 1; } } return end; } public int low(int[] a, int k) { int start,end,mid; start = 0; end = a.length-1; while (start <= end) { mid = (start + end) >> 1; if (a[mid] >= k) { end = mid - 1; } else { start = mid + 1; } } return start; }

public int Sum_Solution(int n) { int sum = n; boolean flag = (sum > 0) && (sum += Sum_Solution(n-1))>0; return sum; }

/** * 给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（m、n 都是整数，n>1 并且 m>1）， * 每段绳子的长度记为 k [0],k [1],...,k [m]。 * 请问 k [0] xk [1] x...xk [m] 可能的最大乘积是多少？ * 例如，当绳子的长度是 8 时， * 我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18。 * * 使用动态规划 * 要点：边界和状态转移公式 * 使用顺推法：从小推到大 * dp[x] 代表x的最大值 * dp[x] = max{d[x-1]*1,dp[x-2]*2,dp[x-3]*3,,,,},不需要全遍历，取半即可 * */ public int cutRope(int target) { // 由于2,3是划分的乘积小于自身，对状态转移会产生额外判断 if (target <= 3) return target-1; int[] dp = new int[target+1]; int mid,i,j,temp; // 设定边界 dp[2] = 2; dp[3] = 3; for (i=4; i<=target; i++) { // 遍历到中间即可 mid = i >> 1; // 暂存最大值 temp = 0; for (j=1; j<=mid; j++) { if (temp < j*dp[i-j]) { temp = j*dp[i-j]; } } dp[i] = temp; } return dp[target]; }

* * 使用动态规划 * 要点：边界和状态转移公式 * 使用顺推法：从小推到大 * dp[x] 代表x的最大值 * dp[x] = max{d[x-1]*1,dp[x-2]*2,dp[x-3]*3,,,,},不需要全遍历，取半即可 * 但是需要注意。2和3这两个特殊情况，因为他们的分解乘积比自身要大，所以特殊处理

package swear2offer.array; import java.util.ArrayList; public class Windows { /** * 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。 * 例如，如果输入数组 {2,3,4,2,6,2,5,1} 及滑动窗口的大小 3， * 那么一共存在 6 个滑动窗口，他们的最大值分别为 {4,4,6,6,6,5} * * 思路： * 先找出最开始size大小的最大值，以及这个最大值的下标 * 然后每次增加一个值，先判断滑动窗口的第一位下标是否超过保存最大值的下标 * 如果超过就要重新计算size区域的最大值， * 如果未超过就使用最大值与新增的元素比较，获取较大的 * */ public ArrayList maxInWindows(int [] num, int size) { ArrayList list = new ArrayList<>(); int i; int[] temp; temp = getMax(num,0,size); if (size<=0 || num==null || num.length==0) return list; // 当窗口大于数组长度 if (num.length <= size) return list; // 把第一个滑动窗口最大值加入数组 list.add(temp[0]); // 从新的窗口开始计算，上一个窗口的最大值和下标保存在temp中 for (i=size; inum.length) e = num.length; int temp = Integer.MIN_VALUE; int k = 0; for (int i=s; i
        

         登录后复制
        
       

/** * 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。 * 数组中某些数字是重复的，但不知道有几个数字是重复的。 * 也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 * 例如，如果输入长度为 7 的数组 {2,3,1,0,2,5,3}， * 那么对应的输出是第一个重复的数字 2。 * * 思路： * 看到 长度n，内容为0-n-1；瞬间就应该想到，元素和下标的转换 * * 下标存的是元素的值，对应的元素存储出现的次数， * 为了避免弄混次数和存储元素，把次数取反，出现一次则-1，两次则-2 * 把计算过的位置和未计算的元素交换，当重复的时候，可以用n代替 * */ public boolean duplicate(int numbers[],int length,int [] duplication) { if (length == 0 || numbers == null) { duplication[0] = -1; return false; } int i,res; i = 0; while (i < length) { // 获取到数组元素 res = numbers[i]; // 判断对应位置的计数是否存在 if (res < 0 || res == length) { i++; continue; } if (numbers[res] < 0) { numbers[res] --; numbers[i] = length; continue; } numbers[i] = numbers[res]; numbers[res] = -1; } res = 0; for (i=0; i
        

         登录后复制