YifanChen's Blog

一个专注技术的新手程序员

0%

发表于 分类于

正值25年新春佳节，都柏林市中心的cineworld上映了两部华语电影，一部是唐探3，另一部是封神2。笔者闲来无事，连续两天前去影院观看了这两部电影。

唐探3：一部精致的意识形态宣传片

唐探3一言以蔽之，如题。细致地来说，我愿将电影归纳为七股势力，两个对比和一个升华。

七股势力

  • 主角

    秦福和阿鬼，一个是市侩气息浓郁的小混混，一个是缝合怪河北-印第安人，是本片的搞笑担当。导演试图通过复杂的身世背景和行为动机来制造笑料，同时也混淆视听。既方便故事的发展，也方便在搞笑之余夹杂主旋律。这其实就是本片中“魔术”的精髓。

  • 润人

    不管是华人商会的白老板，还是魔术大师，都是润人。导演试图将他们描绘成良知未泯，被迫卷入的可怜虫，又赋予他们相当的自信和勇气。这是经典套路。

  • 大清

  • 帮派

  • 美国政客警察

  • 帮派

  • 革命党

两个对比

原住民与新移民的对比

原住民印第安人和新移民华人都受到白人的压榨。

今昔对比

勤勤恳恳，为美国做贡献的过去和一朝财产充公/土地被夺取对比。

一个升华

只有革命才能救中国。

封神2：鸡肋爆米花

如果不想受意识形态毒害，鉴赏能力也有限，那么封神2还是很推荐的。

充满了奇怪的爱情片段和不精致的特效。在爆米花电影中也算是鸡肋的那种，食之无味，弃之可惜。

发表于 分类于

首次使用

  1. 修改pocket3的语言：将屏幕从上往下滑，点击“设置”（齿轮图标），往左滑到最后点“更多”，里面有个“语言”设置按钮进行语言设置。
  2. 资源：
  3. 修改两个app的语言为中文：
    • DJI Mimo：设置中无法调节语言，只会跟随我的系统语言设置，暂时将我的系统语言换回中文
    • 大疆商城：设置-国家/地区-中国大陆
  4. 将pocket3放回保护盖中时，注意屏幕朝里面放回去，否则关不上保护壳
  5. 1/4螺纹手柄：
    • 提升机身握持手感
    • 上面有type c接口，可以用来充电
    • 安装时，直接插入pocket3底部（无需按住解锁按键）。取下时，请按住解锁按键同时向下拔出。
  6. 旋转屏幕至水平方向可以开启pocket3，恢复屏幕到竖直方向可以关闭pocket3。关机状态下云台将进入轴锁锁定状态，防止云台晃动受到损坏。
  7. 橘色的是拍摄按键：
    • 短按：开机、拍照、录像
    • 长按：关机
  8. 黑色的是五维摇杆
  9. pocket3开机默认为视频录像模式，插入SD卡（需要用力用指甲将SD卡给顶进去，插入成功后SD卡会完全没入机身，不会弹出来），点击拍摄按键即可开始录像。再次点击结束录制
  10. 在屏幕上朝右滑动进入回放界面，将自动开始播放最近一次拍摄的视频。点击暂停并再次向右滑动，可以选择收藏或删除该视频。屏幕朝左滑动或者按一次摇杆，回到拍摄界面。

相机功能

  1. 点击屏幕左下角的拍摄图标，多种拍摄模式供选择。包括：全景、拍照、视频、低光视频、慢动作和静止延时。
  2. 选择录像模式后，屏幕向上滑动进入参数设置界面，可以设置录像分辨率，帧率和画幅比例（16：9/1：1），最高支持4K 60HZ 16：9。
  3. 屏幕往左滑动可以开启和关闭PRO模式。在PRO模式下可以做更多参数的调节，包括曝光、白平衡、色彩模式、对焦方式、图像调解等（学妹说的参数预设，大疆pocket3直出参数大合集小红书中的参数就是在这里调节）。
    • 色彩模式：可选择普通色彩、HLG-10bit、D-logM 10bit。
    • 图像调节：可调解锐度、去噪等级。
    • 对焦模式（默认为连续）：
      • 单次：执行一次对焦后不再自动对焦，适用于不改变对焦位置的场景拍摄
      • 连续：持续对焦主体，适用于拍摄动态目标
      • 展示模式：优先对焦前景物体，适用于近距离物体展示。展示模式适合如化妆展示、开箱展示等，此时相机快速对焦镜头前方的被展示物品。
    • 麦克风图标：对收音效果进行设置，包括：
      • 声道：单声道/立体声
      • 降风噪：开/关
      • 指向收音：全向、向前、前后双向

美颜功能

  1. 屏幕左滑可以看到美颜，点击可开启/关闭
  2. 开启美颜后，可以看到屏幕右上角有美颜图标（笑脸）
  3. 美颜效果不会实时在屏幕内显示，连接Mimo后，可以在Mimo内实时观看美颜后的效果，SD卡内会保留原始素材效果
  4. 进入Mimo的美颜调节界面后，可以选择使用默认参数，一键自动美颜，也可以自由调整磨皮、美白、瘦脸等参数
  5. 带有美颜效果的素材需要通过收集DJI Mimo App导出。在Mimo进入美颜设置前，需要稍等片刻完成渲染
  6. 在拍摄时没有开美颜的视频，可以在DJI Mimo App中开启一键美颜，自由调整磨皮、美白、瘦脸等参数，然后一键导出。在拍摄时开启了美颜的视频，也可以在DJI Mimo App中关闭美颜或者重新调整磨皮、美白、瘦脸等参数。

系统功能介绍

  1. 自定义模式：可保存用户自定义拍摄模式，可保存的参数有：

    • 拍摄模式（视频/照片等）
    • 拍摄的基础参数（比如4K/16: 9/60HZ）
    • 图像设置参数（即白平衡的参数，比如AWB）

    保存好后，可以点击屏幕左下角的拍摄图标在多种拍摄模式中进行选择（自定义的拍摄模式被命名为C1/C2等等）

  2. 转屏开录：开启转屏开录开关后，关机状态下顺时针旋转屏幕，即可快速开启录制

  3. 屏幕亮度调节：可以调节屏幕显示亮度，范围0-100%

  4. 自拍跟随：开启后，当相机方向转向屏幕侧时，自动开启智能跟随人脸，摄像头会跟随人脸的移动而移动，确保人脸始终在屏幕的中央

  5. 系统设置，可设置：无线麦克风、云台开机方向、旋转屏幕关机（秒数）、自拍镜像 等系统设置选项

  6. 横竖拍模式切换，默认为自适应横竖拍，也可以根据需要设置为锁定横拍或锁定竖拍

  7. 云台转向速度：

    • 慢：云台转向柔和，具有超强的增稳效果
    • 默认：默认模式下，适合大多数拍摄场景，获得稳定的运镜画面
    • 快：适合拍摄机动性强的目标，增稳效果有所减弱，还原手持临场感

  8. 云台模式：不同云台模式将影响增稳控制的风格

    • 默认增强：默认模式，适合vlog、自拍等大多数拍摄场景
    • 俯仰锁定：镜头保持绝对水平，适合推拉横移的创作拍摄，如舞蹈，运动跟拍等
    • FPV：画面不保持水平，跟随握持方向，适合创意拍摄
    • FPV-I：回中方向垂直于机身的FPV模式，适合沿屏幕取景正对方向快启快拍

云台模式

共有三种云台模式：

  • 默认增稳：适合vlog，自拍等大多数拍摄场景
  • 俯仰锁定：适合推拉横移的创作拍摄，如舞蹈、运动跟拍等。在该模式下，镜头保持绝对水平
  • FPV模式：适合街舞或创意运镜的拍摄。在该模式下，画面不保持水平，跟随握持方向
  • 还新增了一个FPV-I模式，视频里没有介绍，但是我在系统功能介绍的云台模式部分记录了该模式的特点

云台转向速度有三档可以选择，不同转向速度将影响云台跟随手转动的幅度和速度：

  • “慢”档：获得稳定的运镜画面，跟手速度最慢
  • “默认”速度：云台转向柔和，具有超强的增稳效果，跟手速度中等
  • “快”挡：适合拍摄机动性强的目标，增稳效果有所减弱，还原手持拍摄场景快速跟随手转动

智能辅助功能

  1. 智能跟随：双击pocket3拍摄界面，双击跟随主体，可实现跟随拍摄，将被摄物体牢牢锁定在画面中心。智能跟随6.0跟随效果大幅提升，在人物短暂被遮挡后，可以找回目标并重新开始跟随。解除跟随只需要将被跟随物体移出pocket3拍摄范围内，此时pocket3首先会显示黄色的云台到达限位，或者会显示白色的目标丢失。中焦模式不支持智能跟随。开关中焦模式就是点击 分辨率参数（比如4K60）旁边的方框形状即可。中焦模式我目前觉得就是一个放大的功能。
  2. 除手动选择目标外，还提供了三种触发跟随的方式（后两种跟随方式都是通过点击屏幕左侧中间处的图标，分别选择前两项开启）：
    • 自拍跟随：下滑页面开启自拍跟随模式，在拍摄方向转至自拍时，自动对最近的人脸开启智能跟随，并在转回前方视角时取消跟随。
    • 主角跟随：当需要将pocket3放置在远处单人拍摄跟随视角时，可以使用主角跟随模式。此模式下，开始录制后进入镜头的第一个目标将被锁定为画面的主角。镜头将实时跟随主角进行拍摄。
    • 预构图跟随：需要锁定人物在画面中的位置，可使用预构图跟随功能。进入预构图跟随功能后，会在屏幕中显示九个构图点，可以通过上下左右推动摇杆将构图点对准需拍摄的人物脸部后，单击摇杆开启跟随。开启录制后，人物目标将被锁定在选定的构图位置，大大减少运镜难度。
  3. 旋转运镜：通过点击屏幕左侧中间处的图标，选择最后一项开启。画面旋转90°/180°，拍摄独特运镜。
    • 云台新的结构设计可以实现手电筒模式（pocket3向前指）下的90°或180°旋转。点击屏幕上方旋转图标或单击摇杆，云台镜头将自动旋转90°或180°进行拍摄，呈现独特的运镜效果。
    • 非手电筒模式下的常规模式，云台也可以点击屏幕上方旋转图标或单击摇杆进行90°或180°旋转
    • 第一次点击屏幕上方的旋转图标或单击摇杆，会旋转。第二次点击屏幕上方的旋转图标或单击摇杆，会复位

发表于 更新于

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

发表于 更新于 分类于

Comprehensive Introduction to C

参考笔记：https://blog.csdn.net/weixin_52421373/article/details/127972228

vs 2013 ultimate的密钥：

VS_2013英文版下载：https://www.123pan.com/s/mWzgjv-es653.html

中文语言包下载：https://www.123pan.com/s/mWzgjv-ts653.html

KEY:BWG7X-J98B3-W34RT-33B3R-JVYW9

1. 课程简介，C#语言简介，开发环境准备

课程简介

C#面向对象

采用知识点和示例程序相结合的方式

认真做课后作业，独自写一遍视频中的程序

C#语言简介

  • 程序（Program），即软件。机器码（计算机指令）->汇编语言->高级语言。高级语言翻译为计算机指令的过程被称为编译，编译用编译器。

  • 为什么需要程序：随着硬件功能的增强，需要更强大的软件（程序）来统一管理硬件，让硬件之间能够协调和网络通信。这些软件组合在一起形成了操作系统。在操作系统上编写具备特定功能的程序。为什么需要程序可以总结为两点：

    • 管理硬件资源
    • 实现用户的特定需求

  • C#是一门通用的语言，可以编写多种类型的程序。不是特别追求性能时，可以用C#开发各种应用程序。

    • 纵向：语言->类库->框架（由浅入深）

      框架是有一定逻辑组织的类库。框架是类库的最佳组合（best practice），避免自行组合时出错。

    • 横向：命令行程序，桌面程序，设备（平板/手机）程序，Web（网站/服务）程序，游戏…

    C++偏底层，学习曲线陡峭。

    C语言不面向对象，主要目标是编写高性能的操作系统，不适合用来写应用程序。

    Java适合写设备程序和Web程序，但是不适合用来写桌面程序。

  • 怎样编写程序

    编辑->编译（高级语言经过编译变为机器语言）->调试（编译器看不出来的错误，通过调试被发现）->发布

开发环境和学习资料的准备

  • 集成开发环境：集成了编辑、编译、调试和发布四个步骤。

  • 下载Visual Studio：可视化工作室，应用了所见即所得的理念。

    有两种桌面程序，后者是新一代的桌面开发技术：

    • Windows Forms Application
    • WPF Application (windows presentation foundation)

  • 安装Visual Studio(2013)，安装免费版即可

  • 打开Visual Studio，进入start page。选择tools-options-start up-show empty environment，点击OK。下次再打开visual studio，就会显示一个空的开发环境，让我们创建新项目。

  • 学习资料

    • 下载离线MSDN文档（特点：全面，文章数量多，在Visual Studio的help-add and remove help content-manage content中下载，点击update，文档很大，速度较慢）
    • C#语言定义文档（Language Specification）（特点：精确，难读懂，会出现很大的跳跃性，看不懂的去看MSDN文档，谷歌下载即可）
    • 推荐数据：C# 5.0 In A Nutshell（特点：读MSDN文档的指南针，其中列出了重点）

  • MSDN文档中最重要的部分：

    • Visual Basic and Visual C#-Visual C#-C# Programming Guide
    • Visual Basic and Visual C#-Visual C#-C# Reference：横向领略C#语言的特性
    • Visual Basic and Visual C#-Visual C#-C# Reference-C# Sample Application：源码
    • Visual Basic and Visual C#-Visual C#-C# Reference-C# Walkthroughs：功能浏览

本节课作业

  • 下载并安装Visual Studio Express 2013 for Windows Desktop（建议学生下载professional版本，其对学生免费）
  • 下载离线MSDN文档并尝试阅读
  • 编写视频中的小程序（所见即所得的wpf程序）

作业完成情况

  • HelloWorld项目的地址：D:\OneDrive - stu.xjtu.edu.cn\文档\Visual Studio 2013\Projects
  • MSDN文档成功下载了下面四个（最重要的文档已经下载下来了，其他文档要么是没有要么是下载失败）：
    • .NET Framework 4
    • Get started with Blend for Visual Studio 2013
    • Welcome to Visual Studio 2013
    • Visual Basic and Visual C#

2. 初识各类应用程序

带领大家认识各种可以用C#编写的应用程序

编程学习的捷径

  • 编程不是“学”出来的，而是“练”出来的
  • 在反复应用中积累，忽然有一天就会“顿悟”。在实践中理解书本上知识的精髓。
  • 学习原则
    • 从感观到原理
    • 从使用别人的到创建自己的
    • 必须亲自动手
    • 必须学以致用、紧跟实际工作
    • 追求实用，不搞“学院派”

编写我们的第一个程序——Hello, World!

  • Solution与Project

    • Solution是针对客户需求的总的解决方案。举例：汽车经销商需要一套销售软件
    • Project利用具体的技术解决具体的某个问题
    • Visual Studio针对不同技术有不同的Project模板
    • Visual Studio在管理代码时，解决方案（Solution）在最高的级别。一个Solution中可以包含一到多个Project。

    如下图所示（各个组件是Project，所有Project在一起构成一个Solution）：

    solution and project.png

  • Project模板（对比不同VS版本）

    VS有各种版本（express, professional, ultimate），版本越高级，其中包含的Project的模板越多，所支持的开发技术越多。一般来说，professional版本足够用了。

  • 分别编写Console, WPF, Windows Forms的Hello World程序

  • 初学编程时很重要的两点

    • 不要怕见到自己看不懂的东西
    • 要跟着操作，一遍一遍地练习，为的是熟悉手里的工具，培养感觉

见识C#编写的各类应用程序

  • 目的1：让大家拥有辨识各类程序的“火眼金睛”
  • 目的2：让大家了解一下完成C#语言学习后的职业发展方向（你最喜欢哪种？）

十种技术编写Hello World程序，打星号的是当下流行的技术。

Console（控制台）

  • File-New Project-Visual C#-Windows-Console Application，可以分别设置solution和project的name。

  • C#的源码文件用.cs作为扩展名

  • 写入以下的代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace ConsoleHelloWorld
    {
        class Program
        {
            static void Main(string[] args)
            {
                Console.WriteLine("Hello, World!");
            }
        }
    }

  • 运行时，直接点击Start会一闪而过，选择Debug-Start Without Debugging，就可以持续看到结果。

WPF(Windows Presentation Foundation)*

注意对比其与WPF。新建项目，选择WPF Application。现在页面下方出现了一些类似html的代码（xaml代码），设计师可以直接通过修改这些代码来设计界面。我理解类似前后端分离，同时前端不需要写代码，有可视化界面。后端的代码类似Windows Forms。

  • 点击Toolbox，搜索TextBox，将其拖入窗口中并调整大小。改Name，去掉其中的Text。

  • 再搜索Button，将其拖入窗口中并调整大小。改Name，改其中的Text。

  • 既可以改代码来改属性，也可以改可视化界面来改属性。

  • 选中Button，点击Events。目前Click的值为空，点击Button不会有响应。双击Button，同样生成代码模板，在其中写入以下的代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    using System.Windows;
    using System.Windows.Controls;
    using System.Windows.Data;
    using System.Windows.Documents;
    using System.Windows.Input;
    using System.Windows.Media;
    using System.Windows.Media.Imaging;
    using System.Windows.Navigation;
    using System.Windows.Shapes;

    namespace WpfHelloWorld
    {
        /// <summary>
        /// Interaction logic for MainWindow.xaml
        /// </summary>
        public partial class MainWindow : Window
        {
            public MainWindow()
            {
                InitializeComponent();
            }

            private void buttonSayHello_Click(object sender, RoutedEventArgs e)
            {
                textBoxShowHello.Text = "Hello, World!";
            }
        }
    }

  • 运行项目，点击Click Me按钮，TextBox中出现Hello, World!

Windows Forms(Old)

新建项目，选择windows forms application。

  • 点击Toolbox，搜索TextBox，将其拖入窗口中并调整大小。

  • 再搜索Button，将其拖入窗口中并调整大小。

  • 修改Button的属性：修改其上的文字，给其起一个带有独特含义的名字

  • 修改TextBox的属性：修改其名字为textBoxShowHello

  • 选中Button，在属性面板有闪电符号，就是Events（事件）。当前Click对应的值为空，表示点击Click没有任何的反应。双击事件中的Click，自动生成了代码模板。写入以下的代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    using System;
    using System.Collections.Generic;
    using System.ComponentModel;
    using System.Data;
    using System.Drawing;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    using System.Windows.Forms;

    namespace WinFormHelloWorld
    {
        public partial class Form1 : Form
        {
            public Form1()
            {
                InitializeComponent();
            }

            private void buttonSayHello_Click(object sender, EventArgs e)
            {
                textBoxShowHello.Text = "Hello, World!";
            }
        }
    }

  • 现在点击click me时，文本框就显示了Hello, World!现在让程序响应了button click事件，程序的相应为在TextBox中显示出Hello, World。

ASP.NET Web Forms(Old)

选择visual c#-web-asp.net web application，再选择empty，勾选web forms。此时就获得了一个空的网站。右击右侧菜单的WebFormHelloWorld，选择add-web form，输入其名称为default，这样就生成了一个模板代码Default.aspx。在其中加入Hello, World:

1
2
3
4
5
6
7
8
9
10
11
12
<%@ Page Language="C#" AutoEventWireup="true" CodeBehind="Default.aspx.cs" Inherits="WebFormHelloWorld.Default" %>

<!DOCTYPE html>

<html xmlns="http://www.w3.org/1999/xhtml">
<head runat="server">
    <title></title>
</head>
<body>
<h1>Hello, World!</h1>
</body>
</html>

点击运行（点击浏览器的名称即可），网页就显示出了Hello, World!。右键WebFormHelloWorld，点击publish，即可将其部署，供外人访问。

ASP.NET MVC(Model-View-Controller)*

是ASP.NET Web Forms技术的升级版。其特点是代码解耦合，易于维护。创建项目同ASP.NET Web Forms，但是要点击empty，勾选MVC。选择controllers-add-controller，选择MVC 5 Controller - Empty，点击add，然后输入其名称为HomeController，然后add。此时生成了HomeController.cs的样板代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Web.Mvc;

namespace MvcHelloWorld.Controllers
{
    public class HomeController : Controller
    {
        //
        // GET: /Home/
        public ActionResult Index()
        {
            return View();
        }
	}
}

此时views文件夹中的home文件夹中还没有任何view。在函数：public ActionResult Index()中右击，选择add view，点击add，此时在home文件夹中生成了Index.cshtml。在其中写入代码：

1
2
3
4
5
@{
    ViewBag.Title = "Index";
}

<h2>Hello, Wolld!</h2>

点击运行，网页上出现了Hello, World!同样也可以将这个项目publish到自己的网站上去。

WCF(Windows Communication Foundation)*

wcf是纯粹的网络服务。创建项目时选择visual c#-wcf-wcf service application，命名为WcfHello。

打开模板代码IService1.cs，在其中写入代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public interface IService1
{

    [OperationContract]
    string GetData(int value);

    [OperationContract]
    CompositeType GetDataUsingDataContract(CompositeType composite);

    [OperationContract]
    string SayHello();

    // TODO: Add your service operations here
}

回到Service1.svc.cs中，点击IService1下面的蓝色小标记，选择Implement interface IService1。此时就会生成模板代码：

1
2
3
4
public string SayHello()
{
    throw new NotImplementedException();
}

将其改为：

1
2
3
4
public string SayHello()
{
    return "Hello, World!";
}

点击运行，会启动wcf test client的工具。wcf是最特殊的服务，只有纯粹的数据交互，没有前端，因此需要用到这个测试工具。双击其中的SayHello()，点击Invoke，就会调用SayHello函数，该函数会返回一个hello world给客户端。我尝试调用，果然在测试界面打印出了hello world。

现在尝试写一个加法器，在IService1.cs中写：

1
2
[OperationContract]
double Add(double a, double b);

在Service1.svc.cs中写：

1
2
3
4
public double Add(double a, double b)
{
    return a + b;
}

再次运行，双击Add方法，设置a和b的值为10和20，点击Invoke，计算结果为30。

Windows Store Application*

给平板电脑app写的程序。选择visual c#-windows store-blank app(xaml)。其和WPF很像。打开MainPage.xaml，将ToolBox中的TextBox拖进去，然后再拖入button。将TextBox重命名为textBoxShowHello，再将其中的Text清空。将buttom重命名为buttonSayHello，将其content改为Click Me。选择simulator，运行之，此时点击button没有任何反应。

选择button-click，然后双击，生成模板代码，在其中写入代码：

1
textBoxShowHello.Text = "Hello, World!";

再次在simulator中运行，此时点击click me，hello world就出现了。

Windows Phone Application*

创建项目，选择visual c#-windows phone-windows phone app，取名为PhoneHelloWorld。生成的代码同样和wpf非常类似。

同样的，在ToolBox中搜索TextBox，拖入界面中，取名为textBoxShowHello，清空text；再搜索Button，同样拖入界面中，取名为buttonSayHello，将content改为click me；再切换到Button的事件中去，双击click，生成模板代码，写入以下内容：

1
textBoxShowHello.Text = "Hello, World!";

选择一款较好的模拟器（内存和屏幕分辨率可选），然后执行。点击click me，hello world就出现了。

如何部署到手机上？
选择build-deploy solution，如果windows phone连接到了电脑上，就会直接找到该设备然后部署上去。

Cloud(Windows Azure)*

微软云计算平台上的hello world。创建项目，选择visual c#-cloud-windows azure cloud service，项目取名为CloudHelloWorld，要架网站，就选择asp.net web role，点击右箭头将其加到云平台上，改名为SayHello，点击OK。选择empty，勾选MVC。此时看上去和ASP.NET MVC完全相同。

右键controllers-add-controller，选择MVC 5 Controller - Empty，取名为HomeController。在生成的主函数中右键，add view，点击add。在index.cshtml中，写上hello world。点击运行即可，此时要启动云平台的模拟器才能运行程序。

查找最近的项目：file-recent projects and solutions

云平台模拟器会加载刚刚写的网站。

部署时，右键CloudHelloWorld，选择publish，选择云平台的订阅，就可以直接发布。发布网站需要买域名，买空间，但微软的云平台替你完成了这些步骤。

WF(Workflow Foundation)

workflow：工作流。选择visual c#-workflow-workflow console application，这个工作流执行起来是在console中执行，命名为WfHelloWorld。

在ToolBox中搜索WriteLine，拖入界面中，在其中写入"Hello, World!"，点击debug-start with debugging。

3. 初识类与名称空间

剖析Hello, World程序

剖析的对象：最简单的console application。

  • 初识类（class）与名称空间（namespace）
    • 初学者：类（class）构成程序的主体。高级版本：类是最基础的C#类型。类是一个数据结构，将状态（字段）和操作（方法和其他函数成员）组合在一个单元中。类为动态创建的类实例（instance）提供了定义，实例也称为对象（object）。类支持继承和多态性，这是派生类可用来扩展和专用化基类的机制。
    • 名称空间（namespace）以树型结构组织类（和其他类型），也可以有效地避免同名类的冲突。
      • 例如Button和Path类

  • 下面以HelloWorld程序来展示类和名称空间。有以下代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    // using是将名称空间引用到程序中来
    // 名称空间的标记是{}
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    // 编写的Program类放在了ConsoleHelloWorld这个名称空间中，该名称空间的名字默认和project的名字一样
    namespace ConsoleHelloWorld
    {
        // 类在visual studio中高亮的颜色是水蓝色
        // c#是完全面向对象的
        class Program
        {
            static void Main(string[] args)
            {
                // Console类是内置的，我们利用其中的WriteLine方法
                Console.WriteLine("Hello, World!");
            }
        }
    }

    也可以简写为（权限命名写法）：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    namespace ConsoleHelloWorld
    {
        class Program
        {
            static void Main(string[] args)
            {
                System.Console.WriteLine("Hello, World!"); // 权限命名写法
            }
        }
    }

    打印两行：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    namespace ConsoleHelloWorld
    {
        class Program
        {
            static void Main(string[] args)
            {
                System.Console.WriteLine("Hello, World!");
                System.Console.WriteLine("Good morning!");
            }
        }
    }

    更方便的写法是引入名称空间：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    using System;

    namespace ConsoleHelloWorld
    {
        class Program
        {
            static void Main(string[] args)
            {
                Console.WriteLine("Hello, World!");
                Console.WriteLine("Good morning!");
                Console.WriteLine("Good evening!");
            }
        }
    }

    如何知道某个函数属于哪个名称空间？

    • 方法1：help-view help，在index中搜索console class，可以看到相应的文档。其中有信息：Assembly: mscorlib (in mscorlib.dll)，mscorlib(microsoft core library)是类库。与操作系统有关的重要的类都在System这个名称空间中。
    • 点击报红的单词的任意位置，单词的首字母处会出现蓝色的小方块，为智能标记。点开智能标记，可选择Using System或者System.Console。弹出智能标记的快捷键：ctrl + .或者Shift+Alt+F10。

    不同命名空间中相同的类名产生冲突的例子：

    新建一个wpf程序。在MainWindow.xaml.cs中，可以存在两个path类，分别是：

    1
    2
    System.Windows.Shapes.Path
    System.IO.Path

    前者是windows中用于画多边形的path，后者是文件路径的path。如果需要同时用到两者，就只能用权限命名。

    另一个例子：button class有更多种，用来写web/.NET/windows等等。使用名称空间就可以解决类名冲突的问题。

类库(assembly)的应用

dll: dynamic link library（动态链接库），以ddl结尾的文件是类库。

类和名称空间是放在类库中的。类库是类的仓库。

  • 类库引用是使用名称空间和类的物理基础

以一个wpf程序为例，其中的Button

  • 名称空间为System.Windows.Controls
  • 类库为 (in PresentationFramework.dll)
  • 如何查看类库引用在项目的哪里？在项目的References中就可以看到PresentationFramework。双击PresentationFramework，打开的窗口为对象浏览器（ObjectBrowser）。展开其中的PresentationFramework，即可看到有哪些名称空间，展开名称空间又可以看到其中有哪些类。

Console application由于不需要显示窗口，因此需要引用的类库要少于wpf application。

不同技术类型的项目会默认引用不同的类库。

如何为自己的项目添加对其他类库的引用？

  • DLL引用（黑盒引用，无ddl的源代码，直接用编译好的dll文件）

    • 以输出hello world的console application为例。如果有一个外部的dll，必须配有文档。例如一个文件夹中存放了MyLibrary.dll和MyLibrary Document。右键项目的references-add reference-browse，即可把dll文件给加载进来，此时MyLibrary就会出现在References中。然后可以对照文档来使用类库中的名称空间、类和方法。也可以双击References中的MyLibrary，打开对象浏览器，来查看其中的名称空间、类和方法。

    • 黑盒引用的问题：类库一旦出错，本人无法修改，只能让类库的编写者去修改，然后编写者再次将类库编译为ddl并将该文件发送给本人，才能解决这个错误。此时我的项目会对类库产生依赖，我的Program类也会对类库中的类和方法产生依赖。这就是依赖关系。尽量使用弱的依赖关系，避免牵一发而动全身的问题。有一些办法可以减轻依赖关系。

    • 做实验：引用微软提供的类库，让console application显示窗口。在references中添加类库：System.Windows.Forms。help viewer中的msdn文档搜索功能非常难用，不如用微软提供的在线文档。让console application显示窗口的代码为：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      using System;
      using System.Windows.Forms;

      namespace ConsoleHelloWorld
      {
          class Program
          {
              static void Main(string[] args)
              {
                  Form form = new Form();
                  form.ShowDialog();
              }
          }
      }

    • NuGet简介

      使用NuGet添加对dll的引用。NuGet技术被用来解决比较复杂的依赖关系（复杂的依赖关系：底层的类库未被引用，则上层的类库也无法被引用）。

      • 做实验，在console application中引入一个wpf的窗口。在References中添加依赖：PresentationFramework。然后写入以下代码：

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        using System;
        using System.Windows.Forms;

        namespace ConsoleHelloWorld
        {
            class Program
            {
                static void Main(string[] args)
                {
                    System.Windows.Window window = new System.Windows.Window();
                    window.ShowDialog();
                }
            }
        }

        运行时会产生报错：

        1
        2
        3
        Error	1	The type 'System.Windows.Markup.IAddChild' is defined in an assembly that is not referenced. You must add a reference to assembly 'PresentationCore, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35'.	d:\OneDrive - stu.xjtu.edu.cn\文档\Visual Studio 2013\Projects\ConsoleHelloWorld\ConsoleHelloWorld\Program.cs	10	13	ConsoleHelloWorld

        Error	2	The type 'System.Windows.Markup.IQueryAmbient' is defined in an assembly that is not referenced. You must add a reference to assembly 'System.Xaml, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089'.	d:\OneDrive - stu.xjtu.edu.cn\文档\Visual Studio 2013\Projects\ConsoleHelloWorld\ConsoleHelloWorld\Program.cs	10	13	ConsoleHelloWorld

        报错说明更底层的类库：PresentationCore和System.Xaml还没有被引用，需要将这两者加入到References中。再运行时，还会出现报错：

        1
        Error	2	The type 'System.Windows.DependencyObject' is defined in an assembly that is not referenced. You must add a reference to assembly 'WindowsBase, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35'.	d:\OneDrive - stu.xjtu.edu.cn\文档\Visual Studio 2013\Projects\ConsoleHelloWorld\ConsoleHelloWorld\Program.cs	10	13	ConsoleHelloWorld

        还需要添加更底层的WindowsBase，这很麻烦。因为这时候你只有DLL，没有源代码，几乎可以说是“蒙着眼睛引用类库”。这是很危险的！特别是对于大型的项目。

        后来有人用包的形式发布一组类库，用户输入命令，一组类库就都被引用了，不需要手动引用，这样很安全且高效，这就是NuGet技术。

        例如需要写一个用于连接数据库的程序，需要用到技术Entity Framework（实体框架），该类库可以将代码中的类和数据库中的表映射起来。可以采用NuGet技术来对上述类库进行引用。右击References-点击add nuget packages-选择online-输入Entity Framework，点击Install即可，此时就会看到两个自动安装的类库：EntityFramework和EntityFramework.SqlServer，这两个类库由NuGet自动管理。但是我这样操作搜索不到结果，于是我采用了另一种方式。点击Tools-Library Package Manager-Package Manager Console，在其中输入命令：Install-Package EntityFramework，也可以起到相同的效果。

  • 项目引用（白盒引用，有源代码，源代码放在项目中，故称项目引用）

    直接获得类库项目的源代码，比如类库项目的名字是MyLibrary，其中的代码名为Calculator.cs，代码为：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace Tools
    {
        public class Calculator
        {
            public static double Add(double a, double b)
            {
                return a + b;
            }

            public static double Sub(double a, double b)
            {
                return a - b;
            }
        }
    }

    如何引用MyLibrary这个类库，点击References-add references-solution-projects，当前的projects页面为空，因此需要将MyLibrary这个project添加到当前的solution中去。一个项目可以被多个solution包含（这被称为project的重用），因此将类库项目也包含到当前的solution中。将类库的project包含到当前solution中的操作：solution-add-existing project，选中MyLibrary-MyLibrary.csproj，将其添加进来。现在solution中有两个项目，一个是HelloWorld，一个是MyLibrary。再次右击References-add references-solution-projects，勾选MyLibrary，点击OK，此时MyLibrary就作为类库被成功引用了。此时就可以愉快地在console application中引用MyLibrary中的类和方法了：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    using System;

    namespace ConsoleHelloWorld
    {
        class Program
        {
            static void Main(string[] args)
            {
                double result = Tools.Calculator.Sub(1, 1);
                Console.WriteLine(result);
            }
        }
    }

    此时由于已经有了类库的源代码，就可以对类库中的错误进行排除。接下来的内容跳转到排除错误部分。

依赖关系

类与类之间，类库与类库之间一旦互相引用，就产生了依赖关系。依赖关系在软件质量中起了关键作用。

质量好的软件，其依赖关系清晰且好维护；质量差的软件，依赖关系不清楚。

  • 依赖关系，就是类（或对象）之间的耦合关系

  • 优秀的程序追求“高内聚，低耦合”

    • 高内聚指的是一些数据和功能，该属于哪个类，就精确地放入哪个类。
    • 低耦合指的是类和类之间的依赖关系尽可能低
    • “高内聚，低耦合”对类和类库都是如此
    • 程序只有这样做才会结构清晰
    • 教学程序往往会违反这个原则

  • UML（通用建模语言）类图：以图的形式表达程序中的关系，UML除了可以画类图，还可以画流程图、序列图等。类图用来展现类和类之间的关系。以HelloWrold程序为例：

    uml.png

    这是一种非常紧密的耦合关系。

排除错误

如何排除程序中的错误？

在项目引用时，由于有类库的源代码，可以直接debug。点击出错的行（double result = Tools.Calculator.Sub(1, 1);），设置断点。然后debug-start debugging，此时程序会执行到断点前，result值为0.0（还未进行出错行的运算）。接下来点击step into(F11)，此时执行指针就自动跳转到了类库的此处：

1
2
3
4
public static double Sub(double a, double b)
{
    return a - b - 10;
}

就可以发现错误的出处。debug时需要找到root cause。

中文标点符号：全角
英文标点符号：半角

  • 仔细阅读编译器的报错
  • MSDN文档与搜索引擎结合

如何建立一个类库项目

solution-add-new project-class library（非可执行程序，编译出来的结果就是dll文件，即类库），项目起名为SuperCalculator，模板代码重命名为Calculator.cs，在其中写入代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Tools
{
    public class Calculator
    {
        public static double Add(double a, double b)
        {
            return a + b;
        }

        public static double Sub(double a, double b)
        {
            return a - b;
        }

        public static double Mul(double a, double b)
        {
            return a * b;
        }

        public static double Div(double a, double b)
        {
            if (b == 0)
            {
                return double.PositiveInfinity;
            }
            else
            {
                return a / b;
            }
        }
    }
}

接着右击references-add reference-project-SuperCalculator，将这个自定义的类库引入主程序，就可以在主程序中使用它：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using System;
using Tools;

namespace ConsoleHelloWorld
{
    class Program
    {
        static void Main(string[] args)
        {
            double result1 = Calculator.Mul(3, 4);
            Console.WriteLine(result1);
            double result2 = Calculator.Div(3, 4);
            Console.WriteLine(result2);
            double result3 = Calculator.Div(3, 0);
            Console.WriteLine(result3);
        }
    }
}

本节作业

  • 练习创建类库项目进行项目引用
  • 练习DLL引用
  • 练习阅读编译器报错并排除错误

4. 类、对象、类成员简介

类（class）是显示世界事物的模型

  • 类是现实世界事物进行抽象所得到的结果
    • 事物包括“物质”（实体）与“运动”（逻辑）
    • 抽象也被称为建模。建模是一个去伪存真（留下需要的，去掉不要的）、由表及里（暴露的接口是表，封装的内容是里）的过程

类与对象的关系

  • 什么时候叫“对象”，什么时候叫“实例”

    • 对象也叫实例，是类经过“实例化”后得到的内存中的实体

      • Formally “instance” is synonymous with “object”——对象和实例是一回事
      • “飞机”与“一架飞机”有何区别？天上有（一架）飞机——必须是实例飞，概念是不能飞的
      • 有些类是不能实例化的，比如“数学”（Math class），我们不能说“一个数学”

    • 依照类，我们可以创建对象，这就是“实例化”

      • 现实世界中常称“对象”，程序世界中（特别是内存关系）常称“实例”
      • 二者并无太大区别，常常混用，初学者不必迷惑

    • 使用new操作符创建类的实例

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      using System;
      using System.Collections.Generic;
      using System.Linq;
      using System.Text;
      using System.Threading.Tasks;
      using System.Windows.Forms;

      namespace ClassAndInstance
      {
          class Program
          {
              static void Main(string[] args)
              {
                  // 实例化
                  (new Form()).ShowDialog(); // ()表示实例在内存中诞生后的初始化方式，被称为构造器
              }
          }
      }

      上述程序运行的结果就是表单已窗口的形式呈现，即表单已被实例化。

  • 引用变量

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    using System.Windows.Forms;

    namespace ClassAndInstance
    {
        class Program
        {
            static void Main(string[] args)
            {
                Form myForm; // 声明引用变量
                myForm = new Form(); // 用引用变量引用一个实例
                myForm.Text = "My Form!"; // 设置标题的文字
                myForm.ShowDialog();
            }
        }
    }

    在使用引用变量引用了一个实例后，我们就可以多次访问这个实例。

  • 引用变量与实例的关系

    • 孩子与气球。孩子相当于引用变量，气球相当于实例。绳子相当于赋值符号

    • 气球不一定有孩子牵着。此时气球就飞掉了，内存垃圾收集器很快就回收了该变量，内存就被释放掉了

    • 多个孩子可以使用各自的绳子牵着同一个气球。如以下代码所示：

      1
      2
      3
      4
      Form myForm1;
      Form myForm2;
      myForm1 = new Form();
      myForm2 = myForm1;

      上面两个引用变量引用的是同一个实例/对象。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      using System;
      using System.Collections.Generic;
      using System.Linq;
      using System.Text;
      using System.Threading.Tasks;
      using System.Windows.Forms;

      namespace ClassAndInstance
      {
          class Program
          {
              static void Main(string[] args)
              {
                  Form myForm1;
                  Form myForm2;
                  myForm1 = new Form();
                  myForm2 = myForm1;
                  myForm1.Text = "My Form";
                  myForm2.Text = "I changed it!";
                  myForm1.ShowDialog();
              }
          }
      }

      此时显示的是I changed it!。用任何一个引用变量访问到的都是同一个实例。

      多个孩子也可以都通过同一根绳子牵着气球，目前暂且不讲。

类的三大成员

类的成员有十多种，但这三种非常重要，也是初学者最先接触到的。

  • 属性（Property）

    • 用于存储数据
    • 这些数据组合起来表示类或对象当前的状态

  • 方法（Method）

    • 由C语言中的函数（function）进化而来，表示类或对象“能做什么”
    • 工作中90%的时间是在与方法打交道，因为它是“真正做事”、“构成逻辑”的成员

  • 事件（Event）

    • 类或对象通知其他类或对象的机制，为C#所特有（Java通过其他方法实现这个机制）。例如当点击按钮时，发生click这个事件，响应该事件的方法中可以让界面上的文本框显示出Hello World的字符串。
    • 事件是非必须的，但有它在编程会变得方便且灵活，但这也意味着它可能会被滥用。因此，善用事件机制非常重要。

  • 使用MSDN文档。将鼠标移到一个类上，按下快捷键ctrl+shift+F1，就可以跳转到相应的MSDN文档。如果想看该类在哪个分支上，点击左上角的show topic in contents按钮。以Form class为例，其下面的第一句话：Represents a window or dialog box that makes up an application's user interface.，是以一句话概括本类的作用。接着是：

    • 继承关系列表：Inheritance Hierarchy
    • 名称空间：namespace
    • 类库: Assembly
    • 声明的格式：Syntax
    • 构造函数: Constructors
    • 属性：要么用来记忆值，要么表示Form的状态
    • 方法：Form这个类/对象可以做什么
    • 事件：表示Form能以怎样的形式在发生什么事情时通知别的类或对象
    • 类的详细解释，包含了类最常用的功能（即最常用的属性、方法和事件）：Remarks
    • 例子：Examples。MSDN的例子质量良莠不齐
    • 版本信息
    • 平台
    • 多线程安全性：Thread Safety

  • 某些特殊类或对象在成员方面侧重点不同

    • 模型类或对象重在属性，如Entity Framework。模型类的功能主要是从数据库中读取数据，然后把数据写回数据库。其侧重于数据，因此属性特别发达。例子：用Entity Framework生成的作为数据模型的类。首先需要安装Entity Framework及其相关的包，可以使用Nuget/命令行，我的Nuget不管用，因此使用命令行。

      打开sql server 2012 developer version，创建一个样例数据库：AdventureWorksLT2012，打开Tables，再打开SalesLT.Product，打开其前1000行，主要包含ProductID, Name, ProductNumber, Color等数据。

      在项目中，右击solution-add-new item-data-ado.net entity data model，将其名字改为AdventureWorksModel.edmx。选择generate from database，然后新建一个和本地数据库AdventureWorksLT2012的连接。然后选择Product表和Address表。此时visual studio就和entity framework一起生成了一些专门用于数据传输的数据模型类。会显示两个数据模型类，分别是Product和Address类。这两个类中，只有属性，没有方法和事件。使用这些类的代码：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      // 打印产品的Name属性
      AdventureWorksLT2012Entities proxy = new AdventureWorksLT2012Entities();

      // 快速插入foreach代码的方法是：输入foreach时，当VS2013有所提示时，连续按两下Tab键
      foreach(Product p in proxy.Products)
      {
          // 输入cw，然后按两下tab键，就会补全为Console.WriteLine
          Console.WriteLine(p.Name);
      }

      // 打印产品的数目
      Console.WriteLine("==========================="); // 分割线
      Console.WriteLine(proxy.Products.Count());

    • 工具类或对象重在方法，如Math, Console。工具类主要用于计算和其他具体功能。以Math为示例：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      using System;
      using System.Collections.Generic;
      using System.Linq;
      using System.Text;
      using System.Threading.Tasks;

      namespace MethodSample
      {
          class Program
          {
              static void Main(string[] args)
              {
                  double x = Math.Sqrt(4);
                  Console.WriteLine(x);

                  double y = Math.Pow(2, 3);
                  Console.WriteLine(y);
              }
          }
      }

    • 通知类或对象重在事件，如各种Timer（时钟每隔一段时间触发某个事件，这个事件会执行某些功能）。

      新建WPF Application，先创建一个合适大小的textBox，然后去后台，写入以下代码，即可生成一个简易的时钟：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      using System;
      using System.Collections.Generic;
      using System.Linq;
      using System.Text;
      using System.Threading.Tasks;
      using System.Windows;
      using System.Windows.Controls;
      using System.Windows.Data;
      using System.Windows.Documents;
      using System.Windows.Input;
      using System.Windows.Media;
      using System.Windows.Media.Imaging;
      using System.Windows.Navigation;
      using System.Windows.Shapes;
      using System.Windows.Threading;

      namespace EventSample
      {
          /// <summary>
          /// Interaction logic for MainWindow.xaml
          /// </summary>
          public partial class MainWindow : Window
          {
              // Window的构造函数
              public MainWindow()
              {
                  InitializeComponent();
                  DispatcherTimer timer = new DispatcherTimer();
                  timer.Interval = TimeSpan.FromSeconds(1); // 时间间隔1秒钟

                  // 写完+=后，连续按两次tab键
                  // 将timer_Tick函数挂接到事件上
                  // 当事件Tick被触发时，timer_Tick函数就会被执行
                  // timer_Tick方法用于响应事件，因此该方法也被称为事件处理器
                  timer.Tick += timer_Tick;

                  // 让时钟开始
                  timer.Start();
              }

              void timer_Tick(object sender, EventArgs e)
              {
                  this.timeTextBox.Text = DateTime.Now.ToString();
              }
          }
      }

类的静态成员与实例成员

  • 静态（Static）成员在语义上表示它是“类的成员”

  • 实例（非静态）成员在语义上表示它是“对象的成员”，而非“类的成员”

  • 例子：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    using System.Windows.Forms;

    namespace StaticSample
    {
        class Program
        {
            static void Main(string[] args)
            {
                // WriteLine方法是隶属于Console类的，因此该方法是静态方法
                Console.WriteLine("Hello");

                Form form = new Form();
                form.Text = "Hello"; // Text是实例属性
                form.ShowDialog(); // ShowDialog是实例方法
            }
        }
    }

  • 在MSDN文档中，若某个属性上面加了红色的大写的S，那么其是静态属性。同理，同样的标记也被用于静态方法。静态事件非常少见。

  • “绑定”（Binding）指的是编译器如何把一个成员 与 类或对象关联起来

    • 早绑定。编译器就决定将成员与哪个类/对象关联。

    • 晚绑定。程序运行起来后，再决定将成员与哪个类/对象关联，编译器不知道此事。有晚绑定功能的语言是动态语言，比如javascript。

    • 不可小觑的“.”操作符——成员访问

本节作业

  • 跟着视频进行操作，直到能够自己动手编写这些程序

5. 语言基本元素概览、初始类型、变量与方法，算法简介

构成C#语言的基本元素

前五种被统称为标记（Token）。标记是对编译器有意义的记号。

  • 关键字（Keyword）：构成一门编程语言的基本词汇。

    具体参照这个文档：https://learn.microsoft.com/en-us/previous-versions/visualstudio/visual-studio-2013/x53a06bb(v=vs.120)?redirectedfrom=MSDN

    其中包含两个表格，第一个表格中的关键字一直都是关键字（70多个），第二个表格中的关键字是上下文关键字（20多个）。一共100多个关键字。

    注意：

    • 某些关键字有多个用途
    • 关键字按照逻辑分组，可以分为Types, Modifiers, Statement, Namespace, Operator等

  • 操作符（Operator）

    查看文档：https://learn.microsoft.com/en-us/previous-versions/visualstudio/visual-studio-2013/6a71f45d(v=vs.120)?redirectedfrom=MSDN

    操作符大概30-40个。有些操作符是关键字，因此这类关键字被称为操作符关键字。

  • 标识符（Identifier），即名字

    • 什么是合法的标识符

      • 首先不能与关键字冲突。关键字又名保留字，不能被用来作为标识符。

      • 可以用字母、数字和下划线来组成标识符，但是不能拿数字开头，可以拿字母和下划线开头。

      • 怎样阅读语言定义文档

        以Identifier为例：

        identifier1.png

        identifier2.png

        • 斜体字意味着还未完全解释清楚，后面还有它的解释
        • 标识符=非关键字的标识符&关键字+@ 标识符&关键字
        • 下标opt表示可选的
        • 汉语也可以用作标识符

    • 大小写规范：驼峰命名法（myVariable），pascal命名法（MyVariable）

      C#中，变量名都用驼峰法，方法名、类名、名称空间等用pascal法

    • 命名规范：要求变量名、类名、类的成员都有意义

      • 类名是一个名词
      • 类的成员名的属性是名字，方法是动词/动词短语

  • 标点符号：比如{}, ;。是符号，但是不参与运算。

  • 文本（字面值）

    • 整数

      • 多种后缀

      • 例子：

        1
        2
        int x = 2; // 32 bit表示一个数字
        long y = 3L; // 大小写L均可，64 bit表示一个数字，long能表示的数字范围广于int

    • 实数

      • 多种后缀

      • 例子：

        1
        2
        3
        float x = 3.0F; // 32 bit表示一个浮点数，F是必须的后缀，否则3.0默认为双精度浮点数
        double y = 4.0D; // D表示双精度浮点数, 64 bit表示一个浮点数
        double z = 4.0;

    • 字符

    • 字符串

      • 例子：
        1
        2
        3
        4
        char c = 'a'; // 单引号中只能有一个字符，字符类型的变量必须用单引号
        string str1 = "ABCDE";
        string str2 = "a";
        string str3 = "";

    • 布尔

    • 空（null）

      • 例子：
        1
        2
        3
        bool b = true;
        bool b2 = false;
        string str = null;

  • 注释与空白

    • 单行：//
    • 多行（块注释）：/* */。块注释不能嵌套
    • 空白：一个空白和多个空白/tab键生成的空白没有区别
    • 格式化代码：edit-advanced-format document，快捷键为ctrl + k, ctrl + d

简要介绍类型、变量与方法

  • 初识类型（Type）

    • 亦称数据类型（Data Type）：明确的数据类型/推断的数据类型（var）

    • 例子：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      var x = 3; // 编译器会根据赋的值自动推断var变量的类型
      Console.WriteLine(x.GetType().Name); // 输出为Int32

      var y = 3L;
      Console.WriteLine(y.GetType().Name); // 输出为Int64

      var z = 3.0;
      Console.WriteLine(z.GetType().Name); // 输出为Double

      var w = 3.0F;
      Console.WriteLine(w.GetType().Name); // 输出为Single

  • 变量是存放数据的地方，简称“数据”

    • 变量的声明
    • 变量的使用

  • 方法（旧称函数）是处理数据的逻辑，又称“算法”

    • 方法即成员函数

    • 方法的声明

    • 方法的调用

    • 例子：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      using System;
      using System.Collections.Generic;
      using System.Linq;
      using System.Text;
      using System.Threading.Tasks;

      namespace Identifier
      {
          class Program
          {
              static void Main(string[] args)
              {
                  Calculator c = new Calculator();
                  int x = c.Add(3, 4);
                  Console.WriteLine(x);

                  string str = c.GetToday();
                  Console.WriteLine(str);

                  c.PrintSum(2, 3);
              }

          }

          class Calculator
          {
              // 方法
              public int Add(int a, int b)
              {
                  int result = a + b;
                  return result;
              }

              public string GetToday()
              {
                  int day = DateTime.Now.Day;
                  return day.ToString();
              }

              public void PrintSum(int a, int b)
              {
                  int result = a + b;
                  Console.WriteLine(result);
              }
          }
      }

  • 程序=数据+算法

    • 有了变量和方法就可以写有意义的程序了

算法简介

  • 循环初体验

    循环又称迭代。例子：打印x到1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace Identifier
    {
        class Program
        {
            static void Main(string[] args)
            {
                Calculator c = new Calculator();
                c.PrintXTo1(10);
            }

        }

        class Calculator
        {
            public void PrintXTo1(int x)
            {
                for (int i = x; i > 0; i--)
                {
                    Console.WriteLine(i);
                }
            }
        }
    }

  • 递归初体验

    例子：打印x到1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace Identifier
    {
        class Program
        {
            static void Main(string[] args)
            {
                Calculator c = new Calculator();
                c.PrintXTo1(10);
            }

        }

        class Calculator
        {
            // 递归写法
            public void PrintXTo1(int x)
            {
                if (x == 1)
                {
                    Console.WriteLine(x);
                }
                else
                {
                    Console.WriteLine(x);
                    PrintXTo1(x - 1);
                }
            }
        }
    }

  • 计算1到100的和

    循环写法：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace Identifier
    {
        class Program
        {
            static void Main(string[] args)
            {
                Calculator c = new Calculator();
                int result = c.SumFrom1ToX(100);
                Console.WriteLine(result);
            }

        }

        class Calculator
        {
            // 循环写法
            public int SumFrom1ToX(int x)
            {
                int result = 0;
                for (int i = 1; i < x + 1; i++)
                {
                    result += i;
                }
                return result;
            }
        }
    }

    递归写法：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace Identifier
    {
        class Program
        {
            static void Main(string[] args)
            {
                Calculator c = new Calculator();
                int result = c.SumFrom1ToX(100);
                Console.WriteLine(result);
            }

        }

        class Calculator
        {
            // 递归写法
            public int SumFrom1ToX(int x)
            {
                if (x == 1)
                {
                    return 1;
                }
                else
                {
                    int result = x + SumFrom1ToX(x - 1);
                    return result;
                }
            }
        }
    }

本节作业

独立完成“汉诺塔问题”

汉诺塔的问题：n个盘子，由A柱子，经过B柱子，最终放到C柱子上。

以递归角度进行分析为：

  • 把n-1个盘子由A移动到B；(借助辅助塔C)
  • 把第n个盘子，由A移动到C;
  • 把n-1个盘子由B移动到C; (借助辅助塔A)

汉诺塔的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using System;

namespace Identifier
{
    class Program
    {
        static int m = 0;

        public static void move(int disks, char from, char to)
        {
            Console.WriteLine("移动次数: {0} 把块: {1} 按照如下移动： {2} --> {3}", ++m, disks, from, to);
        }

        public static void hanoi(int disks, char from, char to, char assist)
        {
            if (disks == 1)
            {
                move(1, from, to);
                return;
            }
            else
            {
                hanoi(disks - 1, from, assist, to);
                move(disks, from, to);
                hanoi(disks - 1, assist, to, from);
            }

        }

        static void Main(string[] args)
        {
            char A = 'A';
            char B = 'B';
            char C = 'C';
            hanoi(4, A, C, B);
            Console.WriteLine(m);
        }
    }
}

简化后的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using System;

namespace Identifier
{
    class Program
    {
        static int m = 0;

        public static void move(char from, char to)
        {
            m++;
        }

        public static void hanoi(int disks, char from, char to, char assist)
        {
            if (disks == 1)
            {
                move(from, to);
                return;
            }
            else
            {
                hanoi(disks - 1, from, assist, to);
                move(from, to);
                hanoi(disks - 1, assist, to, from);
            }
        }

        static void Main(string[] args)
        {
            char from = 'A';
            char to = 'C';
            char assist = 'B';
            hanoi(4, from, to, assist);
            Console.WriteLine(m);
        }
    }
}

6. 详解类型、变量与对象（上）

分析编程语言在内存中是如何运作的。

什么是类型（Type）

  • 数据结构是类型的延申。

  • 又名数据类型（Data Type）

    • A data type is a homogeneous collection of values, effectively presented, equipped with a set of operations which manipulate these values.
    • 是数据在内存中存储时的“型号”。内存全称是内部存储单元。当今的计算机架构是冯诺依曼系统，其有几大组成部分：运算器和控制器（CPU），存储器（内存），输入输出系统。程序运行时必须从硬盘加载到内存中，内存越大的计算机，内存中可以同时运行的程序越多。总之，内存是计算机程序运行的空间。外存是扩展存储器，是对内存的扩展，如计算机中的硬盘，硬盘是电磁存储，因此关机后数据也不会丢失。
    • 小内存容纳大尺寸数据会轻则丢失精确度，重则发生错误。
    • 大内存容纳小尺寸数据会导致内存的浪费。
    • 编程语言的数据类型与数学中的数据类型不完全相同。例如数学中3/4=0.75，编程中3/4=0。

  • 强类型语言与弱类型语言的比较

    • 编程时，数据受到数据类型的约束，就是强类型编程语言。数据不严格受数据类型的约束，就是弱类型编程语言。强弱类型语言各有优缺点。C#语言是强类型语言。例子：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      int x;
      x = 100; // 内存中用32 bit/4 Byte来存储100这个整数值
      long y;
      y = 100L; // L代表长整型整数，在内存中用64 bit/8 Byte
      // x = 100L; 这样写会报错，且会build失败

      bool b;
      b = true;
      // b = 100; 报错，因为整数100无法转化为bool类型的值

      int x = 100;
      if (x = 200) // if的括号中明确要求一个bool类型的值。赋值后得到的不是bool值，因此会报错
      {
          Console.WriteLine("It's OK!");
      }

    • C语言实例：if条件

      例子：新建一个c++项目，new project-visual c++-win32-Win32 Console Application

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      // Console.cpp : Defines the entry point for the console application.
      //

      #include "stdafx.h"


      int _tmain(int argc, _TCHAR* argv[])
      {
      	int x = 100;
      	// c中没有专门的布尔类型，只要表达式的值不为0，就算作真，此处赋值后，得到的值为200，算作真
      	if (x = 200) 
      	{
      		printf("It's OK!\n");
      	}

      	return 0;
      }

      C中常见的避免错误的写法，将字面值写到前面去，即200 = x，编译器报错后，就立即改为200 == x。

    • JavaScript示例：动态类型。js中的变量基本不受数据类型的约束。

      例子：新建项目，选择visual c#-web-asp.net web application，选择empty，web forms。右击项目-add-html page，命名为index.html，这样其执行后就是首页。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      <!DOCTYPE html>
      <html xmlns="http://www.w3.org/1999/xhtml">
      <head>
          <title></title>
          <script>
              function ButtonClicked() {
                  var myVar = 100;
                  myVar = "Chen Yifan"; // 强类型中不允许，但js中可以
                  alert(myVar); // 弹出小的警告框，显示100，这里js并没有管100的类型
              }
          </script>
      </head>
      <body>
          <h1>Hello, JavaScript!</h1>
          <input type="button" value="Click Me"onclick="ButtonClicked()"/>
      </body>
      </html>

      弱类型，灵活性与危险并存。

    • C#语言（4.0版本后）对弱类型/动态类型的模仿，例子：

      1
      2
      3
      4
      5
      // c#中的dynamic关键字类似于js中的var关键字
      dynamic myVar = 100;
      Console.WriteLine(myVar);
      myVar = "Chen Yifan";
      Console.WriteLine(myVar);

类型在C#语言中的作用

  • 一个C#类型中所包含的信息有：

    • 存储此类型变量所需的内存空间大小，例如int类型占有4 Byte/32 bit，long类型占有8 Byte/64 bit。

    • 此类型的值可表示的最大、最小值范围（与第一条推算）。可以查看以下的文档?redirectedfrom=MSDN)，再分为三个文档：Integral Types Table?redirectedfrom=MSDN), Floating-Point Types Table?redirectedfrom=MSDN), decimal?redirectedfrom=MSDN)。一般用ulong来表示对象的身份id（类似uuid）。

    • 此类型所包含的成员（如方法、属性、事件等）

    • 此类型由何基类（父类）派生而来。程序未执行时，处于静态时期，即编辑期和编译期；程序执行起来后，处于动态/运行时期，即运行期。C#的机制：反射，即程序运行时，拿到对象/类型，可以立即知道其中的成员，然后根据需求来操作这些成员。例子参见TypeSample，代码如下所示：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      using System;
      using System.Collections.Generic;
      using System.Linq;
      using System.Reflection;
      using System.Text;
      using System.Threading.Tasks;
      using System.Windows.Forms;

      namespace TypeSample
      {
          class Program
          {
              static void Main(string[] args)
              {
                  Type myType = typeof(Form); // 查看Form类的类型

                  PropertyInfo[] pInfos = myType.GetProperties(); // 一个类型知道其成员, GetProperties能够在程序运行的过程中动态地探知类型的所有属性
                  MethodInfo[] mInfos = myType.GetMethods(); // GetMethods是得到该类型方法的函数
                  foreach (var m in mInfos)
                  {
                      Console.WriteLine(m.Name);
                  }
                  Console.WriteLine("----------------");
                  foreach (var p in pInfos)
                  {
                      Console.WriteLine(p.Name);
                  }
                  Console.WriteLine("----------------");
                  Console.WriteLine(myType.Name); // Form类的类型的名字就是Form
                  Console.WriteLine(myType.FullName); // Form类的类型的全名是System.Windows.Forms.Form
                  Console.WriteLine(myType.BaseType.FullName); // 一个类型知道其基类/父类
              }
          }
      }

      反射的用途：能够拿到某个属性，就能动态地访问到该属性的值；能够拿到某个方法，就能够动态地调用该方法。

    • 程序运行的时候，此类型的变量在分配在内存的什么位置（即变量应该被分配到栈中还是堆中）。静态的程序在硬盘中，动态的程序在内存中。运行程序就是静态到动态的切换，就是从硬盘中装载到内存中。内存中有两个区域，分别是stack栈和heap堆。

      • Stack简介：函数调用用到的是栈。栈较小，只有1-2M。

      • Stack overflow：栈较小且快。栈爆的两种情况：

        • 算法没写好，函数调用过多
        • 往栈上分配了太多的内存

      • stack overflow的例子1，对应stack overflow的第一种情况：

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        using System;
        using System.Collections.Generic;
        using System.Linq;
        using System.Text;
        using System.Threading.Tasks;

        namespace StackOverflow
        {
            class Program
            {
                static void Main(string[] args)
                {
                    BadGuy bg = new BadGuy();
                    bg.BadMethod();
                }
            }
            
            class BadGuy
            {
                public void BadMethod()
                {
                    int x = 100;

                    // 递归调用BadMethod
                    // 很快就会stack overflow，因为每次调用都需要在栈上切出一块内存存储变量x
                    this.BadMethod(); 
                }
            }
        }

        stack overflow的例子2，对应stack overflow的第二种情况：

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        using System;
        using System.Collections.Generic;
        using System.Linq;
        using System.Text;
        using System.Threading.Tasks;

        namespace StackOverflow
        {
            class Program
            {
                static void Main(string[] args)
                {
                    // stackalloc是往栈上切内存，切的过多就会stack overflow
                    // c#中不推荐使用指针，一定要用需要在函数前加unsafe
                    // 记得去project-StackOverflow properties-build中勾选allow unsafe code，并保存
                    unsafe
                    {
                        int* p = stackalloc int[9999999];
                    }
                }
            }
        }

      • Heap简介：堆用来存储对象/实例。堆较大，有几个G。

      • 使用Performance Monitor查看进程的堆内存使用量

      • 使用wpf application介绍堆。compile是编译，build是组装。一个程序从硬盘加载到内存中，开始执行后，就形成了一个进程（process）。在wpf application中，创建一个界面，上面有两个button，一个用于consume heap memory，一个用于release heap memory，对应的点击两个按钮后执行的逻辑为：

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        using System;
        using System.Collections.Generic;
        using System.Linq;
        using System.Text;
        using System.Threading.Tasks;
        using System.Windows;
        using System.Windows.Controls;
        using System.Windows.Data;
        using System.Windows.Documents;
        using System.Windows.Input;
        using System.Windows.Media;
        using System.Windows.Media.Imaging;
        using System.Windows.Navigation;
        using System.Windows.Shapes;

        namespace HeapSample
        {
            /// <summary>
            /// Interaction logic for MainWindow.xaml
            /// </summary>
            public partial class MainWindow : Window
            {
                public MainWindow()
                {
                    InitializeComponent();
                }

                List<Window> winList; // 本变量需要被两个函数使用，因此被声明在函数之外

                private void Button1_Click(object sender, RoutedEventArgs e)
                {
                    winList = new List<Window>();
                    // 往list中加入15000个Window，Window的实例占用的内存较多
                    for (int i = 0; i < 15000; i++)
                    {
                        Window w = new Window();
                        winList.Add(w);
                    }
                }

                private void Botton2_Click(object sender, RoutedEventArgs e)
                {
                    winList.Clear(); // 找合适的时机回收垃圾内存
                }
            }
        }

        build-build solution后，右击项目，选择open folder in file explorer，进入bin-debug，双击运行HeapSample.exe。win+r，键入perfmon，即performance monitor，打开了性能监视器，可用其监视系统和某个程序的性能。点击添加-process-private bytes，选择实例为HeapSample，即可开始监视HeapSample这个程序使用的堆内存。双击图例，选择图表，最大值从100改为1024，然后的点击两个按钮，即可开始实验。观察到，点击consume heap memory按钮，堆内存的占用拉高；点击release heap memory按钮，堆内存的占用先不变，后拉低（因为不是立即释放内存，而是在合适的时机释放内存，当内存占用不多时，先不会释放内存）。

        未来写程序时，观察程序是否占用过多内存，或者某个操作是否占用过多的内存，就可以用performance monitor。

      • 关于内存泄漏：对象被分配，但没有被回收，导致内存被浪费掉了。比较C++和C#

        • C++中，对象被分配但没被回收，会导致内存泄漏
        • C#中，有垃圾收集器的机制，不需要手动释放内存，会自动回收内存。C#中也不需要手动释放内存，相对安全，不易出现内存泄漏。

    • 此类型所允许的操作（运算），例子：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      using System;
      using System.Collections.Generic;
      using System.Linq;
      using System.Reflection;
      using System.Text;
      using System.Threading.Tasks;
      using System.Windows.Forms;

      namespace TypeSample
      {
          class Program
          {
              static void Main(string[] args)
              {
                  double result1 = 3.0 / 4.0; // 浮点除法
                  Console.WriteLine(result1);

                  double result2 = 3 / 4; // 整数除法
                  Console.WriteLine(result2); 
              }
          }
      }

7. 详解类型、变量与对象（下）

C#语言的类型系统

  • C#的五大数据类型

    • 类（Classes）：如Windows, Form, Console, String
    • 结构体（Structures）：如Int32, Int64, Single, Double
    • 枚举（Enumerations）：如HorizontalAlignment, Visibility
    • 接口（Interfaces）
    • 委托（Delegates）

  • C#类型的派生谱系

    树状的，带有层级结构的类型系统。根部是Object数据类型。C#的类型系统包括引用类型和值类型，引用类型包括类、接口和委托，值类型包括结构体和枚举，所有类型都以Object类型为基类型。三组关键字。第一组对应的是引用类型，蓝色的是数据类型的关键字，黑色的是用于定义引用类型的关键字，class用于定义类，interface用于定义接口，delegate用于定义委托。第二组对应的是值类型，蓝色的是数据类型，黑色的是用于定义值类型的关键字，struct用于定义结构体，enum用于定义枚举。第三组，最上面是bool类型的取值，中间的：void表示函数无返回值，null表示引用变量为空，最下面是用于声明变量的。

    蓝色的字表明：

    • 是现成的数据类型，非常常用，c#已经将其作为关键字
    • 是基本数据类型（又称内建数据类型），别的类型都是基于这些类型构成的，没有更基本的类型来构成它们

    csharpType.png

  • 实验

    • 实验1：证明Form是一个类

      1
      2
      3
      Type myType = typeof(Form); // 获取Form的类型
      Console.WriteLine(myType.FullName);
      Console.WriteLine(myType.IsClass);

      或者在Form上右击，选择go to definition，或者按下快捷键F12，就来到了微软定义Form的地方，可以看到定义Form时，有以下代码：

      1
      public class Form : ContainerControl

      因此Form的类型是class，其基类是ContainerControl。

    • 实验2：结构体类型：int, long等，都是结构体类型。在上面右击，选择go to definition，即可验证。

      1
      2
      public struct Int32 : IComparable, IFormattable, IConvertible, IComparable<int>, IEquatable<int>
      public struct Int64 : IComparable, IFormattable, IConvertible, IComparable<long>, IEquatable<long>

      int即相当于Int32，long即相当于Int64。

    • 实验3：枚举类型，用于限定用户从一个集合中选取有效值。显示窗口时，有三种状态：最大化、标准模式（可调整窗口大小）和最小化。现在来设置窗口的状态，有效值就三个，因此需要枚举类型。

      1
      2
      3
      Form f = new Form();
      f.WindowState = FormWindowState.Maximized; 
      f.ShowDialog(); // 此时显示最大化的窗口

      查看FormWindowState的源代码，用enum关键字声明的类型就是枚举类型：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      #region Assembly System.Windows.Forms.dll, v4.0.0.0
      // C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework\.NETFramework\v4.5\System.Windows.Forms.dll
      #endregion

      using System;
      using System.Runtime.InteropServices;

      namespace System.Windows.Forms
      {
          // Summary:
          //     Specifies how a form window is displayed.
          [ComVisible(true)]
          public enum FormWindowState
          {
              // Summary:
              //     A default sized window.
              Normal = 0,
              //
              // Summary:
              //     A minimized window.
              Minimized = 1,
              //
              // Summary:
              //     A maximized window.
              Maximized = 2,
          }
      }

    • 三个关键字：

      • class：用来声明类 类型
      • struct：用来声明结构体类型
      • enum：用来声明枚举类型

    • 接口和委托类型暂且不讲。

变量、对象与内存（核心内容）

  • 什么是变量

    变量 = 以变量名所对应的内存地址为起点、以其数据类型所要求的存储空间为长度的一块内存区域

    • 表面上来看（C#代码的上下文行文上来看），变量的用途是存储数据

    • 实际上，变量表示了存储位置，并且每个变量都有一个类型，以决定什么样的值能够存入变量

      • 变量表示了存储位置：变量名表示（对应着）变量的值在内存中的存储位置。例子：

        1
        2
        int x; // x是一个标签，其对应着内存中的地址，100就存在这个地址
        x = 100;

      • 每个变量都有一个类型，以决定什么样的值能够存入变量。同样用上面的例子解释：只有int类型的值可以保存到x指示的地址上去。

    • 变量一共有7种

      • 静态变量，实例变量（成员变量，字段），数组元素，值参数，引用参数，输出形参，局部变量

    • 狭义的变量指局部变量，因为其它种类的变量都有自己的约定名称

      • 简单地讲，局部变量就是方法体（函数体）里声明的变量

    • 7种变量的例子：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      using System;
      using System.Collections.Generic;
      using System.Linq;
      using System.Text;
      using System.Threading.Tasks;
      using System.Windows.Forms;

      namespace TypeInCSharp
      {
          class Program
          {
              static void Main(string[] args)
              {
                  int[] array = new int[100]; // 声明了长度为100的整型数组
                  // 取出数组中的元素: array[0], array[99]
                  // 这100个数组中的元素都是变量

                  int x; // 局部变量
              }
          }

          class Student
          {
              public static int Amount; // 静态成员变量

              // 实例变量/字段
              // 字段容易被赋为不合法的值，属性自带逻辑，可以保护字段不被赋不合法的值
              public int Age;
              public string Name;

              // 参数
              // double b是值参数变量, ref double a是引用参数变量, out double a是输出参数变量
              public double Add(ref double a, double b) 
              {
                  double result = a + b; // result是Add方法的局部变量
                  return result; 
              }
          }
      }

    • 变量的声明

      • 有效的修饰符组合opt+类型+变量名+初始化器opt

      • opt表示可选的，没有opt下角标则是必需的

      • 例子：

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        using System;
        using System.Collections.Generic;
        using System.Linq;
        using System.Text;
        using System.Threading.Tasks;
        using System.Windows.Forms;

        namespace TypeInCSharp
        {
            class Program
            {
                static void Main(string[] args)
                {
                    int a; // 声明变量
                    a = 100;
                    int b; // 声明变量
                    b = 200;
                    int c = a + b; // 声明变量
                    Console.WriteLine(c);
                }
            }

            class Student
            {
                // 有效的修饰符组合: public static
                // 类型: int
                // 变量名: Amount
                // 初始化器: = 0
                public static int Amount = 0;
            }
        }

  • 值类型的变量

    • 值类型没有实例，所谓的“实例”与变量合二为一。比如int a = 100，a既是变量，也是int类型的实例。

    • 基本知识：计算机内存的最小单位是bit，1个bit存储1个二进制数。8个bit组成一个字节（Byte），计算机内存中以字节为单元进行存取数据和读取数据，计算机为每个字节准备了一个唯一的编号，内存地址就是某个字节在计算机中的编号。寻找某个特定字节的过程：寻址。

      操作系统如何使用内存：

      • 部分内存保留给计算机操作系统，别的应用程序不能用
      • 其他内存为自由内存

    • 以byte/sbyte/short/ushort这四种结构体为例，演示值类型的变量在内存中如何存储。

      • byte: vs中输入byte，然后快捷键ctrl+shift+F1查看其文档，获取基本信息

      • 例子：

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        using System;
        using System.Collections.Generic;
        using System.Linq;
        using System.Text;
        using System.Threading.Tasks;
        using System.Windows.Forms;

        namespace TypeInCSharp
        {
            class Program
            {
                static void Main(string[] args)
                {
                    byte b;
                    b = 100; // 内存中存储为二进制，值为01100100

                    sbyte sb; // Signed 8-bit integer, range -128 to 127
                    sb = 100; // 内存中存储为二进制，值为01100100，最高位为符号位
                    // 负数 = 正数按位取反加1，故-100 = 10011100（注意进位）

                    ushort us; // Unsigned 16-bit integer, range 0 to 65,535
                    us = 1000; // 内存中存储为二进制，值为000000 + 1111101000, 注意高位存储在内存地址（字节编号）较大处

                    short s; // Signed 16-bit integer, range -32,768 to 32,767
                    s = 1000; // 值为000000 + 1111101000
                    s = -1000; // 按位取反加1, -1000存储为1111110000011000
                    string str = Convert.ToString(s, 2); // s转为二进制，然后打印为字符串
                    Console.WriteLine(str); // 验证-1000存储为1111110000011000
                }
            }
        }

  • 引用类型的变量与实例

    • 引用类型变量与实例的关系：引用类型变量里存储的数据是对象/实例的内存地址

    • 以类为例：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      using System;
      using System.Collections.Generic;
      using System.Linq;
      using System.Text;
      using System.Threading.Tasks;
      using System.Windows.Forms;

      namespace TypeInCSharp
      {
          class Program
          {
              static void Main(string[] args)
              {
                  Student stu; // 计算机看到引用类型，就分配4 Byte，将其中的所有bit都置为0，说明此时变量stu没有引用任何实例
                  stu = new Student(); // 在堆内存中创建一个Student实例，实例才是真正包含ID和Score这两个字段的实体
                  // 将实例在堆内存中的地址保存到stu变量中，即将内存编号以二进制的形式写入上面的4 Byte中

                  // 也可解释为什么可以用两个不同的引用变量来引用同一个实例
                  Student stu2;
                  stu2 = stu;
              }
          }

          class Student
          {
              uint ID; // 32 bit
              ushort Score; // 16 bit
          }
      }

  • 局部变量是在stack上分配内存

  • 变量的默认值。例子：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    using System.Windows.Forms;

    namespace TypeInCSharp
    {
        class Program
        {
            static void Main(string[] args)
            {
                Student stu = new Student();

                // ID和Score的默认值为0
                // 所有类型的变量，其默认值都是分配好的Byte的各个bit全部置为0
                // 但所有本地变量都需要有显示地赋初值
                Console.WriteLine(stu.ID); 
                Console.WriteLine(stu.Score);
            }
        }

        class Student
        {
            public uint ID; 
            public ushort Score; 
        }
    }

  • 常量（值不可改变的变量），例子：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    using System.Windows.Forms;

    namespace TypeInCSharp
    {
        class Program
        {
            static void Main(string[] args)
            {
                const int x = 100; // 常量const，常量不可被二次赋值，常量的初始化器不可省略或者换行
                Console.WriteLine(x);
            }
        }
    }

  • 装箱与拆箱（Boxing & Unboxing）

    在实际编程中少用，因为会导致性能的损失。有以下的例子和笔记：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    using System.Windows.Forms;

    namespace TypeInCSharp
    {
        class Program
        {
            static void Main(string[] args)
            {
                int x = 100;
                object obj = x; // 装箱
                // obj是引用类型，在内存中分配4 Byte的存储单元
                // 分开来写: object obj; // 4 Byte全部置零
                // obj = x;
                // 装箱：当obj要引用的值不是堆上的实例，而是栈上的值类型变量
                // 操作就是在堆上找一片空余的区域，将栈上的值拷贝过去
                // 再将堆上的地址存储到obj对应的内存空间中
                // 总之，obj变量对堆上的实例进行引用，实例中封装着x这个整数，这就是装箱

                // 拆箱: 拿到obj在堆上存储的整数值x
                int y = (int)obj;
                // 看到obj在堆上存储的值，将其转换为整数类型，然后存储在y对应的内存空间中
                Console.WriteLine(y);

                // 装箱和拆箱会损失性能，因为在栈和堆之间搬运了东西
                // 装箱：将栈上的值类型变量封装为object类型的实例，存储在堆上
                // 拆箱：将堆上object类型的实例里面的值，按照要求拆为目标数据类型，存储在栈上
            }
        }
    }

本节作业

  • 理解并熟记所有概念和知识
  • 对照视频编写示例程序，直至能够默写

8. 方法的定义、调用与调试（上）

方法的由来

方法的定义与调用（重要）

构造器（一种特殊的方法）

方法的重载（Overload）

如何对方法进行debug

方法的调用与栈*

9. 方法的定义、调用与调试（下）

发表于 更新于 分类于

Details Explanation of Java Stream

注意

wsl和本地上用IDEA运行java代码，最新修改的结果往往都无法被正常运行出来，我推测是缓存没有及时刷新之类的。有两个解决办法：

  • 每次运行前按下快捷键：ctrl + shift + f9，达到rebuild project的目的
  • 手动点击上边栏，选择build-rebuild project，选择build project没有作用

根据这个帖子，要彻底解决这个问题，恐怕要更新到2024.1以后的版本，我暂时不要更新自己的IDEA，因为当前的IDEA还能够正常使用，而我使用的是破解版的密钥，贸然更新可能会导致反而无法正常使用的情况出现。

不可变集合详解

创建不可变集合

不可变集合：不可以被修改的集合。其长度和内容都不可以被修改。

创建不可变集合的应用场景：

  • 如果某个数据不能被修改，把它防御性地拷贝到不可变集合中是个很好的实践。
  • 当集合对象被不可信的库调用时，不可变形式是安全的。
  • 某些确定的规则。
  • 电脑中的硬件信息。

简单理解：不想让别人修改集合中的内容，就可以给他提供一个不可变的集合。拿到不可变集合的人只能做查询操作，不能删除、修改、添加。

创建不可变集合的书写格式：
在List, Set, Map接口中，都存在静态的of方法，可以获取一个不可变的集合。
| 方法名称 | 说明 |
| :————————————————————: | :————————————————: |
| static <E> List<E> of(E...elements) | 创建一个具有指定元素的List集合对象 |
| static <E> Set<E> of(E...elements) | 创建一个具有指定元素的Set集合对象 |
| static <K, V> Map<K, V> of(E...elements) | 创建一个具有指定元素的Map集合对象 |

List of:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package com.cyf.a01immutable;

import java.util.Iterator;
import java.util.List;

public class ImmutableDemo1 {
    public static void main(String[] args) {
    /*
        创建不可变的List集合
        "张三", "李四", "王五", "赵六"
    */

        // ctrl + alt + v可以自动生成List<String> list，只需要自己写List.of即可
        // 一旦创建完毕之后，是无法进行修改的，在下面的代码中，只能进行查询操作
        List<String> list = List.of("张三", "李四", "王五", "赵六");

        // 查询
        System.out.println(list.get(0));
        System.out.println(list.get(1));
        System.out.println(list.get(2));
        System.out.println(list.get(3));

        System.out.println("-----------------------------");

        // 遍历
        for (String s : list) {
            System.out.println(s);
        }

        System.out.println("-----------------------------");

        // 迭代器遍历
        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String s = it.next();
            System.out.println(s);
        }

        System.out.println("-----------------------------");

        // 普通for循环
        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            System.out.println(s);
        }

        System.out.println("-----------------------------");

        // list.remove("李四");
        // list.add("aaa");
        // list.set(0, "aaa");
    }
}

Set of:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package com.cyf.a01immutable;

import java.util.Iterator;
import java.util.Set;

public class ImmutableDemo2 {
  public static void main(String[] args) {
    /*
        创建不可变的Set集合
        "张三", "李四", "王五", "赵六"
    */

    // ctrl + alt + v可以自动生成List<String> list，只需要自己写List.of即可
    // 一旦创建完毕之后，是无法进行修改的，在下面的代码中，只能进行查询操作
    // 细节：当我们要获取一个不可变的Set集合时，里面的参数一定要保证唯一性
    Set<String> set = Set.of("张三", "李四", "王五", "赵六");

    // set中没有索引，因此查询只能遍历
    for (String s : set) {
      System.out.println(s);
    }

    System.out.println("-----------------------------");

    Iterator<String> it = set.iterator();
    while(it.hasNext()) {
      String s = it.next();
      System.out.println(s);
    }

    System.out.println("-----------------------------");

    // 不能删除、添加、修改
    // set.remove("王五");
  }
}

Map.of:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package com.cyf.a01immutable;

import java.util.Map;
import java.util.Set;

public class ImmutableDemo3 {
  public static void main(String[] args) {
    /*
    创建Map的不可变集合
    细节1：键是不能重复的
    细节2：Map里面的of方法，参数是有上限的，最多只能传递20个参数，即10个键值对
    细节3：如果我们要传递多个键值对对象，数量大于10个，在Map接口中还有一个方法：Map.ofEntries()
    其将键和值看作一个整体，由于形参中可以有一个可变参数，因此可以实现传递多个键值对对象的功能
    */

    // 一旦创建完毕之后，是无法进行修改的，在下面的代码中，只能进行查询操作
    Map<String, String> map =
        Map.of(
            "张三", "南京", "李四", "北京", "王五", "上海", "赵六", "广州", "孙七", "深圳", "周八", "杭州", "吴九", "宁波",
            "郑十", "苏州", "刘一", "无锡", "陈二", "嘉兴");

    // map.keySet获取所有的键
    Set<String> keys = map.keySet();
    for (String key : keys) {
      String value = map.get(key);
      System.out.println(key + "=" + value);
    }

    System.out.println("-----------------------------");

    // map的第二种遍历方式
    // map.entrySet()获取所有键值对
    Set<Map.Entry<String, String>> entries = map.entrySet();
    for (Map.Entry<String, String> entry : entries) {
      String key = entry.getKey();
      String value = entry.getValue();
      System.out.println(key + "=" + value);
    }

    System.out.println("-----------------------------");
  }

  // 如果我想让这个方法能够接收多个键和值
  // 解决方案：
  // 键 可变参数
  // 值 可变参数
  // 键和值的类型不确定：泛型方法<>
  // 由于两个可变参数无法在形参中共存，因此无法设计这个方法
  //  public static<K, V> void of(K...keys, V...values) {
  //
  //  }

}

Map.ofEntries:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package com.cyf.a01immutable;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class ImmutableDemo4 {
  public static void main(String[] args) {
    /*
    创建Map的不可变集合，键值对的数量超过10个
    细节3：如果我们要传递多个键值对对象，数量大于10个，在Map接口中还有一个方法：Map.ofEntries()
    其将键和值看作一个整体，由于形参中可以有一个可变参数，因此可以实现传递多个键值对对象的功能
    */

    // 1. 创建一个普通的Map集合
    HashMap<String, String> hm = new HashMap<>();
    hm.put("张三", "南京");
    hm.put("李四", "北京");
    hm.put("王五", "上海");
    hm.put("赵六", "广州");
    hm.put("孙七", "深圳");
    hm.put("周八", "杭州");
    hm.put("吴九", "宁波");
    hm.put("郑十", "苏州");
    hm.put("刘一", "无锡");
    hm.put("陈二", "嘉兴");
    hm.put("aaa", "111");

    // 2. 利用上面的数据来获取一个不可变的集合
    // 获取所有的键值对对象（Entry对象）
    Set<Map.Entry<String, String>> entries = hm.entrySet();
    // 由于可变参数在底层就是一个数组，因此需要将上面的entries变成数组
    // 需要调用指定类型的toArray函数，类型是Map.Entry
    Map.Entry[] arr1 = new Map.Entry[0]; // 将map中的所有数据放到arr中
    // toArray方法在底层会比较集合的长度跟数组的长度两者的大小
    // 如果集合的长度11 > 数组的长度0：数据在数组中放不下，此时会根据实际数据的个数11，重新创建数组
    // 如果集合的长度<=数组的长度：数据在数组中放得下，此时不会创建新的数组，而是直接用
    // 因此数组的长度直接写成0就可以，不用想数组的长度是否和集合的长度匹配
    Map.Entry[] arr2 = entries.toArray(arr1);

    // 不可变的map集合
    Map map = Map.ofEntries(arr2);

    // 不可增删改，只可查
    // map.put("bbb", "222");
  }
}

上面的代码非常麻烦，可以简化。

Stream流

方法引用

初爽Stream流

Stream流的思想和获取Stream流

发表于 分类于

链接

理论基础

455.分发饼干

376. 摆动序列

53. 最大子序和

知识

理论基础

什么是贪心

贪心算法的本质是找到每个阶段的局部最优，从而去推导全局最优。

例如：

  • 10张面值不同的钞票，如何取能取到总数最多的钱？每次取面额最大的钞票即可，这就是局部最优。取10次后拿到最多的钱，就是全局最优。这是贪心的思路。
  • 背包最大承重是n。有一系列物品，其重量和价值各不相同，问这个背包能装的最大价值是多少？这需要用动态规划的思路来解决。

贪心的两个极端

贪心的题目要么太简短，要么太难。

贪心的套路

不像二叉树或者回溯算法的套路，贪心是没有套路的。部分较难的贪心题目，做过了才知道怎么做，否则完全想不到。非要说有套路，就是要想清楚每个阶段的局部最优，能否由局部最优推出全局最优。怎么由局部最优推出全局最优，也没有固定的思考方式。不需要做数学证明（数学证明的常用方法是数学归纳法和反证法），浪费时间。面试时，只要想到局部最优，可以推出全局最优，没有明显的反例，就已经可以试试，面试官不会要求严谨的数学证明。文字版讲解中有解决贪心算法的四个步骤，但实际做题时无法严格遵循四个步骤，实操性不强。

455.分发饼干

376.摆动序列

53.最大子序和

初次尝试

455.分发饼干

本题我的思路是，找出s数组的最大值，然后看g数组中有几个数小于等于s数组中的最大值，即为结果。我写了如下的代码，但只通过了23/25个测试样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        if (s.size() == 0) return 0;

        sort(s.begin(), s.end());
        int max = s[s.size() - 1];

        int res = 0;
        for (int i = 0; i < g.size(); i ++ )
            if (g[i] <= max)
                res ++ ;
        
        if (s.size() <= res) return s.size();
        return res;
    }
};

直接看代码随想录的讲解吧。

376.摆动序列

53.最大子序和

实现

455.分发饼干

例子：
胃g: 1, 2, 7, 10
饼s: 1, 3, 5, 9
输出：3

策略：尽量用大饼干去喂胃口大的孩子，这样就可以充分利用饼干。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 对两个数组进行排序
sort(g.begin(), g.end());
sort(s.begin(), s.end());

int res = 0;
int index = s.size() - 1; // 饼干的index

// 优先用大饼干喂胃口大的小孩，因此倒序遍历
for (int i = g.size() - 1; i >= 0; i -- ) {
    // 饼干成功投喂后，再向前遍历小孩数组，否则不能向前
    if (index >= 0 && s[index] >= g[i]) {
        res ++ ;
        index -- ;
    }
}

return res;

一定要外层循环遍历胃口，内层循环遍历饼干。如果外层循环遍历饼干，内层循环遍历胃口，拿上面的例子模拟就知道不可行。拿外层循环遍历饼干，内层循环遍历胃口，代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 对两个数组进行排序
sort(g.begin(), g.end());
sort(s.begin(), s.end());

int res = 0;
int index = g.size() - 1; 

for (int i = s.size() - 1; i >= 0; i -- ) {
    if (index >= 0 && s[i] >= g[index]) {
        res ++ ;
        index -- ;
    }
}

return res;

对于上面的例子，上述写法返回值为0。核心在于，要尝试去喂饱胃口大的孩子，而我们无法确保最大的饼干一定能喂饱胃口最大的孩子，如果最大的饼干无法喂饱胃口最大的孩子，那么上述写法的返回值恒为0。

另一种思路：尽量用小饼干去满足胃口小的孩子，这样可以充分利用小饼干。

376.摆动序列

53.最大子序和

心得与备忘录

455.分发饼干

  1. 一定要外层循环遍历胃口，内层循环遍历饼干。
  2. 内存循环用if判断而不用while循环，因为要一个小孩一个小孩地喂过去。
  3. 两种思路：先去满足大胃口的孩子，先去使用小饼干。两种思路遍历的顺序不同。

376.摆动序列

53.最大子序和

发表于 分类于

简介

都柏林，素有美食荒漠、欧洲宁古塔之称。然而，经过本人和好友长期约饭探店的实地考察之后，发现都柏林的中餐馆门类齐全、品种多样，除去价格稍贵外相比于国内并无显著的短板和缺憾。因此，本人维护本帖用于记录都柏林吃喝之旅，并为读者提供一份尽可能详细的都柏林美食推荐清单。

本人向来赞同孔夫子“食不厌精，脍不厌细”的名言，因此，性价比是这份排行榜中相对次要的因素，食物的调味、口感、精细和新颖程度是更重要的。本帖中的五星代表着这个饭店的食物有独道之处，甚至超过了国内同种食物之最。四星代表着这个饭店的食物在味道或性价比方面至少有一个非常出众，而另一个也至少在平均水平之上。三星代表着值得一试，但并不惊艳。果腹则代表着仅供日常果腹之用，胜在量大管饱。心愿清单则是我早有耳闻，但还未成行的餐馆。本帖中推荐的餐馆会附带有谷歌地图的位置信息和一句简短的点评。本帖中也会提到一些国内的餐馆，主要分布在南昌、西安和合肥，都是本人曾经久居过的城市。本帖中评分点评随性，主观色彩浓重，愿博看官一笑。

五星

  1. 四川
  2. 川九香

四星

三星

果腹

国内

心愿清单

  1. 日料Omakase
  2. 西餐Shanahan’s on the Green

发表于 分类于

菜谱

下面是我目前已经掌握的菜肴做法。

青椒炒牛肉

https://www.xiaohongshu.com/explore/64084cf10000000014024bf6?xsec_token=ABjk8kDPjbnjQBy5ninATf_t4OFqDsNTj2tvDoDR8YAew=&xsec_source=pc_user

素炒小青菜

https://www.xiaohongshu.com/explore/649eb823000000001203d1d0?xsec_token=ABhF-yZeYWU_KFyde9iuIRaP4osN7hN84uBTDHM4muOJY=&xsec_source=pc_user

酸汤水饺

https://www.xiaohongshu.com/explore/640626770000000013030f32?xsec_token=ABKMjy9V_2e41wBdiSonEoj8xIax3g9thkyzM_zYygvEo=&xsec_source=pc_user

烤鸡腿

https://www.xiaohongshu.com/explore/61d80f75000000000102f662?xsec_token=ABFeZ243mB41AtUkgopJjbtnfNUjXvXk5X0vREX-Cr9-o=&xsec_source=pc_user

清汤面

https://www.xiaohongshu.com/explore/64ef0d47000000001e031fc3?xsec_token=ABhdjuqwDUBOmK31gzU44aiEzUHgQx9krLx1OMg7WbYlQ=&xsec_source=pc_user

辣椒炒鸡丁

https://www.xiaohongshu.com/explore/642ef0440000000013003052?xsec_token=ABP-oNHr9xdj_dfJ3PFdEz90JgCfpOKhxwZCwXod7BaKM=&xsec_source=pc_user

耗油生菜

https://www.xiaohongshu.com/explore/6331a4890000000017019ee3?xsec_token=ABvHsXQ8990EWiCV0UivQ0VJJbi921rouqm8fD0HcXocg=&xsec_source=pc_user

蛋炒饭

https://www.xiaohongshu.com/explore/6539c724000000001f036536?xsec_token=AByuVdQE_Yu5WBwBdOxBbp1JqGxwtjXagF-Ct3aIRyTB4=&xsec_source=pc_user

炒米粉

https://www.xiaohongshu.com/explore/63d11d5e000000002203b147?xsec_token=AB6hQFjxlcFe1hFOtuDSpjFvIpDPYH0fIElCl-xqe0uk8=&xsec_source=pc_search

排骨汤

https://www.xiaohongshu.com/explore/63b295f3000000001c0349e2?xsec_token=ABx6mW_uBfj9nVHk20uySHX_8uZaNhS6D0mnuGF2iL0IY=&xsec_source=pc_search

https://www.xiaohongshu.com/explore/654d46ab000000003103d1b1?xsec_token=ABC1d6ftIfXeIjYWoQ6zTAFYDNRBJPT1MTjZYuH7pO92o=&xsec_source=pc_search

发表于 更新于 分类于

链接

332.重新安排行程
51. N皇后
37. 解数独
总结

知识

51. N皇后

初始化一个vector<string>，其中的元素全是字符.（共有n行，每行是一个字符串，每个字符串由n个.构成）：

1
vector<string> chessboard(n, string(n, '.'));

实现

今天这三道题都非常难，那么这么难的题，为啥一天做三道？

因为一刷也不求能把这么难的问题解决，所以一刷的时候，就了解一下题目的要求，了解一下解题思路，不求能直接写出代码，先大概熟悉一下这些题，二刷的时候，随着对回溯算法的深入理解，再去解决如下三题。

332.重新安排行程

本题的思路不难，但选择的数据结构和初始化、遍历等操作非常复杂，是一道难题。

本题需要一个特殊的数据结构来存储一个机场映射多个机场，机场之间要靠字母序排列的这种复杂关系，选择的数据结构是unordered_map<string, map<string, int>> targets。其具体的含义为unordered_map<出发机场, map<到达机场, 航班次数>> targets。在遍历 unordered_map<出发机场, map<到达机场, 航班次数>> targets的过程中，可以使用”航班次数”这个字段的数字做相应的增减，来标记到达机场是否使用过了。如果“航班次数”大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。有如下代码：

1
2
3
4
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
// 使用map的原因是为了让其key有序（字典序）
// 第一个unordered_map是为了存储出发机场和到达机场间的映射关系，第二个map是为了对到达机场按照字典序排序，且记录到达机场在输入数据中出现的次数
unordered_map<string, map<string, int>> targets;

本题的树形结构如下所示，以输入：[["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]为例：
332.重新安排行程1

对上述树形结构的解释：始终从JFK出发，输入中JFK可以到KUL或者NRT，因此可以有这两个选择。输入中没有以KUL作为出发点的航班，因此飞向KUL的那一枝结束。飞向NRT的一枝，输入中以NRT为出发点的航班的终点是JFK，因此有行程：JFK->NRT->JFK。输入中以JFK为出发点的航班的终点可以是KUL或者NRT，因此分为两枝。JKF已经飞过NRT，因此剪枝；JKF飞KUL构成了行程：JFK->NRT->JFK->KUL，三趟航班，形成中有四个机场，说明找到了结果。

通过上述分析，我们可以得出代码的终止条件：n张机票，即有n个航班，则行程中有n + 1个机场（机场可重复）时，收集结果。原因是行程是由若干个向量组成的，每个向量都是一个航班，行程是单向的，不会形成环。因此，若有n个向量（即n个航班），那么就会有n + 1个节点（即单个向量的首尾），即n + 1个机场。有如下代码：

1
2
3
4
5
6
vector<string> res; // 存放结果，即由n个航班拼接成的行程，其中有n + 1个机场

// ticketNum为票数，即航班数
if (result.size() == ticketNum + 1) {
    return true;
}

在写单层递归逻辑前，需要先对res数组和targets数组进行初始化，代码如下所示：

1
2
3
4
for (const vector<string>& vec : tickets) {
    targets[vec[0]][vec[1]]++; // 记录映射关系
}
result.push_back("JFK"); // 起始机场

tickets数组是输入，其类型是vector<vector<string>>。由于输入不可更改，且其中的每个元素的类型都是vector<string>，因此用类型为const vector<string>的变量对其进行遍历，这里的引用就不加都可以，不会影响运行结果。vec[0]为出发机场，vec[1]为到达机场。targets中存储的是出发机场与到达机场的映射关系。对一个出发机场，若输入中存在其的到达机场，则在targets中记录这个映射关系，且map<string, int>中的string存储到达机场（vec[1]），int存储次数（有出发机场和其对应的到达机场，则该int存1）。这实现了对每一个航线（从某个出发机场到某个目的地机场）的航班次数进行计数。

根据树形结构，可以写出单层递归的逻辑：

1
2
3
4
5
6
7
8
9
for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
    if (target.second > 0 ) { // 记录到达机场是否飞过了
        result.push_back(target.first);
        target.second--;
        if (backtracking(ticketNum, result)) return true;
        result.pop_back();
        target.second++;
    }
}

这里特别需要注意的是：

1
for (pair<const string, int>& target : targets[result[result.size() - 1]])

其含义为：result[result.size() - 1] 获取 result 向量的最后一个元素，即当前路径中最新的机场。然后，使用这个机场名称作为键，从 targets 映射中检索对应的内层 map，这个内层 map 包含所有从该机场出发的航班及其次数。for 循环遍历这个内层 map，即遍历从当前结果集中的最新机场可以直接到达的所有机场及对应的航班次数。一定要加上引用即 & target，因为后面有对 target.second 做减减操作，如果没有引用，单纯复制，这个结果就没记录下来，那最后的结果就不对了。加上引用之后，就必须在string前面加上const，因为map中的key是不可修改了，这就是语法规定了。

还需要注意本题的递归函数的返回值和参数：

1
bool backtracking(int ticketNum, vector<string>& result)

注意函数返回值用的是bool！因为我们只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线。所以找到了这个叶子节点了直接返回。

拆分地写好了各部分的代码之后，整合起来就是本题的完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    unordered_map<string, map<string, int>> targets;

    bool backtracking(int ticketSum, vector<string>& res)
    {
        // 终止条件
        if (ticketSum + 1 == res.size()) return true;

        // 单层递归逻辑
        // 以res中最新机场为出发点，遍历targets寻找可能的目的地
        for (pair<const string, int>& target: targets[res[res.size() - 1]])
        {
            // target.second > 0说明目的地可用
            if (target.second > 0) 
            {
                // 处理节点
                res.push_back(target.first);
                target.second -- ;
                // 递归
                if (backtracking(ticketSum, res)) return true;
                // 回溯
                res.pop_back();
                target.second ++ ;
            }
        }
        return false;
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        // 初始化res
        vector<string> res;
        res.push_back("JFK"); 

        // 初始化targets
        for (auto vec: tickets)
            targets[vec[0]][vec[1]] ++ ;

        // 调用递归函数并返回结果
        backtracking(tickets.size(), res);
        return res;
    }
};

使用auto来简化上述代码，避免需要手写复杂的变量类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    // 提取输入数据中的信息：构造出发机场和到达机场间的映射，到达机场按照字典序排序并记录到达机场出现的次数
    unordered_map<string, map<string, int>> targets;

    bool backtracking(int ticketSum, vector<string>& res)
    {
        // 终止条件
        if (ticketSum + 1 == res.size()) return true;

        // 单层递归逻辑
        for (auto& target: targets[res[res.size() - 1]])
        {
            if (target.second > 0)
            {
                target.second -- ;
                res.push_back(target.first);
                if (backtracking(ticketSum, res)) return true;
                target.second ++ ;
                res.pop_back();
            }
        }
        return false;
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        // 初始化res
        vector<string> res;
        res.push_back("JFK");
        // 初始化targets
        for (auto ticket: tickets) targets[ticket[0]][ticket[1]] ++ ;
        backtracking(tickets.size(), res);
        return res;
    }
};

51. N皇后

本题是回溯中较难的题目。题意：给一个n*n的棋盘，在其中放n个皇后，要求同一行、同一列、同意斜线上不能有两个皇后，将放置皇后的结果返回。难点：之前讲的组合问题、分割问题、子集问题和排列问题，都是一个一维的集合按照条件输出若个子集，本题则是一个二维的集合（数组）。

首先想如何暴力枚举，以4*4的棋盘为例，需要4个for循环，每一行每个位置尝试放皇后，根据规则判断能否放皇后。回溯算法的本质和暴力枚举没有区别，但回溯算法用递归的方式控制嵌套for循环的层数。

本题的树形结构如下所示，以3*3的棋盘为例：
51.N皇后

第n层递归对应着尝试在第n行中放置皇后。3*3的N皇后问题是无解的，画其只是为了展现其树形结构。树的深度为棋盘的行数，树的宽度为棋盘的列数。接下来写本题的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 每个棋盘是一个二维数组，放置若干棋盘，因此需要三维数组
vector<vector<vector<int>>> res; // 三维数组收集所有可能的摆放结果

// chessboard为棋盘，n为棋盘的大小, row为行，第n层递归负责处理第n行，用row来记录当前处理到了第几行
void backtracking(vector<vector<int>> chessboard, int n, int row)
{
    // 终止条件: 叶子节点收获结果
    if (row == n) 
    {
        res.push_back(chessboard); // 单层递归逻辑中会对合法性进行判断，保证放入res中的chessboard都是合法的
        return;
    }
    
    // 单层递归逻辑
    for (int i = 0; i < n; i ++ )
    {
        // 合法性判断
        // 判断在第row行，第i个位置放皇后是否合法
        if (isValid(row, i, chessboard, n))
        {
            // 放皇后
            chessboard[row][i] = 'Q'; 
            // 递归
            backtracking(chessboard, n, row + 1); // 下一层递归, row->row + 1
            // 回溯
            chessboard[row][i] = '.';
        }
    }
}

总结：回溯法解决二维数组问题，第n层递归处理第n行，每层递归中遍历每一行中的每个元素。

在理解了本题的主题思路后，独立写出代码依然有难度，因为本题返回的变量类型是vector<vector<string>，chessboard的变量类型应该为vector<string>，对其进行初始化有一定难度。另外，isValid函数的实现我第一次写也有一定的困难，直接看文字版讲解。

我独立写出的本题的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    // 结果集
    vector<vector<string>> res;

    bool isValid(vector<string>& chessboard, int n, int row, int col)
    {
        // 同一列中不能有两个皇后
        for (int i = 0; i < row; i ++ )
            if (chessboard[i][col] == 'Q') return false;

        // 主对角线不能有两个皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i -- , j -- )
            if (chessboard[i][j] == 'Q') return false;

        // 副对角线不能有两个皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i -- , j ++ )
            if (chessboard[i][j] == 'Q') return false;

        return true;
    }

    // 传入棋盘，棋盘大小，行数（即递归层数）
    void backtracking(vector<string>& chessboard, int n, int row)
    {
        // 终止条件
        if (row == n) 
        {
            res.push_back(chessboard);
            return;
        }

        // 单层递归逻辑
        for (int i = 0; i < n; i ++ )
        {
            // 合法性判断
            if (isValid(chessboard, n, row, i))
            {
                // 放皇后
                chessboard[row][i] = 'Q';
                // 递归
                backtracking(chessboard, n, row + 1);
                // 回溯
                chessboard[row][i] = '.';
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<string> chessboard(n, string(n, '.'));
        backtracking(chessboard, n, 0);
        return res;
    }
};

需要特别注意的是，在放皇后时，每次只在一行中的某个位置放一个皇后，且放完后会回溯，因此同一行中不会出现两个皇后，因此不需要在isValid函数中对同一行中出现两个皇后的情况进行判断。另外，放皇后的顺序是从行数小放到行数大，从列数小放到列数大。在不同行中，行数小的位置会被优先尝试放置皇后。在同一行的不同列中，列数小的位置会被优先尝试放置皇后。因此，isValid函数中对同一列判断，只需要判断从0-row列；对主对角线判断，只需要判断i从row-1到0，j从col-1到0；对副对角线判断，只需要判断i从row - 1到0，j从col + 1到n（由于优先放小的行，所以i < row, j > col的位置可能已经放置了皇后）。

37. 解数独

给一个99的棋盘，用1-9填满这个棋盘，规则为：同一行中不能有重复的数字，同一列中不能有重复的数字，九宫格中不能有重复的数字。本题求出一个填满的方案即可。本题是回溯章节的难题，和上一题N皇后类似。但用N皇后的思路做本题做不出来。*本题比N皇后多一个维度。N皇后用for循环遍历行，递归遍历列。本题不仅行要放满数字，列也要放满数字，整个棋盘都要放满数字。

本题解法被称为二维递归，即两个for循环，下面是一个递归函数。一个for循环来遍历行，一个for循环来遍历列，这样才能确定一个空格。递归用来确定空格中应该放的数字。本题的树形结构如下所示：
37.解数独

现在开始写本题的代码，本题的代码其实并不复杂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 确定递归函数的返回值和参数
// 返回值为bool类型，原因是本题求数独的一个解即可，一旦棋盘被填满，立即返回
// 若一题有多个结果，多个结果散落在树形结构里，需要将树形结构全都搜索一遍，然后将结果放入结果集中，因此返回值为void类型
bool backtracking(vector<vector<char>>& board) // board要引用，这样才会修改board
{
    // 本题不需要写终止条件，棋盘被填满后会直接return true，若无法满足填充规则，则会return false
    // 两个for循环，一个遍历行，另一个遍历列
    for (int i = 0; i < board.size(); i ++ )
        for (int j = 0; j < board[0].size(); j ++ )
        {
            // 处理节点
            // 棋盘中的点表示空格
            if (board[i][j] == '.')
            {
                for (char k = '1'; k <= '9'; k ++ )
                {
                    // 检查在board的(i, j)处放置数字k是否合法
                    if (isValid(i, j, k, board)) 
                    {
                        board[i][j] = k;
            					 // 进入下一层递归
                        bool res = backtracking(board);
                        // 找到一个结果就立即停止搜索，返回
                        if (res == true) return true;
                        // 回溯
                        board[i][j] = '.';
                    }
                }
                return false; // 在空格处将9个数字都尝试了，无法填入，则说明该棋盘没有结果，返回false
            }
        }
    // 若没有走到return false，则return true（若棋盘一直被填充直到被填满，则不会走if (board[i][j] == '.')）
    return true; 
}

根据上面的核心代码，我自己实现了isValid函数，写出了本题的完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    bool isValid(int i, int j, char k, vector<vector<char>>& board)
    {
        // 检查第i行能否放入k
        for (int j = 0; j < board[0].size(); j ++ )
            if (board[i][j] == k)
                return false;

        // 检查第j列能否放入k
        for (int i = 0; i < board.size(); i ++ )
            if (board[i][j] == k)
                return false;
        
        // 检查九宫格能否放入k
        int starti = i / 3 * 3;
        int startj = j / 3 * 3;
        int endi = starti + 2;
        int endj = startj + 2;
        for (int i = starti; i <= endi; i ++ )
            for (int j = startj; j <= endj; j ++ )
                if (board[i][j] == k)
                    return false;

        return true;
    }

    bool backtracking(vector<vector<char>>& board)
    {
        for (int i = 0; i < board.size(); i ++ )
            for (int j = 0; j < board[0].size(); j ++ )
            {
                if (board[i][j] == '.')
                {
                    // 处理节点
                    for (char k = '1'; k <= '9'; k ++ )
                    {
                        if (isValid(i, j, k, board))
                        {
                            board[i][j] = k;
                            // 递归
                            bool res = backtracking(board);
                            if (res == true) return true;
                            // 回溯
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

心得与备忘录

332.重新安排行程

  1. 本题的解题思路其实不难，画出树形结构后，是一道经典的回溯问题。本题的难点在于选用怎样的数据结构来有效地存放和处理输入的数据。
  2. 因为本题是hard题，且由于使用了较为复杂的数据结构，因此我觉得在hard中都算是难题，显著比N皇后困难。因此，第一遍学习本题，了解本题的思路和核心代码即可，不要求能够将本题完整地写出来。

  3. 本题的实现部分对代码进行了细致的拆分讲解，大致可以分为以下几个要点：

    • 用怎样的数据结构存储输入数据中出发机场和到达机场间的映射关系，且要求同一个出发机场的到达机场按照字典序排列，同时记录到达机场的使用次数
    • 如何对结果集和上面的数据结构进行初始化
    • 根据树形结构写出终止条件和单层搜索逻辑，并确定递归函数的返回值和传入的参数。本题递归函数的返回值是罕见的bool类型，而非void类型

    明确上述三个问题，即可理解本题的思路和实现细节，进而顺畅地写出本题的代码。

  4. 在初始化targets时，范围遍历可以直接采用auto类型的变量，避免需要手写复杂的变量类型。但在单层递归逻辑中遍历targets时，不能直接采用auto，因为for循环中涉及到了对遍历的值的修改操作，因此一定要使用引用，可以使用auto&。

51. N皇后

  1. 本题的新奇之处在于：之前用回溯法解决过组合、切割、子集、排列问题，处理的对象都是一维数组，N皇后问题处理的对象却是二维数组。

  2. 本题的原理实际上非常简单，理解本题的树形结构即可：

    51.N皇后

  3. 由上述树形结构可知，树的宽度是棋盘的列数，树的深度是棋盘的行数。据此，可以轻松地写出backtracking函数的终止条件和单层递归逻辑。

  4. 对棋盘合法性的判断其实是比较容易写错的。按照以下标准验证棋盘是否合法，两皇后：

    • 不能同行

    • 不能同列

    • 不能同斜线 （主对角线和副对角线）

    在isValid函数中，不能同行的判断不需要写。因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，且后序还会回溯释放掉这个元素。因此只需要写不能同列、不能同主对角线、不能同副对角线的判断。这三个判断的书写依据如下图所示。

    n_queen_revised_2.png

    当我们尝试在(row, col)处放置皇后时，只有绿色部分可能在之前被放置过皇后。原因是：递归到当前层，只有行数<row的格点上可能被放置过皇后。根据三条黄线，可以方便地写出三个判断。

  5. 本题的时间复杂度O(n!)，空间复杂度O(n)。

    • 时间复杂度：由于回溯法的本质依然是暴搜，因此，在棋盘的第一行，有n种放置皇后的方式；第二行最多有n - 1种，依次类推，得到时间复杂度为O(n!)。
    • 空间复杂度即为树的深度，即为棋盘的行数，故空间复杂度为O(n)。

37. 解数独

  1. 和之前的递归题目不同，本题的递归是二维递归。一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性。
  2. 本题递归函数的函数返回值类型为bool类型。原因是本题只需要找到一个解，就立即返回。如果需要搜索整棵二叉树，找到所有的解，然后将结果记录在结果集中，那么递归函数的返回值类型为void。
  3. 本题不需要写终止条件。因为在递归逻辑中，如果找到了满足条件的解，就会直接return true。如果某个空格中无论填入哪个数字都无法满足条件，就会直接return false。
  4. 注意return true和return false的位置。前者放在递归函数末尾，意思是若棋盘一直被填充直到被填满，则不会走if (board[i][j] == '.')，就return true。后者放在for (char k = '1'; k <= '9'; k ++ )的结束之处，意思是在空格处将9个数字都尝试了，无法填入，则说明该棋盘没有结果，return false。
  5. 时间复杂度：O(9^m) , m是’.’的数目。空间复杂度：$O(n^2)$，原因是递归的深度是n^2（原因是第一层for循环代表树的宽度，后面两层for循环代表了树的深度。由于本题中数独的长宽固定为9，因此本题中的n = 9）。
  6. 回溯的题目到此结束，总体来说比较简单，有统一的模板，但每个题目又有一些需要注意的小细节。

发表于 更新于 分类于

链接

491.递增子序列
46.全排列
47.全排列 II

知识

491.递增子序列

46.全排列

47.全排列 II

初次尝试

491.递增子序列

本题的关键：递增、至少两个元素、去重。但本题存在一个很大的问题，就是去重的时候不能对原数组进行排序，否则会打乱原数组的顺序，以以下测试样例为例：

1
2
Input: nums = [4,4,3,2,1]
Output: [[4,4]]

一旦顺序被打乱，实际输出和理论输出就会不同，会多出很多递增的子序列。

本题和90.子集II非常像，但又很不一样，很容易掉坑里。直接看卡尔的讲解吧。

46.全排列

本题是排列问题，不需要startIndex，但我写不出代码，直接看卡尔的讲解。经过卡尔的提示用used数组避免重复取元素后，我独立写出了以下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;

    void backtracking(vector<int>& nums, vector<int>& used)
    {
        // 终止条件
        if (path.size() == nums.size())
        {
            res.push_back(path);
            return;
        }

        // 单层递归逻辑
        for (int i = 0; i < nums.size(); i ++ )
        {
            if (used[i] == 1) continue;
            // 处理节点
            path.push_back(nums[i]);
            used[i] = 1;
            // 递归
            backtracking(nums, used);
            // 回溯
            path.pop_back();
            used[i] = 0;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> used(nums.size(), 0);
        backtracking(nums, used);
        return res;
    }
};

47.全排列 II

本题中的数组中会有重复元素，因此本题需要去重逻辑。本题相当于40.组合总和II去重逻辑和46.全排列的结合。我先尝试用set去重。我独立写出了以下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;

    void backtracking(vector<int>& nums, vector<int>& used)
    {
        // 终止条件
        if (path.size() == nums.size())
        {
            res.push_back(path);
            return;
        }

        unordered_set<int> uset;
        for (int i = 0; i < nums.size(); i ++ )
        {
            if (uset.find(nums[i]) != uset.end() || used[i] == 1) continue;
            // 处理节点
            uset.insert(nums[i]);
            used[i] = 1;
            path.push_back(nums[i]);
            // 递归
            backtracking(nums, used);
            // 回溯
            used[i] = 0;
            path.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> used(nums.size(), 0);
        backtracking(nums, used);
        return res;
    }
};

再接着尝试写出used数组去重的代码。我独立写出了如下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;

    void backtracking(vector<int>& nums, vector<int>& used)
    {
        // 终止条件
        if (path.size() == nums.size())
        {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i ++ )
        {
            if (used[i] == 1 || i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue;
            // 处理节点
            used[i] = 1;
            path.push_back(nums[i]);
            // 递归
            backtracking(nums, used);
            // 回溯
            used[i] = 0;
            path.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> used(nums.size(), 0);
        sort(nums.begin(), nums.end());
        backtracking(nums, used);
        return res;
    }
};

由于本题中nums[i]的数据范围在-10-10之间，所以可以不用set去重，而是用数组去重（将数据范围-10-10映射到数组下标范围0-20），这样效率更高，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;

    void backtracking(vector<int>& nums, vector<int>& used)
    {
        // 终止条件
        if (path.size() == nums.size())
        {
            res.push_back(path);
            return;
        }

        // 数组去重
        int hash[21] = {0};

        for (int i = 0; i < nums.size(); i ++ )
        {
            if (used[i] == 1 || hash[nums[i] + 10]) continue;
            // 处理节点
            hash[nums[i] + 10] = 1;
            used[i] = 1;
            path.push_back(nums[i]);
            // 递归
            backtracking(nums, used);
            // 回溯
            used[i] = 0;
            path.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> used(nums.size(), 0);
        backtracking(nums, used);
        return res;
    }
};

实现

491.递增子序列

列出递增子序列，子序列元素数量大于等于2。有以下测试样例：

1
2
Input: [4, 7, 6, 7]
Output: [4, 7, 7], [4, 7], [4, 6], [4, 6, 7], [6, 7], [7, 7]

要求不能有重复的子序列，因此需要去重。本题和90.子集II，只不过要求元素有顺序，且元素个数大于等于2。实际上，本题的细节和90有很大区别。本题的去重思路不可以沿用先排序再去重的做法，因为会改变原数组中元素的顺序，导致递增子序列的改变。例如对上述测试样例排序后，递增子序列会包括[4, 6, 7, 7]，实际上原本的输出不包含[4, 6, 7, 7]。

所有的回溯算法都是深搜，所有的深搜都可以说是递归。画本题的树形结构：
491. 递增子序列1

去重为树层去重。现在开始写代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<int> path; // 单个结果
vector<vector<int>> res; // 结果集

void backtracking(vector<int>& nums, int startIndex)
{
    // 子集类问题可以不写终止条件，具体原因参见78/90
    if (path.size() >= 2) res.push_back(path); // 子集中元素数量大于等于2
    
    unordered_set<int> uset; // set去重
    
    // 单层递归逻辑
    for (int i = startIndex; i < nums.size(); i ++ )
    {
        // 剪枝条件1：所取元素小于子序列最后一个元素，此时要求子序列非空，否则path.back()会报错
        // 剪枝条件2：用set做树层去重
        if (!path.empty() && nums[i] < path.back() || uset.find(nums[i]) != uset.end()) continue;
        
        // 处理节点
        // 记录每一层取的数(for循环中除去递归部分外都是横向遍历的)，每一层不能重复取相同的数
        uset.insert(nums[i]); 
        path.push_back(nums[i]);
        // 递归
        backtracking(nums, i + 1);
        // 回溯
        path.pop_back();
    }
}

为什么没有对uset做回溯操作？
原因：上述代码中，每进入一层递归，都会重新定义一个uset。因此uset就是确保同一层中没有取到相同的元素，在进入下一层递归时，uset会被刷新。因此uset并不会对树枝去重，只会对树层去重。而used数组需要做回溯，因为used数组记录的是元素是否在path中被使用过，因此path中加减元素都需要对used数组进行修改。

本题的去重方式也可以应用于40.组合总和II和90.子集II。本题也可以用数组取代set进行去重，用数组的效率会更高些。

本题的完整代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;

    void backtracking(vector<int>& nums, int startIndex)
    {
        // 收集结果
        if (path.size() >= 2) res.push_back(path);
        unordered_set<int> uset;

        // 单层递归逻辑
        for (int i = startIndex; i < nums.size(); i ++ )
        {
            // 剪枝条件1：所取元素小于子序列最后一个元素，此时要求子序列非空，否则path.back()会报错
            // 剪枝条件2：用set做树层去重
            // cpp中&&的优先级高于||，因此是先与后或，不需要给剪枝条件1加括号
            if (!path.empty() && nums[i] < path.back() || uset.find(nums[i]) != uset.end()) continue;
            // 处理节点
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            // 递归
            backtracking(nums, i + 1);
            // 回溯
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums, 0);
        return res;
    }
};

由于本题nums[i]的数据范围很小，因此可以用数组做去重，运行效率也更高。只需要将set替换为普通数组，然后做一个偏移（数值-100-100映射到数组下标0-200上）即可。代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;

    void backtracking(vector<int>& nums, int startIndex)
    {
        if (path.size() > 1) res.push_back(path);
        int cnt[201] = {0};

        for (int i = startIndex; i < nums.size(); i ++ )
        {
            if (!path.empty() && nums[i] < path.back() || cnt[nums[i] + 100] == 1) continue;
            cnt[nums[i] + 100] = 1;
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums, 0);
        return res;
    }
};

46.全排列

题目中明确说了给定的集合中没有重复元素，因此不用去重。

排列相对于组合的区别：[2, 1], [1, 2]是同一个组合，但是两个排列。排列是强调元素顺序的，组合不强调元素顺序。接下来画本题的树形结构。

46.全排列

排列问题中也需要用到used数组，用于标记哪些元素被使用过，因为在排列问题中同一个元素不能重复使用。组合问题中是用startIndex来避免取同一个元素和避免产生相同组合的情况。树的深度由nums的长度来控制。

used数组用来标记哪些元素被取过，取过的元素不能重复取，但所有没取过的元素都可以重复取，而不需要像组合问题那样用startIndex来控制只能取当前元素的下一个元素。具体的代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<int> path; // 放单个结果
vector<vector<int>> res; // 结果集

void backtracking(vector<int>& nums, vector<int>& used)
{
    // 终止条件
    if (path.size() == nums.size())
    {
        res.push_back(path); // 收获结果
        return;
    }
    
    // 单层递归逻辑
    // 排列问题不需要startIndex，只要不重复取同一个元素即可
    for (int i = 0; i < nums.size(); i ++ )
    {
        if (used[i] == 1) continue; // 不重复取同一个元素
        // 处理节点
        used[i] = 1;
        path.push_back(nums[i]);
        // 递归
        backtracking(nums, used);
        // 回溯
        used[i] = 0;
        path.pop_back();
    }
}

47.全排列 II

上一题给定的集合中没有重复元素，本题给定的集合中有重复元素。以[1, 1, 2]为例，如果依然用上一题的办法求解本题，结果集中会出现两个[1, 1, 2]，因此本题需要做去重。如果对去重的思路不够了解，可以看40.组合总和II。回溯的所有题目中，去重的逻辑都是相同的。本题等于排列+去重。但排列问题中的去重会有些与之前不同的地方。

画出本题的树形结构：
47.全排列II1

用used数组做树层去重前，记得对nums数组进行排序。本题中的used数组有两个作用：

  • 避免同一个元素被重复使用
  • 做树层去重

接下来写具体的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
vector<int> path;
vector<vector<int>> res;

void backtracking(vector<int>& nums, vector<int>& used)
{
    // 终止条件
    if (path.size() == nums.size())
    {
        res.push_back(path);
        return;
    }
    
    // 单层递归逻辑
    for (int i = 0; i < nums.size(); i ++ )
    {
        // 树层去重
        if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue;
        // 同一个元素不能被重复取，因此取过的数直接跳过
        if (used[i] == 1) continue;
        
        // 处理节点
        used[i] = 1;
        path.push_back(nums[i]);
        // 递归
        backtracking(nums, used);
        // 回溯
        used[i] = 0;
        path.pop_back();
    }
}

细节：

1
2
// 树层去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue;

可以通过

1
2
// 树枝去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 1) continue;

也可以通过。这意味着树层去重和树枝去重都可以解决本题。但树层去重的效率更高，树层去重会剪掉更多分支，而树枝去重要一直到最后一个树枝才会列出所有的结果。因此还是推荐树层去重的写法。以[1, 1, 1]为例，画出树层去重和树枝去重的树形结构：
47.全排列II2

47.全排列II3

很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

时间复杂度和空间复杂度分析：

  • 时间复杂度: 最差情况所有元素都是唯一的，时间复杂度为$O(n!\times n)$。 对于n个元素一共有n!中排列方案。而对于每一个答案，我们需要$O(n)$去复制最终放到res数组。
  • 空间复杂度: $O(n)$。空间复杂度即为回溯树的深度，其取决于nums数组中有多少个元素。

心得与备忘录

491.递增子序列

关键点：set去重->剪枝->数组去重取代set去重

  1. 本题和90.子集II乍一看非常相似，但细节上有很大不同，解决本题时不能有惯性思维。

  2. 之前去重的方法都是利用used数组，这意味着需要对nums数组进行排序。在本题中，如果对nums数组进行排序，就会打乱原数组中元素的顺序，导致递增子序列发生改变。因此，本题不能用used数组去重，而需要用set去重。因为用set去重不需要对原数组排序。

  3. 本题有两个剪枝条件：

    • 剪枝条件1：若所取元素小于子序列最后一个元素，则需要剪枝。此时要求子序列非空，否则path.back()会报错。剪枝条件1的原因是本题要求子序列是递增的。

    • 剪枝条件2：用set做树层去重

    两个剪枝条件用||相连。

  4. 为什么不需要对set进行回溯？

    每进入一层递归，都会重新定义一个set。因此set就是确保同一层中没有取到相同的元素。在进入下一层递归时，set会被刷新（重新定义）。因此set并不会对树枝去重，只会对树层去重。而used数组需要做回溯，因为used数组记录的是元素是否在path中被使用过，因此path中加减元素都需要对used数组进行相应的修改。

  5. 本题的去重方法也可以应用于40.组合总和II和90.子集II。

  6. 由于本题nums[i]的数据范围很小，因此可以用数组做去重，运行效率也更高。只需要将set替换为普通数组，然后做一个偏移（数值-100-100映射到数组下标0-200上）即可。

  7. 本题的时间和空间复杂度分别为$O(n\times2^n)$和$O(n)$。同90和78。

46.全排列

  1. 排列问题和组合问题的两大区别：
    • 每层都是从0开始搜索而不是startIndex
    • 需要used数组记录path里都放了哪些元素了
  2. 不需要startIndex的原因：[1, 2]和[2, 1]是同一个组合，但却是不同的排列，因此排列问题不能像组合问题那样从当前元素的下一个元素开始取，而是要取nums数组中所有当前没有取过的元素。
  3. 需要used数组的原因：used数组记录了此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
  4. 终止条件为path.size() == nums.size()，nums数组的大小限制了树的深度。
  5. 本题的时间复杂度为$O(n!)$，空间复杂度为$O(n)$。时间复杂度的原因是有$n$个元素的nums数组共有$n!$种排列。空间复杂度的原因是递归的深度（即树的深度）为$n$。

47.全排列 II

  1. 本题相当于40.组合总和II（树层去重）和46.全排列的结合。
  2. 本题的去重有三种写法：set去重、数组去重、used数组去重。三种写法我都在初次尝试中给出了。
  3. 用used数组去重前，一定要记得对nums数组进行排序。另外两种去重写法则不需要对nums数组进行排序。
  4. 由于本题是在叶子节点处收集结果，因此需要终止条件。
  5. 本题的时间复杂度为$O(n!\times n)$，空间复杂度为$O(n)$。具体原因参见实现部分。
  6. 本题用树层去重和树枝去重都可以，具体原因参见实现部分。但树层去重的效率远高于树枝去重，因此采用一贯以来的used数组树层去重写法即可，不要纠结树枝去重的原理和合理性。