Array sum
Given an array of integers (nums) and a target value (target), find the two integers in the array and return their array index (target).
var twoSum = function(nums, target) { for(let i = 0; i<nums.length -1 ; i++){ for(let j = i+1; j < nums.length ; j++){ if(target - nums[i] === nums[j]){ return [i,j] } } } };Copy the codeThis is the first time I’ve written something like this, and if you’re like this, when you click the execute code button, you’ll notice that it takes a long time to get the result. Well, I guess I was right. I didn’t feel anything.
The double for loop really doesn’t work. Just like you and the legendary neighborhood kid, someone else’s problem solving can only be described as amazing.
I use the inner for loop, which takes more time, while others trade space for time. So start imitating:
var twoSum = function(nums, target) { const res = {} const len =nums.length for(let i =0; i<len ; i++){ if(res[target - nums[i]] ! == undefined){ return [res[target-nums[i]],i] } res[nums[i]] = i } };Copy the code
By looking at other people’s problems, you can see that everyone uses a variable to store nums.length instead of writing nums.length in the for loop, so I learned this too. Then the judgment condition can be directly in the data structure we established to find whether there is an existing value. If it doesn’t exist, store it in our RES for the next loop.
Deletes ordered array duplicates
Give you an ordered array nums, ask you to delete the repeated elements in place, so that each element appears only once, return the deleted array after the new length. Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space
var removeDuplicates = function(nums) { let j = 0; const len = nums.length for (var i = 1; i<len; i++){ if(nums[i] ! = nums[i-1]){ j++; nums[j] = nums[i]; } } return j+1; };Copy the code
If the last one is not equal to the last one, then i++, j++, and then compare the last one. When encountering an equal term, do not deal with the previous term, and directly replace the repeated term with the later term, which can achieve the purpose of eliminating weight.
After checking the solution, I know that this is a double pointer, but there are always divine people. This is from the big guy you see in the solution:
class Solution { public int removeDuplicates(int[] nums) { int index=1; for(int i=1; i<nums.length; If (nums[I]==nums[i-1])continue; if(nums[I]==nums[i-1])continue; Nums [index++]=nums[I]; } } return index; }} By Chen-yi-qian-c https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shuang-zhi-zhen-by-chen-yi-qian-c-u40v/ Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.Copy the codeThere is no end to learning. Learn more about the knowledge of predecessors and strive to be the man who stands on the shoulders of giants.
Search for insertion position
Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order. The time complexity must be set toO(log n)In the algorithm.
var searchInsert = function(nums, target) {
let len = nums.length
let left=0;
let right=len-1
let ans=len;
while (left <= right) {
let mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
Copy the code
If a sorted array is given a target value, the index must be returned with or without a value. So don’t be confused by the word insert, this problem is to look up the index number. Also don’t do those weird solutions. My final implementation is the official one.
Binary search, every time find a mid value, and then compare with the target value, can save a lot of time, at the same time find the mid value after the search scope is reduced, if the target value is less than mid value, the right boundary is mid, and vice versa, you understand. At the end of the process you can determine the position of the final target value.
Merges two ordered arrays
You are given two non-descending arrays of integers, nums1 and nums2, and two integers, m and n, representing the number of elements in nums1 and nums2, respectively.
Please merge nums2 into nums1 so that the merged array is also in non-descending order.
Note: Finally, the merged array should not be returned by the function, but stored in the array nums1. To deal with this, nums1 has an initial length of m + n, where the first m elements represent the elements that should be combined and the last n elements are 0 and should be ignored. Nums2 has a length of n.
For (nums1, nums1, nums1, nums1, nums1, nums1, nums1, nums1, nums1, nums1, nums1, nums1, nums1) Think about the trouble, do what is to do, is to use simple ideas to achieve a variety of problems. While, I just need to decide whether to add or not, and then plug in the comparison result. After all, while will do everything by itself, so let it do it by itself. By looking at the problem solution and thinking about the idea, I know the pointer. This thing is to define a variable to point to the data we need, which is convenient for us to use. After all, taking a variable and saving it is certainly more comfortable and coherent than calling it the original item.
const merge = function(nums1, m, nums2, n) {
let i = m - 1, j = n - 1, k = m + n - 1
while(i >= 0 && j >= 0) {
if(nums1[i] >= nums2[j]) {
nums1[k] = nums1[i]
i--
k--
} else {
nums1[k] = nums2[j]
j--
k--
}
}
};
Copy the codeAfter all, it has to be merged into nums1, so the total number of elements must be m+n. If j > 0, add nums2 to nums1 through a while loop. If j > 0, add nums2 to nums1.
while(j>=0) {
nums1[k] = nums2[j]
k--
j--
}
Copy the codeThis is OK. Finish this problem, later to do the problem, if you think about your ideas around the bar ji, that is probably the idea of running off, code are saved, directly jump out of the thinking.
Yang hui triangle
Given a non-negative integer numRows, generate the former numRows of the “Yang Hui triangle”. In Yang Hui’s triangle, each number is the sum of the numbers on its upper left and upper right. Anyway see problem I was hemp, although now big four, but this Yang Hui triangle or he knows me I forget his state, can see baidu that only.
I’m getting tired of reading so much. Anyway, this thing is a triangle (crap!). Fill the left and right sides with 1, then each number in each row is equal to the sum of the left and right digits in the previous row, and then the number of elements in each row is equal to the number of rows (comfortable). So that’s pretty much enough to figure out how to solve the problem.
If I want to know what I should put in each line, FIRST I need to know what the left and right elements of my previous line are. If I want to push the next row, I have to get to the last item in the result array. Then add some elements to get the element value of push row.
var generate = function(numRows) {
let res = [];
for(let i = 0; i < numRows; i++){
let row = [];
row[0] = 1;
row[i] = 1;
if(i > 1){
for(let j = 1; j < i; j++){
row[j] = res[i - 1][j - 1] + res[i - 1][j];
}
}
res.push(row);
}
return res;
};
Copy the codeThrough trial and error, look at the solution of the problem. The final answer is this. I won’t write about the trial and error process, and I don’t remember how many wonderful mistakes. Row [0] and row[row.length-1] are both 1. All the edges are done, and that leaves the rest of the elements. Each element is a neighboring element of the previous row and. If the index of the current row is j, then the adjacent elements of the previous row must be res[i-1][j-1] and res[i-1][j]. To this also clear. The rest of the mo. Quite a simple thing, forget Yang Hui triangle can also be done in a short time. Same rule, definitely want to see the solution. Just watch the video for the first time to see the comments, the solution and the comments are the same can not be missed.
class Solution { public: The vector < vector < int > > generate (int numRows) {vector < vector < int > > res = {{1}, {1, 1}, {1, 2, 1}, {1,3,3,1}, {1,4,6,4,1}, ,6,15,20,15,6,1,5,10,10,5,1 {1}, {1}, {1,7,21,35,35,21,7,1}, {1,8,28,56,70,56,28,8,1}, {1,9,36,84,126,126,84,36,9,1}, ,11,55,165,330,462,462,330,165,55,11,1,10,45,120,210,252,210,120,45,10,1 {1}, {1}, ,13,78,286,715,1287,1716,1716,1287,715,286,78,13,1,12,66,220,495,792,924,792,495,220,66,12,1 {1}, {1}, ,14,91,364,1001,2002,3003,3432,3003,2002,1001,364,91,14,1 {1}, ,15,105,455,1365,3003,5005,6435,6435,5005,3003,1365,455,105,15,1 {1}, ,16,120,560,1820,4368,8008,11440,12870,11440,8008,4368,1820,560,120,16,1 {1}, ,17,136,680,2380,6188,12376,19448,24310,24310,19448,12376,6188,2380,680,136,17,1 {1}, ,18,153,816,3060,8568,18564,31824,43758,48620,43758,31824,18564,8568,3060,816,153,18,1 {1}, ,19,171,969,3876,11628,27132,50388,75582,92378,92378,75582,50388,27132,11628,3876,969,171,19,1 {1}, ,20,190,1140,4845,15504,38760,77520,125970,167960,184756,167960,125970,77520,38760,15504,4845,1140,190,20,1 {1}, ,21,210,1330,5985,20349,54264,116280,203490,293930,352716,352716,293930,203490,116280,54264,20349,5985,1330,210,21,1 {1}, {1,22,231,1540,7315,26334,74613,170544,319770,497420,646646,705432,646646,497420,319770,170544,74613,26334,7315,1540,23 1,22,1}, {1,23,253,1771,8855,33649,100947,245157,490314,817190,1144066,1352078,1352078,1144066,817190,490314,245157,100947,33649, 8855177 1253,23,1}, {1,24,276,2024,10626,42504,134596,346104,735471,1307504,1961256,2496144,2704156,2496144,1961256,1307504,735471,346104,13 4596425 04106 26202 4276,24,1}, {1,25,300,2300,12650,53130,177100,480700,1081575,2042975,3268760,4457400,5200300,5200300,4457400,3268760,2042975,1081575 , 480700177, 100531, 30126, 50230 0300,25,1}, {1,26,325,2600,14950,65780,230230,657800,1562275,3124550,5311735,7726160,9657700,10400600,9657700,7726160,5311735,312455 0156275657 800230 230657 80149 50260 0325,26,1}, {1,27,351,2925,17550,80730,296010,888030,2220075,4686825,8436285,13037895,17383860,20058300,20058300,17383860,13037895,8 436285468825222075888 030296 010807 30175 50292 5351,27,1}, {1,28,378,3276,20475,98280,376740,1184040,3108105,6906900,13123110,21474180,30421755,37442160,40116600,37442160,30421755 , 21474180131311, 0690900310105118040376, 740982, 80204, 75327, 6378,28,1}, {1,29,406,3654,23751,118755,475020,1560780,4292145,10015005,20030010,34597290,51895935,67863915,77558760,77558760,678639 15518593 5345729 0200001 0100500 5429145156780475 020118 755237 51365 4406,29,1}}; res.resize(numRows); return res; }};Copy the codeThe source of happiness. But there are big boys everywhere, and there will always be someone who will do it in code that you don’t understand
var generate = function(numRows) { return Array(numRows).fill().map((_, i, r) => r[i] = Array(i + 1).fill(1).map((v, j) => j > 0 && j < i ? r[i - 1][j - 1] + r[i - 1][j] : v)) }; By Mantoufan Source: https://leetcode-cn.com/problems/pascals-triangle/solution/xiang-lin-dui-cheng-1xing-dai-ma-2jie-fa-ndok/ LeetCode copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.Copy the codeBig guy problem solution to write, a line of implementation, over 99%, although WE do not have this ability, but also have to see. Because big guy has two solutions, as well as description and graph, or directly move force buckle.