今日推薦開源項目：《文字識別 tesseract.js》
今日推薦英文原文：《Do You Know How to Solve These Programming Problems?》
今日推薦開源項目：《文字識別 tesseract.js》傳送門：GitHub鏈接
推薦理由：OCR——Optical Character Recognition，即光學字元識別，簡單地說就是獲取特定圖片上的文字的過程。這個項目是純 JS 實現的各種語言的 OCR，除了常用的中英文以外提供了相當多語言的支持以防患於未然，即使拋開不常用的語言不提，這個項目的功能依然足夠日常使用，通過項目提供的各種示例可以輕鬆上手。
今日推薦英文原文：《Do You Know How to Solve These Programming Problems?》作者：Daan
原文鏈接：https://medium.com/better-programming/do-you-know-how-to-solve-these-programming-problems-18d04defc05e
推薦理由：一些演算法小題目
Do You Know How to Solve These Programming Problems?
Can you wrap your head around all of them?
Programming is about solving problems. In this piece, I』ve listed six programming problems from several sites that contain programming problems. The problems in this listed are sorted based on how difficult they are to solve — with number one on this list being the easiest, and number six being the most difficult to solve. Can you wrap your head around all of them? I provided the solutions to these programming problems, coded in PHP, at the bottom of this article. You can choose a programming language of your choice to solve these problems. Good luck solving these problems, and happy coding! Challenges1. Plus Minus
Let』s start with a relatively easy problem provided by HackerRank. This challenge is categorized as a warmup.
2. Two Sum
A challenge that』s considered easy, provided by LeetCode.
3. Largest palindrome product
This problem is provided by Project Euler and is considered one of the more easy problems. It』s currently solved by more than 455,000 people.
4. Distinct powers
Another challenge from Project Euler. This one is a little bit harder than the previous problem. It』s solved by around 100,000 people.
5. Kaprekars Constant
If you』ve made it up to this point: Congratulations! It』s time to start the first hard challenge. This challenge is provided by Coderbyte.
6. Swap Nodes in Pairs
Definitely the toughest challenge so far, this challenge is provided by LeetCode. Although it』s considered to be of medium difficulty, I found this one harder to solve than the Kaprekars Constant. This one requires you to know how linked lists work.
Solutions
1. Plus Minus
A really great problem to get you started with a solution that』s really straightforward.<?php
function getFractionals($numbers) {
$length = count($numbers);
$results = [
'positive' => 0,
'negative' => 0,
'zero' => 0,
];
for ($i = 0; $i < $length; $i++) {
if ($numbers[$i] < 0) {
$results['negative'] += 1;
} else if ($numbers[$i] > 0) {
$results['positive'] += 1;
} else {
$results['zero'] += 1;
}
}
return [
$results['positive'] / $length,
$results['negative'] / $length,
$results['zero'] / $length
];
}
print_r(getFractionals([1, 1, 0, -1, -1])); // [0.4, 0.4, 0.2]
print_r(getFractionals([-4, 3, -9, 0, 4, 1])); // [0.5, 0.3333, 0.16667]
2. Two Sum
Although this one』s a little bit harder than the first problem, you shouldn』t have too much trouble solving this one. I used a simple brute-force approach.<?php
function twoSum($numbers, $target) {
for ($i = 0; $i < count($numbers); $i++) {
for ($j = $i + 1; $j < count($numbers); $j++) {
if ($numbers[$j] + $numbers[$i] === $target) {
return [$i, $j];
}
}
}
}
print_r(twoSum([2, 7, 11, 15], 9)); // [0, 1]
print_r(twoSum([2, 7, 11, 15], 17)); // [0, 3]
3. Largest palindrome product
The solution I came up with has the advantage it can be used to find the biggest palindrome that』s the product of any two x-digit numbers. I』ve also added stop conditions to avoid unnecessary extra looping.<?php
function isPalindrome($number) {
return (string) $number === strrev((string) $number);
}function getBiggestPalindrome($digits) {
$start = pow(10, $digits) - 1;
$max = 0;for ($i = $start; $i > 0; $i--) {
if ($i * $start <= $max) {
break;
}for ($j = $start; $j > 0; $j--) {
$product = $i * $j;if ($product < $max) {
break;
}if ($product > $max && isPalindrome($product)) {
$max = $product;
}
}
}return $max;
}
echo getBiggestPalindrome(2); // 9009
echo getBiggestPalindrome(3); // 906609, which is 993 * 913
4. Distinct powers
I solved the distinct powers problem by going the brute-force route. Add each result to the array, and then remove duplicates from the array. The last step is to sort the array.<?php
function distinctPowers($min, $max) {
$numbers = [];
for ($i = $min; $i <= $max; $i++) {
for ($j = $min; $j <= $max; $j++) {
$numbers[] = pow($i, $j);
}
}
$unique_numbers = array_unique($numbers);
sort($unique_numbers);
return $unique_numbers;
}
echo print_r(distinctPowers(2, 5), 1); // [4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125]
echo print_r(count(distinctPowers(2, 100)), 1); // 9183 distinct terms
5. Kaprekars Constant
The Kaprekars Constant problem is a little bit harder to solve. It』s the first problem in this list that requires recursion to solve the problem.function KaprekarsConstant($number, $numberOfIterations = 1) {
$number = (string) $number;
if (strlen($number) < 4) {
for ($i = strlen($number); $i < 4; $i++) {
$number .= '0';
}
}
$asc = str_split($number);
$desc = $asc;
rsort($desc);
sort($asc);
$asc_number = (int) implode($asc, '');
$desc_number = (int) implode($desc, '');
$difference = abs($asc_number - $desc_number);
if ($difference !== 6174) {
return KaprekarsConstant($difference, $numberOfIterations + 1);
}
return $numberOfIterations;
}
echo KaprekarsConstant(2111); // 5
echo KaprekarsConstant(9831); // 7
A screenshot of passing all test cases
6. Swap Nodes in Pairs
This one took me a while to figure out. The trick in my solution is to pass variables by reference instead of by value. Still, this one might take some time to get your head around.function swapPairs($head) {
$current = &$head;
while (!is_null($current->next)) {
$nextValue = $current->next->val;
$temp = &$current;
$temp->next->val = $temp->val;
$temp->val = $nextValue;
$current = &$current->next->next;
}
return $head;
}
下載開源日報APP：https://openingsource.org/2579/
加入我們：https://openingsource.org/about/join/
關注我們：https://openingsource.org/about/love/
