Как решать задачи на leetcode python

Leetcode Algorithm Questions in Python 3

Remark: If one realizes that this is actually the Fibonacci sequence, he could choose to use the explict formula as in Wikipedia: Fibonacci number.

344. Reverse String

Analysis: Use head to store the head of the unchanged part of the list, and use tail to store the tail. Then exchange their positions.

58. Length of Last Word

Analysis: First use the .strip() method to remove any empty space in the beginning and in the end of the string. Then count how many non-empty letters in the tail (from right to left) until we reach to the first empty space.

231. Power of Two

Analysis: One can of course do it in a recursive fashion, that is, divide n by 2, check the remainder: if it is non-zero, stop and return False ; otherwise, update n=n/2 and repeat. If in the end we get n=1 , return True .

However there is an clever one-liner using the bitwise operations such as & and | :

For a good explaination of the Python bitwise operators, see Here. So the idea of the above solution is: if n<=0 , return False . For the second part, n&(n-1)==0 , any positive integer n is represented uniquely as a sequence of bits, that is, 1 s and 0 s. However, n is a power of 2 if and only if the bit form of n looks like 10. 0 , where there is only a leading 1 , and the rest are all 0s. In that case, the bit form of n-1 is 01..1 . Therefore the bitwise and operator n&(n-1) will give a sequence of 0s, since at each corresponding position for the bit forms of n and n-1 , there is always a 0 and a 1 . Meanwhile, if n is not a power of 2, then in the bit form of n , there are at least two 1 s, say . 1. 1. . A moment thinking will lead to the conclusion that the bit form of n-1 will have 1 in the first position, as . 1. *. , therefore the outcome of n&(n-1) is never 0!

217. Contains Duplicate

Analysis: Change the list to set, then compare the lengths of the list and the set.

204. Count Primes

Analysis:

1. Build a logic list res to store whether the integers for 0 to n-1 are prime or not.
2. Initial conditions: 0 and 1 are not primes, so set the first two elements in list to be False , while set the third element (which corresponds to 2) to be True .
3. Using a for loop, we update the list res : if i is a prime, then 2*i , 3*i , etc. are all non-prime.
4. We count how many True are in res .

263. Ugly Number

Analysis:

1. If num is strictly greater than 1, we keep trying to reduce it, by dividing num by 2,3,5 , if divisible.
2. We use the logic variable ugly to track whether num is divisible by 2,3,5 or not.

202. Happy Number

Analysis:

Use a list called history to store the history of numbers we obtain. The variable tail is the current last element in history .

If tail is not 1, we continue the process to add numbers to history .

Each time we add an element to history , we check whether this element has appeared before. If so, then we will get an infinite loop, so we stop the loop.

Once we break the loop, we check whether tail is 1 or not. If 1, then this number is happy; otherwise, it is an unhappy number.

268. Missing Number

Analysis: Sort the list first, then compare the position k with its value nums[k] .

Another direct solution (kinda cheating imo):

171. Excel Sheet Column Number

Analysis: First build a dictionary to indicate which number each letter in the alphabet to stand for. Then s in basically a number in the 26 system. We just need to transform it into a number in the decimal system.

169. Majority Element

Analysis:

1. Compute L = len(nums)//2 , which is the least number of repetitions for the majority element.
2. Sort the list nums .
3. For each element i in the set formed from elements in nums , get its index in the sorted list ind , then check if the ind + L th element is equal to i . If so, we captured the majority element!

121. Best Time to Buy and Sell Stock

Analysis:

1. We use MAX_step to denote the maximal profit if one chooses to sell on the k th day. Note that this quantity can be negative.
2. MAX_step at k can be obtained from the MAX_step at k-1 : it equals the maximal value between prices[k]-prices[k-1] and MAX_step+prices[k]-prices[k-1]) .
3. In the for loop, we inductively update the current max profit if one chooses to sell the stock on the 1<=i<=k day.

122. Best Time to Buy and Sell Stock II

Analysis: Now we allow multiply transactions, this will lead to different analysis.

1. We use P to denote the total profit, buy the last buy date, and sell the last sell date.
2. If the next day price is lower or equal to the price of the previous day, the buy date will move forward, to generate more profit. buy will stop move forward once positive profit is possible, that is, prices[buy+1] > prices[buy] .
3. Once buy is fixed, we consider sell . First set sell = buy + 1 (recall that we will always have prices[sell] > prices[buy], due to how we work with buy in the previous step). sell will move forward if the price keeps increasing strictly. Once the price stops to increase strictly, sell stops moving forward.
4. Once we obtain sell and buy for the next transaction, we update the profit by P=P+prices[sell]-prices[buy] .

198. House Robber

219. Contains Duplicate II

Analysis:

1. The idea is very similar to Problem 217. We just need to check that whether any chunk of length k+1 contains duplicates.
2. Instead of use set() to convert a chunk of the list into a set, we use a little trick here: first we find the set from the first chunk. Then as we move to the right, we remove the first element nums[step-1] from the set, and then add the next element nums[step+k] to the set.

172. Factorial Trailing Zeroes

Analysis: It is the same as count the exponent of 5 in the prime factorization of n-factorial. We first see how many numbers from 1 to n are divisible by 5 : n//5 . For the numbers which can be divided by 25, we have to count them twice, the first time is already included in the previous step, so we need to add how many numbers can be divided by 25, which can be obtained by (n//5)//5 . We continue until the remainder is 0.

168. Excel Sheet Column Title

167. Two Sum II — Input array is sorted

3. Longest Substring Without Repeating Characters (M)

Analysis: s_n is the longest substring without repeating characters which ends at the n th position. L_n = len(s_n) and L is the current maximal length.

4. Median of Two Sorted Arrays (H)

For a detailed explanation of the solution, see https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/Share-my-O(log(min(mn))-solution-with-explanation.

21. Merge Two Sorted Lists

83. Remove Duplicates from Sorted List

876. Middle of the Linked List

String Permutation

Problem Statement: Given a string, write a function that uses recursion to output a list of all the possible permutations of that string. If a character is repeated, treat each occurence as distinct, for example an input of ‘xxx’ would return a list with 6 “versions” of ‘xxx’

For example, given s=’abc’ the function should return [‘abc’, ‘acb’, ‘bac’, ‘bca’, ‘cab’, ‘cba’]

141. Linked List Cycle

The first solution is simply recording all the appeared nodes in a set, and traverse the linked list. Each step we check whether the next node is in the appeared list, if yes, then there is cycle, otherwise no cycle.

The second approach is to traverse the linked list in two difference paces, one is slow and one is fast . If there is a cycle, then before the fast one hit None , he will catch up with the slow one.

Leetcode 934. Разбор задачи на Python с использованием dfs + bfs

Всем привет. Сегодня попробую объяснить моё решение задачи с сайта Leetcode на языке программирования Python.

Формулировка задачи (мой перевод):

Вам дана двоичная матрица размера n x n, где 1 представляет сушу, а 0 представляет воду.

Остров — это 4-направленно связанная группа 1, не связанная ни с какими другими 1. В сетке ровно два острова.

Вы можете изменить 0 на 1, чтобы соединить два острова в один остров.

Возвращает наименьшее количество нулей, которое нужно перевернуть, чтобы соединить два острова.

Официальная формулировка задачи:

1. Для начала я предлагаю найти 1-ый остров в матрице, с помощью обхода в глубину (dfs), если мы нашли элемент 1-го острова, тогда меняем значение в двумерной матрице на 2. Для экономии времени мы будем заранее заполнять очередь для будущего обхода в ширину (bfs).

2. С помощью обхода в ширину мы найдем кратчайший путь до 2-го острова, для этого мы заполнили очередь координатами элементов 1-го острова.

From Zero to Hero: определите ваш уровень решения LeetCode задач от 1 до 5

В этой статье я хочу написать про мой опыт взаимодействия с платформой LeetCode, и описать свою подготовку к интервью в FAANG подобные компании путём разбиения её на уровни.

Вся статья написана исходя из моего опыта, цифры очень грубые, не претендую на объективность, возможно, существуют лучшие практики, как решать LeetCode задачи, будет круто, если вы поделитесь в комментариях своим опытом.

Уровень -1. Отброс. Решенных задач меньше 10

Как определить

Вы тупой (шутка!). 100% решаемых задач на этом уровне — Easy -. Да, в заголовке написано, что их 5, но я выделил этот уровень, потому что это был мой уровень вначале, и думаю уровень многих, кто в жизни не делал такие задачи.

На этом уровне ты не можешь решить самую первую и популярную задачу на LeetCode — Two Sum любыми способами, брут форс, оптимально, неважно.

Как пройти на следующий уровень

Время, которое понадобится вам, чтобы перейти на следующий уровень около 2-5 часов без перерыва.

Все достаточно просто, на этом уровне не нужно копаться в алгоритмах и структурах данных, надо привыкнуть к самой платформе, понять структуру задач, нужно прочитать внимательно описание задачи, посмотреть на примеры, которые нам дают (input) и что нужно получить (output), засамбитить задачку и понять, что есть такое понятие, как edge cases, когда ваше решение покрывает 3 примера, которые вам дали, но остальные 60 test cases почему-то валятся.

После того как всё-таки покрыли все кейсы, посмотрите решение других ребят в разделе Solutions, которые сделали решение лучше, чем у вас, графики Runtime и Memory. Пока не надо брать в голову, что это за графики, все это изучите на следующем уровне.

Вам нужно решить самые простые задачи на литкоде, они похожи на те, что вы решаете на работе 🙂 Где их найти? Всё очень просто. Идёте в Problems -> Easy -> Сортируете по Acceptance.

Поиск самых легких задач на LeetCode

Смотрите на первые 20 задач и решаете те, которые вам понравились, нужно решить около 10. Решать без разницы как, можно самым глупым брутфорсом, в своей любимой среде со всеми подсказками (но не надо, пожалуйста, использовать ChatGPT:), главное — пройти тесты и почувствовать наконец вкус победы на литкоде. Самый лучший путь к мотивации это маленькие победы, не забывайте об этом, поехали дальше!

Уровень 1. Нуб. Решенных задач 10-50

Как определить

100% решаемых задач на этом уровне — Easy.

Вы уже можете решить задачки с уровнем Acceptance 70-80% брут форсом в любимой среде разработки. Понимаете самые простые структуры данных — массивы, словари, связные списки, очереди, стек. Алгоритмы вы, конечно, используете, но не вникаете, что там внутри, просто набираете .sort()

Как пройти на следующий уровень

Время, которое понадобится вам, чтобы перейти на следующий уровень около 25-40 часов без перерыва.

Чтобы пройти на следующий уровень, вам нужна БАЗА. Вы должны пострадать на этом уровне, зато дальше будет куда легче. Вам нужно взять ручку и тетрадку и пойти штудировать алгоритмы и структуры данных. Предлагаю начать с изучения ресурса neetcode.io, особенно его RoadMap, потому что сам им пользуюсь и считаю лучшим ресурсом, для тех, кто вкатывается в алгоритмы.

Roadmap от Neetcode

Выбираете первый раздел, что же там? Ах да, массивы. Если вы поймали себя на мысли, что да пф-ф, что там массивы, что я там не видел, то, пожалуйста, прошу, пойдите и почитайте несколько статей, проконспектируете, порисуете, вбейте в голову, как выглядит этот самый массив, никогда не будет лишним освежить свои знания. Также изучите сложность вставки, удаления и чтения.

Да, здесь внимательно. Если вы до этого не изучили подробно, что такое Big O, идите, пожалуйста, почитаете, проконспектируете и посмотрите несколько видео как он рассчитывается, по времени и по памяти. Ок, теперь вы понимаете, что же это были за графики Runtime и Memory после решения задач.

Теорию нужно закрепить практикой, открываете определённый раздел и решаете все Easy задачи (если хочется больше, можно перейти на вкладку Practice в NeetCode All). И дальше по списку, изучаете теорию представленных разделов, закрепляете практикой easy задачами. На этом этапе нет смысла спускаться дальше уровня Priotity Queue — Graphs — 1DP по роадмапу.

Универсальный совет, как решать задачи, который я много раз слышал, и сам применяю на практике. Устанавливаете таймер в 45 минут, если вы за половину не решили, идёте и смотрите видео решения (алгоритм, без кода!) от NeetCode или других блогеров, пытаетесь реализовать алгоритм в коде. Если уж здесь не получилось, то внимательно переписываете решение и вникаете, что происходит в коде, дебажите и смотрите каждый шаг. Будет хорошо, если вы в комментариях к коду опишете каждый шаг, что происходит, чтобы точно удостовериться, что вы поняли решение.

Уровень 2. Новичок. Решенных задач 50-100

Как определить

70% решаемых задач на этом уровне — Medium, другие 30% — Easy

Вы большой молодец! По моим подсчётам (Solves problems -> beats) этот уровень достигают <25% всех программистов со всего мира.

Наконец, вы можете без подглядки решить задачу типа TwoSum брут форсом, и даже возможно, оптимально. Вы уже понимаете такие структуры данных как деревья, графы, приоритетная очередь, решали задачи разными красивыми способами: two pointers, binary search, sliding window и т.д.

Скорее всего, вы решаете большинство задач с подсказками, глядя на условие, вы понимаете, как решать задачи, какой алгоритм использовать, какое оптимальное решение нужно, но не можете написать это в коде.

Как пройти на следующий уровень

Время, которое понадобится вам, чтобы перейти на следующий уровень, около 25-40 часов без перерыва.

На этом уровне нужно решать оставшиеся миддл задачи из роадмапа ниткода. По моему опыту, миддл задачи отличаются большим количеством edge cases, и более запутанными условиями задачи, алгоритмы и структуры данных такие же.

Если на easy задаче нужно было просто использовать binary search (возможно даже что в условиях задачи это говорится прямо) для того, чтобы найти определённое число из отсортированного массива, на medium нужно сначала отсортировать (возможно, например, это может быть не просто массив, а более сложная структура данных), потом использовать binary search, потом ещё сделать какую-то манипуляцию, чтобы получить ответ. На easy догадаться, что в определённой задаче нужно использовать тот иной алгоритм в разы легче, на medium для этого нужно сначала провести какие-то манипуляции с вводными данными и дальше уже использовать алгоритм, который позволит оптимально сделать данную задачу.

На этом уровне нужно закончить с теорией Computer Science, для этого неплохо бы изучить более углубленно такие алгоритмы, как динамическое программирование, рекурсия, backtracking, greedy, алгоритм разделяй и властвуй, алгоритм флойда, алгоритм гауса, более сложные структуры данных, разные варианты деревьев, какие бывают графы и способы оптимального решения таких задач (DFS, BFS).

Популярные алгоритмы

По мере решения задач из роадмапа, вы столкнётесь со всеми этими алгоритмами и структурами данных. Если вам хочется больше, идёте в NeetCode All и берёте задачу оттуда. Также в литкоде можно отсортировать задачи по тегам, например, динамическое программирование, Problems -> Tags.

Поиск задач определенной тематики

Уровень 3. Любитель. Решенных задач 100-300

Как определить

90% решаемых задач на этом уровне — Medium, 5% — Easy, 5% — Hard

Когда у вас 100 решённых задач вы уже должны знать все алгоритмы и структуры данных, которые могут попасть в 99% задач на литкоде и, в общем, в алгоритмических секциях на собеседованиях. Уровень написания вашего кода должен быть доведён до автоматизма, вы должны быстро понимать какая структура данных, как пройтись, как изменить определённый элемент, какими способами лучше решать оптимально задачу на ту или иную структуру данных, как работает рекурсия, в каком месте ставить указатели, как определить миддл из массива чисел, как крутить деревья в конце концов! Вы должны быть профи в основах Computer Science. Если это еще не так, стоит остановиться и пройтись по всей теории, чтобы больше не тратить на нее время, потому что дальше будет только практика. Прочитать можно, например, эту книжку, она легко читается, но я бы посоветовал еще почитать другие статьи и посмотреть несколько видео.

Грокаем алгоритмы от Адитья Бхаргава

Как пройти на следующий уровень

Время, которое понадобится вам, чтобы перейти на следующий уровень около 150-200 часов без перерыва

Думаю, на этом уровне, многие будут бросать заниматься на литкоде, думая, что они уже могут пройти собеседование. Я считаю, что этого недостаточно, потому что, даже если вы можете решать какие-то задачи без подсказок и укладываетесь в лимит времени, на самом собеседовании уровень вашего стресса будет совершенно другим, и вы с большой вероятностью зафейлите.

Для того чтобы достигнуть следующего уровня, нужно только решать и решать задачки, преимущественно middle, потому что с большой вероятностью на собеседовании вас спросит именно их, так что лучше довести до автоматизма решение таких задачек оптимальным способом.

На собеседовании у вас будет 45 минут на решение задачи, это вместе с объяснением условий задачи. На этом этапе вам нужно стремиться к решению задачи оптимальным способом за 25 минут, потому что собеседующий может добавить follow up к задаче и вы должны его решить в изначальное отведенное время. Достигаете 300 задач и поехали дальше!

Уровень 4. Эксперт. Решенных задач 300-1000

Как определить

70% решаемых задач на этом уровне — Medium, 25% — Hard, 5% — Easy

Это уровень, где вы уже можете подаваться в FAANG подобные компании, если вы в нижней границе решенных задач, вы можете пройти, если вам повезет с интервьюером и задачки будут +- в отраслевых стандартах, без заковыристых edge cases и кучи динамического программирования.

Оптимально, если вы решили 500-600 задач, редко видел отзывы кто не проходил алго-секцию с таким уровнем решенных задач, если вы ближе к 1к решенных задач и не прошли алго-секцию, вам срочно нужно подтянуть английский, с 99% вероятностью интервьюеру не понравились ваши коммуникативные навыки.

Да, на этом уровне вам нужно подтянуть коммуникативные навыки, если интервью будет на английском, то и его тоже. Это очень важно, даже если вы решите задачу, но не будете объяснять по ходу решения свои мысли, вас завалят.

Вот по каким критериям оценивает Google (от ex googler):

Алгоритмы. В начале, не написав ни строчки кода, вы должны объяснить, как вы будете решать эту задачу, какие алгоритмы и структуры данных будете использовать, какая сложность по времени и памяти у них. Сначала лучше предложить брут форс решение, если есть несколько оптимальных, предложить все.

Кодинг. Вы должны озвученные ранее мысли по решению задачи изложить в коде. В идеале вы должны написать хорошо читаемый код с хорошо именованными переменными, методами и т.д. Ну и, конечно, написанный код должен работать и покрывать все кейсы, даже если вы его не запустите, что, скорее всего, будет так, так как вы будете все писать на пустом листке, без всяких подсвечиваний синтаксиса (лучше готовится к этому, если вам предложат писать в каком-то онлайн-редакторе кода, будем считать, что вам повезло).

Коммуникация. Это самое сложная часть для всех не англоговорящих или просто интровертов. Вы должны комментировать каждую написанную вами строчку, почему вы ее пишете и к чему она приведет. Также вы должны разговаривать на общие и профессиональные темы по ходу интервью, здесь могут проверять ваши софт скиллы, даже не дойдя до этапа behavioral.

Способ решения проблемы. Вы с самого начала должны по полочкам расставить условия задачи и задавать уточняющие вопросы и выяснить, какие edge cases могут быть. По мере написания кода вы должны разделять задачи на подзадачи, если это нужно, не писать сумбурно и все переписывать, ваш алгоритм должен быть понятен собеседующему на 100%.

В скрине ниже описана структура, как оценивается кандидат в Гугл. Скрин взят отсюда — начиная от 52:00

Метрики оценки на алго секции от бывшего работника Google

Также на данном этапе лучше начать проводить мок интервью, если вы целенаправленно готовитесь к собеседованиям. Мок интервью, позволят вам выстроить в голове структуру собеседования, отточить навык общения на английском и уменьшить стресс уже при прохождении реального интервью. По совету бывалых, нужно, от 10 до 50 мок интервью, чтобы довести этот навык до автоматизма.

Как пройти на следующий уровень

Время, которое понадобится вам, чтобы перейти на следующий уровень около 300-600 часов без перерыва

Здесь остановка для всех, кто хочет попасть любую FAANG+ компанию. Дальше есть смысл идти только, если вы действительно увлечены спортивным программированием и хотите стать чемпионами мира или выигрывать другие соревнования.

На LeetCode проходят много соревнований и челленджей начиная от ежедневных задач, которые вам дает литкод, заканчивая мировыми соревнованиями, где вам на время нужно решать несколько задач.

Господа, здесь моя остановочка, дальше сами!

Уровень 5. Бог. Решенных задач 1000+

Как определить

Вы это и так знаете, лучше поделитесь в комментариях лайфхаками, как эффективно обучаться и стать такими, как вы.

Как пройти на следующий уровень

To infinity and beyond?

Buzz Lightyear

Name already in use

Leetcode / Python / Python_Basic.md

• Go to file T
• Go to line L
• Copy path
• Copy permalink

• Open with Desktop
• View raw
• Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

• 1. There are seven sequence types: strings, Unicode strings, lists, tuples, bytearrays, buffers, and xrange objects.
• 1. For other containers see the built in dict and set classes, and the collections module.
• 1. 仔细阅读link 中tutorial 这部分！
• 1. Values of n less than 0 are treated as 0 (which yields an empty sequence of the same type as s). Note also that the copies are shallow; nested structures are not copied. This often haunts new Python programmers; consider:

• 1. What has happened is that [[]] is a one-element list containing an empty list, so all three elements of [[]] * 3 are (pointers to) this single empty list. Modifying any of the elements of lists modifies this single list. You can create a list of different lists this way:

s[i:j:k] # slice of s from i to j with step k

• 1. The slice of s from i to j with step k is defined as the sequence of items with index x = i + n*k such that 0 <= n < (j-i)/k . In other words, the indices are i, i+k, i+2*k, i+3*k and so on, stopping when j is reached (but never including j). If i or j is greater than len(s), use len(s). If i or j are omitted or None, they become “end” values (which end depends on the sign of k). Note, k cannot be zero. If k is None, it is treated like 1.

• 1. Count

Creat string simply by enclosing characters in quotes. Python treats single quotes the same as double quotes.

• The operator [n:m] returns the part of the string from the “n-eth” character to the “m-eth” character, including the first but excluding the last.
• If we want to get the ith char in the string, the i should not larger than length-1
• But for the string slices, we could use larger than length, since return the empty string » as following example

String are immutable

• It is tempting to use the [] operator on the left side of an assignment, with the intention of changing a character in a string. For example:

• The “object” in this case is the string and the “item” is the character you tried to assign. For now, an object is the same thing as a value, but we will refine that definition later. An item is one of the values in a sequence.
• The reason for the error is that strings are immutable, which means you can’t change an existing string. The best you can do is create a new string that is a variation on the original:

• String could use «+» as Concatenation.

Compare reverse the string and reverse the list

• We could use the < and > compare the integer string

• [Think in Python] (http://www.greenteapress.com/thinkpython/html/thinkpython009.html)
• [Tutorial: String Method] (https://docs.python.org/2/library/stdtypes.html#string-methods)

• A list is a sequence of values. In a string, the values are characters; in a list, they can be any type. The values in a list are called elements or sometimes items.

• There are several ways to create a new list; the simplest is to enclose the elements in square brackets ([ and ])

• A list within another list is nested.

Lists are mutable:

• numbers[1] = 5
• Any integer expression can be used as an index.
• If you try to read or write an element that does not exist, you get an IndexError.
• If an index has a negative value, it counts backward from the end of the list.

Traversing a list

• Use the enumerate

Python Expression	Results	Description
len([1, 2, 3])	3	Length
[1, 2, 3] + [4, 5, 6]	[1, 2, 3, 4, 5, 6]	Concatenation
[‘Hi!’] * 4	[‘Hi!’, ‘Hi!’, ‘Hi!’, ‘Hi!’]	Repetition
3 in [1, 2, 3]	True	Membership
for x in [1, 2, 3]: print x,	1 2 3	Iteration

• list.append(x)

• list.extend(list2)

• list.insert(index, x)
• list.remove(x)
• 注意：如果在list里面没有x，那么用remove会出错！

• list.pop([i]): by default, it pop the last element in the list

• list.index(x)

• list.count(x)

• list.sort()

• list.reverse()

• del element

List and strings

• strings —> list: new_list = list(strings)
• list —> string: new_string = ‘ ‘.join(list)
• A string is a sequence of characters and a list is a sequence of values, but a list of characters is not the same as a string. To convert from a string to a list of characters, you can use list:

• Because list is the name of a built-in function, you should avoid using it as a variable name. I also avoid l because it looks too much like 1. So that’s why I use t. The list function breaks a string into individual letters. If you want to break a string into words, you can use the split method:

• An optional argument called a delimiter specifies which characters to use as word boundaries. The following example uses a hyphen as a delimiter:

• join is the inverse of split. It takes a list of strings and concatenates the elements. join is a string method, so you have to invoke it on the delimiter and pass the list as a parameter:

• In this case the delimiter is a space character, so join puts a space between words. To concatenate strings without spaces, you can use the empty string, », as a delimiter.

Objects and values

• To check whether two variables refer to the same object, you can use the is operator.
• In the string example, Python only created one string object, and both a and b refer to it.
• In the list example, two list have the same value, but different object
• If use the a=b , list a and list b will have the same address and same value
• In this case we would say that the two lists are equivalent, because they have the same elements, but not identical, because they are not the same object. If two objects are identical, they are also equivalent, but if they are equivalent, they are not necessarily identical.

• slicing, s[1:2], based on the 0, include the 1 and exclude 2
• s == t, equal if all of the characters are the same. s is t ? no guarantee.
• t = s[:] # list slices ALWAYS make copies
• slicing mutable objects ALWAYS makes new objects (list) slicing immutable objects entirely MAY or MAY NOT make a new object (tuple)
• t =s assignments in python NEVER make copies. The association of a variable with an object is called a reference. In this example, there are two references to the same object.An object with more than one reference has more than one name, so we say that the object is aliased.

• When you pass a list to a function, the function gets a reference to the list. If the function modifies a list parameter, the caller sees the change. For example, delete_head removes the first element from a list:

Here’s how it is used:

• The parameter t and the variable letters are aliases for the same object.
• It is important to distinguish between operations that modify lists and operations that create new lists. For example, the append method modifies a list, but the + operator creates a new list:

• This difference is important when you write functions that are supposed to modify lists. For example, this function does not delete the head of a list:

• The slice operator creates a new list and the assignment makes t refer to it, but none of that has any effect on the list that was passed as an argument.
• An alternative is to write a function that creates and returns a new list. For example, tail returns all but the first element of a list:

This function leaves the original list unmodified. Here’s how it is used:

• Careless use of lists (and other mutable objects) can lead to long hours of debugging. Here are some common pitfalls and ways to avoid them:

1. Don’t forget that most list methods modify the argument and return None. This is the opposite of the string methods, which return a new string and leave the original alone.

If you are used to writing string code like this: word = word.strip()

It is tempting to write list code like this: t = t.sort() # WRONG!

Because sort returns None, the next operation you perform with t is likely to fail.

Before using list methods and operators, you should read the documentation carefully and then test them in interactive mode. The methods and operators that lists share with other sequences (like strings) are documented at http://docs.python.org/2/library/stdtypes.html#typesseq.

The methods and operators that only apply to mutable sequences are documented at http://docs.python.org/2/library/stdtypes.html#typesseq-mutable.

1. Pick an idiom and stick with it.

• Part of the problem with lists is that there are too many ways to do things. For example, to remove an element from a list, you can use pop, remove, del, or even a slice assignment.
• To add an element, you can use the append method or the + operator. Assuming that t is a list and x is a list element, these are right:

• Try out each of these examples in interactive mode to make sure you understand what they do. Notice that only the last one causes a runtime error; the other three are legal, but they do the wrong thing.

1. Make copies to avoid aliasing.

• If you want to use a method like sort that modifies the argument, but you need to keep the original list as well, you can make a copy.

• In this example you could also use the built-in function sorted, which returns a new, sorted list and leaves the original alone. But in that case you should avoid using sorted as a variable name!

Using lists as Stacks

Using lists as Queues

• map(function,sequence)
• filter(function, sequence)
• reduce(function, sequence)

• A tuple is a sequence of immutable Python objects. Tuples are sequences, just like lists. The only difference is that tuples can’t be changed i.e., tuples are immutable and tuples use parentheses and lists use square brackets.
• It is not possible to assign to the individual items of a tuple, however it is possible to create tuples which contain mutable objects, such as lists.

• The statement t = 12345, 54321, ‘hello!’ is an example of tuple packing: the values 12345, 54321 and ‘hello!’ are packed together in a tuple. The reverse operation is also possible:

• Access Values in Tuples: t[0], t[1:3]
• Can not change the value in tuple or delete/modify any element in tuple, but create a new tuple as following

• Delete the whole tuple: del t2

Basic Tuple operations:

Tuples respond to the + and * operators much like strings; they mean concatenation and repetition here too, except that the result is a new tuple, not a string. In fact, tuples respond to all of the general sequence operations we used on strings in the prior chapter :

Python Expression	Results	Description
len((1, 2, 3))	3	Length
(1, 2, 3) + (4, 5, 6)	(1, 2, 3, 4, 5, 6)	Concatenation
(‘Hi!’,) * 4	(‘Hi!’, ‘Hi!’, ‘Hi!’, ‘Hi!’)	Repetition
3 in (1, 2, 3)	True	Membership
for x in (1, 2, 3): print x,	1 2 3	Iteration

Build-in Tuple function

SN	Function with Description
1	cmp(tuple1, tuple2)
Compares elements of both tuples.
2	len(tuple)
Gives the total length of the tuple.
3	max(tuple)
Returns item from the tuple with max value.
4	min(tuple)
Returns item from the tuple with min value.
5	tuple(seq)
Converts a list into tuple.

• Tuple 比 list 操作速度快。如果您定义了一个值的常量集，并且唯一要用它做的是不断地遍历它，请使用 tuple 代替 list。
• 如果对不需要修改的数据进行 “写保护”，可以使代码更安全。使用 tuple 而不是 list 如同拥有一个隐含的 assert 语句，说明这一数据是常量。如果必须要改变这些值，则需要执行 tuple 到 list 的转换 (需要使用一个特殊的函数)。
• 还记得我说过 dictionary keys 可以是字符串，整数和 “其它几种类型”吗？Tuples 就是这些类型之一。Tuples 可以在 dictionary 中被用做 key，但是 list 不行。实际上，事情要比这更复杂。Dictionary key 必须是不可变的。Tuple 本身是不可改变的，但是如果您有一个 list 的 tuple，那就认为是可变的了，用做 dictionary key 就是不安全的。只有字符串、整数或其它对 dictionary 安全的 tuple 才可以用作 dictionary key。

• A set is an unordered collection with no duplicate elements. Basic uses include membership testing and eliminating duplicate entries. Set objects also support mathematical operations like union, intersection, difference, and symmetric difference.
• Mutable
• Create a empty set: a = set()

• The input parameter should only be list or the string, tuple, the iterate type

• 如果我们要把’hi’,’hello’放在同一个set里面，不能直接用set(‘hi’)

add(elem) Add element elem to the set.

remove(elem) Remove element elem from the set. Raises KeyError if elem is not contained in the set.

discard(elem) Remove element elem from the set if it is present.

pop() Remove and return an arbitrary element from the set. Raises KeyError if the set is empty.

clear() Remove all elements from the set.

• Reference [Tutorial: set] (https://docs.python.org/2/library/stdtypes.html#frozenset)

• dictionary:
• Indexed by keys, which can be any immutable type; strings and numbers can always be keys.
• Tuples can be used as keys if they contain only strings, numbers, or tuples; if a tuple contains any mutable object either directly or indirectly, it cannot be used as a key.
• You can’t use lists as keys, since lists can be modified in place using index assignments, slice assignments, or methods like append() and extend().
• It is best to think of a dictionary as an unordered set of key: value pairs, with the requirement that the keys are unique (within one dictionary). A pair of braces creates an empty dictionary: <>. Placing a comma-separated list of key:value pairs within the braces adds initial key:value pairs to the dictionary; this is also the way dictionaries are written on output.
• The main operations on a dictionary are storing a value with some key and extracting the value given the key. It is also possible to delete a key:value pair with del. If you store using a key that is already in use, the old value associated with that key is forgotten. It is an error to extract a value using a non-existent key.
• The keys() method of a dictionary object returns a list of all the keys used in the dictionary, in arbitrary order (if you want it sorted, just apply the sorted() function to it). To check whether a single key is in the dictionary, use the in keyword.

• More ways to create the dictionary

• In addition, dict comprehensions can be used to create dictionaries from arbitrary key and value expressions:

• When the keys are simple strings, it is sometimes easier to specify pairs using keyword arguments:

• The order of the key-value pairs is not the same. In fact, if you type the same example on your computer, you might get a different result. In general, the order of items in a dictionary is unpredictable.

• The in operator uses different algorithms for lists and dictionaries. For lists, it uses a search algorithm, as in Section 8.6. As the list gets longer, the search time gets longer in direct proportion. For dictionaries, Python uses an algorithm called a hashtable that has a remarkable property: the in operator takes about the same amount of time no matter how many items there are in a dictionary. I won’t explain how that’s possible, but you can read more about it at http://en.wikipedia.org/wiki/Hash_table.

Explain why the key can not be the mutable type, like list

• Lists can be values in a dictionary, as this example shows, but they cannot be keys. Here’s what happens if you try:

• I mentioned earlier that a dictionary is implemented using a hashtable and that means that the keys have to be hashable.
• A hash is a function that takes a value (of any kind) and returns an integer. Dictionaries use these integers, called hash values, to store and look up key-value pairs.
• This system works fine if the keys are immutable. But if the keys are mutable, like lists, bad things happen. For example, when you create a key-value pair, Python hashes the key and stores it in the corresponding location. If you modify the key and then hash it again, it would go to a different location. In that case you might have two entries for the same key, or you might not be able to find a key. Either way, the dictionary wouldn’t work correctly.
• That’s why the keys have to be hashable, and why mutable types like lists aren’t. The simplest way to get around this limitation is to use tuples, which we will see in the next chapter.

When each key is encountered for the first time, it is not already in the mapping; so an entry is automatically created using the default_factory function which returns an empty list. The list.append() operation then attaches the value to the new list. When keys are encountered again, the look-up proceeds normally (returning the list for that key) and the list.append() operation adds another value to the list. This technique is simpler and faster than an equivalent technique using dict.setdefault():

1) An OrderedDict is a dictionary subclass that remembers the order in which its contents are added. A regular dict does not track the insertion order, and iterating over it produces the values in an arbitrary order. In an OrderedDict, by contrast, the order the items are inserted is remembered and used when creating an iterator.

2) A regular dict looks at its contents when testing for equality. An OrderedDict also considers the order the items were added.

3) 注意，在用key, value pair 定义的时候，the order of the key in the OrderedDict is fix, for the following example:

• popitem(True): like stack，从queue的尾部弹出
• popitem(False): like queue, 从queue的头部弹出

##Basic knowledge ####1. Looping Techniques

• When looping through a sequence, the position index and corresponding value can be retrieved at the same time using the enumerate() function.

• To loop over two or more sequences at the same time, the entries can be paired with the zip() function.

• To loop over a sequence in reverse, first specify the sequence in a forward direction and then call the reversed() function.

• To loop over a sequence in sorted order, use the sorted() function which returns a new sorted list while leaving the source unaltered.

• When looping through dictionaries, the key and corresponding value can be retrieved at the same time using the iteritems() method.

• To change a sequence you are iterating over while inside the loop (for example to duplicate certain items), it is recommended that you first make a copy. Looping over a sequence does not implicitly make a copy. The slice notation makes this especially convenient:

####2. Two methods to get the random list

####3. String Method #####Remove the leading chars or the ######1) str.lstrip([chars]) Return a copy of the string with leading characters removed. The chars argument is a string specifying the set of characters to be removed. If omitted or None, the chars argument defaults to removing whitespace. The chars argument is not a prefix; rather, all combinations of its values are stripped:

######2) str.rstrip([chars]) Return a copy of the string with trailing characters removed. The chars argument is a string specifying the set of characters to be removed. If omitted or None, the chars argument defaults to removing whitespace. The chars argument is not a suffix; rather, all combinations of its values are stripped:

######3) str.strip([chars]) Return a copy of the string with the leading and trailing characters removed. The chars argument is a string specifying the set of characters to be removed. If omitted or None, the chars argument defaults to removing whitespace. The chars argument is not a prefix or suffix; rather, all combinations of its values are stripped:

Usage: [String to Integer (atoi)] (../Array/String_to_Integer.py) ; Simply Path

####4. Build-in function

Return True if all elements of the iterable are true (or if the iterable is empty). Equivalent to:

This function returns a list of tuples, where the i-th tuple contains the i-th element from each of the argument sequences or iterables. The returned list is truncated in length to the length of the shortest argument sequence. When there are multiple arguments which are all of the same length, zip() is similar to map() with an initial argument of None. With a single sequence argument, it returns a list of 1-tuples. With no arguments, it returns an empty list.

The left-to-right evaluation order of the iterables is guaranteed. This makes possible an idiom for clustering a data series into n-length groups using zip(*[iter(s)]*n).

zip() in conjunction with the * operator can be used to unzip a list:

• Take two (non complex) numbers as arguments and return a pair of numbers consisting of their quotient and remainder when using integer division. With mixed operand types, the rules for binary arithmetic operators apply. For integers, the result is the same as (a // b, a % b). For floating point numbers the result is (q, a % b), where q is usually math.floor(a / b) but may be 1 less than that. In any case q * b + a % b is very close to a, if a % b is non-zero it has the same sign as b, and 0 <= abs(a % b) < abs(b).

####5. Difference between range() and xrange()

• xrange(start, stop[, step])
• This function is very similar to range(), but returns an xrange object instead of a list. This is an opaque sequence type which yields the same values as the corresponding list, without actually storing them all simultaneously. The advantage of xrange() over range() is minimal (since xrange() still has to create the values when asked for them) except when a very large range is used on a memory-starved machine or when all of the range’s elements are never used (such as when the loop is usually terminated with break).

• But for the python 3.4, there is NO xrange, only range, return range

6. Global variables

• In the previous example, known is created outside the function, so it belongs to the special frame called __main__ . Variables in __main__ are sometimes called global because they can be accessed from any function. Unlike local variables, which disappear when their function ends, global variables persist from one function call to the next.

*It is common to use global variables for flags; that is, boolean variables that indicate (“flag”) whether a condition is true. For example, some programs use a flag named verbose to control the level of detail in the output:

• If you try to reassign a global variable, you might be surprised. The following example is supposed to keep track of whether the function has been called:

• But if you run it you will see that the value of been_called doesn’t change. The problem is that example2 creates a new local variable named been_called. The local variable goes away when the function ends, and has no effect on the global variable.
• To reassign a global variable inside a function you have to declare the global variable before you use it:

• The global statement tells the interpreter something like, “In this function, when I say been_called, I mean the global variable; don’t create a local one.”
• Here’s an example that tries to update a global variable:

• Python assumes that count is local, which means that you are reading it before writing it. The solution, again, is to declare count global.

*If the global value is mutable, you can modify it without declaring it:

• So you can add, remove and replace elements of a global list or dictionary, but if you want to reassign the variable, you have to declare it:

• ‘_’ has 3 main conventional uses in Python:

To hold the result of the last executed statement in an interactive interpreter session. This precedent was set by the standard CPython interpreter, and other interpreters have followed suit

For translation lookup in i18n (imported from the corresponding C conventions, I believe)

As a general purpose «throwaway» variable name to indicate that part of a function result is being deliberately ignored

• Plain integers (called integers) are implemented using long in C, which gives them at least 32 bits of precision.
• sys.maxint is always set to the maximum plain integer value for the current platform, the minimum value is -sys.maxint — 1

• Long integers have unlimited precision

• Floating point numbers are usually implemented using double in C

10. Multiple Assignment! [Important!!]

• Note: here, a+b first assign to the a, so a = 3 and then a assign to b, b = 1, right now, the value of a does not change!
• But then if we do the a = a + 1, the a has change to 3.
• Check the multiple assignment in the above leetcode question .)

12. Reverse the List

Python supports a style of programming called functional programming where you can pass functions to other functions to do stuff

1. map(func, seq)

1. filter(function, seq)

1. reduce(function, seq)

If seq = [ s1, s2, s3, . , sn ], calling reduce(func, seq) works like this:

• At first the first two elements of seq will be applied to func, i.e. func(s1,s2) The list on which reduce() works looks now like this: [ func(s1, s2), s3, . , sn ]
• In the next step func will be applied on the previous result and the third element of the list, i.e. func(func(s1, s2),s3) The list looks like this now: [ func(func(s1, s2),s3), . , sn ]
• Continue like this until just one element is left and return this element as the result of reduce()

• In the context of Boolean operations, and also when expressions are used by control flow statements, the following values are interpreted as false: False, None, numeric zero of all types, and empty strings and containers (including strings, tuples, lists, dictionaries, sets and frozensets). All other values are interpreted as true.
• The expression x and y first evaluates x; if x is false, its value is returned; otherwise, y is evaluated and the resulting value is returned.
• (Note that neither and nor or restrict the value and type they return to False and True, but rather return the last evaluated argument. This is sometimes useful, e.g., if s is a string that should be replaced by a default value if it is empty, the expression s or ‘foo’ yields the desired value. Because not has to invent a value anyway, it does not bother to return a value of the same type as its argument, so e.g., not ‘foo’ yields False, not ».)
• For example

Class Related Knowledge

1. Basic concepts in OOP: Abstraction, Polymorphism, Encapsulation, Inheritance

2. Class Attributes

• Basic configuration

In this code example, we have a Cat class. The special method init() is called automatically right after the object has been created. Each method in a class definition begins with a reference to the instance object. It is by convention named self. There is nothing special about the self name. We could name it this, for example. The name is the argument. The value is passed during the class instantiation.

The atributes can be assigned dynamically, not just during initialization. This shows the next example.

• So far, we have been talking about the instance attributes. In Python there are also so called class object attributes. Class object attributes are same for all instances of a class.

3. Class Methods

• In Python, we can call methods in two ways. There are bounded and unbounded method calls.

4. Object and Type

1. Everything is an object

• Any classes that we define are objects, and of course, instances of those classes are objects as well.

• Note 1), 2), we create the python in_build int instance, the type of these instance is ‘int’
• Note 3), In Python, the type of an object is represented by the class used to build the object: that is, in Python the word type has the same meaning of the word class.

• 1), 2) The names of the two primitive objects within Python. Earlier type() was introduced as a way to find the type of an object (specifically, the class attribute). In reality, it is both an object itself, and a way to get the type of another object.
• 3), 4) Exploring <type ‘object’>: the type of <type ‘object’> is <type ‘type’>. We also use the class attribute and verify it is the same as calling type()

1. some low level C library is leaking
2. your Python code have global lists or dicts that grow over time, and you forgot to remove the objects after use
3. there are some reference cycles in your app

Sort and Sorted

Python lists have a built-in sort() method that modifies the list in-place and a sorted() built-in function that builds a new sorted list from an iterable.