当前位置：网站首页>Leetcode brush questions
Leetcode brush questions
2022-07-08 00:20:00 【Seventeen 47】
LeetCode Brush problem
- 0 Some feeling
- 1、 Array
- The container with the most water
- Sum of three numbers
- Sum of two numbers
- Array find duplicate values （ Ergodic problem ）
- Adjust the array order so that the odd Numbers precede the even Numbers
- Print matrix clockwise
- A number that appears more than half the times in an array
- The smallest k Number
- The maximum sum of successive subarrays
- 2、 character string （ Questions about characters , Often use ASCII Code is the fastest ）
- 3、 Linked list
- Delete the last of the linked list N Nodes
- Addition of two numbers
- Print linked list from end to end （ Stack 、 recursive ）
- Except for the nodes in the linked list
- The penultimate in the output list k Nodes
- Reverse a linked list
- Merge two ordered linked lists
- The first common node of two linked lists
- 4、 Stack 、 queue
- 5、 recursive 、 loop 、 Dynamic programming
- 6、 Search and sort
- 7、 An operation
0 Some feeling
0.1 The advantages and disadvantages of arrays and linked lists
1、 Array
The container with the most water
subject ：HOT100 11
Answer key 1： double for Loop traversal , Overtime
class Solution {
public:
int maxArea(vector<int>& height) {
int i=0,j=0,Max=0,cur=0;
int len=height.size();
for(i=0;i<len-1;i++){
for(j=i+1;j<len;j++){
cur=min(height[i],height[j])*(j-i);
Max=max(Max,cur);
}
}
return Max;
}
};
Answer key 2： Double pointer , From both sides to the middle , Every time the number is small, the person moves
class Solution {
public:
int maxArea(vector<int>& height) {
int head=0,MAX=0,cur=0;
int tail=height.size()-1;
while(head!=tail){
cur=min(height[head],height[tail])*(tail-head);
MAX=max(cur,MAX);
if(height[head]<height[tail])
head++;
else if(height[head]>height[tail])
tail--;
else
head++;
}
return MAX;
}
};
Sum of three numbers
subject ：HOT100 15
Answer key 1： Sort , Optimized triple for loop , Be careful for In circulation continue and break Differences in usage
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
// enumeration a
for (int first = 0; first < n; ++first) {
// It needs to be different from the last enumeration
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c The corresponding pointer initially points to the rightmost end of the array
int third = n - 1;
int target = -nums[first];
// enumeration b
for (int second = first + 1; second < n; ++second) {
// It needs to be different from the last enumeration
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// Need assurance b The pointer is in c On the left side of the pointer
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// If the pointers coincide , With b Subsequent additions
// There will be no satisfaction a+b+c=0 also b<c Of c 了 , You can exit the loop
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
ans.push_back({
nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
};
Sum of two numbers
subject ：HOT100 01
Answer key 1： double for Loop traversal
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i,j,n=nums.size();
for (i = 0; i < n - 1; i++)
{
for (j = i + 1; j < n; j++)
{
if (nums[i] + nums[j] == target)
{
return {
i,j};
}
}
}
return {
i,j};
};
};
Answer key 2： Hash
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {
it->second, i};
}
hashtable[nums[i]] = i;
}
return {
};
}
};
Array find duplicate values （ Ergodic problem ）
subject ： The finger of the sword Offer 03. Repeated numbers in an array
Answer key 1：
int findRepeatNumber(int* nums, int numsSize){
int i,j;
for(i=0;i<numsSize;i++)
{
for(j=1;j<numsSize-i;j++)
{
if(*(nums+i)==*(nums+i+j))
return *(nums+i);
}
}
return -1;
}
Running results ： Overtime
analysis ： Double loop traversal to find peers , Too time-consuming . When input is small, it can operate correctly , More will take a lot of time .
Adjust the array order so that the odd Numbers precede the even Numbers
subject ： The finger of the sword Offer 21
Answer key 1： Do it on your own , Single subscript traverses the array once from right , The efficiency is not high
int* exchange(int* nums, int numsSize, int* returnSize){
int * ret=(int*)malloc(sizeof(int)*numsSize);
*returnSize=numsSize;
int i=0,j=0,k=1;
for(i=0;i<numsSize;i++)
{
if(nums[i]%2==1)
{
ret[j]=nums[i];
j++;
}
else
{
ret[numsSize-k]= nums[i];
k++;
}
}
return ret;
}
Answer key 2： Double subscript , Traverse the array once from both sides to the middle , Efficiency ratio solution 1 higher , recommend
int* exchange(int* nums, int numsSize, int* returnSize){
int low=0,high=numsSize-1,t;
while(low<high)
{
if(nums[low]%2==0&&nums[high]%2==1)
{
t=nums[low];
nums[low]=nums[high];
nums[high]=t;
}
if(nums[low]%2==1)
low++;
if(nums[high]%2==0)
high--;
}
*returnSize=numsSize;
return nums;
}
Print matrix clockwise
subject ： The finger of the sword Offer 29
Answer key 1：
A number that appears more than half the times in an array
subject ： The finger of the sword Offer 39
Answer key 1： Bubble sort , Take the middle number , Time 5, Space 42
int majorityElement(int* nums, int numsSize){
int i=0,j=0,flag=1,temp=0;
for(i=0;i<numsSize&&flag;i++)
{
flag=0;
for(j=numsSize-1;j>i;j--)
{
if(nums[j-1]>nums[j])
{
temp=nums[j];
nums[j]=nums[j-1];
nums[j-1]=temp;
flag=1;
}
}
}
return nums[numsSize/2];
}
Answer key 2： Eliminate counting , Take the middle number , Time 92, Space 97
int majorityElement(int* nums, int numsSize){
int temp = 0,count = 0; //count Count ,temp Store value
for(int i=0; i<numsSize; i++){
if(count == 0){
// All are eliminated or the first value
temp = nums[i];
count++;
}else if(temp == nums[i]){
// Whether the judgment value is the same
count++; // Same plus one , In order to spend more next time
}else
count--; // Different minus one , Go back together
}
return temp;
}
The smallest k Number
subject ： The finger of the sword Offer 40
Answer key 1： call qsort, Before removal k individual , Time 64, Space 25
int cmp(void const *a,void const *b){
if(*(int*)a>*(int*)b)
return 1;
else if(*(int*)a<*(int*)b)
return -1;
else
return 0;
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
qsort(arr, arrSize,sizeof(int),cmp);
*returnSize=k;
int *ret=(int*)malloc(sizeof(int)*k);
for(int i=0;i<k;i++){
ret[i]=arr[i];
}
return ret;
}
The maximum sum of successive subarrays
subject ： The finger of the sword Offer 42, Time required O(n)
Answer key 1：
2、 character string （ Questions about characters , Often use ASCII Code is the fastest ）
Longest text substring
subject ：HOT 100 5
Answer key 1：
The longest substring without repetition
subject ：HOT 100 3
Answer key 1： Independent solution , Double loop plus hash , adopt , Time and space are only more than percent 5
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> hashtable;
int i=0,j=0,cnt=0,max=0;
int len=s.size();
for(i=0;i<len;i++){
for(j=i;j<len;j++){
auto it=hashtable.find(s[j]);
if(it==hashtable.end()){
hashtable[s[j]] = j;
cnt++;
}
else
break;
}
hashtable.clear();
if(cnt>=max)
max=cnt;
cnt=0;
}
return max;
}
};
Answer key 2： The sliding window + Hash set unordered_set, Look at the official solution , Learn about sliding windows and hash sets
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0;
unordered_set<char> lookup;
int maxStr = 0;
int left = 0;
for(int i = 0; i < s.size(); i++){
while (lookup.find(s[i]) != lookup.end()){
lookup.erase(s[left]);
left ++;
}
maxStr = max(maxStr,i-left+1);
lookup.insert(s[i]);
}
return maxStr;
}
};
Answer key 3： utilize ASCII code , Time 100%
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> m(128,0);// This container is for storing when it encounters the same characters ( The assumption is a) when i The value that should become , The one in front a The next character of
int ans=0; // The final substring length
int i=0;
for(int j=0;j<s.size();j++){
i=max(i,m[s[j]]);// If you encounter the same character ( Assuming that a), here m[s[j]] Will go to the same storage unit again m[a Of ASCII Code value ], Because I met a The value of this position has been changed to the previous one a Next position for , therefore m[s[j]] Greater than i, take i to update
m[s[j]]=j+1;// Update the value of this location , The next time you encounter this letter , take i Adjust to the next position of the letter
ans=max(ans,j-i+1);// Update the final result value , That is, the number of characters in the substring without the same letter
}
return ans;
}
};
Replace spaces in the string （ Array expansion problem ）
subject ： The finger of the sword Offer 05. Replace blank space
Answer key 1：
char * replaceSpace(char* s)
{
char * p1=s;
char * p2=s;
int space_cnt=0;
while(*p1)
{
if(*p1==' ')
space_cnt+=1;
++p1;
}
p2=p1+2*space_cnt;
while(space_cnt>0)
{
if (*p1!=' ')
{
*p2=*p1; // Debugging error ： Write permission conflict
--p1;
--p2;
}
else
{
*(p2)='0';
*(--p2)='2';
*(--p2)='%';
--p1;
--p2;
space_cnt-=1;
}
}
return s;
}
Running results ： Debugging error ： Write permission conflict
analysis ： No official answer has been found , The following is self analysis . Passing in functions replaceSpace Parameters of char *s Is a pointer to a string constant , String constants are stored in the text constant area , Is a constant , It cannot be assigned .
Answer key 2： Pure pointer operation string （ A little bit of a problem , It's easy to make mistakes , Not recommended ）
char* replaceSpace(char* s)
{
char* p1 = s;
int space_cnt = 0;
while (*p1)
{
if (*p1 == ' ')
space_cnt += 1;
++p1;
}
int new_len = strlen(s) + 2 * space_cnt + 1;
char* new_string = (char*)malloc(sizeof(char) * new_len);
while (*s)
{
if (*s != ' ')
{
*new_string = *s;
++s;
++new_string;
}
else
{
*(new_string) = '%';
*(++new_string) = '2';
*(++new_string) = '0';
++s;
++new_string;
}
}
*new_string = '\0';
return (new_string - new_len+1);
}
Answer key 3： Array subscript operation string （ recommend ）
char* replaceSpace(char* s)
{
char* p1 = s;
int space_cnt = 0;
while (*p1)
{
if (*p1 == ' ')
space_cnt += 1;
++p1;
}
int new_len = strlen(s) + 2 * space_cnt + 1;
char* new_string = (char*)malloc(sizeof(char) * new_len);
int i = 0, j = 0;
while (s[i])
{
if (s[i] != ' ')
{
new_string[j] = s[i];
++i;
++j;
}
else
{
new_string[j] = '%';
new_string[++j] = '2';
new_string[++j] = '0';
++i;
++j;
}
}
new_string[j] = '\0';
return new_string;
Characters that appear only once at the first time
subject ： The finger of the sword Offer 50
Answer key 1： C Language , two for Loop traversal
char firstUniqChar(char* s){
int i, j, length;
length = strlen(s);
for(i = 0; i < length; i++){
int flag = 1;
for(j = 0; j < length; j++){
if(s[i] == s[j]&&i != j){
flag = 0;
break;
}
}
if(flag)
return s[i];
}
return ' ';
}
Answer key 2： C Language , two for Loop traversal , Using the idea of character dictionary , Answer key 1 Only the first one can be found , Answer key 2 Can find all .
char firstUniqChar(char* s){
int i,hash[26]={
0};
int len=strlen(s);// Be careful not to strlen(s) Put it in for Inside the loop , Write i<strlen(s), It's going to be slow .
for(i=0;i<len;i++){
hash[s[i]-'a']++;
}
for(i=0;i<strlen(s);i++){
if(hash[s[i]-'a']==1)
return s[i];
}
return ' ';
}
Answer key 3： Hash ,C++
3、 Linked list
Delete the last of the linked list N Nodes
subject ： HOT 100 19
Answer key 1： Do it on your own , two , First traverse to get the length , And find len-N Nodes , Pay attention to the judgment of some special situations
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* p1=head;
int len=0,cnt=0;
while(p1)
{
p1=p1->next;
len++;
}
if(len==1)
return nullptr;
if(len==2&&n==1)
{
head->next=nullptr;
return head;
}
else if(n==len)
return head->next;
p1=head;
while(cnt<len-n-1)
{
p1=p1->next;
cnt++;
}
p1->next=p1->next->next;
return head;
}
};
Answer key 2： Stack , Be careful C++ How to use stack
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);// Create a dummy node
stack<ListNode*> stk;// Create a repository ListNode* The stack
ListNode* cur = dummy;
while (cur) // Push all nodes, including dummy nodes, onto the stack
{
stk.push(cur);
cur = cur->next;
}
for (int i = 0; i < n; ++i) // After ejecting n Nodes , Be careful C++ in POP The operation does not return a value
{
stk.pop();
}
ListNode* prev = stk.top();
prev->next = prev->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
Answer key 3： Front and rear double pointers
/** * 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* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);// Create a dummy node
ListNode* fast=dummy; ListNode* slow=dummy;
int cnt=0;
while(fast->next){
if(cnt<n){
fast=fast->next;
cnt++;
}
else{
fast=fast->next;
slow=slow->next;
cnt++;
}
}
slow->next=slow->next->next;
return dummy->next;
}
};
Addition of two numbers
subject ： HOT 100 2
Answer key 1： Add... One by one , Remember to carry .
/** * 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, *tail = nullptr;// The head and tail pointers of the linked list used to store the results
int carry = 0;// Store the number of carry
while (l1 || l2) {
int n1 = l1 ? l1->val: 0;
int n2 = l2 ? l2->val: 0;
int sum = n1 + n2 + carry;
if (!head) {
head = tail = new ListNode(sum % 10);
} else {
tail->next = new ListNode(sum % 10);
tail = tail->next;
}
carry = sum / 10;
if (l1) {
l1 = l1->next;
}
if (l2) {
l2 = l2->next;
}
}
if (carry > 0) {
tail->next = new ListNode(carry);
}
return head;
}
};
Print linked list from end to end （ Stack 、 recursive ）
subject ： The finger of the sword Offer 06. Print linked list from end to end
Answer key 1： Traverse the linked list twice . The length of the linked list for the first time , Create the corresponding length array ; Copy the linked list elements to the array from beginning to end for the second time ; Last invert array .
int* reversePrint(struct ListNode* head, int* returnSize){
int list_cnt=0;
struct ListNode* p1=head;
struct ListNode* p2=head;
while(p1)
{
p1=p1->next;
list_cnt++;
}
int *ans=(int *)malloc(sizeof(int)*list_cnt);
*returnSize = list_cnt;
int i=0;
while(p2)
{
ans[i++]=p2->val;
p2=p2->next;
}
int temp=0;
for (i=0;i<list_cnt/2;i++)
{
temp=ans[list_cnt-1-i];
ans[list_cnt-1-i]=ans[i];
ans[i]=temp;
}
return ans;
}
Except for the nodes in the linked list
subject ： The finger of the sword Offer 18 This deletion is different from the deletion on the big talk data structure , The big story is to delete the i The next node of a node , Here we find a node according to the value , Then delete the node （ To delete this node, you need to find the previous node of this node ）
Answer key 1： Write it by yourself , Double pointer , Double ergodic . Traverse the linked list for the first time to find the node corresponding to the value , Traverse the linked list for the second time to find the previous node , Finally delete , Delete the header node and handle it separately .
struct ListNode* deleteNode(struct ListNode* head, int val){
struct ListNode* p=head;
struct ListNode* q=head;
int i=0,j=0;
if(head->val==val)
{
head=head->next;
return head;
}
while(p&&(!(p->val==val)))
{
p=p->next;
i++;
}
while(q&&(j<(i-1)))
{
q=q->next;
j++;
}
q->next=p->next;
return head;
}
Answer key 2： Single pointer , One traverse
struct ListNode* deleteNode(struct ListNode* head, int val){
if(head->val == val) {
return head->next;
}
struct ListNode* pre = head;
while ((pre->next != NULL) && (pre->next->val != val)) {
// The node to be deleted was not found , Continue to traverse and find
pre = pre->next;
}
if(pre->next != NULL) {
// find
pre->next = pre->next->next;
}
return head;
}
Answer key 3： recursive
struct ListNode* deleteNode(struct ListNode* head, int val){
if(head->val == val) {
return head->next;
}
// The value after deleting the header node is val The node of , And hook the linked list after this operation behind the head node
head->next = deleteNode(head->next, val);
return head;
}
/* Or use the trinocular operator directly */
struct ListNode* deleteNode(struct ListNode* head, int val){
if(head == NULL) {
return NULL;
}
head->next = deleteNode(head->next, val);
return head->val == val ? head->next : head;
}
The penultimate in the output list k Nodes
subject ： The finger of the sword Offer 22
Answer key 1： Do it on your own , Speed pointer .
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
struct ListNode* fast=head;
struct ListNode* slow=head;
for(int i=0;i<k;i++)
{
fast=fast->next;
}
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
Reverse a linked list
subject ： The finger of the sword Offer 24
Answer key 1： Do it on your own , Stack method . Need to traverse twice , Need a stack , Space for time .
typedef struct{
int * stack;
int stack_top;
int stack_capacity;
}Stack;
Stack * stack_create(int capacity)
{
Stack *ret=(Stack *)malloc(sizeof(Stack));
ret->stack =(int *)malloc(sizeof(int)*capacity);
ret->stack_top=0;
ret->stack_capacity=capacity;
return ret;
}
void stack_push(Stack *obj, int value)
{
obj->stack[obj->stack_top++]=value;
}
int stack_pop(Stack *obj)
{
return obj->stack[--obj->stack_top];
}
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* p1=head;
struct ListNode* p2=head;
Stack * my_stack=stack_create(5000);
while(p1)
{
stack_push(my_stack,p1->val);
p1=p1->next;
}
while(p2)
{
p2->val=stack_pop(my_stack);
p2=p2->next;
}
return head;
}
Answer key 2： Double pointer , Reverse the order , You only need to traverse it once , No need for extra space .
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* next;
while (head) {
next= head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
Answer key 3： recursive , Don't know much about .
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
Answer key 4： Create an empty linked list , The first interpolation .
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* new = (struct ListNode*)malloc(sizeof(struct ListNode));
new->next=NULL;
while (head) {
struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
p->val=head->val;
p->next=new->next;
new->next=p;
head=head->next;
}
return new->next;
}
Merge two ordered linked lists
subject ： The finger of the sword Offer 25
Answer key 1： recursive
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if (l1 == NULL) {
return l2;
} else if (l2 == NULL) {
return l1;
} else if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
Answer key ： hypothesis l1 by 1-2-NULL,l2 by 2-3-4-NULL.
First call mergeTwoLists
The incoming parameter is ： 1-2-NULL,2-3-4-NULL, What is marked in black is the position indicated by the incoming pointer
Meet the third if, Second call mergeTwoLists
The incoming parameter is ：2-NULL,2-3-4-NULL
Meet the fourth if（ The last one else）, Third call mergeTwoLists
The incoming parameter is ：2-NULL,3-4-NULL
Meet the third if, The fourth call mergeTwoLists
The incoming parameter is ：NULL,3-4-NULL
Satisfy the first if, return 3-4-NULL, Return to the third call mergeTwoLists The next sentence of the sentence , return
Answer key 2： iteration , This method takes about the same time as recursion , It takes less space than recursion
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
struct ListNode head;
struct ListNode *p1=l1,*p2=l2,*p3=&head;
if((!l1)||(!l2))
return l1? l1:l2;
while(p1&&p2)
{
if(p1->val<p2->val)
{
p3->next=p1;
p1=p1->next;
}
else
{
p3->next=p2;
p2=p2->next;
}
p3=p3->next;
}
p3->next=p1?p1:p2;
return head.next;
}
Wrong solution ：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* head = new ListNode(-1);
ListNode* p1 = list1;
ListNode* p2 = list2;
ListNode* p3 = head;
while (p1 != nullptr && p2 != nullptr) {
if (p1->val > p2->val) {
p3 = p2;
p3 = p3->next;// here p3->next It was null, Such an assignment p3 Run away . You should use the correct method above
p2 = p2->next;
}
else {
p3 = p1;
p3 = p3->next;
p1 = p1->next;
}
}
p3 = p1 == nullptr ? p2 : p1;
return head;
}
};
The first common node of two linked lists
subject ： The finger of the sword Offer 52, Public node refers to the same storage location , Not the same value .
Answer key 1： Hash , Can't
Answer key 2： I thought of two linked lists, looking forward from the back , The first equal node is the public node , But because it is a one-way linked list , I have no idea , Read the explanation of the question , In fact, I have done reverse linked list before , First reverse the two linked lists, and it's over .
Answer key 3： Double pointer , The length of the two linked lists is different , But the length of the common part is the same .
4、 Stack 、 queue
Valid parenthesis
subject ：HOT 100 20
Answer key ： Stack .
class Solution {
public:
bool isValid(string s) {
stack<char>stk;
int i=0,len=s.size(),left=0,right=0;
if(len%2==1)
return false;
while(i<len){
if(s[i]=='('||(s[i]=='{'||(s[i]=='[')))
{
stk.push(s[i]);
left++;
}
else{
right++;
if(stk.empty())
return false;
else if(s[i]==')'&&stk.top()=='(')
stk.pop();
else if(s[i]=='}'&&stk.top()=='{')
stk.pop();
else if(s[i]==']'&&stk.top()=='[')
stk.pop();
else
return false;
}
i++;
}
if(left!=right)
return false;
return true;
}
};
Queues are implemented with two stacks
subject ： The finger of the sword Offer 09
Answer key ： Two stacks , One is responsible for queue insertion , One is responsible for deleting the queue .C Language has to write its own stack , A little bit of a problem ,C++ There are library functions that directly operate on the stack .
typedef struct{
int * stack;
int stack_top;
int stack_capacity;
}Stack;
Stack * stack_create(int capacity)
{
Stack *ret=(Stack *)malloc(sizeof(Stack));
ret->stack =(int *)malloc(sizeof(int)*capacity);
ret->stack_top=0;
ret->stack_capacity=capacity;
return ret;
}
void stack_push(Stack *obj, int value)
{
obj->stack[obj->stack_top++]=value;
}
void stack_pop(Stack *obj)
{
obj->stack_top--;
}
int stack_get_top(Stack *obj)
{
return obj->stack[obj->stack_top-1];
}
bool stack_empty(Stack* obj) {
return obj->stack_top == 0;
}
void stack_free(Stack *obj)
{
free(obj->stack);
}
typedef struct {
Stack* in_stack;
Stack* out_stack;
} CQueue;
CQueue* cQueueCreate() {
/* Create two stacks , One in and one out */
CQueue * ret=(CQueue *)malloc(sizeof(CQueue));
ret->in_stack=stack_create(10000);
ret->out_stack=stack_create(10000);
return ret;
}
void in2out(CQueue * obj){
while(!stack_empty(obj->in_stack)){
stack_push(obj->out_stack, stack_get_top(obj->in_stack));
stack_pop(obj->in_stack);
}
}
void cQueueAppendTail(CQueue* obj, int value) {
stack_push(obj->in_stack,value);
}
int cQueueDeleteHead(CQueue* obj) {
if(stack_empty(obj->out_stack)){
if(stack_empty(obj->in_stack))
return -1;
in2out(obj);
}
int x =stack_get_top(obj->out_stack);
stack_pop(obj->out_stack);
return x;
}
void cQueueFree(CQueue* obj) {
stack_free(obj->in_stack);
stack_free(obj->out_stack);
}
4.2 contain min Function of the stack
subject ： The finger of the sword Offer 30
Answer key ： Create an auxiliary stack to store the minimum
int min=0;
typedef struct {
int* stack;
int stack_top_high;
int stack_top_low;
int stack_capacity;
} MinStack;
MinStack* minStackCreate() {
MinStack* ret=(MinStack*)malloc(sizeof(MinStack));
ret->stack_capacity=40000;
ret->stack=(int*)malloc(sizeof(int)*ret->stack_capacity);
ret->stack_top_high=20000;
ret->stack_top_low=0;
return ret;
}
void minStackPush(MinStack* obj, int x) {
if(obj->stack_top_low==0)// Empty stack , Then the current value is the minimum
{
obj->stack[obj->stack_top_low++]=x;
obj->stack[obj->stack_top_high++]=x;
min=x;
}
else if(x<min)
{
obj->stack[obj->stack_top_low++]=x;
obj->stack[obj->stack_top_high++]=x;
min=x;
}
else
{
obj->stack[obj->stack_top_low++]=x;
obj->stack[obj->stack_top_high++]=min;
}
}
void minStackPop(MinStack* obj) {
if(obj->stack[obj->stack_top_low-1]==min)
min=obj->stack[obj->stack_top_high-2];
obj->stack_top_low--;
obj->stack_top_high--;
}
int minStackTop(MinStack* obj) {
return obj->stack[obj->stack_top_low-1];
}
int minStackMin(MinStack* obj) {
return obj->stack[obj->stack_top_high-1];
}
void minStackFree(MinStack* obj) {
free(obj);
}
5、 recursive 、 loop 、 Dynamic programming
5.1 Fibonacci sequence
subject ： The finger of the sword Offer 10-1
Answer key 1： Simple recursion , Overtime , This is not used in interviews or practical projects .
int fib(int n){
int mod=1000000007;
int ans=0;
if(n<2)
return n;
else
ans=(fib(n-1)+fib(n-2))%mod;
return ans;
}
Answer key 2： Optimal recursive , Save the intermediate quantity of repeated calculation with an array , Space for time , recommend
int cache[101] = {
0 };
int fib(int n) {
int mod = 1000000007;
int ans = 0;
if (!cache[n] == 0)
return cache[n];
if (n < 2)
return n;
else
ans = (fib(n - 1) + fib(n - 2)) % mod;
cache[n] = ans;
return ans;
}
Answer key 3： Bottom up dynamic planning , recommend
int fib(int n){
int mod=1000000007;
int a=0;
int b=1;
int ans=0;
if(n<2)
return n;
else
for (int i=2;i<=n;i++){
ans=(a+b)%mod;
a=b;
b=ans;
}
return ans;
}
6、 Search and sort
Minimum number of rotation array
subject ： The finger of the sword Offer 11
Answer key 1： Two points search
int minArray(int* numbers, int numbersSize) {
int low = 0;
int high = numbersSize - 1;
while (low < high) {
int pivot = low + (high - low) / 2;
if (numbers[pivot] < numbers[high]) {
high = pivot;
}
else if (numbers[pivot] > numbers[high]) {
low = pivot+1;
}
else {
high -= 1;
}
}
return numbers[low];
}
Search rotation sort array
subject ：HOT 100 33
Answer key 1： Two points search , The code looks at the official solution to find the first and last positions of elements in the sorted array
Find the first and last positions of the elements in the sort array
subject ：HOT 100 34
Answer key 1： Do it on your own , Two points search , This is the binary search standard code , remember , Be careful not to cross the data subscript
7、 An operation
7.1 Binary 1 The number of
subject ： The finger of the sword Offer 15
Answer key 1： Keep moving one bit to the right , Then with 1 Carry out bit and operation , How many bits and how many times , such as 32 Time
int hammingWeight(uint32_t n) {
int cnt=0;
int i=0;
for(i=0;i<32;i++){
if(n&1)
cnt++;
n=n>>1;
}
return cnt;
}
Answer key 2： The simple method in the book
int hammingWeight(uint32_t n) {
int cnt=0;
while(n)
{
n=n&(n-1);
cnt++;
}
return cnt;
}
边栏推荐
- QT creator add JSON based Wizard
- Tools for debugging makefiles - tool for debugging makefiles
- The function is really powerful!
- Relevant methods of sorting arrays in JS (if you want to understand arrays, it's enough to read this article)
- QT and OpenGL: loading 3D models using the open asset import library (assimp) - Part 2
- Robomaster visual tutorial (10) target prediction
- Su embedded training - Day3
- 测试流程不完善，又遇到不积极的开发怎么办？
- 1293_FreeRTOS中xTaskResumeAll()接口的实现分析
- Teach you to make a custom form label by hand
猜你喜欢
Introduction to programming hardware
![[programming problem] [scratch Level 2] March 2019 draw a square spiral](/img/fa/ae9dabdd36ba77b1f4644dd23bee93.png)
[programming problem] [scratch Level 2] March 2019 draw a square spiral
80% of the people answered incorrectly. Does the leaf on the apple logo face left or right?
第四期SFO销毁，Starfish OS如何对SFO价值赋能？
从服务器到云托管，到底经历了什么？
![[question de programmation] [scratch niveau 2] oiseaux volants en décembre 2019](/img/5e/a105f8615f3991635c9ffd3a8e5836.png)
[question de programmation] [scratch niveau 2] oiseaux volants en décembre 2019
每日刷题记录 (十六)
单机高并发模型设计
【测试面试题】页面很卡的原因分析及解决方案
Play sonar
随机推荐
How to learn a new technology (programming language)
Cause analysis and solution of too laggy page of [test interview questions]
ROS from entry to mastery (IX) initial experience of visual simulation: turtlebot3
Robomaster visual tutorial (1) camera
RPA cloud computer, let RPA out of the box with unlimited computing power?
Solutions to problems in sqlserver deleting data in tables
Teach you to make a custom form label by hand
【编程题】【Scratch二级】2019.03 绘制方形螺旋
Go learning notes (1) environment installation and hello world
C language 001: download, install, create the first C project and execute the first C language program of CodeBlocks
备库一直有延迟，查看mrp为wait_for_log，重启mrp后为apply_log但过一会又wait_for_log
【史上最详细】信贷中逾期天数统计说明
Introduction to paddle - using lenet to realize image classification method I in MNIST
How to add automatic sorting titles in typora software?
How to measure whether the product is "just needed, high frequency, pain points"
Installation and configuration of sublime Text3
[programming problem] [scratch Level 2] 2019.09 make bat Challenge Game
CoinDesk评波场去中心化进程：让人们看到互联网的未来
某马旅游网站开发（登录注册退出功能的实现）
80% of the people answered incorrectly. Does the leaf on the apple logo face left or right?