8 Kasım 2019 Cuma

LeetCode

Notlar
- Array ile çalışırken benden önceki eleman var mı kontrolü için index'i 1'den başlatırız

- Array ile çalışırken ilk elemanı atlamak için şöyle yaparız. Diğer elemanlar için de koşul sağlanıyorsa if çalışır
for (int index = 1; ...){
  if (index == 1 || asıl istenen koşul){...}
}
- Array ile çalışırken benden iki önce eleman var mı kontrolü için şöyle yaparız. Eğer index 0 ve 1 ise sol taraf false çıkacağı için bu if'e girmez
if (index -2 <0 || asıl istenen koşul) {...}

HashMap Kullanımı
Örnek
LeetCode 1 : 1. Two Sum probleminde array üzerinde dolaşırken bir HashMap'a bir nesne ekleme ve bunu sorgulama metodları kullanılıyor.

Örnek
LeetCode 535: Encode and Decode TinyURL probleminde verilen bir URL 6 defa random bir karakter üretilerek küçültülüyor. Random karakter İngilizcedeki büyük veya küçük harflerden birisi ya da bir rakam. Bu da toplam 10 rakam + 26 büyük + 26 küçük toplam 62 karakter ediyor. 

62^6 ile de 56,800,235,584 gibi büyük bir sayı elde ediyoruz. Yani 56 milyar küsur tane URL encode edilebilir.

C++ çözümü burada. Java çözümü burada

HashSet Kullanımı
Örnek
LeetCode 217. Contains Duplicate set kullanımını ölçüyor.

Stack Kullanımı
Örnek - Basit Bir Hesap Makinesi
Şöyle yaparız. Burada Stack veya aslında Deque kullanımı ölçülüyor.
public class Solution {
    
  Stack<Integer> numberStack = new Stack<>();
  Stack<Character> operatorStack = new Stack<>();
    
            
  public calculate(String exp){
        
    while(!operatorStack.isEmpty()){
      performOperation();
    }
    return numberStack.pop();
  }
}
Matris (Matrix) Dolaşma

Örnek
36. Valid Sudoku bir matrix dolaşma sorusu. Matrix C++ ile şöyle temsil ediliyor
std::vector<std::vector<char>> v 
- Matrix'te arama yapmak için row + column + veri üçlüsünü kullanmak lazım. Bu üçlüyü HashSet içinde saklamak için string'i belli bir encoding'den geçirmek gerekiyor. Encoding örnekleri ve çözüm burada

- Matrix'i dolaşırken Locality Sensitive Hashing de kullanılıyor. Yani matrix'i alt kutulara bölüyoruz. Alt kutuların büyüklüğü 3x3 olduğu için "row/3",  "colum/3" yapıyoruz. Bu iki değer yine enconding'den geçirilerek arama yapılıyor.


Cycle Detection
Cycle Detection yazısına taşıdım

Sıralama
LeetCode Sıralama yazısına taşıdım

XOR
Örnek
Bir dizide çift olmayan sayısı bulmak için şöyle yaparız
int a = 0;
for (int i = 0; i < nums.length; i++) {
    a ^= nums[i];
}
return a;
Açıklaması şöyle. Aynı sayısı kendisi ile XOR yaparsak 0 elde ederiz. Eğer bir sayının çifti yoksa kendisini verir. Bu durumda çift olmayan sayısı buluruz.
3 ^ 5 ^ 3 ^ 7 ^ 5 = (3 ^ 3) ^ (5 ^ 5) ^ 7 = 0 ^ 0 ^ 7 = 7
Örnek
Bir dizideki eksik sayısı bulmak için şöyle yaparız.
3   6   5   2   7  <--- stepwise accumulated: 3=1+2, 5=1+4, 7=1+2+4
Burada aynı her bit 1^1 işlemi sonucunda 0 olur. Farlı her bit ise 1 olarak kalır.
011
110
101
111
Sonuç olarak 110 alırı. Yani 4

Hiç yorum yok:

Yorum Gönder