数组

1.移除元素

https://leetcode.cn/problems/remove-element/submissions/637689538/

下面就是双指针的实现方案

    public int removeElement(int[] nums, int val) {
        int length = nums.length;
        int i = 0;
        while (i < length) {
            // 如果数组元素相等
            if (nums[i] == val) {
                // 将元素最后一个元素放到当前位置
                nums[i] = nums[length - 1];
                length--;
            } else {
                i++;
            }
        }
        return length;
    }

2.有序数组的平方

https://leetcode.cn/problems/squares-of-a-sorted-array/description/

    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int start = 0;
        int end = n - 1;
        int i = n - 1;
        while (start <= end && i >= 0) {
            if (Math.abs(nums[start]) < Math.abs(nums[end])) {
                res[i] = nums[end] * nums[end];
                end--;
            } else {
                res[i] = nums[start] * nums[start];
                start++;
            }
            i--;
        }
        return res;
    }

3.长度最小的数组

这里需要注意的是，这里是连续的子数组

      public int minSubArrayLen(int target, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int count = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            // 缩小窗口
            while (sum >= target) {
                count = Math.min(count, i - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return count == Integer.MAX_VALUE ? 0 : count;
    }

4.螺旋矩阵

https://leetcode.cn/problems/spiral-matrix-ii/description/

这里需要注意的是。边界的处理，当一条边遍历完，对应的边界也应该有处理

  public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int count = 1;
        int left = 0, right = n - 1, top = 0, bottom = n - 1;
        // 0 表示向右 1 表示向下 2 表示向左 3 表示向上
        int direction = 0;
        while (count <= n * n) {
            switch (direction) {
                // 当向右时，从左到右，
                case 0:
                    for (int i = left; i <= right; i++) {
                        matrix[top][i] = count++;
                    }
                    top++;
                    direction = 1;
                    break;
                case 1:
                    for (int i = top; i <= bottom; i++) {
                        matrix[i][right] = count++;
                    }
                    right--;
                    direction = 2;
                    break;
                case 2:
                    for (int i = right; i >= left; i--) {
                        matrix[bottom][i] = count++;
                    }
                    bottom--;
                    direction = 3;
                    break;
                case 3:
                    for (int i = bottom; i >= top; i--) {
                        matrix[i][left] = count++;
                    }
                    left++;
                    direction = 0;
                    break;
            }
        }
        return matrix;
    }

双调数组

如果一个数组中的所有元素是先递增后递减的，则称这个数组为双调的。编写一个程序，给定一个含有N 个不同int 值的双调数组，判断它是否含有给定的整数。

public class BitonicArraySearch {
    
    /**
     * 在双调数组中查找目标值
     * @param arr 双调数组
     * @param target 目标值
     * @return 目标值在数组中的索引，如果不存在返回-1
     */
    public static int searchInBitonicArray(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        
        int n = arr.length;
        
        // 1. 首先找到峰值点（双调点）
        int peakIndex = findPeakIndex(arr);
        
        // 2. 在递增部分查找
        int result = binarySearchAscending(arr, 0, peakIndex, target);
        if (result != -1) {
            return result;
        }
        
        // 3. 在递减部分查找
        return binarySearchDescending(arr, peakIndex + 1, n - 1, target);
    }
    
    /**
     * 找到双调数组的峰值索引
     */
    private static int findPeakIndex(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // 边界情况处理
            if (mid == 0) {
                if (arr.length == 1 || arr[mid] > arr[mid + 1]) {
                    return mid;
                } else {
                    left = mid + 1;
                }
            } else if (mid == arr.length - 1) {
                if (arr[mid] > arr[mid - 1]) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            } else {
                if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                    return mid; // 找到峰值
                } else if (arr[mid] > arr[mid - 1]) {
                    left = mid + 1; // 峰值在右侧
                } else {
                    right = mid - 1; // 峰值在左侧
                }
            }
        }
        
        return -1; // 理论上不会执行到这里
    }
    
    /**
     * 在递增部分进行二分查找
     */
    private static int binarySearchAscending(int[] arr, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
    
    /**
     * 在递减部分进行二分查找
     */
    private static int binarySearchDescending(int[] arr, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
    
    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试用例
        int[] bitonicArray1 = {1, 3, 8, 12, 4, 2};
        int[] bitonicArray2 = {3, 8, 10, 15, 20, 18, 12, 7};
        int[] bitonicArray3 = {5, 10, 15, 20, 25, 20, 15, 10, 5};
        
        // 测试查找
        testSearch(bitonicArray1, 8, "数组1");  // 应该找到
        testSearch(bitonicArray1, 5, "数组1");  // 应该找不到
        testSearch(bitonicArray1, 12, "数组1"); // 应该找到（峰值）
        
        testSearch(bitonicArray2, 15, "数组2"); // 应该找到
        testSearch(bitonicArray2, 25, "数组2"); // 应该找不到
        testSearch(bitonicArray2, 7, "数组2");  // 应该找到（最后一个元素）
        
        testSearch(bitonicArray3, 25, "数组3"); // 应该找到（峰值）
        testSearch(bitonicArray3, 10, "数组3"); // 应该找到（有重复值但位置不同）
    }
    
    private static void testSearch(int[] arr, int target, String arrayName) {
        int result = searchInBitonicArray(arr, target);
        if (result != -1) {
            System.out.println(arrayName + "中找到目标值 " + target + "，索引为: " + result);
        } else {
            System.out.println(arrayName + "中未找到目标值 " + target);
        }
    }
}

链表

1. 移除链表元素

 public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }

        ListNode pre = head;
        // 当下一个结点不为空的情况下
        while (pre.next != null) {
            // 如果下一个结点的值等于val，则删除下一个结点
            if (pre.next.val == val) {
                // 删除下一个结点
                pre.next = pre.next.next;
            } else {
                // 否则，将pre移到下一个结点
                pre = pre.next;
            }
        }
        return head.val == val ? head.next : head;
    }