算法 分类

第1章整数

二进制

剑指offerⅡ1：整数除法

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1

Weiser大约 6 分钟

第10章前缀树

剑指offerⅡ62：实现前缀树

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

Weiser大约 8 分钟

第11章二分查找

模板

y总的模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[left, right]被划分成[left, mid]和[mid + 1, right]时使用：
int bsearch_1(int left, int right)
{
    while (left < right)
    {
        int mid = left + right >> 1;
        if (check(mid)) right = mid;    // check()判断mid是否满足性质
        else left = mid + 1;
    }
    return left;
}
// 区间[left, r]被划分成[left, mid - 1]和[mid, r]时使用：
int bsearch_2(int left, int right)
{
    while (left < right)
    {
        int mid = left + right + 1 >> 1;
        if (check(mid)) left = mid;
        else right = mid - 1;
    }
    return left;
}

Weiser大约 13 分钟

第12章排序

排序的基础知识

大根堆模板

/**
 * 调整为大顶堆
 * @param arr   待调整的数组
 * @param parent   当前父节点的下标
 * @param length   需要对多少个元素进行调整
 */
private static void adjustHeap(int[] arr, int parent, int length){
    //临时保存父节点
    int temp = arr[parent];
    //左子节点的下标
    int child = 2 * parent + 1;
    //如果子节点的下标大于等于当前需要比较的元素个数，则结束循环
    while(child < length){
        //判断左子节点和右子节点的大小,若右边大，则把child定位到右边
        if(child + 1 < length && arr[child] < arr[child + 1]){
            child ++;
        }
        //若child大于父节点，则交换位置，否则退出循环
        if(arr[child] > temp){
            //父子节点交换位置
            arr[parent] = arr[child];
            //因为交换位置之后，不能保证当前的子节点是它子树的最大值，所以需要继续向下比较，
            //把当前子节点设置为下次循环的父节点，同时，找到它的左子节点，继续下次循环
            parent = child;
            child = 2 * parent + 1;
        }else{
            //如果当前子节点小于等于父节点，则说明此时的父节点已经是最大值了，
            //因此无需继续循环
            break;
        }
    }
    //把当前节点值替换为最开始暂存的父节点值
    arr[parent] = temp;
}

public static void main(String[] args) {
    int[] arr = {4,1,9,3,7,8,5,6,2};
    //构建一个大顶堆，从最下面的非叶子节点开始向上遍历
    for (int i = arr.length/2 - 1 ; i >= 0; i--) {
        adjustHeap(arr,i,arr.length);
    }
    System.out.println(Arrays.toString(arr));
}    
//打印结果：  [9, 7, 8, 6, 1, 4, 5, 3, 2]。 和我们分析的结果一模一样

Weiser大约 5 分钟

第13章回溯法

组合问题

剑指offerⅡ79：所有子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

写法一：

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new LinkedList<>();
        if(nums.length==0){
            return ans;
        }
        dfs(nums,0,new LinkedList<>(),ans);
        System.out.println(ans.toString());
        return ans;
    }

    private void dfs(int[] nums, int index, LinkedList<Integer> subset, List<List<Integer>> ans){
        if(index==nums.length){
            ans.add(new LinkedList<>(subset));
            return;
        }
        subset.add(nums[index]);		//先选择下标为index的数
        dfs(nums,index+1, subset, ans); //在选择index的情况下，确定index+1的选择情况
        subset.removeLast();			//不选择下标为index的数
        dfs(nums,index+1, subset, ans); //在不选择index的情况下，确定index+1的选择情况
    }
}

Weiser大约 8 分钟

第14章动态规划

斐波那契问题

LC70：青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2

Weiser大约 41 分钟

第15章图

图的搜索

解题小经验：

如果面试题要求在无权图中找出两个节点之间的最短距离，那么广度优先搜索可能是更适合的算法。

如果面试题要求找出符合条件的所有路径，那么深度优先搜索可能是最合适的算法。

剑指offerⅡ105：最大的岛屿

给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。

一个岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

Weiser大约 22 分钟

第2章数组

双指针

剑指offerⅡ6：排序数组的两数之和

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值*。*numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。

Weiser大约 6 分钟

第3章字符串

双指针

剑指offerⅡ14：字符串中的变位词

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        int[] counts = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            counts[s1.charAt(i) - 'a']++;
            counts[s2.charAt(i) - 'a']--;
        }
        if (isAllZero(counts)) {
            return true;
        }
        //i是右边界
        for (int i = s1.length(); i < s2.length(); i++) {
            counts[s2.charAt(i) - 'a']--;
            counts[s2.charAt(i - s1.length()) - 'a']++;
            if (isAllZero(counts)) {
                return true;
            }
        }
        return false;
    }

    private boolean isAllZero(int[] counts) {
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
}

Weiser大约 5 分钟

第4章链表

双指针

剑指offerⅡ21：删除倒数第n个节点

给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = head;
        ListNode slow = dummy;
        while (n > 0) {
            fast = fast.next;
            n--;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

Weiser大约 9 分钟

跳转到:

第1章 整数

二进制