头像

三岁


访客:1974

离线:1天前



三岁
1天前

这是题目链接

方案一(双指针)

class Solution {
  public int maxArea(int[] height) {
    int l = 0, r = height.length - 1;
    int max = Math.min(height[l], height[r]) * (r - l);
    while (l < r) {
      if (height[l] >= height[r]) r --;
      else l ++;
      max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
    }

    return max;
  }
}



三岁
1天前

这是题目链接

方案一(动态规划)

参考闫式 DP 分析法

class Solution {

  public boolean isMatch(String s, String p) {
    s = ' ' + s;
    p = ' ' + p;
    int n = s.length();
    int m = p.length();
    boolean[][] f = new boolean[n][m];
    f[0][0] = true;

    for (int i = 0; i < n; i++) {
      for (int j = 1; j < m; j++) {
        // 将 ?* 看做一组
        if (j < m - 1 && p.charAt(j + 1) == '*') {
          continue;
        }

        if (i != 0 && p.charAt(j) != '*') {
          f[i][j] = f[i - 1][j - 1] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
        } else if (p.charAt(j) == '*') {
          f[i][j] = f[i][j - 2] || (i != 0 && f[i - 1][j] && (s.charAt(i) == p.charAt(j - 1)
              || p.charAt(j - 1) == '.'));
        }
      }
    }
    return f[n - 1][m - 1];
  }
}


活动打卡代码 LeetCode 9. 回文数

三岁
1天前

这是题目链接

方案一(暴力)

简单粗暴的暴力,直接将数字转字符串。

class Solution {
    public boolean isPalindrome(int x) {
      if (x < 0) return false;
      if (x < 10) return true;

      String str = Integer.toString(x);
      int length = str.length();
      for (int i = 0; i <= length / 2; i ++) {
        if (str.charAt(i) != str.charAt(length - i - 1)) {
          return false;
        }
      }

      return true;
    }
}

方案二(整数逆序)

将数字反序(反序的是一半,而不是全部),然后比较。

class Solution {
    public boolean isPalindrome(int x) {
      // 1. 负数不可能是回文数
      // 2. 末尾为0的也不可能是回文数,因为最高位肯定不是0 (但是 0 的话就是回文数,所以要排除这个特殊情况)
      if (x < 0 || (x != 0 && x % 10 == 0)) return false;

      int s = 0;
      while (x > s) {
        s = s * 10 + x % 10;
        x /= 10;
      }

      return x == s || x == s / 10;
    }
}



三岁
2天前

这是题目链接

方案一(暴力)

class Solution {

  public int myAtoi(String str) {
    // 去除前面的空格
    int startIndex = 0;
    int length = str.length();
    int res = 0;
    int flag = 1;
    while (startIndex < length && str.charAt(startIndex) == ' ') {
      startIndex++;
    }

    char ch;
    // 如果为空串或者第一个不为空格的字符不是数字,则没办法进行解析,直接返回 0
    if (startIndex >= length || !(((ch = str.charAt(startIndex)) >= '0' || ch <= '9') || (ch == '-'
        || ch == '+'))) {
      return res;
    }

    if (ch == '-' || ch == '+') {
      if (ch == '-') {
        flag = -1;
      }
      startIndex++;
    }

    for (; startIndex < length && (ch = str.charAt(startIndex)) >= '0' && ch <= '9'; startIndex++) {
      int num = ch - '0';
      if (flag > 0 && res > (Integer.MAX_VALUE - num) / 10) {
        return Integer.MAX_VALUE;
      } else if (flag < 0 && -res < (Integer.MIN_VALUE + num) / 10) {
        return Integer.MIN_VALUE;
      }
      res = res * 10 + num;
    }

    return res * flag;
  }
}


活动打卡代码 AcWing 7. 整数反转

三岁
2天前

这是题目链接

方案一

将整数逆序增加,如果在计算的过程中超过了 int 的范围,那么就直接返回 0。y 总牛逼,自己写的垃圾代码就不展示了,虽然还是通过了,但是时间上和这个代码差几倍。

class Solution {
  public int reverse(int x) {
    int res = 0;
    while(x != 0) {
      if (x > 0 && res > (Integer.MAX_VALUE - x % 10) / 10) return 0;
      if (x < 0 && res < (Integer.MIN_VALUE - x % 10) / 10) return 0;
      res = res * 10 + x % 10;
      x /= 10;
    }
    return res;
  }
}


活动打卡代码 LeetCode 6. Z 字形变换

三岁
3天前

这是题目链接

方案一(找规律)

将字母替换为数字(从0开始,就像下标一样),然后找对应的规律。

class Solution {
    public String convert(String s, int numRows) {
      if (numRows == 1) {return s;}

      int length = s.length();
      StringBuilder sb = new StringBuilder(length);
      int step = numRows + (numRows > 2 ? numRows - 2 : 0);
      for (int i = 0; i < numRows; i++) {
        for (int j = i, k = 1; j < length; j += step, k ++) {
          sb.append(s.charAt(j));
          if (numRows > 2 && i > 0 && i < numRows - 1  && (k * step - i < length)) {
            sb.append(s.charAt(k * step - i));
          }
        }
      }

      return sb.toString();
    }
}


活动打卡代码 LeetCode 5. 最长回文子串

三岁
8天前

这是题目链接

方案一(暴力)

核心思想,找到一个字符,或者两个连续相同的字符作为中心,然后不断向两边扩展。直到两边的字符不相同。

class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        if (length <= 1) return s;

        int maxLength = 1;
        int startIndex = 0;
        int endIndex = 1;
        int l, r;
        for (int i = 0; i < length; i++) {
            // 以 i 为回文串的中心
            l = i; r = i;
            while (l >= 1 && r < length - 1 && s.charAt(l - 1) == s.charAt(r + 1)) {
                l --;
                r ++;
            }
            if (maxLength < r - l + 1) {
                maxLength = r - l + 1;
                startIndex = l;
                endIndex = r + 1;
            }

            // 如果 s[i] == s[i+1],就以 i 和 i + 1 为中心
            if (i < length - 1 && s.charAt(i) == s.charAt(i + 1)) {
                l = i;
                r = i + 1;
                while (l - 1 >= 0 && r + 1 < length && s.charAt(l - 1) == s.charAt(r + 1)) {
                    l --;
                    r ++;
                }
                if (maxLength < r - l + 1) {
                    maxLength = r - l + 1;
                    startIndex = l;
                    endIndex = r + 1;
                }
            }
        }

        return s.substring(startIndex, endIndex);
    }
}

时间复杂度:O(n^2)




三岁
9天前

这是题目链接

方案一(双指针算法)

建立两个指针,一个指向子串的起始下标,一个指向子串的结束下标。

核心思想:

如果结束下标的字符没有被占用,就将结束下标向右移动

如果结束下标的字符已经被占用了(即,在当前子串中出现了该字符),就将起始下标向右移动

class Solution {
    // 用的是 BitSet 存储子串中各个字符的占用情况,仅仅适用于子串中字符在 ASCII 码范围内
    // 如果超过这个范围,可以使用 HashMap 作为替代方案。
    BitSet bitSet = new BitSet(256);
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        for (int beginIndex = 0, endIndex = 0; endIndex < s.length(); endIndex++) {
            char ch = s.charAt(endIndex);
            while (bitSet.get(ch)) {
                bitSet.clear(s.charAt(beginIndex ++));
            }
            bitSet.set(ch);
            maxLength = Math.max(maxLength, endIndex - beginIndex + 1);
        }

        return maxLength;
    }
}

时间复杂度:因为

4. 寻找两个正序数组中的中位数

这是题目链接

错误方案一(暴力)

直接将两个数组合并,然后取中位数。最简单直接,也是最容易想到的,但是不符合题目的要求。因为题目要求时间复杂度要在 O(log(m + n)),而这种做法的时间复杂度为 O(m + n)。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        /*
            合并这两个数组
         */
        // 合并后的数组
        int[] fetchedNums = new int[nums1.length + nums2.length];
        // i 代表 fetchNums 的下标;j 代表 nums1 的下标;k 代表 nums2 的下标
        int i = 0, j = 0, k = 0;
        while (j < nums1.length && k < nums2.length) {
            if (nums1[j] <= nums2[k]) {
                fetchedNums[i ++] = nums1[j ++];
            } else {
                fetchedNums[i ++] = nums2[k ++];
            }
        }
        while (j < nums1.length) {fetchedNums[i ++] = nums1[j ++];}
        while (k < nums2.length) {fetchedNums[i ++] = nums2[k ++];}

        /*
            求合并后数组的中位数
         */
        if ((fetchedNums.length & 1) == 1) {
            return fetchedNums[fetchedNums.length / 2] / 1.0;
        } else {
            return (fetchedNums[fetchedNums.length / 2] + fetchedNums[fetchedNums.length / 2 - 1]) / 2.0;
        }
    }
}

时间复杂度:因为要将两个数组都遍历一遍,所以时间复杂度为O(m + n)

空间复杂度:因为开辟了一个新的数组来存储合并后的数组,所以空间复杂度为 O(m + n)

方案一(递归)

通过将找两个数组的中位数,转换为找两个数组中第 k 小的数。

用递归的方式,不断的排除不可能的一部分,最后得到的结果。思路在代码中有体现。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        if ((total & 1) == 0) {
            // 如果是偶数,取 (total / 2) 和 (total / 2 + 1) 的平均值
            int num1 = findKthNumber(nums1, 0, nums2, 0, total / 2);
            int num2 = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
            return (num1 + num2) / 2.0;
        } else {
            // 如果是奇数,只需要取 total / 2 + 1
            return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1) / 1.0;
        }
    }


    private int findKthNumber(int[] nums1, int i, int[] nums2, int j, int k) {
        // 保证 nums1.length <= nums2.length
        if (nums1.length - i > nums2.length - j) return findKthNumber(nums2, j, nums1, i, k);

        // 如果 nums1 中的元素都被丢弃了(可以理解为 nums1 为空),那么结果肯定为 nums2[j + k - 1]
        if (nums1.length == i) return nums2[j + k - 1];
        // 如果 k = 1,那么表示取两个数组中最小的那个值
        if (k == 1) return Math.min(nums1[i], nums2[j]);
        // 边界值处理,由于 k = nums1.length + nums2.length,又因为 nums2.length > nums1.length
        // 所以 nums1.length 可能会小于 k/2,所以如果要丢弃的话,只能丢弃 nums1.length,而不是 k/2
        int si = Math.min(i + k / 2, nums1.length), sj = j + k / 2;
        /*
            核心思路
            如果 nums1[k/2] > nums2[k/2] 那么说明 nums2 的前 k/2 中肯定不包含第 k 小的数
            反之依然,nums1[k/2] < nums2[k/2] 那么说明 nums1 的前 k/2 中肯定不包含第 k 小的数
            如果 nums1[k/2] == nums2[k/2],那么说明 nums[k/2] 和 nums2[k/2] 都有可能是第 k 小的数,所以抛弃任意一个都能得到结果
         */
        if (nums1[si - 1] > nums2[sj - 1]) {
            return findKthNumber(nums1, i, nums2, sj, k - k / 2);
        } else {
            return findKthNumber(nums1, si, nums2, j, k - si + i);
        }
    }
}

时间复杂度:由于是递归的形式,并且每次都取 k/2,所以是 O(log(m + n))。




三岁
9天前

这是题目链接

方案一(双指针算法)

建立两个指针,一个指向子串的起始下标,一个指向子串的结束下标。

核心思想:

如果结束下标的字符没有被占用,就将结束下标向右移动

如果结束下标的字符已经被占用了(即,在当前子串中出现了该字符),就将起始下标向右移动

class Solution {
    // 用的是 BitSet 存储子串中各个字符的占用情况,仅仅适用于子串中字符在 ASCII 码范围内
    // 如果超过这个范围,可以使用 HashMap 作为替代方案。
    BitSet bitSet = new BitSet(256);
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        for (int beginIndex = 0, endIndex = 0; endIndex < s.length(); endIndex++) {
            char ch = s.charAt(endIndex);
            while (bitSet.get(ch)) {
                bitSet.clear(s.charAt(beginIndex ++));
            }
            bitSet.set(ch);
            maxLength = Math.max(maxLength, endIndex - beginIndex + 1);
        }

        return maxLength;
    }
}


活动打卡代码 AcWing 2. 两数相加

三岁
14天前

2. 两数相加

这是题目链接

方案一(模拟)

模拟题,有点像是小学做加法题一样,只不过顺序是反着的。做法的话,没啥好说的。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode(0);
        ListNode res = l3;
        int c = 0;
        int sum = 0;
        while (l1 != null || l2 != null) {
            sum = c;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            l3.next = new ListNode(sum % 10);
            l3 = l3.next;
            c = sum / 10;
        }
        if (c != 0) {
            // 可能还有进位,所以需要特殊处理
            l3.next = new ListNode(c);
        }


        return res.next;
    }
}

时间复杂度:因为必须要扫完,所以时间复杂度的话是 O(n) 的

空间复杂度:因为一共要开辟 n 个节点,所以空间复杂度是 O(n) 的