【leetcode】
1.?Two Sum
【題目】https://leetcode.com/problems/two-sum/description/
【思路】將數(shù)組 利用 map 處理 即可
【代碼】
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int>& nums, int target) { 4 // 哈希表存儲(chǔ) 值->下標(biāo) 的映射 5 unordered_map<int, int> indices; 6 7 for (int i = 0; i < nums.size(); i++) 8 { 9 int temp = target - nums[i]; 10 if (indices.find(temp) != indices.end() && indices[temp] != i) 11 { 12 return vector<int> {indices[temp], i}; 13 } 14 indices.emplace(nums[i], i); 15 } 16 } 17 }; C++ 1 class Solution { 2 public int[] twoSum(int[] nums, int target) { 3 Map<Integer, Integer> indeces = new HashMap<>(); 4 for(int i=0;i<nums.length;++i) { 5 int temp = target - nums[i]; 6 if(indeces.containsKey(temp)) { 7 return new int[] {indeces.get(temp), i}; 8 } 9 indeces.put(nums[i], i); 10 } 11 return null; 12 } 13 } Java【get】
C++中 HashMap 的使用
https://blog.csdn.net/charles1e/article/details/52042066
?
2.?Add Two Numbers （2018/10/17）
【題目】https://leetcode.com/problems/add-two-numbers/description/
【思路】考察數(shù)據(jù)結(jié)構(gòu)——鏈表，主要是鏈表的操作
?
?
3.?Longest Substring Without Repeating Characters （2018/10/22）
【題目】https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
給定一個(gè)字符串，找到一個(gè)最長(zhǎng)的連續(xù)子串，使其滿足每一個(gè)字符都不重復(fù)
【思路】
（1）維護(hù)一個(gè)HashMap 記錄出現(xiàn)過(guò)的字符? key:字符 value:字符在數(shù)組的下標(biāo)
（2）初始 i = j = 0
j 向后移動(dòng) 并把字符加到HashMap中
如果遇到重復(fù)的字符，由 HashMap 更新 i , 使 i 向后跳躍?
比如 123abcda 讀到 j? == 7 時(shí)， 發(fā)現(xiàn) s[7] = s[3] , i 更新為 4
?
?
4.?Median of Two Sorted Arrays （2018/10/22）
【題目】https://leetcode.com/problems/median-of-two-sorted-arrays/description/
給兩個(gè)有序的數(shù)組，求兩個(gè)數(shù)組合并后的中位數(shù)，給出log(m+n)的算法
【思路】
（1）自己leetcode寫了一個(gè)O(M+N)復(fù)雜度的算法，提交竟然AC了
（2）看到log(m+n)，想到二分法，關(guān)鍵時(shí)要如何進(jìn)行二分
官方題解講得挺詳細(xì)的?https://leetcode.com/problems/median-of-two-sorted-arrays/solution/
?
5.?Longest Palindromic Substring （2018/10/24）
【題目】https://leetcode.com/problems/longest-palindromic-substring/description/
大意：找一個(gè)最長(zhǎng)子串，該子串回文
【思路】
（1）找一個(gè)中心，向兩邊擴(kuò)展找最長(zhǎng)回文子串
遍歷每個(gè)中心，假設(shè)字符串長(zhǎng)度為n，一共有 2n -1 個(gè)中心
時(shí)間復(fù)雜度 O(n*n)
（2）dp
狀態(tài)轉(zhuǎn)移方程? dp[i][j] 表示 子串s[i] ~ s[j] 是否為回文
6.?ZigZag Conversion （2018/10/25）
【題目】https://leetcode.com/problems/zigzag-conversion/description/
【思路】畫出圖形，找一下規(guī)律即可
?
7.?Reverse Integer （2018/10/25）
【題目】將一個(gè)int數(shù)反向輸出，如果反向后超出int范圍，輸出0
【思路】水題
?
8.?String to Integer (atoi) （2018/10/25）
【題目】將字符串轉(zhuǎn)化為整數(shù)
【思路】水題
?
9.?Palindrome Number（2018/10/25）
【題目】判斷回文數(shù)
【思路】水題
?
10.?Regular Expression Matching
【題目】
【思路】
?
?
11.?Container With Most Water （2018/10/31）
【題目】https://leetcode.com/problems/container-with-most-water/description/
可以抽象為如下數(shù)學(xué)表達(dá)：
* 給定一個(gè)數(shù)組a[N] , 求max{ s }, s=min(s[i],s[j])*(j-i) 且j > i
【思路】
（1）用暴力搜索 AC了，發(fā)現(xiàn)leetcode不怎么卡時(shí)間
（2）使用雙指針，分別在開頭結(jié)尾向中間移動(dòng)
?
?
12.?Integer to Roman（2018/10/31）
【題目】將一個(gè)整數(shù)轉(zhuǎn)化為羅馬符號(hào)
【思路】先轉(zhuǎn)化個(gè)位的數(shù)字，再轉(zhuǎn)化十位的數(shù)字....
* 注意輸出的順序
?
17. Letter Combinations of a Phone Number（2018/11/3）
【題目】輸出所有序列
【思路】用樹分析題目，很容易想到用dfs
?
?
19. Remove Nth Node From End of List（2018/11/3）
【題目】給一個(gè)單向鏈表，去除倒數(shù)第n個(gè)元素
【思路】雙指針：
?兩個(gè)指針間隔n個(gè)單位，
然后一起向后移動(dòng)，
當(dāng)?shù)诙€(gè)指針移動(dòng)到末尾，第一個(gè)指針就移動(dòng)到了倒數(shù)第n個(gè)元素的位置
?
22. Generate Parentheses (2018/11/4)
【題目】枚舉出規(guī)定長(zhǎng)度的括號(hào)序列
【思路】遞歸 O(2^(2n))
剪枝優(yōu)化，遞歸過(guò)程中一旦檢測(cè)到序列不合法，即終止添加括號(hào)
?
?
23. Merge k Sorted Lists （2018/11/7）
【題目】給出k個(gè)已經(jīng)排好序的鏈表，合成一個(gè)排好序的鏈表
【思路】用最小堆維護(hù)每一個(gè)鏈表的第一個(gè)節(jié)點(diǎn)，
? 每次移除最小堆的最小值，用相應(yīng)的鏈表的下一個(gè)值代替，對(duì)最小堆進(jìn)行更新,更新時(shí)間復(fù)雜度為O(logk),
? 也就是找所有鏈表第一個(gè)節(jié)點(diǎn)的最小值
?【思路2】 題解中用了歸并這種思想
先是 k 組 合并成 k/2 組?
K/2 組 合并成 k/4 組
。。。
直到合并為一組，算法結(jié)束
?
?
【題目】
【思路】?
?
?
轉(zhuǎn)載于:https://www.cnblogs.com/chsobin/p/9689721.html
總結(jié)
以上是生活随笔為你收集整理的【leetcode】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 素数 乘法表 闰年
- 下一篇： P2184 【贪婪大陆】