牛客のいくつかの面白い小題
21913 ワード
以下のいくつかの小さな問題は少し面白いと感じて、一部のコードは自分で書いたので、一部は他の人を総括してあるいは他の人を引用して、コードは少し不足してあるいはその他の解法と最適化があって、指摘を歓迎して、一緒に進歩します.
よく問題を作って、レンガを運ぶように努力して、いつか嫁と結婚することができます.若者、むやみに考えないでください.
/**
* : , 。 。
* : set, , , , 。
*/
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
Set set = new HashSet();
for(int i = 0; i < array.length; i++){
//
if (set.contains(array[i])){
set.remove(array[i]);
}else {
set.add(array[i]);
}
}
Integer[] temp = new Integer[2];
set.toArray(temp);
num1[0] = temp[0];
num2[0] = temp[1];
}
/**
* 。
* @param m m
* @param n n
* @return
*/
public int countBitDiff(int m, int n){
// , 0 ,
String string = Integer.toBinaryString(m^n);
string = string.replace("0", "");
return string.length();
}
/**
* , 。
* : map , , map , 。
* @param pHead1
* @param pHead2
* @return ListNode
*/
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode currentOne = pHead1;
ListNode currentTwo = pHead2;
Map map = new HashMap();
while (currentOne != null){
// map
map.put(currentOne, null);
currentOne = currentOne.next;
}
while (currentTwo != null){
//
if (map.containsKey(currentTwo)){
return currentTwo;
}else {
currentTwo = currentTwo.next;
}
}
return null;
}
/**
* : , ;
* , 5 , ? 5 ?
*/
public static void getJourney(int high)
{
double back = high;
double sum = high;
for(int i = 0; i < 5; i++){
sum += back;
back = back/2;
}
System.out.println(sum);
System.out.println(back);
}
/**
* “*”, 。
* : *, ** 。( , )
*/
public static String MarkNum(String pInStr)
{
StringBuffer stringBuffer = new StringBuffer();
for(int i = 0; i < pInStr.length(); i++){
if (pInStr.charAt(i) >= 48 && pInStr.charAt(i) <= 57){
stringBuffer.append("*" + pInStr.charAt(i) + "*");
}else {
stringBuffer.append(pInStr.charAt(i));
}
}
System.out.println(stringBuffer.toString());
return stringBuffer.toString().replace("**", "");
}
/**
* ,
* , -1。
* : map key, value, 。
*/
public static void PrintSingleChar(String string){
Map map = new HashMap();
for (int i = 0; i < string.length(); i++){
if (map.containsKey(string.charAt(i))){
// 1
map.put(string.charAt(i), map.get(string.charAt(i))+1);
}else {
// value=1
map.put(string.charAt(i), 1);
}
}
for (int i = 0; i < string.length(); i++){
if (map.get(string.charAt(i)) == 1){
System.out.println(string.charAt(i));
return;
}
}
System.out.println("-1");
}
/**
* , k 。
* : , k-1 k 。
* : , k,k 0, null。
*/
public ListNode FindKthToTail(ListNode head,int k) {
ListNode temp = head;
Stack stack = new Stack();
//
while (temp != null){
stack.push(temp);
temp = temp.next;
}
if (!stack.isEmpty() && stack.size() >= k && k > 0){
for (int i = k-1; i > 0; i--){
stack.pop();
}
return stack.pop();
}else {
return null;
}
}
/**
* 1~13 1 , 100~1300 1 ?
* 1~13 1 1、10、11、12、13 6 ,
* 。ACMer , ,
* 1 。
* : , 。
*/
public static int NumberOf1Between1AndN_Solution(int n) {
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0; i <= n; i++){
stringBuffer.append(i);
}
int count = 0;
for (int i = 0; i < stringBuffer.length(); i++){
if(stringBuffer.charAt(i) == '1'){
count++;
}
}
return count;
}
/**
* 。
* : ( , ), 。
*/
public static int GetNumberOfK(int [] array , int k) {
int start = GetLower(array, k);
int end = GetUper(array, k);
return end - start + 1;
}
// k
public static int GetLower(int [] array , int k){
int start = 0;
int end = array.length-1;
int mid = (start + end)/2;
while (start <= end){
if (array[mid] < k){
start = mid + 1;
}else {
end = mid - 1;
}
mid = (start + end)/2;
}
return start;
}
// k
public static int GetUper(int[] array, int k){
int start = 0;
int end = array.length-1;
int mid = (start + end)/2;
while (start <= end){
if (array[mid] <= k){
start = mid + 1;
}else {
end = mid - 1;
}
mid = (start + end)/2;
}
return end;
}
/**
* , 。
* : , , ,
* Set,
*/
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if (pHead == null){
return null;
}else {
Set set = new HashSet();
ListNode listNode = pHead;
while (listNode != null){
if(!set.add(listNode.val)){
return listNode;
}
listNode = listNode.next;
}
return null;
}
}
/**
* (ROL),
* , 。 S,
* K 。 , S=”abcXYZdef”, 3 ,
* “XYZdefabc”。 ?OK, !
* @param str
* @param n
* @return
*/
public static String LeftRotateString(String str,int n) {
int count;
//
if (str.length() == 0){
return "";
}
// n
if (n > str.length()){
count = n%str.length(); // str , ,
}else {
count = n;
}
return str.substring(count) + str.substring(0, count);
}
/**
* , , , 。
* , 。
* string stringA string stringB, bool, 。
* 5000。
* : 256, 256 , ASCII , ,
* AB 。
* @param stringA
* @param stringB
* @return
*/
public boolean checkSam(String stringA, String stringB) {
//
if (stringA == null || stringB == null){
return false;
}
/**
*
* false
*/
if (stringA.length() != stringB.length()){
return false;
}
int[] strA = new int[256];
int[] strB = new int[256];
for(int i = 0; i < stringA.length(); i++){
strA[stringA.charAt(i)]++;
strB[stringB.charAt(i)]++;
}
// ,
for (int i = 0; i < 256; i++){
if (strA[i] != strB[i]){
return false;
}
}
return true;
}
/**
* , , 。
* , “aabcccccaaa” “a2b1c5a3”。 , 。
* string iniString ( 10000), , string, 。
* @param iniString
* @return
*/
public static String zipString(String iniString) {
StringBuffer stringBuffer = new StringBuffer();
int count = 1;
for(int i = 0; i < iniString.length()-1; i++){
if(iniString.charAt(i) == iniString.charAt(i+1)){
count++;
}else{
stringBuffer.append(iniString.charAt(i));
stringBuffer.append(count);
count = 1;
}
}
//System.out.println("stringBuffer = " + stringBuffer.toString());
stringBuffer.append(iniString.charAt(iniString.length()-1));
stringBuffer.append(count);
//System.out.println("s.length = " + stringBuffer.length() + ", s = " + stringBuffer.toString());
if(stringBuffer.length() >= iniString.length()){
return iniString;
}else{
return stringBuffer.toString();
}
}
/**
* , N 0, 。
* N int[][](C++ vector>)mat n,
* int[][] , n 300, int 。
*/
public int[][] clearZero(int[][] mat, int n) {
Set setX = new HashSet();
Set setY = new HashSet();
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(mat[i][j] == 0){
setX.add(i);
setY.add(j);
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(setX.contains(i) || setY.contains(j)){
mat[i][j] = 0;
}
}
}
return mat;
}
よく問題を作って、レンガを運ぶように努力して、いつか嫁と結婚することができます.若者、むやみに考えないでください.