資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時裝研究
法律研究C++ 中的自我交叉
假設我們有一個包含 n 個數字的陣列 x。我們從點 (0,0) 開始，向北移動 x[0] 個單位，然後向西移動 x[1] 個單位，向南移動 x[2] 個單位，向東移動 x[3] 個單位，依此類推。換句話說，每次移動後我們的方向都會逆時針改變。我們必須設計一個具有 O(1) 額外空間的一遍掃描演算法來確定我們的路徑是否自交叉。
因此，如果陣列如下 − [3,4,2,5]
答案將為 true。
要解決這個問題，我們將按照以下步驟操作 −
在 x 的索引 4 處插入 0
n := x 的大小，i := 4
對於 i < n 且 x[i] > x[i - 2]，將 i 加 1，不初始化任何內容，執行 −
什麼都不做
如果 i 等於 n，則返回 false
如果 x[i] >= x[i - 2] - x[i - 4]，則，
x[i - 1] = x[i - 1] - x[i - 3]
對於 i < n 且 x[i] < x[i - 2]，將 i 加 1，執行 −
什麼都不做
當 i 不等於 n 時，返回 true
示例
讓我們看下面的實現，以獲得更好的理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
x.insert(x.begin(), 4, 0);
int n = x.size();
int i = 4;
for(; i < n && x[i] > x[ i - 2];i++);
if(i == n) return false;
if (x[i] >= x[i - 2] - x[i - 4]){
x[i - 1] -= x[i - 3];
}
for (i++; i < n && x[i] < x[i - 2]; i++);
return i != n;
}
};
main(){
Solution ob;
vector<int> v = {3,4,2,5};
cout << (ob.isSelfCrossing(v));
}輸入
{3,4,2,5}輸出
1
更新時間：27-5-2020
207 次瀏覽
廣告