0. leetcode-cn刷题记录

1.两数之和

1.1 解答

• 暴力求解

• 哈希表 降低复杂度

1.1.1 C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
            std::unordered_map<int,int> map;
            for(int i=0;i<nums.size();++i){
                auto it = map.find(target-nums[i]);
                if(it != map.end()){
                    return {it->second, i};
                }
                map[nums[i]] = i;
            }
            return {};
    }
};

拓展——unordered_map in C++ STL

#include <unordered_map>

unordered_map is an associated container that stores elements formed by the combination of key-value and a mapped-value. Both key-value and mapped-value can be any type predefined or user-defined.

• The key value is used to uniquely identify the element

• The mapped value is the content associated with the key

#include <iostream>
#include <unordered_map>
#include <vector>

int main(int argc, char* argv[])
{
	std::vector<int> vec{-5, -4, -6, 2, 1, 7};
	std::unordered_map<int, int> map;
	for (int i = 0; i < vec.size();i++){
		map[vec[i]] = i;
	}
	for(auto& x:map){
		std::cout << x.first << "\t" << x.second<<std::endl;
	}
	return 0;
}

---

// C++ program to demonstrate functionality of unordered_map
#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
	// Declaring umap to be of <string, double> type
	// key will be of string type and mapped value will
	// be of double type
	unordered_map<string, double> umap;

	// inserting values by using [] operator
	umap["PI"] = 3.14;
	umap["root2"] = 1.414;
	umap["root3"] = 1.732;
	umap["log10"] = 2.302;
	umap["loge"] = 1.0;

	// inserting value by insert function
	umap.insert(make_pair("e", 2.718));

	string key = "PI";

	// If key not found in map iterator to end is returned
	if (umap.find(key) == umap.end())
		cout << key << " not found\n\n";

	// If key found then iterator to that key is returned
	else
		cout << "Found " << key << "\n\n";

	key = "lambda";
	if (umap.find(key) == umap.end())
		cout << key << " not found\n";
	else
		cout << "Found " << key << endl;

	// iterating over all value of umap
	unordered_map<string, double>:: iterator itr;
	cout << "\nAll Elements : \n";
	for (itr = umap.begin(); itr != umap.end(); itr++)
	{
		// itr works as a pointer to pair<string, double>
		// type itr->first stores the key part and
		// itr->second stores the value part
		cout << itr->first << " " << itr->second << endl;
	}
	return 0;
}

A practical problem based on unordered_map – given a string of words, find frequencies of individual words.

Input :  str = "geeks for geeks geeks quiz practice qa for";
Output : Frequencies of individual words are
   (practice, 1)
   (for, 2)
   (qa, 1)
   (quiz, 1)
   (geeks, 3)

// C++ program to find freq of every word using
// unordered_map
#include <iostream>
#include <unordered_map>
#include <string>
#include <sstream>
using namespace std;

// Prints frequencies of individual words in str
void printFrequencies(const string &str)
{
	// declaring map of <string, int> type, each word
	// is mapped to its frequency
	unordered_map<string, int> wordFreq;

	// breaking input into word using string stream
	stringstream ss(str); // Used for breaking words
	string word; // To store individual words
	while (ss >> word)
		wordFreq[word]++;

	// now iterating over word, freq pair and printing
	// them in <, > format
	unordered_map<string, int>:: iterator p;
	for (p = wordFreq.begin(); p != wordFreq.end(); p++)
		cout << "(" << p->first << ", " << p->second << ")\n";
}

// Driver code
int main()
{
	string str = "geeks for geeks geeks quiz "
				"practice qa for";
	printFrequencies(str);
	return 0;
}

2.两数相加

2.1 解答

2.1.1 C++

• 关于链表的一些操作

• 数字相加的进位

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            ListNode* head = nullptr; // 头指针
            ListNode* rear = nullptr; // 尾指针
            int carry = 0; // 保存进位位
            while(l1||l2){
                int n1 = l1==nullptr? 0 : l1->val;
                int n2 = l2==nullptr? 0 : l2->val;
                int sum = n1 + n2 + carry; 
                int data = sum % 10;
                if(head==nullptr){
                    head = new ListNode(data);
                    rear = head;
                }else{
                    rear->next = new ListNode(data); // 生成新节点
                    rear = rear->next; //尾指针后移
                }
                carry = sum/10; 
                if(l1!=nullptr){
                    l1 = l1->next;
                }
                if(l2!=nullptr){
                    l2 = l2->next;
                }
            }
            if(carry>0){ // 最后还有进位
                rear->next = new ListNode(carry);
            }
            return head;
    }
};