[LeetCode C++实现]75. Sort Colors

由于使用整数0 1 2分别代表红色 白色 和蓝色,而且是按照红色 白色和蓝色顺序排列。

所以直接排序肯定是正确的。

class Solution {

public:

void sortColors(vector<int>& nums) {

sort(nums.begin(),nums.end());

}

};

运行效率:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sort Colors.

Memory Usage: 8.3 MB, less than 64.12% o......

[LeetCode C++实现]504. Base 7

给定整数,转换为7进制字符串,这里美中不足的是针对数字0需要特殊处理,递归条件里无法区分0这种情况。

class Solution {

public:

string convertToBase7(int num) {

if(num == 0) return "0";

string res;

if(num < 0)

{

res+='-';

num = -1 * num;

}

helper(res,num);

return res;

}

private:

void helper(string& res,int num) {

if(num == 0) return;

helper......

[LeetCode C++实现]437. Path Sum III

完全理解这道题的话,对递归应该来说理解比较深了,这道题目是递归中嵌套一个递归,dfs主要是求解和等于sum的数量,然后pathSum是根据新的结点,求解符合条件的个数。

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x),......

[LeetCode C++实现]279. Perfect Squares

这道题目看似平平无奇,AC的过程中遇到了不少坑。

首先我们按照最直观、最快速的解法来写代码:

class Solution {

public:

int numSquares(int n) {

int sum = 0;

int num = n;

int cnt = 0;

while(num > 0) {

while(n >= sum + num && is_squares(num))

{

sum += num;

cnt += 1;

if(sum == n) return cnt;

}

num--;

}

return cnt;

}

private:

bool i......

快速排序

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。归并排序和快速排序一样均采用了分治法。

C语言实现:

来自算法导论的单向扫描算法,从左往右去扫描直到倒数第二个元素,出现小于最右边的元素则将小的那个元素与i标识的下标的元素交换,单向扫描法存在着冗余的元素交换,比如此时数组已有序1,2,3,4,5,6,单向扫描前5个元素均小于最后的元素6,那么每......

[LeetCode C++实现]113. Path Sum II

与Path Sum不同的是这里需要记录每条符合条件的路径信息,最直观的代码:

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

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

* TreeNo......

[LeetCode C++实现]112. Path Sum

首先使用最直观的解法,思路是递归从上向下,调用hasPathSum时targetSum减去当前结点值。当到达叶子结点时判断当前传入的targetSum是否和本结点相同。

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x),......

[LeetCode C++实现]470. Implement Rand10() Using Rand7()

使用提供的rand7实现rand10,要求随机数字出现的概率相同,这个问题如果反过来要求rand10实现rand7就比较简单了,每次调用rand10,如果返回的数据在1-7直接返回,否则使用rand10重新生成。

按照相同的思路,我们调用多次rand7,比如尝试构造rand7 + rand7,范围是2-14无法等概率求解,我们可以使用rand7 * rand7,范围是1-49,如果生成的范围在1-40,那么我们直接对10取余加一即可,如果在40-49这个范围那么重新生成。视频题解参考

// The rand7() API is already defined for you.

// i......

[LeetCode C++实现]33. Search in Rotated Sorted Array

以前总觉得二分查找简单,刷了一些题目后再也不觉得二分查找简单了,各种边界条件,简直要了老命,但对这道题而言,我们只要找到某半段有序数组即可,如果target恰好位于其中,那么问题就转换为普通的二分查找。下面是两种形式的写法:

class Solution {

public:

int search(vector<int>& nums, int target) {

int l = 0,r = nums.size() - 1;

while(l <= r)

{

int mid = l + (r - l)/2;

if(nums[mid] == target) return......

日常开发笔记总结(十)

面试总结专题

用户态到内核态转换

操作系统的进程空间可分为用户空间和内核空间,它们需要不同的执行权限。其中系统调用运行在内核空间。

从用户态切换到内核态主要有如下几种方式:

1.系统调用

在电脑中,系统调用(英语:system call),指运行在用户空间的程序向操作系统内核请求需要更高权限运行的服务。系统调用提供用户程序与操作系统之间的接口。大多数系统交互式操作需求在内核态运行。如设备IO操作或者进程间通信。

2.异常

页缺失(英语:Page fault,又名硬错误、硬中断、分页错误、寻页缺失、缺页中断、页故障等)指的是当软件试图访问已映射在虚拟地址空间中,但是目前并未......