当前位置:网站首页>Daily question brushing record (XIV)
Daily question brushing record (XIV)
2022-07-05 21:51:00 【Unique Hami melon】
List of articles
- The first question is : The finger of the sword Offer 62. The last number in the circle
- The second question is : The finger of the sword Offer 63. The biggest profit of stocks
- Third question : The finger of the sword Offer 64. seek 1+2+…+n
- Fourth question : The finger of the sword Offer 66. Building a product array
- Fifth question : The finger of the sword Offer 67. Convert a string to an integer
- Sixth question : The finger of the sword Offer 68 - I. The nearest common ancestor of a binary search tree
The first question is : The finger of the sword Offer 62. The last number in the circle
LeetCode: The finger of the sword Offer 62. The last number in the circle
describe :
0,1,···,n-1 this n Number in a circle , From numbers 0 Start , Delete the... From this circle every time m A digital ( Delete and count from the next number ). Find the last number left in the circle .
for example ,0、1、2、3、4 this 5 Numbers make a circle , From numbers 0 Start deleting the 3 A digital , Before deleting 4 The numbers in turn are 2、0、4、1, So the last remaining number is 3.
Their thinking :
- Here we use mathematical thinking
- for the first time When deleting ,
0 1 2 3 4
, Delete2
- The second time When deleting ,
3 4 0 1
, Delete0
- third time When deleting ,
1 3 4
, Delete4
- The fourth time When deleting ,
1 3
, Delete1
- The fifth time There is no need to delete ,
3
, return3
Here you can use reverse push ,
For example, in the fifth time , The initial position subscript position is0
, To know the subscript position of the fourth time , adoptindex = (index + m) % i
, Here isindex
Is the current subscript ,m
Is the deleted subscript ,i
Is the number of times from back to front ( For example, the fourth time here , The opposite is the second time ).
So calculate the subscript to getindex = (0 + 3) % 2 = 1
, So at the fourth time , Finally, the remaining subscripts are1
Code implementation :
class Solution {
public int lastRemaining(int n, int m) {
// The last remaining elements , The subscript can only be 0
int index = 0;
for (int i = 2; i <= n; i++) {
// The last coordinate position can be obtained by mathematical backward deduction
index = (index + m) % i;
}
// Calculate the initial time , Subscript location
return index;
}
}
The second question is : The finger of the sword Offer 63. The biggest profit of stocks
LeetCode: The finger of the sword Offer 63. The biggest profit of stocks
describe :
Suppose you store the price of a stock in an array in chronological order , What's the maximum profit you can get from buying and selling this stock at one time ?
Their thinking :
- The initial conditions , Give Way min = prices[0], Record the maximum max
- Traversal array ,
- If at present prices[i] Greater than min, Record the maximum ,
max = Math.max(max, prices[i] - min)
- If at present prices[i] Less than min, Just replace
min
Code implementation :
class Solution {
public int maxProfit(int[] prices) {
if(prices.length == 0) return 0;
int min = prices[0];
int max = 0;
for(int price : prices) {
if (min > price) {
min = price;
}else{
max = Math.max(max,price-min);
}
}
return max;
}
}
Third question : The finger of the sword Offer 64. seek 1+2+…+n
LeetCode: The finger of the sword Offer 64. seek 1+2+…+n
describe :
seek 1+2+...+n
, It is required that multiplication and division shall not be used 、for、while、if、else、switch、case Wait for keywords and conditional statements (A?B:C).
Their thinking :
- Because it can't be used for loop
- Here we use recursion to evaluate
- utilize
boolean flg = (A) && (B)
, here If A by false End recursion . therefore A Play a if effect , B Play a for effect
Code implementation :
class Solution {
public int sumNums(int n) {
boolean flg = n > 0 && (n += sumNums(n - 1)) >0;
return n;
}
}
Fourth question : The finger of the sword Offer 66. Building a product array
LeetCode: The finger of the sword Offer 66. Building a product array
describe :
Given an array A[0,1,…,n-1]
, Please build an array B[0,1,…,n-1]
, among B[i]
Is the value of an array A
In addition to subscript i
The product of other elements , namely B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]
. Division cannot be used .
Their thinking :
- Because division cannot be used , You can't get rid of yourself here
- First multiply it from left to right , Every time I can't be myself
- Multiply again from right , Every time I can't be myself
Code implementation :
class Solution {
public int[] constructArr(int[] a) {
int[] res = new int[a.length];
int ret = 1;
for(int i = 0; i < a.length; i++) {
res[i] = ret;
ret *= a[i];
}
ret = 1;
for(int i = a.length-1; i >=0 ; i--) {
res[i] *= ret;
ret *= a[i];
}
return res;
}
}
Fifth question : The finger of the sword Offer 67. Convert a string to an integer
LeetCode: The finger of the sword Offer 67. Convert a string to an integer
describe :
Write a function StrToInt, Realize the function of converting string to integer . Out of commission atoi Or other similar library functions .
First , This function discards the useless start space characters as needed , Until the first non space character is found .
When the first non empty character we find is a positive or negative sign , Then combine the symbol with as many consecutive numbers as possible on the back face , As the sign of the integer ; If the first non empty character is a number , Then combine it directly with the following consecutive numeric characters , Form an integer .
In addition to the valid integer part of the string, there may be extra characters , These characters can be ignored , They should have no effect on functions .
Be careful : If the first non space character in the string is not a valid integer character 、 When the string is empty or the string contains only white space characters , Then your function doesn't need to be converted .
In any case , If the function cannot be effectively converted , Please return 0.
explain :
Suppose our environment can only store 32 A signed integer of bit size , So the value range is [−231, 231 − 1]. If the value exceeds this range , Please return INT_MAX (231 − 1) or INT_MIN (−231) .
Their thinking :
- First, remove the spaces before and after
- Then judge whether the current is empty , It may be free after removal
- Judge the first character , Is it a number , Or is it a symbol , If it's not a direct return
0
- If the first character is a minus sign , Record the current symbol
- Cycle the current numeric characters ,
- Use one long Type to calculate the current number size
- If the current number is greater than
Integer.MAX_VALUE
, And the symbol is positive , returnInteger.MAX_VALUE
- If the current number is greater than
Integer.MAX_VALUE
, And the sign is negative , returnInteger.MIN_VALUE
- If the cycle ends , Not more than
Integer.MAX_VALUE
, Returns the current res, A positive sign returns res, Negative sign return -res
Code implementation :
class Solution {
public int strToInt(String str) {
str = str.trim();
int index = 0;
if(index>=str.length()) return 0;
if(!Character.isDigit(str.charAt(0)) && str.charAt(0)!='-' && str.charAt(0)!='+'){
return 0;
}
int flg = 1;
if(str.charAt(0) == '-'){
flg = -1;
index++;
}else if(str.charAt(0) == '+'){
index++;
}
long res = 0;
while(index < str.length() && Character.isDigit(str.charAt(index))){
res = res * 10 + str.charAt(index)-'0';
if(res > Integer.MAX_VALUE && flg == 1){
return Integer.MAX_VALUE;
}else if (res > Integer.MAX_VALUE && flg == -1) {
return Integer.MIN_VALUE;
}
index++;
}
res = flg==1?res:-res;
return (int)res;
}
}
Sixth question : The finger of the sword Offer 68 - I. The nearest common ancestor of a binary search tree
LeetCode: The finger of the sword Offer 68 - I. The nearest common ancestor of a binary search tree
describe :
Given a binary search tree , Find the nearest common ancestor of the two specified nodes in the tree .
In Baidu Encyclopedia, the most recent definition of public ancestor is :“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible ( A node can also be its own ancestor ).”
for example , Given the following binary search tree : root = [6,2,8,0,4,7,9,null,null,3,5]
Their thinking :
Pay attention to several situations here .
root
by Empty When , Go straight back to null- If at present
root
The value of the node , Greater thanp
Value , And Greater thanq
Value , Then it's in the left subtree .- If at present
root
The value of the node , Less thanp
Value , And Less thanq
Value , So it's in the right subtree .- No ,
p
,q
On the left and right , Or the root node , Go straight back to root
Code implementation :
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
if(root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left,p,q);
}else if(root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right,p,q);
}else{
return root;
}
}
}
边栏推荐
- HDU 4391 Paint The Wall 段树(水
- 思特奇加入openGauss开源社区,共同推动数据库产业生态发展
- int GetMonth( ) const throw( ); What does throw () mean?
- MMAP
- Codeforces 12D ball tree array simulation 3 sorting elements
- 华为游戏多媒体调用切换房间方法出现异常Internal system error. Reason:90000017
- ESP32
- An exception occurred in Huawei game multimedia calling the room switching method internal system error Reason:90000017
- R language learning notes
- The solution to the problem that Oracle hugepages are not used, causing the server to be too laggy
猜你喜欢
2.2.5 basic sentences of R language drawing
Matlab | app designer · I used Matlab to make a real-time editor of latex formula
Xlrd common operations
每日刷题记录 (十四)
1.2 download and installation of the help software rstudio
JMeter installation under win7
Li Kou ----- the maximum profit of operating Ferris wheel
Reptile practice
Defect detection - Halcon surface scratch detection
使用Aspect制作全局异常处理类
随机推荐
Experienced inductance manufacturers tell you what makes the inductance noisy. Inductance noise is a common inductance fault. If the used inductance makes noise, you don't have to worry. You just need
Learning notes of statistical learning methods -- Chapter 1 Introduction to statistical learning methods
PIP install beatifulsoup4 installation failed
初级软件测试必问面试题
Drawing HSV color wheel with MATLAB
Haas506 2.0 development tutorial - Alibaba cloud OTA - PAC firmware upgrade (only supports versions above 2.2)
Simple interest mode - lazy type
Net small and medium-sized enterprise project development framework series (one)
Sorting out the problems encountered in MySQL built by pycharm connecting virtual machines
Parker driver maintenance COMPAX controller maintenance cpx0200h
MMAP学习
Xlrd common operations
Some common processing problems of structural equation model Amos software
ICMP introduction
Kingbasees v8r3 cluster maintenance case -- online addition of standby database management node
123456
kingbaseES V8R3数据安全案例之---审计记录清除案例
The solution to the problem that Oracle hugepages are not used, causing the server to be too laggy
About the writing method of SQL field "this includes" and "included in" strings
Evolution of zhenai microservice underlying framework from open source component encapsulation to self-development