荒野老男人

愿你永远年轻,永远热泪盈眶

原文

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

这个题感觉又是个思路难,实现不难的题。

没想到这个题转成判断环,Floyd判圈算法

var findDuplicate = function (nums) {
    let slow = 0;
    let fast = 0;
    // step 1
    while (t...

原文

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

每行的元素从左到右升序排列。

每列的元素从上到下升序排列。

初始搜索位置设置在右上角

  1. 如果跟target相等,return true
  2. 比target大,砍掉一列
  3. 比target小,砍掉一行 直到砍光或者找到
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matr...

原文

给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值

说一下我的解法

首先第一个窗口的最大值和最大值的下标i,一个循环即可找出 窗口前移一个位置时,我们可以假设第一个窗口的最大值还在窗口范围内,那么只需要比较一下最大值和新进入窗口的这个值,会有两种情况

  1. 最大值比新值大,维持最大值和它的下标不变
  2. 新值比最大值大,那么更新最大值和坐标

为什么需要维护坐标,因为随着窗口移动,之前的最大值可能被移出窗口,移出窗口的时候,我们...

原文 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。

这个题,我的思路是先遍历整棵树,给每个节点建立parent,同时找到pq两个节点

然后把p q两个节点的所有祖先存储到数组

从后向前遍历这两个数组,找到分叉的节点

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     t...

这个题,还是用我老办法。

先把链表改成数组,然后该怎么搞就怎么搞。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = funct...

原文

在一个由 '0' 和 '1' 组成的二维矩阵内,找到只包含 '1' 的最大正方形,并返回其面积。

这个题比较有意思,我尝试一下自己想的一个方法,使用感染的方式一圈一圈扩展矩形,但是这个办法失败了,效率不够高

看了一眼评论,这题竟然可以动态规划,我没看评论的细节,自己用动态规划解题

野路子不行啊

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
    let max = 0;
    const dp = Array(...