《编程能力基础》刷题笔记（41 题）

题目：896. 单调数列

因为题目看起来很想递归，所以先送上一种递归方式:(强行递归，必须加班)

/** * 递归(超时) */ function isMonotonic(nums: number[]): boolan { 
        
    return nums[0] < nums[nums.length - 1] ?
        isMonotonicIncrease(nums) : isMonotonicDecrease(nums)
};

// 递归判断是否单调递
const isMonotonicIncrease = function (nums: number[]): boolean { 
        
    if (nums.length == 1) return true
    if (nums[0] > nums[1]) return false
    return isMonotonicIncrease(nums.slice(1)) ? true : false
}

// 递归判断是否单调减
const isMonotonicDecrease = function (nums: number[]): boolean { 
        
    if (nums.length == 1) return true
    if (nums[0] < nums[1]) return false
    return isMonotonicDecrease(nums.slice(1)) ? true : false
}

—

然后才是正文。

解法1：

• 通过 nums[0] 和 nums[1] 可以判断这个序列是 递增 还是 递减
• 明确了目标，然后只需要遍历时两两比较即可，遇到不满足条件的情况直接返回 false

/** * 通过 nums[0] 和 nums[nums.length - 1] 判断出增减方向 * 遍历数组一次，两两比较 */
public boolean isMonotonic1(int[] nums) { 
        
    // 先判断 递增 还是 递减
    if (nums[0] <= nums[nums.length - 1]) { 
         // 递增
        for (int i = 1; i < nums.length; i++) 
            if (nums[i - 1] > nums[i]) return false;
    } else { 
         // 递减
        for (int i = 1; i < nums.length; i++) 
            if (nums[i - 1] < nums[i]) return false;
    }
    return true;
}

解法2：

• 如果没有先判断出序列是 递增 还是 递减，也没关系
• 可以先假设又递增又递减，然后判断时如果遇到一个不满足条件的情况就可以排除这个假设了
• 中间如果加上一步减枝（可以快 1s）

public boolean isMonotonic(int[] nums) { 
        
    boolean inc = true, dec = true;

    for (int i = 0; i < nums.length - 1; i++) { 
        
        if (nums[i] > nums[i + 1]) inc = false;
        if (nums[i] < nums[i + 1]) dec = false;
        // 剪枝操作, 已经明确既不递增也不递减, 直接返回 false
        if (!inc && !dec) return false;
    }
    return inc || dec;
}

解法3：然后就是利用语言特性和 API 的做法了，比如 JS

var isMonotonic = function (nums) { 
        
    return isSorted(nums) || isSorted(nums.reverse())
}
// 判断是否单调增
function isSorted(nums) { 
        
    return nums.slice(1).every((item, i) => nums[i] <= item)
}

题目：28. 实现 strStr()

先来一个每个人必定会尝试一下的解法：库函数

public int strStr(String haystack, String needle) { 
        
    return haystack.indexOf(needle);
}

再来个比较常规但是会超时的暴力解法：暴力

public int strStr1(String haystack, String needle) { 
        
    if (haystack.length() < needle.length()) return -1;
    if (needle.isEmpty()) return 0;
    for (int i = 0; i < haystack.length(); i++) { 
        
        int tmpIdx = 0;
        while (i + tmpIdx < haystack.length()
            && haystack.charAt(i + tmpIdx) == needle.charAt(tmpIdx++)) 
            if (tmpIdx == needle.length()) return i;
    }
    return -1;
}

然后来个可以正常通过的解法：滑动窗口

public int strStr2(String haystack, String needle) { 
        
    if (haystack.length() < needle.length()) return -1;
    // 窗口长度
    int width = needle.length();
    // 当前索引
    int idx = 0;
    // 只访问不会越界的部分
    while (idx + width <= haystack.length()) { 
        
        // 找到则返回索引
        if (needle.equals(haystack.substring(idx, idx + width)))
            return idx;
        idx++; 
    }
    return -1;
}

至于其他比较强力的算法如 KMP 等等，待我功力深厚以后再回来将其拿下！

题目：110. 平衡二叉树

解法1：常规思路，先写一个 获取二叉树节点高度 的函数，然后对二叉树进行 遍历 + 判断

const isBalanced = function (root: TreeNode | null): boolean { 
        
    if (!root) return true
    if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1)
        return false
    return isBalanced(root.left) && isBalanced(root.right)
}
// 获取二叉树节点的高度
const getHeight = (root: TreeNode | null) => { 
        
    if (!root) return 0
    return Math.max(getHeight(root.left), getHeight(root.right)) + 1
}

解法2：这个有点难理解，其实是解法1的升级版

• 解法1一定会遍历完整个树，解法2不一定，遍历时发现不满足条件就会直接结束

const isBalanced = function (root: TreeNode | null): boolean { 
        
    return recur(root) != -1
}

const recur = function (root: TreeNode | null): number { 
        
    if (!root) return 0
    let left = recur(root.left)
    if (left == -1) return -1
    let right = recur(root.right)
    if (right == -1) return -1
    return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1
}

题目：459. 重复的子字符串

这道题比较好想的思路是模拟，但是模拟也是有讲究的，要尽量减少暴力的次数（俗称剪枝）

在我的理解中，剪枝属于一种优化，其实把剪枝部分去掉应该也可以正常运行，但是效率会变低

解法1：模拟 + 剪枝

const repeatedSubstringPattern = function (s: string): boolean { 
        
    if (s.length < 2) return false
    // 只需要遍历一半即可, 一半以后必然不能重复
    for (let i = 1; i <= s.length / 2; i++) { 
        
        let sub = s.substring(0, i)
        // 剪枝：字符串的长度不是串的整数倍, 必然不满足条件
        if (s.length % i != 0) continue
        // 剪枝：最后不是以该子串结尾, 必然不满足条件
        if (sub != s.substring(s.length - sub.length)) continue
        // 利用 repeat API, 查看是否满足满足要求
        if (sub.repeat(s.length / sub.length) == s)
            return true
    }
    return false
}

解法2：技巧

这个思路是参考其他大佬的，确实很奇妙，学习了，可以留个印象

简单明了！！关于java两行代码实现的思路来源

[1] s = acd
[2] ss = acdacd
[3] ss.substring(1, ss.length - 1) = cdac (去头去尾)
判断: [3] 中包含 [1] 则满足条件, s = 'acd' 不满足条件
---

[1] s = acaaca
[2] ss = acaacaacaaca
[3] ss.substring(1, ss.length - 1) = caacaacaac (去头去尾)
判断: [3] 中包含 [1] 则满足条件, s = 'acaaca' 满足条件

const repeatedSubstringPattern = function (s: string): boolean { 
        
    let ss = s.repeat(2)
    return ss.substring(1, ss.length - 1).indexOf(s) != -1
}

题目：150. 逆波兰表达式求值

解法1：用栈模拟，会使这道题万分简单

public int evalRPN(String[] tokens) { 
        
    Stack<Integer> stack = new Stack<>();
    for (String token : tokens) { 
        
        if ("+".equals(token)) { 
        
            Integer num1 = stack.pop();
            Integer num2 = stack.pop();
            stack.push(num2 + num1);
        } else if ("-".equals(token)) { 
        
            Integer num1 = stack.pop();
            Integer num2 = stack.pop();
            stack.push(num2 - num1);
        } else if ("*".equals(token)) { 
        
            Integer num1 = stack.pop();
            Integer num2 = stack.pop();
            stack.push(num2 * num1);
        } else if ("/".equals(token)) { 
        
            Integer num1 = stack.pop();
            Integer num2 = stack.pop();
            stack.push(num2 / num1);
        } else { 
        
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

代码丑陋，略微优化一下：（效率无影响）

public int evalRPN(String[] tokens) { 
        
    Stack<Integer> stack = new Stack<>();
    for (String token : tokens) { 
        
        if ("+".equals(token))
            stack.push(stack.pop() + stack.pop());
        else if ("-".equals(token))
            stack.push(-stack.pop() + stack.pop());
        else if ("*".equals(token))
            stack.push(stack.pop() * stack.pop());
        else if ("/".equals(token)) { 
        
            Integer num1 = stack.pop(), num2 = stack.pop();
            stack.push(num2 / num1);
        } else
            stack.push(Integer.parseInt(token));
    }
    return stack.pop();
}

解法2：用数组代替栈模拟

class Solution { 
        
    public int evalRPN(String[] tokens) { 
        
        int[] res = new int[tokens.length];
        int cur = 1; // 索引从 - 1 开始, 因为必须放进元素才能开始计算
        for (String token : tokens) { 
        
            if ("/*-+".contains(token)) { 
        
                int b = res[cur--], a = res[cur--];
                res[++cur] = calc(a, b, token);
            } else
                res[++cur] = Integer.parseInt(token);
        }
        return res[cur];
    }

    public int calc(int a, int b, String op) { 
        
        if (op.equals("+")) return a + b;
        else if (op.equals("-")) return a - b;
        else if (op.equals("*")) return a * b;
        else if (op.equals("/")) return a / b;
        else return -1;
    }
}

题目：66. 加一

解法1：最朴素的模拟做法，这个基本上是第一反映想到的