当前位置:网站首页>Daily question brushing record (XV)
Daily question brushing record (XV)
2022-07-06 23:23:00 【Unique Hami melon】
List of articles
- The first question is : The finger of the sword Offer 57. And for s Two numbers of
- The second question is : The finger of the sword Offer 57 - II. And for s Continuous positive sequence of
- Third question : The finger of the sword Offer 58 - I. Flip word order
- Fourth question : The finger of the sword Offer 59 - I. Maximum sliding window
- Fifth question : The finger of the sword Offer 59 - II. The maximum value of the queue
- Sixth question : The finger of the sword Offer 60. n The number of dice
- Question seven : The finger of the sword Offer 61. Shunzi in playing cards
The first question is : The finger of the sword Offer 57. And for s Two numbers of
LeetCode: The finger of the sword Offer 57. And for s Two numbers of
Add link description
describe :
Enter an ascending array and a number s, Find two numbers in an array , So that their sum is exactly s. If the sum of many pairs of numbers is equal to s, Then output any pair .
Their thinking :
- The title here says array
nums
Is an incremental sort . You can use the double pointer method- use
left
Point to 0 Subscript , useright
Point tonums.length-1
Subscript- If
nums[left] + nums[right] > target
, At this time and big , Just choose a small number , Give Wayright--
- If
nums[left] + nums[right] < target
, At this time and small , Just choose a large array , Give Wayleft++
- If at this time
nums[left] + nums[right] = target
, Return the value of this subscript .
Code implementation :
class Solution {
public int[] twoSum(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while(left < right) {
int total = nums[left] + nums[right];
if (total > target) {
right--;
}else if(total < target) {
left++;
}else{
return new int[]{
nums[left],nums[right]};
}
}
return new int[]{
};
}
}
The second question is : The finger of the sword Offer 57 - II. And for s Continuous positive sequence of
LeetCode: The finger of the sword Offer 57 - II. And for s Continuous positive sequence of
describe :
Enter a positive integer target , Output all and as target A sequence of continuous positive integers ( Contains at least two numbers ).
The numbers in the sequence are arranged from small to large , The different sequences are arranged in descending order according to the first number .
Their thinking :
- Here is also the method of using double pointers .
- Give Way
left = 1
, Give Wayright=2
, from 1, 2 To traverse the- In Mathematics
1~n
Sum up , Gauss theorem ,(n + 1) * (n - 1 + 1) / 2
, So get[left , right]
And for ,(right+left) * (right-left+1) / 2
- If the current sum
total > target
, Give Wayleft++
- If the current sum
total < target
, Give Wayright++
- If the current sum
total = target
, take [left,right] Join the result set . And letleft++
( Otherwise you can't get out of the loop )
Code implementation :
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> res = new ArrayList<>();
int left = 1;
int right = 2;
while(left < right) {
int total = (right + left) * (right - left + 1) / 2;
if(total > target) {
left++;
}else if(total < target){
right++;
}else{
int[] tmp = new int[right-left+1];
for(int i = 0; i < tmp.length; i++) {
tmp[i] = i + left;
}
res.add(tmp);
left++;
}
}
int[][] ans = new int[res.size()][];
for(int i = 0; i < res.size(); i++) {
ans[i] = res.get(i);
}
return ans;
}
}
Third question : The finger of the sword Offer 58 - I. Flip word order
LeetCode: The finger of the sword Offer 58 - I. Flip word order
describe :
Enter an English sentence , Turn over the order of the words in the sentence , But the order of the characters in the word is the same . For the sake of simplicity , Punctuation is treated like ordinary letters . For example, input string "I am a student. “, The output "student. a am I”.
Their thinking :
- For this question , First, remove the extra space at the beginning and end of the string .
- Then according to the space , Split into string arrays
- Then traverse from back to front , remember , There may be multiple spaces ,
- If the current string is empty , continue
5, Not empty , Add the current string directly , Then pay attention to the situation of adding spaces
Code implementation :
class Solution {
public String reverseWords(String s) {
s = s.trim();
String[] str = s.split(" ");
StringBuilder sb = new StringBuilder();
for(int i = str.length-1; i >=0; i--) {
if(str[i].equals("")) continue;
sb.append(str[i]);
if(i != 0) {
sb.append(" ");
}
}
return sb.toString();
}
}
Fourth question : The finger of the sword Offer 59 - I. Maximum sliding window
LeetCode: The finger of the sword Offer 59 - I. Maximum sliding window
describe :
Given an array nums And the size of the sliding window k, Please find the maximum value in all sliding windows .
Their thinking :
- Here construct a size of k Sliding window of
- If the left border of the current sliding window , Not in the initial position , And The right border of the window > The maximum value of the previous window , Then directly make the maximum value of this window equal to the maximum value of the previous window .
- If the left boundary of the current sliding window is not in the initial position , And The previous value of the left boundary of the window , Less than the maximum value of the previous window , that , Let the maximum value of this window equal to the minimum value of the previous window .( Because the newly added value , It is not as big as the maximum value of the previous window , Value to discard , Smaller than the maximum value of the previous window , that , This maximum has not changed )
- dissatisfaction 2, 3 Directly traverse to find the maximum value .
- Finally, return the maximum value of each window .
Code implementation :
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0) return new int[]{
};
int left = 0;
int right = k - 1;
int[] ans = new int[nums.length-k+1];
while (right < nums.length) {
if(left > 0 && nums[right] > ans[left-1]) {
ans[left] = nums[right];
}else if(left > 0 && nums[left-1] < ans[left-1]){
ans[left] = ans[left-1];
}else {
int max = Integer.MIN_VALUE;
for(int i = left; i <= right; i++) {
max = Math.max(max,nums[i]);
}
ans[left] = max;
}
left++;
right++;
}
return ans;
}
}
Fifth question : The finger of the sword Offer 59 - II. The maximum value of the queue
LeetCode: The finger of the sword Offer 59 - II. The maximum value of the queue
describe :
Please define a queue and implement the function max_value
Get the maximum in the queue , Function required max_value
、push_back
and pop_front
Of The average time complexity is O(1).
If the queue is empty ,pop_front
and max_value
Need to return -1
Their thinking :
- The idea of this question is to use a queue , Additive elements . Use a double ended queue , Add the maximum value
- At the time of joining the team , Judge whether the current double ended queue is empty , If it is not empty, compare
- If you insert value It should be larger than the tail element , Just pop up the tail element , Until it is smaller than the end of the team , Or the team is empty
- The maximum value of the current queue is always placed in this double ended queue .
- When out of the team , Return directly if it is empty -1, If it's not empty . Compare the queue head value of the queue and the double ended queue , Have you been , If it's not consistent , It means that the current maximum has not been out of the team , Never mind . At this time, only the first element of the team is used , There is no need to produce a double ended queue header element .
- When the maximum value is obtained , If the queue is empty, return -1, If it's not empty , Directly return the first element of the double ended queue .
Code implementation :
class MaxQueue {
private Queue<Integer> res;
private Deque<Integer> tmp;
public MaxQueue() {
res = new LinkedList<>();
tmp = new LinkedList<>();
}
public int max_value() {
if(res.isEmpty()) {
return -1;
}
return tmp.peekFirst();
}
public void push_back(int value) {
res.offer(value);
while(!tmp.isEmpty() && value > tmp.peekLast()) {
tmp.pollLast();
}
tmp.offerLast(value);
}
public int pop_front() {
if(res.isEmpty()) {
return -1;
}
int val = res.poll();
if(val == tmp.peekFirst()){
tmp.pollFirst();
}
return val;
}
}
/** * Your MaxQueue object will be instantiated and called as such: * MaxQueue obj = new MaxQueue(); * int param_1 = obj.max_value(); * obj.push_back(value); * int param_3 = obj.pop_front(); */
Sixth question : The finger of the sword Offer 60. n The number of dice
LeetCode: The finger of the sword Offer 60. n The number of dice
describe :
hold n A dice on the ground , The sum of the points on the up side of all dice is s. Input n, Print out s The probability that all possible values of the .
You need to return the answer with an array of floating-point numbers , Among them the first i The elements represent this n The number of points that a die can roll i The probability of the smaller one .
Their thinking :
- Dynamic programming is used here
- Dynamic planning ideas :
- state F(i,j): Said yes i A sieve , Points for j Probability
- State transition equation : F(i,j) = dp[i-1][j-k] * 1/6 (j>k)
- The initial state : F(1,j) = 1/6;
- Return results : F
Code implementation :
class Solution {
public double[] dicesProbability(int n) {
// points j [1~6*n]
double[][] dp = new double[n+1][6*n+1];
// The initial state
for (int i = 1; i <= 6; i++) {
dp[1][i] = 1/6.0;
}
for(int i = 2; i <= n; i++) {
// j The scope of the [i,6i]
for(int j = i; j <= 6*i; j++) {
for(int k = 1; k <= 6; k++) {
// When j > k When , Only the number of points can be found, and it is impossible to throw them out 0 -1
if(j>k) {
dp[i][j] += dp[i-1][j-k] * 1 / 6.0;
}else{
// Just here j<=k, The latter situation will only be smaller , Just skip
break;
}
}
}
}
// n A sieve , The result is [n,6n], Altogether , (6n-n)+1 = 5n+1 Number
double[] res = new double[5*n+1];
for(int i = 0; i < 5 * n + 1; i++) {
res[i] = dp[n][n+i];
}
return res;
}
}
Question seven : The finger of the sword Offer 61. Shunzi in playing cards
LeetCode: The finger of the sword Offer 61. Shunzi in playing cards
describe :
Draw at random from several sets of playing cards 5 card , Judge whether it's a down son , Is this 5 Are cards continuous .2~10 For the number itself ,A by 1,J by 11,Q by 12,K by 13, And big 、 Wang Wei 0 , It can be seen as any number .A Can't be regarded as 14.
Their thinking :
- The meaning of this question is , 0 It can be used as other cards
- Here is the first sorting .
- Then record zero The number of times
- zero After recording , Check whether the difference between the two arrays is 1,
- If the difference is 1, continue
- If two are equal , Go straight back to false;
- If there are other situations , Get the difference in the number of cards , Calculation formula
right - left -1
, According to this data , see zero Is it enough , If zero<0 Go straight back to false.- End of traversal , return true
Code implementation :
class Solution {
public boolean isStraight(int[] nums) {
Arrays.sort(nums);
int zero = 0;
int index = 0;
for(int i = 0; i < nums.length - 1; i++) {
if (nums[i] == 0) {
zero++;
}else{
if(nums[i] == nums[i+1]) {
return false;
}
if(nums[i+1] - nums[i] != 1){
zero -= nums[i+1] - nums[i] - 1;
if(zero < 0) return false;
}
}
}
return true;
}
}
边栏推荐
- 案例推荐丨安擎携手伙伴,保障“智慧法院”更加高效
- 【Unity】升级版·Excel数据解析,自动创建对应C#类,自动创建ScriptableObject生成类,自动序列化Asset文件
- 问下各位,有没有flink sql生成作业的文档啊或是案列啊知道flink cli可以建表和指定目
- The problem that dockermysql cannot be accessed by the host machine is solved
- Dayu200 experience officer runs the intelligent drying system page based on arkui ETS on dayu200
- Use mitmproxy to cache 360 degree panoramic web pages offline
- 自动更新Selenium驱动chromedriver
- mysql-cdc 的jar包 ,在flink运行模式下,是不是要放在不同的地方呢?
- What does front-end processor mean? What is the main function? What is the difference with fortress machine?
- Thinkphp5 multi table associative query method join queries two database tables, and the query results are spliced and returned
猜你喜欢
Case recommendation: An Qing works with partners to ensure that the "smart court" is more efficient
Ajout, suppression et modification d'un tableau json par JS
借助这个宝藏神器,我成为全栈了
Flutter life cycle
Dayu200 experience officer runs the intelligent drying system page based on arkui ETS on dayu200
MySQL数据库之JDBC编程
Cloud native technology container knowledge points
Stop saying that microservices can solve all problems
Cocoscreator+typescripts write an object pool by themselves
Isomorphism + cross end, knowing applet +kbone+finclip is enough!
随机推荐
DockerMySQL无法被宿主机访问的问题解决
食品里的添加剂品种越多,越不安全吗?
European Bioinformatics Institute 2021 highlights report released: nearly 1million proteins have been predicted by alphafold
让 Rust 库更优美的几个建议!你学会了吗?
为了交通安全,可以做些什么?
B 站弹幕 protobuf 协议还原分析
C three ways to realize socket data reception
Why are some people still poor and living at the bottom of society even though they have been working hard?
How can Oracle CDC deserialize with jsondebeziumdeserializationschema
Motion capture for snake motion analysis and snake robot development
Unified Focal loss: Generalising Dice and cross entropy-based losses to handle class imbalanced medi
A novice asks a question. I am now deployed on a single machine. I submitted an SQL job and it runs normally. If I restart the service job, it will disappear and I will have to
云原生(三十二) | Kubernetes篇之平台存储系统介绍
flinksql select id ,count(*) from a group by id .
docker中mysql开启日志的实现步骤
Docker starts MySQL and -emysql_ ROOT_ Password = my secret PW problem solving
问下各位,有没有flink sql生成作业的文档啊或是案列啊知道flink cli可以建表和指定目
安全保护能力是什么意思?等保不同级别保护能力分别是怎样?
MySQL实现字段分割一行转多行的示例代码
PDF批量拆分、合并、书签提取、书签写入小工具