第一題
LeetCode：4-8刷題 class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> ret;
//維護一個二維數組, 從i 到 j 的乘積, dp[i][j] = dp[i][j - 1] * val[j]
vector<vector<int>> dp(nums.size(), vector<int>(nums.size()));
dp[0][0] = nums[0];
for(int i = 1; i < nums.size(); i++) {
dp[0][i] = dp[0][i - 1] * nums[i];
}
for(int i = 1; i < nums.size(); i++) {
for(int j = i; j < nums.size(); j++) {
if(i == j) dp[i][j] = nums[i];
else {
dp[i][j] = dp[i][j - 1] * nums[j];
}
}
}
for(int i = 0; i < nums.size(); i++) {
int leftVal = i == 0 ? 1 : dp[0][i - 1];
int rightVal = i == nums.size() - 1 ? 1 : dp[i + 1][nums.size() - 1];
ret.push_back(leftVal * rightVal);
}
return ret;
}
};
LeetCode：4-8刷題 class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
//分别構造兩個數組, left & right
vector<int> left(nums.size());
vector<int> right(nums.size());
vector<int> ret(nums.size());
left[0] = 1;
right[nums.size() - 1] = 1;
for(int i = 1; i <= nums.size() - 1; i++) {
left[i] = left[i - 1] * nums[i - 1];
}
for(int j = nums.size() - 2; j >= 0; j--) {
right[j] = right[j + 1] * nums[j + 1];
}
for(int i = 0; i < nums.size(); i++) {
ret[i] = left[i] * right[i];
}
return ret;
}
};
LeetCode：4-8刷題 第二題
如何合并兩個連結清單
1.頭節點head(ListNode*);
2.下一個插入節點的前一個節點tail(ListNode*), tail->next就是要插入的位置
3.第一個連結清單中的某個位置aPtr(ListNode*)
4.第二個連結清單中的某個位置bPtr(ListNode*)
==> 步驟:
head作為哨兵節點, tail->next = aPtr->val < bPtr->val ? aPtr : bPtr;
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0 || (lists.size() == 1 && lists[0] == nullptr)) return nullptr;
/**
1.先合并,再排序?
2.一邊排序一邊合并?
*/
ListNode* head = new ListNode;
ListNode* tail = head;
//head->next = tail;
ListNode* aPtr = lists[0];
ListNode* bPtr = lists[1];
while(aPtr != nullptr && bPtr != nullptr) {
if(aPtr->val < bPtr->val) {
tail->next = aPtr;
aPtr = aPtr->next;
} else {
tail->next = bPtr;
bPtr = bPtr->next;
}
tail = tail->next;
}
//把其中一個後邊還剩的節點接在tail後邊
tail->next = aPtr == nullptr ? bPtr : aPtr;
return head->next;
}
};
LeetCode：4-8刷題 /**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKTwoLists(ListNode* a, ListNode* b) {
if(a == nullptr || b == nullptr) return a ? a : b;
ListNode* head = new ListNode;
ListNode* tail = head;
ListNode* aPtr = a;
ListNode* bPtr = b;
while(aPtr != nullptr && bPtr != nullptr) {
if(aPtr->val < bPtr->val) {
tail->next = aPtr;
aPtr = aPtr->next;
} else {
tail->next = bPtr;
bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = aPtr == nullptr ? bPtr : aPtr;
return head->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0 || (lists.size() == 1 && lists[0] == nullptr)) return nullptr;
ListNode* ans = nullptr;
for(int i = 0; i < lists.size(); i++) {
ans = mergeKTwoLists(ans, lists[i]);
}
return ans;
}
};
LeetCode：4-8刷題 /**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKTwoLists(ListNode* a, ListNode* b) {
if(a == nullptr || b == nullptr) return a ? a : b;
ListNode* head = new ListNode;
ListNode* tail = head;
ListNode* aPtr = a;
ListNode* bPtr = b;
while(aPtr != nullptr && bPtr != nullptr) {
if(aPtr->val < bPtr->val) {
tail->next = aPtr;
aPtr = aPtr->next;
} else {
tail->next = bPtr;
bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = aPtr == nullptr ? bPtr : aPtr;
return head->next;
}
ListNode* merge(vector<ListNode*>& lists, int left, int right) {
if(left == right) {
return lists[left];
}
if(left > right) return nullptr;
int mid = left + (right - left) / 2;
ListNode* lmerge = merge(lists, left, mid);
ListNode* rmerge = merge(lists, mid + 1, right);
return mergeKTwoLists(lmerge, rmerge);
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
};
LeetCode：4-8刷題 第三題
LeetCode：4-8刷題 //深度優先算法
class Solution {
public:
int row;
int col;
int maxcount;
int dfs(vector<vector<int>>& grid, int x, int y) {
//起點是 x, y
if(x < 0 || y < 0 || x >= row || y >= col || grid[x][y] == 0) {
return 0;
}
grid[x][y] = 0;
int temp = 1;
//向上檢索
temp += dfs(grid, x, y - 1);
//向下檢索
temp += dfs(grid, x, y + 1);
//向左檢索
temp += dfs(grid, x - 1, y);
//向右檢索
temp += dfs(grid, x + 1, y);
return temp;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
maxcount = 0;
//對于每一個點,都要進行廣度優先搜尋,每次搜尋到無處再搜尋,計數
row = grid.size();
if(row == 0) return 0;
col = grid[0].size();
//起點節點是(0, 0),臨時計數器為temp
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
maxcount = max(maxcount, dfs(grid, i, j));
}
}
return maxcount;
}
};
LeetCode：4-8刷題 第四題
LeetCode：4-8刷題 //錯誤示範: 去太平洋隻能往左往上走, 去大西洋隻能往右往下走
#define INF INT_MAX / 2
class Solution {
public:
int row;
int col;
//(origin_x, origin_y)是否能到達太平洋
bool taipingyang(vector<vector<int>>& heights, int x, int y) {
if(x <= 0 || y <= 0) return true;
bool up = 0, left = 0;
int temp = heights[x][y];
//向左探索
if(temp >= heights[x - 1][y]) left = taipingyang(heights, x - 1, y);
//向上探索
if(temp >= heights[x][y - 1]) up = taipingyang(heights, x, y - 1);
return up || left;
}
bool daxiyang(vector<vector<int>>& heights, int x, int y) {
if(x >= row - 1 || y >= col - 1) return true;
bool down = 0, right = 0;
int temp = heights[x][y];
if(temp >= heights[x + 1][y]) right = daxiyang(heights, x + 1, y);
if(temp >= heights[x][y + 1]) down = daxiyang(heights, x, y + 1);
return right || down;
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
vector<vector<int>> axis;
//一個坐标(x, y),如果能流到太平洋,則存在一條路徑(向上||向左),直到 x < 0 || y < 0
//一個坐标(x, y),如果能流到大西洋,則存在一條路徑(向下||向右),直到 x == row || y == col
row = heights.size();
if(row == 0) return {};
col = heights[0].size();
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
if(taipingyang(heights, i, j) && daxiyang(heights, i, j)) {
axis.push_back({i, j});
}
}
}
return axis;
}
};
#include <iostream>
#include <stack>
#include <cmath>
using namespace std;
void reversee(int& num) {
int m = 0;
stack<int> S;
int temp;
while(num != 0) {
temp = num % 10;
S.push(temp);
num = num / 10;
}
int idx = 0;
while(!S.empty()) {
m += S.top() * pow(10, idx);
S.pop();
idx++;
}
num = m;
}
int main() {
int num;
cin >> num;
reversee(num);
cout << num << endl;
return 0;
}
