Full Stack Netflix Clone

发表于 2024-02-22 更新于 2024-03-08 分类于 web开发

Netflix Clone

tech stack

Frontend: React
Server-side Rendering: Next.js
Styling: Tailwind CSS
Data abstraction layer: Prisma
Storage: MongoDB
Authentication: NextAuth
Deploy: Vercel
Typescript
the entire website fully

The entire website fully responsive across all devices.

function overview

credential login: username + password
profile: automatically generated once we register
homepage: loaded with a random movie-billboard
movies: load from database
favourites: add movies as favourites
botton: shows more information about the movie
play the movie
Google oauth login

How to initialize next.js and Tailwind which is going to be crucial for our styling.

Environment setup

create project

terminal:

1	npx create-next-app --typescript

set everything as default

open folder netflix-clone, enter command:

1	npm run dev

The website is running on: http://localhost:1689/

clean up the project:
remove pages/_document.tsx
remove everything in pages/index.tsx except the main function:

export default function Home() {
  return (
    <>
      <h1>Netflix Clone</h1>
    </>
  );
}

remove all the content in styles/globals.css. Get a white page with Netflix Clone.

add test.tsx in pages folder. Add the below content in test.tsx

const MyPage = () => {
    return (
        <h1>Hello New Page</h1>
    )
}

export default MyPage;

I can visit Hello New Page in http://localhost:1689/test.
Delete test.tsx, it is just a demonstration of how easy it is to use Next.js.

setup tailwind

tailwind tutorial: https://tailwindcss.com/docs/guides/nextjs

run the following commands in terminal:

1 2	npm install -D tailwindcss postcss autoprefixer npx tailwindcss init -p

Now we have tailwind.config.js and postcss.config.js. Open tailwind.config.js and write the below code (according to tailwind tutorial above):

/** @type {import('tailwindcss').Config} */
module.exports = {
  content: [
    "./app/**/*.{js,ts,jsx,tsx}",
    "./pages/**/*.{js,ts,jsx,tsx}",
    "./components/**/*.{js,ts,jsx,tsx}",
  ],
  theme: {
    extend: {},
  },
  plugins: [],
}

Write code in styles/globals.css to import tailwind styles:

1
2
3

@tailwind base;
@tailwind components;
@tailwind utilities;

enter the command npm run dev again and we can see a different web page, because the content in globals.css reset the css.

Try to change the color of netflix clone to green in the web page, just write the following code in index.tsx:

export default function Home() {
  return (
    <>
      <h1 className="text-2xl text-green-500">Netflix Clone</h1>
    </>
  );
}

Auth Screen UI

In styles/globals.css, write:

@tailwind base;
@tailwind components;
@tailwind utilities;

body {
    @apply bg-zinc-900 h-full overflow-x-hidden;
}

the web page turned to black. Add some code in globals.css:

#__next {
    @apply h-full;
}

html {
    @apply h-full;
}

create images folder in public folder and download hero.jpg and logo.png from github repository.

Create auth.tsx in pages. It is the auth page. Write the following code in it:

const Auth = () => {
    return (
        // first div: add background pictures in auth page
        // second dic: make the picture a bit darker in the large screen
        // img: set logo (NETFLIX) className="h-12" makes it smaller
        // third div: container
        <div className="relative h-full w-full bg-[url('/images/hero.jpg')] bg-no-repeat bg-center bg-fixed bg-cover"> 
            <div className="bg-black w-full h-full lg: bg-opacity-50"> 
                <nav className="px-12 py-5">
                    <img src = "/images/logo.png" alt = "Logo" className="h-12"/>
                </nav>
                <div className="flex justify-center">
                    <div className="bg-black bg-opacity-70 px-16 py-16 self-center mt-2 lg: w-2/5 lg: max-w-md rounded-md w-full">
                        <h2 className="text-white text-4xl mb-8 font-semibold">
                            Sign in
                        </h2>
                        <div className="flex flex-col gap-4">
                            
                        </div>
                    </div>
                </div>
            </div>
        </div>
    );
}

export default Auth;

create components folder and create Input.tsx. Write some codes in it:

const Input = () => {
    return (
        <input />
    )
}

export default Input;

Now add the Input in auth.tsx :

import Input from "@/components/Input";

<div className="flex flex-col gap-4">
    <Input />
</div>

Now add some floating labels in Input.tsx:

const Input = () => {
    return (
        <div className="relative">
            <input 
                className="
                    block
                    rounded-md
                    px-6
                    pt-6
                    pb-1
                    w-full
                    text-md
                    text-white
                    bg-neutral-700
                    appearance-none
                    focus: outline-none
                    focus: ring-0
                    peer
                "
                placeholder=" "
            />
        </div>
    )
}

export default Input;

现在我们想在sign in之下的第一个输入框加上Email字样，当点击输入框时，Email变小，不点击输入框时，Email变大，这是一种浮动的特效。

// duration-150: duration for animation
const Input = () => {
    return (
        <div className="relative">
            <input 
                id = "email"
                className="
                    block
                    rounded-md
                    px-6
                    pt-6
                    pb-1
                    w-full
                    text-md
                    text-white
                    bg-neutral-700
                    appearance-none
                    focus: outline-none
                    focus: ring-0
                    peer
                "
                placeholder=" "
            />
            <label 
            className="
                absolute
                text-md
                text-zinc-400
                duration-150 
                transform
                -translate-y-3
                scale-75
                top-4
                z-10
                origin-[0]
                left-6
                peer-placeholder-shown:scale-100
                peer-placeholder-shown:translate-y-0
                peer-focus:scale-75
                peer-focus:-translate-y-3   
            "
            htmlFor="email">
                Email
            </label>
        </div>
    )
}

export default Input;

接下来让输入框模块化。加入react的一些特性：

import React from 'react';

interface InputProps {
    id: string;
    onChange: any;
    value: string;
    label: string;
    type?: string;
}

// duration-150: duration for animation
const Input: React.FC<InputProps> = ({
    id,
    onChange,
    value,
    label,
    type
}) => {
    return (
        <div className="relative">
            <input 
                onChange={onChange}
                type={type}
                value={value}
                id={id}
                className="
                    block
                    rounded-md
                    px-6
                    pt-6
                    pb-1
                    w-full
                    text-md
                    text-white
                    bg-neutral-700
                    appearance-none
                    focus: outline-none
                    focus: ring-0
                    peer
                "
                placeholder=" "
            />
            <label 
            className="
                absolute
                text-md
                text-zinc-400
                duration-150 
                transform
                -translate-y-3
                scale-75
                top-4
                z-10
                origin-[0]
                left-6
                peer-placeholder-shown:scale-100
                peer-placeholder-shown:translate-y-0
                peer-focus:scale-75
                peer-focus:-translate-y-3   
            "
            htmlFor="id">
                {label}
            </label>
        </div>
    )
}

export default Input;

此时发现auth.tsx报错，在input处加入以下代码：

<Input
    label="Email"
    onChange={() => {}}
    id="email"
    type="email"
    value=""
/>

我们发现网页上的输入框无法输入内容，在auth.tsx中加入以下代码来解决这个问题：

import { useState } from "react"
import Input from "@/components/Input";

const Auth = () => {
    const [email, setEmail] = useState('');
    
    label="Email"
    onChange={(ev) => setEmail(ev.target.value)}
    id="email"
    type="email"
    value={email}

现在就可以在网页端的输入框内打字了。然后将上述内容复制两次，制造出username和password的输入框。

const [name, setName] = useState('');
const [password, setPassword] = useState('');

<Input
    label="Username"
    onChange={(ev: any) => setName(ev.target.value)}
    id="name"
    value={name}
/>

<Input
    label="Password"
    onChange={(ev: any) => setPassword(ev.target.value)}
    id="password"
    type="password"
    value={password}
/>

接下来写按钮login botton：

1
2
3

<button className="bg-red-600 py-3 text-white rounded-md w-full mt-10 hover:bg-red-700 transition">
    Login
</button>

产生了一个红色的按钮，点击按钮颜色会变深。

接着

<p className="text-neutral-500 mt-12">
    First time using Netflix?
    <span className="text-white ml-1 hover:underline cursor-pointer">
        Create account
    </span>
</p>

接着在login和register之间产生一个跳转。

const [variant, setVariant] = useState('login');

const toggleVariant = useCallback(() => {
    setVariant((currentVarient) => currentVarient === 'login' ? 'register': 'login')
}, [])

<span onClick={toggleVariant} className="text-white ml-1 hover:underline cursor-pointer">
    Create account
</span>

接着再将原本的login改为{variant === 'login' ? 'Sign in': 'Register'}。这样点击create account就会在sign in和register之间切换。由于在sign in时不需要看到username，而在register时要输入username，因此将username包裹在register中：

{variant === 'register' && (
<Input
    label="Username"
    onChange={(ev: any) => setName(ev.target.value)}
    id="name"
    value={name}
/>
)}

接着让按钮在sign in时显示为login，在register时显示为sign up。

1
2
3

<button className="bg-red-600 py-3 text-white rounded-md w-full mt-10 hover:bg-red-700 transition">
    {variant === 'login' ? 'Login': 'Sign up'}
</button>

接着让login界面中显示提示语：First time using Netflix. Create account。在register页面中显示提出语：Already have an account?Login.

<p className="text-neutral-500 mt-12">
    {variant === 'login' ? 'First time using Netflix?' : 'Already have an account?'}
    <span onClick={toggleVariant} className="text-white ml-1 hover:underline cursor-pointer">
        {variant === 'login' ? 'Create account' : 'Login'}
    </span>
</p>

NextAuth, Prisma, Mongo Setup

将上述登录注册的UI界面通过prisma连接到mongodb。先在vscode中安装扩展prisma，其可以帮助对prisma文件进行格式化和高亮。接着在终端输入命令：npm install -D prisma

再输入命令：npx prisma init，本命令可以产生一个schema.prisma文件。将其中的数据库修改为mongodb:

generator client {
  provider = "prisma-client-js"
}

datasource db {
  provider = "mongodb"
  url      = env("DATABASE_URL")
}

接着在终端输入：npm install @prisma/client。接着再创建新的文件夹lib。在其中创建prismadb.ts文件，写入以下代码：

import { PrismaClient } from '@prisma/client';

const client = global.prismadb || new PrismaClient();

if (process.env.NODE_ENV === 'production') global.prismadb = client;

export default client;

next.js具有特性：hot reloading。每次代码改变时，我们的项目自动更新并重新运行。对prisma而言，每次会产生若干个PrismaClient实例，就会得到报错：已经有若干个Prisma Client正在运行。我们将PrismaClient存储在一个全局文件中，而全局文件并不会被hot reloading影响，因此就不会产生上面的报错。接着来解决prismadb标红的错误。

根目录下创建文件global.d.ts，在其中定义prismadb，写入以下内容：

import { PrismaClient } from '@prisma/client';

declare global {
    namespace globalThis {
        var prismadb: PrismaClient
    }
}

接着进入schema.prisma文件，填入DATABASE_URL。需要先进入.env文件，将其中的database url换成有效的url。在谷歌中搜索mongodb atlas，注册并登录。点击build a database。我的database的username是cyf，密码是20001017。IP地址点击add my current IP address即可。接着在overview页面点击connect，选择mongodb for vscode。复制它给出的URL并粘贴到.env文件中。需要将URL中的<password>替换为自己真实的密码。并在URL的末尾加上我的实际数据库的名字：

1	DATABASE_URL="mongodb+srv://cyf:20001017@cluster0.38xordg.mongodb.net/Cluster0"

接着，在schema.prisma文件中一次性定义好所有的models（数据模型）。因为反复修改数据模型和运行项目可能会导致一些麻烦和报错。schema.prisma文件内容如下所示：

// This is your Prisma schema file,
// learn more about it in the docs: https://pris.ly/d/prisma-schema

// Looking for ways to speed up your queries, or scale easily with your serverless or edge functions?
// Try Prisma Accelerate: https://pris.ly/cli/accelerate-init

generator client {
  provider = "prisma-client-js"
}

datasource db {
  provider = "mongodb"
  url      = env("DATABASE_URL")
}

model User {
  id String @id @default(auto()) @map("_id") @db.ObjectId // 每个model都需要这一行，因为mongodb的model一定需要定义id
  name String
  image String? // ?表示可选，可要可不要
  email String? @unique // 非必须，可能用到oauth login
  emailVerified DateTime?
  hashedPassword String? // 密码登录所需要
  createAt DateTime @default(now())
  updateAt DateTime @updatedAt // 自动更新 更新时间
  favoriteIds String[] @db.ObjectId // 用户最喜欢的电影
  sessions Session[]
  accounts Account[]
}

// 用于Google Account或者GitHub Account
model Account {
  id String @id @default(auto()) @map("_id") @db.ObjectId
  userId String @db.ObjectId // account和userid之间的关系
  type String
  provider String
  providerAccountId String
  refresh_token String? @db.String
  access_token String? @db.String
  expires_at Int?
  token_type String?
  scope String?
  id_token String? @db.String
  session_state String?

  // 将account model和user model之间通过userId连接, onDelate表示二者的删除是同步的(user被删除了，account也被删除)
  user User @relation(fields: [userId], references: [id], onDelete: Cascade)

  @@unique([provider, providerAccountId]) // 独一无二，不允许重复
}

model Session {
  id String @id @default(auto()) @map("_id") @db.ObjectId
  sessionToken String @unique
  userId String @db.ObjectId
  expires DateTime

  user User @relation(fields: [userId], references: [id], onDelete: Cascade)
}

model VerificationToken {
  id String @id @default(auto()) @map("_id") @db.ObjectId
  identifier String
  token String @unique
  expires DateTime

  @@unique([identifier, token])
}

model Movie {
  id String @id @default(auto()) @map("_id") @db.ObjectId
  title String
  description String
  videoUrl String
  thumbnailUrl String // 缩略网址
  genre String // 类型
  duration String
}

接着在终端运行命令：npx prisma db push，将schema.prisma文件中定义的数据模型上传到云端，在mongodb的网页端选择database-browse collections，即可看到定义的5个数据模型。这说明prisma已经成功和mongodb连接起来了。

接着进入pages/api/hello.ts，可以通过链接：http://localhost:1689/api/hello访问到其中的内容。删除hello.ts，新建`[...nextauth].ts`文件，其会被next app识别。我们在这个文件中写next auth的middleware。通过命令npm install next-auth安装next-auth。还需要运行命令：npm install bcrypt。这个包用于用户名密码登录。在[...nextauth].ts文件中写下以下的内容：

import NextAuth from 'next-auth';
import Credentials from 'next-auth/providers/credentials';
import { compare } from 'bcrypt';

import prismadb from '@/lib/prismadb';

export default NextAuth({
    providers: [
        Credentials({
            id: 'credentials',
            name: 'Credentials',
            credentials: {
                email: {
                    label: 'Email',
                    type: 'text',
                },
                password: {
                    label: 'Password',
                    type: 'password',
                }
            },
            async authorize(credentials) {
                if (!credentials?.email || !credentials?.password) {
                    throw new Error('Email and password required');
                }
                
                // 通过email找到用户，需要import prismadb
                const user = await prismadb.user.findUnique({
                    where: {
                        email: credentials.email
                    }
                });

                // 判断找到的user是否存在
                if (!user || !user.hashedPassword) {
                    throw new Error('Email does not exist');
                }

                // 判断用户输入的密码是否正确
                const isCorrectPassword = await compare(
                    credentials.password, 
                    user.hashedPassword
                );

                if (!isCorrectPassword) {
                    throw new Error("Incorrect password"); 
                }

                return user; // 用户密码输入正确，则返回由email找到的唯一user
            }
        })
    ],

    pages: {
        signIn: '/auth',
    },
    // debug on
    debug: process.env.NODE_ENV === 'development',

    session: {
        strategy: 'jwt',
    },
})

在.env文件中加入以下两个环境变量：

1 2	NEXTAUTH_JWT_SECRET = "NEXT-JWT-SECRET" NEXTAUTH_SECRET = "NEXT-SECRET"

在[...nextauth].ts文件中添加以下的内容：

    jwt: {
        secret: process.env.NEXTAUTH_JWT_SECRET,
    },
    secret: process.env.NEXTAUTH_SECRET,
});

接下来修复bcrypt标红的报错。在终端输入命令：npm i -D @types/bcrypt。安装了bcrypt后，不再标红报错。

进入pages/auth.tsx。在其中添加login和register的函数。首先通过命令行安装axios: npm i axios。然后在auth.tsx中引入axios并定义register函数：

import axios from "axios";

// register function
const register = useCallback(async () => {

}, []); // dependency: []

接着写下完整的register函数：

// register function
const register = useCallback(async () => {
    try {
        await axios.post('/api/register', {
            email,
            name,
            password
        });
    } catch (error) {
        console.log(error);
    }
}, []); // dependency: []

接着在pages/api中定义register。在register.ts中写下了如下的代码：

import bcrypt from 'bcrypt';
import { NextApiRequest, NextApiResponse } from 'next';
import prismadb from '@/lib/prismadb';

export default async function handler(req: NextApiRequest, res: NextApiResponse) {
    if (req.method !== 'POST') {
        return res.status(405).end(); // we only want to allow post calls to /api/register
    }

    // try and catch block
    // try: extract some values from request.body
    try {
        const { email, name, password } = req.body;

        // check if an email is already in use
        const existinguser = await prismadb.user.findUnique({
            where: {
                email,
            }
        });

        // email in use, return Email taken
        if (existinguser) {
            return res.status(422).json({error: 'Email taken'});
        }

        // hash the password
        const hashedPassword = await bcrypt.hash(password, 12);

        // 将user信息存入数据库
        const user = await prismadb.user.create({
            data: {
                email,
                name,
                hashedPassword,
                image: '',
                emailVerified: new Date(),
            }
        });

        return res.status(200).json(user);
    } catch (error) {
        console.log(error);
        return res.status(400).end();
    }
}

这就完成了/api/register。在auth.tsx中填入dependency的具体内容：[email, name, password]); // dependency in []。

接着，我们需要在点击sign up按钮时呼叫/api/register。先不管按钮上写的是login还是register，将按钮统一绑定到register函数：

1 2	<button onClick={register} className="bg-red-600 py-3 text-white rounded-md w-full mt-10 hover:bg-red-700 transition"> {variant === 'login' ? 'Login': 'Sign up'}

打开网页，F12打开调试模式，选择network，输入用户名、邮箱和密码，可以看到register函数被成功调用。接着打开mongodb atlas的网站，选择database-browse collections-user，可以看到其中添加了一条用户信息的数据，成功！到此，用户名密码注册部分完成了。

现在开始做Login部分。在auth.tsx中添加以下login函数：

// login function
const login = useCallback(async () => {
    // try and catch block
    try {
        // 需要用到[..nextauth].ts中的Credentials
        await signIn('credentials', {
            email,
            password,
            redirect: false,
            callbackUrl: '/'
        });
    } catch (error) {
        console.log(error);
    }
}, [email, password]); // login only need email and password

接着在按钮处调用login函数：

1	<button onClick={variant === 'login' ? login : register} className="bg-red-600 py-3 text-white rounded-md w-full mt-10 hover:bg-red-700 transition">

这样就可以在点击login按钮时调用login函数，在点击sign up按钮时调用register函数。点击login按钮，网页并没有产生预期的跳转，打印出错误信息：Error: This action with HTTP GET is not supported by NextAuth.js。尝试修复这个问题。在api文件夹中再创建auth文件夹，将[...nextauth].ts文件拖拽到其中。然后这个问题就被修复了。接着继续在login函数中添加router：

const router = useRouter(); 

// login function
const login = useCallback(async () => {
    // try and catch block
    try {
        // 需要用到[..nextauth].ts中的Credentials
        await signIn('credentials', {
            email,
            password,
            redirect: false,
            callbackUrl: '/'
        });

        router.push('/'); 
    } catch (error) {
        console.log(error);
    }
}, [email, password, router]); // login only need email and password, and then we add router

接着在register函数中添加login部分，一旦注册成功后就自动登录。

// register function
const register = useCallback(async () => {
    try {
        await axios.post('/api/register', {
            email,
            name,
            password
        });

        login();
    } catch (error) {
        console.log(error);
    }
}, [email, name, password, login]); // dependency in []

同时注意调整login和register函数的顺序，让login定义在register之前（因为register中需要调用login函数）。现在再次尝试输入邮箱和密码并点击login按钮，发现可以成功跳转到根目录。

Google and Github OAuth

加入Google and Github OAuth非常简单。首先在终端中运行命令：npm install react-icons。通过这个包可以向项目中添加Google, Github和其他炫酷的icon。接下来写google和github一键登录的UI界面。在auth.tsx中加入以下代码。首先是引入react中包含icons的包，然后在login/sign up按钮下定义一个div，用于空出更大的空间。再定义一个div，用于存放按钮。在这个div中定义按钮的各种属性（居中、圆角等）。最后再通过FcGoogle引入Google的图标。接着，我们复制上面的代码，将图标改为Github。以上的代码如下所示：

import { FcGoogle } from 'react-icons/fc';
import { FaGithub } from 'react-icons/fa';

<div className="flex flex-row items-center gap-4 mt-8 justify-center">
    <div
        className="
            w-10
            h-10
            bg-white
            rounded-full
            flex
            items-center
            justify-center
            cursor-pointer
            hover:opacity-80
            transition
        "
    >
        <FcGoogle size={30} />
    </div>

    <div
        className="
            w-10
            h-10
            bg-white
            rounded-full
            flex
            items-center
            justify-center
            cursor-pointer
            hover:opacity-80
            transition
        "
    >
        <FaGithub size={30} />
    </div>
</div>

接着进入.env文件中增加一些环境变量。如下所示：

GITHUB_ID=
GITHUB_SECRET=

GOOGLE_CLIENT_ID=
GOOGLE_CLIENT_SECRET=

接着在[...nextauth].ts文件中添加包和GithubProvider、GoogleProvider。

import GithubProvider from 'next-auth/providers/github';
import GoogleProvider from 'next-auth/providers/google';

GithubProvider({
    clientId: process.env.GITHUB_ID || '',
    clientSecret: process.env.GITHUB_SECRET || ''
}),
GoogleProvider({
    clientId: process.env.GOOGLE_CLIENT_ID || '',
    clientSecret: process.env.GOOGLE_CLIENT_SECRET || ''
}),

接着执行命令：npm install @next-auth/prisma-adapter。接着在[...nextauth].ts文件中添加以下代码：

1
2
3

import { PrismaAdapter } from '@next-auth/prisma-adapter';

adapter: PrismaAdapter(prismadb),

接下来填入.env文件中的GITHUB_ID和GITHUB_SECRET。去到GITHUB-SETTINGS-DEVELOPER SETTINGS-OAUTH APPS-NEW OAUTH APP，填入以下内容：

Register a new OAuth application
Application name
netflix-clone

Homepage URL
http://localhost:1689

Authorization callback URL
http://localhost:1689

接着点击register application，然后将生成的GITHUB_ID和GITHUB_SECRET复制到.env文件中。

现在我们在auth.tsx中给github一键登录写一个函数:

1	onClick={() => signIn('github', { callbackUrl: '/' })}

并在.env文件中指定重定向URL的路径：NEXTAUTH_URL=http://localhost:10564/
进行上述操作后，github一键登录成功，一键登录成功后被导航回到了根目录。然后可以在mongodb的account中看到一条新的数据。本来应该在user中也看到一条新的数据，但我的user中没有github一键登录产生的新user的数据。这个问题在github的issues中有解释：https://github.com/AntonioErdeljac/next-netflix-tutorial/issues/13。这个问题应该不是一个问题，不用担心。

现在开始完成google一键登录。相比于github，Google会更麻烦些。进入google cloud console: https://console.cloud.google.com/welcome?pli=1&project=advance-proton-400620。新建项目并填入项目名称，点创建。选中该项目，搜索apis & services。选择oauth权限请求页面，选择外部，点击创建。填入应用名称、用户支持电子邮件、开发者联系信息，然后保存并继续。然后一路点击保存并继续。点击凭据-创建凭据-创建 OAuth 客户端 ID。选择web应用-添加URL：http://localhost:10564/api/auth/callback/google。我们就可以得到client ID和client secret。将它们复制到.env文件中。然后在auth.tsx中给google一键登录写一个函数:

1	onClick={() => signIn('google', { callbackUrl: '/' })}

在网页端尝试点击google一键登录，成功！

Protecting routes, Profiles screen

如何通过授权登录保护client路径和api路径。在lib文件夹中创建serverAuth.ts。在其中写下如下的代码：

import { NextApiRequest } from 'next';
import { getSession } from 'next-auth/react'; 

import prismadb from '@/lib/prismadb';
import { error } from 'console';

const serverAuth = async (req: NextApiRequest) => {
    // fetch log in user session
    const session = await getSession({ req });

    // use serverAuth in api controller
    // req parameter  will hold jwt token to get logged in user
    // use session to get other fields
    if (!session?.user?.email) {
        throw new Error('Not signed in');
    }

    // 通过email找到不同的user
    const currentUser = await prismadb.user.findUnique({
        where: {
            email: session.user.email,
        }
    });

    // 无currentUser, 说明jwt token或者session不正确或者过期了
    if (!currentUser) {
        throw new Error('Not signed in');
    }

    return { currentUser };
}

export default serverAuth;

用上述文件可以在所有的api routes中检查我们是否登录。进入pages/api中，创建current.ts，在其中写上以下的代码：

import { NextApiRequest, NextApiResponse } from 'next';

import serverAuth from '@/lib/serverAuth';

export default async function handler(req: NextApiRequest, res: NextApiResponse) {
    if (req.method !== 'GET') {
        return res.status(405).end();
    }

    // try and catch block
    try {
        const { currentUser } = await serverAuth(req); 

        return res.status(200).json(currentUser);
    } catch (error) {
        console.log(error);
        return res.status(400).end();
    }
}

下面开始写用于front end fetching的部分，在libs/fetcher.ts，在其中写下代码：

import axios from 'axios';

const fetcher = (url: string) => axios.get(url).then((res) => res.data);

export default fetcher;

在前端写用于载入当前用户的代码。在根目录下新建hooks文件夹，在其中新建文件useCurrentUser.ts。然后在终端中运行命令：npm install swr。然后在useCurrentUser.ts中写入：

import useSWR from 'swr';

import fetcher from '@/lib/fetcher';

// svr: versal developed package, which is good at fetching data
// If the data already exists, we are not going to fetch the data again
const useCurrentUser = () => {
    const { data, error, isLoading, mutate } = useSWR('/api/current', fetcher)

    return {
        data,
        error,
        isLoading,
        mutate
    }
};

export default useCurrentUser;

下面我们来展示如何保护client routes。我们想让用户在不登陆的情况下访问不到我们的网站。在pages/index.tsx中首先创建一个sign out按钮。

1	<button className="h-10 w-full bg-white" onClick={() => signOut()}>Logout!</button>

接下来我们来演示如何在pages/index.tsx中保护家路径。在其中写下以下的代码：

import { NextPageContext } from "next";
import { getSession, signOut } from "next-auth/react";

// fetch our session from client side
// cannot use serverAuth
export async function getServerSideProps(context: NextPageContext) {
  const session = await getSession(context);

  // session不存在，则返回登录界面
  if (!session) {
    return {
      redirect: {
        destination: '/auth',
        permanent: false,
      }
    }
  }

  // session存在，则返回空
  return {
    props: {}
  }
}

export default function Home() {
  return (
    <>
      <h1 className="text-4xl text-green-500">Netflix Clone</h1>
      <button className="h-10 w-full bg-white" onClick={() => signOut()}>Logout!</button>
    </>
  );
}

现在实现了功能：用户不能在未登录的情况下直接访问家目录。现在的问题：登出以后无法登录并进入到家目录。进入mongodb-network access。点击add ip address，选择allow access from anywhere。目前项目仍然不能正常登录。报错信息显示：

[next-auth][error][CLIENT_FETCH_ERROR] 
https://next-auth.js.org/errors#client_fetch_error fetch failed {
  error: {
    message: 'fetch failed',
    stack: 'TypeError: fetch failed\n' +
      '    at node:internal/deps/undici/undici:12443:11\n' +
      '    at process.processTicksAndRejections (node:internal/process/task_queues:95:5)',
    name: 'TypeError'
  },
  url: 'http://localhost:10564/api/auth/session',
  message: 'fetch failed'
}

我尝试了若干种解决办法，最后是这样解决的：
由于在默认情况下，port和forwarded address是不同的，这样就会导致上面的报错，我猜测是产生了跨域问题，导致port和forwarded address之间的信息转发失败了。我们需要将port和forwarded address的端口号改成相同的，并在.env文件和package.json文件中做出相应的修改。以我在本项目中的实际操作为例。我将port改为10564，将forwarded address也改为10564（vscode-PORTS中会自动补全为localhost:10564），然后在.env文件中添加：

1	NEXTAUTH_URL="http://localhost:10564"

在package.json文件中添加：

"scripts": {
"dev": "next dev -p 10564",
"start": "next start -p 10564",
},

然后重启项目，就可以成功地通过用户名密码/github/google登入登出根页面了。

接下来关注如何通过useCurrentUser.ts中的hook来获取用户信息。在index.tsx中加入以下代码：

import useCurrentUser from "@/hooks/useCurrentUser";

const { data : user } = useCurrentUser();

<p className="text-white">Logged in as : {user?.email}</p>

这样在根页面就会显示Logged in as + 登录用户邮箱的信息。现在我们来创建用户档案页面。在pages文件夹下创建profiles.tsx文件，在其中加入以下框架：

const Profiles = () => {
    return (
        <div>
            <p className="text-white text-4xl">Profiles</p>
        </div>
    )
};

export default Profiles;

接着访问http://localhost:10564/profiles，就可以看到白色的Profiles字样。接着在`profiles.tsx`文件中写`fetch session`的代码：

// fetch our session from client side, just like  what we do in index.tsx
export async function getServerSideProps(context: NextPageContext) {
    const session = await getSession(context); // get session

    if (!session) {
        return {
            redirect: {
                destination: '/auth',
                permanent: false,
            }
        }
    }

    return {
        props: {}
    }
}

接着在auth.tsx中，将三个登录处的重定向URL重定向到profiles页面并删除router。现在产生了效果：在未登录时访问profiles页面会被重定向到auth页面。在auth页面登录后会被重定向到profiles页面。从github仓库中下载default blue图片，作为用户的默认头像。在profiles.tsx中写下了如下的代码：

const Profiles = () => {
    const { data: user } = useCurrentUser();

    return (
        <div className="flex items-center h-full justify-center">
            <div className="flex flex-col">
                <h1 className="text-3xl md:text-6xl text-white text-center" >Who is watching?</h1>
                <div className="flex items-center justify-center gap-8 mt-10">
                    <div onClick={() => {}}>

                        <div className="group flex-row w-44 mx-auto">
                            <div
                                className="
                                w-44
                                h-44
                                rounded-md
                                flex
                                items-center
                                justify-center
                                border-2
                                border-transparent
                                group-hover:cursor-pointer
                                group-hover:border-white
                                overflow-hidden
                                "
                            >
                                <img src="/images/default-blue.png" alt="Profile" />
                            </div>
                            <div
                                className="
                                mt-4
                                text-gray-400
                                text-2xl
                                text-center
                                group-hover:text-white
                                "
                            >
                                {user?.name}
                            </div>
                        </div>
                    </div>
                </div>
            </div>
        </div>
    )
};

产生了如下的效果：

然后让点击图片会重定向回到根网页。增加以下代码即可：

1
2
3

const router = useRouter()

<div onClick={() => router.push('/')}>

Navagation Component

清理index.tsx文件，只剩下骨架即可（不需要按钮和sign out功能）：

import { NextPageContext } from "next";
import { getSession } from "next-auth/react";

// fetch our session from client side
// cannot use serverAuth
export async function getServerSideProps(context: NextPageContext) {
  const session = await getSession(context);

  // session不存在，则返回登录界面
  if (!session) {
    return {
      redirect: {
        destination: '/auth',
        permanent: false,
      }
    }
  }

  // session存在，则返回空
  return {
    props: {}
  }
}

export default function Home() {

  return (
    <>
    </>
  );
}

我们需要在上述文件中添加Navbar，但目前Navbar尚不存在，因此需要在components文件夹中添加Navbar.tsx。

const Navbar = () => {
    return (
        <div>
            Navbar
        </div>
    )
}

export default Navbar;

然后在index.tsx中import并添加Navbar。接下来在Navbar.tsx中写入具体的内容。

const Navbar = () => {
    return (
        // navigation type
        <nav className="w-full fixed z-40">
            <div
                className="
                    px-4
                    md:px-16
                    py-6
                    flex
                    flex-row
                    items-center
                    transition
                    duration-500
                    bg-zinc-900
                    bg-opacity-90
                "
            >
                <img className="h-4 lg:h-7" src="/images/logo.png" alt="Logo" />
                <div
                    className="
                    flex-row
                    ml-8
                    gap-7
                    hidden
                    lg:flex
                    "
                >
                    <NavbarItem />
                </div>
            </div>
        </nav>
    )
}

export default Navbar;

接着在components中定义NavbarItem.tsx，写出其骨架：

const NavbarItem = () => {
    return (
        <div>

        </div>
    )
}

export default NavbarItem;

接着丰满其中的细节：

import React from 'react';

interface NavbarItemProps {
    label: string;

}

const NavbarItem: React.FC<NavbarItemProps> = ({
    label
}) => {
    return (
        <div className="text-white cursor-pointer hover:text-gray-300 trasition">
            {label}
        </div>
    )
}

export default NavbarItem;

需要从Navbar.tsx中传入label: <NavbarItem label="Home" />，并依照同样的方式创建另外几个导航组件：

<NavbarItem label="Home" />
<NavbarItem label="Series" />
<NavbarItem label="Films" />
<NavbarItem label="New & Popular" />
<NavbarItem label="My List" />
<NavbarItem label="Browse by languages" />

<div className="lg:hidden flex flex-row items-center gap-2 ml-8 cursor-pointer relative">
    <p className="text-white text-sm">Browse</p>
</div>

小屏幕时，只出现Browse，不出现其他navagation component。接着去查找icons: https://react-icons.github.io/react-icons/。找到一个向下展开的小箭头，在`Navbar.tsx`中引入并使用这个小箭头：

1
2
3

import { BsChevronDown } from 'react-icons/bs';

<BsChevronDown className="text-white transition" />

接着创建手机端（小屏幕）的菜单。先在components中创建MobileMenu.tsx，在其中写以下的代码：

import React from 'react';

interface MobileMenuProps {
    visible?: boolean;
}

const MobileMenu: React.FC<MobileMenuProps> = ({ visible }) => {
    if (!visible) {
        return null;
    }

    return (
        <div className="bg-black w-56 absolute top-8 left-0 py-5 flex-col border-2 border-gray-800 flex">
            <div className='flex flex-col gap-4'>
                <div className='px-3 text-center text-white hover:underline'>
                    Home
                </div>
            </div>
        </div>
    )
};

export default MobileMenu;

然后在Navbar.tsx中引入MobileMenu。并实现手机（小屏幕）上点击browse展开出home的功能。

const [showMobileMenu, setShowMobileMenu] = useState(false);

const toggleMobileMenu = useCallback(() => {
    setShowMobileMenu((current) => !current);
}, []);

<MobileMenu visible={showMobileMenu} />

对于上述代码的解释：这段代码是使用React Hooks编写的，主要用于在React组件中管理和切换移动设备菜单的显示状态。具体来说，这段代码定义了一个状态变量showMobileMenu和一个切换该状态的函数toggleMobileMenu。下面是这段代码的详细解释：

useState 钩子

1	const [showMobileMenu, setShowMobileMenu] = useState(false);

useState是一个React Hook，允许在函数组件中添加状态。这里，它被用来定义一个名为showMobileMenu的状态变量，用于跟踪移动菜单是否显示。该状态的初始值为false，意味着菜单默认是不显示的。
setShowMobileMenu是一个函数，用于更新showMobileMenu状态的值。当调用这个函数并传入一个新的值时，组件会重新渲染，并且showMobileMenu的值会更新为传入的新值。

useCallback 钩子

1
2
3

const toggleMobileMenu = useCallback(() => {
    setShowMobileMenu((current) => !current);
}, []);

useCallback是另一个React Hook，它返回一个记忆化的回调函数。这个回调函数只会在依赖项数组（这里是空数组[]）中的值发生变化时才会更新。在这个例子中，由于依赖项数组为空，toggleMobileMenu函数在组件的整个生命周期内保持不变。
toggleMobileMenu函数的作用是调用setShowMobileMenu来切换showMobileMenu状态的值。它通过传递一个函数给setShowMobileMenu，这个函数接收当前的状态值current作为参数，并返回其相反值!current。这样，如果菜单当前是显示的（true），调用toggleMobileMenu会将其隐藏（设为false），反之亦然。

总结

这段代码的主要目的是控制移动菜单的显示状态。通过点击或触发某个事件来调用toggleMobileMenu函数，可以在显示和隐藏移动菜单之间切换，从而为用户提供一个响应式的导航体验。这种模式在开发响应式Web应用时非常常见，特别是在需要改进移动设备上的用户界面和交互时。

进入MobileMenu.tsx中，加入一些新的class。

<div className='px-3 text-center text-white hover:underline'>
    Home
</div>
<div className='px-3 text-center text-white hover:underline'>
    Series
</div>
<div className='px-3 text-center text-white hover:underline'>
    Films
</div>
<div className='px-3 text-center text-white hover:underline'>
    New & Popular
</div>
<div className='px-3 text-center text-white hover:underline'>
    My List
</div>
<div className='px-3 text-center text-white hover:underline'>
    Browse by Languages
</div>

这样点开browse就会展开上述的内容。接下来是profile menu。首先在导航组件中添加一个search（即一个放大镜形状的图标）。再添加一个铃铛，最后添加用户的默认头像，然后在用户头像处也添加一个向下展开的箭头。在Navbar.tsx中使用如下代码：

<div className="flex flex-row ml-auto gap-7 items-center">
    <div className="text-gray-200 hover:text-gray-300 cursor-pointer transition">
        <BsSearch />
    </div>
    <div className="text-gray-200 hover:text-gray-300 cursor-pointer transition">
        <BsBell />
    </div>
    <div className="flex flex-row items-center gap-2 cursor-pointer relative">
        <div className="w-6 h-6 lg:w-10 lg:h-10 rounded-md overflow-hidden">
            <img src="/images/default-blue.png" alt="" />
        </div>
        <BsChevronDown className="text-white transition" />
    </div>
</div>

再添加AccountMenu。先在components中定义AccountMenu.tsx，在其中写一个骨架：

const AccountMenu = () => {
    return (
        <div>

        </div>
    )
}

export default AccountMenu;

然后再在Navbar.tsx中引入AccountMenu。在AccountMenu.tsx中写入具体的内容：

import { signOut } from "next-auth/react";
import React from "react";

interface AccountMenuProps {
    visible: boolean;

}

const AccountMenu: React.FC<AccountMenuProps> = ({
    visible
}) => {
    if (!visible) {
        return null;
    }

    return (
        <div className="bg-black w-56 absolute top-14 right-0 py-5 flex-col border-2 border-gray-800 flex">
            <div className="flex flex-col gap-3">
                <div className="px-3 group/item flex flex-row gap-3 items-center w-full">
                    <img className="w-8 rounded-md" src="/images/default-blue.png" alt="" />
                    <p className="text-white text-sm group-hover/item:underline">
                        Username
                    </p>
                </div>
            </div>
        </div>
    )
}

export default AccountMenu;

在Navbar.tsx中加入<AccountMenu visible/>，让AccountMenu。接下来再在AccountMenu.tsx中加入signOut按钮。

return (
    <div className="bg-black w-56 absolute top-14 right-0 py-5 flex-col border-2 border-gray-800 flex">
        <div className="flex flex-col gap-3">
            <div className="px-3 group/item flex flex-row gap-3 items-center w-full">
                <img className="w-8 rounded-md" src="/images/default-blue.png" alt="" />
                <p className="text-white text-sm group-hover/item:underline">
                    Username
                </p>
            </div>
            <hr className="bg-gray-600 border-0 h-px my-4" />
            <div onClick={() => signOut()} className="px-3 text-center text-white text-sm hover:underline">
                Sign out of Netflix
            </div>
        </div>
    </div>
)

然后还需要加入展开AccountMenu和收起AccountMenu的功能。在Navbar.tsx中加入代码：

const [showAccountMenu, setShowAccountMenu] = useState(false);

const toggleAccountMenu = useCallback(() => {
        setShowAccountMenu((current) => !current);
    }, []);
    

<div onClick={toggleAccountMenu} className="flex flex-row items-center gap-2 cursor-pointer relative">
    <div className="w-6 h-6 lg:w-10 lg:h-10 rounded-md overflow-hidden">
        <img src="/images/default-blue.png" alt="" />
    </div>
    <BsChevronDown className="text-white transition" />
    <AccountMenu visible={showAccountMenu} />
</div>

然后加入旋转控制AccountMenu展开和收起的箭头的功能。

1	<BsChevronDown className={`text-white transition ${showAccountMenu ? `rotate-180` : `rotate-0`}`} />

同理，对控制browse的箭头也做相同的处理。

1	<BsChevronDown className={`text-white transition ${showMobileMenu ? `rotate-180` : `rotate-0`}`} />

现在想加一个特效：向下滑动时页面变黑，其他情况下页面透明。在Navbar.tsx中加入以下代码：

const [showBackground, setShowBackground] = useState(false);

useEffect(() => {
    const handleScroll = () => {
        if (window.scrollY >= TOP_OFFSET) {
            setShowBackground(true);
        } else {
            setShowBackground(false);
        }
    }

window.addEventListener('scroll', handleScroll); // listen to scroll event

return () => {
    window.removeEventListener('scroll', handleScroll); // remove listener
}
}, []);

    <nav className="w-full fixed z-40">
        <div
            className={`
                px-4
                md:px-16
                py-6
                flex
                flex-row
                items-center
                transition
                duration-500
                ${showBackground ? 'bg-zinc-900 bg-opacity-90' : ''}

            `}

加上这些代码后，当滚动页面时，导航组件都是透明的，但当开始滑动鼠标滚轮时，导航组件的背景变为黑色。
可以在index.sh中添加代码来测试这个功能：

export default function Home() {

  return (
    <>
      <Navbar />
      <div className="bg-gray-500">
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      <div className="h-96"></div>
      </div>
    </>
  );
}

添加完上述代码后，页面可以滚动，发现功能是正常的。

Billboard Component, Random Movie Endpoint

每次会随机加载一部电影。进入github仓库，打开movies.json。将其中的电影全部加入到数据库中。

[
   {
      "title":"Big Buck Bunny",
      "description":"Three rodents amuse themselves by harassing creatures of the forest. However, when they mess with a bunny, he decides to teach them a lesson.",
      "videoUrl":"http://commondatastorage.googleapis.com/gtv-videos-bucket/sample/BigBuckBunny.mp4",
      "thumbnailUrl":"https://upload.wikimedia.org/wikipedia/commons/7/70/Big.Buck.Bunny.-.Opening.Screen.png",
      "genre":"Comedy",
      "duration":"10 minutes"
   },
   {
      "title":"Sintel",
      "description":"A lonely young woman, Sintel, helps and befriends a dragon, whom she calls Scales. But when he is kidnapped by an adult dragon, Sintel decides to embark on a dangerous quest to find her lost friend Scales.",
      "videoUrl":"http://commondatastorage.googleapis.com/gtv-videos-bucket/sample/Sintel.mp4",
      "thumbnailUrl":"http://uhdtv.io/wp-content/uploads/2020/10/Sintel-3.jpg",
      "genre":"Adventure",
      "duration":"15 minutes"
   },
   {
      "title":"Tears of Steel",
      "description":"In an apocalyptic future, a group of soldiers and scientists takes refuge in Amsterdam to try to stop an army of robots that threatens the planet.",
      "videoUrl":"http://commondatastorage.googleapis.com/gtv-videos-bucket/sample/TearsOfSteel.mp4",
      "thumbnailUrl":"https://mango.blender.org/wp-content/uploads/2013/05/01_thom_celia_bridge.jpg",
      "genre":"Action",
      "duration":"12 minutes"
   },
   {
      "title":"Elephant's Dream",
      "description":"Friends Proog and Emo journey inside the folds of a seemingly infinite Machine, exploring the dark and twisted complex of wires, gears, and cogs, until a moment of conflict negates all their assumptions.",
      "videoUrl":"http://commondatastorage.googleapis.com/gtv-videos-bucket/sample/ElephantsDream.mp4",
      "thumbnailUrl":"https://download.blender.org/ED/cover.jpg",
      "genre":"Sci-Fi",
      "duration":"15 minutes"
   }
]

上述json文件中的数据格式和schema.prisma中的movies数据类型中定义的内容相同，除了缺少由mongodb产生的id。在mongodb网站中选择database-browse collections-movie-insert document，将json文件中的内容粘贴进去即可。现在就完成了对数据模型movie的修改。

现在创建一条新的路径：random。在pages/api/random.ts中写下以下的代码：

// random movie will be loaded every time we refresh the page
import { NextApiRequest, NextApiResponse } from "next";

import prismadb from '@/lib/prismadb';
import serverAuth from "@/lib/serverAuth";

export default async function handler(req: NextApiRequest, res: NextApiResponse) {
    // limit request method to GET
    if (req.method !== 'GET') {
        return res.status(405).end();
    }

    // try and catch block
    try {
        // check if the user log in
        await serverAuth(req);

        const movieCount = await prismadb.movie.count();
        const randomIndex = Math.floor(Math.random() * movieCount); // a random integar

        const randomMovies = await prismadb.movie.findMany({
            take: 1,
            skip: randomIndex
        });

        return res.status(200).json(randomMovies[0]); // take only one movies
    } catch (error) {
        console.log(error);
        return res.status(400).end();
    };
}

在hooks/useBillboard.ts中写下以下的代码，避免对首页推荐电影的重复加载：

import useSWR from "swr";

import fetcher from "@/lib/fetcher";

const useBillboard =() => {
    const { data, error, isLoading } = useSWR('/api/random', fetcher, {
        // static data only load once the user visits the page
        // not every time they lose focus out of the window
        revalidateIfStale: false,
        revalidateOnFocus: false,
        revalidateOnReconnect: false,
    });

    return {
        data,
        error,
        isLoading,
    }
}

export default useBillboard;

在components中新建Billboard.tsx，并在其中搭建一个骨架：

import React from "react";

const Billboard = () => {
    return (
        <div>

        </div>
    )
}

export default Billboard;

然后在index.tsx中引入Billboard。接着在Billboard.tsx中填入具体的内容，目的是fetch the data for a random movie。

import useBillboard from "@/hooks/useBillboard";
import React from "react";

const Billboard = () => {
    const { data } = useBillboard();
    return (
        <div>

        </div>
    )
}

export default Billboard;

可以打开网页的调试界面：network-random-preview，就可以看到随机选择的电影的信息。接着继续写Billboard.tsx，在Billboard中添加随机的电影、电影名、电影介绍和More info按钮：

import useBillboard from "@/hooks/useBillboard";
import React from "react";

import { AiOutlineInfoCircle } from "react-icons/ai";

const Billboard = () => {
    const { data } = useBillboard();
    return (
        <div className="relative h-[56.25vw]">
            <video
                className="
                    w-full
                    h-[56.25vw]
                    object-cover
                    brightness-[60%]
                "
                autoPlay
                muted
                loop
                poster={data?.thumbnailUrl}
                src={data?.videoUrl}>
            </video>
            <div className="absolute top-[30%] md:top-[40%] ml-4 md:ml-16">
                <p className="
                    text-white
                    text-1xl 
                    md:text-5xl 
                    h-full 
                    w-[50%] 
                    lg:text-6xl 
                    font-bold 
                    drop-shadow-xl
                    ">
                    {data?.title}
                </p>
                <p className="
                    text-white
                    text-[8px]
                    md:text-lg
                    mt-3
                    md:mt-8
                    w-[90%]
                    md:w-[80%]
                    lg:w-[50%]
                    drop-shadow-xl
                ">
                    {data?.description}
                </p>
                <div className="flex flex-row items-center mt-3 md:mt-4 gap-3">
                    <button
                        className="
                            bg-white
                            text-white
                            bg-opacity-30
                            rounded-md
                            py-1 md:py-2
                            px-2 md:px-4
                            w-auto
                            text-xs lg:text-lg
                            font-semibold
                            flex
                            flex-row
                            items-center
                            hover:bg-opacity-20
                            transition
                        "
                    >
                        <AiOutlineInfoCircle className="mr-1" />
                        More Info
                    </button>
                </div>
            </div>
        </div>
    )
}

export default Billboard;

本节到此结束，效果图如下所示：

补充

await和async的区别和联系：在TypeScript中，async和await关键字一起使用，作为处理异步操作的一种方式，主要用于替代传统的回调函数和Promise。它们两者之间有着明确的区别和各自的用途：

async

async关键字用于声明一个异步函数，它让函数自动返回一个Promise。这意味着，当你在一个函数声明前加上async，这个函数就会返回一个Promise，而不是直接返回值。
使用async，你可以在函数内部使用await表达式。
async函数可以包含零个或多个await表达式。

例子：

async function fetchData() {
  // 函数返回一个Promise
  return "data";
}

在这个例子中，fetchData函数返回一个解析为字符串”data”的Promise。

await

await关键字用于等待一个Promise解析，它只能在async函数内部使用。
当await前面的Promise被解析后，函数执行会继续，await表达式的结果就是Promise解析的值。
使用await可以让异步代码看起来像是同步代码，这使得代码更容易理解和维护。

例子：

async function showData() {
  const data = await fetchData(); // 等待fetchData解析
  console.log(data);
}

在这个例子中，showData函数内部调用了fetchData函数，并在其Promise解析之后继续执行，打印出解析后的数据。

总结

async是一个使函数返回Promise的修饰符，而await是用于等待Promise解析的操作符。
await只能在async函数内部使用。
它们一起使用提供了一种更简洁和直观的方式来处理JavaScript中的异步操作，避免了回调地狱（Callback Hell）的问题。

Movie List & Movie Card Components, Movies Endpoint, Cool hover effect

在pages/api中创建一个新的movies文件夹。在其中创建index.ts，并在其中写入这个api的具体内容：

import { NextApiRequest, NextApiResponse } from "next";

import prismadb from '@/lib/prismadb';
import serverAuth from '@/lib/serverAuth';

export default async function handler(req: NextApiRequest, res: NextApiResponse) {
    // this api call only get request method
    if (req.method !== 'GET') {
        return res.status(405).end();
    }

    // try and catch block
    try {
        await serverAuth(req); // authenticate this route

        // load all the movies
        const movies = await prismadb.movie.findMany();

        return res.status(200).json(movies);
        
    } catch (error) {
        console.log(error);
        return res.status(400).end();
    } 
}

接着再创建一个hook。在hook文件夹中创建useMovieList.ts。并写入以下代码：

import useSWR from "swr";
import fetcher from "@/lib/fetcher";

const useMovieList = () => {
    const { data, error, isLoading }  = useSWR('api/movies', fetcher, {
        // 不需要重新验证
        revalidateIfStale: false,
        revalidateOnFocus: false,
        revalidateOnReconnect: false,
    });

    return {
        data,
        error,
        isLoading
    }
};

export default useMovieList;

接着进入pages/index.tsx，加入以下代码：

1
2
3

<div className="pb-40">
	<MovieList />
</div>

由于我们有多个MovieList，因此需要将MovieList包裹在div中。接着我们创建MovieList。在components中创建MovieList.tsx，并在其中搭建一个骨架：

const MovieList = () => {
    return (
        <div></div>
    )
}

export default MovieList;

接着丰满其中的细节：

import React from "react";

import { isEmpty } from 'lodash';

interface MovieListProps {
    data: Record<string, any>[]; // type: array
    title: string;
}

const MovieList: React.FC<MovieListProps> = ({ data, title }) => {
    // do not render empty data
    if (isEmpty(data)) {
        return null;
    }
    return (
        <div className="px-4 md:px-12 mt-4 space-y-8">
            <div>
                <p className="text-white text-md md:text-xl lg:text-2xl font-semibold mb-4">
                    {title}
                </p>

                <div className="grid grid-cols-4 gap-2">
                    {data.map((movie) => (
                        <div key={movie.id}>movie</div>
                    ))}
                </div>
            </div>
        </div>
    )
}

export default MovieList;

记得安装必要的库：

1 2	npm install lodash npm install -D @types/lodash

接着在pages/index.tsx中给MovieList传入必要的参数：

const { data: movies = [] } = useMovieList(); // use the newly created hook
<div className="pb-40">
    <MovieList title="Trending Now" data={movies} />
</div>

产生了如下效果：

现在将黑色的movies小字转换成实际的电影，并用上炫酷的Tailwind hover效果。在MovieList.tsx中加入下面的代码：

1	<MovieCard key={movie.id} data={movie} />

接着在components文件夹中创建MovieCard.tsx文件。填入以下的骨架：

import React from "react";

interface MovieCardProps {
    data: Record<string, any>;
}

const MovieCard: React.FC<MovieCardProps> = ({
    data
}) => {
    return (
        <div>
            
        </div>
    )
}

export default MovieCard;

接着继续丰满上述代码的细节：

import React from "react";
import { BsFillPlayFill } from "react-icons/bs";

interface MovieCardProps {
    data: Record<string, any>;
}

const MovieCard: React.FC<MovieCardProps> = ({
    data
}) => {
    return (
        <div className="group bg-zinc-900 col-span relative h-[12vw]">
            <img 
            className="
            cursor-pointer
            object-cover
            transition
            duration
            shadow-xl
            rounded-md
            group-hover:opacity-90
            sm:group-hover:opacity-0
            delay-300
            w-full
            h-[12vw]
            "
            src={data.thumbnailUrl} alt="Thumbnail" />
            <div
                className="
                    opacity-0
                    absolute
                    top-0
                    transition
                    duration-200
                    z-10
                    invisible
                    sm:visible
                    delay-300
                    w-full
                    scale-0
                    group-hover:scale-110
                    group-hover:-translate-y-[6vw]
                    group-hover:translate-x-[2vw]
                    group-hover:opacity-100
                "
            >
                <img 
                className="
                    cursor-pointer
                    object-cover
                    transition
                    duration
                    shadow-xl
                    rounded-t-md
                    w-full
                    h-[12vw]
                "
                src={data.thumbnailUrl} alt="Thumbnail" />
                <div
                    className="
                        z-10
                        bg-zinc-800
                        p-2
                        lg:p-4
                        absolute
                        w-full
                        transition
                        shadow-md
                        rounded-b-md
                    "
                >
                    <div className="flex flex-row items-center gap-3">
                        <div
                            className="
                            cursor-pointer
                            w-6
                            h-6
                            lg:w-10
                            lg:h-10
                            bg-white
                            rounded-full
                            flex
                            justify-center
                            items-center
                            transition
                            hover:bg-neutral-300
                            "
                        onClick={() => {}}>
                            <BsFillPlayFill size={30} />
                        </div>
                    </div>

                    <p className="text-green-400 font-semibold mt-4">
                        New <span className="text-white">2024</span>
                    </p>

                    <div className="flex flex-row mt-4 gap-2 items-center">
                        <p className="text-white text-[10px] lg:text-sm">{data.duration}</p>
                    </div>

                    <div className="flex flex-row mt-4 gap-2 items-center">
                        <p className="text-white text-[10px] lg:text-sm">{data.genre}</p>
                    </div>
                </div>
            </div>
        </div>
    )
}

export default MovieCard;

最后实现的效果图如下所示：

Favourites / My List functionality

本节我们将实现favourite按钮，其在播放按钮的旁边。我们还将在Trending List下面实现My List，其中将只展示我们favourite的电影。在pages/api/favorite.ts中写下以下的代码：

// can handle both post request and delete request
// api to add and remove favourite ID in our list
import { NextApiRequest, NextApiResponse } from "next";
import { without } from "lodash";

import prismadb from '@/lib/prismadb';
import serverAuth from "@/lib/serverAuth";

export default async function handler(req: NextApiRequest, res: NextApiResponse) {
    // try and catch block
    try {
        // handle post request
        if (req.method === 'POST') {
            const { currentUser } = await serverAuth(req); // get curent user

            const { movieId } = req.body; // get movieId

            // check if the movieId is correct
            const existingMovie = await prismadb.movie.findUnique({
                where: {
                    id: movieId,
                }
            });

            if (!existingMovie) {
                throw new Error('Invalid ID');
            }

            // update user and push movieId to their favoriteIds defined in schema.prisma
            const user = await prismadb.user.update({
                where: {
                    email: currentUser.email || '',
                },
                data: {
                    favoriteIds: {
                        push: movieId,
                    }
                }
            });

            return res.status(200).json(user);
        }

        // handle delete request when a user want to unfavorite a movie
        if (req.method === 'DELETE') {
            const { currentUser } = await serverAuth(req);

            const { movieId } = req.body;

            const existingMovie = await prismadb.movie.findUnique({
                where: {
                    id: movieId,
                }
            });

            if (!existingMovie) {
                throw new Error('Invalid ID');
            }

            // a list of our current favorite IDs without the above movie id
            const updateFavoriteIds = without(currentUser.favoriteIds, movieId);

            // update User information
            const updatedUser = await prismadb.user.update({
                where: {
                    email: currentUser.email || '',
                },
                data: {
                    favoriteIds: updateFavoriteIds,
                }
            });

            return res.status(200).json(updatedUser);
        }

        return res.status(405).end(); 
    } catch (error) {
        console.log(error);
        return res.status(400).end();
    }
}

接下来创建一个api route，其将只加载我们最喜欢的电影列表。在pages/api/favorites.ts，写下如下的代码：

// fetch all of our favorite movies
import { NextApiRequest, NextApiResponse } from "next";

import prismadb from '@/lib/prismadb';
import serverAuth from "@/lib/serverAuth";

export default async function handler(req:NextApiRequest, res: NextApiResponse) {
    // limit this route only to get method
    if (req.method !== 'GET') {
        return res.status(405).end();
    }

    // try and catch block
    try {
        const { currentUser } = await serverAuth(req);

        // find all movies which have a relation to current user favorite IDs
        const  favoriteMovies  = await prismadb.movie.findMany({
            where: {
                id: {
                    in: currentUser?.favoriteIds,
                }
            }
        });

        return res.status(200).json(favoriteMovies);
        
    } catch (error) {
        console.log(error);
        return res.status(400).end();
    }
}

接着再写一个hook，用于加载最喜欢的电影列表。在hooks/useFavorites.ts中写入以下的代码：

import useSWR from "swr";
import fetcher from "@/lib/fetcher";

const useFavorites = () => {
    const { data, error, isLoading, mutate } = useSWR('/api/favorites', fetcher, {
        revalidateIfStale: false,
        revalidateOnFocus: false,
        revalidateOnReconnect: false,
    });

    return {
        data,
        error,
        isLoading,
        mutate
    }
};

export default useFavorites;

再写一个组件：components/FavoriteButton.tsx，作为按钮：

import axios from "axios";
import React, { useCallback, useMemo } from "react";

import useCurrentUser from "@/hooks/useCurrentUser";
import useFavorites from "@/hooks/useFavorites";

interface FavoriteButtonProps {
    movieId: string;
}

// only one parameter: movieId
const FavoriteButton: React.FC<FavoriteButtonProps> = ({ movieId }) => {
    return (
        <div>

        </div>
    )
}

export default FavoriteButton;

将该按钮加在MovieCard中。在components/MovieCard.tsx中的播放按钮之后加入：

1	<FavoriteButton movieId={data?.id} />

补充知识：在JavaScript和TypeScript中，?操作符在这个上下文中被用作可选链（Optional Chaining）操作符。当你在一个对象后面加上?后跟属性名或方法，这意味着如果这个对象存在（即不是null或undefined），则会尝试访问该属性或方法；如果对象是null或undefined，则不会尝试访问该属性或方法，而是直接返回undefined。这避免了在访问深层嵌套对象属性时可能出现的类型错误。

接着写components/FavoriteButton.tsx：

import axios from "axios";
import React, { useCallback, useMemo } from "react";
import { AiOutlinePlus  } from "react-icons/ai";

import useCurrentUser from "@/hooks/useCurrentUser";
import useFavorites from "@/hooks/useFavorites";

interface FavoriteButtonProps {
    movieId: string;
}

// only one parameter: movieId
const FavoriteButton: React.FC<FavoriteButtonProps> = ({ movieId }) => {
    return (
        <div className="
            cursor-pointer
            group/item
            w-6
            h-6
            lg:w-10
            lg:h-10
            border-white
            border-2
            rounded-full
            flex
            justify-center
            items-center
            transition
            hover:border-neutral-300
        ">
            <AiOutlinePlus className="text-white" size ={25} />
        </div>
    )
}

export default FavoriteButton;

然后在Trending Now列表以外再创建一个My Favorites列表。进入pages/index.tsx中，增加以下的代码：

1
2
3

const { data: favorites = [] } = useFavorites(); // use hook to get favorite movies

<MovieList title="My List" data={favorites} />

由于目前还没有最喜欢的电影，因此My List为空。在FavoriteButton.tsx中添加以下代码：

const { mutate: mutateFavorites } = useFavorites();
const { data: currentUser, mutate } = useCurrentUser();

// check if the favorite list of current user includes movieId
const isFavorite = useMemo (() => {
    const list = currentUser?.favoriteIds || [];

    return list.include(movieId);
}, [currentUser, movieId]); // dependency in []

// once we click the favorite, we will check if the current movie is favorited
// if yes, trigger the delete request
// if no, add the movie in the favorite list
const toggleFavorites = useCallback(async () => {
    let response;

    if (isFavorite) {
        response = await axios.delete('/api/favorite', { data: { movieId }});
    } else {
        response = await axios.post('/api/favorite', { movieId });
    }

    // update the favorite list of current user
    const updatedFavoriteIds = response?.data?.favoriteIds;

    // mutate用于更新currentUser数据
    mutate({
        ...currentUser, // 复制了currentUser对象中的所有属性到一个新对象中
        // 如果currentUser对象中已经存在favoriteIds属性，这一操作将会覆盖原有的值。如果不存在，就会添加一个新的favoriteIds属性
        favoriteIds: updatedFavoriteIds,
    });

    mutateFavorites(); // 来自useFavorites中的mutate，每次更新currentUser的favoriteIds的数据后，立即刷新
}, [movieId, isFavorite, currentUser, mutate, mutateFavorites]);

实现了上述函数后，我们要让favorite按钮变得可交互。添加以下代码：

const Icon = isFavorite ? AiOutlineCheck : AiOutlinePlus;

return (
    <div 
        onClick={toggleFavorites}
    className="
        cursor-pointer
        group/item
        w-6
        h-6
        lg:w-10
        lg:h-10
        border-white
        border-2
        rounded-full
        flex
        justify-center
        items-center
        transition
        hover:border-neutral-300
    ">
        <Icon className="text-white" size ={25} />
    </div>
)

这样点击Trending Now列表上的电影上的加号时，其就会被添加到My List，然后加号会变成勾。这样一部电影就被选择为favorite了。同理，在My List中点击打勾符号，电影就会被取消选中，从My List里面消失。但目前该功能还是有bug。解决方法似乎是：https://github.com/nextauthjs/next-auth/issues/7199，需要将getSession替换为getServerSession。替换后问题得到了解决。

详细解决步骤：在[..nextauth].ts中添加AuthOptions，然后在serverAuth.ts中使用getServerSession替换getSession，并给getServerSession传入三个参数：req, res, authOptions，最后在所有用到serverAuth的api中将const { currentUser } = await serverAuth(req)替换为const { currentUser } = await serverAuth(req, res);。即可以修复上述bug。

Play Button, Video Player, Single Movie Endpoint

在billboard中加入播放按钮。还要创建player route。

首先创建pages/api/movies/[movieId].ts，在其中写入代码：

import { NextApiRequest, NextApiResponse } from "next";

import prismadb from '@/lib/prismadb';
import serverAuth from "@/lib/serverAuth";

export default async function handler(req: NextApiRequest, res: NextApiResponse) {
    // limit to get request
    if (req.method !== 'GET') {
        return res.status(405).end();
    }

    // try and catch block
    try {
        await serverAuth(req, res);

        const { movieId } = req.query; // search for movie Id

        if (typeof movieId !== 'string') {
            throw new Error('Invalid ID');
        }

        if (!movieId) {
            throw new Error('Invalid ID');
        }

        // find movie using movieId
        const movie = await prismadb.movie.findUnique({
            where: {
                id: movieId
            }
        });

        if (!movie) {
            throw new Error('Invalid ID');
        }

        return res.status(200).json(movie);
    } catch (error) {
        console.log(error);
        return res.status(400).end();
    }
}

接着创建一个hook。创建hooks/useMovie.ts，在其中写入代码：

import useSWR from "swr";
import fetcher from "@/lib/fetcher";

// parameter: id，该id会被/api/movies/[movieId].ts中的[movieId]解析
const useMovie = (id?: string) => {
    const { 
        data, 
        error, 
        isLoading 
    } = useSWR(id ? `/api/movies/${id}` : null, fetcher, {
        revalidateIfStale: false,
        revalidateOnFocus: false,
        revalidateOnReconnect: false
    });

    return {
        data,
        error,
        isLoading,
    }
}

export default useMovie;

接着创建一个play按钮的component。创建components/PlayButton.tsx，在其中写入骨架：

import React from "react";
import { BsFillPlayFill } from "react-icons/bs";
import { useRouter } from 'next/router';

interface PlayButtonProps {
    movieId: string;
}

const PlayButton: React.FC<PlayButtonProps> = ({ movieId }) =>{
    const router = useRouter();

    return (
        <div>

        </div>
    )
};

export default PlayButton;

接着在components/Billboard.tsx中加入上述组件。在写有more info字样的按钮前加入：<PlayButton movieId={data?.id} />。接着继续丰满components/PlayButton.tsx中的细节：

import React from "react";
import { BsFillPlayFill } from "react-icons/bs";
import { useRouter } from 'next/router';

interface PlayButtonProps {
    movieId: string;
}

const PlayButton: React.FC<PlayButtonProps> = ({ movieId }) =>{
    const router = useRouter();

    return (
        <button
            onClick={() => router.push(`/watch/${movieId}`)}
            className="
                bg-white
                rounded-md
                py-1 md:py-2
                px-2 md:px-4
                w-auto
                text-xs lg:text-lg
                font-semibold
                flex
                flex-row
                items-center
                hover:bg-neutral-300
                transition
            "
        >
            <BsFillPlayFill size={25} className="mr-1" />
            Play
        </button>
    )
};

export default PlayButton;

现在就实现了点击播放按钮，跳转到另一个页面。接着在MovieCard组件中也实现上述点击播放然后跳转的功能。进入components/MovieCard.tsx，在其中添加代码：

1
2
3

import { useRouter } from 'next/router';
const router = useRouter();
onClick={() => router.push(`/watch/${data?.id}`)}>

现在需要具体写跳转到的页面。开始写/watch页面。创建pages/watch/[movieId].tsx，在其中写入以下的骨架：

// outside of api folder, so this is a client route
import React from "react";

import useMovie from "@/hooks/useMovie";
import { useRouter } from "next/router";

const Watch = () => {
    const router = useRouter();
    const { movieId } = router.query;

    const { data } = useMovie(movieId as string);

    return (
        <div>

        </div>
    )
}

export default Watch;

现在点击播放按钮，会跳转到一个空白页面。继续丰满上述代码：

// outside of api folder, so this is a client route
import React from "react";
import { AiOutlineArrowLeft } from "react-icons/ai";
import useMovie from "@/hooks/useMovie";
import { useRouter } from "next/router";

const Watch = () => {
    const router = useRouter();
    const { movieId } = router.query;

    const { data } = useMovie(movieId as string);

    return (
        <div className="h-screen w-screnn bg-black">
            <nav
                className="
                    fixed
                    w-full
                    p-4
                    z-10
                    flex-row
                    items-center
                    gap-8
                    bg-black
                    bg-opacity-70
                "
            >
                <AiOutlineArrowLeft onClick={() => router.push('/')} className="text-white cursor-pointer" size={40} />
                <p className="text-white text-1xl md:text-3xl font-bold">
                    <span className="font-light">
                        Watching:
                    </span>
                    {data?.title}
                </p>
            </nav>
            <video
                autoPlay
                controls
                className="h-full w-full"
                src={data?.videoUrl}></video>
        </div>
    )
}

export default Watch;

现在就实现了功能：点击播放按钮，跳转到播放视频的页面，播放视频的页面会自动加载视频的名字，并有一个返回按钮，点击之可以返回到homepage。播放视频的页面中的视频可以播放、暂停、拖动时间条。

点击More Info按钮，会显示电影的信息。在Treanding Now下面会加一个展开按钮，会展开电影相关的信息。

创建hooks/useInfoModel.ts，并通过命令npm install zustand安装新的库。zustand是一个轻量化的全局状态管理库。在useInfoModel.ts中写入以下的代码：

import { create } from "zustand";

export interface ModalStoreInterface {
    movieId?: string;
    isOpen: boolean;
    openModal: (movieId: string) => void;
    closeModal: () => void;
};

// hook
const useInfoModal = create<ModalStoreInterface>((set) => ({
    movieId: undefined,
    isOpen: false,
    openModal: (movieId: string) => set({ isOpen: true, movieId }),
    closeModal: () => set({ isOpen: false, movieId: undefined}),
}));

export default useInfoModal;

创建components/InfoModal.tsx，写入以下的代码：

import React, { useCallback, useEffect, useState} from "react";
import { AiOutlineClose } from "react-icons/ai"; // close Button

import PlayButton from "./PlayButton"; // PlayButton
import FavoriteButton from "./FavoriteButton";
import useInfoModal from "@/hooks/useInfoModal";
import useMovie from "@/hooks/useMovie";

interface InfoModalProps {
    visible?: boolean;
    onClose: any;
};

const InfoModal: React.FC<InfoModalProps> = ({ visible, onClose }) => {
    // a state for visible, visible is boolean so !! before it
    const [isVisible, setIsVisible] = useState(!!visible);

    // fetch moveId
    const { movieId } = useInfoModal();
    // fetch data from movie
    const { data = {} } = useMovie(movieId);

    // use Effect
    useEffect(() => {
        setIsVisible(!!visible); // set visible on every new visible change that we get
    }, [visible]); // visible in dependency

    const handleClose = useCallback(() => {
        setIsVisible(false);
        // a cool animation
        setTimeout(() => {
            onClose();
        }, 300); // 300 ms 
    }, [onClose]);

    if (!visible) {
        return null;
    }

    return (
        <div>

        </div>
    )
}

export default InfoModal;

在pages/index.tsx中加入InfoModal：

1 2	import InfoModal from "@/components/InfoModal"; <InfoModal visible onClose={() => {}} />

接下来继续丰满InfoModal.tsx：

import React, { useCallback, useEffect, useState} from "react";
import { AiOutlineClose } from "react-icons/ai"; // close Button

import PlayButton from "./PlayButton"; // PlayButton
import FavoriteButton from "./FavoriteButton";
import useInfoModal from "@/hooks/useInfoModal";
import useMovie from "@/hooks/useMovie";

interface InfoModalProps {
    visible?: boolean;
    onClose: any;
};

const InfoModal: React.FC<InfoModalProps> = ({ visible, onClose }) => {
    // a state for visible, visible is boolean so !! before it
    const [isVisible, setIsVisible] = useState(!!visible);

    // fetch moveId
    const { movieId } = useInfoModal();
    // fetch data from movie
    const { data = {} } = useMovie(movieId);

    // use Effect
    useEffect(() => {
        setIsVisible(!!visible); // set visible on every new visible change that we get
    }, [visible]); // visible in dependency

    const handleClose = useCallback(() => {
        setIsVisible(false);
        // a cool animation
        setTimeout(() => {
            onClose();
        }, 300); // 300 ms 
    }, [onClose]);

    if (!visible) {
        return null;
    }

    return (
        <div
            className="
                z-50
                transition
                duration-300
                bg-black
                bg-opacity-80
                flex
                justify-center
                items-center
                overflow-x-hidden
                overflow-y-auto
                fixed
                inset-0
            "
        >
            <div
                className="
                    relative
                    w-auto
                    mx-auto
                    max-w-3xl
                    rounded-md
                    overflow-hidden
                "
            >

                <div 
                    className={`
                        ${isVisible ? 'scale-100': 'scale-0'}
                        transform
                        duration-300
                        relative
                        flex-auto
                        bg-zinc-900
                        drop-shadow-md
                    `}>

                        <div className="relative h-96">
                            <video 
                                className="
                                    w-full
                                    brightness-[60%]
                                    object-cover
                                    h-full
                                "
                                autoPlay
                                muted
                                loop
                                poster={data?.thumbnailUrl}
                                src={data?.videoUrl}
                            ></video>
                        </div>
                </div>
            </div>
        </div>
    )
}

export default InfoModal;

产生了如下的效果：

接下来再给上面的黑色方框加上一个关闭按钮，并添加播放按钮和收藏按钮。在InfoModal.tsx中添加以下代码：

<div 
className="
    cursor-pointer
    absolute
    top-3
    right-3
    h-10
    w-10
    rounded-full
    bg-black
    bg-opacity-70
    flex
    items-center
    justify-center
"
onClick={() => {}}>
    <AiOutlineClose className="text-white" size={20} />
</div>

<div className="
    absolute
    bottom-[10%]
    left-10
">
    <p className="text-white text-3xl md:text-4xl h-full lg:text-5xl font-bold mb-8">
        {data?.title}
    </p>
    <div className="flex flex-row gap-4 items-center">
        <PlayButton movieId={data?.id} />
        <FavoriteButton movieId={data?.id} />
    </div>
</div>

最后再加上New字样和电影的各类信息：

<div className="px-12 py-8">
    <p className="text-green-400 font-semibold text-lg">
        New
    </p>

    <p className="text-white text-lg">
        {data?.duration}
    </p>

    <p className="text-white text-lg">
        {data?.genre}
    </p>

    <p className="text-white text-lg">
        {data?.description}
    </p>
</div>

并加上点击关闭按钮实现关闭页面的功能，即在onClick函数中调用handleClose即可：onClick={handleClose}>

然后在pages/index.tsx中实现对上述模块InfoModal.tsx的触发。

1 2	const { isOpen, closeModal } = useInfoModal(); // use useInfoModal hook to trigger InfoModal <InfoModal visible={isOpen} onClose={closeModal} />

现在需要实现在billboard中点击More Info按钮展现上述的Info Modal组件的功能。进入components/Billboard.tsx中，写入以下的代码：

const { openModal } = useInfoModal();

const handleOpenModal = useCallback(() => {
    openModal(data?.id);
}, [openModal, data?.id]);

onClick={handleOpenModal}

在电影卡片中再插入一个按钮。使得点击该按钮，可以展现影片的详细信息，在components/MovieCard.tsx中加入以下的代码：

const { openModal } = useInfoModal();

<div 
    onClick={() => openModal(data?.id)}
    className="
        cursor-pointer 
        ml-auto 
        group/item 
        w-6 
        h-6 
        lg:w-10 
        lg:h-10 
        border-white 
        border-2 
        rounded-full 
        flex 
        justify-center 
        items-center 
        transition 
        hover:border-neutral-300">
            <BiChevronDown 
            size={30}
            className="text-white group-hover/item:text-neutral-300"/>
</div>

这样，点击电影卡片上的向下的箭头，就会显示出影片的详细信息。调用我们在本节实现的useInfoModal这个hook即可轻松地实现上述功能。

现在继续修复个人profile中名字始终加载为username的问题。将username改为用户实际的名字。进入components/AccountMenu.tsx中，修改以下的代码：

const { data } = useCurrentUser();

<p className="text-white text-sm group-hover/item:underline">
    {data?.name}
</p>

即可在个人profile中加载出实际的用户名。

Vercel Deployment

可以同时复制并粘贴多行命令，命令行会自动逐一执行这些命令。要想在vercel上部署，要确保没有warning。要解决所有warning，只需要在.eslintrc.json中加入代码：

1
2
3

"rules": {
"@next/next/no-img-element": "off"
}

然后在命令行中输入：npm run lint，即可得到：No ESLint warnings or errors。此时所有warning就都被消去了。

注册vercel时，注意用github账号注册vercel，否则需要将账号绑定到github。进入vercel，点击add new，选中想要导入的github仓库，点击import，在configure project页面添加一些environment variables，即将原本项目中.env文件中的各个环境变量（除去NEXTAUTH_URL外）填入即可。

然后点击deploy即可。部署大概需要两三分钟的时间。部署以后，就可以直接通过域名访问我们的项目的网页。我发现要在本地启动项目，即运行命令：npm run dev，才能实现正常的登录功能。尚不清楚为什么，按理来说部署到云平台后就本地的服务就不需要启动了。

目前该问题依然无法解决，而且似乎部署在vercel上的项目无法正常进行google/github oauth验证登录，尚不明白原因，但不再浪费时间去尝试。至少本项目在本地是能够成功运行的，我将本地的项目回滚到了fix prisma error when deploying的版本。通过链接：http://localhost:33350可以正常进行oauth登录，注册和邮箱密码登录。

尝试在vercel上重新部署本应用，现在发现账号密码登录和github oauth登录都可以正常使用了（不需要在本地启动项目，项目直接在vercel上运行），但google oauth还是无法正常运行，我猜测是账号邮箱重复的问题，可以在数据库中查看并验证我的猜测。实际上应该不是账号邮箱重复的问题，就是哪一步配置不对或者网站抽风，不管了。

Day 17 | Leetcode 110, 257, 404

发表于 2024-02-20 更新于 2024-02-27 分类于算法（二叉树）

链接

110.平衡二叉树
 257. 二叉树的所有路径
 404.左叶子之和

知识

257. 二叉树的所有路径

404.左叶子之和

初次尝试

110.平衡二叉树

先尝试递归解法。我写下了如下的代码，可以运行成功，但时间复杂度较高：

class Solution {
public:
    // 求最大根节点的最大高度，用后序遍历
    int getheight(TreeNode* node)
    {
        if (node == NULL) return 0;
        int left = getheight(node->left);
        int right = getheight(node->right);
        int res = 1 + max(left, right);
        return res;
    }

    bool isBalanced(TreeNode* root) {
        if (root == NULL) return true;

        bool left = isBalanced(root->left);
        int leftdepth = getheight(root->left);

        bool right = isBalanced(root->right);
        int rightdepth = getheight(root->right);

        bool flag = false;
        if (abs(leftdepth - rightdepth) <= 1) flag = true;

        // 根节点需要同时满足：左子树为平衡二叉树，右子树也为平衡二叉树，且左右子树高度差<=1
        // 整个树才是平衡二叉树
        bool res = left && right && flag;
        return res;
    }
};

接着看卡尔的讲解。

257. 二叉树的所有路径

拿到本题，我毫无办法，直接看卡尔的讲解。

404.左叶子之和

本题我本来想一上来就是层序遍历，但后面发现是左叶子，而非左孩子。叶子节点是没有左右孩子的节点。我产生了一个另外的想法，先前序遍历一遍二叉树，遍历到左节点时判断左节点是否是左叶子节点，是的话则将其加入结果res中，最后返回res即可。我尝试了，但做不出来，看卡尔的讲解。

实现

110.平衡二叉树

平衡二叉树：二叉树中任何一个节点左右子树的高度差不超过1。求高度要用后序遍历。本题可以用递归法，也可以用迭代法，但优先掌握递归法。

int getHeight(TreeNode* node) // 返回一个节点的高度
{
    if (node == NULL) return 0; // 终止条件
    
    // 后序遍历
    // 若某节点的左右子树的高度差超过1，说明该子树不再为平衡二叉树，进而说明整个树并非平衡二叉树
    // 当发现这样的节点时，就不返回节点的高度，直接返回-1
    // 左
    int left = getHeight(node->left);
    if (left == -1) return -1; // 左子树并非平衡二叉树，则返回-1
    // 右
    int right = getHeight(node->right);
    if (right == -1) return -1; // 右子树并非平衡二叉树，则返回-1
    
    // 中
    int res;
    if (abs(left - right) > 1) res = -1; // 左右子树相差大于1，则说明该子树为非平衡二叉树，返回-1
    else res = 1 + max(left, right); // 计算左右子树的父节点的高度
    return res;
}

必须用后序遍历，因为需要先计算左右子树的高度，然后才能进行比较。完整代码如下所示：

class Solution {
public:
    // node为根节点的二叉树是平衡二叉树则返回node的高度，是非平衡二叉树则返回-1
    int getheight(TreeNode* node)
    {
        if (node == NULL) return 0;

        int left = getheight(node->left);
        if (left == -1) return -1;
        int right = getheight(node->right);
        if (right == -1) return -1;

        int res;
        if (abs(left - right) > 1) res = -1;
        else res = 1 + max(left, right);
        return res;
    }
    bool isBalanced(TreeNode* root) {
        if (getheight(root) == -1) return false;
        return true;
    }
};

257. 二叉树的所有路径

给定二叉树，返回从根节点到叶子节点的所有路径。求路径需要使用前序遍历。原因：只有前序遍历可以让父节点指向孩子节点，从而输出路径。虽然也可以用迭代法，但推荐使用递归法。回溯和递归是相辅相成、相伴而生的。本题第一次提到回溯。本题的解题过程中有回溯的过程。

为什么会有回溯？假设有以下的二叉树：

假设有容器收集路径，收集到路径125，如何弹出2和5，然后再让容器重新收集路径13？回溯的过程：弹出5和2，加入3。
关键代码：

// path数组用来记录单条路径
// res数组用来存放最终的结果（包含多条路径），是一个数组，数组的每个元素都是一个字符串
void traversal(TreeNode* node, vector<int>& path, vector<string>& res)
{
    path.push_back(node->val); // 中：处理过程
    
    // 终止条件
    // 左右孩子都为空，说明遍历到了叶子节点，收获结果
    if (node->left == NULL && node->right == NULL) 
    {
        res.push_back(path); // 将单条路径的结果放入最终结果中，省略了vector->string和加上->的代码
        return;
    }
    
    // 单层处理逻辑，用前序遍历：中左右
    // 中：处理过程，即添加遍历到的节点，本题的处理过程需要写到终止条件之前
    // 因为本题的终止条件是到叶子节点，若中写在终止条件之后，则叶子节点没有被放入path中
    // 左
    if (node->left) 
    {
        traversal(node->left, path, res); 
    	  path.pop_back(); // 回溯，弹出5和2
    }
    // 右
    if (node->right) 
    {
        traversal(node->right, path, res);
    	  path.pop_back(); // 回溯
    }
}

完整的代码：

class Solution {
public:
    void traversal(TreeNode* node, vector<int>& path, vector<string>& res)
    {
        path.push_back(node->val); // 中

        // 终止条件
        if (node->left == NULL && node->right == NULL)
        {
            string s;
            for (int i = 0; i < path.size() - 1; i ++ )
            {
                s += to_string(path[i]);
                s += "->";
            }
            s += to_string(path[path.size() - 1]);
            res.push_back(s);
            return;
        }

        // 左
        if (node->left) 
        {
            traversal(node->left, path, res);
            path.pop_back(); // 回溯
        }
        // 右
        if (node->right) 
        {
            traversal(node->right, path, res);
            path.pop_back(); // 回溯
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<int> path;
        vector<string> res;

        if (root == NULL) return res;
        traversal(root, path, res);
        return res;
    }
};

404.左叶子之和

左叶子的定义：首先必须是叶子节点（叶子节点的左右孩子为空）。同时还必须是父节点的左孩子。

本题和之前的二叉树类题目有不同之处。之前的题目遍历到哪个节点就处理哪个节点，但这题遍历到某个节点时，不能直接处理该节点，因为无法判断该节点是否其父节点的左孩子。这题的思路为遍历到某个节点，若其左孩子不为空，但左孩子的左右孩子为空，那么该节点的左孩子就是左叶子，处理该节点的左孩子即可。

本题用后序遍历比较容易，因为后序遍历是左右中，是一层层向上返回。本题也可使用迭代法。

int traversal(TreeNode* node) 
{
    // 终止条件1
    if (node == NULL) return 0;
    
    // 终止条件2，可不写，不写就会做无用的递归
    // 如果当前遍历的节点是叶子节点，那其左叶子也必定是0
    if (node->left == NULL && node->right == NULL) return 0;
    
    // 左
    int leftNum = traversal(node->left);
    // node为左叶子的父节点，左叶子为node->left
    if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) 
        leftNum = node->left->val;
    
    // 右
    int rightNum = traversal(node->right);
    // 中
    int sum = leftNum + rightNum;
    
    return sum;
}

上述代码可以精简。但不建议初学者看。

本题其实用层序遍历也可以解决，关键依然在于对于左叶子的父节点的判断，代码如下所示：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int res = 0;
        queue<TreeNode*> q;

        if (root == NULL) return 0;
        q.push(root);

        while (q.size())
        {
            int size = q.size();
            while (size -- )
            {
                TreeNode* node = q.front();
                q.pop();
                if (node->left && node->left->left == NULL && node->left->right == NULL) res += node->left->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return res;
    }
};

直接把queue改为stack，也可以解决本题。采用queue的写法是层序遍历，而采用stack的写法是普通迭代写法（区别于统一迭代写法）。

心得与备忘录

110.平衡二叉树

平衡二叉树：二叉树中任何一个节点左右子树的高度差不超过1。求高度要用后序遍历。
我在初次尝试中的做法较为简单，但没有进行剪枝，意味着即使某些树的子树为非平衡二叉树，依然会继续递归，而不是直接return false。这样导致程序的时间复杂度较高。
卡尔提供的解法的核心思路在于：node为根节点的二叉树是平衡二叉树则返回node的高度，是非平衡二叉树则返回-1。本解法的时间复杂度较低，原因在于当发现某个子树是非平衡二叉树时，就说明整棵二叉树都是非平衡二叉树，则一路返回-1，相当于做了剪枝的操作。
本题优先掌握递归法即可，不要求掌握迭代写法。迭代写法代码很长，且因为迭代法有很多重复的计算，导致效率很低。

257. 二叉树的所有路径

本题第一次让我接触到了回溯。更具体地说，是第一次在代码中显示地写出了回溯。
本题虽然是一个easy，但对我这个初学者来说难度不小，需要记得复习。
本题的核心思路依然是递归三部曲：
- 确定传入的参数：节点、单条路径和最终结果，后两者需要加上引用。
- 终止条件：到达叶子节点
- 单层递归逻辑：前序遍历。中节点的处理逻辑需要放在终止条件之前，否则单条路径中不包含叶子节点。左右节点的处理逻辑注意判空和回溯。
本题推荐采用我在实现中的写法，虽然代码略显复杂，但清楚地体现了回溯的过程，且不容易出错。不建议写精简的写法，容易出错，且对理解本题的原理并无帮助。

404.左叶子之和

注意本题中对于左叶子的定义。
本题不能遍历到哪个节点就处理哪个节点，而是遍历到左叶子的父节点，就处理左叶子。
本题采用后序遍历的写法，代码较为简单，结果从下往上一层层返回。本题也可采用层序遍历的套路写法。
本题有两个终止条件，第二个终止条件可以不写，但会导致多递归一层。
注意如何判断一个节点是否为左叶子的父节点：if (node->left != NULL && node->left->left == NULL && node->left->right == NULL)。
本题依然可以方便地套用层序遍历的常规代码。
我非常惊讶地发现，在本题中，若采用类似层序遍历的写法，用栈或者队列作为存放遍历过的节点的数据结构，都可以得到能够正常运行的代码。卡尔的讲义上给出的迭代法的写法并非是严格意义上的层序遍历，而仅仅是前序遍历的普通迭代写法（也并非统一迭代）。层序遍历需要用队列作为数据结构，而卡尔给的迭代写法采用了栈作为数据结构，但采用严格的层序遍历的写法依然可以解决这道题。

Day 16 | Leetcode 104, 559, 111, 222

发表于 2024-02-18 更新于 2024-02-20 分类于算法（二叉树）

链接

104.二叉树的最大深度
 111.二叉树的最小深度
 222.完全二叉树的节点个数

知识

104.二叉树的最大深度

111.二叉树的最小深度

222.完全二叉树的节点个数

初次尝试

104.二叉树的最大深度

我看到本题后，发现本题在层序遍历里面做过，就用层序遍历先求解。写出了如下代码：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> q;

        if (root != NULL) q.push(root);
        int res = 0;
        while (q.size())
        {
            int size = q.size();
            while (size -- )
            {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res ++ ;
        }
        return res;
    }
};

本题应该可以尝试用别的遍历方法，比如递归去求解。直接看卡尔的视频讲解吧。

559. n叉树的最大深度

本题我首先尝试用层序遍历的解法求解，写出了如下的可以AC的代码：

class Solution {
public:
    int maxDepth(Node* root) {
        queue<Node*> q;
        int height = 0;

        if (root != NULL) q.push(root);

        while (q.size())
        {
            int size = q.size();
            while (size -- )
            {
                Node* node = q.front();
                q.pop();

                for (int i = 0; i < node->children.size(); i ++ )
                    if (node->children[i]) q.push(node->children[i]);
            }
            height ++ ;
        }
        return height;
    }
};

接着思考如何递归求解。递归知道思路，但写不出取孩子树最大高度的那部分关键代码。

111.二叉树的最小深度

本题可以用层序遍历来做，属于层序遍历的10道题之一。我写出了如下的代码：

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*> q;
        int depth = 0;

        if (root != NULL) q.push(root);

        while (q.size())
        {
            int size = q.size();
            depth ++ ;
            while (size -- )
            {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
                if (!node->left && !node->right) return depth;
            }
        }
        return depth;
    }
};

我再尝试用递归求解。发现有坑，做不出来，看卡尔的讲解。

222.完全二叉树的节点个数

拿到本题，我的第一想法依然是层序遍历。不得不说层序遍历法可以解决很多问题。我写下了如下的代码：

class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> q;

        if (root != NULL) q.push(root);

        int cnt = 0;

        while (q.size())
        {
            int size = q.size();
            while (size -- )
            {
                TreeNode* node = q.front();
                q.pop();
                cnt ++ ;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return cnt;
    }
};

感叹下，层序遍历确实能解决很多题，应该还不止卡尔给出的那10道题。我再来尝试递归解法。我觉得应该采用后序遍历，先统计根节点左右子树的节点数量，将二者加起来再加1即可。我写出了如下的代码：

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == NULL) return 0;

        // 后序遍历：左右中
        int left = countNodes(root->left);
        int right = countNodes(root->right);
        int cnt = left + right + 1;
        return cnt;
    }
};

这道题我能想到的解法就是这两种，接着看卡尔的讲解。

实现

104.二叉树的最大深度

什么是深度，什么是高度？

深度：二叉树中任意一个节点到根节点的距离。根节点的深度规定为1（0也可以，规则不同）。
高度：二叉树中任意一个节点到叶子节点的距离。叶子节点的高度规定为1。

求高度用后序遍历，求深度用前序遍历。求高度是从下往上计数，因此要求从下往上遍历，而后序遍历顺序为左右中，恰好就是从下往上。求深度是从上往下计数，因此要求从上往下遍历，而前序遍历顺序为中左右。恰好就是从上往下。本题本来应该用前序遍历，但根节点的高度就是二叉树的最大深度，因此本题用后序遍历也可以做。

递归三部曲：

传入的参数和返回值
1
int getheight(TreeNode* node)

终止条件

1	if (node == NULL) return 0; // 叶子节点的高度是1，其下的空节点高度是0

单层递归（后序遍历：左右中）

int leftheight = getheight(node->left); // 左节点高度
int rightheight = getheight(node->right); // 右节点高度
int height = 1 + max(leftheight, rightheight); // 中节点高度，为左右孩子的高度取最大值+1
return height; // 根节点的高度就是二叉树的最大深度

本题的前序遍历写法相比于后序遍历写法要复杂很多（前序遍历还涉及到回溯的过程）。本题也可以用迭代法实现。

559. n叉树的最大深度

受到代码随想录的启发，写出了递归法（类似后序遍历）的代码：

class Solution {
public:
    int maxDepth(Node* root) {
        if (root == NULL) return 0; // 终止条件
        
        // 挑选出最高的孩子节点，将其高度记为height
        int height = 0;
        for (int i = 0; i < root->children.size(); i ++ )
            height = max(height, maxDepth(root->children[i]));
        height ++ ; // 中节点（父节点）的高度在最高的孩子节点的基础上+1
        
        return height;
    }
};

111.二叉树的最小深度

本题和二叉树的最大深度有很多细节不同，容易踩坑。最小深度：根节点到叶子节点的最小距离（根节点到最近的叶子节点的距离）。像104题一样，本题求二叉树的最小深度，也可以通过后序遍历求高度的方式来求解。二叉树的最小深度实际上就是根节点的最小高度。本题求深度，本来应该用前序遍历，但前序遍历的代码不如后序遍历简洁，因此本题依然推荐使用后序遍历。

误区，不能写：int height = 1 + min(left, right);，若根节点的左子树为空，右子树不为空，则这样写二叉树的最小深度为1，显然不对。正确的方法是取右子树的最小高度，然后+1。为处理这种情况，需要写如下的单次递归的代码：

int left = getheight(node->left);
int right = getheight(node->right);
// 若根节点的左子树为空，右子树不为空，二叉树的最小深度为右子树的最小高度+1
if (node->left == NULL && node->right != NULL)
    return 1 + right;
// 若根节点的左子树不为空，右子树为空，二叉树的最小深度为左子树的最小高度+1
if (node->left != NULL && node->right == NULL)
    return 1 + left;
// 若左右子树都不为空，则取其中最小的最小高度+1返回
int res = 1 + min(left, right);
return res;

本题后序遍历的完整写法如下所示：

// 后序遍历
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;

        int left = minDepth(root->left);
        int right = minDepth(root->right);

        // 左子树为空，右子树非空
        // 也可写作if (left == 0 && right) 
        if (root->left == NULL && root->right != NULL) 
            return 1 + right;
        // 左子树非空，右子树为空
        // 也可写作if (left && right == 0)
        if (root->left != NULL && root->right == NULL)
            return 1 + left;
        // 左右子树都不为空
        int res = 1 + min(left, right);
        return res;
    }
};

我写出了一个精简后的版本，但并不会影响代码的可读性（依然可以轻松看出后序遍历）：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;

        int left = minDepth(root->left); // 左
        int right = minDepth(root->right); // 右
        
        // 中
        if (!left && right) return 1 + right; // 左空右不空
        if (left && !right) return 1 + left; // 左不空右空
        return 1 + min(left, right); // 左右都不空
    }
};

222.完全二叉树的节点个数

普通二叉树，递归法（前中后序）和迭代法（层序遍历）都可以求二叉树的节点个数。我在初次尝试中写的两个版本的代码都是把本题中的二叉树当成了普通二叉树，而没有利用完全二叉树的特性。本题强调了完全二叉树，就是暗示我们尽量利用完全二叉树的特性。

在递归法（前中后序）中，后序遍历的代码是最简洁的。每个节点都遍历了一遍，时间复杂度是O(n)。接下来利用完全二叉树的特性来降低时间复杂度。完全二叉树：除了底层节点，上面的节点都是满的。底层节点从左到右依次排开。对于满二叉树，只要知道深度h，节点数目就是2^h - 1。对于完全二叉树，如果其子树是满二叉树，则可以直接用上述公式来计算，计算完左右子树的节点数再+1（根节点）即可。关键：如何判断子树为满二叉树，并求其深度。

对于满二叉树，一直向左遍历和一直向右遍历的深度应该是相等的。一直向左遍历和一直向右遍历的深度相等的完全二叉树的子树一定是满二叉树。若遇到子树非满二叉树的情况，则继续向下遍历（即继续遍历子树的左右子树），直到是满二叉树为止，然后不断返回并+1。这种方式利用了完全二叉树的特性，且避免了遍历没有必要的节点，时间复杂度小于O(n)。

int getNum(TreeNode* node)
{
    // 终止条件1
    if (node == NULL) return 0; 
    
    // 终止条件2：遇到子树为满二叉树的情况，则返回子树中节点的数量
    TreeNode* left = node->left; // 用于遍历子树的左侧
    TreeNode* right = node->right; // 用于遍历子树的右侧
    int leftdepth = 0, rightdepth = 0; // 左侧和右侧的深度
    // 计算左侧的深度
    while (left)
    {
        left = left->left;
        leftdepth ++ ;
    }
    // 计算右侧的深度
    while (right)
    {
        right = right->right;
        rightdepth ++ ;
    }
    // 左右侧深度相等，说明子树是满二叉树，可以利用公式快速计算子树的节点数量
    if (leftdepth == rightdepth) return (2 << leftdepth) - 1; // 2 << 0 = 2^1, 2 << 1 = 2^2
    
    // 单层递归的逻辑，后序遍历
    leftnum = getNum(node->left); // 左子树数量
    rightnum = getNum(node->right); // 右子树数量
    int res = leftnum + rightnum + 1; // 中
    return res;
}

上述解法不需要去遍历完全二叉树中的所有节点，而是用公式直接计算子树为满二叉树时的节点数量并返回。

心得与备忘录

104.二叉树的最大深度

本题可以用层序遍历法求解，属于层序遍历法可以求解的10道题之一。但本题用递归（后序遍历）求解代码最为简洁。
注意二叉树中深度和高度这两个概念。某个节点的深度指其到根节点的距离，某个节点的高度指其到叶子节点的距离。这两个概念可以说是相反的。
求深度用前序遍历，求高度用后序遍历。
二叉树的最大深度就是根节点的高度。因此本题可以用后序遍历求解，实际上后序遍历的代码远比前序遍历的代码简单。因此本题的推荐做法就是后序遍历。
对于559. n叉树的最大深度。同样可以采用类似后序遍历的递归方法和层序遍历的迭代方法。对于递归方法，注意如何挑选出最高的孩子节点。

111.二叉树的最小深度

本题可以用迭代法（层序遍历）和递归法（前/后序遍历）求解。最推荐的方法是后序遍历，因为其代码最为简洁。
后序遍历是用来求高度的，但二叉树的最小深度就是根节点的最小高度，因此本题可以用后序遍历。
本题的易错点为：不可以直接将104题的max改成min（因为二叉树的最小深度为根节点到叶子节点的最小距离），而是要针对左右子树是否为空进行分类讨论。
本题的层序遍历写法同样需要注意：只有当左右孩子都为空的时候，才说明遍历到最低点了。

222.完全二叉树的节点个数

本题可以采用递归写法和迭代写法。递归写法建议采用后序遍历，迭代写法建议采用层序遍历。二者的时间复杂度都是O(n)。
上述方法对普通二叉树都适用，但对本题的完全二叉树，充分利用其特性可将时间复杂度进一步减小。
一直向左遍历和一直向右遍历的深度相等的完全二叉树的子树一定是满二叉树。若遇到子树非满二叉树的情况，则继续向下遍历，最终必然会遇到满二叉树。对于满二叉树，只要知道深度h，节点数目就是2^h - 1。因此不需要遍历完全二叉树的每一个节点，就可以求得其节点的个数。
上述解法的终止条件有两个，一个是遇到叶子节点，另一个是子树为满二叉树。单层递归逻辑采用后序遍历写法。
时间复杂度分析：递归调用的次数=树的高度=log n，每层递归需要计算子树的高度，故也是log n。因此总的时间复杂度为O(log n * log n)。
空间复杂度分析：递归的深度（即递归调用栈的最大深度）大约是树的高度。对于一棵平衡二叉树来说，其高度大约是log n，其中n是树中节点的数量。故空间复杂度为O(log n)。

Day 15 | Leetcode Breadth-first traversal, 226, 101

发表于 2024-02-15 更新于 2024-02-18 分类于算法（二叉树）

链接

层序遍历
 226.翻转二叉树
 101. 对称二叉树

知识

层序遍历

二叉树的层序遍历相当于图论中的广度优先搜索。leetcode 102：层序输出二叉树。

graph TD;
    A[6] --> B[4];
    A --> C[7];
    B --> D[1];
    B --> E[3];
    C --> F[5]
    C --> G[8]

上述二叉树，一层放在一个数组里，返回的是二维数组。只依赖二叉树本身的结构，无法层序保存二叉树中的节点。需要借助另一种数据结构：队列，用于保存每一层遍历过的元素。图论中的广度优先搜索也是依赖队列实现的。

模拟过程：根节点6加入队列，记录队列大小（size=1）。size表示这层二叉树中有几个元素。接下来弹出当前层的元素6，将6加入到结果数组中，开始处理下一层。再将6的左右孩子4和7加入队列中，此时size=2，第二层的元素个数为2，接下来弹出size（2）个元素，先弹出4，将4的左右孩子1和3加入队列。再弹出7，size归0，第二层遍历结束。弹出7后，再将7的左右孩子5和8加入队列。此时size=4，说明第三层中元素个数为4。接着队列中再弹出size(4)个元素，加入结果数组。上述过程如下图所示。

我尝试根据上述模拟过程独立写出代码，但不知道怎么写while循环结束的条件。直接看卡尔的讲解。

vector<vector<int>> res;
queue<TreeNode*> q;
if (root != NULL) q.push(root);

// 遍历的终止条件：队列中无元素
while (q.size())
{
    int size = q.size(); // 记录当前层节点的数量
    vector<int> vec; // 存放一层的节点的值
    // 队列中弹出size个节点，加入到vec中
    while (size -- )
    {
        TreeNode* node = q.front();
        q.pop();
        vec.push_back(node->val);
        
        // 将弹出节点的左右孩子加入到队列中
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    res.push_back(vec);
}
return res;

上述代码也是图论中广度优先搜索的模板。leetcode上有10道题都可以用本模板解决，只需要改动不超过三行代码。

初次尝试

226.翻转二叉树

我能想到的办法是层序遍历二叉树，然后将每一层的输出数组翻转。但这样做需要将数组还原回到二叉树，比较麻烦。随后有产生想法，让一个节点的左指针指向其右节点，右指针指向其左节点即可，可能需要一个中间变量来存放左节点或者右节点。直接看卡尔的视频。

101. 对称二叉树

看到本题，我的第一想法是，本题是翻转二叉树的变式。若一个二叉树被翻转后，仍和原来保持一致，那么就可以认为它是对称二叉树。现在的问题在于如何比较两棵二叉树是否完全相同，我认为可以采用层序遍历，一层层比较即可。或者直接层序遍历完后将二叉树存入一个二维数组中，然后用两重循环+双指针算法判断二维数组是否对称。这样做实际上有个问题：

上面这棵二叉树，层序遍历得到的二维数组为[1, [2, 2], [3, 3]]。二维数组是对称的，但二叉树却不是对称的。还是看卡尔的讲解吧。

实现

层序遍历

107.二叉树的层次遍历II

只需要在最后翻转res数组即可：reverse(res.begin(), res.end());。翻转一个二维数组，二维数组中所有元素（一维数组）的顺序都会颠倒，但一维数组本身（即一维数组内部的顺序不会改变）。reverse函数可以用双指针算法手动实现：

1
2
3

int len = res.size();
for (int i = 0, j = len - 1; i < len / 2; i ++ , j -- )
    swap(res[i], res[j]);

似乎手动实现的速度要快于调用现成的reverse函数。

199.二叉树的右视图

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> q;

        if (root != NULL) q.push(root);
        while (q.size())
        {
            int size = q.size();
            for (int i = 0; i < size; i ++ )
            {
                TreeNode* node = q.front();
                q.pop();
                if (i == size - 1) res.push_back(node->val); // 将一层最右边的节点的值加入到结果数组中
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return res;
    }
};

637.二叉树的层平均值

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
        queue<TreeNode*> q;

        if (root != NULL) q.push(root);
        while (q.size())
        {
            int size = q.size();
            double sum = 0;
            for (int i = 0; i < size; i ++ )
            {
                TreeNode* node = q.front();
                q.pop();
                sum += node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res.push_back(sum / size);
        }
        return res;
    }
};

429. N叉树的层序遍历

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        queue<Node*> q;

        if (root != NULL) q.push(root);
        while (q.size())
        {
            vector<int> vec;
            int size = q.size();

            while (size -- )
            {
                Node* node = q.front();
                q.pop();
                vec.push_back(node->val);
                for (int i = 0; i < node->children.size(); i ++ )
                    if (node->children[i]) q.push(node->children[i]);
            }
            res.push_back(vec);
        }
        return res;
    }
};

515.在每个树行中找最大值

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> q;

        if (root != NULL) q.push(root);
        while(q.size())
        {
            int size = q.size();
            int max = -2147483648; // Node.val的最小值，可简写为int max = INT_MIN;
            while (size -- )
            {
                TreeNode* node = q.front();
                q.pop();
                max = node->val > max ? node->val: max; // 注意问号表达式的用法
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res.push_back(max);
        }
        return res;
    }
};

116. 填充每个节点的下一个右侧节点指针

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> q;

        if (root != NULL) q.push(root);
        while (q.size())
        {
            int size = q.size();
            Node* node0, *node; 
            for (int i = 0; i < size; i ++ )
            {
                // 取出一层的头结点
                if (i == 0)
                {
                    node0 = q.front();
                    q.pop();
                 // 本句话的目的：当一层只有头节点时，可以让该头节点在弹出的同时继续在队列中行插入其左右子节点
                    node = node0; 
                }
                // 本层前一个节点next指向本节点
                else
                {
                    // node0和node交替前进
                    node = q.front();
                    q.pop();
                    node0->next = node;
                    node0 = node;
                }
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            // 本层最后一个节点指向NULL
            node->next = NULL;
        }
        return root;
    }
};

117.填充每个节点的下一个右侧节点指针II

本题代码和116完全相同。116题目中的条件：完整二叉树实际上是多余的。不管是不是完整二叉树，都可以用同样的代码解题。

104.二叉树的最大深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int res = 0;
        queue<TreeNode*> q;

        if (root != NULL) q.push(root);
        while (q.size())
        {
            int size = q.size();
            while (size -- )
            {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res ++ ;
        }
        return res;
    }
};

111.二叉树的最小深度

class Solution {
public:
    int minDepth(TreeNode* root) {
        int res = 0;
        queue<TreeNode*> q;

        if (root != NULL) q.push(root);
        while (q.size())
        {
            int size = q.size();
            bool flag = true;
            while (size -- )
            {
                TreeNode* node = q.front();
                q.pop();
                if (node->left == NULL && node->right == NULL)
                {
                    flag = false;
                    break;
                }
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res ++ ;
            if (flag == false) break;
        }
        return res;
    }
};

注意：只有当某个节点的左右孩子都为空，这个节点才在二叉树的底部。一旦遇到这样的节点，立即跳出循环，返回res。根据这个思路，我将上述代码做了简化：

class Solution {
public:
    int minDepth(TreeNode* root) {
        int res = 0;
        queue<TreeNode*> q;

        if (root != NULL) q.push(root);
        while (q.size())
        {
            int size = q.size();
            while (size -- )
            {
                TreeNode* node = q.front();
                q.pop();
                if (node->left == NULL && node->right == NULL)
                    return ++ res;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res ++ ;
        }
        return res;
    }
};

226.翻转二叉树

面试中的常考题。本质是交换每个节点的左右孩子，交换的是指针而非数值。这道题显然用递归解比较简单，但要想清楚用哪种遍历顺序。本题用前序和后序是最直接的，用中序遍历代码比较难写。迭代和层序遍历也可以做此题，但不要求掌握。

递归三部曲：

确定递归函数的返回值和参数: TreeNode* invertTree(root)
确定函数的终止条件：if (root == NULL) return root

具体的处理逻辑：前序遍历——中左右

对中节点，需要交换中节点的左右孩子: swap(root->left, root->right)

左节点：invertTree(root->left);

右节点：invertTree(root->right);

将swap函数放在处理逻辑的最后，就是左右中，就是后续遍历。因此前序和后续遍历皆可解本题。但中序遍历不可以，举个例子：

graph TD;
    A[4] --> B[2];
    A --> C[7];
    B --> D[1];
    B --> E[3];
    C --> F[6]
    C --> G[9]

graph TD;
    A[4] --> B[2];
    A --> C[7];
    B --> D[3];
    B --> E[1];
    C --> F[6]
    C --> G[9]

graph TD;
    A[4] --> B[7];
    A --> C[2];
    B --> D[6];
    B --> E[9];
    C --> F[3]
    C --> G[1]

graph TD;
    A[4] --> B[7];
    A --> C[2];
    B --> D[6];
    B --> E[9];
    C --> F[1]
    C --> G[3]

相当于原先根节点的左子树被处理了两次，原先根节点的右子树没被处理。对中序遍历的写法，具体的逻辑应该为：

1
2
3

invertTree(root->left); // 处理左子树
swap(root->left, root->right); // 交换左右子树，原先的右子树变为了现在的左子树，原先的左子树变为了现在的右子树
invertTree(root->left); // 原先的左子树已经被处理过了，现在需要处理原先的右子树，就是现在的左子树

不建议绕弯子去写中序，很容易出错。

前序遍历：

// 前序遍历写法
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root; // 终止条件

        // 中左右
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root; // 每次递归后返回结果
    }
};

后序遍历写法：

// 后序遍历写法
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;

        // 左右中
        invertTree(root->left);
        invertTree(root->right);
        swap(root->left, root->right);
        return root;
    }
};

中序遍历写法(绕，理解即可，不要写)：

// 中序遍历写法
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;

        // 左中右
        invertTree(root->left);
        swap(root->left, root->right);
        invertTree(root->left);
        return root;
    }
};

101. 对称二叉树

本质上是判断根节点的左子树和右子树是否可以互相翻转。需要比较二叉树同是外侧的节点和同是内侧的节点是否相等。接着考虑用哪种方式遍历二叉树。二叉树类的题目确定遍历顺序非常重要。本题目只能使用后序遍历（左右中）。因为我们需要先收集完根节点左右孩子的信息再返回给根节点，才能知道根节点的左右孩子是否相同，进而知道二叉树是否是对称的。

确定函数传入的参数和返回值

// 判断根节点的左右子树是否可以互相翻转
// 本质是判断两个二叉树是否可以相互翻转，因此需要同时处理两棵二叉树
bool compare(TreeNode* left, TreeNode* right) // 传入的参数为左子树的头节点和右子树的头节点
{
}

确定终止条件
共有以下5种情况
|左节点|右节点|返回值|
|:—-:|:—-:|:—-:|
|空|非空|false|
|非空|空|false|
|空|空|true|
|非空且值不等|非空且值不等|false|
|非空且值相等|非空且值相等|继续向下遍历，写单层递归的逻辑|

if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;

单层递归的逻辑（如何像下一层遍历）
同是外侧的节点和同是内侧的节点相同，才可以return true。

bool outside = compare(left->left, right->right); // 比较一对外侧节点是否相同
bool inside = compare(left->right, right->left);  // 比较一对内侧节点是否相同
bool res = outside && inside; // 内外侧节点都相同，则才可以左右翻转
return res;

上面代码框的前三行代码分别对应后序遍历的左右中。中只能放在最后，不能提前，否则会出现还没计算outside和inside就来计算res的情况，因此必须是后序遍历。

后序遍历解决本题的完整代码：

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right)
    {
        if (left == NULL && right == NULL) return true;
        else if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left->val != right->val) return false;

        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        bool res = outside && inside;
        return res;
    }

    bool isSymmetric(TreeNode* root) {
        return compare(root->left, root->right);
    }
};

本题也可以用迭代法实现。

572.另一个树的子树

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right)
    {
        if (left == NULL && right == NULL) return true;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right != NULL) return false;
        else if (left->val != right->val) return false;

        bool outside = compare(left->left, right->left);
        bool inside = compare(left->right, right->right);
        bool res = outside && inside;
        return res;
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (subRoot == NULL) return true;
        else if (root == NULL) return false;
        else if (compare(root, subRoot)) return true;
        // 递归比较root树的子树和subRoot是否相同
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
};

本题注意如何递归地比较root树的子树和subRoot树是否相同：return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);。

心得与备忘录

层序遍历

本题（leetcode102）的模板需要熟记，可以用来解决10道leetcode。
本题的关键在于用队列来保存每一层遍历过的元素。
本题的思路可以概括为：将二叉树的一层加入到队列中，记录队列的大小为size。然后弹出size个节点，用数组收集弹出的节点，并在弹出节点的同时插入弹出的节点的左右子节点。弹完size个节点后，数组中就是当前层的所有元素，而队列中则是下一层的所有节点。
本题不需要用指针来遍历整棵树，只需要对维护和操作队列即可。
本题收获最终结果的退出条件为队列为空；二叉树的一层遍历完毕的退出条件为size = 0。

二叉树的右视图这题需要特别注意，以下写法是错误的：

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> q;

        if (root != NULL) q.push(root);
        while (q.size())
        {
            int size = q.size();
            while (size -- )
            {
                TreeNode* node = q.front();
                q.pop();
                res.push_back(node->val);
                if (node->right) q.push(node->right);
            }
        }
        return res;
    }
};

原因是：对于以下的二叉树：

1
2
3

graph TD;
    A[6] --> B[4];
    A --> C[NULL];

尽管6只有左子节点，没有右子节点，但站在二叉树的右边看这颗二叉树，看到的结果是[6, 4]，如果按照上面的写法，则返回的结果是[6]，4作为左子节点不会被加入到队列中，也不会出现在结果数组中。

N叉树的层序遍历需要注意：新定义的N叉树的名字叫Node，不要下意识地写成TreeNode。在队列中更新N叉树下一层的节点时，注意需要用for循环遍历一遍当前node的孩子数组，因为N叉树中的一个节点不仅有左右孩子，而是有一个孩子数组。
二叉树的最大深度的解题关键在于：层序遍历二叉树，每遍历完一层记录层数的变量+1。
二叉树的最大/最小深度这两道题，res ++放在第二重while循环之后和之前都可以。我在实现中的写法都是把res ++放在了第二重while循环之后，但实际上放在第二重while循环之前写出的代码更简洁易懂，可以参考代码随想录上给出的代码。
注意复习填充每个节点的下一个右侧节点指针，这道题第一遍没有写出来。本题的关键在于特判一层的头节点，以及node0和node交替前进。
116和117题的代码完全相同。差别只在于116题题目说是完整二叉树，117题目则没有这个说明。

226.翻转二叉树

注意：本题中的root是指遍历的每个节点，而非特指根节点。
本题的关键思路：交换中节点的左右子树，递归处理左右节点。
记住前序和后续的写法即可，swap要么写在左右的上面，要么写在左右的下面。抛弃中序写法，太绕！
记得最后要return root。因为终止条件：if (root == NULL) return root，只会返回一个为空的节点。大多数情况下不会触发这个终止条件，而是触发最后一个return root。

可以定义一个cur节点遍历二叉树的每个节点，这样就不会与根节点root产生混淆。

// 前序遍历写法
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        TreeNode* cur = root;
        if (cur == NULL) return cur;

        // 中左右
        swap(cur->left, cur->right);
        invertTree(cur->left);
        invertTree(cur->right);
        return cur;
    }
};

本题除递归写法外，用一般迭代、统一迭代、层序遍历的写法都可以，其实在原本的三种迭代方式的代码的基础上稍作修改就可以，但三种迭代方式的代码本身就已经较为复杂，容易写错，因此除非必须建议不要采用迭代写法。

但还是不得不说，层序遍历解本题也很方便，本题也可以归类到层序遍历能够解决的10道题中，在层序遍历的基础上，交换每个节点的左右子节点即可，代码如下所示：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> q;

        if (root != NULL) q.push(root);
        while (q.size())
        {
            int size = q.size();
            while (size -- )
            {
                TreeNode* node = q.front();
                q.pop();
                swap(node->left, node->right); // 交换每个节点的左右子节点
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return root;
    }
};

101. 对称二叉树

本题实际上需要比较根节点的左右子树是否可以相互翻转，因此需要同时遍历两棵树，所以传入的参数为左右子树的头节点。
本题只能采用后序遍历，遍历左子树的顺序是左右中，遍历右子树的顺序是右左中。
终止条件需要分五类讨论。见实现中的表格。
单层递归的核心逻辑为：判断同在外侧的节点是否相同，判断同在内侧的节点是否相同。
本题的迭代写法其实也不难理解，原理是通过一个容器来成对的存放我们要比较的元素。但优先掌握本题的递归写法即可。
100.相同的树和572.另一个树的子树基本和本题是一样的，只要稍加修改就可以。572题稍有特殊，需要注意如何递归地比较root树的子树和subRoot树是否相同。同时在主函数中也需要进行分类讨论（subRoot树为空, root树为空，两树相同，root树的子树和subRoot树相同/相异）。

Day 14 | Leetcode Recursive traversal, Iterative traversal, Unified iteration

发表于 2024-02-11 更新于 2024-02-13 分类于算法（二叉树）

链接

理论基础
 递归遍历
 迭代遍历
 统一迭代

知识

理论基础

二叉树的种类

解题过程中二叉树有两种主要的形式：满二叉树和完全二叉树（完全二叉树包含满二叉树，满二叉树一定是完全二叉树）

“度”是指一个节点拥有的子节点的数量

满二叉树

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。也可以说深度为k，有2^k-1个节点的二叉树。

完全二叉树

完全二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。

之前我们刚刚讲过优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树

前面介绍的树，都是没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。搜索的时间复杂度是O(logn)。

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树
平衡二叉树
平衡二叉树（Balanced Binary Tree）是一种特殊的二叉树，它满足以下性质：对于树中的每一个节点，其左子树和右子树的高度差的绝对值不超过1。这个条件确保了树的高度大致保持在log(n)级别，其中n是树中节点的数量。由于这种高度平衡，平衡二叉树可以在对数据进行插入、删除和查找操作时提供较好的性能，特别是保持操作的时间复杂度接近于O(logn)。
平衡二叉搜索树
平衡二叉搜索树：又被称为AVL树。具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn。map的key和set中的元素是有序的，因为它们的底层实现是平衡二叉搜索树，而平衡二叉搜索树是有序的。

二叉树的存储方式

二叉树可以链式存储，也可以顺序（线性）存储。那么链式存储方式就用指针，顺序存储的方式就是用数组。顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

用数组来存储二叉树如何遍历的呢？如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。

代码构造二叉树：创造一个头节点，其左指针指向左子节点，右指针指向右子节点，然后向函数中传入头节点即可。

二叉树的遍历方式

二叉树主要有两种遍历方式：

深度优先遍历：先往深走，遇到叶子节点再往回走。
广度优先遍历：一层一层的去遍历。

从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

深度优先遍历（一般用递归法）

前序遍历（递归法，迭代法）
中序遍历（递归法，迭代法）
后序遍历（递归法，迭代法）

广度优先遍历
层次遍历（迭代法）

这里前中后，其实指的就是中间节点的遍历顺序（但是所有遍历顺序都是先左后右）。
左指左子树，右指右子树。在左右子树中继续按照规则搜索。
前序遍历：中左右
中序遍历：左中右
后序遍历：左右中

每个子树和整棵树都遵循中左右/左中右/左右中。

最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。之前我们讲栈与队列的时候，就说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。

而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

二叉树的定义

链式存储的二叉树节点的定义方式：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {} // 构造函数
};

二叉树的定义和链表是差不多的，相对于链表，二叉树的节点里多了一个指针，有两个指针，指向左右孩子。

递归遍历

针对leetcode上的三道题目，分别是前序、中序、后序遍历，题号是144，145和94。按照三步来思考，才能保证写出正确的递归代码。所有二叉树的题目都用递归三部曲进行分析。本章节主要讲如何写出递归的代码，不关注底层实现机制。

三部曲：

确定递归函数的参数和返回值
确定终止条件
确定单层递归的逻辑

前序遍历

前序：中左右

确定递归函数的参数和返回值

没必要一次性确定，可以在写递归函数时根据需要来填充参数。一般参数为根节点和数组，后者用来存放遍历的结果。返回值一般是void，因为我们把想要的结果放在了参数的数组中。
1
2
3
4
void traversal(TreeNode* cur, vector<int>& vec) // 参数为根节点和结果数组
{

}
确定终止条件（搞不好会出现栈溢出等问题）。深度优先搜索是遇到NULL时返回。
1
2
if (cur == NULL)
return;

确定单层递归的逻辑

1
2
3

vec.push_back(cur->val); // 中
treversal(cur->left, vec); // 左
treversal(cur->right, vec); // 右

注意在前序遍历中上面三行代码的顺序不可改变。

中序遍历

左中右。只需要改变第三步：确定单层递归的逻辑的代码。三行代码的顺序不可改变。

1
2
3

treversal(cur->left, vec); // 左
vec.push_back(cur->val); // 中
treversal(cur->right, vec); // 右

后序遍历

左右中。同样只需要改变第三步：确定单层递归的逻辑的代码。三行代码的顺序不可改变。

1
2
3

treversal(cur->left, vec); // 左
treversal(cur->right, vec); // 右
vec.push_back(cur->val); // 中

迭代遍历

前序遍历

非递归的方式：迭代法，如何实现二叉树的前中后序遍历。通常对简单的递归逻辑，要求写出相应的迭代（非递归）写法。最基础的就是用迭代法实现前中后序遍历。使用迭代法模拟递归，也需要使用到栈这种数据结构。理论上，所有递归都可以用栈模拟出来。

以下面的二叉树为例。

graph TD;
    A[5] --> B[4];
    A --> C[6];
    B --> D[2];
    B --> E[1];

前序遍历上述二叉树，顺序为中左右，输出结果为54216。用栈来辅助遍历上述二叉树。首先将5加入栈中，然后弹出5，将其放入结果数组中。接着处理5的左右孩子，先把6加入栈中，再把4加入栈中（栈是先进后出的），然后弹出4，将其放入结果数组中。接着处理4的左右孩子，依旧是先放右孩子1，再放左孩子2，然后弹出2，加入结果数组中，因为2已经是叶子节点了，接着弹出1，加入结果数组中，最后弹出6，加入结果数组中。结果数组中是54216，符合预期。关键点是先将右孩子放入栈中，再将左孩子放入栈中，这样弹出时就会先弹出左孩子。弹出时还要关注弹出的节点是否是叶子节点。是，则不需要继续向栈中加入元素；否，则需要向栈中继续加入弹出节点的左右孩子。

vector<int> function(TreeNode* root)
{
    stack<TreeNode*> st; // 栈
    vector<int> res; // 结果数组
    
    st.push(root); // 中节点入栈
    // 栈不为空，则执行以下逻辑
    while (!st.empty())
    {
        // 将中节点从栈中弹出，加入到结果数组中
        TreeNode* node = st.top();
        st.pop();
        if (node != NULL) // 特判：中节点是否为空
            res.push_back(node->val);
        else continue; // 若中节点为空，进入下一次循环
        
        // 将中节点的左右孩子放入栈中，先将右孩子入栈，再将左孩子入栈，这样出栈时才是先左后右的顺序
        st.push(node->right); // 右
        st.push(node->left); // 左
    }
    return res;
}

递归模拟前序遍历，本来前序遍历的顺序应该是中左右，但由于栈先进后出的特性，代码中实际的顺序是中右左。

后序遍历

后序遍历是左右中。实现后序遍历的原理如下图所示：

1
2
3

graph LR
    A[前序遍历：中左右] -->|颠倒左右| B[中右左]
    B -->|翻转结果数组| C[左右中]

vector<int> function(TreeNode* root)
{
    stack<TreeNode*> st;
    vector<int> res;
    
    st.push(root);
    while (!st.empty())
    {
        // 中
        TreeNode* node = st.top();
        st.pop();
        if (node != NULL)
        	res.push_back(node->val);
        else continue;
        
        st.push(root->left); // 左
        st.push(root->right); // 右
    }
    reverse(res.begin(), res.end());
    return res;
}

中序遍历

中序遍历无法在前序遍历的基础上通过交换某几行代码的顺序来实现。遍历节点和处理节点是两种逻辑。前序和后序遍历中，遍历的节点和要处理的节点是一个顺序，才能写出上述比较简洁的代码。但在中序遍历中，遍历节点的顺序与和处理节点的顺序不同。后面会继续介绍中序遍历的写法，以及如何像递归写法那样更改几行代码的顺序来实现前中后序遍历的迭代写法。

处理二叉树时有两步操作，一步是访问节点，一步是处理节点。访问节点是从根节点开始，一个节点一个节点地去访问。处理节点是把访问到的节点中的元素放入结果数组中。

以下面的二叉树为例：

graph TD;
    A[5] --> B[4];
    A --> C[6];
    B --> D[1];
    B --> E[2];

对于中序遍历，先访问的节点是5，但先处理的节点应该是1（先把1放入结果数组中）。我们要处理1节点，需要先访问节点5、4、1。这就造成了访问的顺序和处理的顺序不同。因此中序遍历需要另一套写法。

下面模拟中序遍历迭代法的过程。需要一个指针帮助我们遍历二叉树，同时用栈记录遍历过的顺序，然后逆向输出即可。指针一路向左访问，指针先指向5，5入栈；指针再指向4，4入栈；指针再指向1，1入栈。到叶子节点了（叶子节点的左指针为空），便从栈中取出元素，从栈中弹出1并加入到结果数组中。看1的右孩子，为空，故再从栈中弹出4并加入到结果数组中，看4的右孩子，不为空，4的右孩子2入栈。2的左孩子为空，故将2从栈中弹出，加入到结果数组中。再看2的右孩子，为空，故从栈中弹出5并加入到结果数组中。5的右孩子为6，不为空，6入栈。6的左孩子为空，故6出栈，加入结果数组中。6的右孩子为空，本该从栈中弹出元素，但此时栈为空，故结束。结果数组为14256，符合中序遍历的顺序。

总结：用指针遍历节点，用栈来记录遍历过的节点，再从栈中弹出元素放入结果数组中。指针一路向左访问，若某个节点的左指针为空，则从栈中取出该节点并放入结果数组中。若某个节点的右指针为空，则从栈中弹出顶部元素并放入结果数组中，若某个节点的右指针不为空，则将右指针指向的节点入栈。

vector<int> traversal(TreeNode* root)
{
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* cur = root; // 用于遍历二叉树的指针，一开始指向根节点
    
    // cur为空且栈也为空时，遍历终止
    while (cur != NULL || !st.empty())
    {
        // 栈用于记录指针访问过的元素
        if (cur != NULL) 
        {
            st.push(cur);
            cur = cur->left; // 指针一路向左访问
        }
        // 指针一路向左，遇到某个节点的左指针为空
        // 则从栈中取出该节点并放入结果数组中
        else 
        {
            cur = st.top();
            st.pop();
            res.push_back(cur->val);
            
            // 看当前指针的右孩子是否为空
            // 若为空，则从栈中弹出顶部节点，并将其加入到结果数组中
            // 若不为空，则将右孩子入栈
            cur = cur->right;
        }
    }
    return res;
}

目前迭代法的前中后序遍历没有像递归那样统一起来，其实也是可以统一起来的。统一的写法：用一个栈完成遍历节点和处理节点的过程，但栈中要加入空节点做标记，标记正在遍历的节点和处理的节点。

统一迭代

对前中后序这三种遍历方式，使用迭代法是可以写出统一风格的代码。以中序遍历为例，我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;

        // 根节点非空才将其放入栈中
        if (root != NULL) st.push(root);

        // 循环条件：栈不为空
        while (!st.empty())
        {
            // 弹出栈顶元素
            TreeNode* node = st.top();
            st.pop();

            // node不为空，则按照右中左的顺序访问节点
            if (node != NULL)
            {
                if (node->right) st.push(node->right); // 右节点
                st.push(node); // 中节点
                st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记
                if (node->left) st.push(node->left); // 左节点
            }
            // 只有遇到空节点的时候，才处理节点（将下一个节点放进结果集）
            else
            {
                // 将空节点弹出，重新取出栈中的元素
                node = st.top();
                st.pop();
                res.push_back(node->val); // 加入到结果集中
            }
        }
        return res;
    }
};

对于前序和后序遍历，只需要改变node不为空时访问节点的顺序即可。前序遍历原本的顺序是中左右，考虑到栈先入后出的特性，调整为右左中。后续遍历原本的顺序是左右中，考虑到栈先入后出的特性，调整为中右左。

实现

递归遍历

144. 前序遍历二叉树

class Solution {
public:
    // 前序遍历递归写法的核心函数
    void traversal(TreeNode* root, vector<int> &vec) // 递归函数的参数和返回值
    {
        if (root == NULL) return; // 确定终止条件
        
        vec.push_back(root->val); // 中
        traversal(root->left, vec); // 左
        traversal(root->right, vec); // 右
    }

    // 相当于主函数，调用核心函数
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;

        traversal(root, res); // 调用核心函数
        return res;
    }
};

完整的，带有测试样例的代码为：

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    void traversal(TreeNode* root, vector<int>& res) {
        if (root == NULL) return;
        res.push_back(root->val);
        traversal(root->left, res);
        traversal(root->right, res);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(root, res);
        return res;
    }
};

int main() {
    // 构建树的示例代码，需要根据实际情况调整
    TreeNode* node3 = new TreeNode(3);
    TreeNode* node2 = new TreeNode(2, node3, nullptr);
    TreeNode* root = new TreeNode(1, nullptr, node2);

    Solution solution;
    vector<int> res = solution.preorderTraversal(root);

    // 打印结果
    for (int val : res) {
        cout << val << " ";
    }
    cout << endl;

    // 释放分配的内存（在实际使用中，考虑使用智能指针自动管理内存）
    delete node3;
    delete node2;
    delete root;

    return 0;
}

145. 后序遍历二叉树

class Solution {
public:
    void traversal(TreeNode* root, vector<int>& res)
    {
        if (root == NULL) return;

        traversal(root->left, res); // 左
        traversal(root->right, res); // 右
        res.push_back(root->val); // 中
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;

        traversal(root, res);
        return res;
    }
};

94. 中序遍历二叉树

class Solution {
public:
    void traversal(TreeNode* root, vector<int>& res)
    {
        if (root == NULL) return;

        traversal(root->left, res); // 左
        res.push_back(root->val); // 中
        traversal(root->right, res); // 右
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;

        traversal(root, res);
        return res;
    }
};

迭代遍历

144. 前序遍历二叉树

// 顺序为中左右，因为栈的先入后出的特性，所以代码顺序调整为中右左
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st; // 用栈实现迭代，模拟递归
        vector<int> res; // 结果数组

        st.push(root);

        while (!st.empty())
        {
            TreeNode* node = st.top();
            st.pop();
            if (node != NULL)
                res.push_back(node->val);
            else continue;

            st.push(node->right); // 右
            st.push(node->left); // 左
        }
        return res;
    }
};

145. 后序遍历二叉树

// 后序遍历：左右中。前序遍历：中左右 
// 中左右->中右左->左右中
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;

        st.push(root);

        while (!st.empty())
        {
            TreeNode* node = st.top();
            st.pop();
            if (node != NULL) res.push_back(node->val);
            else continue;

            st.push(node->left); // 左
            st.push(node->right); // 右
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

94. 中序遍历二叉树

// 中序遍历的迭代写法，参见总结部分的精髓即可写出以下的代码
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        TreeNode* cur = root;

        // 终止条件：指针和栈都为空
        while (cur != NULL || !st.empty())
        {
            // 指针不为空，则将指针指向的节点放入栈中，指针向左走
            if (cur != NULL)
            {
                st.push(cur);
                cur = cur->left;
            }
            // 指针为空，则将栈顶元素弹出并放入结果数组中，指针向右走
            else
            {
                cur = st.top();
                st.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

统一迭代

94. 中序遍历二叉树

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;

        // 将非空的头节点插入栈中
        if (root != NULL) st.push(root);

        // 循环终止条件：栈为空
        while (!st.empty())
        {
            // 弹出栈顶元素
            TreeNode* node = st.top();
            st.pop();

            // 若node不为空，则按照右中左的顺序访问节点
            if (node != NULL)
            {
                if (node->right) st.push(node->right); // 访问右节点
                st.push(node); // 访问中节点
                st.push(NULL); // 只访问没处理，在中结点上面添加NULL来标记
                if (node->left) st.push(node->left); // 访问左节点
            }
            // 若node为空，则处理该节点下面的节点，将其加入到res中
            else
            {
                node = st.top();
                st.pop();
                res.push_back(node->val);
            }
        }
        return res;
    }
};

144. 前序遍历二叉树

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;

        if (root != NULL) st.push(root);

        while (!st.empty())
        {
            TreeNode* node = st.top();
            st.pop();

            // node不为空，访问节点
            if (node != NULL)
            {
                if (node->right) st.push(node->right); // 右
                if (node->left) st.push(node->left); // 左
                st.push(node); // 中
                st.push(NULL); // 中节点后面插入NULL
            }
            // node为空，处理节点
            else
            {
                node = st.top();
                st.pop();
                res.push_back(node->val);
            }
        }
        return res;
    }
};

145. 后序遍历二叉树

// 统一迭代写法
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;

        if (root != NULL) st.push(root);

        while (!st.empty())
        {
            TreeNode* node = st.top();
            st.pop();

            // 节点不为空，则访问节点，顺序为中右左
            if (node != NULL)
            {
                st.push(node);
                st.push(NULL);
                if (node->right) st.push(node->right);
                if (node->left) st.push(node->left);
            }
            // 节点为空，则处理节点
            else
            {
                node = st.top();
                st.pop();
                res.push_back(node->val);
            }
        }
        return res;
    }
};

心得与备忘录

递归遍历

记住递归三部曲：
- 确定递归函数的参数和返回值
- 确定终止条件
- 确定单层递归的逻辑
前序、中序、后序遍历的代码只有单层递归的逻辑部分有所不同。更确切地说，只是三行代码的顺序发生了改变。
递归的核心函数返回值为void，结果数组以引用的方式作为参数传入，经过核心函数的改变后，改变后的数组会被传出，在主函数中调用其即可。
易错点：核心函数中忘记加上引用&，插入数组时没有取root指针的值(root->val)，而是直接将root指针传入了。
注意如何写出完整的带有测试样例的代码，这涉及到如何写struct TreeNode和main函数。
熟悉几个英文单词：
- 遍历：traversal
- 前序：pre-order、中序：in-order、后序：post-order、层序：level-order
- 二叉树：binary tree
- 递归：Recursion 迭代：Iteration

迭代遍历

迭代遍历的本质是用栈来模拟递归，用结果数组来收集结果。由于栈的先入后出的特性，前序遍历的顺序本来应该是中左右，迭代写法的顺序调整为中右左。后序遍历是在前序遍历的基础上颠倒右和左的顺序，再翻转结果数组（前序遍历=中左右->中右左->左右中=后序遍历）。
中序遍历的迭代写法不能像后序遍历那样从前序遍历迭代写法的基础上直接进行改造。这是因为在中序遍历中，遍历节点的顺序与和处理节点的顺序不同。
中序遍历的迭代写法需要一个指针来遍历所有节点，一个栈用于记录遍历过的节点，一个数组用于存放结果。
中序遍历迭代写法的精髓：当指针不为空时，用栈记录指针遍历过的元素，指针持续向左走。当指针为空时，从栈中弹出顶部的节点并将其放入结果数组中，然后指针向右走。当指针为空且栈为空时，终止。
统一迭代的写法可以将前中后序遍历的迭代写法统一起来。
迭代写法确实更复杂些，注意事项也更多，也更容易写错。了解思路即可，可以放过。

统一迭代

统一迭代的思路其实比较清晰：当头节点非空时，头节点入栈。在栈非空时，不断循环。弹出栈顶节点，若该节点不为空，则按照顺序访问节点，并在访问中节点之后插入NULL，作为标记（说明该节点只被访问过，没有被处理过）；若该节点为空，则处理当前的栈顶节点（原本的栈顶节点已被弹出），将其放入结果数组中，并将其弹出。
对于前序、中序和后序遍历，只需要改变node不为空时访问节点的顺序即可。考虑到栈先入后出的特性：前序遍历原本的顺序是中左右，调整为右左中。中序遍历原本的顺序是左中右，调整为右中左。后续遍历原本的顺序是左右中，调整为中右左。
统一迭代思路清晰且对于前中后序遍历能够保持一致的写法，建议用迭代法遍历二叉树时，优先采用统一迭代的写法。前面的迭代遍历的一般写法虽然较为简单，但只能在前序和后序遍历时保持统一，在中序遍历时需要重新写。

Day 13 | Leetcode 239, 347, summary

发表于 2024-02-06 更新于 2024-02-09 分类于算法（栈与队列）

链接

239. 滑动窗口最大值
 347.前 K 个高频元素
 栈与队列总结

知识

239. 滑动窗口最大值

347.前 K 个高频元素

栈与队列总结

初次尝试

239. 滑动窗口最大值

本题应该有些类似于滑动窗口的经典题目：209.长度最小的子数组。本题的思路：用一个长度始终为3的队列，滑过数组。每次算出队列中的最大值，然后存入数组中。我打算另写一个函数来返回三个值中的最大值。但是应该是有办法在队列进出元素的时候顺便维护其中的最大值。

我根据暴力做法的思路，写下了如下的代码：

class Solution {
public:
    // 得出队列中的最大值
    int queuemax(queue<int> q)
    {
        int max = q.front();
        while (q.size())
        {
            q.pop();
            int tmp = q.front();
            if (max < tmp) max = tmp;
        }
        return max;
    }

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        queue<int> q;
        vector<int> res;

        for (int i = 0; i < nums.size(); i ++ )
        {
            if (q.size() < k) q.push(nums[i]);
            else if (q.size() == k)
            {
                res.push_back(queuemax(q));
                q.push(nums[i]);
                q.pop();
            }
        }
        res.push_back(queuemax(q));
        return res;
    }
};

上述代码在输入数组不大时可以正常运行，但输入数组太大时会超时，测试样例通过了37 / 51。上述暴力做法的时间复杂度是O(n * k)。看代码随想录的视频讲解吧。

347.前 K 个高频元素

拿到这道题，我的第一想法是拿哈希去做。但发现哈希不能解决本题，因为对统计频率的数组排序后，数组的下标（即输入数组的元素）被打乱了。直接看卡尔的讲解。

实现

239. 滑动窗口最大值

本题是第一道hard。难点：如何求窗口中的最大值？暴力做法时间复杂度O(n k)。需要一个特殊的队列，实现pop, push和getMaxValue（返回当前队列中的最大值）这三个操作。还可以用一个优先级队列。cpp中的优先级队列就是大顶堆（单调递减）或者小顶堆（单调递增）。大顶堆本质就是一个排序后的二叉树，最大的元素在上面。始终维护大顶堆，让大顶堆不断插入元素和弹出元素，大顶堆最前面的元素就是滑动窗口的最大值。*但是用大顶堆是不行的，因为无法正确地弹出元素（大顶堆内部自动做了排序，打乱了原来元素的顺序）。

因此用优先队列是不行的，需要我们自行实现一个单调队列来解决问题。需要维持队列中的元素是单调递增或单调递减的，同时需要保证pop操作的正确。单调队列中只需要维护有可能成为最大值的元素，而不需要维护k个元素。

模拟单调队列：
假设输入数组为13-1-35321。首先在队列中加入元素1，再加入3，若队列的前面有小于3的元素，则将这些元素全部弹出。这样做可以让队列的出口处就是最大值。由于随着滑动窗口的移动，本身就会舍弃第1个1，因此没必要维护3之前比3小的元素。接着在队列中加入-1。此时队列的前面没有小于-1的元素，故-1可以保留在队列中。此时取队首元素3，就是最大值。接着加入-3，队列前面的元素都大于-3，故保留-3，此时队列的最大值还是3。接着加入5，由于5比队列前面的元素都大，因此需要pop掉除5以外的全部元素，此时取队列的最大值，即队首元素，是5。接着放入3，3<5，放入3，此时队列的最大值还是5。接着加入2，2<5&&2<3，因此放入2，此时队列的最大值还是5。再向后移动，需要把最大值5pop掉，加入1，1<2 && 1<3，因此队列中加入1，此时队列的最大值是队首元素3。

单调队列在数组中移动的规则：除去常规的移动窗口的pop和push操作外，若push进来的元素比队列前面的元素都大，那前面的元素都要pop出去，直到队列前面的元素都大于push进来的元素为止。本方法的好处在于getMaxValue时取队首元素即可。

根据原理，我画出了如下的示意图，可以帮助理解（下图中打x的元素是因为单调队列的特殊规则：若push进来的元素比队列前面的元素都大，那前面的元素都要pop出去而被提前被删去的元素）。

根据上述原理，我尝试写出相应的代码，但是有一个问题我始终无法解决：根据规则：若push进来的元素比队列前面的元素都大，那前面的元素都要pop出去，有时原本的队首元素已经被更新为最大的元素了，意味着滑动窗口本身最前面的元素已经被弹出了，但有时，滑动窗口本身最前面的元素还没有被弹出，它仍作为队首元素，需要手动弹出。如何判断是否需要手动弹出队首元素。我来看看卡尔的代码实现，看他是如何解决这个问题的。

卡尔写了单调队列的三个关键函数。单调队列是在双向队列的基础上实现的，双向队列的首尾都可以出入元素。

deque<int> que; // cpp中队列默认用deque双向队列来实现，双向队列的首尾都可以出元素和入元素

void pop(int val) 
{
    // 只有当需要pop的元素和队首元素（单调队列中目前的最大值）相同时，才弹出队首元素
    // 例如上图的倒数第二行到最后一行的操作（532->321）
    // 若需要pop的元素小于队首元素，那么在push时该元素已经被删除了
    // 例如上图中的-1-35->-353，本来需要手动删除-1，但由于-1<5，因此在push(5)时-1已经被删除了
    if (!que.empty() && val == que.front())
        que.pop_front();
}

void push(int val)
{
    // 当队列不为空且要插入的值val > 队列中的最后一个元素时，持续从队尾弹出元素
    // 例如上图中的3-1-3->-1-35，要插入5，持续从队尾弹出比5小的元素，然后再插入5
    while (!que.empty() && val > que.back()) que.pop_back();
    que.push_back(val);
}

int getMaxValue(deque<int> que)
{
    return que.front();
}

在上述关键代码的基础上，我写下了解决本题的完整代码：

class Solution {
private:
    class MyQueue
    {
    public:
        deque<int> que;
            // 单调队列中只维护当前队列中的最大值，作为队首元素
            // 故窗口滑动时只需要在滑出最大值时手动删除最大值即可
            // 其他值都会在push时被删除
        void pop(int val)
        {
            if (!que.empty() && val == que.front()) que.pop_front();
        }

            // 保证单调队列从队首到队尾是单调递减的
            // 新插入的元素若大于当前队列中的最大值，则删除当前队列，将插入的元素放在队列的首部
        void push(int val)
        {
            while (!que.empty() && val > que.back()) que.pop_back();
            que.push_back(val);
        }

            // 当前队列中的最大值为队首元素，故返回队首元素即可
        int getMaxValue()
        {
            return que.front();
        }
    };
    
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> res;

        for (int i = 0; i < k; i ++ )
            que.push(nums[i]);

        res.push_back(que.getMaxValue());

        for (int i = k; i < nums.size(); i ++ )
        {
            que.pop(nums[i - k]);
            que.push(nums[i]);
            res.push_back(que.getMaxValue());
        }
        return res;
    }
};

347.前 K 个高频元素

两个难点：

如何求数组中每个元素的频率
如何对这个频率进行排序，并求前k个高频的元素

用map来进行排序，key用来存放元素，value用来存放元素出现的次数。接着以value为基准做从大到小的排序（不好做，因为map默认是按照key的顺序来进行排序的），最后输出value对应的key即可。时间复杂度O(nlogn)。

求前k个高频的元素，只需维护k个有序的集合，没必要对所有元素都进行排序。经典的数据结构：大顶堆、小顶堆。堆擅长在很大的数据集中求前k个高/低频的元素。大顶堆的根节点是最大的元素，小顶堆的根节点是最小的元素。

如何用堆解决这个问题？用堆去遍历map中的所有元素（以value为基准进行统计），堆中维持k个元素，遍历完map中的所有元素后，堆中的k个元素就是前k个高频元素。大/小顶堆？用大顶堆遍历map中的所有元素时，遇到新元素时，将其插入到大顶堆中，会弹出堆顶的元素（最大的元素），用大顶堆遍历完map后，堆中剩下的元素是前k个低频的元素。因此要用小顶堆。小顶堆每次在push进来元素时，弹出堆顶元素（最小的元素），堆中剩下的就是最大的元素。最后输出前k个最大的value对应的key。时间复杂度：遍历数组O(n)，每次堆中元素调整O(logk)（堆中有k个元素，堆是树状结构），总时间复杂度为O(nlogk)。在数组很大，k较小的情况下，本做法的性能明显优于对整个map进行排序的性能。优先级队列的底层实现是堆，因此用优先级队列即可。可自行实现大顶堆和小顶堆。

参考代码随想录的代码，我写下了如下的代码：

class Solution {
public:
    class compare
    {
    public: 
        // 为定义小顶堆重载运算符，这里的函数名为operator()，而非operator
        // 对大顶堆，本来应该是右边的元素>左边的元素，对小顶堆，则与此相反
        bool operator() (pair<int, int> lhs, pair<int, int> rhs)
        {
            return lhs.second > rhs.second; // 比较的是元素出现的次数，而非元素的值
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;

        // nums[i]作为key, 出现此处作为value存入map中
        for (int i = 0; i < nums.size(); i ++ )
            map[nums[i]] ++ ;
        
        // 定义小顶堆，其中的元素类型是pair<int, int>，底层实现是vector<pair<int, int>>
        priority_queue<pair<int,int>, vector<pair<int, int>>, compare> q;

        // 遍历map，不断将map中的元素插入小顶堆中，小顶堆不断弹出根节点处最小的元素
        // 最后剩下的k个元素是出现频次最高的k个元素
        for (auto it = map.begin(); it != map.end(); it ++ )
        {
            q.push(*it);
            if (q.size() > k) q.pop();
        }

        vector<int> res(k);

        // 根节点处是最小的元素，越往下元素越大，因此将小顶堆中的k个元素倒着插入res中
        for (int i = k - 1; i >= 0; i -- )
        {
            res[i] = q.top().first; // 插入res的是key, 即nums[i]
            q.pop();
        }
        return res;
    }
};

心得与备忘录

239. 滑动窗口最大值

单调队列需要手动实现，cpp标准库中没有现成可用的单调队列。
单调队列的好处在于能够将当前队列中的最大值放在队首，且不改变其他值的排列顺序（即其他值在单调队列中的排列顺序和它们在输入数组中的排列顺序相同）。
单调队列的特殊规则：若push进来的元素比队列前面的元素都大，那前面的元素都要pop出去。
定义一个类，在双向队列的基础上实现单调队列，而不要试图在主函数中对queue<int>做加工。
本题的详细模拟流程见实现中的图片。
单调队列中定义了三个函数：pop, push和getMaxValue。
对pop函数（负责模拟窗口的滑动，删除队首的最大值），需要注意：
- 单调队列中只维护当前队列中的最大值，作为队首元素
- 故窗口滑动时只需要在滑出最大值时手动删除最大值即可
- 其他值都会在push时被删除
对push函数（负责向单调队列中插入元素，同时调整队列中元素的顺序，将最大值置于队首），需要注意：
- 保证单调队列从队首到队尾是单调递减的
- 新插入的元素若大于当前队列中的最大值，则删除当前队列，将插入的元素放在队列的首部
- 当前队列中的非最大值会在不断调用push函数的过程中被删除，最大值则需要pop函数来删除
时间复杂度: O(n) 空间复杂度: O(k)
输入数组中的每个元素在单调队列中最多也就被插入和弹出各一次，没有任何多余操作，所以整体的时间复杂度还是O(n)。空间复杂度因为我们定义一个辅助队列，所以是O(k)。
本题之所以选择在双向队列的基础上加工出单调队列,是因为双向队列可以方便地在队首和队尾插入和删除元素。
注意类的写法、双向队列的push_back, push_front, pop_back, pop_front以及单调队列的push, pop等方法，不要写错或者混淆。

347.前 K 个高频元素
本题的大致思路：用map来存储元素的值和出现次数，用一个小顶堆遍历map，最终获取出现次数最高的k个元素。
map->priority_queue->vector
本题的思路：用map的key存储元素的值，value存储元素出现的次数。定义一个小顶堆。遍历map，不断将map中的元素插入到小顶堆中，不断弹出小顶堆根节点处的元素，最后小顶堆中剩下的k个元素就是出现次数最高的k个元素。将这k个元素倒着插入结果数组中即可。
为什么使用小根堆：小跟堆根节点处的元素最小，每次弹出元素也是从根节点处弹出，因此用大小为k的小根堆遍历完map后，小根堆中的k个元素是出现次数最高的k个元素，较小的元素在遍历的过程中就已经被弹出了。
注意小顶堆的定义方式：在优先级队列的基础上，传入的参数分别为小顶堆中存储的元素类型，小顶堆的底层实现，自定义的compare类（用于实现小顶堆根节点是最小元素的特性）。
注意如何写compare类，关键在于重载运算符。
注意vector数组是可以定义大小的，定义方式为vector<int> res(k)，vector元素定义了大小之后，就能像普通数组那样用索引给元素赋值：res[i]，插入元素的push_back函数并不是必须的。
根据小根堆的特点，res数组需要倒着插入，即从下标k - 1处开始插入。
定义类是，要记得在类中的函数前加上public，否则无法正常调用类中的函数。
本算法的时间复杂度是O(nlogk)，好于对map全部排序的O(nlogn)，在n较大，k较小时性能提升尤为明显。

栈与队列总结

栈和队列的理论基础：栈先入后出，队列先入先出
用两个栈实现队列，用一个队列实现栈
栈的应用：栈的应用相对较为简单且单一。栈特别适合处理对相邻字符需要做特殊判断的一些问题。比如相邻的括号匹配（20. 有效的括号）、相邻字符的消除（删除字符串中的所有相邻重复项）和后缀表达式中相邻数字的计算（逆波兰表达式求值）。
队列的应用：队列的应用更为复杂且多样，包括手动实现单调队列（239. 滑动窗口最大值）和手动实现大/小顶堆（优先级队列）347. 前k个高频元素）。对于队列的应用要多复习，这两题写起来都较为复杂。
单调队列不是一成不变的，而是不同场景不同写法。不要以为239. 滑动窗口最大值中的单调队列实现就是固定的写法。
栈里面的元素在内存中是连续分布的么？

这个问题有两个陷阱：
- 陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中不一定是连续分布的。
- 陷阱2：缺省情况下，默认底层容器是deque，那么deque在内存中的数据分布是什么样的呢？答案是：不连续的，下文也会提到deque。
拓展题：71. 简化路径
优先级队列就是大/小顶堆，名字虽为队列（因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列），但本质是完全二叉树。大顶堆（堆头是最大元素），小顶堆（堆头是最小元素）。从小到大排就是小顶堆，从大到小排就是大顶堆。大小顶堆和大小根堆是相同的。

Day 11 | Leetcode 20, 1047, 150

发表于 2024-02-05 更新于 2024-02-09 分类于算法（栈与队列）

链接

20. 有效的括号
 1047. 删除字符串中的所有相邻重复项
 150. 逆波兰表达式求值

知识

20. 有效的括号

cpp中，将一个个字母存储在stack中，用stack<int>或者stack<char>都是一样的。若是stack<int>，则字符以ascii码的形式存储。
在Linux系统中，cd（change directory）命令用于更改当前工作目录。它确实可以借助栈的概念来理解路径的导航，尤其是处理相对路径时。

考虑命令cd a/b/c/../../，这里我们可以将目录路径视作一个栈的操作序列：

cd a：进入目录a，相当于将a压入栈。
cd b：进入子目录b，相当于将b压入栈中a的上面。
cd c：进入子目录c，相当于将c压入栈中b的上面。
此时栈的状态为：
1
2
3
c
b
a
然后遇到..，这代表上一级目录，相当于从栈中弹出最上面的元素。第一个..将c弹出。
栈的状态更新为：
1
2
b
a
第二个..将b弹出。
最终栈的状态为：
1
a
所以，最后当前工作目录是a。在这个过程中，我们可以将每个目录视为栈中的一个元素，每进入一个新的子目录就相当于压入一个元素，而每次使用..就相当于弹出一个元素，回到上一级目录。这就是栈数据结构在文件系统路径解析中的一个应用。

初次尝试

20. 有效的括号

不知道怎么做，直接看卡尔的讲解视频。

1047. 删除字符串中的所有相邻重复项

本题应该是一道用栈解决的经典问题。以输入s = “abbaca”为例，定义一个栈，遍历字符串，遍历到第一个字符时，判断栈顶元素是否与之相同，是，则弹出栈顶元素，否，则插入该字符。对后面的字符也是这样处理的。根据这个思路，我独立写出了如下的代码：

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;

        for (int i = 0; i < s.size(); i ++ )
        {
            if (st.empty()) st.push(s[i]);
            else if (s[i] == st.top()) st.pop();
            else st.push(s[i]);
        }
        string out;
        while (st.size())
        {
            out += st.top();
            st.pop();
        }
        reverse(out.begin(), out.end());
        return out;
    }
};

需要特别注意：

对栈做top操作时需要保证其非空，否则会报访问未知地址，导致程序非法访问内存的错误
将栈中的一个个元素弹出并插入到一个字符串中后，需要将字符串颠倒顺序，输出才是正确的顺序

150. 逆波兰表达式求值

我看题后，暂时还没有解题思路。先看视频，了解本题的解题思路。

实现

20. 有效的括号

本题是用栈来解决的经典题目。栈的应用：编译器做词法分析、linux系统的命令。

不匹配的场景共有三个：

多出左括号
括号的类型不匹配
多出右括号

各种不匹配的场景都可被归为以上三类。

如何用栈结构解决三类不匹配的情形？

对1，从字符串的左边向右边遍历，遇到左括号，就将一个对应的右括号加入到栈中。当遍历到字符串的右括号时，若栈顶元素和右括号相同，则弹出栈顶元素。如果字符串遍历完了，但栈不为空，栈中还剩余右括号，就说明字符串中的左括号多了，不匹配。

对2，从左往右遍历字符串，遇到左括号，就在栈中加入一个对应的右括号。遇到右括号，将其与栈顶的元素比较，若不相同，则说明不匹配。

对3，从左往右遍历字符串，遇到左括号，就在栈中加入一个对应的右括号。遇到右括号，将其与栈顶的元素比较，相同则弹出栈顶的元素。若字符串还没遍历完，栈就空了，说明字符串的前面没有左括号与后面的右括号对应，说明多出了右括号，也不匹配。

字符串遍历完之后，栈是空的，就说明全都匹配了。

剪枝：字符串长度为奇数，一定会有不匹配的括号，直接return false即可。

看了卡尔的视频后，我写出了如下的代码：

class Solution {
public:
    bool isValid(string s) {
        stack<int> st; // stack<int>和stack<char>都可以

        // 剪枝：字符串长度为奇数，一定不匹配
        if (s.size() % 2) return false;

        for (int i = 0; i < s.size(); i ++ )
        {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '[') st.push(']');
            else if (s[i] == '{') st.push('}');
            // 不匹配的两种情况：多出右括号和括号类型不匹配
            // 两个判据不可颠倒，否则可能会出现栈为空但依然试图取栈顶元素的情况，编译器会报错
            else if (st.empty() || s[i] != st.top()) return false;
            // 栈不为空且栈的顶元素和s[i]相同，则弹出st的顶元素，两两抵消
            else st.pop();
        }
        // 不匹配的情况：多出左括号
        return st.empty();
    }
};

1047. 删除字符串中的所有相邻重复项

本题用栈解决非常简单，用其他数据结构比较复杂。本题和20. 有效的括号是同一类问题。本题的主要思路：相邻的字母相同，就做消除的动作。

栈用来存遍历过的元素，同时帮助我们完成消除的动作。本题可以用一个字符串来模拟栈的行为，这样在输出时就不需要再把栈转换为字符串了。用字符串模拟栈时，可以让字符串的尾部作为栈顶，字符串的头部作为栈底，这样字符串中字符的顺序就是正确的。

根据以上原理，我写出了以下的代码：

class Solution {
public:
    string removeDuplicates(string s) {
        string out;

        for (int i = 0; i < s.size(); i ++ )
        {
            if (out.empty()) out.push_back(s[i]);
            else if (s[i] == out.back()) out.pop_back();
            else out.push_back(s[i]);
        }
        return out;
    }
};

可以将上述代码写的更为精简（将两种需要push_back()的情况合并为一种）：

class Solution {
public:
    string removeDuplicates(string s) {
        string res;

        for (int i = 0; i < s.size(); i ++ )
        {
            // 字符串为空或者字符串尾部的元素与s[i]不同时，直接在字符串的尾部插入s[i]
            if (res.empty() || res.back() != s[i]) res.push_back(s[i]);
            // 否则，意味着字符串尾部的元素和s[i]相同，则两两抵消，弹出字符串尾部的元素
            else res.pop_back();
        }
        return res;
    }
};

相比于我在初次尝试中空间复杂度为O(n)的做法，上面的做法空间复杂度是O(1)，因为返回值不计空间复杂度。

150. 逆波兰表达式求值

什么是逆波兰表达式：是后缀表达式。后缀表达式是方便计算机来做运算的一种表达式。我们正常易于阅读的表达式是中缀表达式。例如(1+2)x(3+4)。画成二叉树的形式：

graph TD;
    A[x] --> B[+];
    A --> C[+];
    B --> D[1];
    B --> E[2];
    C --> F[3];
    C --> G[4];

后缀表达式就是上述二叉树的后序遍历。后续遍历的顺序是左右中。因此后缀表达式是：12+34+x。二叉树的中序表达式是1+2x3+4。中序表达式若要得到正确的结果，需要加上括号。但后缀表达式我们不需要加任何括号，从头到尾遍历我们就可以计算出正确的结果。计算机只需顺序处理后缀表达式，即可得到计算结果，而不必担心括号优先级，这就是为什么说后缀表达式是方便计算机来做运算的一种表达式。

计算机如何顺序处理后缀表达式？用栈。遍历后缀表达式时，遇到数字就将数字加入栈中，遇到运算符就从栈中取出元素来做运算，再把运算结果加入栈中。以上面的后缀表达式为例，先将1和2加入栈中，遇到+，则弹出2和1，算2+1=3，将3加入栈中。再将3和4加入栈中，遇到+，则弹出4和3，算4+3=7，将7加入栈中。遇到x，栈中弹出7和3，算7x3=21。最后将21加入栈中。后缀表达式的结果就是栈中最后的元素。

总结：两个数字遇到一个操作符时，也做消除操作，将合成的数字加入到栈中。栈适合做相邻字符的消除操作。

根据以上原理，我参照代码随想录的代码写出了如下的代码：

class Solution {
public:
    int evalRPN(vector<string>& s) {
        stack<long long> st;

        for (int i = 0; i < s.size(); i ++ )
        {
            if (s[i] == "+" || s[i] == "-" || s[i] == "*" || s[i] == "/")
            {
                // 注意采用long long类型
                long long num1 = st.top();
                st.pop();
                long long num2 = st.top();
                st.pop();
                // 注意是先num2再num1
                if (s[i] == "+") st.push(num2 + num1);
                else if (s[i] == "-") st.push(num2 - num1);
                else if (s[i] == "*") st.push(num2 * num1);
                else st.push(num2 / num1);
            }
            else
                st.push(stoll(s[i])); // stoi可以将字符串转换为int, stoll可以将字符串转换为long long
        }
        int res = st.top();
        st.pop(); // 释放内存
        return res;
    }
};

本题关于数字的变量类型全部用int而不用long long，也可以通过评测。

心得与备忘录

20. 有效的括号

本题的思路：在字符串中遇到左括号就在栈中插入右括号，在字符串中遇到右括号则判断其能否与栈顶元素相消。
不匹配的三种情况：多出右括号、多出左括号、括号类型不匹配。
本题利用了栈的性质：后插入的元素先弹出，这与本题字符串中后出现的左括号必然有先出现的右括号与之匹配的题意相符。
st.empty()和s[i] != st.top()这两个判据顺序不可颠倒，否则会出现栈为空但依然试图取栈顶元素的情况，编译器会报错。
本题可以做剪枝优化：字符串长度为奇数，则必然不匹配。
栈用stack<int>或者stack<char>都可以。前者就是将字符存储为ascii码。

1047. 删除字符串中的所有相邻重复项

栈特别适合处理对相邻字符需要做特殊判断的一些问题。比如相邻的括号匹配和消除。
字符串类型的变量也有empty, back, pop_back, push_back等函数。
本题可以用字符串来模拟栈，这样返回时不需要将栈转换回字符串，且可以通过让字符串头部对应栈底，字符串尾部对应栈顶的方式，来让输出的字符串不需要调整顺序（即不需要reverse）
本题需要考虑三种情况：栈为空/栈顶元素和字符串中元素相同/不相同
函数的递归调用需要用到栈
一个函数的返回值不会被计入这个函数的空间复杂度，额外的空间占用才会被计入空间复杂度

150. 逆波兰表达式求值

栈适合用于做相邻两个字符的消除操作。
逆波兰表达式即为二叉树的后缀表达式。
后缀表达式由二叉树的后序遍历（按左右中的顺序）得到。
本题思路：遇到数字则将其插入栈中，遇到运算符就弹出栈中的两个数字，计算并将计算结果插入栈中。
注意：运算时先num2（后弹出的数字，二叉树的左子节点）后num1（先弹出的数字，二叉树的右子节点）。
stoi可以将字符串转换为int，stoll可以将字符串转换为long long。
本题无需采用long long类型变量，用int类型变量就可以通过测评。

Day 10 | Leetcode 232, 225

发表于 2024-02-04 更新于 2024-02-05 分类于算法（栈与队列）

链接

栈与队列理论基础
 232.用栈实现队列
 225. 用队列实现栈

知识

栈与队列理论基础

顾名思义，队列是先进先出，栈是先进后出（可以从顶部添加元素，也可以从顶部移除元素，但是不能从中间或底部添加或移除元素）。

栈和队列是STL（C++标准库）里面的两个数据结构。STL有多个版本，其中有三个版本最为普遍。我们介绍的栈和队列是三个版本中的SGI STL里面的数据结构。知道版本才确定其底层实现。

栈：先进后出

栈提供push和pop等等接口，时间复杂度都是O(1)，所有元素必须符合先进后出规则（只能在顶部添加和移除元素），所以栈不提供走访功能，也不提供迭代器(iterator)。不像是set 或者map提供迭代器iterator来遍历所有元素。

我们可以用多种容器来实现栈的功能，栈的底层实现可以是vector，deque（双端队列），list（双向链表）都是可以的，主要就是数组和链表的底层实现。

我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构（deque是容器）。deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。SGI STL中队列底层实现缺省情况下一样使用deque实现的。也可以指定vector为栈的底层实现，初始化语句如下：

1
2
3

// 第一个参数int：指定了栈中元素的类型
// 第二个参数std::vector<int>：指定了底层容器的类型及其元素类型。即使用一个整型向量来存储栈中的元素。
std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈

通过允许指定底层容器，std::stack提供了灵活性，可以根据不同的性能需求或使用场景来选择最合适的容器类型。例如，std::vector提供了随机访问的能力，但是在容器前端添加或删除元素可能较慢，而std::deque在容器的前端和后端添加或删除元素都较快，但不支持快速随机访问。选择哪种底层容器取决于你的具体需求。

队列是先进先出的数据结构，同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。

也可以指定list 为起底层实现，初始化queue的语句如下：

1	std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

STL队列和栈都不被归类为容器，而被归类为container adapter（容器适配器）。因为可以用不同的容器来实现栈和队列的功能，因此栈和队列不对应于某个特定的容器。

初次尝试

232.用栈实现队列

yxc讲过的应该是用数组来实现栈和队列，并没有见过怎么用栈来实现队列。直接看卡尔的讲解。

225. 用队列实现栈

我想了想，没想出什么好办法，听卡尔讲吧。

实现

232.用栈实现队列

不涉及具体的算法，考察对栈和队列的基本操作。向队列中插入元素123，则队列吐出元素的顺序是123。向栈中插入元素123，则栈吐出元素的顺序是321。若想用栈实现队列，就需要两个栈，一个栈用于存储元素，另一个栈用于改变第一个栈中元素出栈的顺序。第一个栈吐出元素的顺序是321，将它们依次插入第二个栈中，则第二个栈吐出元素的顺序是123。第一个栈被称为入栈，第二个栈被称为出栈。

入栈中不要有滞留元素的行为，一旦需要弹出元素，就把入栈中的所有元素全部放入出栈中，让出栈实现元素的弹出。如果没有把入栈中的所有元素全部放入出栈，则出栈中弹出元素的顺序会与队列弹出元素的顺序不同。

本题pop函数的实现需要特别注意。若出栈为空，则将入栈中的所有元素加入到出栈中。peek和pop方法大部分代码都是重复的，可以在peek中直接调用pop方法：result = this->pop();。此时第一个元素被获取的同时也被弹出了，因此需要将其插入回去：stackOut.push(result)（peek方法只需要查询元素的数值，不需要像pop函数那样弹出元素）。参考视频讲解中的伪代码，我写出了以下的代码：

class MyQueue {
public:

    stack<int> inStack; // 入栈
    stack<int> outStack; // 出栈

    MyQueue() {
    }
    
    void push(int x) {
        // 向入栈中插入元素即可
        inStack.push(x);
    }
    
    int pop() {
        // 若出栈为空，则将入栈中的所有元素全部加入到出栈中
        // 如果没有把入栈中的所有元素加入到出栈中，则弹出元素的顺序会发生错误
        // 若出栈不为空，则跳过if判断部分，直接执行本函数最后三行代码
        if (outStack.empty())
        {
            while (inStack.size())
            {
                int tmp = inStack.top();
                inStack.pop();
                outStack.push(tmp);
            }
        }

        // 返回出栈顶部的元素并将该元素弹出
        int res = outStack.top();
        outStack.pop();
        return res;
    }
    
    int peek() {
        // 复用上面实现的pop函数
        int res = this->pop();
        // 由于pop函数弹出了出栈顶部的元素，peek函数只需要查询出栈顶部的元素，不需要弹出
        // 因此将该元素插入回出栈中
        outStack.push(res);
        return res;
    }
    
    bool empty() {
        // 入栈和出栈同时为空时，队列才为空
        // 若只有入栈为空，则出栈中依然有元素没有弹出，说明队列还可以弹出元素，不为空
        // 若只有出栈为空，则入栈中依然有元素可以加入出栈中，之后出栈还可以继续弹出元素，故队列也不为空
        if (inStack.empty() && outStack.empty()) return true;
        else return false;
    }
};

225. 用队列实现栈

两个栈才能实现一个队列。虽然两个队列可以模拟栈，但重点讲一个队列模拟栈的进元素和出元素。

用两个队列模拟栈：假设栈中先后插入元素123，则栈弹出元素的顺序为321。那么我们可以在队列1中先插入123，然后将1和2放入队列2中，然后从队列1中弹出元素3。接着若想让队列1弹出元素2，则将队列2中的元素2放入队列1中即可。详细讲解见代码随想录网站。

用一个队列模拟栈：在队列中先加入123，然后取出元素1，加入队列中；再取出元素2，加入队列中，此时队列弹出的元素就是3。推广：队列中有size个元素，先弹出(size - 1)个元素，再将它们加入队列中，再弹出队列中剩余的最后一个元素即可。

根据上述原理，我独立写出了以下的代码：

class MyStack {
public:
queue<int> q;

    MyStack() {     
    }
    
    void push(int x) {
       q.push(x); 
    }
    
    int pop() {
        int count = q.size(); // 队列中有size个元素
        // 循环(size - 1)次
        // 先弹出队首的元素，再将其加入到队尾中
        while (count > 1) 
        {
            int tmp = q.front();
            q.pop();
            q.push(tmp); 
            count -- ;        
        }
        // 弹出队首的元素，即为最后插入的元素
        int res = q.front();
        q.pop();
        return res;
    }
    
    // 复用pop函数，但是由于本函数只需要实现查询元素的功能，要记得将弹出的元素插入回去
    // 也可直接return q.back()。因为栈顶的元素就是队列尾部的元素（队列中，从front弹出元素，从back插入元素）
    int top() {
        int res = this->pop();
        q.push(res);
        return res;
    }
    
    // 队列为空，则栈也为空
    bool empty() {
        return q.empty();
    }
};

更简洁的写法：

class MyStack {
public:
queue<int> q;

    MyStack() {
        
    }
    
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        int size = q.size();
        size -- ;
        while (size -- )
        {
            q.push(q.front());
            q.pop();
        }
        int res = q.front();
        q.pop();
        return res;
    }
    
    int top() {
        return q.back();
    }
    
    bool empty() {
        return q.empty();
    }
};

用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。据此原理，我写下了如下的代码：

class MyStack {
public:
queue<int> q1;
queue<int> q2;

    MyStack() {
        
    }
    
    void push(int x) {
        q1.push(x);
    }
    
    int pop() {
        // 将除去队尾的元素的其他元素全部加入到q2中
        int size = q1.size();
        size -- ;
        while (size -- )
        {
            q2.push(q1.front());
            q1.pop();
        }
        // 收获答案
        int res = q1.front();
        // 将q2赋给q1
        q1 = q2;
        // 清空q2
        while (q2.size()) q2.pop();
        return res;
    }
    
    int top() {
        return q1.back();
    }
    
    bool empty() {
        return q1.empty() && q2.empty();
    }
};

心得与备忘录

232.用栈实现队列

注意stack内置的pop函数不会返回被移除的元素的值。
实现pop函数时：出栈为空，则插入入栈中的所有元素；出栈不为空，则直接弹出出栈中的首元素。
一旦需要弹出元素，就把入栈中的所有元素全部放入出栈中，否则出栈中弹出元素的顺序会与队列弹出元素的顺序不同。
入栈和出栈都为空时，模拟的队列才为空。
取出栈顶元素再弹出栈顶元素的实现，都是先int tmp = stack.top()，再stack.pop()。

225. 用队列实现栈

本题的关键在于如何弹出元素。
队列中，从front弹出元素，从back插入元素。取出队列尾部的元素：queue.back()，取出队列头部的元素：queue.front()。
掌握一个队列实现栈的方法即可，两个队列实现栈更加复杂。

Day 9 | Leetcode 28, 459, summary

发表于 2024-02-03 更新于 2024-02-04 分类于算法（字符串）

链接

28. 实现 strStr()
459.重复的子字符串
 字符串：总结篇
 双指针总结篇

知识

KMP算法理论

KMP与解决的问题

KMP：发明本算法的三位学者的英文名首字母

应用：字符串匹配问题

经典例子：

给出文本串: aabaabaaf
给出模式串: aabaaf
求在文本串中是否出现过模式串

暴力方法与KMP

暴力解法：两重for循环，先遍历文本串，再遍历模式串，挨个匹配。从文本串的首位开始，若模式串不匹配文本串，则将模式串后移一位，直到匹配上。时间复杂度O(m * n)，m和n分别是文本串和模式串的长度。

KMP算法：跳到之前已匹配的地方，继续匹配。

前缀表的由来

KMP算法如何知道我们之前已匹配过哪些，且跳到已匹配的内容后面继续匹配？

前缀表有什么特性，可以让我们找到之前已匹配过的内容？

在f处不匹配，找到f前面子串的后缀是aa，找到与该后缀相等的前缀的后面开始匹配。故我们要求一个字符串中的最长相等前后缀，重新匹配时跳到最长前缀之后开始匹配。

前缀与后缀

前缀：包含首字母，不包含尾字母的所有子串。

后缀：包含尾字母，不包含首字母的所有子串。

最长相等前后缀

最长相等的前缀和后缀的长度。以模式串aabaaf为例。

子串	前缀	后缀	最长相等的前缀和后缀的长度
a	无	无	0
aa	a	a	1
aab	a, aa	b, ab	0
aaba	a, aa, aab	a, ba, aba	1
aabaa	a, aa, aab, aaba	a, aa, baa, abaa	2
aabaaf	a, aa, aab, aaba, aabaa	f, af, aaf, baaf, abaaf	0

得到模式串的前缀表：010120。

使用前缀表的匹配过程

模式串 aabaaf
前缀表 010120
发现f不匹配，要找f前的最长相等前后缀，由前缀表得到最长相等前后缀为2。2意味着有一个后缀aa，前面也有一个与之相等的前缀aa。在后缀aa的后面不匹配了，就要从与后缀相等的前缀的后面继续开始匹配。最长相等前后缀为2，故从s[2] = 'b'处开始重新匹配。

next数组

next/prefix都可以用来表示前缀表。在遇到不匹配的地方，next数组告诉我们要回退到哪里。前缀表为010120，对其的处理包括：右移/统一减一。不处理前缀表，就将其作为next数组，依然可以完成KMP算法。

总结

KMP算法->能解决哪些问题->为什么KMP算法匹配失败后可以跳到某个位置->前缀表->前缀表的特性及如何求取前缀表->用前缀表完成一次匹配的操作->实现KMP算法时，有时对前缀表统一减一，有时右移，这不设计KMP算法原理性的东西，只是实现上方法不同而已。

KMP算法的代码实现

next数组不同的实现方式

模式串：aabaaf

文本串：aabaabaaf

前缀表：010120，用next数组表示。

如何求next数组？

有人会把前缀表右移，第一位放上-1，得到-101012，作为next数组。
有人会把前缀表整体-1，得到-10-101-1，作为next数组。
有人会直接拿前缀表做Next数组。
上述实现方式都可以，但具体处理逻辑会略有差别。

模式串与文本串在模式串的最后一位f处发生了冲突，看f的前一位的前缀表的值是多少，发现是2，于是跳转到下标为2的位置，即b。如果next数组是前缀表右移得到，就直接比较f对应的next数组的值，发现是2，于是也跳转到b的位置。若next数组是前缀表-1得到，那么就把f的前一位的next数组的值+1，依然跳转到b的位置。

next数组的核心：遇到冲突向前回退。本节我们就拿前缀表作为next数组。

求Next数组的具体代码

共4步：

初始化
处理前后缀不相同的情况
处理前后缀相同的情况
更新next数组的值

// 传入的参数：next数组，我们需要对其进行赋值，模式串s
void getNext(vector<int> next, string s)
{
    // 初始化
    // 指针i：指向后缀末尾位置
    // 指针j：指向前缀末尾位置，还代表着i之前（包括i）的子串的最长相等前后缀的长度
    int j = 0; // 前缀从0开始
    int next[N]; 
    next[0] = 0; // next数组初始位置为0
    
    // 比较前后缀所对应的字符是否相等，故i从1开始，这样i和j才能进行比较
    for (int i = 1; i < s.size(); i ++ )
    {
        // 处理前后缀末尾不相同的情况
        // 因为在一次循环中，i相当于是固定不动的，所以此时j回退
        // j回退到next[j - 1]指向的位置，即遇见冲突，就看next数组（即前缀表）的前一位
        // 不止回退一步，而要连续回退，不能写if，而要写while
        while ( j > 0 && s[i] != s[j]) j = next[j - 1]; // 因为要求j - 1 >= 0，因此要求j > 0
        
        // 处理前后缀相同的情况
        // j代表着i之前（包括i）的子串的最长相等前后缀的长度
        if (s[i] == s[j]) j ++ ;
        
        // 更新next数组，在其中存储i之前（包括i）的子串的最长相等前后缀的长度
        next[i] = j;
    }
}

模拟运行过程

当j指向s[1]，i指向s[2]时，前后缀不匹配，此时next[j - 1] = next[0] = 0，j回退到s[0]，再次比较前后缀是否匹配，发现仍不相同，此时j无法继续回退，我们就更新next数组的值，next[2] = 0，这就代表i = 2之前包括i的子串的最长相等前后缀为0，这与表格中的结果相同。此时i后移一位，指向s[3]，有s[3] == s[0]，j ++，j = 1，next[3] = 1，说明aaba的最长相等前后缀长度是1，这与表格中的结果相同。进入下一轮循环，i = 4，同理。最终用getNext函数完成了对next数组的求值。

总结

用上述函数，求得了next数组，即前缀表。

28. 实现 strStr()

求next数组的代码：

// 传入的参数：next数组，我们需要对其进行赋值，模式串s
void getNext(vector<int> next, string s)
{
    int j = 0; // 前缀从0开始
    int next[N]; 
    next[0] = 0; // next数组初始位置为0
    
    // 比较前后缀所对应的字符是否相等，故i从1开始，这样i和j才能进行比较
    for (int i = 1; i < s.size(); i ++ )
    {
        while ( j > 0 && s[i] != s[j]) j = next[j - 1]; // 因为要求j - 1 >= 0，因此要求j > 0
        
        if (s[i] == s[j]) j ++ ;
        
        // 更新next数组，在其中存储i之前（包括i）的子串的最长相等前后缀的长度
        next[i] = j;
    }
}

用next数组做匹配的代码（文本串s，模式串t）：

int j = 0; // 因为next数组里记录的起始位置为0
for (int i = 0; i < s.size(); i++) { // i从0开始，遍历文本串
    while(j > 0 && s[i] != t[j]) { // 不匹配, j - 1 >= 0 => j > 0
        j = next[j - 1]; // j 寻找之前匹配的位置
    }
    if (s[i] == t[j]) { // 匹配，j和i同时向后移动
        j++; // i的增加在for循环里
    }
    // j指向了模式串t的末尾，那么就说明模式串t完全匹配文本串s里的某个子串了
    if (j == t.size()) { // 文本串s里出现了模式串t
        // 返回当前在文本串匹配模式串的位置i-模式串的长度 + 1，就是文本串字符串中出现模式串的第一个位置（位置从0开始）
        return (i - t.size() + 1);
    }
}

完整代码：

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        // 特殊情况，模式串长度为0，则返回0，本处是一个易错点
        if (needle.size() == 0) {
            return 0;
        }
        // 定义next数组
        int next[needle.size()];
        // 填充next数组
        getNext(next, needle);
        // 用next数组做匹配
        // j指向模式串，i指向文本串
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        // 模式串匹配不上文本串，则返回-1
        return -1;
    }
};

n为文本串长度，m为模式串长度

时间复杂度: 生成next数组，时间复杂度是O(m)；根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)。所以总共的时间复杂度为O(n + m)
空间复杂度: 开辟空间用于存储next数组，即模式串的前缀表，因此是O(m)

459.重复的子字符串

暴力解法

枚举所有的子串，看能否构成字符串。

1 2	for 子串结束位置 for 子串与主串比较

时间复杂度O(n^2)。目标子串的开始位置必然是主串最前面的元素，因此只需要枚举子串的结束位置即可。

移动匹配

设一个可由重复的子串构成的字符串为s，那么两个s拼接起来，前一个s的后半部分和后一个s的前半部分又可以构成一个新的字符串s。s由重复子串构成的判据：两个s相加起来，若其中出现了s，那么s就是由重复子串构成的。

注意：在(s + s)中去搜索s时，一定要把(s + s)的首元素和尾元素删去。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string ss = s + s;
        ss.erase(ss.begin());
        ss.erase(ss.end() - 1);
        
        // string::npos 是 std::string 类型的一个静态成员常量，表示字符串中不存在匹配的位置。在 find() 函数中，如果没有找到匹配的子串，则返回 string::npos。这个值通常是一个很大的无符号整数，表示找不到匹配的位置。
        if (ss.find(s) != string::npos)
            return true;
        else 
            return false;
    }
};

find函数的实现其实就是28. 实现strStr()。若用KMP实现find函数，那么时间复杂度是O(m + n)，find函数的其他实现方法时间复杂度大抵也是O(m + n)。

KMP解法

KMP算法的应用场景：模式串是否在文本串中出现过，即上面的find函数的一种实现方式。

前缀：不包含尾字母，一定包含首字母的所有子串。
后缀：包含尾字母，不包含首字母的所有子串。

结论：若s由重复子串组成，那么它的最小重复单位就是它的最长相等前后缀不包含的那个子串。后缀不包含和前缀不包含的部分是相同的，都是最小重复子串。

举例：abababab，最长相等前缀是ababab，最长相等后缀是ababab，剩余的部分ab即为最小重复子串。

推导：设原字符串是s，标出其下标；设最长相等前缀是t，最长相等后缀是f，也分别标出下标。利用最长相等前缀和最长相等后缀的下标之间的对应关系和最长相等前后缀和原字符串下标之间的对应关系推导即可。

实现：设s存在最小重复单位，len为s的长度，则next[len - 1]为s的最长相等前后缀的长度，最小重复单位的长度为：len - next[len - 1]，若该长度能被原字符串的长度整除：len % (len - next[len - 1]) == 0，那么return true。有如下代码：

class Solution {
public:
    // 求next数组
    void getNext (int* next, const string& s){
        // 初始化
        next[0] = 0;
        int j = 0;
        for(int i = 1;i < s.size(); i++){
            // 处理前后缀不相同的情况
            while(j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            // 处理前后缀相同的情况
            if(s[i] == s[j]) {
                j++;
            }
            // 更新next数组
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern (string s) {
        if (s.size() == 0) {
            return false;
        }
        int next[s.size()];
        getNext(next, s);
        int len = s.size();
        // 核心代码
        if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        return false;
    }
};

初次尝试

28. 实现 strStr()

直接听卡尔讲，尝试去理解，不要求独立写出代码。

459.重复的子字符串

直接听卡尔讲，尝试去理解，不要求独立写出代码。

实现

28. 实现 strStr()

因为KMP算法很难，大家别奢求一次就把kmp全理解了，大家刚学KMP一定会有各种各样的疑问，先留着，别期望立刻啃明白，第一遍了解大概思路，二刷的时候，再看KMP会懂很多。或者说大家可以放弃一刷可以不看KMP，今天来回顾一下之前的算法题目就可以。

因为大家算法能力还没到，细扣很难的算法，会把自己绕进去，就算别人给解释，只会激发出更多的问题和疑惑。所以大家先了解大体过程，知道这么回事，等自己有算法基础和思维了，在看多看几遍视频，慢慢就理解了。

459.重复的子字符串

本题算是KMP算法的一个应用，不过对KMP了解不够熟练的话，理解本题就难很多。

建议是 KMP和本题，一刷的时候，可以适当放过，了解怎么回事就行，二刷的时候再来硬啃

心得与备忘录

28. 实现 strStr()

我觉得KMP算法很想一种特殊的双指针算法。一个指针i用于遍历文本串，另一个指针j用于根据next数组的指引在模式串中移动。这种双指针算法可以把时间复杂度从暴力算法的O(n * m)优化为O(n + m)。
代码分为独立的两部分，第一部分是求next数组（即前缀表），第二部分是同时在两个字符串中移动指针并使用next数组。
当模式串为空时，应当返回0。因为空字符串被认为是任何字符串的子串，所以文本串中最开始与模式串匹配的字符的索引就是0。如果文本串中不存在与之匹配的模式串，则返回 -1。

459.重复的子字符串

本题有两种解法：移动匹配和KMP解法。如果忘记了KMP算法的next数组怎么写，可以使用移动匹配方法（最难写的KMP部分可以用find函数来代劳）。
注意string中find函数的用法：在 find() 函数中，如果没有找到匹配的子串，则返回 string::npos。
本题的KMP解法的关键在于结论：若s由重复子串组成，那么它的最小重复单位就是它的最长相等前后缀不包含的那个子串。

总结

字符串总结

常见题型和常用方法：

花式反转字符串（整体&局部反转，有时还要搭配双指针算法删除空格）
后续处理字符串
KMP算法（匹配模式串和文本串）
移动匹配（核心也是KMP算法，只不过核心由库函数find实现）

小知识：

substr，split，reverse, erase这四个库函数的时间复杂度都是O(n)，在循环中使用会使得程序的时间复杂度达到O(n^2)。此时需要双指针算法等进行优化。
字符串本质为字符数组，数据结构基本等用于普通数组，因此普通数组中常用的双指针算法也常用于字符串中。

双指针总结

双指针应用于：

数组：移除元素
字符串：反转字符串、替换数字、翻转字符串里的单词
链表：反转链表、环形链表II

哈希表章节：三数之和、四数之和，两数之和若要求返回两数的值而非索引，也可以用双指针做，代码如下：

vector<int> twoSum(vector<int> nums, int target)
{
    vector<int> res; // 存储结果
    sort(nums.begin(), nums.end()); // 先排序
    
    int left = 0, right = nums.size() - 1;
    
    while (left < right)
    {
        if (nums[left] + nums[right] > target) right -- ;
        else if (nums[left] + nums[right] < target) left ++ ;
        else
        {
            res.push_back({nums[left], nums[right]}); // 收获答案
            // 去重
            while (left < right && nums[left] == nums[left + 1]) left ++ ;
            while (left < right && nums[right] == nums[right - 1]) right -- ;
            // 寻找新的答案
            left ++ ;
            right -- ;
        }
    }
    return res;
}

上述代码本质上就是三数之和、四数之和的一部分（for循环中的while循环）。相比于两数之和的哈希写法，新增了值去重的功能。

双指针的题目中，以三数、四数之和以及反转链表最容易写错，一定要多复习。三数、四数之和的易错点在于剪枝、去重和求四数之和时的int类型变量的溢出。反转链表的易错点在于搞错了tmp, cur->next, prev和cur更新的先后顺序。

Day 8 | Leetcode 344, 541, k54, 151, k55

发表于 2024-02-01 更新于 2024-02-03 分类于算法（字符串）

链接

344.反转字符串
 541. 反转字符串II
卡码网：54.替换数字
 151.翻转字符串里的单词
 卡码网：55.右旋转字符串

知识

541. 反转字符串II

一般来说，编程语言自己实现的库函数都是左闭右开的，因此reverse(s, i, i + k)表示的是反转字符串s的第i位到第i + k位，不包含第i + k位。

卡码网：54.替换数字

注意，cpp中比较大小不能写作48 <= s[i] <= 57，而是要写作s[i] >= 48 && s[i] <= 57。表达式48 <= s[i] <= 57实际上会先计算48 <= s[i]，这个表达式的结果是一个布尔值true或false，在C++中，这个布尔值会被隐式转换为整数，true转换为1，false转换为0。然后，该整数（0或1）会与57进行比较，所以条件几乎总是为真（除非s[i]是字符'0'）。
扩容字符串的函数为resize函数。
cpp中是可以不遍历字符串中的每个字符，就直接cout输出整个字符串的。
字符串和数组的区别（摘自代码随想录）：
字符串是若干字符组成的有限序列，也可以理解为是一个字符数组，但是很多语言对字符串做了特殊的规定，接下来我来说一说C/C++中的字符串。
在C语言中，把一个字符串存入一个数组时，也把结束符 ‘\0’存入数组，并以此作为该字符串是否结束的标志。
在C++中，提供一个string类，string类会提供 size接口，可以用来判断string类字符串是否结束，就不用’\0’来判断是否结束。
那么vector< char > 和 string 又有什么区别呢？
其实在基本操作上没有区别，但是string提供更多的字符串处理的相关接口，例如string 重载了+，而vector却没有。所以想处理字符串，我们还是会定义一个string类型。
若要求某个字符在0-9之间，既可以写s[i] >= 48 && s[i] <= 57（’0’的ascii码是48，’1’的ascii码是57），也可以写s[i] >= '0' && s[i] <= '9'。

151.翻转字符串里的单词

erase函数的时间复杂度是O(n)
本题可以用split函数来从字符串中分割出单词，但那样就失去了意义
若给一个函数传入的参数加上引用&，那么在函数中对这个参数进行了修改，调用该函数后该参数也会被修改。

卡码网：55.右旋转字符串

注意：若在ACM模式中调用reverse函数，必须#include <algorithm>，否则会报错。但若调用swap函数，不需要引用任何头文件，直接使用即可。

初次尝试

344.反转字符串

先尝试用reverse函数秒杀，顺便复习reverse函数的用法：

class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(), s.end());
    }
};

reverse函数相当于把字符串反转以后，将新的字符串存入了旧的字符串中。

我曾经做过反转链表的题，猜测用双指针可以解决这道题。写下了以下的代码：

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int l = 0, r = s.size() - 1; l < r; l ++ , r -- )
        {
            // swap(s[l], s[r]);
            int tmp = s[l];
            s[l] = s[r];
            s[r] = tmp;
        }
    }
};

直接用swap函数或者手写swap函数都是可以的。l < r或者l <= r都可以。因为字符串中字符的个数为奇数时，中间那个字符交换不交换都一样；字符个数为偶数时，交换最后两个成对的字符即可。

541. 反转字符串II

拿到这道题，我的第一想法是分类讨论。设字符串的长度是len。若len < k，则全部反转；若k <= len < 2k，则反转前k个字母；若len >= 2k，则按照题意反转。本题在反转的逻辑上没有困难，但问题在于如何分割出需要反转的子字符串。我没想出来什么好办法，写的逻辑太复杂又容易出错。

卡码网：54.替换数字

我先输入字符串s，然后定义每个元素由char类型变量组成的vector。遍历字符串s，若其中的某个字符的ascii码在48-57之间，说明该字符是数字0-9，那么向vector中依次插入number这6个字符。其他情况下，向vector中插入原始字符即可。据此思路写下以下的代码，可以通过评测。

# include <iostream>
# include <vector>

using namespace std;

int main()
{
    string s;
    cin >> s;

    vector<char> out;

    for (int i = 0; i < s.size(); i ++ )
    {
        if (s[i] >= 48 && s[i] <= 57)
        {
            out.push_back('n');
            out.push_back('u');
            out.push_back('m');
            out.push_back('b');
            out.push_back('e');
            out.push_back('r');
        }
        else
            out.push_back(s[i]);
    }

    for (int i = 0; i < out.size(); i ++ )
        cout << out[i];
    cout << endl;
    return 0;
}

151.翻转字符串里的单词

这道题yxc应该讲过,要么通过流的方式读入为一个个单词，样例代码如下所示：

#include <iostream>
#include <string>
#include <sstream> // 引入 stringstream

using namespace std;

int main()
{
    string line;
    getline(cin, line); // 使用 getline 读取一整行

    stringstream ss(line); // 使用 stringstream 来分割字符串
    string word;
    while (ss >> word) { // 从 stringstream 中读取单词，直到结束
        cout << word << endl; // 输出单个单词
    }

    return 0;
}

要么通过双指针算法找出一个个单词并存储之。然后再将一个个单词逆序拼接为字符串并输出。我先尝试后一种方法。但没有做出来。

卡码网：55.右旋转字符串

本题我下意识地使用substr来写，得到如下的代码：

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int k;
    string s;
    cin >> k >> s;
    
    string s1 = s.substr(s.size() - k, s.size()); // 后面k个字符
    string s2 = s.substr(0, s.size() - k); // 字符串在后面k个字符前的字符
    cout << s1 + s2 << endl;
}

向substr中传入的区间是左闭右开的。

若不借助库函数，我还有一个想法。先拿一个字符串保存输入字符串的后面k个字符。然后在输入字符串的基础上，从尾部倒着插入前面的那些字符，最后再将另一个字符串保存的原字符串的后面k个字符插到新字符串的前面去。其实倒着插入和顺着插入也没什么区别。

我还想到一种做法。受到151. 翻转字符串里的单词启发，首先反转整个字符串，然后反转字符串的前k位，最后反转字符串的后(n - k)位。由此写出了两个版本的代码，第一版是直接调用reverse函数，第二版是手动实现reverse函数。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    int k;
    string s;
    cin >> k >> s;
    
    reverse(s.begin(), s.end());
    reverse(s.begin(), s.begin() + k);
    reverse(s.begin() + k, s.end());
    cout << s << endl;
}

#include <iostream>
#include <string>

using namespace std;

// 手动实现reverse函数
void reverseString(string &s, int i, int j)
{
    for (int a = i, b = j; a < b; a ++ , b -- )
    {
        int tmp = s[a];
        s[a] = s[b];
        s[b] = tmp;
    }
}

int main()
{
    int k;
    string s;
    cin >> k >> s;
    
    reverseString(s, 0, s.size() - 1);
    reverseString(s, 0, k - 1);
    reverseString(s, k, s.size() - 1);
    cout << s << endl;
}

实现

344.反转字符串

在算法的思路上，字符串和数组非常类似。本题应用双指针法即可：首尾交换，再次一级交换，以此类推。因此首尾各有一个指针，两指针交换，然后两指针同时向中间移动。若库函数直接把题目解决了，就不要用库函数。若库函数是题目的一部分，且我们知道库函数的大体实现逻辑和时间复杂度，那就可以用。代码如下所示：

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0, j = s.size() - 1; i < s.size() / 2; i ++ , j -- )
            swap(s[i], s[j]);
    }
};

swap函数有两种方法，一种是常见的交换数值，另一种是位运算，可参见代码随想录。

541. 反转字符串II

模拟题，模拟复杂的规则下，如何反转字符串。题意：每2k段的前k个字符进行反转，尾部如果剩下的字符超过长度超过k，则反转k个字符，剩下的不动。尾部如果剩下的字符长度小于k，则全部反转。本题的代码可以很简洁。

本题每次取2k段，因此按照2k来遍历：for (int i = 0; i < s.size(); i += 2k)。然后在for循环中操作前k个字符即可。边界条件想不明白可以带一个具体的例子来试。代码和注释如下所示：

class Solution {
public:
    string reverseStr(string s, int k) {
        // 每隔2k个字符跳转一次，即每次取出2k个字符
        for (int i = 0; i < s.size(); i += 2 * k)
        {
            // 对2k个字符的前k个字符进行反转
            // 由于每次取2k，取若干次后。字符串的尾部剩下的字符长度l可能l < k 或 k <= l < 2k
            // 对前一种情况，需要将尾部全部反转，对后一种情况，需要反转尾部剩下字符的前k个字符
            // 先处理后一种情况，注意加上条件i + k <= s.size()，这可以避免对索引超出范围的元素进行反转
            // 至于i + k是否能取到s.size()，可以举例子：k = 3, s = {a, b, c}，由此可见可以取等于
            // 也可以从理论上分析，由于reverse的区间是左闭右开的，因此s.begin() + i + k实际上取不到，因此可以让i + k = s.size() 
            // 处理完后continue即可，除去反转2k个字符中的前k个字符的一般情况，尾部剩下的字符的长度的第一种情况和第二种情况只可能有一种发生
            if (i + k <= s.size())
            {
                reverse(s.begin() + i, s.begin() + i + k); // 左闭右开
                continue;
            }
            // 再处理前一种情况，当剩余的字符长度l < k时，反转剩余的全部字符
            reverse(s.begin() + i, s.end());
        }
        return s;
    }
};

也可以不用continue，直接采用if-else写法，参见代码随想录的写法（代码随线录的注释也更加简洁明了）：

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k );
            } else {
                // 3. 剩余字符少于 k 个，则将剩余字符全部反转
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};

卡码网：54.替换数字

本题的最佳解法不需要额外的辅助空间。首先扩充原字符串到每个数字字符替换成 “number” 之后的大小。然后用双指针算法，指针i指向旧字符串的末尾，指针j指向新字符串的末尾。用指针i遍历旧字符串，若遇到字母，则原样填入指针j指向的位置；若遇到数字，则从后往前将number填入到指针j指向的位置。直到i和j都指向新旧字符串的开头为止。这里的新旧字符串其实是扩容之后和扩容之前的同一字符串，只是为了方便区分称它们为新旧字符串。根据这个思路，我写出了如下的代码：

# include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;
    
    // count为字符串中数字的数量
    int count = 0;
    for (int i = 0; i < s.size(); i ++ )
        if (s[i] >= 48 && s[i] <= 57)
            count ++ ;
    
    int oldSize = s.size();
    s.resize(oldSize + count * 5); // 字符串扩容
    
    // 双指针算法，i指向旧字符串，j指向新字符串
    for (int i = oldSize - 1, j = s.size() - 1; i >= 0; )
    {
        if (s[i] < 48 || s[i] > 57) 
        {
            s[j] = s[i];
            i -- ;
            j -- ;
        }
        else
        {
            s[j] = 'r';
            s[j - 1] = 'e';
            s[j - 2] = 'b';
            s[j - 3] = 'm';
            s[j - 4] = 'u';
            s[j - 5] = 'n';
            i -- ;
            j -= 6;
        }
    }
    
    // 可以直接写作cout << s << endl;
    for (int i = 0; i < s.size(); i ++ )
        cout << s[i];
    return 0;
}

代码随想录的代码本质上和我写的是一样的，但他写的更见简洁一些，我写的更易于理解一些。

我的写法中，必须让i >= 0，不能写成i > 0，否则答案错误。例子，输入1，输出本来应该为number，若for循环的条件为i > 0，则不会进入for循环，直接输出1，这显然是不对的。但对于代码随想录的写法：for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--)，则j < i是正确的，若首字符为字母，则j = i时两指针均以指向首字符，首字符保留即可，不需要处理；若首字符为数字，则逻辑也可以正确执行。若j <= i，则反而会出现越界的问题，因为当j和i都指向首字符后，for循环的条件依然满足，此时完成当前循环后，i和j继续-1，再次判断时，i依然等于j，再次进入循环，此时s[i]和s[j]就不存在了（s[-1]不存在）。

151.翻转字符串里的单词

是字符串中操作比较复杂的题目，给的字符串中在开头、中间、结尾都可能有空格。反转字符串里的单词后，要将多余的空格都删掉。

整体思路：先让单词的顺序和目标相同，即将整个字符串都反转。再对每个单词做反转，就得到了目标字符串。将原字符串整体反转，再将每一个单词反转。

难点：如何删去多余的空格。要求空间复杂度O(1)，即不能申请新的字符串来放置删去多余空格后的字符串。且不能使用库函数。使用快慢双指针算法，删除多余空格的时间复杂度为O(n)。快指针用于遍历旧字符串，慢指针用于依次指向新字符串中的各个元素。（新字符串在旧字符串的基础上修改，并不需要另外创建字符串来存储新字符串）。双指针的用法同数组章节的移除元素。

根据上述思路，我写出了如下的代码：

class Solution
{
public:
    void removeExtraSpace(string &s)
    {
        int slow = 0;
        for (int fast = 0; fast < s.size(); fast ++ )
        {
            if (s[fast] != ' ') // 去除字符串开头的空格
            {
                // 每复制完一个单词后，加一个空格
                // 这句话不可以放在while循环后，否则会在最后一个单词后面增加一个多余的空格
                if (slow != 0) s[slow ++ ] = ' ';

                // 将旧字符串的非空部分复制到新字符串中
                while (fast < s.size() && s[fast] != ' ') s[slow ++ ] = s[fast ++ ];
            }
        }
        s.resize(slow);
    }

    string reverseWords(string s) 
    {
        removeExtraSpace(s); // 删去所有多余的空格

        reverse(s.begin(), s.end()); // 反转整个字符串，注意reverse函数是左开右闭的

        // 反转每个单词
        int start = 0, i = 0;
        while (i < s.size())
        {
            while (i < s.size() && s[i] != ' ') i ++ ; // 找到空格
            reverse(s.begin() + start, s.begin() + i); // 反转start到空格之间的单词
            start = i + 1; // 更新start
            i = start; // 更新i
        }
        return s;
    }
};

代码随想录中的反转每个单词的写法和我的略有不同，他用的是for循环，但本质是一样的。

卡码网：55.右旋转字符串

我在初次尝试中已经给出了空间复杂度为O(1)的最优解法，下面两幅图（对应两种等效的方法）可以帮助理解：

先反转整个字符串，再反转两个子串
先反转子串，再反转整个字符串

心得与备忘录

344.反转字符串

两种for循环的写法：for (int i = 0, j = s.size() - 1; i < s.size() / 2; i ++ , j -- )和for (int l = 0, r = s.size() - 1; l < r; l ++ , r -- )都可以。

541. 反转字符串II

for循环每次以2k为长度去跳转

本题反转字符的三种情况：

每隔 2k 个字符的前 k 个字符进行反转
剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
剩余字符少于 k 个，则将剩余字符全部反转

三种情况每次只可能出现一种，即出现了一种情况，另外两种情况就不会出现了。据此，我写出了结构分明的三段式代码：

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k)
        {
            // 情况1
            if (i + 2 * k <= s.size())
            {
                reverse(s.begin() + i, s.begin() + i + k);
                continue; // 可以省略
            }
            // 情况2
            else if (i + k <= s.size())
            {
                reverse(s.begin() + i, s.begin() + i + k);
                continue; // 可以省略
            }
            // 情况3
            else
                reverse(s.begin() + i, s.end());
        }
        return s;
    }
};

情况1和情况2可以合并（即剩余字符的长度l满足l >= k时，都是反转剩下字符的前k个；只有当l满足l < k时，才要反转剩下的所有字符），因此产生了实现部分中的第二版代码。每次思考时应该先想到三种情况，再写出结构分明的三段式代码，然后对其进行简化。能够写出三段式代码即可，虽然不简洁但思路清晰简单、不容易出错。

如果要求一段段地操作字符串或数组，那么for循环中的i变量是可以一段段增加的，而没必要每次+1

卡码网：54.替换数字

本题注意使用双指针做法。代码推荐参考我在实现中的写法，虽然和代码随想录的代码略有差别，但本质是完全一样的。
本题注意考虑边界条件，在我的写法中，是i >= 0而非i > 0；在代码随想录的写法中，是j < i而非j <= i。如果边界条件写得不对会导致发生指针异常或者部分样例无法通过。考虑边界条件时，可以举特例，也可以让代码先运行，若发生错误则修改相应的边界条件。
很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。对于线性数据结构，填充或者删除，后序处理会高效的多。

这么做有两个好处：
1. 不用申请新数组。算法的空间复杂度从O(N)降到了O(1)。
2. 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。算法的时间复杂度从O(n^2)降到了O(n)。

151.翻转字符串里的单词

本题的总体思路：移除多余的空格->反转整个字符串->反转字符串中的每个单词
利用快慢双指针移除多余的空格有两种写法，一种较为复杂，需要分别移除字符串前面的空格和字符串中间和最后的连续的不止一个的空格，最后再移除字符串最后可能存在的一个空格。另一种较为简单，思路和27.移除元素是相同的。快指针用于遍历旧字符串，慢指针用于依次指向新字符串中的各个元素。时间复杂度O(n)
推荐使用较为简单的双指针写法。除去从旧字符串中复制每个单词到新字符串中的代码，还需要加上用于在新字符串中添加每个单词尾部的空格的代码。注意这两行代码的顺序不能写反，必须是先有添加空格的代码，再有复制单词的代码，否则会导致在新字符串的末尾多添加一个空格。
上面提到的新旧字符串只是有时间上的先后，没有空间上的拷贝。新字符串就是在旧字符串的基础上利用双指针算法通过删除和改动部分元素得到的。因此空间复杂度为O(1)。

卡码网：55.右旋转字符串

本题加上限制条件：不能申请额外空间，只能在本串上操作（对cpp）。
可以先反转总串，再反转子串；也可以先反转子串，再反转总串。
右旋转字符串和左旋转字符串方法完全相同，就是反转的区间不同。

Netflix Clone

tech stack

function overview

Environment setup

create project

setup tailwind

Auth Screen UI

NextAuth, Prisma, Mongo Setup

Google and Github OAuth

Protecting routes, Profiles screen

Navagation Component

Billboard Component, Random Movie Endpoint

补充

async

await

总结

Movie List & Movie Card Components, Movies Endpoint, Cool hover effect

Favourites / My List functionality

Play Button, Video Player, Single Movie Endpoint

Info Modal Component

Vercel Deployment

链接

知识

257. 二叉树的所有路径

404.左叶子之和

初次尝试

110.平衡二叉树

257. 二叉树的所有路径

404.左叶子之和

实现

110.平衡二叉树

257. 二叉树的所有路径

404.左叶子之和

心得与备忘录

110.平衡二叉树

257. 二叉树的所有路径

404.左叶子之和

链接

知识

104.二叉树的最大深度

111.二叉树的最小深度

222.完全二叉树的节点个数

初次尝试

104.二叉树的最大深度

559. n叉树的最大深度

111.二叉树的最小深度

222.完全二叉树的节点个数

实现

104.二叉树的最大深度

559. n叉树的最大深度

111.二叉树的最小深度

222.完全二叉树的节点个数

心得与备忘录

104.二叉树的最大深度

111.二叉树的最小深度

222.完全二叉树的节点个数

链接

知识

层序遍历

初次尝试

226.翻转二叉树

101. 对称二叉树

实现

层序遍历

107.二叉树的层次遍历II

199.二叉树的右视图

637.二叉树的层平均值

429. N叉树的层序遍历

515.在每个树行中找最大值

116. 填充每个节点的下一个右侧节点指针

117.填充每个节点的下一个右侧节点指针II

104.二叉树的最大深度

111.二叉树的最小深度

226.翻转二叉树

101. 对称二叉树

572.另一个树的子树

心得与备忘录

层序遍历

226.翻转二叉树

101. 对称二叉树