[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......

[LeetCode C++实现]1636. Sort Array by Increasing Frequency

无脑使用unordered_map来保存数字出现次数,然后按照出现次数排序,如果出现次数相等,则数值大的排在前面。

class Solution {

public:

vector<int> frequencySort(vector<int>& nums) {

unordered_map<int,int> cnt;

for(auto num:nums){

cnt[num]++;

}

sort(nums.begin(),nums.end(),[&](int a,int b){

return cnt[a] == cnt[b] ? a>......

[LeetCode C++实现]25. Reverse Nodes in k-Group

非常经典的链表逆序题目:

/**

* 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......

[LeetCode C++实现]47. Permutations II

class Solution {

public:

vector<vector<int>> permuteUnique(vector<int>& nums) {

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

vector<vector<int>> res;

permuteUnique(nums,0,res);

return res;

}

private:

void permuteUnique(vector<int> nums,int begin,vector<vector<int>......

[LeetCode C++实现]59. Spiral Matrix II

class Solution {

public:

vector<vector<int>> generateMatrix(int n) {

vector<vector<int>> ans(n,vector<int>(n,0));

int num = 1;

//设定访问边界

int up = 0,down = n-1,left = 0,right = n -1;

while(true)

{

//从左向右访问

for(int i = left;i <= right;i++)

ans[up][i] = num++;

if(++up &......

[LeetCode C++实现]54.Spiral Matrix

class Solution {

public:

vector<int> spiralOrder(vector<vector<int>>& matrix) {

int m = matrix.size(),n = matrix[0].size();

vector<int> ans;

//设定访问边界

int up = 0,down = m -1,left = 0,right = n -1;

while(true)

{

//从左向右访问

for(int i = left;i <= right;i++)

ans.push_back(ma......

[LeetCode C++实现]103. Binary Tree Zigzag Level Order Traversal

最开始使用BFS代码如下:

/**

* 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) {}

* TreeNode(int x, TreeNode *left,......

[LeetCode C++实现]415. Add Strings

首先使用最直观 最ugly的代码AC,根据失败的case,AC的代码如下:

class Solution {

public:

string addStrings(string num1, string num2) {

int m = num1.size(),n = num2.size();

int carry = 0;

string res;

while(m > 0 && n > 0)

{

int num = num1[m-1]-'0'+num2[n-1]-'0'+carry;

carry = 0;

if(num >= 10)

{

carry = 1;......

[LeetCode C++实现]42. Trapping Rain Water

大名鼎鼎的一道题,看讨论区居然有5 6种解法,令人尴尬的是我一种都没AC,看了大神的解题思路,自己较轻松的完成了代码。

暴力破解

暴力破解方法是后续所有解法的基础,如果理解不了暴力破解解法,那么后续所有解法将无法理解。

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation: Th......

[LeetCode C++实现]1. Two Sum

鼎鼎大名的第一道题,最直观的n平方复杂度解法:

class Solution {

public:

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

for(int i = 0;i < nums.size();i++)

{

for(int j = i+1;j < nums.size();j++)

{

if(nums[i] + nums[j] == target)

return {i,j};

}

}

return {-1,-1};

}

};

优化后的解法:

class Soluti......