算法数据结构系列-实践篇-数组算法程序员

@TOC
Offer-03 数组中重复的数字问题描述：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

public int findRepeatNumber(int[] nums) { if (nums == null || nums.length < 1) { return -1; } int len = nums.length; for (int i = 0; i < len; i++) { int index = nums[i] % len; // 通过取余,获取数字原来的数,但仅作为索引使用,并改变当前遍历点i的值 if (nums[index] >= len) {//是index不是i,要判断index是否重复 return nums[i] % len; } nums[index] += len; //加length方便,将数还原 } return -1; }

Offer-66 构建乘积数组问题描述：给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]，不能使用除法，具体可参考Offer-66题。

文章图片

public int[] constructArr(int[] a) { int[] b = new int[a.length]; b[0] = 1; for (int i = 1; i < a.length; i++) { b[i] = b[i - 1] * a[i - 1]; } int tmp = 1; for (int i = a.length - 2; i >= 0; i--) { tmp = tmp * a[i+1]; b[i] = tmp * b[i]; } return b; }

Offer-45 把数组排成最小的数问题描述：输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。如果输入: [10,2]，输出: "102"，具体可参考Offer-45题。关于排序的规则理解，可以亲自按插入排序试一下。

文章图片

public String minNumber(Integer[] nums) { if (nums == null || nums.length < 1) { return ""; }Arrays.sort(nums, new Comparator() { @Override public int compare(Integer o1, Integer o2) { String x = o1.toString() + o2.toString(); String y = o2.toString() + o1.toString(); return x.compareTo(y); } }); StringBuilder sb = new StringBuilder(); for (Integer num : nums) { sb.append(num); } return sb.toString(); }

Offer-49 判断丑数问题描述：我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number），求按从小到大的顺序的第 n 个丑数。蛮力法：根据丑数定义，若一个数能被2整除，则连续除以2；若还能被3整除，则连续除以3；若还能被5整除，则连续除以5；如果最后结果是1则是丑数，否则不是；动态规划：新丑数，是前面已经生成的丑数的2倍或3倍或5倍。具体详见Offer-49题。

文章图片

文章图片

Offer-29 顺时针打印矩阵问题描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]，输出：[1,2,3,6,9,8,7,4,5]。

文章图片

public int[] spiralOrder2(int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return new int[0]; }int cols = matrix[0].length; int rows = matrix.length; int[] order = new int[cols * rows]; int top = 0, bottom = rows - 1, left = 0, right = cols - 1; int index = 0; while (index < order.length) { for (int column = left; column <= right; column++) { order[index++] = matrix[top][column]; } if (index == order.length) { break; }for (int row = top + 1; row <= bottom; row++) { order[index++] = matrix[row][right]; } if (index == order.length) { break; }for (int column = right - 1; column > left; column--) { order[index++] = matrix[bottom][column]; } if (index == order.length) { break; }for (int row = bottom; row > top; row--) { order[index++] = matrix[row][left]; }top++; bottom--; left++; right--; } return order; }

offer-61 扑克牌中的顺子从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。输入: [1,2,3,4,5]，输出: True；输入: [0,0,1,2,5]，输出: True；

文章图片

public boolean isStraight(int[] nums) { Set set = new HashSet<>(); int min = 15, max = -1; for (int num : nums) { if (set.contains(num)) { return false; } if (num == 0) { continue; }set.add(num); min = Math.min(min, num); max = Math.max(max, num); } return (max - min) < 5; }

Offer-57 和为s的两个数字问题描述：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

文章图片

public int[] twoSum(int[] nums, int target) { if (nums == null || nums.length < 3) { return nums; }int i = 0, j = nums.length - 1; while (i < j) { int s = nums[i] + nums[j]; if (s == target) { return new int[]{nums[i], nums[j]}; } if (s < target) { i++; continue; } j--; } return new int[0]; }

Offer-57-II 和为s的连续正数序列输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。输入：target = 9，输出：[[2,3,4],[4,5]]

文章图片

public int[][] findContinuousSequence(int target) { int i = 1; // 滑动窗口的左边界 int j = 1; // 滑动窗口的右边界 int sum = 0; // 滑动窗口中数字的和 List list = new ArrayList<>(); while (i <= target / 2) { if (sum < target) { sum += j; j++; continue; }if (sum > target) { sum -=i; i++; continue; }int[] arr = new int[j-i]; // 记录结果 for (int k = i; k < j; k++) { arr[k-i] = k; } list.add(arr); sum -= i; // 左边界向右移动 i++; } return list.toArray(new int[list.size()][]); }

Offer-59-1 滑动窗口的最大值问题描述：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

文章图片

public Integer[] maxSlidingWindow(Integer[] nums, int k) { if (nums == null || nums.length < 1) { return new Integer[0]; } Integer[] result = new Integer[nums.length - k + 1]; Deque queue = new LinkedList<>(); for (int i = 0; i < k; i++) { while (!queue.isEmpty() && queue.peekLast() < nums[i]) { // 查找插入位置 queue.removeLast(); } queue.offer(nums[i]); } Integer index = 0; result[index++] = queue.peekFirst(); for (int j = k; j < nums.length; j++) { if (nums[j - k] == queue.peekFirst()) { queue.removeFirst(); } while (!queue.isEmpty() && queue.peekLast() < nums[j]) { // 查找插入位置 queue.removeLast(); } queue.offer(nums[j]); result[index++] = queue.peekFirst(); } return result; }

Offer-44 数字序列中某一位的数字数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。

文章图片

public int findNthDigit(int n) { int digit = 1; long start = 1, count = 9; while (n > count) { // 求所在的数字的位数 n -= count; digit++; start *= 10; count = 9 * start * digit; } long num = start + (n-1)/digit; // 求坐在数字 return Long.toString(num).charAt(((n - 1) % digit)) -'0'; }

Offer-39 数组中出现次数超过一半的数字数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

文章图片

public int majorityElement(int[] nums) { if (nums == null || nums.length < 1) { return -1; }int vote = 0, x = -1; for (int num : nums) { if (vote == 0) { x = num; } vote += num == x ? 1 : -1; } return x; }

面试题-01-08 零矩阵问题描述：编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零，具体详见金典01-08题。

文章图片

public void setZeroes(int[][] matrix) { if (matrix == null || matrix.length < 1) { return; } boolean[] rows = new boolean[matrix.length]; boolean[] cols = new boolean[matrix[0].length]; for (int i = 0; i < rows.length; i++) { for (int j = 0; j < cols.length; j++) { if (matrix[i][j] == 0) { rows[i] = true; cols[j] = true; } } }for (int i = 0; i < rows.length; i++) { for (int j = 0; j < cols.length; j++) { if (rows[i] || cols[j]) { matrix[i][j] = 0; } } } }

面试题-01-07 旋转矩阵问题描述：给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。不占用额外内存空间能否做到。