Category: C/C++

C++ memset 的使用

在竞赛时使用 memset 发现初始化的默认值无法生效，后来发现我对 memset 的参数的理解有误。void * memset ( void * ptr, int value, size_t num );将指针 ptr 所指向的内存块中前 num 个字节，用 value 替换。注意，这里面的 value 是一个字节的值。下面谈及两个场景，初始化为 0。memset(a,0,sizeof(a));初始化“最大值”，之所以加上引号，是因为并不是真正的最大值。但是能够带来最大值的效果的同时，还能带来一些好处。memset(a,0x3f,sizeof(0x3f));0x3f3f3f3f 代表的十进制数值是 1061109567 是 10^9，和 32 位的有符号整型的最大值是一个量级。而往往，数据在一般情况下都是小于 10^9 的。所以，可以达到替换最大值的效果0x3f3f3f3f + 0x3f... Read More

为什么C语言不会过时？

这是C语言系列博客的第3篇，如果对前2篇感兴趣，可以点击下面的链接：什么教材适合零基础的C语言学习者？为什么C语言很难评价任何一门编程语言，都是招人骂的。 永远是这样。就像是春寒料峭的季节， 街上穿棉袄和穿单衣的擦肩而过，双方一定是同时在心里出现了两个字：“傻逼！”这个在心理学上有个专业的名字：叫做“二逼”现象那我为啥还要做这个挨骂的事呢？作为《C语言点滴》《drop of knowledge of C++》书籍的作者，《C语言新思维，第二版》的译者。我觉得我有责任系统的介绍一下这本语言，他的特点，还有他的未来。这个问题对很多刚刚踏入程序猿这个行业的新手至关重要。因为他们有深深的担忧，万一C语言就像Fortran，perl语言那样过时了怎么办？为什么C语言不会过时？先上一个表，这个就是著名的TIOBE语言排行榜。目前它是一个最权威的一个语言流行度的排行榜，从这个排行榜上看，你会得到一个... Read More

小旭讲解 LeetCode 399. Evaluate Division 并查集

原题英文 —— Evaluate DivisioEquations are given in the formatA / B = k, whereAandBare variables represented as strings, andkis a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return-1.0.Example:Givena / b = 2.0, b / c = 3.0.queries are:a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .return[6.0, 0.5, -1.0, 1.0, -1.0 ].The input is:vec... Read More

小旭讲解 LeetCode 39. Combination Sum 回溯法

原题Given asetof candidate numbers (candidates)(without duplicates)and a target number (target), find all unique combinations incandidateswhere the candidate numbers sums totarget.Thesamerepeated number may be chosen fromcandidatesunlimited number of times.NoteAll numbers (includingtarget) will be positive integers.The solution set must not contain duplicate combinations.Example 1Input: candidates... Read More

一只青蛙跳出来的分治法、回溯法与动态规划

从2018年7月份开始，基础薄弱的我从0开始刷LeetCode题目。目的性很明确，也很简单——就是为了提高解决问题的思考实践能力，也为了提升自己的核心竞争力。也许，牛人会觉得这并不算什么竞争力。是的，我同意的。但，这是我目前能做的比较基础的事情罢了。迄今（2018年12月28日）为止，已经刷了108道题目。顺序基本上是按照出现的频率（Frequency）来刷的，这个频率在LeetCode上需要订阅后才可以看得到。那么在刷了108道题目后，有那么一些题目会觉得“似曾相识”了，也会有一种触类旁通的感觉了。所以，我觉得应该适当放慢刷题的速度，同时做做总结了。所以，计划了一项视频解说计划，在YouTubeh和B站都建立了《小旭解说算法之路》的频道，欢迎订阅，多多提建议。那么，进入正题。经过了108道题的历练之后，我来说说对于分治法、回溯法和动态规划的理解。我觉得他们三者是一个相互有交集的概念，并不... Read More

小旭讲解 LeetCode 53. 最大子序和 动态规划 分治策略

原题Given an integer arraynums, find the contiguous subarray(containing at least one number) which has the largest sum and return its sum.ExampleInput: [-2,1,-3,4,-1,2,1,-5,4]Output: Explanation:[4,-1,2,1] has the largest sum = 6.Follow upIf you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.题解动态规划哔哩哔哩 动态规划YouTube 动态规划通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。... Read More

[LeetCode]743. Network Delay Time

原题There are N network nodes, labelled 1 to N.Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.NoteN will be in the ... Read More

[LeetCode]893. Groups of Special-Equivalent Strings

原题You are given an array A of strings.Two strings S and T are special-equivalent if after any number of moves, S == T.A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.Return the number of groups o... Read More

[LeetCode]Valid Palindrome II

原题Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.Example 1Input: "aba"Output: TruExample 2Input: "abca"Output: TruExplanation: You could delete the character 'c'.NoteThe string will only contain lowercase characters a-z. The maximum length of the string is 50000.思路水题。判断是否是回文字符串最简单的方式就是从左右两端逐步向中心逼近（双指针），如下代码[code lang="cpp"for (in... Read More

[LeetCode 889]Construct Binary Tree from Preorder and Postorder Traversal

原题Return any binary tree that matches the given preorder and postorder traversals.Values in the traversalspreandpostare distinctpositive integers.Example 1Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1Output: [1,2,3,4,5,6,7Note1 <= pre.length == post.length <= 30pre[]andpost[]are both permutations of1, 2, ..., pre.length.It is guaranteed an answer exists. If there exists multiple an... Read More

[LeetCode]Sum of Subarray Minimums

原题Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.Since the answer may be large, return the answer modulo 10^9 + 7.Example 1Input: [3,1,2,4Output: 1Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.Note1 <= A.length <1 <= A[i] <... Read More

[LeetCode]Fruit Into Baskets

原题In a row of trees, the i-th tree produces fruit with type tree[i].You start at any tree of your choice, then repeatedly perform the following stepsAdd one piece of fruit from this tree to your baskets.  If you cannot, stop.Move to the next tree to the right of the current tree.  If there is no tree to the right, stop.Note that you do not have any choice after the initial choice of starting tree... Read More

[LeetCode]Remove Nth Node From End of List

原题Given a linked list, remove the n-th node from the end of list and return its head.ExampleGiven linked list: 1->2->3->4->5, and n = 2.After removing the second node from the end, the linked list becomes 1->2->3->5.NoteGiven n will always be valid.Follow upCould you do this in one pass思路首先，明确题意。题目给出了一个只有后继（successor），没有前驱（predecessor）的一个单向链表。要求删除倒数第n个节点。那么，思路自然会想到的就是在一次遍历就搞定题目要求。所以，我们自然要在遍历的过程中保存一... Read More

[LeetCode]4Sum

原题Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.NoteThe solution set must not contain duplicate quadruplets.ExampleGiven array nums = [1, 0, -1, 0, -2, 2], and target = 0.A solution set is[-1, 0, 0, 1][-2, -1, 1, 2][-2, 0, 0, 2题解本题的... Read More

[LeetCode]3Sum Closest

原题Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.ExampleGiven array nums = [-1, 2, 1, -4], and target = 1.The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).思路本题目的解题思路和3Sum很像，区别在于3Sum求解的是三个数字和为target（即为0），然而3Su... Read More

[LeetCode]3Sum

原题Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Note: The solution set must not contain duplicate triplets.For example, given array S = [-1, 0, 1, 2, -1, -4]A solution set is[-1, 0, 1][-1, -1, 2题解暴力解法因为需要计算三个数字的总和，所以需要进行3层的遍历，故时间复杂度需要O(n^3)，看来不可取，果断放弃。毕竟是medium难度的题，不至于这么个解法。two-pointes solutio... Read More

[LeetCode]Two Sum

原题Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.ExampleGiven nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].题解暴力解法暴力解法使用两层for循环，遍历每一种存在的情况。[code lang="cpp"class Solution publicvector<int... Read More

[LeetCode]Palinkdrom Number

ProbleDetermine whether an integer is a palindrome. Do this without extra space.Some hints[code lang="shell" collapse="true"Could negative integers be palindromes? (ie, -1If you are thinking of converting the integer to string, note the restriction of using extra space.You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that th... Read More

[LeetCode]Roman to Integer

ProbleGiven a roman numeral, convert it to an integer.Input is guaranteed to be within the range from 1 to 3999.IdeaFinding the Law of Changing Roman Numbers into Arabic Numbers。Solutio[code lang="cpp"class Solution publicint romanToInt(string s) int l = s.length(), a = 0;for (int i = 0; i < l; ++iif (i < l - 1 && char2int(s[i]) < char2int(s[i + 1])) a -= char2int(s[i]);} else a += char2int(s[i]);... Read More

跟我一起写Makefile

概述什么是makefile？或许很多Winodws的程序员都不知道这个东西，因为那些Windows的集成开发环境(integrated development environment, IDE)都为你做了这个工作，但我觉得要作一个好的和professional的程序员，makefile还是要懂。这就好像现在有这么多的HTML的编辑器，但如果你想成为一个专业人士，你还是要了解HTML的标识的含义。特别在Unix下的软件编译，你就不能不自己写makefile了，会不会写makefile，从一个侧面说明了一个人是否具备完成大型工程的能力。因为，makefile关系到了整个工程的编译规则。一个工程中的源文件不计其数，并且按类型、功能、模块分别放在若干个目录中，makefile定义了一系列的规则来指定，哪些文件需要先编译，哪些文件需要后编译，哪些文件需要重新编译，甚至于进行更复杂的功能操作，因为ma... Read More

2018LeeCode算法题解一之Valid Palindrome

原题Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.For example"A man, a plan, a canal: Panama" is a palindrome."race a car" is not a palindrome.NoteHave you consider that the string might be empty? This is a good question to ask during an interview.For the purpose of this problem, we define empty string as valid palindrome.原题链接：https://... Read More

[维护中]基于文本图形（ncurses）的文本搜索工具 ncgrep

源码下载http://github.com/ncgrep/ncgre背景作为一个VIM党，日常工作开发中，会经常利用grep进行关键词搜索，以快速定位到文件。如图但是，这一过程会有两个效率问题展示的结果无法进行直接交互，需要手动粘贴文件路径在打开展示的结果没有进行分组，直接将结果罗列出来可想而知，当搜索的内容结果集比较大时，可谓痛苦。那可以用Vim中的Ag插件进行搜索啊？是的，但他只解决了交互的问题。仍然没有解决结果集分组分类的痛点。思路在使用Eclipse等IDE进行文本全局搜索时，在加载效果（懒加载）可视化方面有很大优势。那么，期望基于linux系统，提供一个类似的搜索工具。优点（功能）如下结果集可以直接交互结果集可以进行分组展示结果集通过“懒加载”方式装载基于文本图形界面的类库是什么呢？网上大致了解了下VIM、htop类似的软件，其都是基于一个叫ncurses的类库实现的。项目... Read More

使用Cgo的一点总结

今天想给一个C库写一个Golang binding，就查了一下cgo的使用，也遇到了一些坑。cgo的基本使用想在Go代码中使用C语言必须在代码开头注释中写，然后再紧接着的下一行写import "C"，这样就算是导入完成了。这个”C”不是一个真正的包，而是一个类似于命名空间的东西，所有能调用的C的变量、函数都包含在里面。举个最简单的例子package mai// #include <stdi// #include <stdli/void print(char *str) printf("%s\n", str);*import "C"import "unsafe"func main() s := "hello"cs := C.CString(sdefer C.free(unsafe.Pointer(cs)C.print(cs这个例子展示了cgo的基本使用方法。... Read More

关于int的取值范围（有种背下来）

unsigned int 0～429496729int -2147483648～214748364unsigned long 0～429496729long -2147483648～214748364long long的最大值：922337203685477580long long的最小值：-922337203685477580unsigned long long的最大值：184467440737095516__int64的最大值：922337203685477580__int64的最小值：-922337203685477580unsigned __int64的最大值：1844674407370955161原文链接：http://blog.csdn.net/niuox/article/details/823194 Read More