Eric's Blogs

public int GetNumberOfK(int[] array, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i : array) {
        if (map.containsKey(i)) {
            map.put(i, map.get(i) + 1);
        } else {
            map.put(i, 1);
        }
    }
    if (map.containsKey(k)) {
        return map.get(k);
    } else {
        return 0;
    }
}

import java.util.Arrays;
public class Solution {

    public int GetNumberOfK(int [] array , int k) {
        int index = Arrays.binarySearch(array, k);
        if(index<0)return 0;
        int cnt = 1;
        for(int i=index+1; i < array.length && array[i]==k;i++)
            cnt++;
        for(int i=index-1; i >= 0 && array[i]==k;i--)
            cnt++;
        return cnt;

    }
}

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    for (ListNode p1 = pHead1; p1 != null; p1 = p1.next) {
        for (ListNode p2 = pHead2; p2 != null; p2 = p2.next) {
            if (p1 == p2) {
                return p1;
            }
        }
    }
    return null;
}

public int Sum_Solution(int n) {
        int tmp = n;
        boolean b=tmp >0 && (1==(tmp += (Sum_Solution(n - 1))));
        return tmp;
    }

public static int Sum_Solution(int n) {
        int sum = n;
        boolean flag = (sum > 0) && ((sum += Sum_Solution(--n)) > 0);
        return sum;
    }

public static int Sum_Solution1(int n) {
       return (int) (Math.pow(n, 2) + n) >> 1;
}

public static int Sum_Solution2(int n) {
        int res = 0;
        int a = n;//若a=2=10
        int b = n + 1;//b=3=11
        while (a != 0) {
            if ((a & 1) == 1)//a在第二位==1的时候才更新res=0+110=6
                res += b;
            a >>= 1;//a右移1位 1
            b <<= 1;//b左移动1位 110
        }
        return res>>=1;//n(n+1)/2     
 }

public int Sum(int n) {
       int res = multi(n, n + 1);//n*(n-1)
       return res>>=1;//n*(n-1)/2
   }
    
   private int multi(int a, int b) {
       int res = 0;
       //循环体内部, if ((a & 1) == 1), res += b;
       boolean flag1 = ((a & 1) == 1) && (res += b) > 0;
       a >>= 1;
       b <<= 1;
       // while (a != 0) {}循环条件
       boolean flag2 = (a != 0) && (res += multi(a,b)) > 0 ;
       return res;
   }

String version = "1.5.1"; 
boolean processOrder() {   
    return true; 
}

public class Logger {
   private String format;
   public String getFormat() {
      return this.format;
   }
   public void setFormat(String format) {
      this.format = format;
   }
}

class AudioPlayer {
   protected boolean openSpeaker(Speaker sp) {
      // 实现细节
   }
}
 
class StreamingAudioPlayer extends AudioPlayer {
   protected boolean openSpeaker(Speaker sp) {
      // 实现细节
   }
}

public class InstanceCounter {
   private static int numInstances = 0;
   protected static int getCount() {
      return numInstances;
   }
 
   private static void addInstance() {
      numInstances++;
   }
 
   InstanceCounter() {
      InstanceCounter.addInstance();
   }
 
   public static void main(String[] arguments) {
      System.out.println("Starting with " +
      InstanceCounter.getCount() + " instances");
      for (int i = 0; i < 500; ++i){
         new InstanceCounter();
          }
      System.out.println("Created " +
      InstanceCounter.getCount() + " instances");
   }
}

public class Test{
  final int value = 10;
  // 下面是声明常量的实例
  public static final int BOXWIDTH = 6;
  static final String TITLE = "Manager";
 
  public void changeValue(){
     value = 12; //将输出一个错误
  }
}

public class Test{
    public final void changeName(){
       // 方法体
    }
}

public final class Test {   
	// 类体 
}

abstract class Caravan{
   private double price;
   private String model;
   private String year;
   public abstract void goFast(); //抽象方法
   public abstract void changeColor();
}

public transient int limit = 55;   // 不会持久化 
public int b; // 持久化

public class MyRunnable implements Runnable
{
    private volatile boolean active;
    public void run()
    {
        active = true;
        while (active) // 第一行
        {
            // 代码
        }
    }
    public void stop()
    {
        active = false; // 第二行
    }
}

Public static class RainbowColor { 
    
   // 红橙黄绿青蓝紫七种颜色的常量定义
   public static final int RED = 0; 
   public static final int ORANGE = 1; 
   public static final int YELLOW = 2; 
   public static final int GREEN = 3; 
   public static final int CYAN = 4; 
   public static final int BLUE = 5; 
   public static final int PURPLE = 6; 
}

enum RainbowColor { RED, ORANGE, YELLOW, GREEN, CYAN, BLUE, PURPLE }

// 定义一周七天的枚举类型         
public enum WeekDayEnum { Mon, Tue, Wed, Thu, Fri, Sat, Sun } 
 
// 读取当天的信息
WeekDayEnum today = readToday(); 
 
// 根据日期来选择进行活动
switch(today) { 
 Mon: do something; break; 
 Tue: do something; break; 
 Wed: do something; break; 
 Thu: do something; break; 
 Fri: do something; break; 
 Sat: play sports game; break; 
 Sun: have a rest; break; 
}

// 定义 RSS(Really Simple Syndication) 种子的枚举类型
public enum NewsRSSFeedEnum { 
   // 雅虎头条新闻 RSS 种子
   YAHOO_TOP_STORIES("<a href="http://rss.news.yahoo.com/rss/topstories"><code>http://rss.news.yahoo.com/rss/topstories</code></a>"), 
    
   //CBS 头条新闻 RSS 种子
   CBS_TOP_STORIES("<a href="http://feeds.cbsnews.com/CBSNewsMain?format=xml"><code>http://feeds.cbsnews.com/CBSNewsMain?format=xml</code></a>"), 
    
   // 洛杉矶时报头条新闻 RSS 种子
   LATIMES_TOP_STORIES("<a href="http://feeds.latimes.com/latimes/news?format=xml"><code>http://feeds.latimes.com/latimes/news?format=xml</code></a>"); 
        
   // 枚举对象的 RSS 地址的属性
   private String rss_url; 
        
   // 枚举对象构造函数
   private NewsRSSFeedEnum(String rss) { 
       this.rss_url = rss; 
   } 
        
   // 枚举对象获取 RSS 地址的方法
   public String getRssURL() { 
       return this.rss_url; 
   } 
}

// 定义一个一周七天的枚举类型
package example.enumeration.codes; 
 
public enum WeekDayEnum { 
   Mon(1), Tue(2), Wed(3), Thu(4), Fri(5), Sat(6), Sun(7); 
 
   private int index; 
 
   WeekDayEnum(int idx) { 
       this.index = idx; 
   } 
 
   public int getIndex() { 
       return index; 
   } 
} 
 
// 客户端程序，将一个枚举值通过网络传递给服务器端
package example.enumeration.codes; 
 
import java.io.IOException; 
import java.io.ObjectOutputStream; 
import java.io.OutputStream; 
import java.net.InetSocketAddress; 
import java.net.Socket; 
import java.net.UnknownHostException; 
 
public class EnumerationClient { 
 
   public static void main(String... args) throws UnknownHostException, IOException { 
       Socket socket = new Socket(); 
 // 建立到服务器端的连接
       socket.connect(new InetSocketAddress("127.0.0.1", 8999)); 
   // 从连接中得到输出流
       OutputStream os = socket.getOutputStream(); 
       ObjectOutputStream oos = new ObjectOutputStream(os); 
 // 将星期五这个枚举值传递给服务器端
       oos.writeObject(WeekDayEnum.Fri); 
       oos.close(); 
       os.close(); 
       socket.close(); 
   } 
} 
 
// 服务器端程序，将从客户端收到的枚举值应用到逻辑处理中
package example.enumeration.codes; 
 
import java.io.*; 
import java.net.ServerSocket; 
import java.net.Socket; 
 
public class EnumerationServer { 
 
   public static void main(String... args) throws IOException, ClassNotFoundException { 
       ServerSocket server = new ServerSocket(8999); 
 // 建立服务器端的网络连接侦听
       Socket socket = server.accept(); 
 // 从连接中获取输入流
       InputStream is = socket.getInputStream(); 
       ObjectInputStream ois = new ObjectInputStream(is); 
 // 读出客户端传递来的枚举值
       WeekDayEnum day = (WeekDayEnum) ois.readObject(); 
 // 用值比较方式来对比枚举对象
       if (day == WeekDayEnum.Fri) { 
           System.out.println("client Friday enum value is same as server's"); 
       } else if (day.equals(WeekDayEnum.Fri)) { 
           System.out.println("client Friday enum value is equal to server's"); 
       } else { 
           System.out.println("client Friday enum value is not same as server's"); 
       } 
        
 // 用 switch 方式来比较枚举对象
       switch (day) { 
           case Mon: 
               System.out.println("Do Monday work"); 
               break; 
           case Tue: 
               System.out.println("Do Tuesday work"); 
               break; 
           case Wed: 
               System.out.println("Do Wednesday work"); 
               break; 
           case Thu: 
               System.out.println("Do Thursday work"); 
               break; 
           case Fri: 
               System.out.println("Do Friday work"); 
               break; 
           case Sat: 
               System.out.println("Do Saturday work"); 
               break; 
           case Sun: 
               System.out.println("Do Sunday work"); 
               break; 
           default: 
               System.out.println("I don't know which is day"); 
               break; 
       } 
        
       ois.close(); 
       is.close(); 
       socket.close(); 
   } 
}

enum WeekDayEnum { Mon, Tue, Wed, Thu, Fri, Sat, Sun }

for(WeekDayEnum day : EnumSet.range(WeekDayEnum.Mon, WeekDayEnum.Fri)) { 
    System.out.println(day); 
}

EnumSet<WeekDayEnum> subset = EnumSet.of(WeekDayEnum.Mon, WeekDayEnum.Wed); 
     for (WeekDayEnum day : subset) { 
         System.out.println(day);  
     }

// 定义一个 EnumMap 对象，映射表主键是日期枚举类型，值是颜色枚举类型
private static Map<WeekDayEnum, RainbowColor> schema = 
           new EnumMap<WeekDayEnum, RainbowColor>(WeekDayEnum.class); 
    
static{ 
   // 将一周的每一天与彩虹的某一种色彩映射起来
   for (int i = 0; i < WeekDayEnum.values().length; i++) { 
       schema.put(WeekDayEnum.values()[i], RainbowColor.values()[i]); 
   } 
} 
System.out.println("What is the lucky color today?"); 
System.out.println("It's " + schema.get(WeekDayEnum.Sat));

ArrayList<String> list = new ArrayList<>();
TreeSet<String> set = new TreeSet<>();

public ArrayList<String> Permutation(String str) {
    if (str == null || str.length() == 0) {
        return list;
    }
    getPermutation(new String(), str);
    for (String s : set) {
        list.add(s);
    }
    return list;
}
private void getPermutation(String ordered, String unordered) {
    if (unordered == null || unordered.length() == 0) {
        set.add(ordered);
        return;
    }
    for (int i = 0; i < unordered.length(); i++) {
        getPermutation(ordered + unordered.charAt(i), unordered.substring(0, i) + unordered.substring(i + 1));
    }
}

链接：https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7?f=discussion
来源：牛客网

/**
     * 1、递归算法
     *
     * 解析：http://www.cnblogs.com/cxjchen/p/3932949.html  (感谢该文作者！)
     *
     * 对于无重复值的情况
     *
     * 固定第一个字符，递归取得首位后面的各种字符串组合；
     * 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合； *递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
     *
     * 假如有重复值呢？
     * *由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。
     * 例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。
     * 但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。
     * 由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。
     *
     * 换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，
     * 所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！
     *
     *
     * @param str
     * @return
     */
 
public ArrayList<String> Permutation(String str){
 
        ArrayList<String> list = new ArrayList<String>();
        if(str!=null && str.length()>0){
            PermutationHelper(str.toCharArray(),0,list);
            Collections.sort(list);
        }
        return list;
    }
    private void PermutationHelper(char[] chars,int i,ArrayList<String> list){
        if(i == chars.length-1){
            list.add(String.valueOf(chars));
        }else{
            Set<Character> charSet = new HashSet<Character>();
            for(int j=i;j<chars.length;++j){
                if(j==i || !charSet.contains(chars[j])){
                    charSet.add(chars[j]);
                    swap(chars,i,j);
                    PermutationHelper(chars,i+1,list);
                    swap(chars,j,i);
                }
            }
        }
    }
 
    private void swap(char[] cs,int i,int j){
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
 
/**
     * 2、字典序排列算法
     *
     * 可参考解析： http://www.cnblogs.com/pmars/archive/2013/12/04/3458289.html  （感谢作者）
     *
     * 一个全排列可看做一个字符串，字符串可有前缀、后缀。
     * 生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。
     * 这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。
     *
     * [例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的987654321，
     * 从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。
     *
     * 【例】 如何得到346987521的下一个
     * 1，从尾部往前找第一个P(i-1) < P(i)的位置
     * 3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1
     * 最终找到6是第一个变小的数字，记录下6的位置i-1
     *
     * 2，从i位置往后找到最后一个大于6的数
     * 3 4 6 -> 9 -> 8 -> 7 5 2 1
     * 最终找到7的位置，记录位置为m
     *
     * 3，交换位置i-1和m的值
     * 3 4 7 9 8 6 5 2 1
     * 4，倒序i位置后的所有数据
     * 3 4 7 1 2 5 6 8 9
     * 则347125689为346987521的下一个排列
     *
     * @param str
     * @return
     */
 
public ArrayList<String> Permutation2(String str){
        ArrayList<String> list = new ArrayList<String>();
        if(str==null || str.length()==0){
            return list;
        }
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        list.add(String.valueOf(chars));
        int len = chars.length;
        while(true){
            int lIndex = len-1;
            int rIndex;
            while(lIndex>=1 && chars[lIndex-1]>=chars[lIndex]){
                lIndex--;
            }
            if(lIndex == 0)
                break;
            rIndex = lIndex;
            while(rIndex<len && chars[rIndex]>chars[lIndex-1]){
                rIndex++;
            }
            swap(chars,lIndex-1,rIndex-1);
            reverse(chars,lIndex);
 
            list.add(String.valueOf(chars));
        }
 
        return list;
    }
 
    private void reverse(char[] chars,int k){
        if(chars==null || chars.length<=k)
            return;
        int len = chars.length;
        for(int i=0;i<(len-k)/2;i++){
            int m = k+i;
            int n = len-1-i;
            if(m<=n){
                swap(chars,m,n);
            }
        }
 
    }

public boolean duplicate(int numbers[], int length, int[] duplication) {
    if (numbers == null || numbers.length == 0) {
        return false;
    }
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < numbers.length; i++) {
        if (set.contains(numbers[i])) {
            duplication[0] = numbers[i];
            return true;
        } else {
            set.add(numbers[i]);
        }
    }
    return false;
}

public int FirstNotRepeatingChar(String str) {
    if (str == null || str.length() == 0) {
        return -1;
    }
    /** K:字符 V:下标，出现多处下标置为-1 */
    Map<Character, Integer> countMap = new LinkedHashMap<>();
    int index = 0;
    for (char c : str.toCharArray()) {
        if (countMap.containsKey(c)) {
            countMap.put(c, -1);
        } else {
            countMap.put(c, index);
        }
        index++;
    }
    index = 0;
    for (Character character : countMap.keySet()) {
        int id = countMap.get(character);
        if (id != -1) {
            return id;
        }
        index++;
    }
    return -1;
}

public int TreeDepth(TreeNode root) {
    if (root==null){
        return 0;
    }
    return Math.max(TreeDepth(root.left)+1,TreeDepth(root.right)+1);
}