2020-07-27
55. 跳躍游戲
思路
- 對nums數(shù)組，令nums[i] += i,這樣表示i位置最遠可以走到的距離
- 算法
從i = 0開始
對于當前i亮钦，可以從0走到nums[i]，選取0-nums[i]的最大值充活，如果最大值大于等于n-1蜂莉，則可以到達最后，若小于混卵，重復這個步驟映穗，除非i=最大值，則不能到達最后
- 為了降低時間復雜度幕随，創(chuàng)建一個數(shù)組v蚁滋，v[i] = max(nums[k]), k = 0,1,...,i
AC代碼
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = int(nums.size());
for(int i = 0; i < n; i++) {
nums[i] += i;
}
vector<int> v;
int max = nums[0];
for(int i = 0; i < n; i++) {
if (nums[i] > max) {
max = nums[i];
}
v.push_back(max);
}
int i = 0;
while (i != v[i]) {
i = v[i];
if (i >= n-1) {
return true;
}
}
return false || n == 1;
}
};
優(yōu)化
參考已經(jīng)提交的代碼，可以不創(chuàng)建數(shù)組v赘淮，也用O(n)的時間完成
優(yōu)化代碼
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = int(nums.size());
int i = 0;
int max = nums[0];
while (i <= max) {
if (max < i + nums[i]) {
max = i + nums[i];
}
if (max >= n-1) {
return true;
}
i++;
}
return false || n == 1;
}
};
這道題leetcode上的測速不準辕录，沒有參考價值，相同參考代碼能跑出不同的速度梢卸。
16. 最接近的三數(shù)之和
AC代碼
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int mincut = nums[0] + nums[1] + nums[2];
for(int i = 0; i < (int)nums.size() - 2; i ++) {
int j = i + 1, k = nums.size() - 1;
while(j < k) {
int threesum = nums[i] + nums[j] + nums[k];
if(abs(threesum - target) < abs(mincut - target)) mincut = threesum;
if(threesum == target) return target;
else if(threesum < target) j ++;
else k --;
}
}
return mincut;
}
};
優(yōu)化
跳過一些不用考慮的值走诞，1.和上次枚舉的數(shù)相同的值，2.已經(jīng)等于target的情況
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int n = nums.size();
int best = 1e7;
// 根據(jù)差值的絕對值來更新答案
// 枚舉 a
for (int i = 0; i < n; ++i) {
// 保證和上一次枚舉的元素不相等
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 使用雙指針枚舉 b 和 c
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
// 如果和為 target 直接返回答案
if (sum == target) {
return target;
}
if (abs(sum - target) < abs(best - target)) {
best = sum;
}
if (sum > target) {
// 如果和大于 target蛤高，移動 c 對應(yīng)的指針
int k0 = k - 1;
// 移動到下一個不相等的元素
while (j < k0 && nums[k0] == nums[k]) {
--k0;
}
k = k0;
} else {
// 如果和小于 target蚣旱，移動 b 對應(yīng)的指針
int j0 = j + 1;
// 移動到下一個不相等的元素
while (j0 < k && nums[j0] == nums[j]) {
++j0;
}
j = j0;
}
}
}
return best;
}
};
61. 旋轉(zhuǎn)鏈表
AC代碼
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head == NULL) {
return head;
}
int n = 0;
ListNode *p = head;
while (p->next != NULL) {
n++;
p = p->next;
}
n++;
k %= n;
p->next = head;
p = head;
for (int i = 0; i < n - k - 1; i++) {
p = p->next;
}
ListNode* new_head = p->next;
p->next = NULL;
return new_head;
}
};
經(jīng)驗
看似簡單的題，發(fā)現(xiàn)了自己的知識漏洞戴陡，圖遍歷的時候要有visit數(shù)組記錄它是否訪問過塞绿，此處用map代替。
133. 克隆圖
AC代碼
class Solution {
public:
Node* cloneGraph(Node* node) {
if(node == NULL) return NULL;
unordered_map<Node*, Node*> m;
queue<Node*> q;
q.push(node);
Node* head = new Node(node->val, vector<Node*>{});
m[node]=head;
while (!q.empty()) {
Node* temp = q.front();
q.pop();
for (Node* child: temp->neighbors) {
if(!m.count(child)) {
m[child] = new Node(child->val, vector<Node*>{});
q.push(child);
}
m[temp]->neighbors.push_back(m[child]);
}
}
return head;
}
};
120. 三角形最小路徑和
超時算法 普通的搜索
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int ni = int(triangle.size());
vector<int> v(ni, 0);
vector<int> index(ni, 0);
int sum = INT_MAX;
while(v[0] == 0) {
int t_sum = 0;
for (int j = 0; j < ni; j++) {
t_sum += triangle[j][index[j]];
}
if (t_sum < sum) {
sum = t_sum;
}
int i = ni-1;
while (i > 0 && v[i] == 1) {
v[i] = 0;
i--;
}
index[i]++;
for (int j = i+1; j < ni ; j++) {
index[j] = index[j-1];
}
v[i] = 1;
}
return sum;
}
};
優(yōu)化思路
一個個枚舉會超時恤批，要用動態(tài)規(guī)劃
AC代碼
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int ni = int(triangle.size());
vector<int> v(ni, 0);
v[0] = triangle[0][0];
for (int i = 1; i < ni; i++) {
v[i] = v[i-1] + triangle[i][i];
for (int j = i - 1; j > 0; j--) {
v[j] = min(v[j-1],v[j]) + triangle[i][j];
}
v[0] += triangle[i][0];
}
return *min_element(v.begin(), v.end());
}
};
2020-07-28
33. 搜索旋轉(zhuǎn)排序數(shù)組
AC代碼
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, h = int(nums.size())-1;
while (l <= h) {
int mid = (h-l)/2+l;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] > nums[l]) {
if (target >= nums[l] && target < nums[mid]) {
h = mid - 1;
} else {
l = mid + 1;
}
} else if (nums[mid] == nums[l]) {
if (h == l) {
return -1;
}
l++;
} else {
if (target <= nums[h] && target > nums[mid]) {
l = mid + 1;
} else {
h = mid - 1;
}
}
}
return -1;
}
};
思路
- 二分查找法，由于是兩段有序开皿，分別有幾種情況涧黄，且沒有相等元素
- nums[mid] > nums[l]，說明l-mid為嚴格的升序笋妥，如果target在nums[l]-nums[mid]之間，h=mid-1窄潭，否則l=mid+1。切換到l-h之間搜索
- nums[mid] == nums[l]嚷辅，說明 (l+h)/2 = l, h=l-1 或 h=l
- h=l-1，令l=h
- h=l簸搞，mid=h=l扁位，說明無解域仇，return -1
- nums[mid] < nums[h]，說明mid-h為嚴格升序寺擂，如果target在nums[mid]-nums[h]之間暇务，l=mid+1，否則h=mid-1怔软。切換到l-h之間搜索
74. 搜索二維矩陣
AC代碼
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = int(matrix.size());
if (m <= 0) {
return false;
}
int n = int(matrix[0].size());
int num = m*n;
int l = 0,h = num-1;
while (l <= h) {\\二分查找法
int mid = (h-l)/2+l;
if (matrix[(mid)/n][(mid)%n] == target) {//算出mid對應(yīng)的下標就行
return true;
} else if (matrix[(mid)/n][(mid)%n] > target) {
h = mid-1;
} else {
l = mid+1;
}
}
return false;
}
};
