關于圖形的題目一般歸屬到hard裡面，需要打開思路
預設小頂堆，
new PriorityQueue<Integer>((a, b) -> b - a);// store num <= median
，這個是大頂堆
PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){
@Override
public int compare(ListNode o1,ListNode o2){
if (o1.val<o2.val)
return -;
else if (o1.val==o2.val)
return ;
else
return ;
}
});
動态規劃的動作，初始狀态的定義，狀态的緩存，狀态之間的動作關系。
130. Surrounded Regions
注意使用m*n表示數組的行數跟列數
X X X X
X O O X
X X O X
X O X X
完成後
X X X X
X X X X
X X X X
X O X X
思路：這個利用原來的傳染方法，一旦發現邊緣地帶有O，利用深度搜尋方法将O切換成為*，然後再執行一次周遊。
309. Best Time to Buy and Sell Stock with Cooldown
動态規劃問題，這個定義了三個狀态，狀态0，是停盤狀态， 狀态1是購買後的狀态，狀态2是賣出後的狀态
定義三個數組，數組下标i表示的是第i次操作。
//這裡給出代碼
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= ) return ;
int[] s0 = new int[prices.length];
int[] s1 = new int[prices.length];
int[] s2 = new int[prices.length];
s0[] = ;//停盤
s1[] = -prices[];// 買
s2[] = Integer.MIN_VALUE;// 賣
for (int i = ; i < prices.length; i++) {
s0[i] = Math.max(s0[i - ], s2[i - ]);
s1[i] = Math.max(s0[i - ] - prices[i], s1[i - ]);
s2[i] = Math.max(s2[i - ], s1[i - ] + prices[i]);
}
return Math.max(s0[prices.length - ], s2[prices.length - ]);
}
}
28. Implement strStr()
KMP算法的實作
這個是簡單的版本
public class Solution {
public int strStr(String haystack, String needle) {
char[] has = haystack.toCharArray();
char[] nee = needle.toCharArray();
if (nee.length == ) {
return ;
}
int[] next = getNext(nee);
int i = ;
int j = ;
while (i < has.length) {
if (has[i] == nee[j]) {
i++;
j++;
if (j == nee.length) return i - nee.length;
} else {
if (j != ) {
j = next[j - ];
} else {
i++;
}
}
}
return -;
}
public int[] getNext(char[] arr) {
int[] next = new int[arr.length];
next[] = ;
int i = ;
int len = ;
while (i < arr.length) {
if (arr[i] == arr[len]) {
len++;
next[i] = len;
i++;
} else {
if (len == ) {
next[i] = ;
i++;
} else {
len = next[len - ];
}
}
}
return next;
}
}
214. Shortest Palindrome
給定一個字元串，加上最小的得到一個回文的字元串
也是利用到KMP的算法
public String shortestPalindrome(String s) {
String temp = s + "#" + new StringBuilder(s).reverse().toString();
int[] table = getTable(temp);
//get the maximum palin part in s starts from 0
return new StringBuilder(s.substring(table[table.length - ])).reverse().toString() + s;
}
一道樹的題目
思路:原來是要個建構二叉樹進遞歸實作，現在換成了三個數組的實作，第一個數組按照需求将資料依次存入，第二個數組用來緩存是否出現了，第三個素組用來存儲父節點，然後對于連續兩個同一結點的，就是4層樹，但是輸入形式是113,212，224等代表不同的東西
public static int sum(){
ArrayList list = new ArrayList();
Scanner scanner= new Scanner(System.in);
int inputData = ;
while(scanner.hasNext()){
inputData =scanner.nextInt();
if(inputData == ){
break;
}
list.add(inputData);
}
int resu = ;
int[] sarr = new int[]; //
int[] hasvalue = new int[];
for (int k = ; k < ; k++) {
hasvalue[k] = -;
}
for (int i = ; i < list.size(); i++) {
int temp = (int)list.get(i);
int lev = (temp / ) - ;
int ind = (temp % ) / - ;
int val = temp % ;
int index = (int) (Math.pow(, lev) + ind - );
if (lev > ) {
int faindex = (int) (Math.pow(, lev - ) - + ind / );
sarr[index] = sarr[faindex] + val;
hasvalue[index] = ;
} else {
sarr[index] = val;
hasvalue[index] = ;
}
}
int[] fa = new int[];
fa[] = ;
int faTemp = ;
for (int j = ; j < ; j += ) {
fa[j] = faTemp;
fa[j + ] = faTemp;
faTemp++;
}
for (int i = ; i < ; i += ) {
if (hasvalue[i] == - && hasvalue[i + ] == -) {
resu += sarr[fa[i]];
}
}
for (int j = ; j < ; j++) {
if (hasvalue[j] > ){
resu += sarr[j];
}
}
return resu;
}
給定不同顔色，1-9，給你一串氣球，随便剪，剪完之後每一個子串都不重複，這個可以采用遞歸法，但是時間有一定的限制。最好的方法是動态規劃。
我當時采用的是尾遞歸的方法，存在兩種可改進的地方，一是如果從目前的子串進行切分的時候，如果不滿足條件，沒有進行break的操作。二，對于重複的出現的字元串沒有加Map進行緩存做了過多次的判斷
//這個是正統的動态規劃問題
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = ;
if (sc.hasNext()) {
n = sc.nextInt();
}
int[] a = new int [n + ];
int[] dp = new int [n + ];
int[] cut = new int[];
for (int i = ; i <= n; i++) {
a[i] = sc.nextInt();
}
dp[] = ;
for(int i = ; i <= n; i++){
for (int k = ; k < ; k++) {
cut[k] = ;
}
for(int j = ; j < i; j++){
cut[a[i - j]]++; //從某個地方開始切分，我這邊記錄下出現的緩存
if(cut[a[i - j]] > )// 已經從這個地方切過了再往前去也沒有什麼更好的辦法了的，就停止了
break;
dp[i] = (int) ((dp[i] + dp[i - j - ]) % maxn);
}
}
System.out.println(Arrays.toString(dp));
}
//還是這個方法比厲害
360附件題目，分金子，也是個很不錯的動态規劃問題
A、B兩夥馬賊得到金子，輸入一個長度為n的數組字元串，問如果A先選，那麼求A最後能得到的最大的收入是多少
//也是一道動态規劃的題目，dp是一個二維數組，其中dp[i][i + a]表示從第i到 i + a個子數組中A先選的到金額數目，sum就顯得很有用了，還是畫圖進行考慮，看看兩邊從哪個選能得到相對更大的數
for (int ca = ; ca < T; ca++) {
int n = ;
n = scanner.nextInt();
int[] arr = new int[];
for (int j = ; j <= n; j++) {
arr[j] = scanner.nextInt();
}
int[] sum = new int[];
sum[] = ;
for (int k = ; k <= n; k++) {
sum[k] = sum[k - ] + arr[k];
}
int [][] dp = new int[][];
for(int a = ; a < n ; a++) {
for(int j = ; j < n ; j++) {
for(int i = ; i <= n - j ; i++){
dp[i][i + j] = Math.max(sum[i + j - ] - sum[i - ] - dp[i][i + j - ] + arr[i + j], sum[i + j] - sum[i] - dp[i + ][i + j] + arr[i]);
}
}
System.out.println("Case " + ca + ":" + dp[][n] + " " + (sum[n] - dp[][n]) );
}
42. Trapping Rain Water
就是看能放下多少的雨水
一個outofbox的方法，可以從左邊到右邊left得到leftmax與rightmax，選取一方低的，得到相關的內插補點,保證水不會沖另外一方流出去
140. Word Break II
更新下backtrack的方法，從前面往後進行遞歸，動态規劃用于緩存後面的子串的結果
同時，String.startsWith()方法,需要注意
//回溯法的更新版本
public class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
return DFSHelp(s, wordDict, new HashMap<String, LinkedList<String>>());
}
public List<String> DFSHelp(String s, List<String> wordDict, HashMap<String, LinkedList<String>> map) {
if (map.containsKey(s)) {
return map.get(s);
}
LinkedList<String> res = new LinkedList<String>();
if (s.length() == ) {
res.add("");
return res;
}
for (String word : wordDict) {
if (s.startsWith(word)) {
List<String> sublist = DFSHelp(s.substring(word.length()), wordDict, map);
for (String sub : sublist) {
res.add(word + (sub.isEmpty() ? "" : " ") + sub);
}
}
}
map.put(s, res);
return res;
}
}
212. Word Search II
給定一個二維數組，數組中的每一個位置為一個字元，給定一個字元串數組，輸出其中可以被字元進行組成的字元串，兩個字元之間必須是鄰居
思路：建構單詞查找樹，進行DFS，設定通路标記, Trie樹的一個應用
//深度搜尋
public class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> resu = new LinkedList<String>();
TrieNode root = makeTrieNode(words);
for (int i = ; i < board.length; i++) {
for (int j = ; j < board[].length; j++) {
dfs(board, root, i, j, resu);
}
}
return resu;
}
public void dfs (char[][] board, TrieNode root, int i, int j, List<String> resu) {
char c = board[i][j];
if (c == '#' || root.next[c - 'a'] == null) {
return;
}
root = root.next[c - 'a'];
if (root.word != null) {
resu.add(root.word);
root.word = null;//de-duplicate
}
board[i][j] = '#';
if (i > ) dfs(board, root, i - , j, resu);
if (j > ) dfs(board, root, i, j - , resu);
if (i < board.length - ) dfs(board, root, i + , j, resu);
if (j < board[].length - ) dfs(board, root, i, j + , resu);
board[i][j] = c;
}
public TrieNode makeTrieNode (String[] words) {
TrieNode root = new TrieNode();
for (String s : words) {
TrieNode p = root;
for (char c : s.toCharArray()) {
int i = c - 'a';
if (p.next[i] == null) {
p.next[i] = new TrieNode();
}
p = p.next[i];
}
p.word = s;
}
return root;
}
class TrieNode {
TrieNode[] next = new TrieNode[];
String word;
}
}
10. Regular Expression Matching
字元比對問題，采用動态規劃的方法，’.’表示的是比對一個字元，‘*’表示的是比對前面任意多個字元，判斷初始字元串s含有通配符的字元串p是否相等
public class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
boolean[][] dp = new boolean[s.length()+][p.length()+];
dp[][] = true;
for (int i = ; i < p.length(); i++) {
if (p.charAt(i) == '*' && dp[][i-]) {
dp[][i+] = true;
}//這個地方是為了去掉前面為0 的影響,這個時候i為0，也就是s串還沒有開始比對
}
for (int i = ; i < s.length(); i++) {
for (int j = ; j < p.length(); j++) {
if (p.charAt(j) == '.') {
dp[i+][j+] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
dp[i+][j+] = dp[i][j];
}
if (p.charAt(j) == '*') {
if (p.charAt(j-) != s.charAt(i) && p.charAt(j-) != '.') {
dp[i+][j+] = dp[i+][j-];
} else {
dp[i+][j+] = (dp[i+][j] || dp[i][j+] || dp[i+][j-]);
}
}
}
}
return dp[s.length()][p.length()];
}
}
76. Minimum Window Substring
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.
給定兩個字元串，S如果包含T，傳回的是S中包含T的最小長度的子串，如果不包含傳回“”，
思路：O(n)時間複雜度，用兩個HashMap進行緩存。根據start不段進行更新操作
下面給出的是用一個的方法
public String minWindow(String s, String t) {
HashMap<Character,Integer> map = new HashMap();
for(char c : s.toCharArray())
map.put(c,);
for(char c : t.toCharArray()) {
if(map.containsKey(c))
map.put(c,map.get(c)+);
else
return "";
}
int start =, end=, minStart=,minLen = Integer.MAX_VALUE, counter = t.length();
while(end < s.length()) {
char c1 = s.charAt(end);
if(map.get(c1) > )
counter--;
map.put(c1,map.get(c1)-);
end++;
while(counter == ) {
if(minLen > end-start) {
minLen = end-start;
minStart = start;
}
char c2 = s.charAt(start);
map.put(c2, map.get(c2)+);
if(map.get(c2) > )
counter++;
start++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart,minStart+minLen);
}
128. Longest Consecutive Sequence
給定一個數組，輸出連續不斷的最長的子序列的長度。
思路：out of box ， 給定一個Map緩存即可，其長度，每當過來一個數，判斷n - 1，作為left，n+1作為right，那麼長度為 left + right + 1，同時更新n-left，與n+right
329. Longest Increasing Path in a Matrix
這個就是采用遞歸，之一注意遞歸條件，i<0 或者 i>length, j <0或者j >length或者對目前的值進行比較。
295. Find Median from Data Stream
找到資料流中的中位數
思路：兩個堆
PriorityQueue pq = new PriorityQueue<Integer>((a, b) -> b - a);// 大頂堆
PriorityQueue pq = new PriorityQueue<Integer>;// 預設小頂堆
PriorityQueue pq = new PriorityQueue<Integer>((a, b) -> a - b);// 小頂堆
41. First Missing Positive
給一個無序的數組，要求傳回第一個丢失的正數。
思路：将正數i放在數組的第i-1的位置上，然後再周遊得到。
84. Largest Rectangle in Histogram
要求，輸入一組數組，輸出得到最大的矩形面積，用stack進行index的緩存，當height[i] > stack.peek(),進行入棧動作，否則進行面積的計算 i- 1 - satck.peek();此處 i為stack.pop()
239. Sliding Window Maximum
315. Count of Smaller Numbers After Self
要求，給定一個數組，從右邊開始，統計出右邊數中比它本身還要小的數
思路：采用BST進行二叉樹的建構，時間複雜度為NlongN，要小心的處理好插入節點目前循環的邏輯
//遞歸的構造樹的時候，需要處理好目前結點的位置關系
public class Solution {
public List<Integer> countSmaller(int[] nums) {
Integer [] ans = new Integer[nums.length];
Node root = null;
for (int i = nums.length - ; i >= ; i--) {
root = insertNode(nums[i], root, ans, i, );
}
return Arrays.asList(ans);
}
public Node insertNode(int num, Node root, Integer[] ans, int i, int preNum) {
if (root == null) {
root = new Node(num, );
ans[i] = preNum;
} else if (root.val == num) {
root.dup++;
ans[i] = preNum + root.sum;
} else if (root.val > num) {
root.sum++;
root.left = insertNode(num, root.left, ans, i, preNum);
} else {
root.right = insertNode(num, root.right, ans, i, preNum + root.sum + root.dup);
}
return root;
}
class Node {
Node left, right;
//sum 表示左邊樹的個數，dup表示目前結點重複的個數，val表示目前結點的值
int val, sum, dup = ;// sum to count left node nums
public Node (int v, int s) {
val = v;
sum = s;
}
}
}
297. Serialize and Deserialize Binary Tree
要求：對一個二叉樹進行序列化和反序列化，中間結果為String
思路： 利用遞歸的方法，采用前序周遊，不足的地方補”X”,利用StirngBuilder進行緩存
在反序列化的時候用Queue進行資料的緩存。Queue的底層實作是linkedlist
239. Sliding Window Maximum
給定滑動視窗，取出滑動視窗裡面元素的最大值。這個采用雙向隊列的方式進行,一定要明白這個雙向隊列裡面放的是數組元素的下标，
思路： 1.移除滑動視窗左面的下标
2.從後面進行判斷，對下标記中index如果小于目前nums[i],就移除
3.對傳回結果進行修改
Deque<Integer> dequ = new ArrayDeque<Integer>();
dequ.pollLast()
dequ.peekLast()
23. Merge k Sorted Lists
這個暫時采用優先隊列來做，但是我可以隻維護其中數組數量大小的隊列，新定義一個資料結構。
149. Max Points on a Line
判斷經過同一條直線的最大的點的數量,根據公式進行推導
用 Since a is a rational, there exists y0 and x0, y0/x0=(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a
這兩個數進行判定
//這個地方值得學習的是取兩個數的最大公約數
//以及針對兩個變量，加上 x和 y的緩存
private int generateGCD(int a,int b){
if (b == ) return a;
else return generateGCD(b,a%b);
}
146. LRU Cache
要求：實作一個緩存，給定capacity容量大小的限定
思路：本來打算用隊列來實作，其實是錯誤的，容量不足時，需要删除最後一個，其中讀和插入操作都會影響優先級别。
這個地方采用的是雙連結清單加HashMap進行緩存的結構,注意回顧雙連結清單的删除結點操作以及追加到頭結點後面的操作。
4. Median of Two Sorted Arrays
要求：兩個有序數組，輸出兩個數組合并以後的中位數。
思路：從中位數的定義出發，找出兩個數組的下标 i和j的關系，如果是奇數個，傳回的max_left，如果是偶數個，傳回max_left 與 min_right的平均數。
44. Wildcard Matching
要求：實作通配符。這裡面的？比對一個字元， *比對任意一個子串，同時也包括0。
與10. Regular Expression Matching正規表達式比對相對應
//通配符，比對，解決了,這塊也可以寫成動态規劃的形式
// dp[i + 1][j + 1] = dp[i][j + 1],*比對多個
//dp[i + 1][j + 1] = dp[i + 1][j], *比對為空
public class Solution {
public boolean isMatch(String str, String pattern) {
int s = 0, p = 0, match = 0, starIdx = -1;
while (s < str.length()){
// advancing both pointers
if (p < pattern.length() && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
s++;
p++;
}
// * found, only advancing pattern pointer
else if (p < pattern.length() && pattern.charAt(p) == '*'){
starIdx = p;//記錄
match = s;
p++;
}
// last pattern pointer was *, advancing string pointer
else if (starIdx != -1){
p = starIdx + 1;//
match++;
s = match;
}
//current pattern pointer is not star, last patter pointer was not *
//characters do not match
else return false;
}
//check for remaining characters in pattern
while (p < pattern.length() && pattern.charAt(p) == '*')
p++;
return p == pattern.length();
}
}
Sunday算法的實作，優于與kmp算法
兩個都是字元串比較算法，Sunday在處理重複元素的時，時間複雜度比kmp要差
public static int SundaySearch(){
GetNext();
System.out.println(Arrays.toString(_next));
int destLen = dest.length();
int patternLen = pattern.length();
if (destLen == ) return -;
for (int i = ; i <= destLen - patternLen;){
int j = i;//dest[j]
int k = ;//pattern[k]
for (; k < patternLen && j < destLen && dest.charAt(j) == pattern.charAt(k); j++, k++)
;//do nothing
if (k == patternLen)//great! find it!
return i;
else{
if (i + patternLen < destLen) {
i += (patternLen - _next[dest.charAt(i + patternLen)]);
}
else
return -;
}
}
return -;
}
public static void GetNext(){
int len = pattern.length();//get the length
for (int i = ; i < ; i++)
_next[i] = -;
for (int i = ; i < len; i++)
_next[pattern.charAt(i)] = i;
}
alibaba的一道時間間隔内，限制通路次數的題目
// 在機關時間間隔内，限制通路次數。
static String[] demo(int M, int N, List<String> listlog) throws ParseException {
// M 是時間間隔 N是限制次數
SimpleDateFormat formatter = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
List<String> resu = new ArrayList<String>();
Map<String, LinkedList<String>> mapqu = new HashMap<String, LinkedList<String>>();
for (int i = ; i < listlog.size(); i++) {
String temp = listlog.get(i);
String [] parm = getPam(temp);
String name = parm[];
if ( resu.contains(name)) {
continue;
}
if (mapqu.containsKey(name)) {
LinkedList<String> qu = mapqu.get(name);
qu.add(temp);
if (qu.size() > N) {
String be = qu.poll();
Date bt = formatter.parse(be.substring(, ));
Date da = formatter.parse(temp.substring(, ));
int min = (int) ((da.getTime() - bt.getTime()) / / );
if (min < M) {
resu.add(name);
continue;
}
}
} else {
LinkedList<String> qu = new LinkedList<String>();
qu.add(temp);
mapqu.put(name, qu);
}
}
String [] re = new String[resu.size()];
for (int i = ; i < resu.size(); i++) {
re[i] = resu.get(i);
}
return re;
}
public static String[] getPam(String s) {
return s.split("#");
}
122. Best Time to Buy and Sell Stock II
隻要明白a[i + 1] - a[i] + a[i] - a[i - 1] = a[i + 1] - a[i - 1];即可
309. Best Time to Buy and Sell Stock with Cooldown
定義了三個狀态， 三個數組進行狀态的緩存
123. Best Time to Buy and Sell Stock III
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
現在函數要求隻有兩次的購買機會
//這裡的動态規劃買的隻是比我便宜的時候，我來買
public int maxProfit(int[] prices) {
if (prices == null || prices.length < ) return ;
int[] hold1 = new int[prices.length];
int[] hold2 = new int[prices.length];
int[] res1 = new int[prices.length];
int[] res2 = new int[prices.length];
hold1[] = -prices[];
hold2[] = Integer.MIN_VALUE;
res1[] = ;
res2[] = ;
for (int i = ; i < prices.length; i++) {
hold1[i] = Math.max(hold1[i - ], - prices[i]);
res1[i] = Math.max(res1[i - ], hold1[i - ] + prices[i]);
hold2[i] = Math.max(hold2[i - ], res1[i - ] - prices[i]);
res2[i] = Math.max(res2[i - ], hold2[i- ] + prices[i]);
}
return Math.max(res1[prices.length - ], res2[prices.length - ]);
}
188. Best Time to Buy and Sell Stock IV
要求：Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
最多交易k次：
public class Solution {
public int maxProfit(int k, int[] prices) {
if (k >= prices.length / ) {
return getMax(prices);
}
int[][] hold = new int[prices.length][k + ];
int[][] unhold = new int[prices.length][k + ];
hold[][] = -prices[];
for (int i = ; i < prices.length; i++) {
hold[i][] = Math.max(hold[i - ][], -prices[i]);
}
for (int j = ; j <= k; j++) {
hold[][j] = -prices[];
}
for (int i = ; i < prices.length; i++) {
for (int j = ; j <= k; j++) {
hold[i][j] = Math.max(hold[i - ][j], unhold[i - ][j] - prices[i]);
unhold[i][j] = Math.max(unhold[i - ][j], hold[i - ][j - ] + prices[i]);
}
}
return Math.max(hold[prices.length-][k], unhold[prices.length - ][k]);
}
public int getMax(int[] prices) {
int result = ;
for (int i = ; i < prices.length; i++) {
if (prices[i] - prices[i - ] > ) {
result += prices[i] - prices[i - ];
}
}
return result;
}
}
連結清單反轉問題
隻是需要兩個額外的Node結點即可。
數組中出現次數大于n / 2的，投票處理
*Arrays.copyOf(result, index)不包含index
pow（x, n）
對n減半，對x進行平方，遞歸調用
231. Power of Two
判斷一個數是不是2的次方
public boolean isPowerOfTwo(int n) {
if( n<=){
return false;
}
return (n&(n-))==;
}
是不是3的次方
public boolean isPowerOfThree(int n) {
if(n>)
while(n%==) n /= ;
return n==;
}
是不是 4的次方
public boolean isPowerOfFour(int num) {
while (num> && (num&)==)
num>>=;
return num==;
}
連結清單快排java版本
這個雙指針的問題，注意q指針每次都先行一步
public static void quickSort(ListNode head, ListNode tail) {
if (head != tail) {
ListNode partion = getPartion (head, tail);
quickSort(head, partion);
quickSort(partion.next, tail);
}
}
public static ListNode getPartion(ListNode beg, ListNode end) {
int key = beg.val;
ListNode p = beg;
ListNode q = beg.next;// quick
while (q != end) {
if (q.val < key) {
p = p.next;
swap(p, q);
}
q = q.next;
}
swap(beg, p);
return p;
}
public static void swap(ListNode p, ListNode q) {
int temp = p.val;
p.val = q.val;
q.val = temp;
}
![7大排序算法詳解+java實作[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)