涓€銆丄rrays & Linked List
- 鍙嶈浆鍒楄〃 https://leetcode-cn.com/problems/reverse-linked-list/
- 涓や袱浜ゆ崲閾捐〃涓殑鑺傜偣 https://leetcode-cn.com/problems/swap-nodes-in-pairs/
- 鐜舰閾捐〃 https://leetcode-cn.com/problems/linked-list-cycle/
- 鐜舰閾捐〃 II https://leetcode-cn.com/problems/linked-list-cycle-ii/
- K 涓竴缁勭炕杞摼琛?https://leetcode-cn.com/problems/reverse-nodes-in-k-group/ 锛堝緟琛ヰ煋岋級
浜屻€佸爢鏍?& 闃熷垪
- 鏈夋晥鐨勬嫭鍙?https://leetcode-cn.com/problems/valid-parentheses/
- 闈㈣瘯棰橈細
鐢ㄦ爤瀹炵幇闃熷垪 https://leetcode-cn.com/problems/implement-queue-using-stacks/
鐢ㄩ槦鍒楀疄鐜版爤 https://leetcode-cn.com/problems/implement-stack-using-queues/ - java涓殑鏍堬細
Stack<Integer> stack =new Stack<>();
stack.push(1);
stack.peek();
stack.pop();
stack.isEmpty();
- java涓殑闃熷垪
Queue<Integer> queue = new Queue<Integer>();
queue.offer(2);
queue.poll();
queue.peek();
queue.isEmpty();
涓夈€佷紭鍏堥槦鍒?/h3>
- PriorityQueue 浼樺厛闃熷垪锛屾甯稿叆锛屾寜鐓т紭鍏堢骇鍑猴紙璁剧疆灞炴€ф潵瑙勫畾浼樺厛绾э級
- 浼樺厛闃熷垪鐨勫疄鐜版満鍒?br>
鏂规硶涓€锛氬爢锛坔eap锛夊疄鐜帮紝鍫嗕篃鏈夊緢澶氱
鏂规硶浜岋細浜屽弶鎼滅储鏍?/li>
- 闈㈣瘯棰橈細鏁版嵁娴佷腑鐨勭 K 澶у厓绱?https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
- 瑙i鏂规硶鐨勬牳蹇冿細浣跨敤鍫嗗瓨鍌ㄥ墠k涓ぇ鐨勫厓绱狅紙鍙兘鏄В鍐宠繖绉嶇k绯诲垪棰樼洰鐨勯€氱敤鎯虫硶锛燂級
- 闈㈣瘯棰橈細婊戝姩绐楀彛鐨勬渶澶у€?https://leetcode-cn.com/problems/sliding-window-maximum/
鏂规硶涓€锛氫娇鐢ㄥぇ椤跺爢瀹炵幇
鏂规硶浜岋細浣跨敤鍙岀闃熷垪缁存姢涓€涓弗鏍奸€掑鐨勫崟璋冮槦鍒?/li>
鍥涖€佹槧灏勶紙Map锛?amp;闆嗗悎锛坰et锛?/h3>
- 鏈川锛氶€氳繃hash鍑芥暟灏唙alue鏄犲皠鍒版煇涓綅缃笂锛屽疄鐜癘(1)鏌ユ壘
- 瀹炵幇锛欻ashMap/TreeMap锛堜簩鍙夋悳绱㈡爲锛夛紝HashSet/TreeSet
- 鏈夋晥鐨勫瓧姣嶅紓浣嶈瘝 https://leetcode-cn.com/problems/valid-anagram/)
- 涓ゆ暟涔嬪拰 https://leetcode-cn.com/problems/two-sum/
鍙互浣跨敤鍙屾寚閽堬紝涔熷彲浠ヤ娇鐢℉ashMap瑙e喅
- 涓夋暟涔嬪拰 https://leetcode-cn.com/problems/3sum/ sort+涓€灞傚惊鐜?鍙屾寚閽堥亶鍘? 娉ㄦ剰瀵光€樹笉閲嶅鈥欑殑澶勭悊
- 鍥涙暟涔嬪拰 https://leetcode-cn.com/problems/4sum/ 鍚屼笂
浜斻€佹爲銆佷簩鍙夋爲銆佷簩鍙夋悳绱㈡爲
- 浜屽弶鎼滅储鏍戯細鏍硅妭鐐圭殑鍊煎ぇ浜庡乏瀛愭爲锛屽皬浜庡彸瀛愭爲
- 浜屽弶鎼滅储鏍戠殑鎬ц川锛氫腑搴忛亶鍘嗕骇鐢熼€掑搴忓垪
- 楠岃瘉浜屽弶鎼滅储鏍? https://leetcode-cn.com/problems/validate-binary-search-tree/
- 瑙f硶锛氫腑搴忛亶鍘嗙粨鏋滃瓨鍌ㄤ笅鏉ラ獙璇佹槸鍚︿弗鏍奸€掑锛涙垨鑰咃紝姣忔璁板綍涓婁竴涓繑鍥炵殑鍊硷紝鍦ㄤ腑搴忛亶鍘嗕腑鍒ゆ柇鏄惁涓ユ牸閫掑
- 鍋氫簡涓€浜涢鐩彂鐜帮紝鐩稿悓鐨勬€濊矾涓嬶紝鍙嶈€岄€掑綊鐨勬柟娉曞張绠€鍗曘€佸張蹇?/li>
- 浜屽弶鎼滅储鏍戠殑鏈€杩戝叕鍏辩鍏?https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)
- 瑙f硶锛氳皥鍒颁簩鍙夋悳绱㈡爲涓€瀹氬拰鑺傜偣鐨勫ぇ灏忓叧绯绘湁鍏筹紝娉ㄦ剰鍦ㄦ渶杩戝叕鍏辩鍏堝浼氬彂鐢熺殑鍙樺寲锛歱銆乹涓ょ偣寮€濮嬪垎鍚憀eft銆乺ight涓よ竟
- 浜屽弶鏍戠殑鏈€杩戝叕鍏辩鍏?https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
- 瑙f硶锛氶€掑綊鐨勬€濇兂锛侊紒锛?/li>
鍏€侀€掑綊鍜屽垎娌?/h3>
- Pow(x, n) https://leetcode-cn.com/problems/powx-n/ 娉ㄦ剰n涓鸿礋鏁扮殑鎯呭喌
涓冦€佽椽蹇冪畻娉?/h3>
- 鎬绘槸鍋氬嚭瀵瑰綋鍓嶇幆澧冩渶浼樼殑閫夋嫨
- 閫傜敤璐績鐨勫満鏅細闂鑳藉鍒嗚В鎴愬瓙闂鏉ヨВ鍐筹紝瀛愰棶棰樼殑鏈€浼樿В鑳藉閫掓帹鍒版渶缁堥棶棰樼殑鏈€浼樿В銆傝繖绉嶅瓙闂鏈€浼樿В绉颁负鏈€浼樺瓙缁撴瀯銆?/li>
- 涔板崠鑲$エ鐨勬渶浣虫椂鏈?II https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
鍏€佸箍搴︽湁闄愭悳绱紙bfs锛変笌娣卞害浼樺厛鎼滅储锛坉fs锛?/h3>
- 鎰熻浜屽弶鏍戠殑鍓嶅簭閬嶅巻鏈夌偣鍍忔繁搴︽湁闄愭悳绱?/li>
- 骞垮害浼樺厛鎼滅储锛氫竴灞備竴灞傚湴鎼滐紝鍙互浣跨敤闃熷垪鏉ュ疄鐜帮紝瀵逛簬鏍戞潵璇达紝鏄病鏈夌幆瀛樺湪鐨勶紝浣嗗鏋滄槸鍥句笂鐨勬悳绱紝闇€瑕佷娇鐢ㄤ竴涓暟缁刬sVisit鏉ヨ褰曞綋鍓嶇殑鐐规槸鍚﹀凡缁忚璁块棶杩?/li>
public void bfs(Graph graph, Node start, Node end){
Queue<Node> queue;
List visited;
queue.offer(start);;
visited.add(start);
while (!queue.isEmpty()){
Node node = queue.poll();
visited.add(node);
process(node); //瀵瑰綋鍓嶅厓绱犺繘琛屽鐞?
nodes=generate_related_nodes(node);//鑾峰彇node鑺傜偣鐨勭浉鍏冲悗缁妭鐐癸紝涓斾粬浠病鏈夎璁块棶杩?
queue.push(nodes);
}
//other processing work
}
- 娣卞害浼樺厛鎼滅储鍙互浣跨敤閫掑綊鎴栬€呮爤鏉ュ疄鐜?/li>
#浣跨敤閫掑綊鐨勬柟娉曪紙甯哥敤锛?
#浼唬鐮?
visited = set()
def dfs(node, visited):
visited.add(node)
#澶勭悊杩囩▼
for next_node in node.children():
if not next_node in visited:
dfs(next_node, visited)
#浣跨敤杩唬锛堟爤锛夌殑鏂规硶
def dfs(self, tree):
if tree.root is None:
return []
visited, stack = [], [tree.root]
while stack:
node = stack.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node) #娌℃湁琚闂繃鐨勫瓙鑺傜偣
stack.push(nodes)
- 浜屽弶鏍戠殑灞傚簭閬嶅巻 https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
閲囩敤bfs鏉ヨВ鍐筹紝姣忔灏嗘爤涓殑鍏ㄩ儴鍏冪礌poll鍗充负璇ュ眰鐨勫厓绱狅紝鐒跺悗鍦╬oll鐨勮繃绋嬩腑灏嗗叾瀛╁瓙鑺傜偣offer杩涘幓
- 浜屽弶鏍戠殑鏈€澶ф繁搴?https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
閫掑綊锛宒fs
- 浜屽弶鏍戠殑鏈€灏忔繁搴?https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
涓€瀹氳娉ㄦ剰璇婚锛岀湅鍏跺鏈€灏忔繁搴︾殑瀹氫箟
鍙互浣跨敤閫掑綊鐨勬柟娉曪紝涔熷彲浠ヤ娇鐢╞fs锛屾瘡灞傞亶鍘嗙殑杩囩▼涓垽鏂槸鍚︿负鍙跺瓙鑺傜偣鏉ユ柇瀹氭槸鍚﹀仠姝紱涔熷彲浠ヤ娇鐢╠fs鐨勬柟娉?/li>
- 鎷彿鐢熸垚 https://leetcode-cn.com/problems/generate-parentheses/
鈶?鍋氶鏃剁殑璇尯锛氭兂瑕佹壘鍒颁竴绉嶄粠n-1瀵规嫭鍙风敓鎴恘瀵规嫭鍙风殑鏂规硶锛屼絾鏄€绘槸浼氭湁閲嶅鐨勶紝鐒跺悗灏遍櫡鍏ヤ簡鎵惧幓閲嶆柟娉曠殑姝诲惊鐜腑锛屽強鏃跺悗鏉ユ兂鎼滅储鏉ヨВ鍐筹紝杩樻槸鍦ㄦ€濊€冨幓閲嶇殑闂
鈶?浣嗘悳绱㈡牴鏈笉浼氫骇鐢熼噸澶嶇殑缁勫悎鏂瑰紡锛屾悳绱㈢殑鏈川鏄竴绉嶆灇涓撅紝鍙互浜х敓鎵€鏈夌殑缁勫悎鏂瑰紡锛屾悳绱㈤厤鍚堝壀鏋濇墠鏄纭殑瑙e喅鎬濊矾
鈶?鍒ゆ柇鎷彿鏄惁鍚堟硶锛氫换浣曚竴涓椂鍒诲乏鎷彿鐨勬暟閲忚澶т簬绛変簬鍙虫嫭鍙风殑鏁伴噺
涔濄€佸壀鏋?/h3>
- 鍓灊鏄悳绱腑缁忓父鐢ㄥ埌鐨勪紭鍖栫瓥鐣ワ紝鍏抽敭鍦ㄤ簬閲嶅鐨勬楠ゅ浣曡繘琛屾湁鏁堢殑鏍囪鍜屽垽瀹?/li>
- N 鐨囧悗 https://leetcode-cn.com/problems/n-queens/
- N鐨囧悗 II https://leetcode-cn.com/problems/n-queens-ii/
- N鐨囧悗闂鐨勯噸鐐瑰湪浜庡壀鏋濓紝浣跨敤绌洪棿鎹㈡椂闂寸殑鏂瑰紡锛屼娇鐢ㄤ竴浜涙暟缁勬垨鑰卻et鏉ユ爣璇嗗綋鍓嶄綅缃槸鍚﹀凡缁忔槸绂佺敤浣嶇疆锛屽阀濡欑殑鍦版柟鏄鏂滅嚎浣嶇疆鐨勫鐞嗭細瀵逛簬浣嶇疆[i][j]锛屽彲浠ラ€氳繃i+j鍜宨-j鐨勫敮涓€鎬х‘瀹氬叾浣嶄簬鍝袱鏉℃枩绾夸笂
- 鏈夋晥鐨勬暟鐙?https://leetcode-cn.com/problems/valid-sudoku/ 鍙屽眰寰幆妯℃嫙鍗冲彲
- 瑙f暟鐙?https://leetcode-cn.com/problems/sudoku-solver/ 鍙屽眰寰幆DFS锛屽紑杈熼澶栫殑绌洪棿鐢ㄤ簬鍒ゆ柇褰撳墠鍙緵閫夋嫨鐨勫€间互鍙婄敤鏉ュ垽鏂槸鍚﹀悎娉?/li>
鍗併€佷簩鍒嗘煡鎵?/h3>
- 鍓嶆彁鏉′欢锛歴orted锛堝崟璋冮€掑鎴栬€呴€掑噺锛夛紱bounded锛堝瓨鍦ㄤ笂涓嬬晫锛夛紱accessible by index锛堣兘澶熼€氳繃绱㈠紩璁块棶锛?/li>
- x 鐨勫钩鏂规牴 https://leetcode-cn.com/problems/sqrtx/
- 涓ょ瑙f硶锛氫簩鍒嗭紱鐗涢】杩唬娉?/li>
- 棰樼洰涓姹傝緭鍑虹殑缁撴灉鐨勬暣鏁伴儴鍒嗗嵆鍙紝鍙互灏濊瘯灏嗕唬鐮佸啓鍏紝杈撳嚭鎸囧畾绮惧害鐨勭粨鏋?/li>
@Test
public void test5(){
int num=1;
while (num!=-1){
Scanner in = new Scanner(System.in);
num = in.nextInt();
System.out.println(mySqrt(num,0.0001));
}
}
public double mySqrt(int num, double accuracy){
double left = 0;
double right = num;
while(right>=left){
double middle = (left+right)/2;
if(Math.abs(middle*middle-num)<=accuracy) return middle;
if(middle*middle>num) right=middle;
else left=middle;
}
return -1;
}
鍗佷竴銆佸瓧鍏告爲锛圱rie锛?/h3>
- Trie鏍戯紝鍗冲瓧鍏告爲锛屽張绉板崟璇嶆煡鎵炬爲鎴栭敭鏍戯紝鏄竴绉嶆爲褰㈢粨鏋勶紝鏄竴绉嶅搱甯屾爲鐨勫彉绉嶃€傚吀鍨嬪簲鐢ㄤ簬缁熻鍜屾帓搴忓ぇ閲忕殑瀛楃涓诧紙浣嗕笉浠呴檺浜庡瓧绗︿覆锛夛紝鎵€浠ョ粡甯歌鎼滅储寮曟搸绯荤粺鐢ㄤ簬鏂囨湰璇嶉缁熻
- 浼樼偣锛氭渶澶ч檺搴﹀湴鍑忓皯鏃犺皳鐨勫瓧绗︿覆姣旇緝锛屾煡璇㈡晥鐜囨瘮鍝堝笇琛ㄩ珮
- Trie鐨勬牳蹇冩€濇兂鏄┖闂存崲鏃堕棿锛屽埄鐢ㄥ瓧绗︿覆鐨勫叕鍏卞墠缂€鏉ラ檷浣庢煡璇㈡椂闂寸殑寮€閿€浠ヨ揪鍒版彁楂樻晥鐜囩殑鐩殑
-
Trie鏍戜娇鐢ㄤ竴鏉¤竟鏉ヤ唬琛ㄤ竴涓瓧姣嶏紝鍗曡瘝鐨勯暱搴﹀拰瀵绘壘璇ュ崟璇嶆壘杩囩殑璺緞鐨勯暱搴︾浉鍚?/p>
-
瀛楀吀鏍戠殑鍩烘湰鏁版嵁缁撴瀯
- 瀹炵幇 Trie (鍓嶇紑鏍? https://leetcode-cn.com/problems/implement-trie-prefix-tree/
public class Trie {
class TrieNode{
TrieNode[] next;
boolean isEnd;
public TrieNode(){
isEnd=false;
next = new TrieNode[26];
}
}
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
if(node.next[c-'a']==null){
node.next[c-'a']=new TrieNode();
}
node = node.next[c-'a'];
}
node.isEnd=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
node = node.next[c-'a'];
if(node == null) return false;
}
return node.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = root;
for(char c : prefix.toCharArray()){
node = node.next[c-'a'];
if(node == null) return false;
}
return true;
}
}
- 鍗曡瘝鎼滅储 https://leetcode-cn.com/problems/word-search/
dfs+鍥炴函鍗冲彲瑙e喅
- 鍗曡瘝鎼滅储 II https://leetcode-cn.com/problems/word-search-ii/)
鐩稿綋浜庡湪涓婁竴涓鐨勫熀纭€涓婏紝涓€娆¤鍒ゆ柇澶氫釜鍗曡瘝锛屽厛鎶婃墍鏈夌殑鍗曡瘝鏋勫缓鎴愪竴妫礣rie鏍戯紝鐒跺悗DFS鍒ゆ柇鍗曟鏄惁鍦ㄧ煩闃典腑鍙互鎵惧埌锛堝緟琛ヰ煋岋級
鍗佷簩銆佷綅杩愮畻
- 寮傛垨鐨勪竴涓噸瑕佺壒寰侊紝x^x=0
- 浣嶈繍绠楃殑甯哥敤鎿嶄綔锛?br>
x&1 == 0 x&1==1 鐢ㄦ潵鍒ゆ柇濂囧伓
x=x&(x-1) 娓呴浂鏈€浣庝綅鐨?
x&-x 寰楀埌鏈€浣庝綅鐨?
- 鉁呬綅杩愮畻缁忓父鐢ㄥ湪鏁?鐨勪釜鏁扮浉鍏崇殑棰樼洰涓?/li>
- 浣?鐨勪釜鏁?https://leetcode-cn.com/problems/number-of-1-bits/
鐢ㄤ笂闈㈢殑寮忓瓙灏卞彲浠ュ緢濂界殑瑙e喅
- 2鐨勫箓 https://leetcode-cn.com/problems/power-of-two/ 鍋氭硶鍚屼笂
- 姣旂壒浣嶈鏁?https://leetcode-cn.com/problems/counting-bits/
鍚堢悊鍒╃敤鍓嶉潰宸茬粡绠楀嚭鏉ョ殑缁撴灉锛坉p+浣嶈繍绠楋級
- N鐨囧悗 II https://leetcode-cn.com/problems/n-queens-ii/
涔嬪墠鐨勬柟娉曟槸浣跨敤鏁扮粍锛坈ol[]銆乸ie[]銆乶a[]锛夋潵璁板綍浣嶇疆鐨勫崰鐢ㄦ儏鍐碉紝杩欓噷鍊熷姪浣嶈繍绠楋紝浣跨敤涓変釜int绫诲瀷鐨勬暟鍊艰繘琛岃褰曪紝col姣旇緝濂界悊瑙e崰鐢ㄧ殑浣嶇疆缃?鍗冲彲锛屽浜巌nt绫诲瀷鐨刾ie鍜宯a瀹為檯涓婅褰曠殑鏄綋鍓嶈鐨勬瘡涓綅缃笂鐨勫厓绱犳槸鍚﹀湪涔嬪墠缁撴灉鐨勫瑙掔嚎鏂瑰悜涓婏紝杞崲鍒版柊琛岀殑鏃跺€欙紝pie宸︾Щ锛宯a鍙崇Щ
public class Queens {
int res= 0;
public int totalNQueens(int n) {
if(n<=0) return 0;
dfs(n,0,0,0,0);
return res;
}
public void dfs(int n, int row, int col, int pia, int na){
if(row==n){
res+=1;
return;
}
//璁$畻褰撳墠鍙敤鐨勪綅缃紝娉ㄦ剰浣跨敤鐨勬槸32浣嶇殑int锛岃娑堥櫎n浣嶄箣鍓嶇殑閭d簺0瀵筨its鐨勫奖鍝?
int bits = (~(col|pia|na))&((1<<n)-1);
while (bits!=0){
//鑾峰彇褰撳墠閫夊畾鐨?鐨勪綅缃?
int pos= bits&(-bits);
dfs(n,row+1,col|pos,(pia|pos)<<1,(na|pos)>>1);
//鍘绘帀鏈€鍚庝竴涓?
bits=bits&(bits-1);
}
}
}
- 鍐欎綅杩愮畻鐨勫叕寮忕殑鏃跺€欙紝涓€瀹氳浣跨敤鎷彿锛屽洜涓哄畠鐨勮繍绠椾紭鍏堢骇杈冧綆锛岄槻姝㈠嚭鐜伴敊璇?/li>
鍗佷笁銆佸姩鎬佽鍒?/h3>
- 馃А閫氳繃閫掑綊+璁板繂鍖栨潵鎺ㄥ鍑哄姩鎬佽鍒掔殑鏂规硶
- 鐘舵€佺殑瀹氫箟
- 鐘舵€佽浆绉绘柟绋嬶紝濡備綍鍒濆鍖栦篃寰堥噸瑕侊紝涓€鑸兘鏄垵濮嬪寲绗竴琛?/li>
- 鏈€浼樺瓙缁撴瀯
- 涓嶅悓璺緞 https://leetcode-cn.com/problems/unique-paths/ 鏁板鏂规硶鍗冲彲瑙e喅
- 涓嶅悓璺緞 II https://leetcode-cn.com/problems/unique-paths-ii/ 鍔ㄦ€佽鍒掞紝娉ㄦ剰鐗逛緥锛堣捣濮嬬偣鍜岄噸鐐规槸闅滅鐨勬儏鍐碉級
- 鐖ゼ姊?https://leetcode-cn.com/problems/climbing-stairs/
- 涓夎褰㈡渶灏忚矾寰勫拰 https://leetcode-cn.com/problems/triangle/
- 涔樼Н鏈€澶у瓙鏁扮粍 https://leetcode-cn.com/problems/maximum-product-subarray/
- 鍏充簬涔板崠鑲$エ鐨勯鐩?br>
涔板崠鑲$エ鐨勬渶浣虫椂鏈?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?II https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?III https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?IV https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
鏈€浣充拱鍗栬偂绁ㄦ椂鏈哄惈鍐峰喕鏈?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
涔板崠鑲$エ鐨勬渶浣虫椂鏈哄惈鎵嬬画璐?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
鎵╁睍鎯呭喌锛氱敱浜庨鐩腑瑕佹眰涓嶈兘鍚屾椂鎸佹湁澶氳偂锛屾墍浠ョ涓夌淮鍙湁0鍜?涓ょ鎯呭喌锛堟寔鏈夋垨鑰呮病鏈夛級锛屼絾鏄鏋滃厑璁告渶澶氬悓鏃舵寔鏈塳鑲$殑璇濓紝鏈€鍚庝竴缁存湁k绉嶏紝鍚屾牱瑕佸啀澶氫竴缁村惊鐜潵杩涜琛ㄧず
- 濡傛灉鑳藉姝g‘鐨勫鐘舵€佽繘琛屽畾涔夛紝閭d箞灏辩畻鏄垚鍔熶簡涓€鍗婏紱浠庝笂闈㈢殑绯诲垪棰樼洰锛屽彲浠ヨ€冭檻涓嬮潰鐨勬柟娉曪細
鏂规硶涓€锛氫粠dp[i]涓€缁村紑濮嬭€冭檻锛岃〃绀轰互i涓虹粓鐐癸紝缁撴灉鐨勬儏鍐点€傛灇涓炬瘡涓€涓彲鑳芥墽琛岀殑鍔ㄤ綔浠ュ強浜х敓鐨勭粨鏋滐紝鑰冭檻鎵ц杩欎釜鍔ㄤ綔瀵逛箣鍓嶇殑鐘舵€佹湁浠€涔堟牱鐨勮姹傦紵闇€瑕佷粈涔堟牱鐨勮緟鍔╀俊鎭紙鐘舵€侊級锛熸鏃跺彲鑳戒細鍙戠幇涓€缁寸殑dp涓嶈兘婊¤冻瑕佹眰锛屾鏃舵牴鎹渶瑕佺殑璧嬪€间俊鎭繘琛岀淮搴︾殑鎵╁厖鍗冲彲
鏂规硶浜岋細鍏堟€濊€冮€掑綊鐨勬柟娉曪紝浠庨€掑綊鏂规硶绉嶆壘鐏垫劅
- 鏈€闀块€掑瀛愬簭鍒?https://leetcode-cn.com/problems/longest-increasing-subsequence/
涓€鍏变笁绉嶆柟娉曪細鏆村姏dfs瀵绘壘锛沝p锛涚淮鎶や竴涓渶闀夸笂鍗囧瓙搴忓垪鐨勬暟缁?/li>
- 闆堕挶鍏戞崲 https://leetcode-cn.com/problems/coin-change/
鏈€濂界殑鎬濊€冭繃绋嬶細鍏堟兂濡備綍閫掑綊瑙e喅锛岀劧鍚庤浆鍖栦负鍔ㄦ€佽鍒?br>
锛堢粡甯哥敤鍒扮殑鏂规硶锛氳€冭檻鏈€鍚庝竴姝ラ噰鐢ㄤ粈涔堟牱鐨勫姩浣滐紝鐒跺悗鍐嶆€濊€冪敤涓嶇敤娣诲姞棰濆鐨勭淮搴︽潵瀛樺偍闇€瑕佺殑淇℃伅锛?/li>
鍗佸洓銆佸苟鏌ラ泦
鏂规硶浜岋細浜屽弶鎼滅储鏍?/li>
鏂规硶涓€锛氫娇鐢ㄥぇ椤跺爢瀹炵幇
鏂规硶浜岋細浣跨敤鍙岀闃熷垪缁存姢涓€涓弗鏍奸€掑鐨勫崟璋冮槦鍒?/li>
- 鏈川锛氶€氳繃hash鍑芥暟灏唙alue鏄犲皠鍒版煇涓綅缃笂锛屽疄鐜癘(1)鏌ユ壘
- 瀹炵幇锛欻ashMap/TreeMap锛堜簩鍙夋悳绱㈡爲锛夛紝HashSet/TreeSet
- 鏈夋晥鐨勫瓧姣嶅紓浣嶈瘝 https://leetcode-cn.com/problems/valid-anagram/)
- 涓ゆ暟涔嬪拰 https://leetcode-cn.com/problems/two-sum/
鍙互浣跨敤鍙屾寚閽堬紝涔熷彲浠ヤ娇鐢℉ashMap瑙e喅 - 涓夋暟涔嬪拰 https://leetcode-cn.com/problems/3sum/ sort+涓€灞傚惊鐜?鍙屾寚閽堥亶鍘? 娉ㄦ剰瀵光€樹笉閲嶅鈥欑殑澶勭悊
- 鍥涙暟涔嬪拰 https://leetcode-cn.com/problems/4sum/ 鍚屼笂
浜斻€佹爲銆佷簩鍙夋爲銆佷簩鍙夋悳绱㈡爲
- 浜屽弶鎼滅储鏍戯細鏍硅妭鐐圭殑鍊煎ぇ浜庡乏瀛愭爲锛屽皬浜庡彸瀛愭爲
- 浜屽弶鎼滅储鏍戠殑鎬ц川锛氫腑搴忛亶鍘嗕骇鐢熼€掑搴忓垪
- 楠岃瘉浜屽弶鎼滅储鏍? https://leetcode-cn.com/problems/validate-binary-search-tree/
- 瑙f硶锛氫腑搴忛亶鍘嗙粨鏋滃瓨鍌ㄤ笅鏉ラ獙璇佹槸鍚︿弗鏍奸€掑锛涙垨鑰咃紝姣忔璁板綍涓婁竴涓繑鍥炵殑鍊硷紝鍦ㄤ腑搴忛亶鍘嗕腑鍒ゆ柇鏄惁涓ユ牸閫掑
- 鍋氫簡涓€浜涢鐩彂鐜帮紝鐩稿悓鐨勬€濊矾涓嬶紝鍙嶈€岄€掑綊鐨勬柟娉曞張绠€鍗曘€佸張蹇?/li>
- 浜屽弶鎼滅储鏍戠殑鏈€杩戝叕鍏辩鍏?https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)
- 瑙f硶锛氳皥鍒颁簩鍙夋悳绱㈡爲涓€瀹氬拰鑺傜偣鐨勫ぇ灏忓叧绯绘湁鍏筹紝娉ㄦ剰鍦ㄦ渶杩戝叕鍏辩鍏堝浼氬彂鐢熺殑鍙樺寲锛歱銆乹涓ょ偣寮€濮嬪垎鍚憀eft銆乺ight涓よ竟
- 浜屽弶鏍戠殑鏈€杩戝叕鍏辩鍏?https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
- 瑙f硶锛氶€掑綊鐨勬€濇兂锛侊紒锛?/li>
鍏€侀€掑綊鍜屽垎娌?/h3>
- Pow(x, n) https://leetcode-cn.com/problems/powx-n/ 娉ㄦ剰n涓鸿礋鏁扮殑鎯呭喌
涓冦€佽椽蹇冪畻娉?/h3>
- 鎬绘槸鍋氬嚭瀵瑰綋鍓嶇幆澧冩渶浼樼殑閫夋嫨
- 閫傜敤璐績鐨勫満鏅細闂鑳藉鍒嗚В鎴愬瓙闂鏉ヨВ鍐筹紝瀛愰棶棰樼殑鏈€浼樿В鑳藉閫掓帹鍒版渶缁堥棶棰樼殑鏈€浼樿В銆傝繖绉嶅瓙闂鏈€浼樿В绉颁负鏈€浼樺瓙缁撴瀯銆?/li>
- 涔板崠鑲$エ鐨勬渶浣虫椂鏈?II https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
鍏€佸箍搴︽湁闄愭悳绱紙bfs锛変笌娣卞害浼樺厛鎼滅储锛坉fs锛?/h3>
- 鎰熻浜屽弶鏍戠殑鍓嶅簭閬嶅巻鏈夌偣鍍忔繁搴︽湁闄愭悳绱?/li>
- 骞垮害浼樺厛鎼滅储锛氫竴灞備竴灞傚湴鎼滐紝鍙互浣跨敤闃熷垪鏉ュ疄鐜帮紝瀵逛簬鏍戞潵璇达紝鏄病鏈夌幆瀛樺湪鐨勶紝浣嗗鏋滄槸鍥句笂鐨勬悳绱紝闇€瑕佷娇鐢ㄤ竴涓暟缁刬sVisit鏉ヨ褰曞綋鍓嶇殑鐐规槸鍚﹀凡缁忚璁块棶杩?/li>
public void bfs(Graph graph, Node start, Node end){
Queue<Node> queue;
List visited;
queue.offer(start);;
visited.add(start);
while (!queue.isEmpty()){
Node node = queue.poll();
visited.add(node);
process(node); //瀵瑰綋鍓嶅厓绱犺繘琛屽鐞?
nodes=generate_related_nodes(node);//鑾峰彇node鑺傜偣鐨勭浉鍏冲悗缁妭鐐癸紝涓斾粬浠病鏈夎璁块棶杩?
queue.push(nodes);
}
//other processing work
}
- 娣卞害浼樺厛鎼滅储鍙互浣跨敤閫掑綊鎴栬€呮爤鏉ュ疄鐜?/li>
#浣跨敤閫掑綊鐨勬柟娉曪紙甯哥敤锛?
#浼唬鐮?
visited = set()
def dfs(node, visited):
visited.add(node)
#澶勭悊杩囩▼
for next_node in node.children():
if not next_node in visited:
dfs(next_node, visited)
#浣跨敤杩唬锛堟爤锛夌殑鏂规硶
def dfs(self, tree):
if tree.root is None:
return []
visited, stack = [], [tree.root]
while stack:
node = stack.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node) #娌℃湁琚闂繃鐨勫瓙鑺傜偣
stack.push(nodes)
- 浜屽弶鏍戠殑灞傚簭閬嶅巻 https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
閲囩敤bfs鏉ヨВ鍐筹紝姣忔灏嗘爤涓殑鍏ㄩ儴鍏冪礌poll鍗充负璇ュ眰鐨勫厓绱狅紝鐒跺悗鍦╬oll鐨勮繃绋嬩腑灏嗗叾瀛╁瓙鑺傜偣offer杩涘幓
- 浜屽弶鏍戠殑鏈€澶ф繁搴?https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
閫掑綊锛宒fs
- 浜屽弶鏍戠殑鏈€灏忔繁搴?https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
涓€瀹氳娉ㄦ剰璇婚锛岀湅鍏跺鏈€灏忔繁搴︾殑瀹氫箟
鍙互浣跨敤閫掑綊鐨勬柟娉曪紝涔熷彲浠ヤ娇鐢╞fs锛屾瘡灞傞亶鍘嗙殑杩囩▼涓垽鏂槸鍚︿负鍙跺瓙鑺傜偣鏉ユ柇瀹氭槸鍚﹀仠姝紱涔熷彲浠ヤ娇鐢╠fs鐨勬柟娉?/li>
- 鎷彿鐢熸垚 https://leetcode-cn.com/problems/generate-parentheses/
鈶?鍋氶鏃剁殑璇尯锛氭兂瑕佹壘鍒颁竴绉嶄粠n-1瀵规嫭鍙风敓鎴恘瀵规嫭鍙风殑鏂规硶锛屼絾鏄€绘槸浼氭湁閲嶅鐨勶紝鐒跺悗灏遍櫡鍏ヤ簡鎵惧幓閲嶆柟娉曠殑姝诲惊鐜腑锛屽強鏃跺悗鏉ユ兂鎼滅储鏉ヨВ鍐筹紝杩樻槸鍦ㄦ€濊€冨幓閲嶇殑闂
鈶?浣嗘悳绱㈡牴鏈笉浼氫骇鐢熼噸澶嶇殑缁勫悎鏂瑰紡锛屾悳绱㈢殑鏈川鏄竴绉嶆灇涓撅紝鍙互浜х敓鎵€鏈夌殑缁勫悎鏂瑰紡锛屾悳绱㈤厤鍚堝壀鏋濇墠鏄纭殑瑙e喅鎬濊矾
鈶?鍒ゆ柇鎷彿鏄惁鍚堟硶锛氫换浣曚竴涓椂鍒诲乏鎷彿鐨勬暟閲忚澶т簬绛変簬鍙虫嫭鍙风殑鏁伴噺
涔濄€佸壀鏋?/h3>
- 鍓灊鏄悳绱腑缁忓父鐢ㄥ埌鐨勪紭鍖栫瓥鐣ワ紝鍏抽敭鍦ㄤ簬閲嶅鐨勬楠ゅ浣曡繘琛屾湁鏁堢殑鏍囪鍜屽垽瀹?/li>
- N 鐨囧悗 https://leetcode-cn.com/problems/n-queens/
- N鐨囧悗 II https://leetcode-cn.com/problems/n-queens-ii/
- N鐨囧悗闂鐨勯噸鐐瑰湪浜庡壀鏋濓紝浣跨敤绌洪棿鎹㈡椂闂寸殑鏂瑰紡锛屼娇鐢ㄤ竴浜涙暟缁勬垨鑰卻et鏉ユ爣璇嗗綋鍓嶄綅缃槸鍚﹀凡缁忔槸绂佺敤浣嶇疆锛屽阀濡欑殑鍦版柟鏄鏂滅嚎浣嶇疆鐨勫鐞嗭細瀵逛簬浣嶇疆[i][j]锛屽彲浠ラ€氳繃i+j鍜宨-j鐨勫敮涓€鎬х‘瀹氬叾浣嶄簬鍝袱鏉℃枩绾夸笂
- 鏈夋晥鐨勬暟鐙?https://leetcode-cn.com/problems/valid-sudoku/ 鍙屽眰寰幆妯℃嫙鍗冲彲
- 瑙f暟鐙?https://leetcode-cn.com/problems/sudoku-solver/ 鍙屽眰寰幆DFS锛屽紑杈熼澶栫殑绌洪棿鐢ㄤ簬鍒ゆ柇褰撳墠鍙緵閫夋嫨鐨勫€间互鍙婄敤鏉ュ垽鏂槸鍚﹀悎娉?/li>
鍗併€佷簩鍒嗘煡鎵?/h3>
- 鍓嶆彁鏉′欢锛歴orted锛堝崟璋冮€掑鎴栬€呴€掑噺锛夛紱bounded锛堝瓨鍦ㄤ笂涓嬬晫锛夛紱accessible by index锛堣兘澶熼€氳繃绱㈠紩璁块棶锛?/li>
- x 鐨勫钩鏂规牴 https://leetcode-cn.com/problems/sqrtx/
- 涓ょ瑙f硶锛氫簩鍒嗭紱鐗涢】杩唬娉?/li>
- 棰樼洰涓姹傝緭鍑虹殑缁撴灉鐨勬暣鏁伴儴鍒嗗嵆鍙紝鍙互灏濊瘯灏嗕唬鐮佸啓鍏紝杈撳嚭鎸囧畾绮惧害鐨勭粨鏋?/li>
@Test
public void test5(){
int num=1;
while (num!=-1){
Scanner in = new Scanner(System.in);
num = in.nextInt();
System.out.println(mySqrt(num,0.0001));
}
}
public double mySqrt(int num, double accuracy){
double left = 0;
double right = num;
while(right>=left){
double middle = (left+right)/2;
if(Math.abs(middle*middle-num)<=accuracy) return middle;
if(middle*middle>num) right=middle;
else left=middle;
}
return -1;
}
鍗佷竴銆佸瓧鍏告爲锛圱rie锛?/h3>
- Trie鏍戯紝鍗冲瓧鍏告爲锛屽張绉板崟璇嶆煡鎵炬爲鎴栭敭鏍戯紝鏄竴绉嶆爲褰㈢粨鏋勶紝鏄竴绉嶅搱甯屾爲鐨勫彉绉嶃€傚吀鍨嬪簲鐢ㄤ簬缁熻鍜屾帓搴忓ぇ閲忕殑瀛楃涓诧紙浣嗕笉浠呴檺浜庡瓧绗︿覆锛夛紝鎵€浠ョ粡甯歌鎼滅储寮曟搸绯荤粺鐢ㄤ簬鏂囨湰璇嶉缁熻
- 浼樼偣锛氭渶澶ч檺搴﹀湴鍑忓皯鏃犺皳鐨勫瓧绗︿覆姣旇緝锛屾煡璇㈡晥鐜囨瘮鍝堝笇琛ㄩ珮
- Trie鐨勬牳蹇冩€濇兂鏄┖闂存崲鏃堕棿锛屽埄鐢ㄥ瓧绗︿覆鐨勫叕鍏卞墠缂€鏉ラ檷浣庢煡璇㈡椂闂寸殑寮€閿€浠ヨ揪鍒版彁楂樻晥鐜囩殑鐩殑
-
Trie鏍戜娇鐢ㄤ竴鏉¤竟鏉ヤ唬琛ㄤ竴涓瓧姣嶏紝鍗曡瘝鐨勯暱搴﹀拰瀵绘壘璇ュ崟璇嶆壘杩囩殑璺緞鐨勯暱搴︾浉鍚?/p>
-
瀛楀吀鏍戠殑鍩烘湰鏁版嵁缁撴瀯
- 瀹炵幇 Trie (鍓嶇紑鏍? https://leetcode-cn.com/problems/implement-trie-prefix-tree/
public class Trie {
class TrieNode{
TrieNode[] next;
boolean isEnd;
public TrieNode(){
isEnd=false;
next = new TrieNode[26];
}
}
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
if(node.next[c-'a']==null){
node.next[c-'a']=new TrieNode();
}
node = node.next[c-'a'];
}
node.isEnd=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
node = node.next[c-'a'];
if(node == null) return false;
}
return node.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = root;
for(char c : prefix.toCharArray()){
node = node.next[c-'a'];
if(node == null) return false;
}
return true;
}
}
- 鍗曡瘝鎼滅储 https://leetcode-cn.com/problems/word-search/
dfs+鍥炴函鍗冲彲瑙e喅
- 鍗曡瘝鎼滅储 II https://leetcode-cn.com/problems/word-search-ii/)
鐩稿綋浜庡湪涓婁竴涓鐨勫熀纭€涓婏紝涓€娆¤鍒ゆ柇澶氫釜鍗曡瘝锛屽厛鎶婃墍鏈夌殑鍗曡瘝鏋勫缓鎴愪竴妫礣rie鏍戯紝鐒跺悗DFS鍒ゆ柇鍗曟鏄惁鍦ㄧ煩闃典腑鍙互鎵惧埌锛堝緟琛ヰ煋岋級
鍗佷簩銆佷綅杩愮畻
- 寮傛垨鐨勪竴涓噸瑕佺壒寰侊紝x^x=0
- 浣嶈繍绠楃殑甯哥敤鎿嶄綔锛?br>
x&1 == 0 x&1==1 鐢ㄦ潵鍒ゆ柇濂囧伓
x=x&(x-1) 娓呴浂鏈€浣庝綅鐨?
x&-x 寰楀埌鏈€浣庝綅鐨?
- 鉁呬綅杩愮畻缁忓父鐢ㄥ湪鏁?鐨勪釜鏁扮浉鍏崇殑棰樼洰涓?/li>
- 浣?鐨勪釜鏁?https://leetcode-cn.com/problems/number-of-1-bits/
鐢ㄤ笂闈㈢殑寮忓瓙灏卞彲浠ュ緢濂界殑瑙e喅
- 2鐨勫箓 https://leetcode-cn.com/problems/power-of-two/ 鍋氭硶鍚屼笂
- 姣旂壒浣嶈鏁?https://leetcode-cn.com/problems/counting-bits/
鍚堢悊鍒╃敤鍓嶉潰宸茬粡绠楀嚭鏉ョ殑缁撴灉锛坉p+浣嶈繍绠楋級
- N鐨囧悗 II https://leetcode-cn.com/problems/n-queens-ii/
涔嬪墠鐨勬柟娉曟槸浣跨敤鏁扮粍锛坈ol[]銆乸ie[]銆乶a[]锛夋潵璁板綍浣嶇疆鐨勫崰鐢ㄦ儏鍐碉紝杩欓噷鍊熷姪浣嶈繍绠楋紝浣跨敤涓変釜int绫诲瀷鐨勬暟鍊艰繘琛岃褰曪紝col姣旇緝濂界悊瑙e崰鐢ㄧ殑浣嶇疆缃?鍗冲彲锛屽浜巌nt绫诲瀷鐨刾ie鍜宯a瀹為檯涓婅褰曠殑鏄綋鍓嶈鐨勬瘡涓綅缃笂鐨勫厓绱犳槸鍚﹀湪涔嬪墠缁撴灉鐨勫瑙掔嚎鏂瑰悜涓婏紝杞崲鍒版柊琛岀殑鏃跺€欙紝pie宸︾Щ锛宯a鍙崇Щ
public class Queens {
int res= 0;
public int totalNQueens(int n) {
if(n<=0) return 0;
dfs(n,0,0,0,0);
return res;
}
public void dfs(int n, int row, int col, int pia, int na){
if(row==n){
res+=1;
return;
}
//璁$畻褰撳墠鍙敤鐨勪綅缃紝娉ㄦ剰浣跨敤鐨勬槸32浣嶇殑int锛岃娑堥櫎n浣嶄箣鍓嶇殑閭d簺0瀵筨its鐨勫奖鍝?
int bits = (~(col|pia|na))&((1<<n)-1);
while (bits!=0){
//鑾峰彇褰撳墠閫夊畾鐨?鐨勪綅缃?
int pos= bits&(-bits);
dfs(n,row+1,col|pos,(pia|pos)<<1,(na|pos)>>1);
//鍘绘帀鏈€鍚庝竴涓?
bits=bits&(bits-1);
}
}
}
- 鍐欎綅杩愮畻鐨勫叕寮忕殑鏃跺€欙紝涓€瀹氳浣跨敤鎷彿锛屽洜涓哄畠鐨勮繍绠椾紭鍏堢骇杈冧綆锛岄槻姝㈠嚭鐜伴敊璇?/li>
鍗佷笁銆佸姩鎬佽鍒?/h3>
- 馃А閫氳繃閫掑綊+璁板繂鍖栨潵鎺ㄥ鍑哄姩鎬佽鍒掔殑鏂规硶
- 鐘舵€佺殑瀹氫箟
- 鐘舵€佽浆绉绘柟绋嬶紝濡備綍鍒濆鍖栦篃寰堥噸瑕侊紝涓€鑸兘鏄垵濮嬪寲绗竴琛?/li>
- 鏈€浼樺瓙缁撴瀯
- 涓嶅悓璺緞 https://leetcode-cn.com/problems/unique-paths/ 鏁板鏂规硶鍗冲彲瑙e喅
- 涓嶅悓璺緞 II https://leetcode-cn.com/problems/unique-paths-ii/ 鍔ㄦ€佽鍒掞紝娉ㄦ剰鐗逛緥锛堣捣濮嬬偣鍜岄噸鐐规槸闅滅鐨勬儏鍐碉級
- 鐖ゼ姊?https://leetcode-cn.com/problems/climbing-stairs/
- 涓夎褰㈡渶灏忚矾寰勫拰 https://leetcode-cn.com/problems/triangle/
- 涔樼Н鏈€澶у瓙鏁扮粍 https://leetcode-cn.com/problems/maximum-product-subarray/
- 鍏充簬涔板崠鑲$エ鐨勯鐩?br>
涔板崠鑲$エ鐨勬渶浣虫椂鏈?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?II https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?III https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?IV https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
鏈€浣充拱鍗栬偂绁ㄦ椂鏈哄惈鍐峰喕鏈?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
涔板崠鑲$エ鐨勬渶浣虫椂鏈哄惈鎵嬬画璐?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
鎵╁睍鎯呭喌锛氱敱浜庨鐩腑瑕佹眰涓嶈兘鍚屾椂鎸佹湁澶氳偂锛屾墍浠ョ涓夌淮鍙湁0鍜?涓ょ鎯呭喌锛堟寔鏈夋垨鑰呮病鏈夛級锛屼絾鏄鏋滃厑璁告渶澶氬悓鏃舵寔鏈塳鑲$殑璇濓紝鏈€鍚庝竴缁存湁k绉嶏紝鍚屾牱瑕佸啀澶氫竴缁村惊鐜潵杩涜琛ㄧず
- 濡傛灉鑳藉姝g‘鐨勫鐘舵€佽繘琛屽畾涔夛紝閭d箞灏辩畻鏄垚鍔熶簡涓€鍗婏紱浠庝笂闈㈢殑绯诲垪棰樼洰锛屽彲浠ヨ€冭檻涓嬮潰鐨勬柟娉曪細
鏂规硶涓€锛氫粠dp[i]涓€缁村紑濮嬭€冭檻锛岃〃绀轰互i涓虹粓鐐癸紝缁撴灉鐨勬儏鍐点€傛灇涓炬瘡涓€涓彲鑳芥墽琛岀殑鍔ㄤ綔浠ュ強浜х敓鐨勭粨鏋滐紝鑰冭檻鎵ц杩欎釜鍔ㄤ綔瀵逛箣鍓嶇殑鐘舵€佹湁浠€涔堟牱鐨勮姹傦紵闇€瑕佷粈涔堟牱鐨勮緟鍔╀俊鎭紙鐘舵€侊級锛熸鏃跺彲鑳戒細鍙戠幇涓€缁寸殑dp涓嶈兘婊¤冻瑕佹眰锛屾鏃舵牴鎹渶瑕佺殑璧嬪€间俊鎭繘琛岀淮搴︾殑鎵╁厖鍗冲彲
鏂规硶浜岋細鍏堟€濊€冮€掑綊鐨勬柟娉曪紝浠庨€掑綊鏂规硶绉嶆壘鐏垫劅
- 鏈€闀块€掑瀛愬簭鍒?https://leetcode-cn.com/problems/longest-increasing-subsequence/
涓€鍏变笁绉嶆柟娉曪細鏆村姏dfs瀵绘壘锛沝p锛涚淮鎶や竴涓渶闀夸笂鍗囧瓙搴忓垪鐨勬暟缁?/li>
- 闆堕挶鍏戞崲 https://leetcode-cn.com/problems/coin-change/
鏈€濂界殑鎬濊€冭繃绋嬶細鍏堟兂濡備綍閫掑綊瑙e喅锛岀劧鍚庤浆鍖栦负鍔ㄦ€佽鍒?br>
锛堢粡甯哥敤鍒扮殑鏂规硶锛氳€冭檻鏈€鍚庝竴姝ラ噰鐢ㄤ粈涔堟牱鐨勫姩浣滐紝鐒跺悗鍐嶆€濊€冪敤涓嶇敤娣诲姞棰濆鐨勭淮搴︽潵瀛樺偍闇€瑕佺殑淇℃伅锛?/li>
鍗佸洓銆佸苟鏌ラ泦
- 鎬绘槸鍋氬嚭瀵瑰綋鍓嶇幆澧冩渶浼樼殑閫夋嫨
- 閫傜敤璐績鐨勫満鏅細闂鑳藉鍒嗚В鎴愬瓙闂鏉ヨВ鍐筹紝瀛愰棶棰樼殑鏈€浼樿В鑳藉閫掓帹鍒版渶缁堥棶棰樼殑鏈€浼樿В銆傝繖绉嶅瓙闂鏈€浼樿В绉颁负鏈€浼樺瓙缁撴瀯銆?/li>
- 涔板崠鑲$エ鐨勬渶浣虫椂鏈?II https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
鍏€佸箍搴︽湁闄愭悳绱紙bfs锛変笌娣卞害浼樺厛鎼滅储锛坉fs锛?/h3>
- 鎰熻浜屽弶鏍戠殑鍓嶅簭閬嶅巻鏈夌偣鍍忔繁搴︽湁闄愭悳绱?/li>
- 骞垮害浼樺厛鎼滅储锛氫竴灞備竴灞傚湴鎼滐紝鍙互浣跨敤闃熷垪鏉ュ疄鐜帮紝瀵逛簬鏍戞潵璇达紝鏄病鏈夌幆瀛樺湪鐨勶紝浣嗗鏋滄槸鍥句笂鐨勬悳绱紝闇€瑕佷娇鐢ㄤ竴涓暟缁刬sVisit鏉ヨ褰曞綋鍓嶇殑鐐规槸鍚﹀凡缁忚璁块棶杩?/li>
public void bfs(Graph graph, Node start, Node end){
Queue<Node> queue;
List visited;
queue.offer(start);;
visited.add(start);
while (!queue.isEmpty()){
Node node = queue.poll();
visited.add(node);
process(node); //瀵瑰綋鍓嶅厓绱犺繘琛屽鐞?
nodes=generate_related_nodes(node);//鑾峰彇node鑺傜偣鐨勭浉鍏冲悗缁妭鐐癸紝涓斾粬浠病鏈夎璁块棶杩?
queue.push(nodes);
}
//other processing work
}
- 娣卞害浼樺厛鎼滅储鍙互浣跨敤閫掑綊鎴栬€呮爤鏉ュ疄鐜?/li>
#浣跨敤閫掑綊鐨勬柟娉曪紙甯哥敤锛?
#浼唬鐮?
visited = set()
def dfs(node, visited):
visited.add(node)
#澶勭悊杩囩▼
for next_node in node.children():
if not next_node in visited:
dfs(next_node, visited)
#浣跨敤杩唬锛堟爤锛夌殑鏂规硶
def dfs(self, tree):
if tree.root is None:
return []
visited, stack = [], [tree.root]
while stack:
node = stack.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node) #娌℃湁琚闂繃鐨勫瓙鑺傜偣
stack.push(nodes)
- 浜屽弶鏍戠殑灞傚簭閬嶅巻 https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
閲囩敤bfs鏉ヨВ鍐筹紝姣忔灏嗘爤涓殑鍏ㄩ儴鍏冪礌poll鍗充负璇ュ眰鐨勫厓绱狅紝鐒跺悗鍦╬oll鐨勮繃绋嬩腑灏嗗叾瀛╁瓙鑺傜偣offer杩涘幓
- 浜屽弶鏍戠殑鏈€澶ф繁搴?https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
閫掑綊锛宒fs
- 浜屽弶鏍戠殑鏈€灏忔繁搴?https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
涓€瀹氳娉ㄦ剰璇婚锛岀湅鍏跺鏈€灏忔繁搴︾殑瀹氫箟
鍙互浣跨敤閫掑綊鐨勬柟娉曪紝涔熷彲浠ヤ娇鐢╞fs锛屾瘡灞傞亶鍘嗙殑杩囩▼涓垽鏂槸鍚︿负鍙跺瓙鑺傜偣鏉ユ柇瀹氭槸鍚﹀仠姝紱涔熷彲浠ヤ娇鐢╠fs鐨勬柟娉?/li>
- 鎷彿鐢熸垚 https://leetcode-cn.com/problems/generate-parentheses/
鈶?鍋氶鏃剁殑璇尯锛氭兂瑕佹壘鍒颁竴绉嶄粠n-1瀵规嫭鍙风敓鎴恘瀵规嫭鍙风殑鏂规硶锛屼絾鏄€绘槸浼氭湁閲嶅鐨勶紝鐒跺悗灏遍櫡鍏ヤ簡鎵惧幓閲嶆柟娉曠殑姝诲惊鐜腑锛屽強鏃跺悗鏉ユ兂鎼滅储鏉ヨВ鍐筹紝杩樻槸鍦ㄦ€濊€冨幓閲嶇殑闂
鈶?浣嗘悳绱㈡牴鏈笉浼氫骇鐢熼噸澶嶇殑缁勫悎鏂瑰紡锛屾悳绱㈢殑鏈川鏄竴绉嶆灇涓撅紝鍙互浜х敓鎵€鏈夌殑缁勫悎鏂瑰紡锛屾悳绱㈤厤鍚堝壀鏋濇墠鏄纭殑瑙e喅鎬濊矾
鈶?鍒ゆ柇鎷彿鏄惁鍚堟硶锛氫换浣曚竴涓椂鍒诲乏鎷彿鐨勬暟閲忚澶т簬绛変簬鍙虫嫭鍙风殑鏁伴噺
涔濄€佸壀鏋?/h3>
- 鍓灊鏄悳绱腑缁忓父鐢ㄥ埌鐨勪紭鍖栫瓥鐣ワ紝鍏抽敭鍦ㄤ簬閲嶅鐨勬楠ゅ浣曡繘琛屾湁鏁堢殑鏍囪鍜屽垽瀹?/li>
- N 鐨囧悗 https://leetcode-cn.com/problems/n-queens/
- N鐨囧悗 II https://leetcode-cn.com/problems/n-queens-ii/
- N鐨囧悗闂鐨勯噸鐐瑰湪浜庡壀鏋濓紝浣跨敤绌洪棿鎹㈡椂闂寸殑鏂瑰紡锛屼娇鐢ㄤ竴浜涙暟缁勬垨鑰卻et鏉ユ爣璇嗗綋鍓嶄綅缃槸鍚﹀凡缁忔槸绂佺敤浣嶇疆锛屽阀濡欑殑鍦版柟鏄鏂滅嚎浣嶇疆鐨勫鐞嗭細瀵逛簬浣嶇疆[i][j]锛屽彲浠ラ€氳繃i+j鍜宨-j鐨勫敮涓€鎬х‘瀹氬叾浣嶄簬鍝袱鏉℃枩绾夸笂
- 鏈夋晥鐨勬暟鐙?https://leetcode-cn.com/problems/valid-sudoku/ 鍙屽眰寰幆妯℃嫙鍗冲彲
- 瑙f暟鐙?https://leetcode-cn.com/problems/sudoku-solver/ 鍙屽眰寰幆DFS锛屽紑杈熼澶栫殑绌洪棿鐢ㄤ簬鍒ゆ柇褰撳墠鍙緵閫夋嫨鐨勫€间互鍙婄敤鏉ュ垽鏂槸鍚﹀悎娉?/li>
鍗併€佷簩鍒嗘煡鎵?/h3>
- 鍓嶆彁鏉′欢锛歴orted锛堝崟璋冮€掑鎴栬€呴€掑噺锛夛紱bounded锛堝瓨鍦ㄤ笂涓嬬晫锛夛紱accessible by index锛堣兘澶熼€氳繃绱㈠紩璁块棶锛?/li>
- x 鐨勫钩鏂规牴 https://leetcode-cn.com/problems/sqrtx/
- 涓ょ瑙f硶锛氫簩鍒嗭紱鐗涢】杩唬娉?/li>
- 棰樼洰涓姹傝緭鍑虹殑缁撴灉鐨勬暣鏁伴儴鍒嗗嵆鍙紝鍙互灏濊瘯灏嗕唬鐮佸啓鍏紝杈撳嚭鎸囧畾绮惧害鐨勭粨鏋?/li>
@Test
public void test5(){
int num=1;
while (num!=-1){
Scanner in = new Scanner(System.in);
num = in.nextInt();
System.out.println(mySqrt(num,0.0001));
}
}
public double mySqrt(int num, double accuracy){
double left = 0;
double right = num;
while(right>=left){
double middle = (left+right)/2;
if(Math.abs(middle*middle-num)<=accuracy) return middle;
if(middle*middle>num) right=middle;
else left=middle;
}
return -1;
}
鍗佷竴銆佸瓧鍏告爲锛圱rie锛?/h3>
- Trie鏍戯紝鍗冲瓧鍏告爲锛屽張绉板崟璇嶆煡鎵炬爲鎴栭敭鏍戯紝鏄竴绉嶆爲褰㈢粨鏋勶紝鏄竴绉嶅搱甯屾爲鐨勫彉绉嶃€傚吀鍨嬪簲鐢ㄤ簬缁熻鍜屾帓搴忓ぇ閲忕殑瀛楃涓诧紙浣嗕笉浠呴檺浜庡瓧绗︿覆锛夛紝鎵€浠ョ粡甯歌鎼滅储寮曟搸绯荤粺鐢ㄤ簬鏂囨湰璇嶉缁熻
- 浼樼偣锛氭渶澶ч檺搴﹀湴鍑忓皯鏃犺皳鐨勫瓧绗︿覆姣旇緝锛屾煡璇㈡晥鐜囨瘮鍝堝笇琛ㄩ珮
- Trie鐨勬牳蹇冩€濇兂鏄┖闂存崲鏃堕棿锛屽埄鐢ㄥ瓧绗︿覆鐨勫叕鍏卞墠缂€鏉ラ檷浣庢煡璇㈡椂闂寸殑寮€閿€浠ヨ揪鍒版彁楂樻晥鐜囩殑鐩殑
-
Trie鏍戜娇鐢ㄤ竴鏉¤竟鏉ヤ唬琛ㄤ竴涓瓧姣嶏紝鍗曡瘝鐨勯暱搴﹀拰瀵绘壘璇ュ崟璇嶆壘杩囩殑璺緞鐨勯暱搴︾浉鍚?/p>
-
瀛楀吀鏍戠殑鍩烘湰鏁版嵁缁撴瀯
- 瀹炵幇 Trie (鍓嶇紑鏍? https://leetcode-cn.com/problems/implement-trie-prefix-tree/
public class Trie {
class TrieNode{
TrieNode[] next;
boolean isEnd;
public TrieNode(){
isEnd=false;
next = new TrieNode[26];
}
}
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
if(node.next[c-'a']==null){
node.next[c-'a']=new TrieNode();
}
node = node.next[c-'a'];
}
node.isEnd=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
node = node.next[c-'a'];
if(node == null) return false;
}
return node.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = root;
for(char c : prefix.toCharArray()){
node = node.next[c-'a'];
if(node == null) return false;
}
return true;
}
}
- 鍗曡瘝鎼滅储 https://leetcode-cn.com/problems/word-search/
dfs+鍥炴函鍗冲彲瑙e喅
- 鍗曡瘝鎼滅储 II https://leetcode-cn.com/problems/word-search-ii/)
鐩稿綋浜庡湪涓婁竴涓鐨勫熀纭€涓婏紝涓€娆¤鍒ゆ柇澶氫釜鍗曡瘝锛屽厛鎶婃墍鏈夌殑鍗曡瘝鏋勫缓鎴愪竴妫礣rie鏍戯紝鐒跺悗DFS鍒ゆ柇鍗曟鏄惁鍦ㄧ煩闃典腑鍙互鎵惧埌锛堝緟琛ヰ煋岋級
鍗佷簩銆佷綅杩愮畻
- 寮傛垨鐨勪竴涓噸瑕佺壒寰侊紝x^x=0
- 浣嶈繍绠楃殑甯哥敤鎿嶄綔锛?br>
x&1 == 0 x&1==1 鐢ㄦ潵鍒ゆ柇濂囧伓
x=x&(x-1) 娓呴浂鏈€浣庝綅鐨?
x&-x 寰楀埌鏈€浣庝綅鐨?
- 鉁呬綅杩愮畻缁忓父鐢ㄥ湪鏁?鐨勪釜鏁扮浉鍏崇殑棰樼洰涓?/li>
- 浣?鐨勪釜鏁?https://leetcode-cn.com/problems/number-of-1-bits/
鐢ㄤ笂闈㈢殑寮忓瓙灏卞彲浠ュ緢濂界殑瑙e喅
- 2鐨勫箓 https://leetcode-cn.com/problems/power-of-two/ 鍋氭硶鍚屼笂
- 姣旂壒浣嶈鏁?https://leetcode-cn.com/problems/counting-bits/
鍚堢悊鍒╃敤鍓嶉潰宸茬粡绠楀嚭鏉ョ殑缁撴灉锛坉p+浣嶈繍绠楋級
- N鐨囧悗 II https://leetcode-cn.com/problems/n-queens-ii/
涔嬪墠鐨勬柟娉曟槸浣跨敤鏁扮粍锛坈ol[]銆乸ie[]銆乶a[]锛夋潵璁板綍浣嶇疆鐨勫崰鐢ㄦ儏鍐碉紝杩欓噷鍊熷姪浣嶈繍绠楋紝浣跨敤涓変釜int绫诲瀷鐨勬暟鍊艰繘琛岃褰曪紝col姣旇緝濂界悊瑙e崰鐢ㄧ殑浣嶇疆缃?鍗冲彲锛屽浜巌nt绫诲瀷鐨刾ie鍜宯a瀹為檯涓婅褰曠殑鏄綋鍓嶈鐨勬瘡涓綅缃笂鐨勫厓绱犳槸鍚﹀湪涔嬪墠缁撴灉鐨勫瑙掔嚎鏂瑰悜涓婏紝杞崲鍒版柊琛岀殑鏃跺€欙紝pie宸︾Щ锛宯a鍙崇Щ
public class Queens {
int res= 0;
public int totalNQueens(int n) {
if(n<=0) return 0;
dfs(n,0,0,0,0);
return res;
}
public void dfs(int n, int row, int col, int pia, int na){
if(row==n){
res+=1;
return;
}
//璁$畻褰撳墠鍙敤鐨勪綅缃紝娉ㄦ剰浣跨敤鐨勬槸32浣嶇殑int锛岃娑堥櫎n浣嶄箣鍓嶇殑閭d簺0瀵筨its鐨勫奖鍝?
int bits = (~(col|pia|na))&((1<<n)-1);
while (bits!=0){
//鑾峰彇褰撳墠閫夊畾鐨?鐨勪綅缃?
int pos= bits&(-bits);
dfs(n,row+1,col|pos,(pia|pos)<<1,(na|pos)>>1);
//鍘绘帀鏈€鍚庝竴涓?
bits=bits&(bits-1);
}
}
}
- 鍐欎綅杩愮畻鐨勫叕寮忕殑鏃跺€欙紝涓€瀹氳浣跨敤鎷彿锛屽洜涓哄畠鐨勮繍绠椾紭鍏堢骇杈冧綆锛岄槻姝㈠嚭鐜伴敊璇?/li>
鍗佷笁銆佸姩鎬佽鍒?/h3>
- 馃А閫氳繃閫掑綊+璁板繂鍖栨潵鎺ㄥ鍑哄姩鎬佽鍒掔殑鏂规硶
- 鐘舵€佺殑瀹氫箟
- 鐘舵€佽浆绉绘柟绋嬶紝濡備綍鍒濆鍖栦篃寰堥噸瑕侊紝涓€鑸兘鏄垵濮嬪寲绗竴琛?/li>
- 鏈€浼樺瓙缁撴瀯
- 涓嶅悓璺緞 https://leetcode-cn.com/problems/unique-paths/ 鏁板鏂规硶鍗冲彲瑙e喅
- 涓嶅悓璺緞 II https://leetcode-cn.com/problems/unique-paths-ii/ 鍔ㄦ€佽鍒掞紝娉ㄦ剰鐗逛緥锛堣捣濮嬬偣鍜岄噸鐐规槸闅滅鐨勬儏鍐碉級
- 鐖ゼ姊?https://leetcode-cn.com/problems/climbing-stairs/
- 涓夎褰㈡渶灏忚矾寰勫拰 https://leetcode-cn.com/problems/triangle/
- 涔樼Н鏈€澶у瓙鏁扮粍 https://leetcode-cn.com/problems/maximum-product-subarray/
- 鍏充簬涔板崠鑲$エ鐨勯鐩?br>
涔板崠鑲$エ鐨勬渶浣虫椂鏈?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?II https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?III https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?IV https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
鏈€浣充拱鍗栬偂绁ㄦ椂鏈哄惈鍐峰喕鏈?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
涔板崠鑲$エ鐨勬渶浣虫椂鏈哄惈鎵嬬画璐?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
鎵╁睍鎯呭喌锛氱敱浜庨鐩腑瑕佹眰涓嶈兘鍚屾椂鎸佹湁澶氳偂锛屾墍浠ョ涓夌淮鍙湁0鍜?涓ょ鎯呭喌锛堟寔鏈夋垨鑰呮病鏈夛級锛屼絾鏄鏋滃厑璁告渶澶氬悓鏃舵寔鏈塳鑲$殑璇濓紝鏈€鍚庝竴缁存湁k绉嶏紝鍚屾牱瑕佸啀澶氫竴缁村惊鐜潵杩涜琛ㄧず
- 濡傛灉鑳藉姝g‘鐨勫鐘舵€佽繘琛屽畾涔夛紝閭d箞灏辩畻鏄垚鍔熶簡涓€鍗婏紱浠庝笂闈㈢殑绯诲垪棰樼洰锛屽彲浠ヨ€冭檻涓嬮潰鐨勬柟娉曪細
鏂规硶涓€锛氫粠dp[i]涓€缁村紑濮嬭€冭檻锛岃〃绀轰互i涓虹粓鐐癸紝缁撴灉鐨勬儏鍐点€傛灇涓炬瘡涓€涓彲鑳芥墽琛岀殑鍔ㄤ綔浠ュ強浜х敓鐨勭粨鏋滐紝鑰冭檻鎵ц杩欎釜鍔ㄤ綔瀵逛箣鍓嶇殑鐘舵€佹湁浠€涔堟牱鐨勮姹傦紵闇€瑕佷粈涔堟牱鐨勮緟鍔╀俊鎭紙鐘舵€侊級锛熸鏃跺彲鑳戒細鍙戠幇涓€缁寸殑dp涓嶈兘婊¤冻瑕佹眰锛屾鏃舵牴鎹渶瑕佺殑璧嬪€间俊鎭繘琛岀淮搴︾殑鎵╁厖鍗冲彲
鏂规硶浜岋細鍏堟€濊€冮€掑綊鐨勬柟娉曪紝浠庨€掑綊鏂规硶绉嶆壘鐏垫劅
- 鏈€闀块€掑瀛愬簭鍒?https://leetcode-cn.com/problems/longest-increasing-subsequence/
涓€鍏变笁绉嶆柟娉曪細鏆村姏dfs瀵绘壘锛沝p锛涚淮鎶や竴涓渶闀夸笂鍗囧瓙搴忓垪鐨勬暟缁?/li>
- 闆堕挶鍏戞崲 https://leetcode-cn.com/problems/coin-change/
鏈€濂界殑鎬濊€冭繃绋嬶細鍏堟兂濡備綍閫掑綊瑙e喅锛岀劧鍚庤浆鍖栦负鍔ㄦ€佽鍒?br>
锛堢粡甯哥敤鍒扮殑鏂规硶锛氳€冭檻鏈€鍚庝竴姝ラ噰鐢ㄤ粈涔堟牱鐨勫姩浣滐紝鐒跺悗鍐嶆€濊€冪敤涓嶇敤娣诲姞棰濆鐨勭淮搴︽潵瀛樺偍闇€瑕佺殑淇℃伅锛?/li>
鍗佸洓銆佸苟鏌ラ泦
public void bfs(Graph graph, Node start, Node end){
Queue<Node> queue;
List visited;
queue.offer(start);;
visited.add(start);
while (!queue.isEmpty()){
Node node = queue.poll();
visited.add(node);
process(node); //瀵瑰綋鍓嶅厓绱犺繘琛屽鐞?
nodes=generate_related_nodes(node);//鑾峰彇node鑺傜偣鐨勭浉鍏冲悗缁妭鐐癸紝涓斾粬浠病鏈夎璁块棶杩?
queue.push(nodes);
}
//other processing work
}
#浣跨敤閫掑綊鐨勬柟娉曪紙甯哥敤锛?
#浼唬鐮?
visited = set()
def dfs(node, visited):
visited.add(node)
#澶勭悊杩囩▼
for next_node in node.children():
if not next_node in visited:
dfs(next_node, visited)
#浣跨敤杩唬锛堟爤锛夌殑鏂规硶
def dfs(self, tree):
if tree.root is None:
return []
visited, stack = [], [tree.root]
while stack:
node = stack.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node) #娌℃湁琚闂繃鐨勫瓙鑺傜偣
stack.push(nodes)
閲囩敤bfs鏉ヨВ鍐筹紝姣忔灏嗘爤涓殑鍏ㄩ儴鍏冪礌poll鍗充负璇ュ眰鐨勫厓绱狅紝鐒跺悗鍦╬oll鐨勮繃绋嬩腑灏嗗叾瀛╁瓙鑺傜偣offer杩涘幓
閫掑綊锛宒fs
涓€瀹氳娉ㄦ剰璇婚锛岀湅鍏跺鏈€灏忔繁搴︾殑瀹氫箟
鍙互浣跨敤閫掑綊鐨勬柟娉曪紝涔熷彲浠ヤ娇鐢╞fs锛屾瘡灞傞亶鍘嗙殑杩囩▼涓垽鏂槸鍚︿负鍙跺瓙鑺傜偣鏉ユ柇瀹氭槸鍚﹀仠姝紱涔熷彲浠ヤ娇鐢╠fs鐨勬柟娉?/li>
鈶?鍋氶鏃剁殑璇尯锛氭兂瑕佹壘鍒颁竴绉嶄粠n-1瀵规嫭鍙风敓鎴恘瀵规嫭鍙风殑鏂规硶锛屼絾鏄€绘槸浼氭湁閲嶅鐨勶紝鐒跺悗灏遍櫡鍏ヤ簡鎵惧幓閲嶆柟娉曠殑姝诲惊鐜腑锛屽強鏃跺悗鏉ユ兂鎼滅储鏉ヨВ鍐筹紝杩樻槸鍦ㄦ€濊€冨幓閲嶇殑闂
鈶?浣嗘悳绱㈡牴鏈笉浼氫骇鐢熼噸澶嶇殑缁勫悎鏂瑰紡锛屾悳绱㈢殑鏈川鏄竴绉嶆灇涓撅紝鍙互浜х敓鎵€鏈夌殑缁勫悎鏂瑰紡锛屾悳绱㈤厤鍚堝壀鏋濇墠鏄纭殑瑙e喅鎬濊矾
鈶?鍒ゆ柇鎷彿鏄惁鍚堟硶锛氫换浣曚竴涓椂鍒诲乏鎷彿鐨勬暟閲忚澶т簬绛変簬鍙虫嫭鍙风殑鏁伴噺
- 鍓灊鏄悳绱腑缁忓父鐢ㄥ埌鐨勪紭鍖栫瓥鐣ワ紝鍏抽敭鍦ㄤ簬閲嶅鐨勬楠ゅ浣曡繘琛屾湁鏁堢殑鏍囪鍜屽垽瀹?/li>
- N 鐨囧悗 https://leetcode-cn.com/problems/n-queens/
- N鐨囧悗 II https://leetcode-cn.com/problems/n-queens-ii/
- N鐨囧悗闂鐨勯噸鐐瑰湪浜庡壀鏋濓紝浣跨敤绌洪棿鎹㈡椂闂寸殑鏂瑰紡锛屼娇鐢ㄤ竴浜涙暟缁勬垨鑰卻et鏉ユ爣璇嗗綋鍓嶄綅缃槸鍚﹀凡缁忔槸绂佺敤浣嶇疆锛屽阀濡欑殑鍦版柟鏄鏂滅嚎浣嶇疆鐨勫鐞嗭細瀵逛簬浣嶇疆[i][j]锛屽彲浠ラ€氳繃i+j鍜宨-j鐨勫敮涓€鎬х‘瀹氬叾浣嶄簬鍝袱鏉℃枩绾夸笂
- 鏈夋晥鐨勬暟鐙?https://leetcode-cn.com/problems/valid-sudoku/ 鍙屽眰寰幆妯℃嫙鍗冲彲
- 瑙f暟鐙?https://leetcode-cn.com/problems/sudoku-solver/ 鍙屽眰寰幆DFS锛屽紑杈熼澶栫殑绌洪棿鐢ㄤ簬鍒ゆ柇褰撳墠鍙緵閫夋嫨鐨勫€间互鍙婄敤鏉ュ垽鏂槸鍚﹀悎娉?/li>
鍗併€佷簩鍒嗘煡鎵?/h3>
- 鍓嶆彁鏉′欢锛歴orted锛堝崟璋冮€掑鎴栬€呴€掑噺锛夛紱bounded锛堝瓨鍦ㄤ笂涓嬬晫锛夛紱accessible by index锛堣兘澶熼€氳繃绱㈠紩璁块棶锛?/li>
- x 鐨勫钩鏂规牴 https://leetcode-cn.com/problems/sqrtx/
- 涓ょ瑙f硶锛氫簩鍒嗭紱鐗涢】杩唬娉?/li>
- 棰樼洰涓姹傝緭鍑虹殑缁撴灉鐨勬暣鏁伴儴鍒嗗嵆鍙紝鍙互灏濊瘯灏嗕唬鐮佸啓鍏紝杈撳嚭鎸囧畾绮惧害鐨勭粨鏋?/li>
@Test
public void test5(){
int num=1;
while (num!=-1){
Scanner in = new Scanner(System.in);
num = in.nextInt();
System.out.println(mySqrt(num,0.0001));
}
}
public double mySqrt(int num, double accuracy){
double left = 0;
double right = num;
while(right>=left){
double middle = (left+right)/2;
if(Math.abs(middle*middle-num)<=accuracy) return middle;
if(middle*middle>num) right=middle;
else left=middle;
}
return -1;
}
鍗佷竴銆佸瓧鍏告爲锛圱rie锛?/h3>
- Trie鏍戯紝鍗冲瓧鍏告爲锛屽張绉板崟璇嶆煡鎵炬爲鎴栭敭鏍戯紝鏄竴绉嶆爲褰㈢粨鏋勶紝鏄竴绉嶅搱甯屾爲鐨勫彉绉嶃€傚吀鍨嬪簲鐢ㄤ簬缁熻鍜屾帓搴忓ぇ閲忕殑瀛楃涓诧紙浣嗕笉浠呴檺浜庡瓧绗︿覆锛夛紝鎵€浠ョ粡甯歌鎼滅储寮曟搸绯荤粺鐢ㄤ簬鏂囨湰璇嶉缁熻
- 浼樼偣锛氭渶澶ч檺搴﹀湴鍑忓皯鏃犺皳鐨勫瓧绗︿覆姣旇緝锛屾煡璇㈡晥鐜囨瘮鍝堝笇琛ㄩ珮
- Trie鐨勬牳蹇冩€濇兂鏄┖闂存崲鏃堕棿锛屽埄鐢ㄥ瓧绗︿覆鐨勫叕鍏卞墠缂€鏉ラ檷浣庢煡璇㈡椂闂寸殑寮€閿€浠ヨ揪鍒版彁楂樻晥鐜囩殑鐩殑
-
Trie鏍戜娇鐢ㄤ竴鏉¤竟鏉ヤ唬琛ㄤ竴涓瓧姣嶏紝鍗曡瘝鐨勯暱搴﹀拰瀵绘壘璇ュ崟璇嶆壘杩囩殑璺緞鐨勯暱搴︾浉鍚?/p>
-
瀛楀吀鏍戠殑鍩烘湰鏁版嵁缁撴瀯
- 瀹炵幇 Trie (鍓嶇紑鏍? https://leetcode-cn.com/problems/implement-trie-prefix-tree/
public class Trie {
class TrieNode{
TrieNode[] next;
boolean isEnd;
public TrieNode(){
isEnd=false;
next = new TrieNode[26];
}
}
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
if(node.next[c-'a']==null){
node.next[c-'a']=new TrieNode();
}
node = node.next[c-'a'];
}
node.isEnd=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
node = node.next[c-'a'];
if(node == null) return false;
}
return node.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = root;
for(char c : prefix.toCharArray()){
node = node.next[c-'a'];
if(node == null) return false;
}
return true;
}
}
- 鍗曡瘝鎼滅储 https://leetcode-cn.com/problems/word-search/
dfs+鍥炴函鍗冲彲瑙e喅
- 鍗曡瘝鎼滅储 II https://leetcode-cn.com/problems/word-search-ii/)
鐩稿綋浜庡湪涓婁竴涓鐨勫熀纭€涓婏紝涓€娆¤鍒ゆ柇澶氫釜鍗曡瘝锛屽厛鎶婃墍鏈夌殑鍗曡瘝鏋勫缓鎴愪竴妫礣rie鏍戯紝鐒跺悗DFS鍒ゆ柇鍗曟鏄惁鍦ㄧ煩闃典腑鍙互鎵惧埌锛堝緟琛ヰ煋岋級
鍗佷簩銆佷綅杩愮畻
- 寮傛垨鐨勪竴涓噸瑕佺壒寰侊紝x^x=0
- 浣嶈繍绠楃殑甯哥敤鎿嶄綔锛?br>
x&1 == 0 x&1==1 鐢ㄦ潵鍒ゆ柇濂囧伓
x=x&(x-1) 娓呴浂鏈€浣庝綅鐨?
x&-x 寰楀埌鏈€浣庝綅鐨?
- 鉁呬綅杩愮畻缁忓父鐢ㄥ湪鏁?鐨勪釜鏁扮浉鍏崇殑棰樼洰涓?/li>
- 浣?鐨勪釜鏁?https://leetcode-cn.com/problems/number-of-1-bits/
鐢ㄤ笂闈㈢殑寮忓瓙灏卞彲浠ュ緢濂界殑瑙e喅
- 2鐨勫箓 https://leetcode-cn.com/problems/power-of-two/ 鍋氭硶鍚屼笂
- 姣旂壒浣嶈鏁?https://leetcode-cn.com/problems/counting-bits/
鍚堢悊鍒╃敤鍓嶉潰宸茬粡绠楀嚭鏉ョ殑缁撴灉锛坉p+浣嶈繍绠楋級
- N鐨囧悗 II https://leetcode-cn.com/problems/n-queens-ii/
涔嬪墠鐨勬柟娉曟槸浣跨敤鏁扮粍锛坈ol[]銆乸ie[]銆乶a[]锛夋潵璁板綍浣嶇疆鐨勫崰鐢ㄦ儏鍐碉紝杩欓噷鍊熷姪浣嶈繍绠楋紝浣跨敤涓変釜int绫诲瀷鐨勬暟鍊艰繘琛岃褰曪紝col姣旇緝濂界悊瑙e崰鐢ㄧ殑浣嶇疆缃?鍗冲彲锛屽浜巌nt绫诲瀷鐨刾ie鍜宯a瀹為檯涓婅褰曠殑鏄綋鍓嶈鐨勬瘡涓綅缃笂鐨勫厓绱犳槸鍚﹀湪涔嬪墠缁撴灉鐨勫瑙掔嚎鏂瑰悜涓婏紝杞崲鍒版柊琛岀殑鏃跺€欙紝pie宸︾Щ锛宯a鍙崇Щ
public class Queens {
int res= 0;
public int totalNQueens(int n) {
if(n<=0) return 0;
dfs(n,0,0,0,0);
return res;
}
public void dfs(int n, int row, int col, int pia, int na){
if(row==n){
res+=1;
return;
}
//璁$畻褰撳墠鍙敤鐨勪綅缃紝娉ㄦ剰浣跨敤鐨勬槸32浣嶇殑int锛岃娑堥櫎n浣嶄箣鍓嶇殑閭d簺0瀵筨its鐨勫奖鍝?
int bits = (~(col|pia|na))&((1<<n)-1);
while (bits!=0){
//鑾峰彇褰撳墠閫夊畾鐨?鐨勪綅缃?
int pos= bits&(-bits);
dfs(n,row+1,col|pos,(pia|pos)<<1,(na|pos)>>1);
//鍘绘帀鏈€鍚庝竴涓?
bits=bits&(bits-1);
}
}
}
- 鍐欎綅杩愮畻鐨勫叕寮忕殑鏃跺€欙紝涓€瀹氳浣跨敤鎷彿锛屽洜涓哄畠鐨勮繍绠椾紭鍏堢骇杈冧綆锛岄槻姝㈠嚭鐜伴敊璇?/li>
鍗佷笁銆佸姩鎬佽鍒?/h3>
- 馃А閫氳繃閫掑綊+璁板繂鍖栨潵鎺ㄥ鍑哄姩鎬佽鍒掔殑鏂规硶
- 鐘舵€佺殑瀹氫箟
- 鐘舵€佽浆绉绘柟绋嬶紝濡備綍鍒濆鍖栦篃寰堥噸瑕侊紝涓€鑸兘鏄垵濮嬪寲绗竴琛?/li>
- 鏈€浼樺瓙缁撴瀯
- 涓嶅悓璺緞 https://leetcode-cn.com/problems/unique-paths/ 鏁板鏂规硶鍗冲彲瑙e喅
- 涓嶅悓璺緞 II https://leetcode-cn.com/problems/unique-paths-ii/ 鍔ㄦ€佽鍒掞紝娉ㄦ剰鐗逛緥锛堣捣濮嬬偣鍜岄噸鐐规槸闅滅鐨勬儏鍐碉級
- 鐖ゼ姊?https://leetcode-cn.com/problems/climbing-stairs/
- 涓夎褰㈡渶灏忚矾寰勫拰 https://leetcode-cn.com/problems/triangle/
- 涔樼Н鏈€澶у瓙鏁扮粍 https://leetcode-cn.com/problems/maximum-product-subarray/
- 鍏充簬涔板崠鑲$エ鐨勯鐩?br>
涔板崠鑲$エ鐨勬渶浣虫椂鏈?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?II https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?III https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?IV https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
鏈€浣充拱鍗栬偂绁ㄦ椂鏈哄惈鍐峰喕鏈?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
涔板崠鑲$エ鐨勬渶浣虫椂鏈哄惈鎵嬬画璐?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
鎵╁睍鎯呭喌锛氱敱浜庨鐩腑瑕佹眰涓嶈兘鍚屾椂鎸佹湁澶氳偂锛屾墍浠ョ涓夌淮鍙湁0鍜?涓ょ鎯呭喌锛堟寔鏈夋垨鑰呮病鏈夛級锛屼絾鏄鏋滃厑璁告渶澶氬悓鏃舵寔鏈塳鑲$殑璇濓紝鏈€鍚庝竴缁存湁k绉嶏紝鍚屾牱瑕佸啀澶氫竴缁村惊鐜潵杩涜琛ㄧず
- 濡傛灉鑳藉姝g‘鐨勫鐘舵€佽繘琛屽畾涔夛紝閭d箞灏辩畻鏄垚鍔熶簡涓€鍗婏紱浠庝笂闈㈢殑绯诲垪棰樼洰锛屽彲浠ヨ€冭檻涓嬮潰鐨勬柟娉曪細
鏂规硶涓€锛氫粠dp[i]涓€缁村紑濮嬭€冭檻锛岃〃绀轰互i涓虹粓鐐癸紝缁撴灉鐨勬儏鍐点€傛灇涓炬瘡涓€涓彲鑳芥墽琛岀殑鍔ㄤ綔浠ュ強浜х敓鐨勭粨鏋滐紝鑰冭檻鎵ц杩欎釜鍔ㄤ綔瀵逛箣鍓嶇殑鐘舵€佹湁浠€涔堟牱鐨勮姹傦紵闇€瑕佷粈涔堟牱鐨勮緟鍔╀俊鎭紙鐘舵€侊級锛熸鏃跺彲鑳戒細鍙戠幇涓€缁寸殑dp涓嶈兘婊¤冻瑕佹眰锛屾鏃舵牴鎹渶瑕佺殑璧嬪€间俊鎭繘琛岀淮搴︾殑鎵╁厖鍗冲彲
鏂规硶浜岋細鍏堟€濊€冮€掑綊鐨勬柟娉曪紝浠庨€掑綊鏂规硶绉嶆壘鐏垫劅
- 鏈€闀块€掑瀛愬簭鍒?https://leetcode-cn.com/problems/longest-increasing-subsequence/
涓€鍏变笁绉嶆柟娉曪細鏆村姏dfs瀵绘壘锛沝p锛涚淮鎶や竴涓渶闀夸笂鍗囧瓙搴忓垪鐨勬暟缁?/li>
- 闆堕挶鍏戞崲 https://leetcode-cn.com/problems/coin-change/
鏈€濂界殑鎬濊€冭繃绋嬶細鍏堟兂濡備綍閫掑綊瑙e喅锛岀劧鍚庤浆鍖栦负鍔ㄦ€佽鍒?br>
锛堢粡甯哥敤鍒扮殑鏂规硶锛氳€冭檻鏈€鍚庝竴姝ラ噰鐢ㄤ粈涔堟牱鐨勫姩浣滐紝鐒跺悗鍐嶆€濊€冪敤涓嶇敤娣诲姞棰濆鐨勭淮搴︽潵瀛樺偍闇€瑕佺殑淇℃伅锛?/li>
鍗佸洓銆佸苟鏌ラ泦
@Test
public void test5(){
int num=1;
while (num!=-1){
Scanner in = new Scanner(System.in);
num = in.nextInt();
System.out.println(mySqrt(num,0.0001));
}
}
public double mySqrt(int num, double accuracy){
double left = 0;
double right = num;
while(right>=left){
double middle = (left+right)/2;
if(Math.abs(middle*middle-num)<=accuracy) return middle;
if(middle*middle>num) right=middle;
else left=middle;
}
return -1;
}
- Trie鏍戯紝鍗冲瓧鍏告爲锛屽張绉板崟璇嶆煡鎵炬爲鎴栭敭鏍戯紝鏄竴绉嶆爲褰㈢粨鏋勶紝鏄竴绉嶅搱甯屾爲鐨勫彉绉嶃€傚吀鍨嬪簲鐢ㄤ簬缁熻鍜屾帓搴忓ぇ閲忕殑瀛楃涓诧紙浣嗕笉浠呴檺浜庡瓧绗︿覆锛夛紝鎵€浠ョ粡甯歌鎼滅储寮曟搸绯荤粺鐢ㄤ簬鏂囨湰璇嶉缁熻
- 浼樼偣锛氭渶澶ч檺搴﹀湴鍑忓皯鏃犺皳鐨勫瓧绗︿覆姣旇緝锛屾煡璇㈡晥鐜囨瘮鍝堝笇琛ㄩ珮
- Trie鐨勬牳蹇冩€濇兂鏄┖闂存崲鏃堕棿锛屽埄鐢ㄥ瓧绗︿覆鐨勫叕鍏卞墠缂€鏉ラ檷浣庢煡璇㈡椂闂寸殑寮€閿€浠ヨ揪鍒版彁楂樻晥鐜囩殑鐩殑
-
Trie鏍戜娇鐢ㄤ竴鏉¤竟鏉ヤ唬琛ㄤ竴涓瓧姣嶏紝鍗曡瘝鐨勯暱搴﹀拰瀵绘壘璇ュ崟璇嶆壘杩囩殑璺緞鐨勯暱搴︾浉鍚?/p>
-
瀛楀吀鏍戠殑鍩烘湰鏁版嵁缁撴瀯
- 瀹炵幇 Trie (鍓嶇紑鏍? https://leetcode-cn.com/problems/implement-trie-prefix-tree/
public class Trie {
class TrieNode{
TrieNode[] next;
boolean isEnd;
public TrieNode(){
isEnd=false;
next = new TrieNode[26];
}
}
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
if(node.next[c-'a']==null){
node.next[c-'a']=new TrieNode();
}
node = node.next[c-'a'];
}
node.isEnd=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
node = node.next[c-'a'];
if(node == null) return false;
}
return node.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = root;
for(char c : prefix.toCharArray()){
node = node.next[c-'a'];
if(node == null) return false;
}
return true;
}
}
- 鍗曡瘝鎼滅储 https://leetcode-cn.com/problems/word-search/
dfs+鍥炴函鍗冲彲瑙e喅 - 鍗曡瘝鎼滅储 II https://leetcode-cn.com/problems/word-search-ii/)
鐩稿綋浜庡湪涓婁竴涓鐨勫熀纭€涓婏紝涓€娆¤鍒ゆ柇澶氫釜鍗曡瘝锛屽厛鎶婃墍鏈夌殑鍗曡瘝鏋勫缓鎴愪竴妫礣rie鏍戯紝鐒跺悗DFS鍒ゆ柇鍗曟鏄惁鍦ㄧ煩闃典腑鍙互鎵惧埌锛堝緟琛ヰ煋岋級
鍗佷簩銆佷綅杩愮畻
- 寮傛垨鐨勪竴涓噸瑕佺壒寰侊紝x^x=0
- 浣嶈繍绠楃殑甯哥敤鎿嶄綔锛?br>
x&1 == 0 x&1==1 鐢ㄦ潵鍒ゆ柇濂囧伓
x=x&(x-1) 娓呴浂鏈€浣庝綅鐨?
x&-x 寰楀埌鏈€浣庝綅鐨? - 鉁呬綅杩愮畻缁忓父鐢ㄥ湪鏁?鐨勪釜鏁扮浉鍏崇殑棰樼洰涓?/li>
- 浣?鐨勪釜鏁?https://leetcode-cn.com/problems/number-of-1-bits/
鐢ㄤ笂闈㈢殑寮忓瓙灏卞彲浠ュ緢濂界殑瑙e喅 - 2鐨勫箓 https://leetcode-cn.com/problems/power-of-two/ 鍋氭硶鍚屼笂
- 姣旂壒浣嶈鏁?https://leetcode-cn.com/problems/counting-bits/
鍚堢悊鍒╃敤鍓嶉潰宸茬粡绠楀嚭鏉ョ殑缁撴灉锛坉p+浣嶈繍绠楋級 - N鐨囧悗 II https://leetcode-cn.com/problems/n-queens-ii/
涔嬪墠鐨勬柟娉曟槸浣跨敤鏁扮粍锛坈ol[]銆乸ie[]銆乶a[]锛夋潵璁板綍浣嶇疆鐨勫崰鐢ㄦ儏鍐碉紝杩欓噷鍊熷姪浣嶈繍绠楋紝浣跨敤涓変釜int绫诲瀷鐨勬暟鍊艰繘琛岃褰曪紝col姣旇緝濂界悊瑙e崰鐢ㄧ殑浣嶇疆缃?鍗冲彲锛屽浜巌nt绫诲瀷鐨刾ie鍜宯a瀹為檯涓婅褰曠殑鏄綋鍓嶈鐨勬瘡涓綅缃笂鐨勫厓绱犳槸鍚﹀湪涔嬪墠缁撴灉鐨勫瑙掔嚎鏂瑰悜涓婏紝杞崲鍒版柊琛岀殑鏃跺€欙紝pie宸︾Щ锛宯a鍙崇Щ
public class Queens {
int res= 0;
public int totalNQueens(int n) {
if(n<=0) return 0;
dfs(n,0,0,0,0);
return res;
}
public void dfs(int n, int row, int col, int pia, int na){
if(row==n){
res+=1;
return;
}
//璁$畻褰撳墠鍙敤鐨勪綅缃紝娉ㄦ剰浣跨敤鐨勬槸32浣嶇殑int锛岃娑堥櫎n浣嶄箣鍓嶇殑閭d簺0瀵筨its鐨勫奖鍝?
int bits = (~(col|pia|na))&((1<<n)-1);
while (bits!=0){
//鑾峰彇褰撳墠閫夊畾鐨?鐨勪綅缃?
int pos= bits&(-bits);
dfs(n,row+1,col|pos,(pia|pos)<<1,(na|pos)>>1);
//鍘绘帀鏈€鍚庝竴涓?
bits=bits&(bits-1);
}
}
}
- 鍐欎綅杩愮畻鐨勫叕寮忕殑鏃跺€欙紝涓€瀹氳浣跨敤鎷彿锛屽洜涓哄畠鐨勮繍绠椾紭鍏堢骇杈冧綆锛岄槻姝㈠嚭鐜伴敊璇?/li>
鍗佷笁銆佸姩鎬佽鍒?/h3>
- 馃А閫氳繃閫掑綊+璁板繂鍖栨潵鎺ㄥ鍑哄姩鎬佽鍒掔殑鏂规硶
- 鐘舵€佺殑瀹氫箟
- 鐘舵€佽浆绉绘柟绋嬶紝濡備綍鍒濆鍖栦篃寰堥噸瑕侊紝涓€鑸兘鏄垵濮嬪寲绗竴琛?/li>
- 鏈€浼樺瓙缁撴瀯
- 涓嶅悓璺緞 https://leetcode-cn.com/problems/unique-paths/ 鏁板鏂规硶鍗冲彲瑙e喅
- 涓嶅悓璺緞 II https://leetcode-cn.com/problems/unique-paths-ii/ 鍔ㄦ€佽鍒掞紝娉ㄦ剰鐗逛緥锛堣捣濮嬬偣鍜岄噸鐐规槸闅滅鐨勬儏鍐碉級
- 鐖ゼ姊?https://leetcode-cn.com/problems/climbing-stairs/
- 涓夎褰㈡渶灏忚矾寰勫拰 https://leetcode-cn.com/problems/triangle/
- 涔樼Н鏈€澶у瓙鏁扮粍 https://leetcode-cn.com/problems/maximum-product-subarray/
- 鍏充簬涔板崠鑲$エ鐨勯鐩?br>
涔板崠鑲$エ鐨勬渶浣虫椂鏈?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?II https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?III https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?IV https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
鏈€浣充拱鍗栬偂绁ㄦ椂鏈哄惈鍐峰喕鏈?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
涔板崠鑲$エ鐨勬渶浣虫椂鏈哄惈鎵嬬画璐?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
鎵╁睍鎯呭喌锛氱敱浜庨鐩腑瑕佹眰涓嶈兘鍚屾椂鎸佹湁澶氳偂锛屾墍浠ョ涓夌淮鍙湁0鍜?涓ょ鎯呭喌锛堟寔鏈夋垨鑰呮病鏈夛級锛屼絾鏄鏋滃厑璁告渶澶氬悓鏃舵寔鏈塳鑲$殑璇濓紝鏈€鍚庝竴缁存湁k绉嶏紝鍚屾牱瑕佸啀澶氫竴缁村惊鐜潵杩涜琛ㄧず
- 濡傛灉鑳藉姝g‘鐨勫鐘舵€佽繘琛屽畾涔夛紝閭d箞灏辩畻鏄垚鍔熶簡涓€鍗婏紱浠庝笂闈㈢殑绯诲垪棰樼洰锛屽彲浠ヨ€冭檻涓嬮潰鐨勬柟娉曪細
鏂规硶涓€锛氫粠dp[i]涓€缁村紑濮嬭€冭檻锛岃〃绀轰互i涓虹粓鐐癸紝缁撴灉鐨勬儏鍐点€傛灇涓炬瘡涓€涓彲鑳芥墽琛岀殑鍔ㄤ綔浠ュ強浜х敓鐨勭粨鏋滐紝鑰冭檻鎵ц杩欎釜鍔ㄤ綔瀵逛箣鍓嶇殑鐘舵€佹湁浠€涔堟牱鐨勮姹傦紵闇€瑕佷粈涔堟牱鐨勮緟鍔╀俊鎭紙鐘舵€侊級锛熸鏃跺彲鑳戒細鍙戠幇涓€缁寸殑dp涓嶈兘婊¤冻瑕佹眰锛屾鏃舵牴鎹渶瑕佺殑璧嬪€间俊鎭繘琛岀淮搴︾殑鎵╁厖鍗冲彲
鏂规硶浜岋細鍏堟€濊€冮€掑綊鐨勬柟娉曪紝浠庨€掑綊鏂规硶绉嶆壘鐏垫劅
- 鏈€闀块€掑瀛愬簭鍒?https://leetcode-cn.com/problems/longest-increasing-subsequence/
涓€鍏变笁绉嶆柟娉曪細鏆村姏dfs瀵绘壘锛沝p锛涚淮鎶や竴涓渶闀夸笂鍗囧瓙搴忓垪鐨勬暟缁?/li>
- 闆堕挶鍏戞崲 https://leetcode-cn.com/problems/coin-change/
鏈€濂界殑鎬濊€冭繃绋嬶細鍏堟兂濡備綍閫掑綊瑙e喅锛岀劧鍚庤浆鍖栦负鍔ㄦ€佽鍒?br>
锛堢粡甯哥敤鍒扮殑鏂规硶锛氳€冭檻鏈€鍚庝竴姝ラ噰鐢ㄤ粈涔堟牱鐨勫姩浣滐紝鐒跺悗鍐嶆€濊€冪敤涓嶇敤娣诲姞棰濆鐨勭淮搴︽潵瀛樺偍闇€瑕佺殑淇℃伅锛?/li>
鍗佸洓銆佸苟鏌ラ泦
涔板崠鑲$エ鐨勬渶浣虫椂鏈?II https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?III https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
涔板崠鑲$エ鐨勬渶浣虫椂鏈?IV https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
鏈€浣充拱鍗栬偂绁ㄦ椂鏈哄惈鍐峰喕鏈?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
涔板崠鑲$エ鐨勬渶浣虫椂鏈哄惈鎵嬬画璐?https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
鎵╁睍鎯呭喌锛氱敱浜庨鐩腑瑕佹眰涓嶈兘鍚屾椂鎸佹湁澶氳偂锛屾墍浠ョ涓夌淮鍙湁0鍜?涓ょ鎯呭喌锛堟寔鏈夋垨鑰呮病鏈夛級锛屼絾鏄鏋滃厑璁告渶澶氬悓鏃舵寔鏈塳鑲$殑璇濓紝鏈€鍚庝竴缁存湁k绉嶏紝鍚屾牱瑕佸啀澶氫竴缁村惊鐜潵杩涜琛ㄧず
鏂规硶涓€锛氫粠dp[i]涓€缁村紑濮嬭€冭檻锛岃〃绀轰互i涓虹粓鐐癸紝缁撴灉鐨勬儏鍐点€傛灇涓炬瘡涓€涓彲鑳芥墽琛岀殑鍔ㄤ綔浠ュ強浜х敓鐨勭粨鏋滐紝鑰冭檻鎵ц杩欎釜鍔ㄤ綔瀵逛箣鍓嶇殑鐘舵€佹湁浠€涔堟牱鐨勮姹傦紵闇€瑕佷粈涔堟牱鐨勮緟鍔╀俊鎭紙鐘舵€侊級锛熸鏃跺彲鑳戒細鍙戠幇涓€缁寸殑dp涓嶈兘婊¤冻瑕佹眰锛屾鏃舵牴鎹渶瑕佺殑璧嬪€间俊鎭繘琛岀淮搴︾殑鎵╁厖鍗冲彲
鏂规硶浜岋細鍏堟€濊€冮€掑綊鐨勬柟娉曪紝浠庨€掑綊鏂规硶绉嶆壘鐏垫劅
涓€鍏变笁绉嶆柟娉曪細鏆村姏dfs瀵绘壘锛沝p锛涚淮鎶や竴涓渶闀夸笂鍗囧瓙搴忓垪鐨勬暟缁?/li>
鏈€濂界殑鎬濊€冭繃绋嬶細鍏堟兂濡備綍閫掑綊瑙e喅锛岀劧鍚庤浆鍖栦负鍔ㄦ€佽鍒?br> 锛堢粡甯哥敤鍒扮殑鏂规硶锛氳€冭檻鏈€鍚庝竴姝ラ噰鐢ㄤ粈涔堟牱鐨勫姩浣滐紝鐒跺悗鍐嶆€濊€冪敤涓嶇敤娣诲姞棰濆鐨勭淮搴︽潵瀛樺偍闇€瑕佺殑淇℃伅锛?/li>
涔嬪墠鐪嬭繃浜嗭紝涔熷仛浜嗙瑪璁? https://www.jianshu.com/p/a380c8ad5b88
- 宀涘笨鏁伴噺 https://leetcode-cn.com/problems/number-of-islands/ DFS鎴栬€呭苟鏌ラ泦
鍗佷簲銆丩RU Cache
-
LRU锛圠east Recently used锛夋渶杩戞渶灏戜娇鐢紝涓€鍗婁娇鐢ㄥ弻鍚戦摼琛ㄦ潵瀹炵幇锛孫(1)瀹炵幇鏌ヨ锛堢涓€涓級銆佷慨鏀瑰拰鏇存柊
- LRU 缂撳瓨鏈哄埗 https://leetcode-cn.com/problems/lru-cache/
闇€瑕佷娇鐢℉ashMap锛岀劧鍚庤嚜宸卞疄鐜颁竴涓弻鍚戦摼琛ㄣ€備娇鐢ㄨ櫄鎷熺殑澶村熬鑺傜偣浼氭洿瀹规槗瑙e喅闂