Patrick Wezhi Xu

LeetCode Weekly Contest 156 and others

Second week of LeetCode Challenge. Participated the virtual contest. Weekly Contest 156 1207. Unique Number of Occurrences Brute force. Record total occurrence of each number and iterate over it to see if there is any duplication. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: bool uniqueOccurrences(vector<int>& arr) { unordered_map<int, int> occ; unordered_map<int, bool> flag; for (int i = 0; i < arr.

LeetCode Weekly Contest 155 and others

This is the first week of LeetCode Challenges. It includes weekly contest 155 and other problems. Weekly Contest 155 1200. Minimum Absolute Difference Brute force. Find the minimum absolute difference and then iterate the list again to output the pairs with minimum absolute difference. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public: vector<vector<int>> minimumAbsDifference(vector<int>& arr) { vector<vector<int>> ans; if (arr.

CLDictP: A Command-Line Dictionary Tool

A command line dictionary written in Perl using Merriam-Webster APIs. This is my first project using Perl. I feel it is tedious to type formatted definitions to Quizlet(A website which can make flashcards for you) and I’m too lazy to open browser and online dictionary pages. Why not combining these two? It uses following APIs: Merriam-Webster Learner Merriam-Webster Collegiate For each entry, it contains:

Static Linked List - Another Way To Represent Graphs

Static Linked List is a data structure that stores linked list in static arrays. It is usually used to represent graphs. It is very interesting that its Chinese name literally translated as “Linked Forward Star”. You have two choices of paths to understand this. Start from Forward Star. Start from Adjacency List. However, I would recommend to explore both ideas to have a better understanding.

POJ 3279 Fliptile

There are \(M \times N\) \((1 \le M, N \le 15)\)square tiles. Each tile can be flipped and the color of tile can change between black(1) and white(0). When you flip a tile, 4 adjacent tiles will also be flipped. Note that the four adjacent flipped tiles will NOT cause their adjacent tiles to flip. Given a configuration, find the minimum number of flips so that all square tiles become white.

Build a Proxy Server to Access Chinese IP Including Netease Music

Sometimes we need to access Chinese content, like Youku Video, Netease Music (Cloud Music) and QQ music. It is very annoying to get “Can Only Be Streamed in Mainland China” or similar messages. Being tired of that, fortunately I have got a VPS from Aliyun and I build a proxy server using Shadowsocks on it and everything works smoothly now. VPS You need to have a VPS with Chinese IP address, there are tons of choices, like Aliyun(Alibaba Cloud) and Tencent Cloud etc.

USACO Party Lamps

A set of \(N\) \((10 \le N \le 100)\) lamps, numbered from 1 to N. Four types of button: Button type Usage 1 flip all lamps (On to Off, Off to On) 2 flip odd numbered lamps (e.g. 1, 3, 5) 3 flip even numbered lamps (e.g. 2, 4, 6) 4 flip \(3k+1 ; with ; k \ge 0\) numbered lamps (e.

POJ 3268 Silver Cow Party

There are one cow from each \(N\) (\(1 \le N \le 1000\)) farms want to go to the number X farm to have a party, hurrah! One cow from each farm need to go to the party and go back. There are \(M\) (\(1 \le M \le 100,000\)) weighted (represents time) one-direction roads connects pairs of roads. Cows are smart though, they want to go via the shortest path. The question is, what is the longest time the cow will take.

UVa 108 Maximum Sum

Given an array with size \(N \times N (N \le 100)\), find the maximum value of its subarray. Link: Problem on UVa Solutions First thought is to brute force - find all possible subarrays then the time complexity will be \(O(N^6)\). TLE for sure. Then comes up with an algorithm that takes \(O(N^4)\), which is enough to AC. However, it can be \(O(N^3)\), see solution 2. Solution 1 We build a sum array which is the sum of the numbers in rectangle area with the top-left of the array and bottom-right node \(i, j)\).

UVa 443 Humble Numbers

Find \(n\)th \( (1 \le n \le 5842)\) number whose only prime factors are 2, 3, 5 or 7. Link: Solutions Solution 1 Kind of brute force, using STL set and vector to list all humble numbers. Using long long to avoiding overflow. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include<iostream>#include<vector>#include<set>using namespace std; typedef long long ll; const int t[] = { 2, 3, 5, 7}; set<ll> s; int main(void) { s.

POJ 2376 Cleaning Shifts

\(N\) (\(1 \le N \le 25,000\)) cows, each cow only available for a interval of time. \(T\) (\(1 \le T \le 1,000,000\)) shifts. Find minimum number of cows to complete \(T\) shifts. Link: Notes Each shift must has at least one cow assigned to it. A cow finishes after the end time. That is, if there are two cows, start and end at \((1, 3)\) and \((4, 10)\) respectively.