qiaoxu123’s gists

qiaoxu123 / hash.cpp

Last active February 24, 2019 01:08

> 一道非常简单的字符串搜索题目，使用hash方法最简单，但是用的很不熟练。。 - Approach 1 : hash - Approach 2 : pair > if the string is extremely long, we wouldn't want to traverse it twice, so instead only storing just counts of a char, we also store the index, and then traverse the

	//Runtime: 64 ms, faster than 44.53%
	//Memory Usage: 13.5 MB, less than 49.72%

	class Solution {
	public:
	int firstUniqChar(string s) {
	unordered_map<char,int> set;


	for(int i = 0;i < s.length();++i)

qiaoxu123 / simple.cpp

Last active February 23, 2019 00:14

> 这道跟之前那道Best Time to Buy and Sell Stock 买卖股票的最佳时间很类似，但都比较容易解答。这道题由于可以无限次买入和卖出。我们都知道炒股想挣钱当然是低价买入高价抛出，那么这里我们只需要从第二天开始，如果当前价格比之前价格高，则把差值加入利润中，因为我们可以昨天买入，今日卖出，若明日价更高的话，还可以今日买入，明日再抛出。以此类推，遍历完整个数组后即可求得最大利润。

	//Runtime: 8 ms, faster than 100.00%
	//Memory Usage: 9.5 MB, less than 65.93%

	class Solution {
	public:
	int maxProfit(vector<int>& prices) {
	if(prices.empty()) return 0;
	int ret = 0;
	for (size_t p = 1; p < prices.size(); ++p)
	ret += max(prices[p] - prices[p - 1], 0);

qiaoxu123 / code.cpp

Created February 22, 2019 00:40

	//Runtime: 16 ms, faster than 98.23%
	//Memory Usage: 12.3 MB, less than 77.06%

	class Solution {
	public:
	bool isValidSudoku(vector<vector<char>>& board) {
	int used1[9][9] = {0},used2[9][9] = {0},used3[9][9] = {0};

	for(int i = 0;i < board.size();++i)
	for(int j = 0;j < board[i].size();++j)

qiaoxu123 / hash.cpp

Last active February 21, 2019 11:40

> 这道题是之前那道Intersection of Two Arrays的拓展，不同之处在于这道题允许我们返回重复的数字，而且是尽可能多的返回，之前那道题是说有重复的数字只返回一个就行。 - Approach 1 : hash > 用哈希表来建立nums1中字符和其出现个数之间的映射, 然后遍历nums2数组，如果当前字符在哈希表中的个数大于0，则将此字符加入结果res中，然后哈希表的对应值自减1 - Approach 2 > 对两个数组进行排序，然后和之前的程序相同做法即可

	//Runtime: 12 ms, faster than 82.84%
	//Memory Usage: 9.6 MB, less than 26.11%

	class Solution {
	public:
	vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
	unordered_map<int,int> hash;
	vector<int> res;
	for(auto i : nums1) ++hash[i];
	for(auto i : nums2) {

qiaoxu123 / binary_search.cpp

Last active February 20, 2019 01:56

> 思路：该题目主要是查找两个数组的交集，并注意不要有重复数字。**主要考察数组的查找与遍历** - Approach 1 : set数组可以用个set把nums1都放进去，然后遍历nums2的元素，如果在set中存在，说明是交集的部分，加入结果的set中，最后再把结果转为vector的形式即可： - Approach 2 ：two pointers 先给两个数组排序，然后用两个指针分别指向两个数组的开头，然后比较两个数组的大小，把小的数字的指针向后移，如果两个指针指的数字相等，那么看

	//Runtime: 12 ms, faster than 89.15%
	//Memory Usage: 9.2 MB, less than 73.59%

	class Solution {
	public:
	vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
	set<int> res;
	sort(nums2.begin(),nums2.end());
	for(auto a : nums1) {
	if(binarySearch(nums2,a)) {

qiaoxu123 / rotate_anticlockwise.cpp

Last active February 10, 2019 01:16

> 考察二维数组的使用，挺难的。使用了数学思想下面列出的是顺时针旋转和逆时针旋转

	/*
	* anticlockwise rotate
	* first reverse left to right, then swap the symmetry
	* 1 2 3 3 2 1 3 6 9
	* 4 5 6 => 6 5 4 => 2 5 8
	* 7 8 9 9 8 7 1 4 7
	*/

	//Runtime: 8 ms, faster than 100.00%
	void anti_rotate(vector<vector<int> > &matrix) {

qiaoxu123 / easy.cpp

Created February 2, 2019 11:27

> 一道数组类题目，考察数组数据的处理。题目的难点在于如何处理进位问题在这直接原地进行进位处理，可以很方便地理解。

	//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Plus One.
	//Memory Usage: 770 KB, less than 50.21% of C++ online submissions for Plus One.

	class Solution {
	public:
	vector<int> plusOne(vector<int>& digits) {
	for(int i = digits.size() - 1; i >= 0; --i){
	if(digits[i] == 9)
	digits[i] = 0;
	else{

qiaoxu123 / min_max.cpp

Created January 31, 2019 02:53

#### Approach 1 : Sort >首先对数组进行排序，然后将未排序数组与原数组进行比较 --- #### Approach 2 : max on left, min on right > The idea is that: 1. From the left, for a number to stay untouched, there need to be no number less than it on the right hand side; 2. From the rig

	//Runtime: 24 ms, faster than 98.78% of C++ online submissions

	/**
	* /------------\
	* nums: [2, 6, 4, 8, 10, 9, 15]
	* minr: 2 4 4 8 9 9 15
	* <--------------------
	* maxl: 2 6 6 8 10 10 15
	* -------------------->
	*/

qiaoxu123 / iteration.cpp

Created January 25, 2019 03:05

> Tree题目，还是考察Tree 的Depth Search - Approach 1 : Recursion > 使用递归实现，自己还是没有写出来，很不熟练 - Approach 2 : Iterations > 借助heap来实现

_

qiaoxu123 / myCode.cpp

Created January 24, 2019 00:42

> 经典的数组类题目。可以使用简单的额外空间方法，或者使用固定空间算法。同时还要考虑排序问题，在此处使用的std的sort函数实现 - Approach 1 ： std::sort

	//Runtime: 76 ms, faster than 100.00% of C++

	class Solution {
	public:
	vector<int> sortedSquares(vector<int>& A) {
	vector<int> array;
	for(int i = 0;i < A.size();++i){
	array.push_back(A[i] * A[i]);
	}
	std::sort(array.begin(),array.end());

xqiao qiaoxu123