跳至主要內容
第1章 整数

第1章 整数

二进制

剑指offerⅡ1:整数除法

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

注意:

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

Weiser大约 6 分钟算法整数二进制
第10章 前缀树

第10章 前缀树

剑指offerⅡ62:实现前缀树

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


Weiser大约 8 分钟算法前缀树
第11章 二分查找

第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章 排序

第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章 回溯法

第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章 动态规划

第14章 动态规划

斐波那契问题

LC70:青蛙跳台阶问题

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

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:2

Weiser大约 41 分钟算法单序列DP双序列DP矩阵路径DP背包股票
第15章 图

第15章 图

图的搜索

解题小经验:

  • 如果面试题要求在无权图中找出两个节点之间的最短距离,那么广度优先搜索可能是更适合的算法。
  • 如果面试题要求找出符合条件的所有路径,那么深度优先搜索可能是最合适的算法。

剑指offerⅡ105:最大的岛屿

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

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


Weiser大约 22 分钟算法图的搜索拓扑并查集
第2章 数组

第2章 数组

双指针

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

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

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


Weiser大约 6 分钟算法数组双指针
第3章 字符串

第3章 字符串

双指针

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

给定两个字符串 s1s2,写一个函数来判断 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章 链表

第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 分钟算法链表
2