Leetcode face T10 (1-9) array, ByteDance interview sharing

Sparse array search . There's an ordered array of strings , It's interspersed with empty strings , Write a method , Find the position of a given string .

Example 1:

Input : words = [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”,“dad”, “”, “”], s = “ta”

Output ：-1

explain : There is no return -1.

Example 2:

Input ：words = [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”,“dad”, “”, “”], s = “ball”

Output ：4

Tips :

words The length of is [1, 1000000] Between

source ： Power button （LeetCode）

link ：https://leetcode-cn.com/problems/sparse-array-search-lcci

Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

stay Java To determine whether the string values are equal, use s1,equals(s1). Don't use it directly ==, It took a long time mmp.

class Solution {

// direct method

// public int findString(String[] words, String s) {

// for(int i =0;i <words.length;i++){

// if(words[i].equals(s)){

// return i;

// }

// }

// return -1;

// }

// Binary search

public int findString(String[] words, String s) {

// Direct binary search

int left = 0;

int right = words.length - 1;

//[left.right)

while(left <= right){

while(left < words.length && words[left].equals("")){

left++;

}

while(right >= 0 && words[right].equals("")){

right–;

}

int mid = left + (right - left) / 2;

while(mid < words.length && words[mid].equals("")){

mid++;

}

if(words[mid].equals(s)){

return mid;

}else if(words[mid].compareTo(s) > 0){

// Shrink the right border , Lock left boundary

right = mid - 1;

}else if(words[mid].compareTo(s) < 0){

// Shrink the left border , Lock the right boundary

left = mid + 1;

}

}

return -1;

}

}

Q10.9  Sort matrix search

Given M×N matrix , Every line 、 Each column is arranged in ascending order , Write code to find an element .

Example :

The existing matrix matrix as follows ：

[

[1,   4,  7, 11, 15],

[2,   5,  8, 12, 19],

[3,   6,  9, 16, 22],

[10, 13, 14, 17, 24],

[18, 21, 23, 26, 30]

]

Given target = 5, return  true.

Given  target = 20, return  false.

source ： Power button （LeetCode）

link ：https://leetcode-cn.com/problems/sorted-matrix-search-lcci

Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

class Solution {

public boolean searchMatrix(int[][] matrix, int target) {

if (matrix == null || matrix.length == 0) {

return false;

}

int m = matrix.length, n = matrix[0].length, row = 0, col = n - 1;

while (row < m && col >= 0) {

if (matrix[row][col] < target) {

row++;

} else if(matrix[row][col] > target) {

col–;

} else {

return true;

}

}

return false;

}

}

Q10.10 Rank of digital stream

Suppose you are reading a string of integers . Every once in a while , You want to find out the numbers x The rank of ( Less than or equal to x The number of values of ). Please implement data structures and algorithms to support these operations , in other words ：

Realization track(int x)  Method , This method is called every time a number is read in ;

Realization getRankOfNumber(int x) Method , Returns less than or equal to x The number of values of .

Be careful ： This question is slightly changed from the original one

Example :

Input :

[“StreamRank”, “getRankOfNumber”, “track”, “getRankOfNumber”]

[[], [1], [0], [0]]

Output :

[null,0,null,1]

Tips ：

x <= 50000

track  and  getRankOfNumber Methods are called no more than 2000 Time

source ： Power button （LeetCode）

link ：https://leetcode-cn.com/problems/rank-from-stream-lcci

Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

int[] nums;

public StreamRank() {

nums = new int[50002];

}

public void track(int x) {

// Avoid for 0

++x;

for (int i = x; i <= nums.length - 1; i += lowBit(i))

nums[i]++;

}

public int getRankOfNumber(int x) {

int sum = 0;

++x;

for (int i = x; i > 0; i -= lowBit(i))

sum += nums[i];

return sum;

}

public int lowBit(int x) {

return x & (-x);

}

Q10.11  Peak and valley

In an array of integers ,“ peak ” Is an element greater than or equal to an adjacent integer , Accordingly ,“ valley ” Is an element less than or equal to an adjacent integer . for example , In the array {5, 8, 4, 2, 3, 4, 6} in ,{8, 6} It's the peak , {5, 2} It's the valley . Now, given an array of integers , Sort the array in alternating order of peaks and valleys .

Example :

Input : [5, 3, 1, 2, 3]

Output : [5, 1, 3, 2, 3]

Tips ：

nums.length <= 10000

source ： Power button （LeetCode）

link ：https://leetcode-cn.com/problems/peaks-and-valleys-lcci

Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

greedy , Refer to the explanation of the question ：

（1） If i Is the position of the peak , Then judge whether the current position is less than the previous position （ The former is Gu ）, If less than , The exchange , If it is greater than, it will not be processed . namely ： if(nums[i]<nums[i-1]) swap(nums[i],nums[i-1]);

（2） If i For the location of the valley , Then judge whether the current position is greater than the previous position （ The previous one is the peak ）, If more than , The exchange , If it is greater than, it will not be processed . namely ： if(nums[i]>nums[i-1]) swap(nums[i],nums[i-1]);

public void wiggleSort(int[] nums) {

/* Sort the array O(nlogn)

int[] res = Arrays.copyOf(nums, nums.length);

Arrays.sort(res);

int index = res.length - 1;

for(int i = 0;i < res.length;i += 2) {

nums[i] = res[index–];

}

for(int i = 1;i < res.length;i += 2) {

nums[i] = res[index–];

}

*/

// Direct traversal O(n)

for(int i = 1;i < nums.length;i++) {

Review the interview notes ：

This information I started with spring recruitment , I'll put all the blogs 、 Forum . High quality... On the website Android Develop advanced interview questions and collect them , Then the whole network looks for the best solution . Every interview question is 100% real one + Optimal solution . The context of knowledge + A lot of details .
Save everyone's time in searching materials on the Internet to learn , You can also share it with your friends and learn together .
Leave a little praise for the article , You can get it for free ~

Poke me for ：GitHub

《960 page Android Development Notes 》

《1307 page Android Develop interview tips 》

Including Tencent 、 Baidu 、 millet 、 Ali 、 Letv 、 Meituan 、58、 Cheetah 、360、 Sina 、 Sohu and other first-line Internet companies were asked questions in the interview . Being familiar with the knowledge listed in this article will greatly increase the probability of passing the first two rounds of technical interview .

《507 page Android Development related source code analysis 》

As long as the programmer is , Whether it's Java still Android, If you don't read the source code , Just look at API file , It's just a matter of skin , This is not conducive to the establishment and completion of our knowledge system and the improvement of actual combat technology .

B%EF%BC%9F%E5%A6%82%E4%BD%95%E9%9D%A2%E8%AF%95%E6%8B%BF%E9%AB%98%E8%96%AA%EF%BC%81.md)**

《960 page Android Development Notes 》

[ Outside the chain picture transfer in …(img-kEEjSeXJ-1644918789060)]

《1307 page Android Develop interview tips 》

Including Tencent 、 Baidu 、 millet 、 Ali 、 Letv 、 Meituan 、58、 Cheetah 、360、 Sina 、 Sohu and other first-line Internet companies were asked questions in the interview . Being familiar with the knowledge listed in this article will greatly increase the probability of passing the first two rounds of technical interview .

[ Outside the chain picture transfer in …(img-0Q8Ytred-1644918789061)]

《507 page Android Development related source code analysis 》

As long as the programmer is , Whether it's Java still Android, If you don't read the source code , Just look at API file , It's just a matter of skin , This is not conducive to the establishment and completion of our knowledge system and the improvement of actual combat technology .

The real ability to exercise is to directly read the source code , Not limited to reading the source code of the major systems , It also includes a variety of excellent open source libraries .