题目(LeetCode 704) 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1
输入:nums= [-1,0,3,5,9,12],target= 9 输出: 4 解释: 9 出现在nums中并且下标为 4
提示：
- 你可以假设
nums中的所有元素是不重复的。 n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
思路：有序数组，元素不重复。可以用二分查找。 二分查找，根据左右下标取一个中间值，和元素进行比对，根据中间值和元素值的大小比较，来更新左右边界。以此来达到快速查找。
需要注意左右边界的设置。
代码：
//有序数组，找到某元素下标值。 public class binarySearch { //测试用例 public static void main(String[] args) { int[] ints = new int[]{1,2,3,5,6,7,8,9,10,15,18,19,62}; binarySearch binarySearch = new binarySearch(); int a = binarySearch.clac(ints,62); System.out.println(a); } //实现 public int clac(int[] array, int target){ int left = 0; int right = array.length-1; while(left<=right) { int middle = (right+left) / 2; if (target < array[middle]) { right = middle - 1; }else if(target>array[middle]){ left =middle+1; }else{ return middle; } } return -1; } }
题目(LeetCode 27)
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
思路：因为不仅仅删除元素，还需要更新数组的长度，所以就需要删除+更新操作。
第一种解法是暴力双循环，外层循环找到需要删除的元素后删除元素，内循环把后续的元素往前移一位。这样的做法简单粗暴，但是毕竟是双循环，效率是n^2
第二种做法是双指针，快慢指针结合。快慢指针，开始位置相同。直到遇到需要删除的值，慢指针不动，快指针前移。
这里的微妙之处就在于，由于for循环的存在，快指针一直移动，慢指针只在找到的值不是需要删除的值时候移动。
如果是需要删除的值，快指针+1，慢指针停留。注意，这种做法，没有办法把数组所有要删除的数覆盖掉，只是通过这种方法计算出了正确的数组个数对应的索引位置。
代码：
package com.dwj.LeetCode.array; //在数组中移除元素，并返回数组长度 //双指针写法，快慢指针 public class ArrayRemove2 { public static void main(String[] args) { ArrayRemove2 arrayRemove2 = new ArrayRemove2(); int size = arrayRemove2.RemoveEle(new int[]{1,2,2,3,4},2); System.out.println(size); } public int RemoveEle(int[] array,int RemoveVal){ //快慢指针定义 int faseIndex = 0; int slowIndex = 0; //初始条件：slowIndex=0 结束条件：faseIndex走到头 //一开始，快慢指针同时移动，直到遇到了需要移除的值，快指针跳过，然后不断把后面不需要移除的值前移覆盖。 for (slowIndex =0; faseIndex<array.length;faseIndex++){ //如果快指针位置上的值不是需要删除的值，slow指针位置+1，并且让所处的值移动覆盖 if (array[faseIndex]!=RemoveVal){ array[slowIndex]=array[faseIndex]; slowIndex++; } } return slowIndex; } }
题目(LeetCode 977) 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104nums已按 非递减顺序 排序
思路：
由于负数的平方和可能比正数大，需要一个新的数组对其进行排序。例如可以使用双指针的方法。
一个指针在左，一个指针在右。比对两边的大小，由于最大的一定在最左或最右。大的放入新数组的最右边。
代码：
package com.dwj.LeetCode.array; //计算有序数组的平方和，并排序 public class Square { public static void main(String[] args) { int[] ints = {-9, 2, 3, 4, 5, 6}; Square square = new Square(); int[] result = square.sortedSquares(ints); for (int i = 0; i <result.length ; i++) { System.out.println(result[i]); } } public int[] sortedSquares(int[] nums){ //右端下标 int right = nums.length-1; //左端下标 int left = 0; int[] result = new int[nums.length]; //新的result数组从末尾写入 int index = result.length-1; //注意这里要left <= right，因为最后要处理两个元素 while (left<=right){ if(nums[left]*nums[left]>nums[right]*nums[right]){ result[index--] = nums[left] * nums[left]; //这里的index-- ，操作后，index-1 ++left; }else{ result[index--] = nums[right]*nums[right]; --right; } } return result; } }
这里，复习一下对于 i++和 ++i的区别：
Int i=10;
Int j = 0;
j = i++ //j=10
题目(LeetCode 209)
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 105
思路：
1.暴力双循环。外面从i开始，里面从i+1开始加。如果找到了，保存长度后续用于比对。
2.滑动窗口。滑动窗口的本质是用一个for循环完成两个for循环的事情。这里for循环的下标是终止位置。
当终止位置达到预期值后，改变起始位置，进行下一次循环操作。
在这个题目中，第一次循环，终止下标移动到大于s，然后改变起始点位置进行重新计算大于s的下标位置。
直到终止点到最后一个元素，结束。可以理解为终止位置向前移动的过程中，不断地改变起始位置的过程。
代码：
package com.dwj.LeetCode.array; //给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。 public class MinLengthArray { public static void main(String[] args) { MinLengthArray minLengthArray = new MinLengthArray(); int result = minLengthArray.minSubArrayLen(8,new int[]{1,2,3,4}); System.out.println(result); } public int minSubArrayLen(int s, int[] nums) { // 左指针 int left = 0; // 序列数值的和 int sum = 0; // 长度大小 int result = Integer.MAX_VALUE; // 让右指针不断走,直到终点 for (int right = 0; right < nums.length; right++) { sum += nums[right];
// 这里不能用if，要用while更合适。滑动窗口的本质是进行完一次运算后，起始位置移动到适合的大小，是一个持续移动到合适位置的过程。
while (sum >= s) { // 判断当前长度大小是否是历史最短 result = Math.min(result, right - left + 1); //减去左指针位置的值,让窗口向右滑动 sum -= nums[left++]; } } return result == Integer.MAX_VALUE ? 0 : result; } }
题目(LeetCode 59)
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3 输出：[[1,2,3],[8,9,4],[7,6,5]]
提示：
1 <= n <= 20
思路：
考察推导过程对代码的掌控。 要坚持循环不变量原则，要坚持左闭右开或者左开右闭的原则。
代码：
package com.dwj.LeetCode.array; public class SpiralMatrix { public static void main(String[] args) { SpiralMatrix spiralMatrix = new SpiralMatrix(); int[][] ints = spiralMatrix.generateMatrix(3); // for (int i = 0; i <ints.length ; i++) { // for (int j = 0; j <ints.length ; j++) { // System.out.println(ints[i][j]); // } // } } public int[][] generateMatrix(int n) { int[][] res = new int[n][n]; // 循环次数 int loop = n / 2; // 定义每次循环起始位置 int startX = 0; int startY = 0; // 定义偏移量。为了计算每条边上的数据个数 开始位置+n-偏移量 int offset = 1; // 定义填充数字 int count = 1; // 定义中间位置 int mid = n / 2; while (loop > 0) { int i = startX; int j = startY; // 模拟上侧从左到右 for (; j<startY + n -offset; ++j) { res[startX][j] = count++; } // 模拟右侧从上到下 for (; i<startX + n -offset; ++i) { res[i][j] = count++; } // 模拟下侧从右到左 for (; j > startY; j--) { res[i][j] = count++; } // 模拟左侧从下到上 for (; i > startX; i--) { res[i][j] = count++; } //每次结束循环次数-1 loop--; //开始位置+1 startX += 1; startY += 1; //偏移量+2 offset += 2; } if (n % 2 == 1) { res[mid][mid] = count; } return res; } }
原文地址：http://www.cnblogs.com/dwj-ngu/p/16790245.html
