Ascendlogo

Posted on Edited on In

448.Find All Numbers Disappeared in an Array

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

1
2
Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:

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

时间复杂度：O(nlogn)
空间复杂度：O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int nums_size = nums.size();
        vector<int> ans_vec;
        int count = 1;
        for (int num : nums) {
            if (num < count)continue;
            else while(num > count) {
                ans_vec.push_back(count);
                count++;
            }
            count++;
        }
        while (count <= nums_size) {
            ans_vec.push_back(count);
            count++;
        }
        return ans_vec;
    }
};

原地修改：

时间复杂度：O(n)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        for (auto& num : nums) {
            int x = (num - 1) % n;
            nums[x] += n;
        }
        vector<int> ret;
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                ret.push_back(i + 1);
            }
        }
        return ret;
    }
};

Posted on Edited on In

434.Number of Segments in a String

Given a string s, return the number of segments in the string.

A segment is defined to be a contiguous sequence of non-space characters.

Example 1:

1
2
3
Input: s = "Hello, my name is John"
Output: 5
Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]

Example 2:

1
2
Input: s = "Hello"
Output: 1

上锁：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int countSegments(string s) {
        int ans = 0;
        bool flag = true;
        for (char ch : s) {
            if (ch != ' ' && flag) {
                ans++;
                flag = false;
            }
            if (ch == ' ')flag = true;
        }
        return ans;
    }
};

原地法：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int countSegments(string s) {
        int segmentCount = 0;

        for (int i = 0; i < s.size(); i++) {
            if ((i == 0 || s[i - 1] == ' ') && s[i] != ' ') {
                segmentCount++;
            }
        }

        return segmentCount;
    }
};

Posted on Edited on In

415.Add Strings

Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

Example 1:

1
2
Input: num1 = "11", num2 = "123"
Output: "134"

Example 2:

1
2
Input: num1 = "456", num2 = "77"
Output: "533"

Example 3:

1
2
Input: num1 = "0", num2 = "0"
Output: "0"

时间复杂度：O(max(len1,len2)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        string ans = "";
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1[i] - '0' : 0;
            int y = j >= 0 ? num2[j] - '0' : 0;
            int result = x + y + add;
            ans.push_back('0' + result % 10);
            add = result / 10;
            i -= 1;
            j -= 1;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Posted on Edited on In

414.Third Maximum Number

Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

Example 1:

1
2
3
4
5
6
Input: nums = [3,2,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.

Example 2:

1
2
3
4
5
6
Input: nums = [1,2]
Output: 2
Explanation:
The first distinct maximum is 2.
The second distinct maximum is 1.
The third distinct maximum does not exist, so the maximum (2) is returned instead.

Example 3:

1
2
3
4
5
6
Input: nums = [2,2,3,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.

排序：

时间复杂度：O(nlogn)

空间复杂度：O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int thirdMax(vector<int> &nums) {
        sort(nums.begin(), nums.end(), greater<>());
        for (int i = 1, diff = 1; i < nums.size(); ++i) {
            if (nums[i] != nums[i - 1] && ++diff == 3) {
                return nums[i];
            }
        }
        return nums[0];
    }
};

有序集合：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int thirdMax(vector<int> &nums) {
        set<int> s;
        for (int num : nums) {
            s.insert(num);
            if (s.size() > 3) {
                s.erase(s.begin());
            }
        }
        return s.size() == 3 ? *s.begin() : *s.rbegin();
    }
};

一次遍历：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int thirdMax(vector<int> &nums) {
        long a = LONG_MIN, b = LONG_MIN, c = LONG_MIN;
        for (long num : nums) {
            if (num > a) {
                c = b;
                b = a;
                a = num;
            } else if (a > num && num > b) {
                c = b;
                b = num;
            } else if (b > num && num > c) {
                c = num;
            }
        }
        return c == LONG_MIN ? a : c;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int thirdMax(vector<int> &nums) {
        int *a = nullptr, *b = nullptr, *c = nullptr;
        for (int &num : nums) {
            if (a == nullptr || num > *a) {
                c = b;
                b = a;
                a = &num;
            } else if (*a > num && (b == nullptr || num > *b)) {
                c = b;
                b = &num;
            } else if (b != nullptr && *b > num && (c == nullptr || num > *c)) {
                c = &num;
            }
        }
        return c == nullptr ? *a : *c;
    }
};

Posted on Edited on In

文件和目录命令

  • ls

    • -a显示指定目录下所有子目录和文件，包括隐藏文件

    • -l纵向显示文件列表和详细信息

    • -h以KB显示文件大小

    • 通配符的使用

      • *表示任意个数字符

        ？表示任意一个字符

        []表示可以匹配字符组中的任意一个

        [abc]匹配a，b，c中任意一个

        [a-f]匹配a到f范围中任意一个字符

  • cd

    • cd 切换到当前用户主目录/home/用户目录
    • cd ～ 切换到当前用户主目录/home/用户目录
    • cd . 保持当前目录不变
    • cd .. 切换到上级目录
    • cd - 可以在最近两次工作目录之间来回切换
    • 绝对路径：在输入路径时最前面不是/或～，表示相对当前目录所在的目录位置
    • 相对路径：在输入路径时，最前面是/或者～，表示从根目录/家目录开始的具体位置

  • touch

    • 文件不存在，创建文件
    • 文件存在，修改末次修改时间

  • mkdir

    • 创建目录，同一个目录下目录和文件都不能同名
    • -p创建多级目录

  • rm

    • 删除后无法恢复
    • -f强制删除，忽略不存在的文件
    • -r递归删除目录下内容，删除文件夹时使用

  • tree

    • 以树状图列出文件目录结构
    • -d只显示目录

拷贝和移动命令

  • cp

    • cp 源文件 目标文件复制文件或目录到另一个文件或目录中
    • -i覆盖文件前提示
    • -r若给出源文件是目录文件，则cp将递归复制该目录下所有子目录和文件，目标文件必须为一个目录名

  • mv

    • mv 源文件 目标文件：移动或重命名文件或目录
    • -i覆盖前提示

文件内容命令

  • cat

    • 显示文件全部内容
    • -b为文件标行号
    • -n为所有行标行号（包括空行）

  • more

    • 分屏显示文件
    • Space显示下一页
    • Enter一次滚动一行
    • b回滚一屏
    • f前滚一屏
    • q退出

  • grep

    • 文本搜索工具
    • -n显示匹配行及行号
    • -v显示不含不包含目标文本的行
    • -i忽略大小写
    • ^a行首，搜索以a开始的行
    • ke$行尾，搜索以ke为结尾的行

  • echo

    • 显示参数指定的文字
    • >表示输出，会覆盖文件原有内容
    • >>表示输入，会将内容追加到已有文件的

  • 管道|

    • 将一个命令的输出通过管道作为另一个命令的输入
    • more
    • grep

远程操作命令

  • shutdown

    • shutdown 选项 时间
    • -r重新启动
    • -c取消关机计划

  • ifconfig

    • 查看配置网卡设置信息
    • 127.0.0.1本地回环地址

  • ping

    • 检测计算机到计算机网络连接是否正常，数值越大，速度越慢

  • scp

    • 远程拷贝命令
    • scp -P port filename user@remote:Desktop/filename
      • 复制当前目录下文件到远程文件夹
    • scp -P port user@remote:Desktop/filename filename
      • 从远程文件夹复制文件到当前目录
    • WIN scp command
      • scp -rp .\Desktop\Notes logo@192.168.142.128:Desktop/
      • 复制当前目录下文件夹到远程目录
      • scp -p logo@192.168.142.128:Desktop/linuxNotes/Command.md C:\Users\admin\Desktop
        • 从远程文件夹复制文件到当前目录
    • -r复制文件夹

  • ssh

    • ssh -p 22 user@remote

    • ssh-keygen生成ssh钥匙

    • ssh-copy-id -p port user@remote让远程服务器记住公匙

    • 添加别名：在~/.ssh/config中追加

      1
      2
      3
      4
      Host logo_ubuntu
      	Hostname 172.***.***.***
      	User logo
      	Port 22

用户权限命令

  • ls -l 拓展

    • r 可读 4

      w 可写 2

      x 可执行 1

    • 第一列（一个字符）：是否是文件夹标记

      第二列（三个字符）：文件拥有者权限

      第三列（三个字符）：组权限

      第四列（三个字符）：其他用户权限

      第五列（数字）：硬连接数

      • 硬连接数：有多少种方式可以访问当前目录/文件

  • chmod

    • 修改用户/组对文件/目录权限
    • chmod +/- rwx 文件|目录名
      • 执行文件：./文件名

  • sudo

    • 以其他身份来执行命令，预设的身份为root

组管理命令

  • 创建组/删除组都需要sudo
  • groupadd 组名添加组
  • groupdel 组名删除组
  • cat/etc/group确认组信息
  • 组信息保存在/etc/group文件中
  • /etc目录是专门用来保存系统配置信息的目录
  • chgrp -R 组名 文件/目录名递归修改文件/目录的所属组

用户管理

  • useradd -m -g 组添加新用户

    • -m 自动建立用户家目录
    • -g 指定用户所在的组，否则会建立一个和用户同名的组

  • passwd 用户名设置用户密码

  • userdel -r 用户名删除信息

    • -r 删除用户家目录

  • cat /etc/passwd | grep 用户名确认用户信息，新建用户后，用户信息会保存在/etc/passwd中

  • id 用户名查看用户UID（用户标识）和GID（组标识）信息

  • who查看当前所有登陆的用户列表

  • whoami查看当前登陆用户的账户名

  • passwd文件：/etc/passwd文件保存的是用户的信息，由6个分号组成的7个信息

    • 用户名

      密码（x，表示加密的密码）

      UID

      GID

      用户全名或本地账号

      家目录

      登陆使用的Shell，就是登陆之后使用的终端命令，ubuntu默认的是dash

  • usermod -g 组 用户名修改用户主组

  • usermod -G 组 用户名修改用户附加组

    • usermod -G sudo 用户名给用户添加sudo权限

  • usermod -s /bin/bash修改用户登陆Shell为bash，XShell下dash存在缺陷

  • which

    • which 命令查看执行命令所在位置

      • /user/passwd用于保存用户信息的文件

        /user/bin/passwd用于修改用户密码的程序

        /bin二进制执行文件目录，主要用于具体应用

        /sbin系统管理员专用的二进制代码存放目录，主要用于系统管理

        /usr/bin后期安装的一些软件

        /usr/sbin超级用户的一些管理程序

  • su

    • su - 用户名切换用户和目录
    • exit退出当前登陆目录
    • su切换到root，但不安全

  • 修改文件权限

    • chown 用户名 文件名|目录名修改文件的拥有者
    • chgrp -R 组名 文件名|目录名递归修改文件的组
    • chmod -R 755递归修改文件权限，三个数字分别代表拥有者/组/其他用户的权限
    • r -> 4 w -> 2 x -> 1,例如755->rwx r-x r-x

系统信息相关命令

  • date查看当前系统时间

  • cal 查看日历

    • -y查看一年的日历

  • df -h显示磁盘剩余空间

  • du -h[目录名]显示目录下文件大小

  • ps aux查看进程的详细状况

    • ps默认只会显示当前用户通过终端启动的应用程序

    • a 显示终端上的所有进程，包括其他用户的进程

      u 显示进程的详细状态

      x 显示没有控制终端的进程

  • top动态显示运行中的进程并排序

  • kill [-9] 进程代号终止指定代号的进程，-9表示强行终止

    • 使用kill时不要终止root身份开启的进程

其他命令

  • find

    • find[路径] -name "*.py"查找文件

  • ln

    • ln -s 被链接的源文件 链接文件建立文件的软链接
    • 无-s建立的是硬链接文件（两个文件占用相同大小的硬盘空间）
    • 源文件要使用绝对路经，方便移动链接文件后仍能正常使用
    • 在Linux中文件名和文件数据是分开存储的

打包压缩

  • tar -cvf 打包文件.tar打包文件

  • tar -xvf 打包文件.tar解包文件

  • c 生成档案文件，创建打包文件

    x 解开档案文件

    v 列出归档解档的详细过程，显示进度

    f 指定档案文件名称，f后面一定是.tar文件，所以必须放选项最后

  • gzip

    • tar只负责打包文件，但不压缩

    • 用gzip压缩打包后文件扩展名为filename.tar.gz

    • tar -zcvf 打包文件.tar.gz 被压缩的文件/路径...压缩文件

    • tar -zxvf 打包文件.tar.gz 解压缩文件

    • tar -zxvf 打包文件.tar.gz -C 目标路径解压缩文件到指定路径（指定路径必须存在）

  • bzip2

    • tar -jcvf 打包文件.tar.gz 被压缩的文件/路径...压缩文件
    • tar -jxvf 打包文件.tar.gz 解压缩文件

软件安装

  • sudo apt install 软件包

  • sudo apt remove 软件包

  • sudo apt upgrade

Posted on Edited on In

412.Fizz Buzz

Given an integer n, return a string array answer (1-indexed) where:

  • answer[i] == "FizzBuzz" if i is divisible by 3 and 5.
  • answer[i] == "Fizz" if i is divisible by 3.
  • answer[i] == "Buzz" if i is divisible by 5.
  • answer[i] == i (as a string) if none of the above conditions are true.

Example 1:

1
2
Input: n = 3
Output: ["1","2","Fizz"]

Example 2:

1
2
Input: n = 5
Output: ["1","2","Fizz","4","Buzz"]

Example 3:

1
2
Input: n = 15
Output: ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> ans_vec;
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 && i % 5 == 0)ans_vec.push_back("FizzBuzz");
            else if (i % 3 == 0)ans_vec.push_back("Fizz");
            else if (i % 5 == 0)ans_vec.push_back("Buzz");
            else ans_vec.push_back(to_string(i));
        }
        return ans_vec;
    }
};

Posted on Edited on In

409.Longest Palindrome

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

Example 1:

1
2
3
Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

1
2
3
Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.

贪心：

时间复杂度：O(n)

空间复杂度：O(S)，S为字符集大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> count;
        int ans = 0;
        for (char c : s)
            ++count[c];
        for (auto p : count) {
            int v = p.second;
            ans += v / 2 * 2;
            if (v % 2 == 1 && ans % 2 == 0)
                ++ans;
        }
        return ans;
    }
};

Posted on Edited on In

405.Convert a Number to Hexadecimal

Given an integer num, return a string representing its hexadecimal representation. For negative integers, two’s complement method is used.

All the letters in the answer string should be lowercase characters, and there should not be any leading zeros in the answer except for the zero itself.

Note: You are not allowed to use any built-in library method to directly solve this problem.

Example 1:

1
2
Input: num = 26
Output: "1a"

Example 2:

1
2
Input: num = -1
Output: "ffffffff"

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string toHex(int num ) {
        string pos = "0123456789abcdef";
        if (num == 0)
        {
            return "0";
        }
        string ans;

        unsigned _num = num;
        while (_num)
        {
            ans += pos[_num % 16];
            _num = _num / 16;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

位运算：

时间复杂度：O(k)，k是整数的十六进制数的位数

空间复杂度：O(k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string toHex(int num) {
        if (num == 0) {
            return "0";
        }
        string sb;
        for (int i = 7; i >= 0; i --) {
            int val = (num >> (4 * i)) & 0xf;
            if (sb.length() > 0 || val > 0) {
                char digit = val < 10 ? (char) ('0' + val) : (char) ('a' + val - 10);
                sb.push_back(digit);
            }
        }
        return sb;
    }
};

Posted on Edited on In

404.Sum of Left Leaves

Given the root of a binary tree, return the sum of all left leaves.

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

Example 1:

img

1
2
3
Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.

Example 2:

1
2
Input: root = [1]
Output: 0

深度优先遍历：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isLeafNode(TreeNode* node) {
        return !node->left && !node->right;
    }

    int dfs(TreeNode* node) {
        int ans = 0;
        if (node->left) {
            ans += isLeafNode(node->left) ? node->left->val : dfs(node->left);
        }
        if (node->right && !isLeafNode(node->right)) {
            ans += dfs(node->right);
        }
        return ans;
    }

    int sumOfLeftLeaves(TreeNode* root) {
        return root ? dfs(root) : 0;
    }
};

广度优先遍历：

时间复杂度：O(n)

空间复杂度：O(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
30
31
32
33
34
class Solution {
public:
    bool isLeafNode(TreeNode* node) {
        return !node->left && !node->right;
    }

    int sumOfLeftLeaves(TreeNode* root) {
        if (!root) {
            return 0;
        }

        queue<TreeNode*> q;
        q.push(root);
        int ans = 0;
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left) {
                if (isLeafNode(node->left)) {
                    ans += node->left->val;
                }
                else {
                    q.push(node->left);
                }
            }
            if (node->right) {
                if (!isLeafNode(node->right)) {
                    q.push(node->right);
                }
            }
        }
        return ans;
    }
};

Posted on Edited on In

401.Binary Watch

A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

  • For example, the below binary watch reads "4:51".

img

Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order.

The hour must not contain a leading zero.

  • For example, "01:00" is not valid. It should be "1:00".

The minute must be consist of two digits and may contain a leading zero.

  • For example, "10:2" is not valid. It should be "10:02".

Example 1:

1
2
Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

Example 2:

1
2
Input: turnedOn = 9
Output: []

枚举法：

时间复杂度：O(1)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        for (int h = 0; h < 12; ++h) {
            for (int m = 0; m < 60; ++m) {
                if (__builtin_popcount(h) + __builtin_popcount(m) == turnedOn) {
                    ans.push_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m));
                }
            }
        }
        return ans;
    }
};

二进制枚举：

时间复杂度：O(1)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        for (int i = 0; i < 1024; ++i) {
            int h = i >> 6, m = i & 63; // 用位运算取出高 4 位和低 6 位
            if (h < 12 && m < 60 && __builtin_popcount(i) == turnedOn) {
                ans.push_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m));
            }
        }
        return ans;
    }
};