题目(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;
}
}
标签：nums,int,代码,元素,随想录,Day1,数组,public,指针 From： https://www.cnblogs.com/dwj-ngu/p/16790245.html