算法学习随手记录

本文记录了我在算法领域系统性学习的日程、内容与个人思考。谨以此文，勉励自身。

留给我的时间不多了，我将算法学习时间规划为了大约两个月，第一个月深度学习数据结构理论体系并配合轻度刷题巩固每日所学，第二个月重度刷题加深理解并熟悉技巧，希望接下来两个月不辜负今天写下的每一个字。 —— 2023.10.24

数组

第一天 2023.10.24

为了在学习算法的同时也能对我近期的面试有些积极的影响，我从面试考察较多的数组开始。

声明和初始化

// 常用方式一
int[] nums = new int[3];
int[][] nums = new int[2][1];
​
// 常用方式二
int[] nums = {1, 2, 3};
int[][] nums = {{1,1}, {1,2}};

其中，案例中的二维数组可以看作是2行1列的矩阵，但实际上二维数组从上到下，从左到右是线性的。

在解决数组问题的思想上大多数情况都会用到双指针思想，其次为动态规划思想，那么我将先总结有关双指针衍生出来的具体算法。

原地删除算法

Lc 27.移除元素

public int removeElement(int[] nums, int val) {
    // 初始化快慢指针
    int slow = 0, fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
        // 目标元素直接舍弃
        fast++;
    }
    return slow;
}

这道题的解法就是在一次循环中快指针查找目标元素，慢指针构建新数组，最后返回慢指针的索引就是新数组的长度。

滑动窗口算法

Lc 209.长度最小的子数组

public int minSubArrayLen(int target, int[] nums) {
    // 初始化左右指针
    int left = 0, right = 0, sum = 0, len = Integer.MAX_VALUE;
    // 模拟队列实现FIFO
    while (right < nums.length) {
        sum += nums[right++];
        while (sum >= target) {
            len = Math.min(len, right - left);
            sum -= nums[left++];
        }
    }
    return len == Integer.MAX_VALUE ? 0 : len;
}

这道题是利用队列的FIFO做了一个滑动窗口，在实际编码中利用数组加左右双指针代替了队列去实现。

中心扩散算法

Lc 5.最长回文子串

public String longestPalindrome(String s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        // 奇数回文
        int len1 = expandAroundCenter(s, i, i);
        // 偶数回文
        int len2 = expandAroundCenter(s, i, i + 1);
        // 更新最大长度
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}
​
public int expandAroundCenter(String s, int left, int right) {
    // 左右指针判断是否为回文串
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

这道题基本解法是遍历字符串并对每一个字符都利用双指针做一次回文串判断，以上代码区分了奇偶，也可以直接判断重复单边扩散

那么双指针其实可以解决大部分数组题目，在以上双指针做法中我们只需要关注指针的活动区间和移动条件即可解题。数组题另一个常用的方法即动态规划，由于对二维数组比较抵触，看到动态规划就浑身难受，所以今天就先休息了，明天一定会继续研究。