Array(1) -- Move Zeroes，Contains Duplicate II，Two Sum，Pascal's Triangle

Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]

void moveZeroes(vector<int>& nums) { int j = 0; // move all the nonzero elements advance for (int i = 0; i < nums.size(); i++) { if (nums[i] != 0) { nums[j++] = nums[i]; } } //fill the end of array with zero for (;j < nums.size(); j++) { nums[j] = 0; } }

Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j]and the difference between i and j is at most k.

维持k大小的set，如果set中找不到，就删掉第i-k-1个，添加i到set中

set<int> cand; for (int i = 0; i < nums.size(); i++) { if (i > k) cand.erase(nums[i-k-1]); if (!cand.insert(nums[i]).second) return true; } return false;

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

使用unordered_map, O(n)；如果array是有序的，则可以采用前后双指针

vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> hash; vector<int> result; for(int i = 0;i < nums.size(); i++){ int diff = target - nums[i]; if(hash.find(diff) != hash.end()){ result.push_back(hash[diff]); result.push_back(i); break; } hash[nums[i]] = i; } return result; }

Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5, Return

[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 先将首尾的1生成，然后生成中间的数

vector<vector<int>> generate(int numRows) { vector<vector<int>> res; for(auto i=0;i<numRows;++i) { res.push_back(vector<int>(i+1,1)); for(auto j=1; j<i; ++j) res[i][j] = res[i-1][j-1] + res[i-1][j]; } return res; }