leetcode部分题目（C++）

r囧r小猫 2022-09-24 12:20 180阅读 0赞

## 2016.3.19 ##

### 88. Merge Sorted Array（从尾到头） ###

[MySubmissions][]

Question

TotalAccepted: **92780**Total Submissions: **310153**Difficulty: **Easy**

Given two sorted integer arrays *nums1* and *nums2*,merge *nums2* into *nums1* as one sorted array.

**Note:**  
You may assume that *nums1* has enough space (size that isgreater or equal to *m* \+ *n*) to hold additionalelements from *nums2*. The number of elements initialized in *nums1*and *nums2* are *m* and *n* respectively.

[Subscribe][] to see which companies asked this question

class Solution \{

public:

void merge(vector<int>& nums1, int m, vector<int>&nums2, int n) \{

if(nums1.empty()) //哈哈，改了两次可以了

if(nums2.empty())return;

for(int k=0;k<n;k++)

nums1\[k\]=nums2\[k\];

if(!nums1.empty()&&nums2.empty())return;

int i;

int x=m-1;

int y=n-1;

for(i=m+n-1;i>=0;i--)

if(nums1\[x\]>nums2\[y\])

nums1\[i\]=nums1\[x\];

x--;

else

nums1\[i\]=nums2\[y\];

y--;

if(x==-1) //主要改了这，还有下面的if，因为需要考虑到，遍历到某个列表开头没有节点的情况

for(int p=0;p<=y;p++)

nums1\[p\]=nums2\[p\];

break;

if(y==-1)

break;

\};

### 111.Minimum Depth of Binary Tree（BFS） ###

TotalAccepted: **98605**Total Submissions: **324359**Difficulty: **Easy**

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along theshortest path from the root node down to the nearest leaf node.

class Solution \{

public:

int minDepth(TreeNode \*root) \{

if (root == NULL)

return 0;

if (root->left == NULL)

return minDepth(root->right) + 1;

else if (root->right ==NULL)

return minDepth(root->left) + 1;

else

return min(minDepth(root->left), minDepth(root->right)) + 1;

\};

### 219. Contains Duplicate II （先判断k个，在判n-k个） ###

Total Accepted:**50318**Total Submissions:**170599**Difficulty:**Easy**

Givenan array of integers and an integer *k*,find out whether there are two distinct indices *i* and *j* in the array such that **nums\[i\] = nums\[j\]** and the difference between *i* and *j*isat most *k*.

class Solution \{

public:

bool containsNearbyDuplicate(vector<int>& nums, int k) \{

if(nums.empty()) return false;

int size=nums.size();

map<int,int> m;

int i;

for( i=0;i<k+1;i++) //先判断前k个，

if(m\[nums\[i\]\]==1)return true;

else m\[nums\[i\]\]=1;

if(i==size-1)break;

if(i==size-1)return false;

m\[nums\[0\]\]=0;

for(int j=i;j<size;j++) //然后判断n-k个

if(m\[nums\[j\]\]==1)return true;

else m\[nums\[j\]\]=1;

// if(i==size-1)break;

m\[nums\[j-k\]\]=0; // 额，开始时候，j-k-1,有问题，改了之后可以了，复杂度n，还不错。。。。

return false;

\};

### 263. Ugly Number（除尽） ###

[MySubmissions][MySubmissions 1]

Question

Total Accepted:**47733**Total Submissions:**132069**Difficulty:**Easy**

Writea program to check whether a given number is an ugly number.

Uglynumbers are positive numbers whose prime factors only include `2,3, 5`. For example, `6,8`are ugly while `14`is not ugly since it includesanother prime factor `7`.

Notethat `1`is typically treated as an uglynumber.

class Solution \{

public:

bool isUgly(int num) \{

if(num<=0)return false;

while(num%2==0)

num=num>>1;

while(num%3==0)

num /= 3;

while(num%5==0)

num /= 5;

if(num==1)return true;

else return false;

\};

### 223. Rectangle Area（重合坐标） ###

TotalAccepted: **32685**Total Submissions: **111070**Difficulty: **Easy**

Find the total area covered by two **rectilinear** rectanglesin a **2D** plane.

Each rectangle is defined by its bottom left corner andtop right corner as shown in the figure.

Assume that the total area is never beyond the maximumpossible value of **int**.

**Credits:**  
Special thanks to [@mithmatt][mithmatt] for adding this problem, creating the above imageand all test cases.

[Subscribe][] to see which companies asked this question

class Solution \{

public:

int computeArea(int A, int B, int C, int D, int E, int F, int G, int H)\{ //开始时候想分1个点交叉，2个点交叉//...4个点交叉讨论，发现不行，后来查到下面这个方法

int area= (C-A)\*(D-B)+(G-E)\*(H-F);

if (E > C || G < A || F > D || H < B)

return area;

int overLapArea=0;

int h1 = max(A, E); //先计算重合的横坐标

int h2 = min(C, G);

int h = h2 - h1;

int v1 = max(B, F); //计算重合的纵坐标

int v2 = min(D, H);

int v = v2 - v1;

overLapArea=h\*v;

area -= overLapArea;

return area;

\};

### 190. Reverse Bits （1<<i） ###

[MySubmissions][MySubmissions 2]

Question

TotalAccepted: **56594**Total Submissions: **194167**Difficulty: **Easy**

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binaryas **00000010100101000001111010011100**), return 964176192 (representedin binary as**00111001011110000010100101000000**).

**Follow up**:  
If this function is called many times, how would you optimize it?

Related problem: [Reverse Integer][]

**Credits:**  
Special thanks to [@ts][ts] for adding this problem and creating all testcases.

[Subscribe][] to see which companies asked this question

//其实可以使用数组做，不过想到空间利用率，还是直接位操作比较好

class Solution \{

public:

uint32\_t reverseBits(uint32\_t n) \{ //哈哈，一次通过，如果原数第i位是1，则第31-i位置是1

uint32\_t temp;

for(int i=0;i<32;i++)

if((1<<i)&n)

temp += 1<<(31-i);

return temp;

\};

### 20. Valid Parentheses（见到(\[\{ ，就入栈） ###

[My Submissions][]

Question

Total Accepted:**99325**Total Submissions:**342842**Difficulty:**Easy**

Given a string containingjust the characters `'('`, `')'`, `'{'`, `'}'`, `'['`and `']'`, determine if the input string is valid.

The brackets must close inthe correct order, `"()"`and `"()[]{}"`are all valid but `"(]"`and `"([)]"`are not.

[Subscribe][]to see which companies asked this question

class Solution \{

public:

bool isValid(string s) \{

stack<char> stk;

int size=(int)s.length();

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

if((s\[i\]=='(')||(s\[i\]=='\[')||(s\[i\]=='\{'))

stk.push(s\[i\]);

else

if(stk.empty())return false;

char temp=stk.top();

if((temp=='('&&s\[i\]==')')||(temp=='\['&&s\[i\]=='\]')||(temp=='\{'&&s\[i\]=='\}'))

//if((temp=='('&&s\[i\]==')')||(temp=='\['||s\[i\]=='\]')||(temp=='\{'&&s\[i\]=='\}'))

//尼玛，这个小马虎的错找了半个小时！！！！气死了

stk.pop();

else

return false;

if(stk.empty())

return true;

else

return false;

\};

### 58. Length of Last Word（从尾到头） ###

[My Submissions][My Submissions 1]

Question

Total Accepted:**86714**Total Submissions:**299284**Difficulty:**Easy**

Given a string *s* consists of upper/lower-case alphabetsand empty space characters `' '`, return the length of lastword in the string.

If the last word does notexist, return 0.

**Note:**A word is defined as a character sequence consists of non-spacecharacters only.

For example,   
Given *s* = `"Hello World"`,  
return `5`.

[Subscribe][]to see which companies asked this question

//我知道可以用循环到最后做（比如统计空格数，然后再数到空格位置，再数长度，很复杂，因此直接不用）

//我想到了倒着做的方法会更好

class Solution \{

public:

int lengthOfLastWord(string s) \{ //哈哈哈，一次通过！！

if(s.empty())return 0;

string temp;

int size=s.size();

int count=0;

int flagConsistSpace=1;

for(int i=size-1; i>=0;i--)

if(s\[i\]==' '&&flagConsistSpace) continue;

if(s\[i\]!=' ')flagConsistSpace=0;

if(!flagConsistSpace&&s\[i\]==' ')

break;

count++;

return count;

\};

### 205. Isomorphic Strings（map对应及判断出现过） ###

[My Submissions][My Submissions 2]

Question

TotalAccepted: **50240**Total Submissions: **173192**Difficulty: **Easy**

Given two strings ***s*** and ***t***,determine if they are isomorphic.

Two strings are isomorphic if the characters in ***s*** canbe replaced to get ***t***.

All occurrences of a character must be replaced with another characterwhile preserving the order of characters. No two characters may map to the samecharacter but a character may map to itself.

For example,  
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

**Note:**  
You may assume both ***s*** and ***t*** havethe same length.

class Solution \{

public:

bool isIsomorphic(string s, string t) \{

if(s.empty()&&t.empty())return true;

int Ssize=s.size();

int Tsize=t.size();

if(Ssize!=Tsize)return false;

int i;

int j;

map<char,char> m;

map<char,int> show;//表明已经有s种的元素指向该元素，重复指向则返回错

for(i=0;i<Ssize;i++)\{

map<char,char>::iteratorit;//注意别忘了冒号

it=m.find(s\[i\]);

if(it==m.end())

if(show\[t\[i\]\]==1)returnfalse;//此处改了改，表明不能让两个及以上的s\[i\]指向相同的s\[j\]

m\[s\[i\]\]=t\[i\];

show\[t\[i\]\]=1;

else if(m\[s\[i\]\]!=t\[i\])returnfalse;//同样元素对应到不同的值，也错

else continue;

return true;

\};

## 2016.3.20 ##

### 299. Bulls and Cows（数组记录次数） ###

[My Submissions][My Submissions 3]

Question

Total Accepted:**22552**Total Submissions:**77861**Difficulty:**Easy**

For example:

Secret number:  "1807"

Friend's guess: "7810"

Hint: `1`bull and `3`cows. (The bull is `8`, the cows are `0`, `1`and `7`.)

Please note that bothsecret number and friend's guess may contain duplicate digits, for example:

Secret number:  "1123"

Friend's guess: "0111"

In this case, the 1st `1`in friend's guess isa bull, the 2nd or 3rd `1`is a cow, and yourfunction should return `"1A1B"`.

You may assume that thesecret number and your friend's guess only contain digits, and their lengthsare always equal.

**Credits:**  
Special thanks to [@jeantimex][jeantimex]for adding this problem and creating all test cases.

[Subscribe][]to see which companies asked this question

class Solution \{

public:

string getHint(string secret, string guess) \{

string ret;

if(secret.empty()||guess.empty())return ret; //哈哈，就改了一次，就ac了

int size=secret.size();

int AshowTimes\[10\]=\{0\};

int BshowTimes\[10\]=\{0\};

int A=0;

int B=0;

int i;

for(i=0;i<size;i++)

if(secret\[i\]==guess\[i\]) A++;

else

AshowTimes\[secret\[i\]-'0'\]++;

BshowTimes\[guess\[i\]-'0'\]++;

for(i=0;i<10;i++)

if(BshowTimes\[i\]>AshowTimes\[i\])B +=AshowTimes\[i\];

else B+=BshowTimes\[i\];

stringstream ss;

ss<<A;

ret=ss.str();

ret += 'A';

ss.str("");//一定要清空，不然默认在尾部继续添加

ss<<B;

ret += ss.str();

ret+='B';

return ret;

/\*

char buff\[20\];

sprintf(buff, "%dA%dB", bulls, cows);//网上另一种输出的办法

return buff;

\*/

\};

### 19. Remove Nth Node From End ofList（fast指针先走n步，删倒数第n个） ###

[MySubmissions][MySubmissions 3]

Question

Total Accepted:**100054**Total Submissions:**344561**Difficulty:**Easy**

Givena linked list, remove the *n*thnode from the end of list andreturn its head.

Forexample,

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

**Note:**  
Given *n* will always be valid.  
Try to do this in one pass.

[Subscribe][]to see which companies asked thisquestion

/\*\*

\*Definition for singly-linked list.

\*struct ListNode \{

\* int val;

\* ListNode \*next;

\* ListNode(int x) : val(x), next(NULL) \{\}

\* \};

\*/

class Solution \{

public:

ListNode\* removeNthFromEnd(ListNode\* head, int n) \{

if(!head)return NULL;

int size=0;

ListNode \*p=head;

while(p)

size++;

p=p->next;

if(n>size||n<=0)return head;

int deleteNum=size-n;

if(deleteNum==0)head=head->next; //改了一下这，就ac，必须考虑如果想删除的是第一个节点的情况，因为要返回head

else\{

p=head;

int i;

ListNode \*pre =new ListNode(0);

pre->next=head;

for(i=0;i<deleteNum;i++)

pre=pre->next;

p=p->next;

pre->next=p->next;

delete p;

return head;

/\*

l另外一种思路是用两个指针 fast 和slow。 fast先走n 步,slow这时候从头开始走，当fast走到尾的时候slow就走到需要跳过的位置了。

这样只需要走一遍就可以了。

\*/

\};

[MySubmissions]: https://leetcode.com/problems/merge-sorted-array/submissions/
[Subscribe]: https://leetcode.com/subscribe/
[MySubmissions 1]: https://leetcode.com/problems/ugly-number/submissions/
[mithmatt]: https://leetcode.com/discuss/user/mithmatt
[MySubmissions 2]: https://leetcode.com/problems/reverse-bits/submissions/
[Reverse Integer]: https://leetcode.com/problems/reverse-integer/
[ts]: https://oj.leetcode.com/discuss/user/ts
[My Submissions]: https://leetcode.com/problems/valid-parentheses/submissions/
[My Submissions 1]: https://leetcode.com/problems/length-of-last-word/submissions/
[My Submissions 2]: https://leetcode.com/problems/isomorphic-strings/submissions/
[My Submissions 3]: https://leetcode.com/problems/bulls-and-cows/submissions/
[Bulls and Cows]: https://en.wikipedia.org/wiki/Bulls_and_Cows
[jeantimex]: https://leetcode.com/discuss/user/jeantimex
[MySubmissions 3]: https://leetcode.com/problems/remove-nth-node-from-end-of-list/submissions/