PAT 갑 급 문제 분류 어 셈 블 리 - 이론

58897 단어
본문 은 PAT A 급 분류 어 셈 블 리 시리즈 문장 이다.
 
이론 이라는 문 제 는 저 를 매우 난처 하 게 하 는 문제 입 니 다. 순 전 히 데이터 구 조 를 시험 하기 위해 데이터 구 조 를 시험 하 는 것 입 니 다.Author 란 의 한 선생님 을 보면 데이터 구 조 를 가 르 치 는 선생님 의 생각 이 다른 사람과 다르다 는 것 을 알 수 있다.
번호
표제
분수
부주의
Author
1051
Pop Sequence
25
하나의 시퀀스 가 pop 시퀀스 인지 아 닌 지 를 판단 합 니 다.
CHEN, Yue
1052
Linked List Sorting
25
링크 정렬
CHEN, Yue
1057
Stack
30
중위 기능 이 있 는 stack
CHEN, Yue
1074
Reversing Linked List
25
세그먼트 역전 링크
CHEN, Yue
1089
Insert or Merge
25
삽입 정렬 또는 병합 정렬 판단
CHEN, Yue
1097
Deduplication on a Linked List
25
체인 워 치
CHEN, Yue
1098
Insertion or Heap Sort
25
삽입 정렬 또는 쌓 기 정렬 판단
CHEN, Yue
여러 문제 가 MOOC 에 올 랐 을 때 데이터 구조 문제 집 에서 풀 렸 는데 1051, 1074, 1089 가 있 었 다.그리고 1098. 예전 에 merge 를 할 때 같이 하고 싶 었 는데 나중에 merge 가 너무 오래 걸 려 서 넘 어 갔 어 요.
이번 에는 1074, 1098, 1051, 1057 네 문 제 를 강의 합 니 다.맞 아, 문제 번호 순 으로 안 해.
 
1074：
이것 은 내 가 만 든 첫 번 째 PAT 문제 일 수도 있 고, 첫 번 째 로 걸 린 문제 일 수도 있다.사실 5 비트 정수 로 링크 를 모 의 하 는 모든 문 제 는 100000 크기 의 배열 을 만들어 야 주 소 를 직접 찾 아야 시간 제한 에 들 어 갈 수 있 는 것 같 습 니 다. std::map 안 됩 니 다.하지만 내 가 처음에 C 로 만 들 었 다 면 바로 배열 을 만 들 었 을 것 이 고 뒤의 문제 도 없 었 을 것 이다.
이 문제 의 설명 은 데이터 구조 과정 에 있다.
초기 작품 이 라 코드 가 어색 하고 고치 기 귀찮아 서 자고 싶 어 요.
 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 
 9 struct Node
10 {
11     int address;
12     int data;
13     int next;
14 };
15 
16 int main(int argc, char const *argv[])
17 {
18     int first, n, k;
19     std::cin >> first >> n >> k;
20     std::vector data(n);
21     for (int i = 0; i != n; ++i)
22         std::cin >> data[i].address >> data[i].data >> data[i].next;
23     
24     decltype(data) list;
25     int address = first;
26     for (int i = 0; i != n; ++i)
27     {
28         auto pos = std::find_if(std::begin(data), std::end(data), [address](const Node& node) {
29             return node.address == address;
30         });
31         list.emplace_back(*pos);
32         address = pos->next;
33         if (address == -1)
34             break;
35     }
36     n = list.size();
37 
38     auto begin = list.begin();
39     auto end = begin + (list.end() - begin) / k * k;
40     for (; begin != end; begin += k)
41     {
42         std::stack stack;
43         for (auto iter = begin; iter != begin + k; ++iter)
44             stack.push(*iter);
45         for (auto iter = begin; iter != begin + k; ++iter)
46         {
47             *iter = stack.top();
48             stack.pop();
49         }
50     }
51     for (int i = 0; i != n - 1; ++i)
52         list[i].next = list[i + 1].address;
53     list[n - 1].next = -1;
54     
55     std::cout << std::setfill('0');
56     for (auto& node : list)
57     {
58         std::cout << std::setw(5) << node.address << ' ';
59         std::cout << std::setw(0) << node.data << ' ';
60         if (node.next == -1)
61         {
62             std::cout << "-1";
63             break;
64         }
65         std::cout << std::setw(5) << node.next << std::endl;
66     }
67 
68     return 0;
69 }

 
1098：
그의 형제 문 제 는 1089 데이터 구조 과정 에서 이 문제 에서 도 사용 되 는 판단 삽입 정렬 방법 을 포함한다.
 1 #include 
 2 #include 
 3 #include 
 4 
 5 int main()
 6 {
 7     int size;
 8     std::cin >> size;
 9     std::vector<int> original(size);
10     std::vector<int> partial(size);
11     for (auto& i : original)
12         std::cin >> i;
13     for (auto& i : partial)
14         std::cin >> i;
15 
16     int cur = 1;
17     for (; cur != size && partial[cur] >= partial[cur - 1]; ++cur)
18         ;
19     bool insertion = true;
20     for (auto i = cur; i != size; ++i)
21         if (partial[i] != original[i])
22         {
23             insertion = false;
24             break;
25         }
26     
27     if (insertion)
28     {
29         std::cout << "Insertion Sort" << std::endl;
30         int insert = partial[cur];
31         for (--cur; cur >= 0; --cur)
32             if (partial[cur] > insert)
33                 partial[cur + 1] = partial[cur];
34             else
35                 break;
36         partial[cur + 1] = insert;
37     }
38     else
39     {
40         std::cout << "Heap Sort" << std::endl;
41         int cur = size - 1;
42         auto top = partial[0];
43         for (; cur >= 0; --cur)
44             if (partial[cur] <= top)
45                 break;
46         if (cur >= 0)
47         {
48             std::pop_heap(partial.begin(), partial.begin() + cur + 1);
49             partial[cur] = top;
50         }
51     }
52     auto end = partial.end() - 1;
53     for (auto iter = partial.begin(); iter != end; ++iter)
54         std::cout << *iter << ' ';
55     std::cout << *end;
56 }

사실 이 문 제 는 좀 더 간단 해 야 한다. 왜냐하면 그 문 제 는 스스로 merge 를 써 야 하기 때문에 이 문제 의 힙 은 표준 라 이브 러 리 를 사용 할 수 있다. 제공 하 다 std::pop_heap 등 함 수 는 쌓 기 작업 에 쓰 인 다.더미 요 소 를 보 려 면 시작 교체 기 를 참조 하면 됩 니 다. 표준 라 이브 러 리 는 주지 않 았 습 니 다.
BTW, 쌓 는 작업 은 O (N) 의 것 으로 수학 을 조합 한 다 는 것 을 증명 한다.
그리고 나 는 이 두 문제 가 매우 어색 하 다 고 느낀다.
 
1051：
하나의 서열 이 stack 에서 pop 으로 나 온 서열 인지 아 닌 지 를 판단 합 니 다.
 1 #include 
 2 #include 
 3 #include 
 4 
 5 class Stack : public std::stack<int>
 6 {
 7     using super = std::stack<int>;
 8 public:
 9     explicit Stack(int _cap)
10         : capacity_(_cap)
11     {
12         ;
13     }
14     void push(const int& _data)
15     {
16         if (size() == capacity_)
17             throw 0;
18         super::push(_data);
19     }
20 private:
21     int capacity_;
22 };
23 
24 void check(int _cap, const std::vector<int>& _data)
25 {
26     Stack stack(_cap);
27     int pushed = 0;
28     for (auto i : _data)
29     {
30         if (stack.empty())
31         {
32             stack.push(++pushed);
33         }
34         if (stack.top() < i)
35         {
36             for (int j = pushed + 1; j <= i; ++j)
37                 stack.push(j);
38             pushed = i;
39         }
40         if (stack.top() == i)
41         {
42             stack.pop();
43             continue;
44         }
45         if (stack.top() > i)
46             throw 0;
47     }
48 }
49 
50 int main()
51 {
52     int m, n, k;
53     std::cin >> m >> n >> k;
54     std::vector<int> data(n);
55     for (int i = 0; i != k; ++i)
56         try
57         {
58             for (int j = 0; j != n; ++j)
59                 std::cin >> data[j];
60             check(m, data);
61             std::cout << "YES" << std::endl;
62         }
63         catch(...)
64         {
65             std::cout << "NO" << std::endl;
66         }
67 
68     return 0;
69 }

제목 이 어렵 지 않 습 니 다. 여기 코드 를 붙 이 는 것 은 잘못된 시범 을 보 여 주 려 는 것 입 니 다.알고리즘 자체 가 정확 하고 AC 를 사용 할 수 있 지만 디자인 이 좋 지 않 습 니 다. 표준 라 이브 러 리 의 용기 류 는 기본 클래스 로 사용 되 는 것 이 아 닙 니 다. 구조 함수 가 가상 이 아니 기 때문에 제 가 쓴 것 입 니 다. Stack 직접 상속 std::stack 좋 지 않 습 니 다. 비록 이런 디자인 에서 하위 클래스 의 subclass 는 분석 할 필요 가 없 지만 전체 프로그램 은 파생 류 에서 기본 클래스 로 전환 하 는 지침 을 만 들 지 않 았 습 니 다.제 본 뜻 은 adapter 를 실현 하려 는 것 입 니 다. 게 으 름 을 피 우기 위해 서 는 직접 공유 상속 을 해 야 합 니 다. Stack 클래스 중 하나 포장 std::stack 실례공사 에서 공유 상속 표준 라 이브 러 리 용 기 는 잘못된 것 이다.
 
1057：
이번에 번호 대로 말 하지 않 는 것 은 바로 이 문제 가 압권 이 되 어야 하기 때문이다.
처음 봤 을 때 stack 하나 랑 중위 수 잖 아 요. 둘 다 쓸 줄 알 아 요. 같이 놓 아 도 쓸 줄 알 아 요.그리고 제 가 첫 번 째 버 전 을 써 서 하나 만 들 었 어 요. std::stack 의 adapter 는 push, pop, median 작업 을 제공 합 니 다. 그 중에서 median 은 stack 복사, 정렬, 주소 지정 중위 수 입 니 다.느낌 이 좋 고 사례 도 지 났 으 니 AC 를 생각해 보 세 요.
 1 #include 
 2 #include <string>
 3 #include 
 4 #include 
 5 
 6 class Stack
 7 {
 8 public:
 9     Stack() = default;
10     void push(int i)
11     {
12         stack.push_back(i);
13     }
14     void pop()
15     {
16         if (stack.empty())
17             std::cout << "Invalid";
18         else
19         {
20             std::cout << stack.back();
21             stack.pop_back();
22         }
23         std::cout << std::endl;
24     }
25     void median()
26     {
27         if (stack.empty())
28             std::cout << "Invalid";
29         else
30         {
31             auto temp = stack;
32             std::sort(temp.begin(), temp.end());
33             int m = 0;
34             if (temp.size() % 2)
35                 m = temp[(temp.size() - 1) / 2];
36             else
37                 m = temp[temp.size() / 2 - 1];
38             std::cout << m;
39         }
40         std::cout << std::endl;
41     }
42 private:
43     std::vector<int> stack;
44 };
45 
46 int main()
47 {
48     int count;
49     std::cin >> count;
50     Stack stack;
51     for (int i = 0; i != count; ++i)
52     {
53         std::string instr;
54         std::cin >> instr;
55         if (instr == "Push")
56         {
57             int i;
58             std::cin >> i;
59             stack.push(i);
60         }
61         else if (instr == "Pop")
62         {
63             stack.pop();
64         }
65         else
66         {
67             stack.median();
68         }
69     }
70 }

하지만 그렇지 않다.케이스 5 개, 시간 초과 3 개.
예. std::cin 문자열 읽 기 가 너무 느 립 니까?C 의 입 출력 으로 바 꾸 고 2 개의 case 가 시간 을 초과 합 니 다.
그리고 나 서 나 는 데 이 터 를 입력 하 는 데 비교적 작은 범위 가 유용 하 다 고 생각 하여 배열 을 만 들 고 난잡 한 방문 통 제 를 써 서 매번 에 모든 요 소 를 한 번 씩 방문 하 는 것 을 방지 했다.소 용 없어, 시간 초과 야.
나 는 선형 구조 가 이 문 제 를 해결 할 수 없다 는 것 을 깨 달 았 다. 그렇지 않 으 면 이 30 점 에 떳떳 하지 못 할 것 이다.그래서 std::map 저장 하 러 왔어요.먼저 코드 넣 기:
  1 #include 
  2 #include <string>
  3 #include 
  4 #include 
  5 
  6 class Median
  7 {
  8 public:
  9     Median() = default;
 10     int get()
 11     {
 12         return median;
 13     }
 14     void insert(int i)
 15     {
 16         if (median_count == 0)
 17         {
 18             median = i;
 19             median_count = 1;
 20         }
 21         else if (i < median)
 22             ++small[i], ++small_count;
 23         else if (i > median)
 24             ++large[i], ++large_count;
 25         else
 26             ++median_count;
 27         adjust();
 28     }
 29     void erase(int i)
 30     {
 31         if (i < median)
 32         {
 33             --small[i], --small_count;
 34             if (small[i] == 0)
 35                 small.erase(i);
 36         }
 37         else if (i > median)
 38         {
 39             --large[i], --large_count;
 40             if (large[i] == 0)
 41                 large.erase(i);
 42         }
 43         else
 44             --median_count;
 45         adjust();
 46     }
 47 private:
 48     std::map<int, int, std::greater<int>> small;
 49     int small_count = 0;
 50     std::map<int, int> large;
 51     int large_count = 0;
 52     int median;
 53     int median_count = 0;
 54     void small_to_median()
 55     {
 56         median = small.begin()->first;
 57         median_count = small.begin()->second;
 58         small.erase(small.begin());
 59         small_count -= median_count;
 60     }
 61     void large_to_median()
 62     {
 63         median = large.begin()->first;
 64         median_count = large.begin()->second;
 65         large.erase(large.begin());
 66         large_count -= median_count;
 67     }
 68     void median_to_small()
 69     {
 70         small[median] = median_count;
 71         small_count += median_count;
 72     }
 73     void median_to_large()
 74     {
 75         large[median] = median_count;
 76         large_count += median_count;
 77     }
 78     void adjust()
 79     {
 80         if (median_count == 0)
 81         {
 82             if (small_count < large_count)
 83                 large_to_median();
 84             else if (small_count)
 85                 small_to_median();
 86         }
 87         else if (small_count + median_count < large_count)
 88         {
 89             median_to_small();
 90             large_to_median();
 91         }
 92         else if (small_count >= median_count + large_count)
 93         {
 94             median_to_large();
 95             small_to_median();
 96         }
 97     }
 98 };
 99 
100 class Stack
101 {
102 public:
103     Stack() = default;
104     void push(int i)
105     {
106         stack_.push(i);
107         median_.insert(i);
108     }
109     void pop()
110     {
111         if (stack_.empty())
112             std::cout << "Invalid";
113         else
114         {
115             int i = stack_.top();
116             stack_.pop();
117             std::cout << i;
118             median_.erase(i);
119         }
120         std::cout << std::endl;
121     }
122     void median()
123     {
124         if (stack_.empty())
125             std::cout << "Invalid";
126         else
127         {
128             std::cout << median_.get();
129         }
130         std::cout << std::endl;
131     }
132 private:
133     std::stack<int> stack_;
134     Median median_;
135 };
136 
137 int main()
138 {
139     int count;
140     std::cin >> count;
141     Stack stack;
142     for (int i = 0; i != count; ++i)
143     {
144         std::string instr;
145         std::cin >> instr;
146         if (instr == "Push")
147         {
148             int i;
149             std::cin >> i;
150             stack.push(i);
151         }
152         else if (instr == "Pop")
153             stack.pop();
154         else
155             stack.median();
156     }
157 }

이 알고리즘 은 매우 복잡 하 다.클 라 이언 트 유지 보수 Stack 실례 Median 실례 지만, 두 가 지 는 모두 내 가 쓴 부류 이다.Median 두 개 포함 std::map 예 를 들 어 중위 보다 작은 숫자 와 중위 보다 큰 숫자 를 각각 저장 합 니 다.핵심 알고리즘 은 Median::adjust() ，그것 은 양쪽 내용 을 조정 함으로써 중위 수의 정확성 을 유지한다.자세히 말 하고 싶 지 않 으 니 코드 를 보 세 요. std::map 기본 적 인 조작 들
두 번 의 조정 사이 에는 하나의 조작 만 있 기 때문에 한 번 의 조정 을 보장 할 수 있 으 면 좋 겠 다.
토로 할 만 한 점 은 C + + 의 입 출력 이 이 문제 에서 C 보다 100 ms 느 렸 다 는 것 이다.그러나 알고리즘 이 맞지 않 아 입 출력 이 아무리 빨 라 도 시간 을 초과 해 야 한다.PAT 는 입 출력 시간 에 대한 카드 문제 가 별로 없 는 것 같 습 니 다. 왜냐하면 세상 에는 C 와 C + + 를 제외 하고 프로 그래 밍 언어 가 많 기 때문에 그들의 느낌 을 고려 해 야 합 니 다.
 
쓰 고 보 니 다른 블 로그 에 서 는 이렇게 귀 찮 은 방법 이 없 었 다. 마치 나무 모양 의 배열 을 사용 한 것 같 았 다. 나 는 할 줄 몰 랐 다.
 1 try
 2 {
 3     learn_queue.push("    ");
 4 }
 5 catch(...)
 6 {
 7     std::cout << "    " << std::endl;
 8 }
 9 
10 --------------------------------------------------------------------------------
11     
12 Program exited with code 0...

마침 나무 얘 기 가 나 왔 으 니 다음 편 에는 나 무 를 쓰 세 요.
자바 의 springMvc 프레임 워 크 간단 실현
c 언어 로 단일 체인 표 의 기본 조작 을 실현 합 니 다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage