刷题笔记分类

题目

题目描述：输出两个不超过100位的大整数的乘积。输入：输入两个大整数，如1234567 和 123 输出：输出乘积，如：151851741

例如：求 1234567891011121314151617181920 * 2019181716151413121110987654321 的乘积结果

分析

所谓大数相乘（Multiplication algorithm），就是指数字比较大，相乘的结果超出了基本类型的表示范围，所以这样的数不能够直接做乘法运算。

Cutewr大约 5 分钟

回溯

总结

不要以全局思想练回溯！

拆解成规模更小的子问题去练！

回溯就是暴力递归，暴力递归就是尝试

把问题转化为规模缩小了的同类问题的子问题
有明确的不需要继续进行递归的条件(base case)
有当得到了子问题的结果之后的决策过程
不记录每一个子问题的解

汉诺塔问题

如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

Cutewr大约 17 分钟

多路归并

合并两个有序链表【LC 21题】

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

多路归并的开胃菜：2路归并，找到两个链表中较小的那一个，加入新链表中。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy=new ListNode(0);
        ListNode cur=dummy;
        ListNode node1=list1,node2=list2;
        while(node1!=null && node2!=null){
            if(node1.val<node2.val){
                cur.next=node1;
                node1=node1.next;
            }else{
                cur.next=node2;
                node2=node2.next;
            }
            cur=cur.next;
        }
        cur.next= node1==null ? node2 : node1;
        return dummy.next;
    }
}

Cutewr大约 7 分钟

前缀和

区间和检索【LC 】

Cutewr小于 1 分钟

栈和队列

用栈实现队列【LC 232题】

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

Cutewr大约 5 分钟

双指针

移动零【LC 283题】

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。

💡 使用一个开始的指针flag来记录下一个非零元素放置的位置。遍历数组，如果数不为0，那么交换它开始元素的位置，并使flag++。

class Solution {
    public void moveZeroes(int[] nums) {
        int flag=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                int temp=nums[i];
                nums[i]=nums[flag];
                nums[flag]=temp;
                flag++;
            }
        }
    }
}

Cutewr大约 3 分钟

树

二叉树的递归遍历【LC 144 145 94题】

递归序

按照如下函数，遍历完每个节点都会经过三次。

以下图为例：首先经过recursion(2)->recursion(1)->recursion(1.left)【null 返回】->recursion(1)

recursion(1.right)【null 返回】->recursion(1)>recursion(2)【返回】
recursion(3)>recursion(3.left)【null 返回】->recursion(3)
recursion(3.right)【null 返回】->recursion(3)>recursion(2)【最终返回，方法执行完】

Cutewr大约 30 分钟

图

图的表示方式

邻接表
邻接矩阵

稀疏图适合用邻接表，稠密图适合用邻接矩阵

岛屿数量【LC 200题】

一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？【举例】 001010 111010 100100 000000 这个矩阵中有三个岛

public class NumIslands {
    public int numIslands(char[][] grid) {
        if (grid==null) return 0;
        int res=0;
        int N=grid.length;
        int M=grid[0].length;
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                if (grid[i][j]=='1'){
                    res++;
                    infect(grid,i,j,N,M);
                }
            }
        }
        return res;
    }

    private void infect(char[][] grid, int i, int j, int N, int M) {
      //我只关心这个1能在我和我的周围传递下去，如果不能就直接返回
      // 注意这个判断条件 不等于1 也传递不下去了 不要忘了
        if (i<0 || i>=N || j<0 || j>=M || grid[i][j]!='1') return;
        grid[i][j]='0';
        infect(grid,i+1,j,N,M);
        infect(grid,i,j+1,N,M);
        infect(grid,i-1,j,N,M);
        infect(grid,i,j-1,N,M);
    }
}

Cutewr大约 10 分钟

数组

二分查找【LC 704题】

我们一般定义查找区间的时候，要么是左闭右开[left,right)，要么是左闭右闭[left,right]。

在修改区间范围的时候，一定要坚持这个区间的开闭准则

左闭右闭[left,right]的写法

package Array;

public class Search {
    //左闭右闭写法
    public int search(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while (left<=right){    //注意点一：由于是左闭右闭区间，所以当left=right时，区间内还有元素
            int mid=(left+right)/2;
            if (nums[mid]==target) return mid;  
            // 注意点二 如果mid不符合条件，从区间内剔除
            else if (nums[mid]>target) right=mid-1; 
            else left=mid+1;
        }
        return -1;
    }
}

Cutewr大约 14 分钟

哈希表

两数之和【LC 1题】

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 *target* 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

Cutewr大约 8 分钟