最近在準(zhǔn)備面試，發(fā)現(xiàn)自己真的菜的不行瑞你，就計(jì)劃接下來(lái)的時(shí)間把 leetcode 上面刷的 中等題 和 每日一題做個(gè)簡(jiǎn)書筆記。稍微記錄一下，等保研時(shí)或許還有用昂勉。
- 旋轉(zhuǎn)圖像
題目：給定一個(gè) n × n 的二維矩陣表示一個(gè)圖像。將圖像順時(shí)針旋轉(zhuǎn) 90 度扫腺。
說(shuō)明：給定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋轉(zhuǎn)輸入矩陣岗照，使其變?yōu)?
[
[7,4,1],
[8,5,2],
[9,6,3]
]
思路：可以先沿著反對(duì)角線轉(zhuǎn)一次，再?gòu)闹虚g轉(zhuǎn)一次。
class Solution {
//解題思路：先沿著對(duì)角線轉(zhuǎn)一次攒至，再沿著水平線轉(zhuǎn)一次
public void rotate(int[][] matrix) {
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j <matrix.length - i ; j++){
swap(matrix,i,j,matrix.length-1-j,matrix.length-1-i);
}
}
for(int i = 0; i < matrix.length/2; i++){
for(int j = 0; j <matrix.length; j++){
swap(matrix,i,j,matrix.length-1-i,j);
}
}
}
//swap element i and j
public void swap(int matrix[][],int ix,int iy,int jx,int jy){
int temp = matrix[ix][iy];
matrix[ix][iy] = matrix[jx][jy];
matrix[jx][jy] = temp;
}
}
- 有效的數(shù)獨(dú)：
判斷一個(gè) 9x9 的數(shù)獨(dú)是否有效煞肾。只需要根據(jù)以下規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可嗓袱。
數(shù)字 1-9 在每一行只能出現(xiàn)一次籍救。
數(shù)字 1-9 在每一列只能出現(xiàn)一次。
數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次渠抹。
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
輸出：true
思路：
- 可以遍歷三次 9*9 數(shù)組蝙昙，分別判斷是否符合三個(gè)要求
- 可以只遍歷一次，訪問(wèn)每一個(gè)元素時(shí)判斷三個(gè)要求是否被違背：可以用二進(jìn)制位來(lái)表示一列 / 一行 / 一個(gè) 3*3的 Grid 中的狀態(tài)梧却，使用位操作更新奇颠。
class Solution {
private final int VERTICAL = 0;
private final int HORIZONTAL = 1;
private final int GRID = 2;
public boolean isValidSudoku(char[][] board) {
int status[] = new int[27];//一列、一格放航、一行有九個(gè)狀態(tài)烈拒，九個(gè)bit就夠,總共27個(gè)。
for(int i = 0 ; i < 9; i ++){
for(int j = 0; j < 9; j ++){
if(board[i][j] !='.'){
int n = board[i][j] - '0';
if(!checkAndSet(status, VERTICAL ,i, n)){
return false;
}
if(!checkAndSet(status, HORIZONTAL, j,n)){
return false;
}
if(!checkAndSet(status, GRID, (i/3) * 3 + (j/3), n)){
return false;
}
}
}
}
return true;
}
/*
* @param type : VERTICAL(從上到下), HORIZONTAL(從左到右)广鳍，GRID(3*3)
* @param index : 這一類中的第 index 行/列/格子荆几。
* @param num : 數(shù)字 1-9
*/
public boolean checkAndSet(int status[], int type, int index, int num){
int i = type * 9 + index;
if((status[i] & (1 << (num-1))) == 0 ){
status[i] = (status[i]^(1<<(num-1)));
return true;
}
return false;
}
}
這里使用了short，內(nèi)存使用率為 9/16赊时，可以換成int吨铸，會(huì)把內(nèi)存使用率提高到 27/32。
- 跳躍游戲
給定一個(gè)非負(fù)整數(shù)數(shù)組祖秒，你最初位于數(shù)組的第一個(gè)位置诞吱。
數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度。
判斷你是否能夠到達(dá)最后一個(gè)位置竭缝。
輸入: [2,3,1,1,4]
輸出: true
解釋: 我們可以先跳 1 步房维，從位置 0 到達(dá) 位置 1, 然后再?gòu)奈恢?1 跳 3 步到達(dá)最后一個(gè)位置。
思想：將數(shù)組中分成“好位置”和“壞位置”抬纸，可以從好位置跳到最后而壞位置不可以咙俩；動(dòng)態(tài)規(guī)劃，從后向前(反過(guò)來(lái)也行)一格一格的試探好位置松却，并記錄目前最靠前的好位置
public boolean canJump(int[] nums) {
int last = nums.length-1;//數(shù)組的最后一個(gè)位置一定是“好位置”
for(int j = last-1; j >-1; --j){
if(last - j <= nums[j]){
last = j;
}
}
if(last == 0){
return true;
}
return false;
}
}
- 第k個(gè)排列
按大小順序列出所有排列情況暴浦，并一一標(biāo)記，當(dāng) n = 3 時(shí), 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
給定 n 和 k晓锻，返回第 k 個(gè)排列歌焦。
輸入: n = 3, k = 3
輸出: "213"
class Solution {
public String getPermutation(int n, int k) {
List<Integer> l = new ArrayList<>();
l.add(1);
int fac[] = new int[n];
fac[0] = 1;
for(int i = 1; i < n; i++){
fac[i] = fac[i-1] * i; //初始化到一個(gè)數(shù)組中，運(yùn)用動(dòng)態(tài)規(guī)劃砚哆。
l.add(i+1);
}
StringBuilder builder = new StringBuilder("");
k--;
//觀察序列独撇，n = 3 的全排列，第一個(gè)數(shù)index是 (位置-1)/2 ,第二個(gè)數(shù)是(位置-1)/1,第三個(gè)數(shù)是(位置-1)/1，除數(shù)除了最后一項(xiàng)是1纷铣，符合n!,只需要維護(hù)一個(gè)數(shù)組卵史，按照計(jì)算得到的idx從數(shù)組中取出并刪除。
for(int i = n-1; i >= 0; --i){
int idx = k / fac[i];
k -= idx * fac[i];
builder.append((char)(l.get(idx)+'0'));//要先強(qiáng)制轉(zhuǎn)型搜立，否則append會(huì)把后面的樹(shù)作為int處理以躯，得到4950這樣的
l.remove(idx);
}
return builder.toString();
}
}
- 多數(shù)元素
給定一個(gè)大小為 n 的數(shù)組，找到其中的多數(shù)元素啄踊。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素忧设。
輸入: [3,2,3]
輸出: 3
我使用的解法是哈希映射的方法，太naive颠通，不貼代碼了址晕，記錄下官方十分強(qiáng)大的投票算法。
//如果我們把眾數(shù)記為 +1+1顿锰，把其他數(shù)記為 -1?1谨垃，將它們?nèi)考悠饋?lái)
//，顯然和大于 0硼控，從結(jié)果本身我們可以看出眾數(shù)比其他數(shù)多刘陶。
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
//作者：LeetCode-Solution
//鏈接：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
//來(lái)源：力扣（LeetCode）
//著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)淀歇，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處易核。
這里的candidate可能不是眾數(shù)匈织，但是沒(méi)有關(guān)系浪默，由于眾數(shù)占多數(shù)，在數(shù)組中總是可能出現(xiàn)count=0的時(shí)候缀匕，這時(shí)會(huì)重新選擇候選人纳决，其他人投出去的選票，總是會(huì)被眾數(shù)投出去的抵消掉乡小。
- 旋轉(zhuǎn)鏈表：
給定一個(gè)鏈表阔加，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng) k 個(gè)位置满钟，其中 k 是非負(fù)數(shù)胜榔。
輸入: 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 5->1->2->3->4->NULL
向右旋轉(zhuǎn) 2 步: 4->5->1->2->3->NULL
暴力的解法可以遍歷列表k遍，每次將最后一個(gè)節(jié)點(diǎn)置于第一個(gè)湃番，時(shí)間復(fù)雜度(k*n)夭织。
更好的方法是：將首尾相連，將head相連吠撮，將head和last都向后挪動(dòng) n - k%n 位尊惰。
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head==null ){
return null;
}
ListNode l = head;
int n = 1;
while(l.next!=null){
l = l.next;
n++;
}
l.next = head;
for(int i = 0; i < n - k%n; i++){ //注意這里要%n，否則k>n時(shí)出問(wèn)題。
head = head.next;
l = l.next;
}
l.next = null;
return head;
}
}
- 不同路徑
- 一道很典型的動(dòng)態(tài)規(guī)劃題弄屡，方程很好找题禀。
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步膀捷。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）迈嘹。
現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會(huì)有多少條不同的路徑全庸？
網(wǎng)格中的障礙物和空位置分別用 1 和 0 來(lái)表示江锨。
輸入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
輸出: 2
無(wú)障礙物版本：
class Solution {
// len(x,y) = len(x+1,y) + len (x,y+1);
// len (m, n-1) = 1;
public int uniquePaths(int m, int n) {
int res[][] = new int[m][n];
res[m-1][n-1] = 1;
for(int i = m -1 ; i >=0; --i){
for(int j = n-1; j >=0; --j){
if(j < n - 1){
res[i][j] += res[i][j+1];
}
if(i < m - 1){
res[i][j] += res[i+1][j];
}
}
}
return res[0][0];
}
}
障礙物版本
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int res[][] = new int[m][n];
if(obstacleGrid[m-1][n-1] == 0){
res[m-1][n-1] = 1;
}
for(int i = m - 1 ; i >=0; --i){
for(int j = n - 1; j >=0; --j){
if(obstacleGrid[i][j] == 0){
if(j < n - 1){
res[i][j] += res[i][j+1];
}
if(i < m - 1){
res[i][j] += res[i+1][j];
}
}
}
}
return res[0][0];
}
}
- 最短路徑
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int res[][] = new int[m][n];
res[m-1][n-1] = grid[m-1][n-1];
for(int i = m - 1 ; i >=0; --i){
for(int j = n - 1; j >=0; --j){
if(i == m-1 && j < n-1){
res[i][j] = res[i][j+1] +grid[i][j];
}
if(j == n-1 && i < m-1){
res[i][j] = res[i+1][j] + grid[i][j];
}
if(j < n - 1 && i < m-1){
res[i][j] = Math.min(res[i][j+1] ,res[i+1][j]) +grid[i][j];
}
}
}
return res[0][0];
}
}
- 簡(jiǎn)化路徑
以 Unix 風(fēng)格給出一個(gè)文件的絕對(duì)路徑，你需要簡(jiǎn)化它糕篇∽挠或者換句話說(shuō)，將其轉(zhuǎn)換為規(guī)范路徑拌消。
示例 1：
輸入："/home/"
輸出："/home"
解釋：注意挑豌，最后一個(gè)目錄名后面沒(méi)有斜杠。
示例 2：
輸入："/../"
輸出："/"
解釋：從根目錄向上一級(jí)是不可行的墩崩，因?yàn)楦悄憧梢缘竭_(dá)的最高級(jí)氓英。
示例 3：
輸入："/home//foo/"
輸出："/home/foo"
解釋：在規(guī)范路徑中，多個(gè)連續(xù)斜杠需要用一個(gè)斜杠替換鹦筹。
示例 4：輸入："/a/./b/../../c/"
輸出："/c"
示例 5：
輸入："/a/../../b/../c//.//"
輸出："/c"
示例 6：
輸入："/a//b////c/d//././/.."
輸出："/a/b/c"
思路：使用LinkedList 模擬棧來(lái)簡(jiǎn)化路徑
class Solution {
LinkedList<String> list = new LinkedList<>();
public String simplifyPath(String path) {
String[] strs=path.split("/");
for(String str: strs){
if(str.equals("")||str.equals(".")){
continue;
}
if(str.equals("..")){
if(list.size()>0){
list.removeLast();
}
} else {
list.addLast(str);
}
}
StringBuilder sb= new StringBuilder("");
if(list.size() == 0){
return "/";
}
for(String str:list){
sb.append("/");
sb.append(str);
}
return sb.toString();
}
}
- 拼寫單詞
- 給你一份『詞匯表』（字符串?dāng)?shù)組） words 和一張『字母表』（字符串） chars铝阐。
假如你可以用 chars 中的『字母』（字符）拼寫出 words 中的某個(gè)『?jiǎn)卧~』（字符串），那么我們就認(rèn)為你掌握了這個(gè)單詞铐拐。
注意：每次拼寫時(shí)徘键，chars 中的每個(gè)字母都只能用一次。
提示：
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
所有字符串中都僅包含小寫英文字母
思路：限制了只會(huì)出現(xiàn)小寫字母(連續(xù))遍蟋，那么我們可以去統(tǒng)計(jì)單詞中每個(gè)字母出現(xiàn)的次數(shù)存在數(shù)組中吹害，如果A單詞中的每個(gè)字母的出現(xiàn)次數(shù)都小于等于B單詞中的出現(xiàn)次數(shù)，可以認(rèn)為是“掌握了”
class Solution {
public int countCharacters(String[] words, String chars) {
int chs[] = new int[26];
for(char ch :chars.toCharArray()){
chs[ch-'a']++;
}
int res = 0;
for(String str:words){
int s[] = new int[26];
for(char ch : str.toCharArray()){
s[ch-'a']++;
}
boolean f = false;
for(int i = 0; i < 26; ++i){
if(s[i] > chs[i]){
f = true;
break;
}
}
if(!f){
res+=str.length();
}
}
return res;
}
}
- 搜索二維矩陣
編寫一個(gè)高效的算法來(lái)判斷 m x n 矩陣中虚青，是否存在一個(gè)目標(biāo)值它呀。該矩陣具有如下特性：
每行中的整數(shù)從左到右按升序排列。
每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)棒厘。
輸入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
輸出: true
這個(gè)腦子就是得轉(zhuǎn)一下纵穿，我死命想用兩次二分法在兩個(gè)維度上分別搜索，但是死活不行奢人，看完力扣官方題解之后茅塞頓開(kāi)谓媒。什么有序二維數(shù)組，從內(nèi)存的角度上來(lái)看就是個(gè)有序的一維數(shù)組嘛达传！
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length==0){
return false;
}
int m = matrix.length;
int n = matrix[0].length;
int low = 0;
int high = m * n -1;
int mid = (low+high)/2;
while(low <= high){
int val = matrix[mid/n][mid%n];
if(val < target){
low = mid + 1;
} else if(val == target){
return true;
} else {
high = mid - 1;
}
mid = (low+high)/2;
}
return false;
}
}
- 顏色分類
給定一個(gè)包含紅色篙耗、白色和藍(lán)色迫筑，一共 n 個(gè)元素的數(shù)組，原地**對(duì)它們進(jìn)行排序宗弯，使得相同顏色的元素相鄰脯燃，并按照紅色、白色蒙保、藍(lán)色順序排列辕棚。
此題中，我們使用整數(shù) 0邓厕、 1 和 2 分別表示紅色逝嚎、白色和藍(lán)色。
注意:
不能使用代碼庫(kù)中的排序函數(shù)來(lái)解決這道題详恼。
進(jìn)階：
- 一個(gè)直觀的解決方案是使用計(jì)數(shù)排序的兩趟掃描算法补君。
首先，迭代計(jì)算出0昧互、1 和 2 元素的個(gè)數(shù)挽铁，然后按照0、1敞掘、2的排序叽掘，重寫當(dāng)前數(shù)組。 - 你能想出一個(gè)僅使用常數(shù)空間的一趟掃描算法嗎玖雁？
輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]
思路更扁，桶排序。
class Solution {
public void sortColors(int[] nums) {
int colors[] = new int[3];
for(int i =0; i< nums.length;++i){
colors[nums[i]]++;
}
int j = 0;
for(int i = 0; i < nums.length;++i){
while( j < 3 && colors[j] == 0){
j++;
}
if(j==3){
break;
}
nums[i] = j;
colors[j]--;
}
}
}
- 無(wú)重復(fù)最長(zhǎng)子串
- 給定一個(gè)字符串赫冬，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度浓镜。
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3面殖。
解題思路：使用動(dòng)態(tài)規(guī)劃竖哩，存放每一個(gè)字母最近出現(xiàn)的下標(biāo)的下一位。使用一次掃描而結(jié)果就是在迭代過(guò)程中的 max(oldVal, 右指針-max(左指針,index[右指針?biāo)谧帜竇+1,)
class Solution {
public int lengthOfLongestSubstring(String s) {
int index[] = new int[256];//存放字母出現(xiàn)的下標(biāo)的下一位脊僚，會(huì)隨著掃描更新為最右的坐標(biāo)，0表示還沒(méi)出現(xiàn)過(guò)
int res = 0;
int i = 0;//左指針
for(int j = 0; j < s.length(); ++j){
i = Math.max(index[s.charAt(j)],i);//如果當(dāng)前字母在i之后出現(xiàn)過(guò)遵绰，那么左指針就要更新到之前出現(xiàn)過(guò)位置的下一位辽幌，若沒(méi)有出現(xiàn)，i不變椿访。
res = Math.max(res, j-i+1);// 更新一下res
index[s.charAt(j)] = j+1;// 更新index
}
return res;
}
}
- 刪除排序數(shù)組中的重復(fù)項(xiàng)
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length==0){
return 0;
}
int oldVal = nums[0];
int res = 1;
int j = 1;
for(int i = 1; i < nums.length; ++i){
if(oldVal!=nums[i]){
j = 1;
nums[res++] = nums[i];
oldVal = nums[i];
} else if(j < 2&&nums[i]==oldVal){
nums[res++] = nums[i];
j++;
}
}
return res;
}
}
- 最大子序和
考慮到有負(fù)數(shù)有正數(shù)乌企，
- 極端情況，全是負(fù)數(shù)成玫，那么就相當(dāng)于找最小元素
- 如果只有一個(gè)正數(shù)加酵，那么正數(shù)所在的大小為1的序列就是最大子序
可以考慮使用動(dòng)態(tài)規(guī)劃：- 記錄一個(gè)大小為n的數(shù)組拳喻，記錄包含當(dāng)前元素為子序列最后一個(gè)元素時(shí)的最大子序和。
- 如果之前的子序和大于0猪腕，那么當(dāng)前的最大子序列和等于之前最大子序列和加上當(dāng)前元素冗澈，否則就是當(dāng)前元素。在迭代的過(guò)程中記錄最大的子序列和陋葡。
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length, maxSum = nums[0];
for(int i = 1; i < n; ++i) {
if (nums[i - 1] > 0) nums[i] += nums[i - 1];//原地修改
maxSum = Math.max(nums[i], maxSum);//記錄最大子序列和
}
return maxSum;
}
}
給定一棵二叉樹(shù)亚亲，想象自己站在它的右側(cè)，按照從頂部到底部的順序腐缤，返回從右側(cè)所能看到的節(jié)點(diǎn)值捌归。
輸入: [1,2,3,null,5,null,4]
輸出: [1, 3, 4]
解釋:
1 <---
/
2 3 <---
\
5 4 <---
思路：使用隊(duì)列輔助廣度優(yōu)先遍歷，記錄樹(shù)的深度岭粤。有一個(gè)無(wú)意間發(fā)現(xiàn)的小技巧惜索，我在開(kāi)始寫的時(shí)候按照正常思路從左向右遍歷子樹(shù)仅炊，發(fā)現(xiàn)得到的是 二叉樹(shù)的左視圖雷恃，變換遍歷順序之后疙剑，得到了二叉樹(shù)的右視圖宰闰。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
class Pair{
int depth;
TreeNode n;
Pair(TreeNode n, int depth){
this.n = n;
this.depth = depth;
}
}
public List<Integer> rightSideView(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
LinkedList<Pair> q = new LinkedList<>();
q.addLast(new Pair(root,0));
List<Integer> l = new ArrayList<>();
int prevDepth = -1;
while(!q.isEmpty()){
Pair p = q.removeFirst();
if(p.depth!=prevDepth){
l.add(p.n.val);
}
if(p.n.right!=null){//先右子
q.addLast(new Pair(p.n.right,p.depth+1));
}
if(p.n.left!=null){//再左子
q.addLast(new Pair(p.n.left,p.depth+1));
}
prevDepth = p.depth;
}
return l;
}
}
給定一個(gè)二維矩陣潭陪，計(jì)算其子矩形范圍內(nèi)元素的總和颠放，該子矩陣的左上角為 (row1, col1) 伪朽，右下角為 (row2, col2)帮毁。
圖中子矩陣左上角 (row1, col1) = (2, 1) 溜宽，右下角(row2, col2) = (4, 3)吉拳，該子矩形內(nèi)元素的總和為 8。
給定 matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
說(shuō)明:
你可以假設(shè)矩陣不可變适揉。
會(huì)多次調(diào)用 sumRegion 方法留攒。
你可以假設(shè) row1 ≤ row2 且 col1 ≤ col2。
- 思路：由于會(huì)調(diào)用多次sumRegion方法嫉嘀，一般的暴力解法會(huì)超時(shí)炼邀。
可以先計(jì)算所有(i,j)的 sumRegion(0,0,i,j) ，記為s(i, j), 則
class NumMatrix {
//注意這里的sumRegion會(huì)調(diào)用多次
int sum[][];
public NumMatrix(int[][] matrix) {
if(matrix.length==0){
return;
} else {
int m = matrix.length;
int n = matrix[0].length;
sum = new int[m+1][n+1];//sum下標(biāo)從1開(kāi)始剪侮，小 trick拭宁，
for(int i = 0; i < m; ++i){
for(int j= 0; j < n; ++j){
sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] + matrix[i][j] - sum[i][j];
}
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return sum[row1][col1] + sum[row2+1][col2+1] - sum[row1][col2+1] - sum[row2+1][col1];
}
}
- 01矩陣
給定一個(gè)由 0 和 1 組成的矩陣，找出每個(gè)元素到最近的 0 的距離瓣俯。給定的矩陣元素不超過(guò)10000個(gè)
兩個(gè)相鄰元素間的距離為 1 杰标。
示例 1:
輸入:
0 0 0
0 1 0
0 0 0
輸出:
0 0 0
0 1 0
0 0 0
示例 2:
輸入:
0 0 0
0 1 0
1 1 1
輸出:
0 0 0
0 1 0
1 2 1
思路：兩遍dp，一次從左上往右下彩匕，一次從右下往左上腔剂。
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int row = matrix.size();
if(row == 0){
return matrix;
}
int col = matrix[0].size();
vector<vector<int>> distance(row,vector(col,INT_MAX - 10000));//-10000是因?yàn)? for(int i = 0; i < row; ++i){
for(int j = 0; j < col; ++j){
if(matrix[i][j]==0){//第一次掃描的時(shí)候看看標(biāo)記出來(lái)0
distance[i][j] = 0;
} else {
if(i>0){//注意邊界條件
distance[i][j] = min(distance[i-1][j]+1,distance[i][j]);
}
if(j>0){
distance[i][j] = min(distance[i][j-1]+1,distance[i][j]);
}
}
}
}
for(int i = row-1; i >=0; --i){
for(int j = col-1; j >=0; --j){
if(i<row-1){
distance[i][j] = min(distance[i+1][j]+1,distance[i][j]);
}
if(j<col-1){
distance[i][j] = min(distance[i][j+1]+1,distance[i][j]);
}
}
}
return distance;
}
};
感覺(jué)如果不知道起點(diǎn)在哪的時(shí)候：(0,0) 不一定是0，需要我們?nèi)ニ阉饕幌峦找牵梢杂眠@種方式解決掸犬。這里使用了兩次dp袜漩，正好cover了所有情況(向左，向右湾碎，向上宙攻，向下)
- 機(jī)器人的運(yùn)動(dòng)范圍
地上有一個(gè)m行n列的方格，從坐標(biāo) [0,0] 到坐標(biāo) [m-1,n-1] 胜茧。一個(gè)機(jī)器人從坐標(biāo) [0, 0] 的格子開(kāi)始移動(dòng)粘优，它每次可以向左、右呻顽、上雹顺、下移動(dòng)一格（不能移動(dòng)到方格外），也不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子廊遍。例如嬉愧，當(dāng)k為18時(shí)，機(jī)器人能夠進(jìn)入方格 [35, 37] 喉前，因?yàn)?+5+3+7=18没酣。但它不能進(jìn)入方格 [35, 38]，因?yàn)?+5+3+8=19卵迂。請(qǐng)問(wèn)該機(jī)器人能夠到達(dá)多少個(gè)格子？
思路：
把和的格子看成障礙物见咒，直接以（0,0）作為起點(diǎn)偿衰，使用bfs搜索。
class Solution {
// 計(jì)算 x 的數(shù)位之和
int get(int x) {
int res=0;
for (; x; x /= 10) {
res += x % 10;
}
return res;
}
public:
int movingCount(int m, int n, int k) {
if (!k) return 1;
queue<pair<int,int> > Q;
// 向右和向下的方向數(shù)組
int dx[2] = {0, 1};
int dy[2] = {1, 0};
vector<vector<int> > vis(m, vector<int>(n, 0));
Q.push(make_pair(0, 0));
vis[0][0] = 1;
int ans = 1;
//需要證明改览，如果sum(m)+sum(n)<k,則一定有一條路徑
while (!Q.empty()) {
auto [x, y] = Q.front();
Q.pop();
for (int i = 0; i < 2; ++i) {
int tx = dx[i] + x;
int ty = dy[i] + y;
if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) continue;
Q.push(make_pair(tx, ty));
vis[tx][ty] = 1;
ans++;
}
}
return ans;
}
};
- 括號(hào)生成
數(shù)字 n 代表生成括號(hào)的對(duì)數(shù)下翎，請(qǐng)你設(shè)計(jì)一個(gè)函數(shù)，用于能夠生成所有可能的并且 有效的 括號(hào)組合宝当。
示例：
輸入：n = 3
輸出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
使用回溯法：
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
generate(n*2,n,res,"",0);
return res;
}
void generate(int n,int l/*左括號(hào)剩余個(gè)數(shù)*/, vector<string>& v,string str,int m/*字符串中左括號(hào)比右括號(hào)多的個(gè)數(shù)*/){
if(n<1){
v.push_back(str);
return;
}
if(l > 0){
// str = str + '('; 別這么寫视事，會(huì)影響下面的case！Ｇ炜俐东！
generate(n-1,l-1,v,str+'(',m+1);
}
if(m > 0){
// str = str + ')';
generate(n-1,l,v,str+')',m-1);
}
}
};
- 二叉樹(shù)插入
給定一個(gè)二叉樹(shù)，根節(jié)點(diǎn)為第1層盾鳞，深度為 1犬性。在其第 d 層追加一行值為 v 的節(jié)點(diǎn)。
添加規(guī)則：給定一個(gè)深度值 d （正整數(shù)）腾仅，針對(duì)深度為 d-1 層的每一非空節(jié)點(diǎn) N，為 N 創(chuàng)建兩個(gè)值為 v 的左子樹(shù)和右子樹(shù)套利。
將 N 原先的左子樹(shù)推励，連接為新節(jié)點(diǎn) v 的左子樹(shù)鹤耍；將 N 原先的右子樹(shù)，連接為新節(jié)點(diǎn) v 的右子樹(shù)验辞。
如果 d 的值為 1稿黄，深度 d - 1 不存在，則創(chuàng)建一個(gè)新的根節(jié)點(diǎn) v跌造，原先的整棵樹(shù)將作為 v 的左子樹(shù)杆怕。
輸入:
二叉樹(shù)如下所示:
4
/ \
2 6
/ \ /
3 1 5
且 v = 1 d = 2輸出:
4
/ \
1 1
/ \
2 6
/ \ /
3 1 5
思路： 使用bfs獲得第d-1層的所有節(jié)點(diǎn)，然后按照題目要求添加壳贪。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int v, int d) {
if(root==nullptr){
return root;
}
if(d==1){
TreeNode* newRoot = new TreeNode(v);
newRoot->left = root;
return newRoot;
}
pair<TreeNode*,int> rootpair = make_pair(root,1);
queue<pair<TreeNode*,int>> q;//記錄深度
q.push(rootpair);
while(!q.empty()){
auto [node, curDepth] = q.front();
if(curDepth==d-1){
break;
}
q.pop();
if(node->left!=nullptr){
q.push(make_pair(node->left,curDepth+1));
}
if(node->right!=nullptr){
q.push(make_pair(node->right,curDepth+1));
}
}
while(!q.empty()){
auto [node, curDepth] = q.front();
q.pop();
TreeNode* leftTemp = node->left;
TreeNode* rightTemp = node->right;
node -> left = new TreeNode(v);
node -> right = new TreeNode(v);
node -> left -> left = leftTemp;
node -> right -> right = rightTemp;
}
return root;
}
};
- 相同的樹(shù)
給定兩個(gè)二叉樹(shù)陵珍，編寫一個(gè)函數(shù)來(lái)檢驗(yàn)它們是否相同。
如果兩個(gè)樹(shù)在結(jié)構(gòu)上相同违施，并且節(jié)點(diǎn)具有相同的值互纯，則認(rèn)為它們是相同的。
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p&&!q){
return true;
}
if((p&&!q)||(!p&&q)||p->val!=q->val){
return false;
}
queue<TreeNode*> pQ;
queue<TreeNode*> qQ;
pQ.push(p);
qQ.push(q);
while(!pQ.empty()){
TreeNode* ptmp = pQ.front();
TreeNode* qtmp = qQ.front();
pQ.pop();
qQ.pop();
if(qtmp->left||ptmp->left){
if(!qtmp->left || !ptmp->left || ptmp->left->val != qtmp->left->val){
return false;
}
pQ.push(ptmp->left);
qQ.push(qtmp->left);
}
if(qtmp->right||ptmp->right){
if(!qtmp->right || !ptmp->right || ptmp->right->val != qtmp->right->val){
return false;
}
pQ.push(ptmp->right);
qQ.push(qtmp->right);
}
}
return true;
}
};
衍生：對(duì)稱二叉樹(shù)：
給定一個(gè)二叉樹(shù)磕蒲，檢查它是否是鏡像對(duì)稱的留潦。
思路：一個(gè)樹(shù)如果是對(duì)稱的，那它左子和右子的值一定相等辣往，左子的左子和右子的右子一定對(duì)稱兔院。
bool isSymmetric(TreeNode* root){
if(!root){
return true;
}
return isMirror(root->left,root->right);
// if(!root||(!root->left&&!root->right)){ return true;}
//wrong!
// if(root->left&&root->right){
// return isSymmetric(root->left)&&isSymmetric(root->right)&& root->left->val==root->right->val;
// } else {
// return false;
// }
}
bool isMirror(TreeNode* node1,TreeNode* node2){
if(!node1&&!node2){
return true;
}
if(!node1||!node2){
return false;
}
return (node1->val == node2 ->val)
&& isMirror(node1->left,node2->right)
&& isMirror(node1->right,node2->left);
}
- 二叉樹(shù)展開(kāi)為鏈表
給定一個(gè)二叉樹(shù)，原地將它展開(kāi)為鏈表站削。
TIM截圖20200415101029.png
方案一坊萝，自頂向下搜索，將左子樹(shù)掛在右子上钻哩，原有的右子樹(shù)掛在現(xiàn)在最右節(jié)點(diǎn)的右邊屹堰。
public:
void flatten(TreeNode* root){
while(root){
if(!root->left){
root = root->right;
} else {
TreeNode* r = root -> right;
root -> right = root -> left;
root -> left = nullptr;
TreeNode* tmp = root;
while(tmp->right){
tmp = tmp -> right;
}
tmp -> right = r;
root = root->right;
}
}
}
方案二，不難看出鏈表化后的二叉樹(shù)是其前序遍歷的版本街氢，我們可以反其道而行之扯键，使用后序遍歷，頭插到鏈表上珊肃。
TreeNode* pre;//當(dāng)前鏈表
void flatten(TreeNode* root){//后序遍歷
if(!root){
return;
}
flatten(root->right);
flatten(root->left);
//頭插入鏈表
root->right = pre;
pre = root;
//記得把left置null
root->left = nullptr;
}
- 合并區(qū)間
給出一個(gè)區(qū)間的集合荣刑，請(qǐng)合并所有重疊的區(qū)間。
示例 1:
輸入: [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
示例 2:
輸入: [[1,4],[4,5]]
輸出: [[1,5]]
解釋: 區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間伦乔。
思路：先對(duì)于intervals 按照左區(qū)間大小排序厉亏，從前向后遍歷，步長(zhǎng)為1烈和，如果可以合并（R1 > L2）爱只，就合并
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()==0){
return {};
}
sort(intervals.begin(),intervals.end());
vector<vector<int>> res;
for(int i = 0; i< intervals.size(); ++i){
int L = intervals[i][0],R = intervals[i][1];
if(res.empty()|| L >res.back()[1] ){
res.push_back({L,R});
} else {
res.back()[1] = max(res.back()[1],R);
}
}
return res;
}
};
- 反轉(zhuǎn)鏈表 II
反轉(zhuǎn)從位置 m 到 n 的鏈表。請(qǐng)使用一趟掃描完成反轉(zhuǎn)招刹。
說(shuō)明:
1 ≤ m ≤ n ≤ 鏈表長(zhǎng)度恬试。
示例:
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
int i = 0;
ListNode* h = new ListNode(0);
h->next = head;
ListNode* prev = h;
for(int i = 0; i < m-1; ++i){
prev=prev->next;
}
ListNode* rStart = prev->next;//反轉(zhuǎn)前第m個(gè)節(jié)點(diǎn)窝趣，
ListNode* end = rStart; //反轉(zhuǎn)后的第n個(gè)節(jié)點(diǎn)
ListNode* rBetween = new ListNode(0);//反轉(zhuǎn)的過(guò)程以頭插法，插入這個(gè)列表
for(int i = m-1; i< n; ++i){
ListNode* tmp = rStart->next;
rStart->next = rBetween->next;
rBetween->next = rStart;
rStart = tmp;
}
prev->next = rBetween->next;
end->next = rStart;
return h->next;
}
};
- 反轉(zhuǎn)鏈表
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
class Solution {
public:
//迭代版本
// ListNode* reverseList(ListNode* head) {
// ListNode* h = new ListNode(0);
// h->next = head;
// ListNode* res = new ListNode(0);
// while(h->next!=nullptr){
// h = h -> next;
// ListNode* tmp = res -> next;
// res->next = new ListNode(h->val);
// res->next -> next = tmp;
// }
// return res->next;
// }
//遞歸
ListNode* reverseList(ListNode* head){
if(!head||!head->next){
return head;
}
ListNode* res = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return res;
}
};
例如训柴，給定如下二叉搜索樹(shù): root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
輸出: 6
解釋: 節(jié)點(diǎn) 2 和節(jié)點(diǎn) 8 的最近公共祖先是 6哑舒。
示例 2:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
輸出: 2
解釋: 節(jié)點(diǎn) 2 和節(jié)點(diǎn) 4 的最近公共祖先是 2, 因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。
思路：根據(jù)平衡二叉搜索樹(shù)定義幻馁，兩個(gè)節(jié)點(diǎn)（2, 4）的最近公共祖先的值（2）一定大于等于較小節(jié)點(diǎn)（4）且小于等于較大節(jié)點(diǎn)（4），且最近公共祖先的父節(jié)點(diǎn)的值(6)一定同時(shí)大于兩個(gè)節(jié)點(diǎn)或同時(shí)小于兩個(gè)節(jié)點(diǎn)仗嗦。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root||!p||!q){
return root;
}
TreeNode* res = root;
while(res){
if(res->val >= p->val && res->val >= q->val){//等于是
if(res->val == p->val || res->val ==q->val){//防止 2,4 都大于等于2膘滨，即示例 2
break;
}
res = res->left;
} else if(res->val <= p->val && res->val <= q->val){
if(res->val == p->val || res->val ==q->val){
break;
}
res = res->right;
} else {
break;
}
}
return res;
}
};
給定一個(gè)整數(shù)數(shù)組，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 儒将。?
設(shè)計(jì)一個(gè)算法計(jì)算出最大利潤(rùn)吏祸。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
- 你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）钩蚊。
- 賣出股票后贡翘，你無(wú)法在第二天買入股票 (即冷凍期為 1 天)。
示例:
輸入: [1,2,3,0,2]
輸出: 3
解釋: 對(duì)應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]
思路：動(dòng)態(tài)規(guī)劃
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n==0){
return 0;
}
int dp[n][3];
dp[0][0]=0;//當(dāng)天不持股砰逻，且當(dāng)天沒(méi)賣出
dp[0][1]=-prices[0];//第i天持股
dp[0][2]=0;//當(dāng)天不持股鸣驱，股票是當(dāng)天賣出的，第0天特殊情況蝠咆，認(rèn)為當(dāng)天買入當(dāng)天賣出
for(int i = 1; i< n ;i++){
dp[i][0] = max(dp[i-1][0],dp[i-1][2]); //
dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1]);
dp[i][2] = dp[i-1][1]+prices[i];
}
return max(dp[n-1][0],dp[n-1][2]);//
}
};
```
28. 超級(jí)丑數(shù)
超級(jí)丑數(shù)是指其所有質(zhì)因數(shù)都是長(zhǎng)度為 k 的質(zhì)數(shù)列表 primes 中的正整數(shù)踊东。
> 示例:
輸入: n = 12, primes = [2,7,13,19]
輸出: 32
解釋: 給定長(zhǎng)度為 4 的質(zhì)數(shù)列表 primes = [2,7,13,19]，前 12 個(gè)超級(jí)丑數(shù)序列為：
[1,2,4,7,8,13,14,16,19,26,28,32] 刚操。
使用動(dòng)態(tài)規(guī)劃闸翅，觀察一下規(guī)律：
* 開(kāi)始時(shí)丑數(shù)序列dp為 $[1]$
* $dp[1] = min(dp[0] * prime[0],dp[0] * prime[1],dp[0] * prime[2],dp[0] * prime[3]) = dp[0]* prime[0] =2$
* $dp[2] = min(dp[1] * prime[0],dp[0] * prime[1],dp[0] * prime[2],dp[0] * prime[3]) = dp[1]* prime[0]=4$
* $dp[3] = min(dp[2] * prime[0],dp[0] * prime[1],dp[0] * prime[2],dp[0] * prime[3])= dp[0]* prime[1]=7$
* $dp[4] = min(dp[2] * prime[0],dp[1] * prime[1],dp[0] * prime[2],dp[0] * prime[3]) = dp[2]*prime[0]=8$
* $dp[5] = min(dp[3] * prime[0],dp[1] * prime[1],dp[0] * prime[2],dp[0] * prime[3]) = dp[0]*prime[2]=13$
* **! dp[6]中出現(xiàn)了 2 * 7 和 7 * 2 相等的情況，需要都考慮進(jìn)來(lái)并去重菊霜。** $dp[6] = min(dp[3] * prime[0],dp[1] * prime[1],dp[1] * prime[2],dp[0] * prime[3]) = dp[3]*prime[0]= dp[1] * prime[1] =14$
根據(jù)上述規(guī)律坚冀，維護(hù)下兩個(gè)數(shù)組：
* index數(shù)組：index[j] 是第j個(gè)prime當(dāng)前在dp的下標(biāo)
* dp：超級(jí)丑數(shù)序列。
```c++
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
if(n==0){
return 1;
}
int dp[n];
dp[0]=1;
int k = primes.size();
vector<int> index(k,0);
for(int i = 1; i < n; ++i){
int minVal = INT_MAX;
for(int j = 0; j < k; ++j){
if(dp[index[j]] * primes[j]<minVal){
minVal = dp[index[j]] * primes[j];
}
}
for(int j =0; j < k; ++j){//去重 2*7 和 7*2
if(dp[index[j]]* primes[j] == minVal){
++index[j];
}
}
dp[i]=minVal;
}
return dp[n-1];
}
};
- 硬幣
給定數(shù)量不限的硬幣鉴逞，幣值為25分记某、10分、5分和1分构捡，編寫代碼計(jì)算n分有幾種表示法液南。(結(jié)果可能會(huì)很大，你需要將結(jié)果模上1000000007)
示例1:
輸入: n = 5
輸出：2
解釋: 有兩種方式可以湊成總金額:
5=5
5=1+1+1+1+1
示例2:
輸入: n = 10
輸出：4
解釋: 有四種方式可以湊成總金額:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
思路：動(dòng)態(tài)規(guī)劃
-
一開(kāi)始我想的是這樣的一個(gè)方程勾徽，但是結(jié)果不對(duì)滑凉，原因是因?yàn)?+5和5+1會(huì)被認(rèn)為是6的兩種找零方式。
img_0835.png -
修改后的方程：
TIM截圖20200423182940.png
實(shí)現(xiàn)：
class Solution {
public:
int mod = 1000000007;
int coins[4] = {1,5,10,25};
int waysToChange(int n) {
if(n==0){
return 0;
}
int dp[n+1];
for(int i = 1; i<=n; ++i){
dp[i]=0;
}
dp[0]=1;
for(int i = 0; i <4; ++i){
int coin=coins[i];
for(int j = coin; j <= n; ++j){
dp[j] = (dp[j]+dp[j-coin])%mod;
}
}
return dp[n];
}
};
給定一個(gè)整數(shù) n，求以 1 ... n 為節(jié)點(diǎn)組成的二叉搜索樹(shù)有多少種譬涡？
示例:
輸入: 3
輸出: 5
解釋: 給定 n = 3, 一共有 5 種不同結(jié)構(gòu)的二叉搜索樹(shù):
class Solution {
public:
int numTrees(int n) {
if(n==0){
return 1;
}
int dp[n+1];//dp[i]表示有i個(gè)節(jié)點(diǎn)的組成樹(shù)的個(gè)數(shù)
dp[0] = 1;
for(int i=1; i <= n; ++i){
int tmp = 0;
for(int j=0; j < i;++j){
tmp += dp[j]*dp[i-j-1];
}
dp[i] = tmp;
}
return dp[n];
}
};
- 螺旋矩陣
給定一個(gè)包含 m x n 個(gè)元素的矩陣（m 行, n 列）闪幽，請(qǐng)按照順時(shí)針螺旋順序啥辨，返回矩陣中的所有元素涡匀。
示例 1:
輸入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
輸出: [1,2,3,6,9,8,7,4,5]
思路：使用4個(gè)變量{l, r, b, t}記錄一個(gè)bounding box，按照螺旋的順序溉知，對(duì)box進(jìn)行遍歷：
- 如果矩陣的大小是{x, y}陨瘩，一開(kāi)始 {l,r,t,b} = {0, y-1, 0, x-1}
- 然后從左遍歷box中的第一行，top 向下移動(dòng)一個(gè)單位级乍，如果 top 比 bottom還低（即 boundingbox中只剩一行）結(jié)束舌劳。
- 從上到下遍歷最后一列，...
- 從右到左遍歷最后一行玫荣，...
- 從下到上遍歷第一列甚淡，...
- back to 1
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int len = matrix.size();
if(len==0){
return vector<int>();
}
int t = 0,l= 0,b=len,r=matrix[0].size();
vector<int> res;
while(true){
for(int i = l; i < r; ++i){
res.push_back(matrix[t][i]);
}
t++;
if(t==b){
break;
}
for(int i = t; i < b; ++i){
res.push_back(matrix[i][r]);
}
r--;
if(r==l){
break;
}
for(int i = r; i >= l; --i){
res.push_back(matrix[b][i]);
}
b--;
if(t==b){
break;
}
for(int i = b; i >= t; --i){
res.push_back(matrix[i][l]);
}
l++;
if(l==r){
break;
}
}
return res;
}
};
- 驗(yàn)證二叉搜索樹(shù)
給定一個(gè)二叉樹(shù)，判斷其是否是一個(gè)有效的二叉搜索樹(shù)捅厂。
假設(shè)一個(gè)二叉搜索樹(shù)具有如下特征：
節(jié)點(diǎn)的左子樹(shù)只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)贯卦。
節(jié)點(diǎn)的右子樹(shù)只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。
所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)焙贷。
思路：一開(kāi)始的時(shí)候沒(méi)有注意到是整個(gè)左子樹(shù)的節(jié)點(diǎn)都要小于撵割，右子樹(shù)都要大于。所以沒(méi)有考慮到這種case
需要在遞歸的時(shí)候加上一個(gè)上下界的判斷辙芍。
bool isValidBST(TreeNode* root) {
if(!root){
return true;
}
return isValidBST(root,((long)INT_MIN)-1,((long)INT_MAX)+1);//long是需要考慮邊界值的情況
}
bool isValidBST(TreeNode* root, long min, long max){
return root->val > min && root->val < max
&& (!root->left ||isValidBST(root->left,min,root->val))
&& (!root->right||isValidBST(root->right,root->val,max));
}
- 合并 k 個(gè)有序列表：
先實(shí)現(xiàn)有序列表的兩兩合并啡彬，再進(jìn)行歸并式的合并，分而治之故硅。
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size()==0){
return nullptr;
}
return merge(lists,0,lists.size()-1);
}
ListNode* merge(vector<ListNode*> v, int start,int end){
if(start == end){
return v[start];
}
int mid = start+end >> 1;
return merge2Lists(merge(v,start,mid),merge(v,mid+1,end));
}
ListNode* merge2Lists(ListNode* l1,ListNode* l2) {
ListNode* head = new ListNode(0);
ListNode* tmp = head;
while(l1 && l2){
if(l1->val < l2->val){
head -> next = l1;
l1 = l1 -> next;
} else {
head -> next = l2;
l2 = l2 ->next;
}
head = head-> next;
}
head -> next = l1? l1:l2 ;
return tmp->next;
}
};
-
數(shù)組中數(shù)字出現(xiàn)的次數(shù)
一個(gè)整型數(shù)組 nums 里除兩個(gè)數(shù)字之外庶灿，其他數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字吃衅。要求時(shí)間復(fù)雜度是O(n)往踢，空間復(fù)雜度是O(1)。
思路：先考慮一個(gè)簡(jiǎn)單一點(diǎn)的case捐晶，如果一個(gè)組中只有一個(gè)出現(xiàn)一次的數(shù)字菲语，其他數(shù)字都出現(xiàn)了2次，那么我們可以將整個(gè)列表異或得到那個(gè)只出現(xiàn)一次的數(shù)據(jù)：
int ret = 0;
for(int n : nums)
ret ^= n;
那可以將上面的問(wèn)題變成：
- 先將給定的數(shù)組分為兩個(gè) 只有一個(gè)出現(xiàn)一次的數(shù)字惑灵，其他數(shù)字都出現(xiàn)了2次 的兩個(gè)數(shù)組
- 分別對(duì)于兩個(gè)數(shù)組進(jìn)行異或山上，得到結(jié)果
問(wèn)題就是在如何實(shí)現(xiàn)1上面，為了實(shí)現(xiàn)1英支，分到的數(shù)組有兩個(gè)要求：
1）兩個(gè)只出現(xiàn)一次的數(shù)字需要被分到兩個(gè)組
2）任意一對(duì)大小相同的數(shù)字要被分到一個(gè)組
這個(gè)要求依舊可以巧妙的使用異或解決：
將整個(gè)數(shù)組全員異或得到一個(gè)值佩憾，由于一個(gè)數(shù)組中有兩個(gè)只出現(xiàn)一次的樹(shù)，所以
中肯定有一位是1，記錄下這個(gè)1的位置妄帘，用這個(gè)bit位的值將數(shù)組一分為二楞黄。這個(gè)分組方法滿足我們上面的要求：
- 由于在這個(gè)位置bit相同的數(shù)字會(huì)分到同一個(gè)數(shù)組，所以兩個(gè)相同的數(shù)字會(huì)被分到同一組抡驼，滿足1）
- 由于在
中這個(gè)位是1鬼廓，證明只出現(xiàn)一次的兩個(gè)數(shù)在這個(gè)位上的bit值不同，所以這兩個(gè)只出現(xiàn)一次的數(shù)字不會(huì)出現(xiàn)在同一個(gè)組中致盟，滿足2）碎税。
實(shí)現(xiàn)：
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int ret = 0;
for(int n : nums)
ret ^= n;
int div = 1;
while((div & ret) == 0)
div <<= 1;
int a=0, b=0;
for(int n: nums)
if(n & div)
a ^= n;
else
b ^= n;
return vector<int>{a,b};
}
};
- 子集
- 給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）馏锡。
說(shuō)明：解集不能包含重復(fù)的子集雷蹂。
思路：遞歸
實(shí)現(xiàn)：
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> list= {};
func(list,0,nums);//這里nums沒(méi)排序也過(guò)了，不過(guò)要注意一下杯道，如果題目沒(méi)有明確是否有序還是要排一下
return res;
}
void func(vector<int>& list,int index, vector<int> nums){
if(index == nums.size()){
res.push_back(list);
return;
}
for(int i = index; i < nums.size();++i){
list.push_back(nums[i]);
func(list, i+1,nums);
list.pop_back();
}
func(list,nums.size(),nums);
}
};
- 子集
給定一個(gè)可能包含重復(fù)元素的整數(shù)數(shù)組 nums匪煌，返回該數(shù)組所有可能的子集（冪集）。
說(shuō)明：解集不能包含重復(fù)的子集党巾。
示例:
輸入: [1,2,2]
輸出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
可以看到兩個(gè)重復(fù)的2擎椰，我們只保留了第一個(gè)朗若，這樣得到的子集集合就是答案：
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<int> list= {};
sort(nums.begin(),nums.end());
func(list,0,nums);
return res;
}
void func(vector<int>& list,int index, vector<int> nums){
if(index == nums.size()){
res.push_back(list);
return;
}
for(int i = index; i < nums.size();++i){
if(i > index && nums[i] == nums[i-1]){ /*注意 i > index 而不是 > 0 否則會(huì)錯(cuò)誤的將[2,2]所在的枝子剪掉*/
continue;
}
list.push_back(nums[i]);
func(list, i+1,nums);
list.pop_back();
}
func(list,nums.size(),nums);
}
};
- 格雷編碼
格雷編碼是一個(gè)二進(jìn)制數(shù)字系統(tǒng)呕寝，在該系統(tǒng)中，兩個(gè)連續(xù)的數(shù)值僅有一個(gè)位數(shù)的差異腻贰。
給定一個(gè)代表編碼總位數(shù)的非負(fù)整數(shù) n叹侄，打印其格雷編碼序列巩搏。即使有多個(gè)不同答案，你也只需要返回其中一種趾代。
格雷編碼序列必須以 0 開(kāi)頭贯底。
是一道找規(guī)律的題：
0 -> [0]
1 -> [ 0, 1]
2 -> [ 00, 01, 11, 10]
3 -> [000,001,011,010,
110, 111,101,100]
2 中的 00,01可以認(rèn)為是1中的[0,1]前面加了個(gè)0，也就是沒(méi)變撒强；而11,10可以認(rèn)為是1中的[0,1]倒序過(guò)來(lái)再加個(gè)1禽捆。
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> result(1,0);
for(int i = 0; i < n; i++){
int mask = 1 << i;
for(int j = result.size()-1; j>=0; --j){
result.push_back(mask^result[j]);
}
}
return result;
}
};
- 二叉樹(shù)鋸齒狀層次遍歷
要求：層次遍歷的基礎(chǔ)上，第一層從左到右遍歷第二層從右到左飘哨，以此類推胚想。
思路：如果使用BFS，需要對(duì)于在換層的時(shí)候?qū)﹃?duì)列進(jìn)行倒序芽隆，復(fù)雜度較高浊服。如果使用BFS统屈，可以用根據(jù)層數(shù)，直接使用insert(vec.begin(), val)和push_back(val)插入牙躺，效率更高愁憔。
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
dfs(res,0,root);
return res;
}
void dfs(vector<vector<int>>& res, int level, TreeNode* root){
if(!root){
return;
}
if(level >= res.size()){
res.push_back(vector<int>());
}
if(!root->left){
dfs(res,level+1,root->left);
}
if(!root->right){
dfs(res,level+1,root->right);
}
if(level%2==0){
res[level].push_back(root->val);
} else {
res[level].insert(res[level].begin(),root->val);
}
}
38.目標(biāo)和
給定一個(gè)非負(fù)整數(shù)數(shù)組，a1, a2, ..., an, 和一個(gè)目標(biāo)數(shù)孽拷，S《终疲現(xiàn)在你有兩個(gè)符號(hào) + 和 -。對(duì)于數(shù)組中的任意一個(gè)整數(shù)乓搬，你都可以從 + 或 -中選擇一個(gè)符號(hào)添加在前面思犁。
返回可以使最終數(shù)組和為目標(biāo)數(shù) S 的所有添加符號(hào)的方法數(shù)。
示例 1:
輸入: nums: [1, 1, 1, 1, 1], S: 3
輸出: 5
解釋:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5種方法讓最終目標(biāo)和為3进肯。
注意:
數(shù)組非空，且長(zhǎng)度不會(huì)超過(guò)20棉磨。
初始的數(shù)組的和不會(huì)超過(guò)1000江掩。
保證返回的最終結(jié)果能被32位整數(shù)存下。
思路：
- 剪枝
搜索空間為2^n乘瓤，可以排序后進(jìn)行剪枝环形，即：如果現(xiàn)在剩余的數(shù)組和都已經(jīng)小于當(dāng)前sum和目標(biāo)S之間差的絕對(duì)值，可以進(jìn)行剪枝衙傀。剪枝之前可以進(jìn)行一次倒序排序抬吟，使剪枝后的效率更高。
class Solution {
int res = 0;
vector<int> sum;
public:
int findTargetSumWays(vector<int>& nums, int S) {
int len = nums.size();
if(len==0){
return S==0?1:0;
}
sort(nums.rbegin(),nums.rend());
sum=vector(len,0);
sum[len-1]=nums[len-1];
for(int i = len-2; i >=0; --i){
sum[i] = sum[i+1] + nums[i];
}
findTargetSum(nums,0,0,S);
return res;
}
void findTargetSum(vector<int>&nums, int index, int s, int target){
if(index == nums.size()&&s==target){
res+=1;
return;
}
if(index >= nums.size()||(s < target && target-s > sum[index])||(s > target && s - target > sum[index])){
return;
}
findTargetSum(nums,index+1,s-nums[index],target);
findTargetSum(nums,index+1,s+nums[index],target);
}
};
2统抬、動(dòng)態(tài)規(guī)劃
可以把這個(gè)問(wèn)題考慮成為：我要把nums分成兩個(gè)集合火本，一個(gè)集合是正，一個(gè)集合是負(fù)數(shù)聪建，有集中分發(fā)可以讓兩個(gè)集合相加等于S钙畔。題中限制了 數(shù)組非空，且長(zhǎng)度不會(huì)超過(guò)20金麸。初始的數(shù)組的和不會(huì)超過(guò)1000擎析。 我們可以整一個(gè)num.size() * 2001的數(shù)組，設(shè)dp[i][j]為數(shù)組前i個(gè)元素和為j的方法個(gè)數(shù)
可以使用元祖法來(lái)省空間
-
前K個(gè)高頻單詞
沒(méi)什么好講的思路挥下，主要熟悉一下c++的api
值得注意的一點(diǎn)揍魂，iterator取出元素會(huì)做一個(gè)deep copy，修改它不會(huì)影響數(shù)組中的元素值棚瘟。
class Solution {
public:typedef struct sfi{
string s;
int freq = 0;//出現(xiàn)次數(shù)
} comp;typedef pair<string,sfi> pss;
static bool cmp(pss i, pss j){
if (i.second.freq == j.second.freq){
return i.second.s < j.second.s;
} else {
return i.second.freq > j.second.freq;
}
}
vector<string> topKFrequent(vector<string>& words, int k) {
map<string,comp> v;
for(int i = 0; i < words.size(); ++i){
auto iter = v.find(words[i]);
if(iter == v.end()){
comp c;
c.s=words[i];
c.freq = 1;
v[words[i]]=c;
} else {
comp c = iter->second;//這里是一個(gè)deep copy!
c.freq++;
v[words[i]]=c;
}
}
vector<pss> vec;
for(auto mp=v.begin(); mp != v.end(); mp++){
vec.push_back(pss(mp->first, mp->second));
}
sort(vec.begin(),vec.end(),cmp);
vector<string> res;
for(int i = 0; i < k; ++i){
res.push_back(vec[i].first);
}
return res;
}
}; 奇偶鏈表
給定一個(gè)單鏈表现斋，把所有的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分別排在一起。請(qǐng)注意解取，這里的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)指的是節(jié)點(diǎn)編號(hào)的奇偶性步责，而不是節(jié)點(diǎn)的值的奇偶性。
code：
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
ListNode* odd = head;
if(!odd){
return head;
}
ListNode* even = head->next;
ListNode* tmp = even;
while(odd->next&&even->next){
odd->next = odd->next->next;
odd = odd ->next;
even->next = even->next->next;
even = even->next;
}
odd->next=tmp;
return head;
}
};
- 把二叉搜索樹(shù)轉(zhuǎn)化為累加樹(shù)
使得每個(gè)節(jié)點(diǎn)的值是原來(lái)的節(jié)點(diǎn)值加上所有大于它的節(jié)點(diǎn)值之和。
思路：二叉樹(shù)反向中序遍歷
class Solution {
public:
TreeNode* bstToGst(TreeNode* root) {
int s = 0;
sum(root, s);
return root;
}
void sum(TreeNode* root, int& s){
if(!root){
return;
}
sum(root->right, s);
s += root->val;
root -> val = s;
sum(root->left, s);
}
};
- 祖父節(jié)點(diǎn)值為偶數(shù)的節(jié)點(diǎn)和
給你一棵二叉樹(shù)蔓肯，請(qǐng)你返回滿足以下條件的所有節(jié)點(diǎn)的值之和：
該節(jié)點(diǎn)的祖父節(jié)點(diǎn)的值為偶數(shù)遂鹊。（一個(gè)節(jié)點(diǎn)的祖父節(jié)點(diǎn)是指該節(jié)點(diǎn)的父節(jié)點(diǎn)的父節(jié)點(diǎn)。）
如果不存在祖父節(jié)點(diǎn)值為偶數(shù)的節(jié)點(diǎn)蔗包，那么返回 0 秉扑。
*/
class Solution {
public:
int sumEvenGrandparent(TreeNode* root) {
if(!root){
return 0;
}
queue<TreeNode*> q;
q.push(root);
int res = 0;
while(!q.empty()){
TreeNode* t = q.front();
q.pop();
if(t->val%2==0){
res+=sumOfGrandChildren(t);
}
if(t->left){
q.push(t->left);
}
if(t->right){
q.push(t->right);
}
}
return res;
}
int sumOfGrandChildren(TreeNode* root){
TreeNode* leftChild = root->left;
TreeNode* rightChild = root -> right;
int res = 0;
if(leftChild){
res += leftChild->left? leftChild->left->val:0;
res += leftChild->right? leftChild->right->val:0;
}
if(rightChild){
res += rightChild -> left? rightChild->left->val : 0;
res += rightChild -> right? rightChild->right->val:0;
}
return res;
}
};
- 重復(fù)的DNA序列
所有 DNA 都由一系列縮寫為 A，C调限，G 和 T 的核苷酸組成舟陆，例如：“ACGAATTCCG”。在研究 DNA 時(shí)耻矮，識(shí)別 DNA 中的重復(fù)序列有時(shí)會(huì)對(duì)研究非常有幫助秦躯。
編寫一個(gè)函數(shù)來(lái)查找目標(biāo)子串，目標(biāo)子串的長(zhǎng)度為 10裆装，且在 DNA 字符串 s 中出現(xiàn)次數(shù)超過(guò)一次踱承。
示例：
輸入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
輸出：["AAAAACCCCC", "CCCCCAAAAA"]
思路：
滑動(dòng)窗口+HashMap
- string 版本
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int len = 10;
vector<string> res;
if(s.size() < len){
return res;
}
char strs[s.size()+1];
strcpy(strs, s.c_str());
map<string,int> m;
for(int i=0; i <= s.size()-len; ++i){
char* a = strs + i;
char* b = strs + i + len;
char tmp = *b;
*b = '\0';
auto iter = m.find(a);
if(iter!=m.end()){
m[a] = iter->second+1;
} else {
m[a] = 1;
}
*b = tmp;
}
for(auto i = m.begin(); i!=m.end(); ++i){
if(i->second>1){
res.push_back(i->first);
}
}
return res;
}
};
問(wèn)題：string 計(jì)算hash時(shí)間太長(zhǎng)，string是不可變對(duì)象哨免，會(huì)大量new新的obj
2茎活、改進(jìn)版
使用0-3來(lái)表示四種字母，即使用兩位來(lái)表示一個(gè)字母琢唾。key的計(jì)算也比較簡(jiǎn)單载荔，可以使用位運(yùn)算來(lái)更新key。
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int len = 10;
vector<string> res;
if(s.size() < len){
return res;
}
unordered_map<int,int> m;
int key = 0;
for(int i = 0; i < len-1; ++i){
key = (key << 2) + getVal(s[i]);
}
int mask = 0xFFFFF;
for(int i=len-1; i < s.size(); ++i){
key = ((key << 2)&mask) + getVal(s[i]);
auto iter = m.find(key);
if(iter!=m.end()){
m[key] = iter->second+1;
} else {
m[key] = 1;
}
}
for(auto i = m.begin(); i!=m.end(); ++i){
if(i->second>1){
res.push_back(decode(i->first,len));
}
}
return res;
}
string decode(int val,int len){
char dir[] = {'A','C','G','T'};
char res[len+1];
res[len] = '\0';
for(int i = 0 ; i < len; ++i){
res[len-i-1] = dir[val&0x3];
val >>= 2;
}
return string(res);
}
int getVal(char a){
if(a=='A') return 0;
if(a=='C') return 1;
if(a=='G') return 2;
if(a=='T') return 3;
return 0;
}
};
值得一提的是采桃，這里使用unordered_map會(huì)比map快一倍（88ms vs 188ms）
- 只出現(xiàn)一次的元素
給定一個(gè)非空整數(shù)數(shù)組懒熙，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)了三次芍碧。找出那個(gè)只出現(xiàn)了一次的元素煌珊。
說(shuō)明：
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來(lái)實(shí)現(xiàn)嗎泌豆？
示例 1:
輸入: [2,2,3,2]
輸出: 3
示例 2:
輸入: [0,1,0,1,0,1,99]
輸出: 99
思路：異或定庵，永遠(yuǎn)滴神！
class Solution {
public:
int singleNumber(vector<int>& nums) {
int seen_once=0, seen_twice = 0;
//使用異或的時(shí)候踪危，可以把一個(gè)int當(dāng)成一個(gè)int集合蔬浙，異或一次，就是放進(jìn)這個(gè)集合贞远，再異或一次畴博，就取出來(lái)。
for(int num:nums){
// 如果見(jiàn)到過(guò)0次蓝仲，seen_twice 和 seen_once 兩個(gè)集合里面就不會(huì)有這個(gè)數(shù)字俱病，可認(rèn)為是0.
// 如果見(jiàn)到過(guò)1次官疲，seen_twice 是 0，seen_once 是 num
// 如果見(jiàn)到過(guò)2次亮隙，seen_twice 是 num
seen_once = ~seen_twice & (num ^ seen_once );
// 見(jiàn)過(guò)0次+1 ：~0 & (num ^ seen_once) = num^seen_once = num
// 見(jiàn)過(guò)1次+1 ：~0 & (num ^ seen_once) = num^seen_once = 0
// 見(jiàn)過(guò)2次+1 ：~num & (num ^ seen_once) = ~num & (num^0)= 0
seen_twice = ~seen_once & (num ^ seen_twice);
// 見(jiàn)過(guò)0次+1 ：~num(這里seen_once=num途凫，因?yàn)樯厦娴拇a執(zhí)行過(guò)了) & (num ^ seen_twice) = ~num & num = 0
// 見(jiàn)過(guò)1次+1 ：~0 & (num ^ seen_twice) = num ^ seen_twice = num;
// 見(jiàn)過(guò)2次+1 ：~0 & (num ^ seen_twice) = num ^ seen_twice = 0;
}
return seen_once;//最后seen_once剩下來(lái)的就是只出現(xiàn)了一個(gè)的
}
};
- 缺失的數(shù)字
給定一個(gè)包含 0, 1, 2, ..., n 中 n 個(gè)數(shù)的序列，找出 0 .. n 中沒(méi)有出現(xiàn)在序列中的那個(gè)數(shù)溢吻。
示例 1:
輸入: [3,0,1]
輸出: 2
示例 2:
輸入: [9,6,4,2,3,5,7,0,1]
輸出: 8
說(shuō)明:
你的算法應(yīng)具有線性時(shí)間復(fù)雜度维费。你能否僅使用額外常數(shù)空間來(lái)實(shí)現(xiàn)?
方案1 ：數(shù)學(xué)
根據(jù)求和公式，可以計(jì)算出原本的總和促王，減去數(shù)組中的元素就是缺失的元素犀盟，但是會(huì)有溢出風(fēng)險(xiǎn)，可以邊加下標(biāo)邊減數(shù)組中的內(nèi)容
int missingNumber(vector<int>& nums) {
int sum = 0;
for (int i = 1; i <= nums.size(); i++) {
sum += i;
sum -= nums[i - 1];
}
return sum;
}
方案2:異或
使用異或的場(chǎng)景是蝇狼，只要有辦法湊對(duì)找落單的阅畴，可以往異或方向去考慮：當(dāng)我們遍歷一個(gè)數(shù)組的時(shí)候，可以得到[0, len-1]的這些下標(biāo)题翰，再加上len恶阴，就是[0, len-1]，數(shù)組中的元素是[0, len]中少了一個(gè)豹障，把所有的這些異或起來(lái)，成對(duì)的變成0焦匈，落單的就留了下來(lái)血公。
int missingNumber(vector<int>& nums) {
int len = nums.size();
int missing = 0;
for(int i = 0; i < len; ++i){
missing ^= i ^ nums[i];
}
return missing^len;
}
- 移除掉k位數(shù)字
給定一個(gè)以字符串表示的非負(fù)整數(shù) num，移除這個(gè)數(shù)中的 k 位數(shù)字缓熟，使得剩下的數(shù)字最小累魔。
注意:
num 的長(zhǎng)度小于 10002 且 ≥ k。
num 不會(huì)包含任何前導(dǎo)零够滑。
思路：首先我們需要考慮怎么樣可以使刪除后的數(shù)字最小垦写，高位的數(shù)字優(yōu)先級(jí)高，所以需要從左向右掃描彰触。我們希望從高位開(kāi)始梯投，盡可能的非單調(diào)遞減。所以就要?jiǎng)h除高位逆序?qū)χ械牡谝粋€(gè)數(shù)字况毅。需要考慮到刪完數(shù)字為0開(kāi)頭和刪完為0的特殊情況分蓖。自己寫的太啰嗦，借鑒力扣大神的一個(gè)寫法尔许。
class Solution {
public:
string removeKdigits(string num, int k) {
if(num.size() == k) return string(1, '0');
string stk;//string可以拿來(lái)當(dāng)一個(gè)棧使用么鹤，下面算法保證這個(gè)棧內(nèi)的元素單調(diào)非遞減
int i = 0;
while(k > 0 && i < num.size()) // 將num中的字符按規(guī)則移動(dòng)到棧中
{
if(stk.empty() || stk.back() <= num[i]) // 直接入棧，并轉(zhuǎn)而遍歷下一個(gè)元素
{
stk.push_back(num[i]);
++i;
}
else // stk.back() > num[i]
{
stk.pop_back();
--k;
}
}
// 1. 如果i == 0, 則 k 可能不等于0, 移除掉stk末尾k個(gè)元素.
// 2. 如果k == 0, 則 i 可能不等于0, 需要加上num中i之后的元素.
stk = stk.substr(0, stk.size() - k) + num.substr(i);
// 移除開(kāi)頭的0,在全0的情況下保證至少剩下一個(gè)0.
size_t beginIndex = 0;
while(beginIndex < stk.size() - 1 && stk[beginIndex] == '0') ++beginIndex;
return stk.substr(beginIndex);
}
};
- 快速冪
class Solution {
public:
double myPow(double x, int n) {
int neg = n < 0;
n=abs(n);
double res = 1;
double cur = x;
while(n > 0){
int m = n%2;
n/=2;
if(m){
res *=cur;
}
cur *=cur;
}
return neg? 1/res:res;
}
};
變體：超級(jí)次方
你的任務(wù)是計(jì)算 ab 對(duì) 1337 取模味廊，a 是一個(gè)正整數(shù)蒸甜，b 是一個(gè)非常大的正整數(shù)且會(huì)以數(shù)組形式給出棠耕。
示例 1:
輸入: a = 2, b = [3]
輸出: 8
示例 2:
輸入: a = 2, b = [1,0]
輸出: 1024
思路：開(kāi)始還頭疼想著想著怎么把大數(shù)數(shù)組轉(zhuǎn)成2進(jìn)制，后來(lái)看了一個(gè)題解柠新，可以十進(jìn)制直接快速冪后對(duì)于10進(jìn)制的那個(gè)個(gè)位數(shù)再進(jìn)行一次二進(jìn)制快速冪窍荧。
class Solution {
//(a*b)%c = (a%c)*(b%c);
public:
int superPow(int a, vector<int>& b) {
a= a%1337;
int res = 1;
int cur = a;
for(int i = 0; i < b.size(); ++i){
if(b[b.size()-1-i]>0){
res = (res *fastPow(cur,b[b.size()-1-i]))%1337;
}
cur = fastPow(cur,10);//dp中如果dp[i]可以只由固定個(gè)dp[i-x]遞推出來(lái)，可以不用開(kāi)數(shù)組登颓，固定幾個(gè)變量就好搅荞。
}
return res;
}
int fastPow(int a, int n){
int res = 1;
int cur = a%1337;
while(n>0){
if(n%2==1){
res*=cur;
}
cur=(cur*cur)%1337;
n/=2;
}
return res%1337;
}
};
示例:
A = [1, 2, 3, 4]
返回: 3, A 中有三個(gè)子等差數(shù)組: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
思路：統(tǒng)計(jì)所有的等差數(shù)組長(zhǎng)度lens(>=3)框咙，每個(gè)等差序列有(len-2)*(len-1)/2個(gè)len>3的子序列
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
if(A.size() < 3){
return 0;
}
int res = 0;
//思路：先找數(shù)組中等差數(shù)組的長(zhǎng)度咕痛，再
int len = 2;//等差數(shù)組長(zhǎng)度（要大于三）
int oldDiff = A[1]-A[0];
int cur = 2;
// vector<int> lens; //記錄數(shù)組中非重疊等差數(shù)組們的長(zhǎng)度 改-無(wú)需記錄，循環(huán)的時(shí)候算就可以了
while(cur < A.size()){
int curDiff = A[cur]-A[cur-1];
if(curDiff != oldDiff ){
oldDiff = curDiff;
if(len > 2){
// lens.push_back(len);
res += (len-1)*(len-2)/2;
}
len = 2;
} else {
len++;
}
cur++;
}
if(len > 2){
res += (len-1)*(len-2)/2;
// lens.push_back(len);
}
// int res = 0;
// for(int num : lens){
// res += (num-1)*(num-2)/2;//
// }
return res;
}
};
思路2:動(dòng)態(tài)規(guī)劃喇嘱，
- 查找和最小的k個(gè)數(shù)對(duì)
可以使用優(yōu)先級(jí)隊(duì)列/小頂堆來(lái)實(shí)現(xiàn)
Priority queues are a type of container adaptors, specifically designed such that** its first element is always the greatest of the elements it contains**, according to some strict weak ordering criterion.
// Priority queue
class Solution {
public:
struct cmp{
bool operator ()(pair<int,int> a, pair<int,int> b){
return a.first + a.second > b.first + b.second;
}
};
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
vector<vector<int>> res;
priority_queue<pair<int,int>, vector<pair<int,int> >,cmp> q;//priority_queue<Type, Container, Compare>
for(int i = 0; i < nums1.size(); ++i){
for(int j = 0; j < nums2.size(); ++j){
q.push(pair<int,int>(nums1[i],nums2[j]));
}
}
for(int i = 0; i < k && !q.empty();++i){
pair<int,int> p =q.top();
q.pop();
res.push_back({p.first,p.second});
}
return res;
}
};
- 旋轉(zhuǎn)函數(shù)
給定一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 A 茉贡。
假設(shè) Bk 是數(shù)組 A 順時(shí)針旋轉(zhuǎn) k 個(gè)位置后的數(shù)組，我們定義 A 的“旋轉(zhuǎn)函數(shù)” F 為：
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]者铜。
計(jì)算F(0), F(1), ..., F(n-1)中的最大值腔丧。
注意:
可以認(rèn)為 n 的值小于 105。
示例:
A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 作烟。
思路：
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (1 * 4) + (2 * 3) + (3 * 2) + (0 * 6) = 0 + 4 + 6 + 6 = 16
F(2) = (2 * 4) + (3 * 3) + (0 * 2) + (1 * 6) = 0 + 6 + 8 + 9 = 23
F(3) = (3 * 4) + (0 * 3) + (1 * 2) + (2 * 6) = 0 + 2 + 12 + 12 = 26
規(guī)律如下愉粤，如果數(shù)組nums的長(zhǎng)度為len，總和為sum拿撩，F(xiàn)(i) = F(i-1) + sum - nums[len-1-i];
注意衣厘，在加和的過(guò)程中可能溢出
class Solution {
public:
int maxRotateFunction(vector<int>& A) {
long res=0;
int len=A.size();
long sum=0;
for(int i = 0; i < len; ++i){
res += A[i]*i;
sum += A[i];
}
long old = res;//注意會(huì)溢出
for(int i = 0; i<len-1; ++i){
old = old + sum - A[len-1-i]*(long)len;
res = max(res,old);
}
return (int)res;
}
};
