有不少不会的，就参考题目答案看了下断点调试了下
主要是能看下日期，大概知道自己那天写了那些，那些天没写。
#include <iostream>
#include <time.h>
#include <vector>
#include <unordered_set>
#include <map>
#include <stack>
#include <queue>
#include <unordered_map>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <iomanip>
#include <sstream>
using namespace std;
struct TreeNode
{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x),left(NULL),right(NULL){}
TreeNode(int x,TreeNode* p1,TreeNode* p2) : val(x),left(p1),right(p2){}
};
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
ListNode(int x,ListNode* p) : val(x), next(p) {}
};
struct TrieNode
{
bool isTrie;
TrieNode* t_next[26];
TrieNode() : isTrie(false)
{
for(int i=0;i<26;i++)
{
t_next[i] = NULL;
}
}
};
class Trie {
private:
TrieNode* t_map;
public:
/** Initialize your data structure here. */
Trie() {
t_map = new TrieNode();
}
/** Inserts a word into the trie. */
void insert(string word) {
if(word.size() == 0) return;
TrieNode* temp = t_map;
for(int i=0;i<word.size();i++)
{
cout<<" i is "<<i<<" word i is "<<word[i]<<" word i - a is "<<word[i] - 'a'<<endl;
if((temp->t_next)[word[i] - 'a'] == NULL)
{
TrieNode* node = new TrieNode();
(temp->t_next)[word[i] - 'a'] = node;
temp = (temp->t_next)[word[i] - 'a'];
}
else
{
temp = (temp->t_next)[word[i] - 'a'];
}
}
temp->isTrie = true;
cout<<"insert success this word is "<<word<<endl;
}
/** Returns if the word is in the trie. */
bool search(string word) {
if(word.size() == 0 || t_map == NULL) return false;
TrieNode* temp = t_map;
for(int i =0;i<word.size();i++)
{
if(NULL == (temp->t_next)[word[i] - 'a']) return false;
else temp = (temp->t_next)[word[i] - 'a'];
}
if(temp->isTrie) return true;
else return false;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
if(prefix == "" || t_map == NULL) return false;
TrieNode* temp = t_map;
for(int i=0;i<prefix.size();i++)
{
if(NULL == (temp->t_next)[prefix[i] - 'a']) return false;
else temp = (temp->t_next)[prefix[i] - 'a'];
}
return true;
}
};
class Point{
public:
Point(){};
Point (int x, int y): x(x),y(y) {};
int operator+(const Point &a){ //类内重载，运算符重载函数作为类的成员函数
Point ret;
ret.x = this->x + a.x;
ret.y = this->y + a.y;
return ret.x + ret.y;
}
int x,y;
string operator=(const Point& a)
{
string res;
if(a.x == this->x)
{
res = "equal";
}
else res = "not equal";
cout<<"int operator= res is "<<res<<endl;
return res;
}
};
//1207 单独的新类，已完成
class BSTIterator {
public:
BSTIterator(TreeNode* root) {
if(root == NULL)
{
k = 0;
count = 0;
}
else
{
k = 1;
count = getTreeNodeNums(root);
q.push(root);
while (!q.empty())
{
TreeNode* tmp = q.front();
q.pop();
nums.push_back(tmp->val);
if(tmp->left != NULL) q.push(tmp->left);
if(tmp->right != NULL) q.push(tmp->right);
}
std::sort(nums.begin(),nums.end());
}
}
int next() {
if(k > count || k <= 0) return 0;
int tmp = k;
k++;
return nums[tmp-1];
}
bool hasNext() {
if(k <= count && k > 0) return true;
else return false;
}
int getTreeNodeNums(TreeNode* root)
{
if(root == NULL) return 0;
return 1 + getTreeNodeNums(root->left) + getTreeNodeNums(root->right);
}
queue<TreeNode*> q;
vector<int> nums;
int k = 0; //表示当前是第k小个
int count = 0; //表示一共有多少个节点
};
//1211 leetcode 155
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
nums.clear();
}
void push(int x) {
nums.push_back(x);
}
void pop() {
nums.pop_back();
}
int top() {
if(nums.size() == 0) return 0;
return nums[nums.size()-1];
}
int getMin() {
if(nums.size() == 0) return 0;
auto minVal = std::min_element(nums.begin(),nums.end());
return *minVal;
}
vector<int> nums;
};
class Solution
{
public:
//20_1105 leetcode 208
//单独建类 已完成
//1106 leetcode 212
/*
给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
输入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
输出: ["eat","oath"]
*/
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
//这个真不会
}
//1107 leetcode 207
ListNode* reverseList(ListNode* head) {
if(head == NULL) return NULL;
ListNode* pre = NULL;
ListNode* cur = head;
while (cur != NULL)
{
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
//1107 leetcode 204
int countPrimes(int n) {
if(n <= 1) return 0;
}
//1107 leetcode 207道题目
/*
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
*/
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
}
//1109 leetcode 209
/*
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
*/
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size();
int minCount = INT_MAX;
bool flag = false;
for(int i = 0;i < n - 1;i++)
{
int curSum = 0;
for(int j=i;j < n; j++)
{
curSum = curSum + nums[j];
if(curSum >= s)
{
minCount = min(j-i+1,minCount);
flag = true;
break;
}
}
}
if(!flag) return 0;
return minCount;
}
//1109 leetcode 205
/*
同构字符串
输入: s = "egg", t = "add"
输出: true
输入：
"aba"
"baa"
输出： 预期：
true false
*/
bool isIsomorphic(string s, string t) {
if((s.size() == 0 && t.size() == 0) || (s == t) ) return true;
if(s.size() != t.size()) return false;
vector<int> nums_s(s.size(),0);
vector<int> nums_t(t.size(),0);
unordered_map<char,int> unMap1;
unordered_map<char,int> unMap2;
int count1 = 0;
int count2 = 0;
for(int i=0;i<s.size();i++)
{
if(unMap1.find(s[i]) == unMap1.end())
{
unMap1[s[i]] = count1;
nums_s[i] = count1;
count1++;
}
else
{
nums_s[i] = unMap1[s[i]];
}
}
for(int i=0;i<t.size();i++)
{
if(unMap2.find(t[i]) == unMap2.end())
{
unMap2[t[i]] = count2;
nums_t[i] = count2;
count2++;
}
else
{
nums_t[i] = unMap2[t[i]];
}
}
for(int i =0;i<s.size();i++)
{
if(nums_s[i] != nums_t[i]) return false;
}
return true;
}
//20_1110 leetcode 203
/*
删除链表中等于给定值 val 的所有节点。
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
*/
ListNode* removeElements(ListNode* head, int val) {
if(head == NULL) return NULL;
ListNode* dumy = new ListNode(0); //不能定义为空
dumy->next = head;
ListNode* pre = dumy;
while (head != NULL)
{
while (head != NULL && head->val == val)
{
head = head->next;
}
pre->next = head;
pre = head;
if(head == NULL) break;
else head = head->next;
}
return dumy->next;
}
//20_1110 leetcode 202
/*
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
*/
int countHappyNumTimes = 0;
bool isHappy(int n) {
if(n <= 0) return false;
if(n == 1) return true;
if(countHappyNumTimes > 100) return false;
countHappyNumTimes++;
return isHappy(calAllSingleNums(n));
}
int calAllSingleNums(int n)
{
int sum = 0;
while (n >0)
{
sum = sum + pow(n%10,2);
n = n / 10;
}
return sum;
}
//20_1111 leetcode 201
/*
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
示例 1:
输入: [5,7]
输出: 4
*/
int rangeBitwiseAnd_donothing(int m, int n) {
return 0;
}
//20_1117 leetcode 201
/*
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
示例 1:
输入: [5,7]
输出: 4
*/
int rangeBitwiseAnd(int m, int n) {
if(m == 0) return 0;
int temp = 1;
while (m != n)
{
m = m >> 1;
n = n >> 1;
temp = temp << 1;
}
return m * temp;
}
//20_1117 leetcode 200
/*
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
*/
//参考自https://blog.csdn.net/u014128608/article/details/91648737
int numIslands(vector<vector<int>>& grid) {
if(grid.size() == 0) return 0;
int cnt = 0;
for(int row = 0; row < grid.size(); row++)
{
for(int col = 0; col < grid[row].size(); col++)
{
if(grid[row][col] == 1)
{
cnt++;
dfsNumIslands(grid,row,col);
}
}
}
return cnt;
}
void dfsNumIslands(vector<vector<int>>& grid, int row, int col)
{
//根据row col位置dfs
if(row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || grid[row][col] == 0) return ;
grid[row][col] = 0;
dfsNumIslands(grid, row + 1, col);
dfsNumIslands(grid, row - 1, col);
dfsNumIslands(grid,row, col +1);
dfsNumIslands(grid,row, col -1);
}
//1117 leetcode 199 二叉树的右视图
/*
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
/ \ \
6 5 4 <---
*/
vector<int> rightSideView(TreeNode* root) {
queue<TreeNode*> q;
vector<int> res;
if(root == NULL) return res;
q.push(root);
while (!q.empty())
{
int qSize = q.size();
int count = 0;
while (count < qSize)
{
TreeNode* cur = q.front();
q.pop();
count++;
if(count == qSize)
{
res.push_back(cur->val);
}
if(cur->left != NULL) q.push(cur->left);
if(cur->right != NULL) q.push(cur->right);
}
}
return res;
}
//20_1117 临时贴一个二叉树层序遍历进阶版(每一层保存在一个数组中，最终是一个二维数组)
vector<vector<int>> getTreeNodeFloorPrint(TreeNode* root)
{
vector<vector<int>> res;
if(root == NULL) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty())
{
int count = 0;
int qSize = q.size();
vector<int> tmp;
while (count < qSize)
{
TreeNode* cur = q.front();
q.pop();
tmp.push_back(cur->val);
if(cur->left != NULL) q.push(cur->left);
if(cur->right != NULL) q.push(cur->right);
count++;
}
res.push_back(tmp);
}
return res;
}
//1117 leetcode 198
/*
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
*/
int rob_leetcode198(vector<int>& nums) {
if(nums.size() == 0) return 0;
if(nums.size() == 1) return nums[0];
if(nums.size() == 2) return max(nums[0],nums[1]);
if(nums.size() == 3)
{
int tmp = max(nums[0],nums[1]);
return max(tmp,nums[2]);
}
vector<int> dp(nums.size(),0);
dp[0] = nums[0];
dp[1] = max(nums[0],nums[1]);
for(int i=2;i<nums.size();i++)
{
dp[i] = max(dp[i-1],dp[i-2] + nums[i]);
}
return dp[nums.size() - 1];
}
//1117 leetcode 197
/*
SQL问题 已经完成
*/
//1117 leetcode 196
/*
SQL问题 已经完成
*/
//1117 leetcode 195
/*
Bash问题 已经完成
*/
//1118 leetcode 194
/*
Bash问题 已经完成
*/
//1118 leetcode 193
/*
Bash问题 已经完成
*/
//1118 leetcode 192
/*
Bash问题 已经完成
*/
//1119 leetcode 191
/*
二进制求有多少个1
*/
int hammingWeight(uint32_t n) {
// 参考自 https://leetcode-cn.com/problems/number-of-1-bits/comments/
int res = 0;
while(n)
{
res += n%2;
n = n>>1;
}
return res;
}
//1120 leetcode 190
/*
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
*/
uint32_t reverseBits(uint32_t n) {
vector<int> bits;
for(int i=0;i<32;i++)
{
bits.push_back(n%2);
n/=2;
}
uint32_t m=0;
for(int i=0;i<32;i++)
{
m=2*m+bits[i];
}
return m;
}
//1121 leetcode 189
/*
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
要求使用空间复杂度为 O(1) 的 原地 算法
*/
void rotate(vector<int>& nums, int k) {
if(k >= nums.size()) k = k%nums.size();
if(k == 0) return;
vector<int> v1(k,0);
vector<int> v2(nums.size()-k,0);
v1.assign(nums.begin()+ (nums.size() - k), nums.end());
v2.assign(nums.begin(),nums.begin()+ nums.size()-k);
for(int i=0;i<k;i++) nums[i] = v1[i];
for(int i=0;i<v2.size();i++) nums[i+k] = v2[i];
}
//1121 leetcode 188
int maxProfit_leetcode188(int k, vector<int>& prices) {
}
//1121 leetcode 121
//买卖股票 1 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
/*
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
*/
int maxProfit_leetcode121(vector<int>& prices) {
if(prices.size() == 0) return 0;
vector<int> dp(prices.size(), 0);
int curMinPrice = 0; //当前最小的价格
curMinPrice = prices[0];
for(int i=1;i<prices.size();i++)
{
if(prices[i] <= curMinPrice) curMinPrice = prices[i];
else
{
int tmp = prices[i] - curMinPrice;
dp[i] = tmp;
}
}
std::sort(dp.begin(),dp.end());
return dp[dp.size()-1];
}
//1126 leetcode 122 买卖股票的最佳时机 II
int maxProfit_leetcode122(vector<int>& prices) {
if(prices.size() == 0) return 0;
int res = 0;
int n = prices.size();
for(int i=0;i<n-1;i++)
{
if(prices[i] < prices[i+1])
{
res = res + prices[i+1] - prices[i];
}
}
return res;
}
//1130 leetcode 123买卖股票的最佳时机 III
int maxProfit_leetcode123(vector<int>& prices) {
if(prices.size() == 0) return 0;
int res = 0;
int firstDealSell;
int secondDealSell;
for(secondDealSell = prices.size() - 1; secondDealSell > 0 ; secondDealSell --)
{
if(prices[secondDealSell - 1] < prices[secondDealSell]) break;
}
for(firstDealSell = 1; firstDealSell < prices.size(); firstDealSell++)
{
while (firstDealSell + 1 < prices.size() && prices[firstDealSell + 1] >= prices[firstDealSell])
{
firstDealSell++;
}
int res1 = helpMaxProfix_leetcode123(prices,0,firstDealSell);
int res2 = helpMaxProfix_leetcode123(prices, firstDealSell+1, secondDealSell);
if(res1 + res2 > res)
{
res = res1 + res2;
}
}
return res;
}
int helpMaxProfix_leetcode123(vector<int>& prices, int left,int right)
{
int res = 0;
if(left >= right) return res;
int minPrice = prices[left];
for(int i = left+1;i<=right;i++)
{
res = max(res, prices[i] - minPrice);
minPrice = min(minPrice,prices[i]);
}
return res;
}
//1130 不会，参考自 https://blog.csdn.net/qq_41231926/article/details/84451773
int maxProfit_leetcode123_Second(vector<int>& prices)
{
//vector<int> stockPrices = {3,3,5,0,0,3,1,4};
int res = 0;
if(prices.size() == 0) return 0;
vector<vector<int>> dp(2,vector<int>(prices.size(),0));
for(int k =0;k<2;k++)
{
dp[k][0] = 0;
int minNumber = prices[0];
for(int i =1;i < prices.size();i++)
{
for(int b = 1;b<i;b++)
{
if(k == 0)
{
minNumber = min(minNumber,prices[b]);
}
else
{
minNumber = min(minNumber,prices[b] - dp[k -1][b-1]);
}
}
dp[k][i] = max(dp[k][i-1],prices[i] - minNumber);
}
}
return dp[1][prices.size() - 1];
}
//1203 leetcode 187
vector<string> findRepeatedDnaSequences(string s) {
if(s.size() < 10) return {};
unordered_set<string> res,mem;
for(int i =0;i<s.size() - 9;i++)
{
string cur = s.substr(i,10);
if(mem.count(cur)) res.insert(cur);
else mem.insert(cur);
}
return vector<string>(res.begin(),res.end());
}
//1203 leetcode 186
//订阅题目
//1203 leetcode 185
//SQL题目 已完成
//1203 leetcode 184
//SQL题目 已完成
//1203 leetcode 183
//SQL题目 已完成
//1203 leetcode 182
//SQL题目 已完成
//1203 leetcode 181
//SQL题目 已完成
//1203 leetcode 180
//SQL题目 已完成
//1204 leetcode 179
string largestNumber(vector<int>& nums) {
std::sort(nums.begin(),nums.end(),cmp);
string result = "";
int numSize = nums.size();
for(int i=0;i<numSize;i++)
{
result += to_string(nums[i]);
}
int resultSize = result.size(), beginIndex = 0;
while (beginIndex < resultSize && result[beginIndex] == '0')
{
beginIndex++;
}
if(beginIndex == resultSize) return "0";
else
{
return result.substr(beginIndex,resultSize);
}
}
static bool cmp(int num1, int num2)
{
string str1 = to_string(num1);
string str2 = to_string(num2);
return str1 + str2 > str2 + str1;
}
//1204 leetcode 178
//SQL题目 已完成 这道题目的'Rank'要用''
/* 整体结果作为tmp tmp放在外面
SELECT max(Salary) as SecondHighestSalary
from (SELECT salary
from employee
WHERE salary not in
(SELECT max(salary) from employee)) as tmp;
*/
//1204 leetcode 177
//SQL题目 已完成
//1204 leetcode 176
//SQL题目 已完成
//1204 leetcode 175
//SQL题目 已完成
//1207 leetcode 174
/*
这个真不会
https://blog.csdn.net/xiaoan08133192/article/details/107302857?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.control
*/
int calculateMinimumHP(vector<vector<int>>& dungeon) {
if(dungeon.size() == 0) return 0;
int row = dungeon.size();
int column = dungeon[0].size();
vector<vector<int>> dp(row,vector<int>(column,0));
for(int i = row-1;i>=0;i--)
{
for(int j = column -1 ;j>=0 ;j--)
{
if(i == row -1)
{
if(j == column-1) dp[i][j] = dungeon[i][j] > 0 ? 1 : (1 - dungeon[i][j]);
else
{
int tmp = dp[i][j+1] - dungeon[i][j];
dp[i][j] = tmp <= 0 ? 1 : tmp;
}
continue;
}
if(j == column -1)
{
int tmp = dp[i+1][j] - dungeon[i][j];
dp[i][j] = tmp <= 0 ? 1 : tmp;
continue;
}
int tmp1 = dp[i+1][j] - dungeon[i][j];
int tmp2 = dp[i][j+1] - dungeon[i][j];
dp[i][j] = min((tmp1 <= 0 ? 1 : tmp1),(tmp2 <= 0 ? 1 : tmp2));
}
}
return dp[0][0];
}
//1207 leetcode 173
//已经单独建类完成
//1208 leetcode 172
//实际上是算5的个数
int trailingZeroes(int n) {
if (n <= 2) return 0;
int res = 0;
for(int i =1;i<=n;i++)
{
if(i %5 != 0) continue;
res+=getIncludeFiveNUmber(i);
}
return res;
}
int getIncludeFiveNUmber(int n)
{
if(n < 5 || (n %5 != 0)) return 0;
return 1 + getIncludeFiveNUmber(n/5);
}
//1208 leetcode 171
int titleToNumber(string s) {
//26进制转10进制
int res = 0;
for(int i =0;i<s.size();i++)
{
cout<<"cur res is "<<res<<" cur s[i] is "<<s[i]<<endl;
res = res * 26 + (s[i] - 'A' + 1);
}
return res;
}
//1208 leetcode 169
int majorityElement(vector<int>& nums) {
if(nums.size() == 0) return 0;
unordered_map<int,int> unmapNumbers;
int res = 0;
for(int i =0;i<nums.size();i++)
{
if(unmapNumbers.find(nums[i]) == unmapNumbers.end())
{
unmapNumbers[nums[i]] = 1;
}
else
{
unmapNumbers[nums[i]]++;
}
}
for(auto it = unmapNumbers.begin();it != unmapNumbers.end();it++)
{
if(it->second > nums.size()/2) res = it->first;
}
return res;
}
//1208 leetcode 168
string convertToTitle(int n) {
if(n <= 0) return "";
string res = "";
vector<int> nums;
if(n <= 26)
{
res.push_back('A' + (n-1));
return res;
}
while(n > 26)
{
int tmp = n % 26;
n = n/26;
if(tmp == 0)
{
tmp = 26;
n = n-1;
}
nums.push_back(tmp);
}
if(n > 0) nums.push_back(n);
std::reverse(nums.begin(),nums.end());
for(int i =0;i<nums.size();i++)
{
int tmp = nums[i];
res.push_back('A' + (nums[i]-1));
}
return res;
}
//1208 leetcode 167
vector<int> twoSum(vector<int>& numbers, int target) {
int len = numbers.size();
int i = 0;
int j = len -1;
vector<int> res;
if(len == 0) return res;
while(i < j && numbers[i] + numbers[j] != target)
{
if(numbers[i] + numbers[j] == target)
{
break;
}
else if(numbers[i] + numbers[j] < target)
{
i++;
}
else
{
j--;
}
}
res.push_back(i+1);
res.push_back(j+1);
return res;
}
//1209 leetcode 166
string fractionToDecimal(int numerator, int denominator) {
//这个暂时先不做了。后续看下
}
//1209 leetcode 165
int compareVersion(string version1, string version2)
{
int i = 0 ,j = 0;
while(i < version1.size() || j < version2.size())
{
int a = 0, b = 0;
while(i < version1.size() && version1[i] != '.') a = a * 10 + version1[i++] - '0';
while(j < version2.size() && version2[j] != '.') b = b * 10 + version2[j++] - '0';
if (a > b) return 1;
else if (a < b) return -1;
i++;
j++;
}
return 0;
}
//1211 leetcode 164
int maximumGap(vector<int>& nums) {
//后续优化下时间复杂度
if(nums.size() < 2) return 0;
std::sort(nums.begin(),nums.end());
int res = nums[1] - nums[0];
for(int i=0;i<nums.size()-1;i++)
{
res = max(res,(nums[i+1] - nums[i]));
}
return res;
}
//1211 leetcode 162
int findPeakElement(vector<int>& nums) {
if(nums.size() < 2) return 0;
if(nums.size() == 2)
{
if(nums[1] > nums[0]) return 1;
else return 0;
}
int res = 0;
int i = 0;
for(i=0;i<nums.size()-2;i++)
{
if(nums[i+1] > nums[i] && nums[i+1] > nums[i+2])
{
res = i+1;
break;
}
}
//cout<<"cur i is "<<i<<endl;
if(i == nums.size()-2)
{
if(nums[nums.size()-1] > nums[nums.size()-2] && nums[nums.size()-2] > nums[nums.size() -3])
return nums.size()-1;
}
return res;
}
//1211 leetcode 160
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) {
return NULL;
}
ListNode *you = headA, *she = headB;
while (you != she) { // 若是有缘，你们早晚会相遇
you = you ? you->next : headB; // 当你走到终点时，开始走她走过的路
she = she ? she->next : headA; // 当她走到终点时，开始走你走过的路
}
// 如果你们喜欢彼此，请携手一起走完剩下的旅程（将下面这个 while 块取消注释）。
// 一路上，时而你踩着她的影子，时而她踩着你的影子。渐渐地，你变成了她，她也变
// 成了你。
/* while (she) {
you = she->next;
she = you->next;
} */
return you;
}
void travelListNode(ListNode* root)
{
if(root == NULL) return;
cout<<"cur val is "<<root->val<<endl;
travelListNode(root->next);
}
//1211 leetcode 155
//已经单独建类完成
};
int main()
{
Solution solution;
time_t now_time = time(NULL);
tm* thisLocalTime = localtime(&now_time);
cout<<endl;
cout<<asctime(thisLocalTime)<<endl;
system("pause");
return 0;
} 
京公网安备 11010502036488号