?

目錄

?

力扣.1054距離相等的條形碼

力扣767.重構字符串

力扣47.全排列II

力扣980.不同路徑III

力扣509.斐波那契數列（記憶化搜索)

---

力扣.1054距離相等的條形碼

是否策略正確

但是假如 1 2 2 此時 1_2? ? ?此時中間只能填寫2，但是就不對了，所以，限定條件，先處理出現次數最多的次數，其余無所謂?

2_2

證明:題目一定有解，性質:兩個兩個一組

（n+1）/2組，出現次數最多的次數，一定是小于(n+1)/2個，那么

假如出現次數最多的，等于(n+1)/2,一定正確

第二個，最多的，小于(n+1)/2, 假如你? ?前面? ? ? ? o _ o_ o_ o_ x_ x_x 假如你第二個沒填寫完，就還是x,但是你不可能說是x填重復的，換句話，x絕對不可能繞過一圈來再次相鄰，

class Solution {public int[] rearrangeBarcodes(int[] barcodes) {Arrays.sort(barcodes);int n=barcodes.length;Map<Integer,Integer>map=new HashMap<>();int[]a=new int[n];int max=0;int maxcount=0;
//第一個點，該定義變量就去定義，不要老想著優化for(int i=0;i<n;i++){map.put(barcodes[i],map.getOrDefault(barcodes[i],0)+1);if(maxcount<map.get(barcodes[i])){max=barcodes[i];maxcount=map.get(barcodes[i]);}}//先處理出現次數最多的那個數字int index=0;//統計處那個字符數字最多，然后給他填上
//最難的一步就是maxcount你是否能理清楚for(int i=0;i<maxcount;i++){a[index]=max;index+=2;}//處理剩下的數，可以直接刪除，也可以遍歷時候跳過，不要太糾結map.remove(max);for(int x:map.keySet()){for(int i=0;i<map.get(x);i++){if(index>=n) index=1;a[index]=x;index+=2;}}return a;}
}

力扣767.重構字符串

跟上面那個題思路一樣，只需要進行一個判斷，是否滿足條件就行。

max>(n+1)/2的情況下，就返回空字符串

class Solution {public String reorganizeString(String s) {HashMap<Character,Integer>map=new HashMap<>();//(n+1)/2char[]a=s.toCharArray();int n=a.length;char max=a[0];int maxCount=0;for(int i=0;i<n;i++){map.put(a[i],map.getOrDefault(a[i],0)+1);if(maxCount<map.get(a[i])){max=a[i];maxCount=map.get(a[i]);}}if(maxCount>(n+1)/2)return "";else{StringBuffer sb=new StringBuffer();int index=0;for(int i=0;i<maxCount;i++){a[index]=max;index+=2;}map.remove(max);for(char x:map.keySet()){for(int i=0;i<map.get(x);i++){if(index>=n)index=1;a[index]=x;index+=2;}}return sb.append(a).toString();}}
}

力扣47.全排列II

1.同一個節點都所有分支中，相同的元素只可以選擇一次

同一個數只能使用一次

并且我們需要對數組，進行一個排序，去確定 check[i]==true||nums[i]與nums[i-1]是否相同

同一層的話，不用考慮 check[i-1]==false

考慮不合法的分支(這里的i不可以等于0,0一定合法，不用判斷)?

check[i]==true ||(i!=0&&nums[i]==nums[i-1]&&check[i-1]==false)

假如i位置是true代表當前位置已經被使用了，或者，當前位置的前一個沒有被使用，但是我和你是在一層，換句話說，我們屬于一層，那么就應該剪枝

考慮合法的分支(這里面的i是可以等于0的(

check[i]=false&&(nums[i]!=nums[i-1]||check[i-1]==true(此時的條件是a[i]=a[i-1])? ? ? )

class Solution {List<List<Integer>>ret=new ArrayList<>();List<Integer>ans=new ArrayList<>();boolean[]check;int n;//伴隨著就是如何剪枝public void dfs(int pos,int []nums){if(pos==n){ ret.add(new ArrayList<>(ans)); return ;}for(int i=0;i<n;i++){if((check[i]==true)||(i!=0&&check[i-1]==false&&nums[i]==nums[i-1])){continue;}    check[i]=true;ans.add(nums[i]);   dfs(pos+1,nums);ans.remove(ans.size()-1);check[i]=false;;}}public List<List<Integer>> permuteUnique(int[] nums) {n=nums.length;Arrays.sort(nums);check=new boolean[n];dfs(0,nums);    return ret;}
}

力扣980.不同路徑III

step++,然后到達終點之后，路徑++，然后不斷遞增就好

這個要注意，最后才調用這個函數要讓step走完

class Solution {int pathCount=0;int[]dx={0,0,1,-1};int[]dy={1,-1,0,0};int n;int m;int step;boolean[][]vis;public void dfs(int count,int[][]grid,int i,int j){if(grid[i][j]==2){if(count==step)pathCount++;return;}for(int k=0;k<4;k++){int x=i+dx[k];int y=j+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]==false&&(grid[x][y]==0||grid[x][y]==2)){vis[x][y]=true;dfs(count+1,grid,x,y);vis[x][y]=false;}}  }public int uniquePathsIII(int[][] grid) {n=grid.length;m=grid[0].length;vis=new boolean[n][m];int bx=0;int by=0;//這么判斷是否走完全了for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1){bx=i;by=j;vis[bx][by]=true;}else if(grid[i][j]==0||grid[i][j]==2)step++;}}dfs(0,grid,bx,by);return pathCount;}
}

力扣509.斐波那契數列（記憶化搜索)

存儲在map，假如有值，直接返回，就不用再去遞歸了。

class Solution {Map<Integer,Integer>map=new HashMap<>();public int dfs(int n){if(map.containsKey(n)){return map.get(n);}   map.put(n,dfs(n-1)+dfs(n-2));return map.get(n);}public int fib(int n) {map.put(0,0);map.put(1,1);return dfs(n);}
}