GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — 2022-08-05 10:41:15 PM · behappyyoung/PythonSampleCodes@66bc37c

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • Algorithm
    • .ipynb_checkpoints
      • Untitled3-checkpoint.ipynb
    • ArrayRelated
      • .ipynb_checkpoints
        • Interval Intersections-checkpoint.ipynb
        • M-checkpoint.ipynb
        • Max Area of Island-checkpoint.ipynb
        • MaxArea-checkpoint.ipynb
        • Misc-checkpoint.ipynb
        • Move Zero-checkpoint.ipynb
        • My Calendar-checkpoint.ipynb
        • Non-overlapping Intervals-checkpoint.ipynb
        • Permutation in String-checkpoint.ipynb
        • Task Scheduler-checkpoint.ipynb
        • Test-checkpoint.ipynb
        • Untitled5-checkpoint.ipynb
        • Untitled6-checkpoint.ipynb
        • Untitled8-checkpoint.ipynb
        • Untitled9-checkpoint.ipynb
        • findAndReplacePattern-checkpoint.ipynb
        • longest Palindrome-checkpoint.ipynb
        • validSudoku-checkpoint.ipynb
      • Interval Intersections.ipynb
      • M.ipynb
      • Math-Numbers
        • .ipynb_checkpoints
          • Increasing Triplet-checkpoint.ipynb
          • Mirror Reflection-checkpoint.ipynb
        • Increasing Triplet.ipynb
        • Mirror Reflection.ipynb
      • Max Area of Island.ipynb
      • MaxArea.ipynb
      • Misc.ipynb
      • Move Zero.ipynb
      • My Calendar.ipynb
      • Non-overlapping Intervals.ipynb
      • Permutation in String.ipynb
      • Strings
        • .ipynb_checkpoints
          • Minimum Window Substring-checkpoint.ipynb
          • Top K Frequent Words-checkpoint.ipynb
        • Minimum Window Substring.ipynb
        • Top K Frequent Words.ipynb
      • Task Scheduler.ipynb
      • Test.ipynb
      • Untitled5.ipynb
      • Untitled6.ipynb
      • Untitled8.ipynb
      • Untitled9.ipynb
      • findAndReplacePattern.ipynb
      • longest Palindrome.ipynb
      • validSudoku.ipynb
    • Backtracking
      • Generate Parenteses.ipynb
    • BinaryTree
      • .ipynb_checkpoints
        • Flatten Tree-checkpoint.ipynb
        • Merge Tree-checkpoint.ipynb
        • TreeNode-checkpoint.ipynb
      • Flatten Tree.ipynb
      • Merge Tree.ipynb
      • TreeNode.ipynb
      • Untitled.ipynb
      • _BinaryTree.py
    • BitManipulations
      • .ipynb_checkpoints
        • Reverse Bits-checkpoint.ipynb
        • Untitled-checkpoint.ipynb
      • Reverse Bits.ipynb
      • Untitled.ipynb
    • DynamicProgramming
      • Out of Boundary Paths.ipynb
      • .ipynb_checkpoints
        • Out of Boundary Paths-checkpoint.ipynb
        • Coin Change-checkpoint.ipynb
        • Matrix Update-checkpoint.ipynb
        • Max Subarrays Sum,Product-checkpoint.ipynb
        • Maximum Subarrays-checkpoint.ipynb
        • Partition Equal Subset Sum-checkpoint.ipynb
        • Triangle Minimum Total-checkpoint.ipynb
        • Untitled1-checkpoint.ipynb
        • k Inverse Pairs-checkpoint.ipynb
      • Coin Change.ipynb
      • Longest-Common-Subsequence.ipynb
      • Matrix Update.ipynb
      • Max Subarrays Sum,Product.ipynb
      • Maximum Subarrays.ipynb
      • Partition Equal Subset Sum.ipynb
      • Triangle Minimum Total.ipynb
      • Untitled1.ipynb
      • k Inverse Pairs.ipynb
    • Graph
      • .ipynb_checkpoints
        • Course Scheduler-checkpoint.ipynb
        • Untitled1-checkpoint.ipynb
      • Course Scheduler.ipynb
      • Untitled1.ipynb
    • LeetCode
      • .ipynb_checkpoints
        • LeetCode-checkpoint.ipynb
      • LeetCode.ipynb
    • LinedLists
      • .ipynb_checkpoints
        • Remove Nth From End-checkpoint.ipynb
        • Sort Linked List-checkpoint.ipynb
        • Split Linked List-checkpoint.ipynb
        • Untitled-checkpoint.ipynb
        • Untitled1-checkpoint.ipynb
        • merge_k_sorted_lists-checkpoint.ipynb
      • Remove Nth From End.ipynb
      • Remove-Nth-From-End.py
      • Sort Linked List.ipynb
      • Split Linked List.ipynb
      • Untitled.ipynb
      • Untitled1.ipynb
      • merge_k_sorted_lists.ipynb
    • Math
      • .ipynb_checkpoints
        • Math-checkpoint.ipynb
        • Median of Two Sorted Array-checkpoint.ipynb
        • Number of Squares-checkpoint.ipynb
      • Math.ipynb
      • Median of Two Sorted Array.ipynb
      • Number of Squares.ipynb
    • String
      • .ipynb_checkpoints
        • First Uniquie character of string-checkpoint.ipynb
        • Untitled2-checkpoint.ipynb
      • First Uniquie character of string.ipynb
      • Minimum Window Substring.ipynb
      • Untitled2.ipynb
    • Tree
      • .ipynb_checkpoints
        • Untitled-checkpoint.ipynb
        • Untitled1-checkpoint.ipynb
        • binary-tree-right-side-view-checkpoint.ipynb
      • Untitled.ipynb
      • Untitled1.ipynb
      • binary-tree-right-side-view.ipynb
    • Untitled3.ipynb
  • Concepts
    • .ipynb_checkpoints
      • Dict-checkpoint.ipynb
      • Untitled-checkpoint.ipynb
    • Dict.ipynb
    • List
      • .ipynb_checkpoints
        • Untitled-checkpoint.ipynb
      • Untitled.ipynb
    • Sorting.ipynb
    • String
      • .ipynb_checkpoints
        • Strings-checkpoint.ipynb
      • Strings.ipynb
    • Untitled.ipynb

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.
Dismiss banner
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎Algorithm/.ipynb_checkpoints/Untitled3-checkpoint.ipynb‎

Copy file name to clipboard
+6Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
{
2+
"cells": [],
3+
"metadata": {},
4+
"nbformat": 4,
5+
"nbformat_minor": 5
6+
}
Collapse file

‎Algorithm/ArrayRelated/.ipynb_checkpoints/Interval Intersections-checkpoint.ipynb‎

Copy file name to clipboard
+6Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
{
2+
"cells": [],
3+
"metadata": {},
4+
"nbformat": 4,
5+
"nbformat_minor": 5
6+
}
Collapse file

‎Algorithm/ArrayRelated/.ipynb_checkpoints/M-checkpoint.ipynb‎

Copy file name to clipboard
+312Lines changed: 312 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,312 @@
1+
{
2+
"cells": [
3+
{
4+
"cell_type": "code",
5+
"execution_count": 6,
6+
"id": "3bdf4aac",
7+
"metadata": {},
8+
"outputs": [
9+
{
10+
"data": {
11+
"text/plain": [
12+
"[6, 3, 1, 2, 2, 1, 0]"
13+
]
14+
},
15+
"execution_count": 6,
16+
"metadata": {},
17+
"output_type": "execute_result"
18+
}
19+
],
20+
"source": [
21+
"def countSmaller(nums):\n",
22+
" if not nums:\n",
23+
" return nums\n",
24+
" answers = []\n",
25+
" for i in range(len(nums)-1):\n",
26+
" count = 0\n",
27+
" for j in range(i+1, len(nums)):\n",
28+
" if nums[i] > nums[j]:\n",
29+
" count += 1\n",
30+
" answers.append(count)\n",
31+
" answers.append(0)\n",
32+
" return answers\n",
33+
" \n",
34+
"nums = [21,5,2,6,20,3,1]\n",
35+
"countSmaller(nums)"
36+
]
37+
},
38+
{
39+
"cell_type": "code",
40+
"execution_count": 77,
41+
"id": "34b281dd",
42+
"metadata": {},
43+
"outputs": [
44+
{
45+
"name": "stdout",
46+
"output_type": "stream",
47+
"text": [
48+
"5 0 [0, 0]\n",
49+
"1 0 [0, 0, 0]\n",
50+
"20 4 [4, 0, 0, 0, 0]\n",
51+
"6 3 [3, 4, 0, 0, 0, 0]\n",
52+
"21 6 [6, 3, 4, 0, 0, 0, 0]\n",
53+
"22 9 [9, 0, 4, 6, 3, 4, 0, 0, 0, 0]\n",
54+
"4 1 [1, 9, 0, 4, 6, 3, 4, 0, 0, 0, 0]\n",
55+
"7/6\n",
56+
"5/2 20/4\n",
57+
"1/0 6/3 - 21/6\n",
58+
"- 4/1 - - - 22/9\n",
59+
"- - - -\n"
60+
]
61+
},
62+
{
63+
"data": {
64+
"text/plain": [
65+
"[1, 9, 0, 4, 6, 3, 4, 0, 0, 0, 0]"
66+
]
67+
},
68+
"execution_count": 77,
69+
"metadata": {},
70+
"output_type": "execute_result"
71+
}
72+
],
73+
"source": [
74+
"\"\"\"\n",
75+
"new custom TreeNode with left / same counts\n",
76+
"\n",
77+
"\"\"\"\n",
78+
"class TreeNode:\n",
79+
" def __init__(self, x, lcount=0, samecount=1):\n",
80+
" self.val = x\n",
81+
" self.left = None\n",
82+
" self.right = None\n",
83+
" self.lcount = lcount\n",
84+
" self.samecount = samecount\n",
85+
" \n",
86+
"\n",
87+
" def __str__(self):\n",
88+
" return str(self.val)\n",
89+
"\n",
90+
"def print_btree(root):\n",
91+
" current_level = [root]\n",
92+
" while current_level:\n",
93+
" print(' '.join('-' if node == '-' else f'{node.val}/{node.lcount}' for node in current_level))\n",
94+
" next_level = list()\n",
95+
" for n in current_level:\n",
96+
" if n == '-':\n",
97+
" continue\n",
98+
" if n.left:\n",
99+
" next_level.append(n.left)\n",
100+
" else:\n",
101+
" next_level.append('-')\n",
102+
" if n.right:\n",
103+
" next_level.append(n.right)\n",
104+
" else:\n",
105+
" next_level.append('-')\n",
106+
" current_level = next_level\n",
107+
" \n",
108+
"def countSmaller_bst(nums):\n",
109+
" if not nums:\n",
110+
" return nums\n",
111+
" \n",
112+
" answers = [0]\n",
113+
" bst = TreeNode(nums[len(nums)-1])\n",
114+
" \n",
115+
" def build_tree(c, c_root, pre_lcount=0):\n",
116+
" if not c_root:\n",
117+
" answers.insert(0, pre_lcount)\n",
118+
" print(c, pre_lcount, answers)\n",
119+
" return TreeNode(c, pre_lcount)\n",
120+
" \n",
121+
" if c == c_root.val:\n",
122+
" answers.insert(0, pre_lcount)\n",
123+
" c_root.samecount += 1\n",
124+
" elif c < c_root.val:\n",
125+
" c_root.lcount += 1\n",
126+
" c_root.left = build_tree(c, c_root.left, pre_lcount)\n",
127+
" elif c > c_root.val:\n",
128+
" c_root.right = build_tree(c, c_root.right, max(pre_lcount, c_root.lcount)+1*c_root.samecount)\n",
129+
"\n",
130+
" return c_root\n",
131+
"\n",
132+
" for i in range(len(nums)-2, -1, -1):\n",
133+
" if nums[i] == bst.val:\n",
134+
" bst.samecount += 1\n",
135+
" answers.insert(0, bst.lcount)\n",
136+
" else:\n",
137+
" build_tree(nums[i], bst) \n",
138+
" \n",
139+
" \n",
140+
" print_btree(bst)\n",
141+
" return answers\n",
142+
" \n",
143+
"# nums = [5,2,6,1]\n",
144+
"# nums = [5183,2271,3067,539,8939,2999,9264,737,3974,5846,-210,9278,5800,2675,6608,1133,-1,6018,9672,5179,9842,7424,-209,2988,2757,5984,1107,2644,-499,7234,7539,6525,347,5718,-742,1797,5292,976,8752,8297,1312,3385,5924,2882,6091,-282,2595,96,1906,8014,7667,5895,7283,7974,-167,7068,3946,6223,189,1589,2058,9277,-302,8157,8256,5261,8067,1071,9470,2682,8197,5632,753,3179,8187,9042,8167,4657,7080,7801,5627,7917,8085,928,-892,-427,3685,4676,2431,8064,8537,343,505,4352,2108,4399,66,2086,1922,9126,9460,393,443,5689,7595,850,8493,2866,732,3738,7933,3666,2370,5804,4045,7903,8009,5387,5542,7593,6862,1547,6934,-160,9693,4560,7429,9989,7232,-594,587,6476,9277,4471,5979,6268,2419,6706,-727,1927,7361,9684,5519,2703,1723,5181,3545,4290,9421,4288,1656,1541,9632,1448,-490,4747,5416,4139,-845,3834,3349,8594,7882,2279,7777,9369,9917,8167,6799,-612,5604,5787,2615,7033,5986,-322,8631,1793,-612,3528,206,419,1413,8585,5658,-981,1391,8088,7035,6259,-651,3118,9105,4531,2569,7576,7981,838,5715,1387,8506,331,7844,9187,681]\n",
145+
"nums = [4, 22,5,7, 21,6,20,5, 1, 5, 7]\n",
146+
"# nums = [26,78,27,100,33,67,90,23,66,5,38,7,35,23,52,22,83,51,98,69,81,32,78,28,94,13,2,97,3,76,99,51,9,21,84,66,65,36,100,41]\n",
147+
"countSmaller_bst(nums)"
148+
]
149+
},
150+
{
151+
"cell_type": "code",
152+
"execution_count": 108,
153+
"id": "59e5f101",
154+
"metadata": {},
155+
"outputs": [
156+
{
157+
"name": "stdout",
158+
"output_type": "stream",
159+
"text": [
160+
"-- 5 7 0 [0, 0] {7: 1} {}\n",
161+
"-- 1 7 0 [0, 1, 0, 0] {7: 3, 5: 5} {7: 2}\n",
162+
"20 7 4\n",
163+
"-- 20 20 1 [1, 3, 0, 1, 0, 0] {7: 3, 5: 5, 1: 0} {7: 3}\n",
164+
"6 5 6\n",
165+
"-- 6 6 1 [1, 1, 3, 0, 1, 0, 0] {7: 6, 5: 5, 1: 0, 20: 1} {7: 3}\n",
166+
"21 7 7\n",
167+
"21 20 2\n",
168+
"-- 21 21 2 [2, 1, 1, 3, 0, 1, 0, 0] {7: 6, 5: 5, 1: 0, 20: 1, 6: 1} {7: 3}\n",
169+
"22 7 10\n",
170+
"22 20 2\n",
171+
"22 21 3\n",
172+
"-- 22 22 3 [3, 0, 2, 1, 1, 3, 0, 1, 0, 0] {7: 9, 5: 5, 1: 0, 20: 1, 6: 1, 21: 2} {7: 3, 5: 2}\n",
173+
"-- 4 7 0 [0, 3, 0, 2, 1, 1, 3, 0, 1, 0, 0] {7: 12, 5: 5, 1: 0, 20: 1, 6: 1, 21: 2, 22: 3} {7: 3, 5: 2}\n",
174+
"{7: 15, 5: 5, 1: 0, 20: 1, 6: 1, 21: 2, 22: 3, 4: 0}\n",
175+
"7\n",
176+
"- 20\n",
177+
"- 21\n",
178+
"- 22\n",
179+
"- -\n"
180+
]
181+
},
182+
{
183+
"data": {
184+
"text/plain": [
185+
"[0, 0, 3, 0, 2, 1, 1, 3, 0, 1, 0, 0]"
186+
]
187+
},
188+
"execution_count": 108,
189+
"metadata": {},
190+
"output_type": "execute_result"
191+
}
192+
],
193+
"source": [
194+
"\"\"\"\n",
195+
"normal TreeNode\n",
196+
"\n",
197+
"\"\"\"\n",
198+
"class TreeNode:\n",
199+
" def __init__(self, x, lcount=0, samecount=0):\n",
200+
" self.val = x\n",
201+
" self.left = None\n",
202+
" self.right = None\n",
203+
" \n",
204+
"\n",
205+
" def __str__(self):\n",
206+
" return str(self.val)\n",
207+
"\n",
208+
"def print_btree(root):\n",
209+
" current_level = [root]\n",
210+
" while current_level:\n",
211+
" print(' '.join('-' if node == '-' else f'{node.val}' for node in current_level))\n",
212+
" next_level = list()\n",
213+
" for n in current_level:\n",
214+
" if n == '-':\n",
215+
" continue\n",
216+
" if n.left:\n",
217+
" next_level.append(n.left)\n",
218+
" else:\n",
219+
" next_level.append('-')\n",
220+
" if n.right:\n",
221+
" next_level.append(n.right)\n",
222+
" else:\n",
223+
" next_level.append('-')\n",
224+
" current_level = next_level\n",
225+
" \n",
226+
"\n",
227+
"def countSmaller_bst_a(nums):\n",
228+
" if not nums:\n",
229+
" return nums\n",
230+
" \n",
231+
" answers = [0]\n",
232+
" left_counts = dict()\n",
233+
" same_counts = dict()\n",
234+
" \n",
235+
" \n",
236+
" bst = TreeNode(nums[len(nums)-1])\n",
237+
" left_counts[nums[len(nums)-1]] = 0\n",
238+
" \n",
239+
" def build_tree(c, c_root, last_left, pre_lcount=0):\n",
240+
" if not c_root:\n",
241+
" answers.insert(0, pre_lcount)\n",
242+
" print('--', c, last_left, pre_lcount, answers, left_counts, same_counts)\n",
243+
" left_counts[c] = pre_lcount\n",
244+
" return TreeNode(c)\n",
245+
" \n",
246+
" if c == c_root.val:\n",
247+
" answers.insert(0, pre_lcount)\n",
248+
" same_counts[c] = same_counts.get(c, 1) +1\n",
249+
" return None\n",
250+
" elif c < c_root.val:\n",
251+
" if last_left:\n",
252+
" left_counts[c_root.val] = left_counts.get(last_left, 0) + same_counts.get(last_left, 1)\n",
253+
" else:\n",
254+
" left_counts[c_root.val] = 0\n",
255+
" \n",
256+
" c_root.left = build_tree(c, c_root.left, last_left)\n",
257+
" elif c > c_root.val:\n",
258+
" print(c, c_root.val, max(pre_lcount, left_counts.get(c_root.val, 0))+1)\n",
259+
" last_left = c_root.val\n",
260+
" c_root.right = build_tree(c, c_root.right, last_left, max(pre_lcount, left_counts.get(last_left, 0))+same_counts.get(last_left, 1))\n",
261+
"\n",
262+
" return c_root\n",
263+
"\n",
264+
" for i in range(len(nums)-2, -1, -1):\n",
265+
" last_left = None\n",
266+
" if nums[i] == bst.val:\n",
267+
" same_counts[nums[i]] = same_counts.get(nums[i], 1) + 1\n",
268+
" answers.insert(0, left_counts.get(nums[i], 0))\n",
269+
" else:\n",
270+
" build_tree(nums[i], bst, last_left) \n",
271+
" \n",
272+
" print(left_counts)\n",
273+
" print_btree(bst)\n",
274+
" return answers\n",
275+
" \n",
276+
"# nums = [5,2,6,1]\n",
277+
"# nums = [5183,2271,3067,539,8939,2999,9264,737,3974,5846,-210,9278,5800,2675,6608,1133,-1,6018,9672,5179,9842,7424,-209,2988,2757,5984,1107,2644,-499,7234,7539,6525,347,5718,-742,1797,5292,976,8752,8297,1312,3385,5924,2882,6091,-282,2595,96,1906,8014,7667,5895,7283,7974,-167,7068,3946,6223,189,1589,2058,9277,-302,8157,8256,5261,8067,1071,9470,2682,8197,5632,753,3179,8187,9042,8167,4657,7080,7801,5627,7917,8085,928,-892,-427,3685,4676,2431,8064,8537,343,505,4352,2108,4399,66,2086,1922,9126,9460,393,443,5689,7595,850,8493,2866,732,3738,7933,3666,2370,5804,4045,7903,8009,5387,5542,7593,6862,1547,6934,-160,9693,4560,7429,9989,7232,-594,587,6476,9277,4471,5979,6268,2419,6706,-727,1927,7361,9684,5519,2703,1723,5181,3545,4290,9421,4288,1656,1541,9632,1448,-490,4747,5416,4139,-845,3834,3349,8594,7882,2279,7777,9369,9917,8167,6799,-612,5604,5787,2615,7033,5986,-322,8631,1793,-612,3528,206,419,1413,8585,5658,-981,1391,8088,7035,6259,-651,3118,9105,4531,2569,7576,7981,838,5715,1387,8506,331,7844,9187,681]\n",
278+
"nums = [4, 4, 22,5,21,6, 20,7, 1, 7, 5, 7]\n",
279+
"countSmaller_bst_a(nums)"
280+
]
281+
},
282+
{
283+
"cell_type": "code",
284+
"execution_count": null,
285+
"id": "2d70fdf2",
286+
"metadata": {},
287+
"outputs": [],
288+
"source": []
289+
}
290+
],
291+
"metadata": {
292+
"kernelspec": {
293+
"display_name": "Python 3",
294+
"language": "python",
295+
"name": "python3"
296+
},
297+
"language_info": {
298+
"codemirror_mode": {
299+
"name": "ipython",
300+
"version": 3
301+
},
302+
"file_extension": ".py",
303+
"mimetype": "text/x-python",
304+
"name": "python",
305+
"nbconvert_exporter": "python",
306+
"pygments_lexer": "ipython3",
307+
"version": "3.6.9"
308+
}
309+
},
310+
"nbformat": 4,
311+
"nbformat_minor": 5
312+
}

0 commit comments

Comments
0 (0)
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.